Uncertainty principles and compressed sensing
Let . Let be the set of functions from to , and for let be the set of functions whose support is a subset of .
. We also define .
is a -dimensional vector space, for each . In particular, is an -dimensional vector space and thus . We speak interchangeably about a signal of length , a function from to , and a vector of length ; sometimes one of these is more convenient.
For , the Fourier transform of is defined by
The Fourier inversion formula is
Define by . By the Fourier inversion formula, 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 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 , given and , can we uniquely reconstruct ? We can do this if and only if ; this is because by the Fourier inversion formula we can define a function by defining its Fourier transform.
Now say that is -sparse. Given and , can we uniquely reconstruct ? i.e., is there a unique -sparse function (namely itself) which agrees with the measurements we have?
Certainly is necessary. Actually it is necessary that (if ). Suppose . The subspace of has dimension , and the subspace has dimension . But , and thus there is a nonzero element in their intersection, say there is a nonzero such that . Let where is supported on and is supported on . so and are distinct -sparse functions such that .
Unique reconstructions fails if and only if there is a nonzero -sparse function whose Fourier transform vanishes on all of . In other words, unique reconstruction of -sparse functions measured on holds if and only if for all -sparse there is some such that .
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: and cannot both be compactly supported (Paley-Wiener), and even and cannot both be supported on sets of finite measure (Benedicks).
Discrete uncertainty principle: If is not identically zero, then .
The Plancherel identity tells us that
By the Fourier inversion formula,
By the Cauchy-Schwarz inequality,
By the Plancherel identity we have
Since is not identically this gives
Now, we have unique recoverability if and only if for every -sparse function has a frequency in . This will happen in particular if . If then . Therefore, if then by the Discrete Uncertainty Principle we will have unique reconstruction.
The bound cannot not be improved in general: When is a square, let be the indicator function for and let . Then is -sparse so , and . We know that . The zero function and are both -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 .)
If and is the indicator function for the multiples of , then , and one can show that . See p. 226 of Audrey Terras, Fourier analysis on finite groups and applications, 1999. We can take measurements and still not be able to distinguish from the zero function.
When is a prime then these types of counterexamples do not exist.
Uncertainty principle for cyclic groups of prime order: If is prime and is not identically zero, then . This demands far fewer measurements than the Discrete Uncertainty Principle.
We have unique reconstruction if for every -sparse , is not identically zero on . It would suffice that for every -sparse , . By this uncertainty principle we know that , so if then we have unique reconstruction.
If we take a bump function on that is on then the Fourier transform will be concentrated on the same set. This yields a function on defined by the values of the bump function on the integers . If there is roundoff error, then is -sparse, since it is very small outside of . If we take then will be very small on and so by roundoff error in fact zero on . This examples applies whether or not is prime, so if there is error then we don’t have unique reconstruction for all sets satisfying when 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 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 , then with probability for any fixed ,
for all -sparse functions . means that and differ by at most 10%.
For a single function we cans show that gets its “fair share” of the 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 -sparse functions.
Chernoff inequality: Let be independent random variables with , mean and variance . Let . Then for any one has
for some absolute constants .
Let and take with probability . Then and . When is small relative to , then and have nearly the same distribution, because most multisets of size will not have repeated entries.
To use the Chernoff inequality we want , where . 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 big components in the signal and then for the rest of the components, the th component decays for some . 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 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 be prime and . Let be distinct elements of and let be distinct elements of . Then the matrix has nonzero determinant.
Now, let be nonempty subsets of with . Define by . 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 is for some choice of and . Therefore is an isomorphism.
Suppose by contradiction that there is a nonzero such that . Let . Then there some that is disjoint from and such that . defined by is an isomorphism, but is a nonzero vector that it sends to zero, a contradiction. Therefore for all nonzero , . 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 is prime, a positive integer and a polynomial with integer coefficients. If are th roots of unity such that , then is a multiple of .
To prove this, let and let for some integers . Now define
Here we are not talking about quotient rings, just the result of polynomial long division. So and (since the quotient from the long division will be equal to when evaluated at ). Since is prime the minimal polynomial of is the cyclotomic polynomial ; must be the product of this with a polynomial over the integers, but since has degree at most , it is an integer multiple of the minimal polynomial. Therefore is an integer multiple of .
Now we have everything we need for the proof of Chebotarev’s lemma. Let . We have to show that
is not a multiple of . To do this, define
evaluated at .
This is equal to
which is a Vandermonde determinant and is equal to
These factors are all distinct modulo , hence the product is not a multiple of .