A note on Fourier–Walsh Analysis on the Boolean Cube
Permalink
The Fourier–Walsh expansion represents functions on $\Omega_n=\lbrace-1,1\rbrace^n$ in an orthonormal basis of coordinate products. The construction proceeds from a measure space to its Hilbert space $L^2$, then uses orthogonality to derive the coefficients and approximation formulas. On the Boolean cube, the integrals defining the inner product become finite averages.