Return to Question

Suppose have a probability distribution over space of $n$ binary variables. We can view logarithm of the density as a function $f$ from $\{-1,1\}^n$ to $\mathbb{R}$. Fourier expansion of the $f$ can be viewed as expansion of $f$ in terms of square free monomials.

Given a sample from this density, we'd like to find Fourier coefficients that approximate true density. For real-life densities, fit is usually done by adjusting a small number of low order coefficients to fit the sample and fixing the rest to 0. Why does it work better than adjusting high-order coefficients?

This was inspired by Gil Kalai's question on CSTheory.

Originally I thought it's because real life distributions have high entropy, but it seems that restricting entropy, or any symmetric function of the density is not enough to break symmetry between different coefficients.

Here is a plot of all Fourier coefficients (0th order one dropped) realizable by empirical densities of 20 samples of 2-variable density. Z-axis, corresponds to $x_1 x_2$ term, $x,y$ axes are $x_1$ and $x_2$ terms.  http://yaroslavvb.com/upload/save/log-linear-simplex.png

Suppose have a probability distribution over space of $n$ binary variables. We can view logarithm of the density as a function $f$ from $\{-1,1\}^n$ to $\mathbb{R}$. Fourier expansion of the $f$ can be viewed as expansion of $f$ in terms of square free monomials.

Given a sample from this density, we'd like to find Fourier coefficients that approximate true density. For real-life densities, fit is usually done by adjusting a small number of low order coefficients to fit the sample and fixing the rest to 0. Why does it work better than adjusting high-order coefficients?

This was inspired by Gil Kalai's question on CSTheory.

Originally I thought it's because real life distributions have high entropy, but it seems that restricting entropy, or any symmetric function of the density is not enough to break symmetry between different coefficients.

Here is a plot of all Fourier coefficients (0th order one dropped) realizable by empirical densities of 20 samples of 2-variable density. Z-axis, corresponds to $x_1 x_2$ term, $x,y$ axes are $x_1$ and $x_2$ terms.

^(source)

Suppose have a probability distribution over space of $n$ binary variables. We can view logarithm of the density as a function $f$ from $\{-1,1\}^n$ to $\mathbb{R}$. Fourier expansion of the $f$ can be viewed as expansion of $f$ in terms of square free monomials.

Given a sample from this density, we'd like to find Fourier coefficients that approximate true density. For real-life densities, fit is usually done by adjusting a small number of low order coefficients to fit the sample and fixing the rest to 0. Why does it work better than adjusting high-order coefficients?

This was inspired by Gil Kalai's question on CSTheory.

Originally I thought it's because real life distributions have high entropy, but it seems that restricting entropy, or any symmetric function of the density is not enough to break symmetry between different coefficients.

Here is a plot of all Fourier coefficients (0th order one dropped) realizable by empirical densities of 20 samples of 2-variable density. Z-axis, corresponds to $x_1 x_2$ term, $x,y$ axes are $x_1$ and $x_2$ terms. http://yaroslavvb.com/upload/save/log-linear-simplex.png

Suppose have a probability distribution over space of $n$ binary variables. We can view logarithm of the density as a function $f$ from $\{-1,1\}^n$ to $\mathbb{R}$. Fourier expansion of the $f$ can be viewed as expansion of $f$ in terms of square free monomials.

Given a sample from this density, we'd like to find Fourier coefficients that approximate true density. For real-life densities, fit is usually done by adjusting a small number of low order coefficients to fit the sample and fixing the rest to 0. Why does it work better than adjusting high-order coefficients?

This was inspired by Gil Kalai's question on CSTheory.

Originally I thought it's because real life distributions have high entropy, but it seems that restricting entropy, or any symmetric function of the density is not enough to break symmetry between different coefficients.

Here is a plot of all Fourier coefficients (0th order one dropped) realizable by empirical densities of 20 samples of 2-variable density. Z-axis, corresponds to $x_1 x_2$ term, $x,y$ axes are $x_1$ and $x_2$ terms. http://yaroslavvb.com/upload/save/log-linear-simplex.png

Suppose have a probability distribution over space of $n$ binary variables. We can view logarithm of the density as a function $f$ from $\{-1,1\}^n$ to $\mathbb{R}$. Fourier expansion of the $f$ can be viewed as expansion of $f$ in terms of square free monomials.

Given a sample from this density, we'd like to find Fourier coefficients that approximate true density. For real-life densities, fit is usually done by adjusting a small number of low order coefficients to fit the sample and fixing the rest to 0. Why does it work better than adjusting high-order coefficients?

Suppose have a probability distribution over space of $n$ binary variables. We can view logarithm of the density as a function $f$ from $\{-1,1\}^n$ to $\mathbb{R}$. Fourier expansion of the $f$ can be viewed as expansion of $f$ in terms of square free monomials.

Given a sample from this density, we'd like to find Fourier coefficients that approximate true density. For real-life densities, fit is usually done by adjusting a small number of low order coefficients to fit the sample and fixing the rest to 0. Why does it work better than adjusting high-order coefficients?

This was inspired by Gil Kalai's question on CSTheory.

Originally I thought it's because real life distributions have high entropy, but it seems that restricting entropy, or any symmetric function of the density is not enough to break symmetry between different coefficients.

Here is a plot of all Fourier coefficients (0th order one dropped) realizable by empirical densities of 20 samples of 2-variable density. Z-axis, corresponds to $x_1 x_2$ term, $x,y$ axes are $x_1$ and $x_2$ terms. http://yaroslavvb.com/upload/save/log-linear-simplex.png