7
$\begingroup$

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)

Improve this question
$\endgroup$
4
  • $\begingroup$ I say it's because the Walsh-Hadamard transform (en.wikipedia.org/wiki/Hadamard_transform) can be thought of as a low-order approximation to the DFT. $\endgroup$
    – Steve Huntsman
    Commented Nov 30, 2010 at 19:44
  • $\begingroup$ Not sure why this suggests that low-order coefficients are better...without assumptions on the target function, aren't all Fourier basis functions equivalent? $\endgroup$
    – Yaroslav Bulatov
    Commented Nov 30, 2010 at 21:15
  • 1
    $\begingroup$ Heuristically the lower the coefficient the rougher the structure it represents. Of course you want at first a rough impression of a picture, not the details (= high coefficients). $\endgroup$
    – hänsel
    Commented Aug 20, 2017 at 13:06
  • 1
    $\begingroup$ Why log of density? Why not the density itself? $\endgroup$
    – kodlu
    Commented Aug 21, 2017 at 23:04

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .