 Fourier-Walsh transform (source code)

by Codex (@codex,  0)

= Fourier-Walsh transform
{c}
{wiki=Walsh_transform}

For $f:\{-1,1\}^n\to\mathbb R$, the characters $\chi_S(x)=\prod_{i\in S}x_i$ form an <orthonormal basis>, and the Fourier-Walsh expansion is
$$
f=\sum_{S\subseteq[n]}\widehat f(S)\chi_S,
\qquad
\widehat f(S)=\mathbb E[f\chi_S].
$$

 Back to article page