Transcript PPT

Fourier Transforms
in Computer Science
Can a function [0,2p]zR be expressed as
a linear combination of sin nx, cos nx ?
If yes, how do we find the coefficients?
If f(x)=
anexp(2pi n x)
S
nZ
then
Fourier’s recipe
1
an =

f(x)exp(-2pi n x) dx
0
The reason that this works is that
the exp(-2pi nx) are orthonormal
with respect to the inner product
1
<f,g> =
 f(x)g(x) dx
0
Given “good” f:[0,1]zC we define
its Fourier transform as f:ZzC
f(n) =
1

f(x)exp(-2pi n x) dx
0
space of
functions
space of
functions
Fourier Transform
space of
functions
space of
functions
Fourier Transform
2
L [0,1]
Plancherel
formula
Parseval’s
identity
isometry
<f,g>
||f||
2
=
-<f,g>
=
||f||2
2
L (Z)
space of
functions
space of
functions
Fourier Transform
convolution
f*g
1

(f*g)(x)=
0
f(y)g(x-y) dy
pointwise
multiplication
-fg
Can be studied in a more general setting:
interval [0,1]
Lebesgue measure
and integral
exp(2pi n x)
form a topological
group G, dual of G
LCA
group G
Haar measure
and integral
characters
of G
continuous
homomorphisms GzC
Fourier coefficients
0
of AC functions
Linial, Mansour, Nisan ‘93
circuit
output
AND
OR
AND
OR
AND
OR
AND
depth=3
AND
size=8
Input:
x1 x2 x3 x1 x2 x3
AC circuits
0
constant depth,
polynomial size
output
AND
OR
AND
OR
AND
OR
AND
depth=3
AND
size=8
Input:
x1 x2 x3 x1 x2 x3
Random restriction of a function
n
f : {0,1} z {0,1}
x 1 x2
...
0
1
x2
(1-p)/2
(1-p)/2
p
xn
Fourier transform over
n
Z2
characters
c A(x)= P (-1)
iA
xi
for each subset
of {1,...,n}
Fourier coefficients
f(A)= P(f(x)=cA(x))-P(f(x)=c A(x))
Hastad switching lemma
o
f AC0z high Fourier coefficients
of a random restriction are zero
with high probability
All coefficients of size >s are 0
with probability at least
1/d 1-1/d s
1-M(5p
size of the circuit
s
depth
)
We can express the Fourier coefficients of the random restriction of f
using the Fourier coefficients of f
|x|
E[r(x)]=p f(x)
- 2
|x|
2
|y|
E[r(x) ]=p S f(x+y) (1-p)
ymx
Sum of the squares of the high
Fourier coefficients of an AC0
Function is small
- 2
1
1/d
S f(x) < 2M exp(- 5e(t/2) )
|x|>s
0
Learning of AC functions
Influence of variables
on Boolean functions
Kahn, Kalai, Linial ‘88
The Influence of variables
If (x i)
The influence of xi on f(x1 ,x2 , …,xn )
set the other variables randomly
the probability that change of x i will
change the value of the function
Examples: for the AND function of n variables
each variable has influence 1/2 n
for the XOR function of n variables
each variable has influence 1
The Influence of variables
If (x i)
The influence of xi in f(x1 ,x2 , …,xn )
set the other variables randomly
the probability that change of x i will
change the value of the function
For balanced f there is a variable
with influence > (c log n)/n
We have a function f i such that
p
I(x i)=||f i || p , and the Fourier coefficients of f i can be expressed
using the Fourier coefficients of f
fi (x)=f(x)-f(x+i)
f i(x) =2f(x)
=0
if i is in x
otherwise
We can express the sum of the
influences using the Fourier
coefficients of f
- 2
S I(x i ) = 4S |x| f(x)
if f has large high Fourier
coefficients then we are happy
How to inspect small coefficients?
Beckner’s linear operators
f(x)
|x|-
a f(x)
a<1
Norm 1 linear operator
1+a2
from L
n
(Z 2 )
2
to L
n
(Z 2 )
Can get bound ignoring high FC
- 2
4/3
|x|
S I(x i ) > 4S |x| f(x) (1/2)
Explicit Expanders
Gaber, Galil ’79 (using Margulis ’73)
Expander
Any (not too big) set of vertices W
has many neighbors (at least (1+a)|W|)
positive
constant
W
Expander
Any (not too big) set of vertices W
has many neighbors (at least (1+a)|W|)
positive
constant
N(W)
W
|N(W)|>(1+a)|W|
Why do we want explicit expanders
of small degree?
extracting randomness
sorting networks
Example of explicit bipartite expander
of constant degree:
Zm x Z m
(x,y)
Zm x Z m
(x,y)
(x+y,y)
(x+y+1,y)
(x,x+y)
(x,x+y+1)
Transform to a continuous problem
M(s(A)-A)+M(t(A)-A)>2cM(A)
2
T
measure
For any measurable A one of the
transformations s:(x,y)z(x+y,y)
and t:(x,y)z(x,x+y) “displaces” it
Estimating the Rayleigh quotient
2
2
of an operator on XmL(T )
Functions with f(0)=0
(T f) (x,y)=f(x-y,y)+f(x,y-x)
r(T)=sup { |<Tx,x>| ; ||x||=1}
It is easier to analyze the corres2
ponding linear operator in Z
(S f)(x,y)=f(x+y,y)+f(x,x+y)
Let L be a labeling of the arcs of the graph with
vertex set Z x Z and edges (x,y)z(x+y,y) and
(x,y)z(x,x+y) such that L(u,v)=1/L(v,u). Let C be
maximum over all vertices of sum of the labels
of the outgoing edges. Then r(S)cC.
Lattice Duality:
Banaszczyk’s
Transference Theorem
Banaszczyk ‘93
Lattice:
given n x n regular matrix B,
n
a lattice is { Bx; x Z }
Successive minima:
k smallest r such that a ball
centered in 0 of diameter r
contains k linearly
independent lattice points
Dual lattice:
Lattice
L* with
matrix B
-T
Transference theorem:
*
k n-k+1
 
