Primer on Fourier Analysis

Primer on Fourier Analysis

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

Recently Viewed Presentations

  • SIMCA

    SIMCA

    À sa sortie, deux moteurs sont disponibles, un 944 cm3 de 48 ch (5 chevaux fiscaux) et un 1118 cm3 de 60 ch (6 chevaux fiscaux). Ces moteurs non chemisés peuvent fonctionner à l'essence sans plomb 98 RON à partir...
  • Age of Ideologies I - CalvaryABQ.org

    Age of Ideologies I - CalvaryABQ.org

    Age of Ideologies I WWII: Pius XII, Dietrich Bonhöffer, Corrie Ten Boom Post WWI Christianity 1914 World War I started 1918 World War I ended, leaving a much changed Europe Post WWI Europe suffered a massive dechristianization The Roman Catholics...
  • mTrack: High-Precision Passive Tracking Using Millimeter Wave Radios

    mTrack: High-Precision Passive Tracking Using Millimeter Wave Radios

    Especially from small objects, like pen . Costly to deploy substantial nodes. Overview the Basic Idea. 60GHz . ... 2 cm and 6 cm. Event Detection. 7 users. Each provides a 10-sampletraining set. 20~50-sample testing set. Application: Trackpad. Experiment Setup.
  • Casual Pay (CASPA) - Timesheets Introduction  Welcome and

    Casual Pay (CASPA) - Timesheets Introduction Welcome and

    (Xmas, Easter, Anzac Day etc) Submit your timesheets on time to ensure payment in the current pay cycle. ... Enter the number of sessions for each task on each day. If the hours worked were the same or similar to...
  • Ecosystems: What Are They and How Do They Work

    Ecosystems: What Are They and How Do They Work

    Ecosystems: What Are They and How Do They Work. Chapter 3 (Miller and Spoolman, 2010) ... Estuaries. Deep ocean. ... Food web - complex network of interconnected food chains. Figure 3.13A food chain. The arrows show how chemical energy in...
  • SRM in GGF

    SRM in GGF

    Co-Scheduling Network and Storage with TeraPaths and SRM Dantong Yu (BNL) Arie Shoshani (LBNL) September 28-29, 2009 * * ESG main: Downloads to date: 31TB/99,938 files Summary: SRM Methods (partial list) File Movement srmPrepareToGet srmPrepareToPut srmRemoteCopy srmBringOnline srmAddFilesToSpace srmPurgeFrom Space...
  • Bmeu Sox Certification

    Bmeu Sox Certification

    The Promotion is April 1 - June 30, 2014 Mobile Barcode Promotions MAIL AND DIGITAL PERSONALIZATION PROMOTION Offers an upfront discount to encourage mailers to enhance the value of their mail by utilizing technology to create a more relevant, integrated...
  • Signal-Theoretic Representations of Appearance

    Signal-Theoretic Representations of Appearance

    Computer Graphics (Fall 2008) COMS 4160, Lecture 23: Radiosity http://www.cs.columbia.edu/~cs4160