Fourier Analysis

Fourier analysis of ANY real valued boolean fn.

The function space for Uniform distribution

Dimensionality

Take the real space $R^{2^n}$: Not $\mathrm{\infty }$ dimensional Hilbert space. Any real valued boolean function can be represented by a point in this space.

Can also be applied to randomized boolean functions: Alter expectations and probabilites to handle extra randomness.

Inner product

$⟨f,g⟩:=2^{-n}\sum _{x}f(x)g(x)=E_{x{\in }_U{\{\pm 1\}}^n}[f(x)g(x)]$: defined thus scaled to make $\parallel p_S\parallel =\parallel f\parallel =1$. If $S\ne T$: $⟨p_S,p_T⟩=0$.

The basis

These form an alternate basis: Parity functions $p_S$, where S is the index vector.

The standard basis is just $\left\{e_i\right\}$.

Transforms

Discrete Fourier series

Discrete Fourier series for any real valued fn over ${\{\pm 1\}}^n$: $f=\sum _{S\subseteq [n]}\hat{f}(S)p_S$.

${\parallel f\parallel }^2=\sum _S\hat{f}(S{)}^2=E_x[f(x{)}^2]=1$: [Parseval].

Correlation / Discrete Fourier coefficient

Aka Fourier weights on basis vectors or Fourier spectrum. $\hat{f}(S)=⟨f,p_S⟩=E_x[f(x)p_S(x)]=P{r}_x(f(x)=p_S(x))-P{r}_x(p(x)\ne p_S(x))$: so, a measure of how good an approx of f $p_S$ is. $⟨f,g⟩=\sum _S\hat{f}(S)\hat{g}(S)$.

Fourier transform of f

$\hat{f}(S)=2^{-n}\sum _{x}f(x)p_S(x)$. All $\hat{f}(S)$ can be computed in time $O(n{2}^n)$ using FFT alg, given all f(x). \why Inverse FFT can be similarly done. Also see Functional analysis ref.

Estimating coefficients

Estimate all Fourier coefficients of f using FFT

$f_R$: A boolean fn on ${\{0,1\}}^m$: Take random m*n matrix, define $f_R(y)=f(yR)$. Fourier coefficients of $f_R$ are Fourier coefficients of f restricted to a random subspace.

For random non singular m*n R, with m large enough to give good estimation of $Pr(f(x)p_a(x)=1)$ whp. Thence find approximations of all the Fourier coefficients of f by finding all coefficients of $f_R$ using FFT.

Relationship with total influence

$I(f)=\sum _S|S|\hat{f}(S{)}^2$. \why

Relationship with noise sensitivity

Eg: $N{S}_{ϵ}(\underset{i}{\bigwedge }{x}_i)=\frac{2}{2^n}(1-(1-ϵ{)}^n)\approx 0$; For parity: $N{S}_{ϵ}(p_{1^n}(x))=2^{-1}-2^{-1}(1-2ϵ{)}^n\approx 2^{-1}$; note correlation with good/ bad Fourier concentration.

$N{S}_{ϵ}(f)=2^{-1}-2^{-1}\sum _S(1-2ϵ{)}^{|S|}\hat{f}(S{)}^2$:\ $P{r}_{x,y}(f(x)\ne f(y))=2^{-1}-2^{-1}{E}_{x,y}[f(x)f(y)]$; \ But $$E_{x,y}[f(x)f(y)]=E_{x,y}[(\sum _S\hat{f}(S)p_S(x))(\sum _T\hat{f}(T)p_T(x))]=\sum _{S,T}\hat{f}(S)\hat{f}(T)E_{x,y}[p_S(x)p_T(y)]=\sum _S\hat{f}(S)\hat{f}(T)E_{x,y}[p_S(x)p_S(y)]$$; but\ $E_{x,y}[p_S(x)p_S(y)]=\prod _{i}E[p_{\left\{i\right\}}(x)p_{\left\{i\right\}}(y)]=(1-2ϵ{)}^{|S|}$.

$\sum _{|S|\ge {ϵ}^{-1}}\hat{f}(S{)}^2\le N{S}_{ϵ}(f)$, k const: $2N{S}_{ϵ}(f)=1-\sum _S(1-2ϵ{)}^{|S|}\hat{f}(S{)}^2=\sum _S\hat{f}(S{)}^2-\sum _S(1-2ϵ{)}^{|S|}\hat{f}(S{)}^2=\sum _S\hat{f}(S{)}^2(1-(1-2ϵ{)}^{|S|})\approx \sum _S\hat{f}(S{)}^2(1-e^{-2})\ge k^{\prime }\sum _S\hat{f}(S{)}^2$.

As, $\sum _{|S|\ge {ϵ}^{-1}}\hat{f}(S{)}^2\le N{S}_{ϵ}(f)$, any f is $(N{S}_{ϵ}(f),{ϵ}^{-1})$ concentrated.

Concentration in the spectrum

Aka Fourier concentration.

(eps, d) concentrated function f

${\parallel \sum _{|S|>d}\hat{f}(S)p_S\parallel }_2^2\le ϵ$. Visualize with histogram.

If C = polysize DNF formulae, every $c\in C$ is $(ϵ,\log |c|\log \frac{1}{ϵ})$ concentrated. \why

Depth d ckts of size $|c|$: $(ϵ,\log |c|\log \frac{1}{ϵ}{)}^{d-1}$ concentrated. \why

Best fitting d degree polynomial

${\parallel f-g\parallel }^2=\sum _S(\hat{f}(S)-\hat{g}(S){)}^2=E_x[(f(x)-g(x)){)}^2]$; \ so $\underset{g}{min}{E}_x[(f(x)-g(x){)}^2]=\sum _{|S|\le d}\hat{f}(S)p_S$.

t - sparse f

Number of non zero coefficients in f $\le t$.

Sparse approximator for any f

\(\exists \frac{\norm{f}{1}^{2}}{\eps}\) \ sparse g with ${\parallel f-g\parallel }^2\le ϵ$: Remove all \(\hat{f}< \frac{\eps}{\norm{f}{1}}\); then g is \(\frac{\norm{f}{1}^{2}}{\eps}\) sparse: \(\norm{f}{1} = \sum \hat{f}(S)\) and each $\hat{f}(S)$ has min size \(\frac{\eps}{\norm{f}{1}}\). $$\norm{f-g}^{2} = \sum{p_{S} \notin basis(g)} \hat{f}(S)^{2} \leq \ (\max_{p_{S} \notin basis(g)}) \hat{f}(S) \sum_{p_{S} \notin basis(g)} \hat{f}(S) \leq \eps$$.

So, sgn(g) approximates f.

Weak parity learning problem

Let f have a t-heavy Fourier component; then find a t/2 heavy Fourier component. Thence find weakly correlated parity.

KM alg solves this; See colt ref.