Uncertainty principles and compressed sensing

Jordan Bell
April 21, 2010

Let ZN=/N. Let p(ZN) be the set of functions from ZN to , and for TZN let p(T) be the set of functions ZN whose support is a subset of T.

fp(T)=(xT|f(x)|)1/p. We also define f0(ZN)=xsupp(f)1.

p(T) is a |T|-dimensional vector space, for each p. In particular, p(ZN) is an N-dimensional vector space and thus p(ZN)N. We speak interchangeably about a signal of length N, a function from ZN to , and a vector of length N; sometimes one of these is more convenient.

For f1(ZN), the Fourier transform f^ of f is defined by



The Fourier inversion formula is


Define F:1(ZN)1(ZN) by F(f)=f^. By the Fourier inversion formula, F is an isomorphism of vector spaces.

In this note we shall state and explain the main points of the proofs of several uncertainty principles for ZN that are given in Terence Tao’s paper An uncertainty principle for cyclic groups of prime order, Math. Res. Lett. 12 (2005), no. 1, 121–127 and the April 15, 2007 entry, “Ostrowski lecture: The uniform uncertainty principle and compressed sensing”, in Terence Tao’s blog (terrytao.wordpress.com). Also see the PDF on Tao’s website from the talk by Candès and Tao, “The uniform uncertainty principle and compressed sensing”, Harmonic Analysis and Related Topics, Seville, December 5, 2008.

We shall also state and prove a theorem from Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inform. Theory 52 (2006), no. 2, 489–509 of Candès, Romberg and Tao which gives unique reconstruction. We shall explain why unique reconstruction (even in the special case of the theorem) fails when there is noise. Finally, we’ll give some motivation for the Uniform Uncertainty Principle.

For f1(ZN), given ΛZN and {f^(ξ)}ξΛ, can we uniquely reconstruct f? We can do this if and only if Λ=ZN; this is because by the Fourier inversion formula we can define a function by defining its Fourier transform.

Now say that f1(ZN) is S-sparse. Given ΛZN and {f^(ξ)}ξΛ, can we uniquely reconstruct f? i.e., is there a unique S-sparse function (namely f itself) which agrees with the measurements {f^(ξ)}ξΛ we have?

Certainly |Λ|S is necessary. Actually it is necessary that |Λ|2S (if 2SN). Suppose |Λ|<2S. The subspace F(1({1,,2S})) of 1(ZN) has dimension 2S, and the subspace 1(ZN-Λ) has dimension N-|Λ|. But 2S+N-|Λ|>N, and thus there is a nonzero element in their intersection, say there is a nonzero f1({1,,2S}) such that f^|Λ=0. Let f=f1-f2 where f1 is supported on {1,,S} and f2 is supported on {S+1,,2S}. f0 so f1 and f2 are distinct S-sparse functions such that f1^|Λ=f2^|Λ.

Unique reconstructions fails if and only if there is a nonzero 2S-sparse function whose Fourier transform vanishes on all of Λ. In other words, unique reconstruction of S-sparse functions measured on Λ holds if and only if for all 2S-sparse g1(ZN) there is some ξΛ such that g^(ξ)0.

The uncertainty principle suggests that the Fourier transform of a sparse function will have large support, and if the Fourier transform has large support then for most sets Λ the Fourier transform of the function will not be identically zero on Λ. Generally, the support of a function and the support of its Fourier transform cannot both be small: f and f^ cannot both be compactly supported (Paley-Wiener), and even f and f^ cannot both be supported on sets of finite measure (Benedicks).

Discrete uncertainty principle: If f1(ZN) is not identically zero, then |supp(f)||supp(f^)|N.

The Plancherel identity tells us that


By the Fourier inversion formula,


By the Cauchy-Schwarz inequality,




By the Plancherel identity we have






Since f is not identically 0 this gives


Now, we have unique recoverability if and only if for every 2S-sparse function g has a frequency in Λ. This will happen in particular if |Λ|>N-|supp(g^)|. If |Λ|>N-N2S then |Λ|>N-|supp(g^)|. Therefore, if |Λ|>N-N2S then by the Discrete Uncertainty Principle we will have unique reconstruction.

The bound |Λ|>N-N2S cannot not be improved in general: When N is a square, let f be the indicator function for T={0,N,2N,,N-N} and let Λ=ZN-T. Then f is N-sparse so N-N2S=N-N2, and |Λ|=N-N. We know that f^=f. The zero function and f are both N-sparse functions whose Fourier transforms agree on Λ, so unique reconstruction does not occur. (Here we showed that one can’t do better in general than |Λ|>N-NS.)

If N=ab and f is the indicator function for the multiples of b, then |supp(f)|=a, and one can show that |supp(f^)|=b. See p. 226 of Audrey Terras, Fourier analysis on finite groups and applications, 1999. We can take |Λ|=ab-b measurements and still not be able to distinguish f from the zero function.

When N is a prime then these types of counterexamples do not exist.

Uncertainty principle for cyclic groups of prime order: If N is prime and f1(ZN) is not identically zero, then |supp(f)|+|supp(f^)|N+1. This demands far fewer measurements than the Discrete Uncertainty Principle.

We have unique reconstruction if for every 2S-sparse g1(ZN), g^ is not identically zero on Λ. It would suffice that for every 2S-sparse g, supp(g^)>N-|Λ|. By this uncertainty principle we know that supp(g^)>N-supp(g)N-2S, so if |Λ|2S then we have unique reconstruction.

