Primer on Fourier Analysis Dana Moshkovitz Princeton University and The Institute for Advanced Study Fourier Analysis in Theoretical Computer Science Fourier Analysis in Theoretical Computer Science (Unofficial List) The Fourier Magic Fourier Analysis
something that looks scary to analyze bunch of (in)equalities Today: Explain the Fourier Magic What is it? Why is it useful? What does it do? When to use it?
What do we know about it? Its Just a Different Way to Look at Functions Its Changing Basis Background: Real/complex functions form vector space Idea: Represent functions in Fourier basis, which is the basis of the shift operators (representation by frequency). Advantage: Convolution (complicated
global operation on functions) becomes simple (local) in Fourier basis Generality: Here will only consider the Boolean case very-special case Fourier Basis (Boolean Cube Case) Boolean cube: additive group Z2n Space of functions: Z2n. Inner product space where f,g=EEx[f(x)g(x)]. Characters: (x+y)=E(x)(y)
Foundations Claim (Characterization): The characters are the eigenvectors of the shift operators Ssf(x) f(x+s). Corollary (Basis): The characters form an orthonormal basis. Claim (Explicit): The characters are the functions S(x) =E (-1) x for S[n]. iS i Fourier Transform =E Polynomial Expansion Fourier coefficients: f^(S) =E f,S.
Note: f^()=EEx[f(x)] Polynomial expansion: substitute yi=E(-1)x i f(y1,,yn) =E S[n]f^(S)i2Syi Fourier transform: f f^ level |S| The Fourier Spectrum
Degree-k Polynomial |S| 0 k k-Junta |S| 0 k
Orthonormal Bases Parseval Identity (generalized Pythagorean Thm): For any f, S(f^(S))2 =E Ex[ (f (x))2] So, for Boolean f:{1}n{1}, we have: x(f^(x))2 =E 1 In general, for any f,g, f,g =E 2nf^,g^ Convolution Convolution:
(f*g)(x) =E Ey[f(y)g(x-y)] Example Weighted average: (f*w)(0) =E Ey[f(y)w(y)] Convolution in Fourier Basis Claim: For any f,g, (f*g)^ f^g^ Proof: By expanding according to definition. Things You Can Do with Convolution Parts of The Spectrum
Variance: Varx[f(x)] =E Ex[f(x)2] - Ex[f(x)]2 =E S; f^(S)2 Influence of ith variable: Infi(f) =E Px[f(x)f(xei)] =E S3i f^(S)2 Smoothening f Perturbation: x y : for each i, yi =E xi with probability 1- yi =E 1-xi otherwise Tf(x) =E Ex y[f(y)]
Convolution: Tf f*P(noise=E) Fourier: (Tf)^ (1-2)|S|f^ Smoothed Function is Close to Low Degree! Tail: Part of |Tf|22 on levels k is: (1-2)2k |f|22 e-ck Hence, weight on levels C 1/ log 1/
Hypercontractivity Theorem (Bonami, Gross): For f, for (p-1)/(q-1), |Tf|q |f|p Roughly, and incorrectly ;-): Tf much [in a tougher norm] smoother than f Noise Sensitivity and Stability Noise Sensitivity: NS(f) =E Px y (f(x)f(y)) Correlation: NS(f) =E 2(E[f]-f,Tf)
Stability: Set :=E 1/2-/2 S(f) =E f,Tf Fourier: S(f) =E f^, |S|f^ =E S |S| f^(S)2 Thresholds Are Stablest and Hardness of Approximation What is it? Isoperimetric inequality on noise stability [MOO05]. Applications to hardness of approximation (e.g., Max-Cut
[KKMO04]). Derived from Invariance Principle (extended Central Limit Theorem), used by the [R08] extension of [KKMO04]. Thresholds Are Stablest Theorem [MOO05]: Fix 0<<1. For balanced f (i.e., E[f]=E0) where Infi(f) for all i, S(f) 2/ arcsin + O( (loglog 1/)/log1/) noise stability of threshold functions t(x)=sign(aixi), ai2=1
More Material is s ly a n A r ie r u o F
n o s e s r u o c t n e ll
e c x e e There ar d n a r u in D
it Ir : f o s e g a p e m o
h e h t n o le b availa , t o h
K h s a h b u S , r le d in
K y u G , t u g d ie r F d
Ehu . v e g e R d e d O , ll
e n n o D O n a y R l, e s
s o Elchanan M