n
c
can be used to show that O(n)
approximation of the shortest
lattice vector in 2-norm is not
NP-hard unless NP=co-NP
(Lagarias, H.W. Lenstra, Schnorr’ 90)
Poisson summation formula:
For “nice” f:RzC
S f(x)
xZ
=
S f(x)
xZ
Define Gaussian-like measure
n
on the subsets of R
r(A)=
exp(-p ||x||
S
x A
2
)
Prove using Poisson summation
formula:
r((L+u)\B)<0.285 r(L)
a ball of diameter (3/4)n1/2 centered around 0
Define Gaussian-like measure
on the subsets of R
p(A)= r(A  L)/r(L)
Prove using Poisson summation
formula:
*
*
p(u) = r(L+u)/r(L)
 
> then we have
n
a vector u perpendicular to
If
*
k n-k+1
all lattice points in
L B and L* B
outside ball
small + small
r(L* +u)/r(L* )
inside ball,
“moved by u”
T
p(u)= S r(x)exp(-2piu x)
xL
large
Weight of a function –
sum of columns (mod m)
,
Therien ‘94
m
4
1
2
4
1
4
1
2
3
4
1
3
4
1
4
1
6
1
3
6
1
2
1
3
3
2
5
3
2
4
2
5
n
Is there a set of columns which
sum to the zero column (mod t) ?
If m>c n t 11/2 then there always
exists a set of columns which
sum to zero column (mod t)
wt(f)= number of non-zero
Fourier coefficients
w(fg)cw(f)w(g)
w(f+g)cw(f)+w(g)
t+1 is a prime
x1ai,1 +
fi (x)=g
... +
xma i,m
If no set of columns sums to
the zero column mod t then
t
g= P (1-(1-f i ) )
m
restricted to B={0,1} is 10
m
n
t = wt(g 1B )c t
m
(t-1)