If we take a bump function on that is 1 on {-N,-N+1,,N} then the Fourier transform will be concentrated on the same set. This yields a function f on ZN defined by the values of the bump function on the integers 0,1,,N-1. If there is roundoff error, then f is N-sparse, since it is very small outside of {0,1,,N}. If we take Λ={N/3,N/3+1,,2N/3} then f^ will be very small on Λ and so by roundoff error in fact zero on Λ. This examples applies whether or not N is prime, so if there is error then we don’t have unique reconstruction for all sets satisfying |Λ|2S when N is prime.

These obstructions to unique reconstruction all involved sets of observed frequencies Λ that were arithmetic progressions. More generally, the problem Λ were structured. It turns out that if we select a set of frequencies uniformly at random among all (N|Λ|) sets of size |Λ we will usually not have these obstructions. (“Most sets” don’t have the properties that make unique reconstruction fail.)

Uniform Uncertainty Principle: If Λ is a random set with |Λ|Slog4N, then with probability 1-O(N-A) for any fixed A,


for all 4S-sparse functions f1(ZN). XY means that X and Y differ by at most 10%.

For a single function f we cans show that Λ gets its “fair share” of the 2 norm using the Chernoff inequality, but it is much harder to prove for all functions since there are so many functions…We need some way of keeping a handle on the set of all S-sparse functions.

Chernoff inequality: Let X1,,Xn be independent random variables with |Xi|K, mean μi and variance σi2. Let Sn=i=1nXi,μ=i=1nμi,σ2=i=1nσi2. Then for any λ>0 one has


for some absolute constants C,c>0.

Let n=|Λ| and take Xi=|f^(ξ)|2 with probability 1N. Then μi=1N2(f^) and μ=|Λ|N2(f^). When |Λ| is small relative to N, then i=1nXi and ξΛ|f^(ξ)|2 have nearly the same distribution, because most multisets of size |Λ| will not have repeated entries.

To use the Chernoff inequality we want P(|Sn-μ|>δμ)P(|Sn-μ|>λσ), where δ=0.1. So let λ=δμσ.

The paper Near-optimal signal recovery from random projections: Universal encoding strategies?, IEEE Trans. Inform. Theory 52 (2006), no. 12, 5406–5425 by Candès and Tao deals with signals that are not sparse but that obey a “power law”, where there are S big components in the signal and then for the rest of the components, the nth component decays O(n-1/p) for some p>0. This paper is a tour de force. The “main result of the paper” which states that if a measurement process obeys UUP and ERP then we can reconstruct something which has a very close 2 norm to the original signal. But to actually show that ERP and UUP hold for the measurement processes (=ensembles=random matrices) they deal with in the paper is a whole other barrel of monkeys. (In this presentation we talked about the Fourier ensemble, which is the hardest ensemble to prove ERP and UUP for.)

Proof of the uncertainty principle for cyclic groups of prime order. First assume what we’ll call Chebotarev’s lemma: Let p be prime and 1np. Let x1,,xn be distinct elements of Zp and let ξ1,,xn be distinct elements of Zp. Then the matrix (e2πixiξk)1j,kn has nonzero determinant.

Now, let A,A~ be nonempty subsets of Zp with |A|=|A~|. Define T:2(A)2(A~) by Tf=f^|A~. Thinking of the left-hand side (physical space) as having a basis of Dirac deltas and the right-hand side (frequency space) as having a basis of exponentials, the matrix representation of T is (e2πixiξk)1j,kn for some choice of xi and ξi. Therefore T is an isomorphism.

Suppose by contradiction that there is a nonzero f2(Zp) such that |supp(f)|+|supp(f^)|p. Let A=supp(f). Then there some A~2(Zp) that is disjoint from supp(f^) and such that |A|=|A~|. T:2(A)2(A~) defined by Tf=f^|A~ is an isomorphism, but f is a nonzero vector that it sends to zero, a contradiction. Therefore for all nonzero f2(Zp), |supp(f)|+|supp(f^)|p+1. We’ve seen too that this bound is sharp. Thus the uncertainty principle for cyclic groups of prime order is proved.

Now we’ll turn to proving Chebotarev’s lemma.

The proof of Chebotarev’s lemma itself requires another rather easy lemma (from the “Galois theory of the cyclotomic integers”): Let p is prime, n a positive integer and P(z1,,zn) a polynomial with integer coefficients. If ω1,,ωn are pth roots of unity such that P(ω1,,ωn)=0, then P(1,,1) is a multiple of p.

To prove this, let ω=e2πi/p and let ωj=ωkj for some integers 0kj<p. Now define


Here we are not talking about quotient rings, just the result of polynomial long division. So Q(ω)=0 and Q(1)=P(1,,1) (since the quotient from the long division will be equal to 0 when evaluated at 1). Since p is prime the minimal polynomial of ω is the cyclotomic polynomial Φp(z)=1+z++zp-1; Q(z) must be the product of this with a polynomial over the integers, but since Q(z) has degree at most p-1, it is an integer multiple of the minimal polynomial. Therefore Q(1)=P(1,,1) is an integer multiple of Φp(1)=p.

Now we have everything we need for the proof of Chebotarev’s lemma. Let ωj=e2πixj/p. We have to show that


is not a multiple of p. To do this, define


and put



(z2ddz2)1(z3ddz3)2(znddzn)n-1D(z1,,zn) (1)

evaluated at z1==zn=1.

This is equal to


None of the factorials are multiples of p since np. So to show that P(1,,1) is not a multiple of p it suffices to show that (1) is not a multiple of p. But (1) is equal to


which is a Vandermonde determinant and is equal to


These factors are all distinct modulo p, hence the product is not a multiple of p.