Consider a signal x∈RNx∈RN, and suppose that the basis ΨΨ provides a KK-sparse representation of xx

As we discussed in Compression, the standard procedure for compressing sparse signals, known as transform coding, is to (i) acquire the full NN-sample signal xx; (ii) compute the complete set of transform coefficients αα; (iii) locate the KK largest, significant coefficients and discard the (many) small coefficients; (iv) encode the values and locations of the largest coefficients.

This procedure has three inherent inefficiencies: First, for a high-dimensional signal, we must start with a large number of samples NN. Second, the encoder must compute all NN of the transform coefficients αα, even though it will discard all but KK of them. Third, the encoder must encode the locations of the large coefficients, which requires increasing the coding rate since the locations change with each signal.

This raises a simple question: For a given signal, is it possible to directly estimate the set of large α(n)α(n)'s that will not be discarded? While this seems improbable, Candès, Romberg, and Tao [10], [14] and Donoho [18] have shown that a reduced set of projections can contain enough information to reconstruct sparse signals. An offshoot of this work, often referred to as Compressed Sensing (CS) [9], [14], [11], [12], [8], [18], [19], has emerged that builds on this principle.

In CS, we do not measure or encode the KK significant α(n)α(n) directly. Rather, we measure and encode M<NM<N projections y(m)=<x,φmT>y(m)=<x,φmT> of the signal onto a second set of functions {φm},m=1,2,...,M{φm},m=1,2,...,M. In matrix notation, we measure

The CS theory tells us that when certain conditions hold, namely that the functions {φm}{φm} cannot sparsely represent the elements of the basis {ψn}{ψn} (a condition known as incoherence of the two dictionaries [14], [10], [18], [29]) and the number of measurements MM is large enough, then it is indeed possible to recover the set of large {α(n)}{α(n)} (and thus the signal xx) from a similarly sized set of measurements yy. This incoherence property holds for many pairs of bases, including for example, delta spikes and the sine waves of a Fourier basis, or the Fourier basis and wavelets. Significantly, this incoherence also holds with high probability between an arbitrary fixed basis and a randomly generated one.

Although the problem of recovering xx from yy is ill-posed in general (because x∈RNx∈RN, y∈RMy∈RM, and M<NM<N), it is indeed possible to recover sparse signals from CS measurements. Given the measurements y=Φxy=Φx, there exist an infinite number of candidate signals in the shifted nullspace N(Φ)+xN(Φ)+x that could generate the same measurements yy (see Linear Models from Low-Dimensional Signal Models). Recovery of the correct signal xx can be accomplished by seeking a sparse solution among these candidates.

Recovery via convex optimization

The practical revelation that supports the new CS theory is that it is not necessary to solve the ℓ0ℓ0-minimization problem to recover αα. In fact, a much easier problem yields an equivalent solution (thanks again to the incoherency of the bases); we need only solve for the ℓ1ℓ1-sparsest coefficients αα that agree with the measurements yy [10], [9], [14], [11], [12], [8], [18], [19]

α ^ = arg min ∥ α ∥ 1 s.t. y = Φ Ψ α . α ^ = arg min ∥ α ∥ 1 s.t. y = Φ Ψ α .

(4)

As discussed in Nonlinear Approximation from Approximation, this optimization problem, also known as Basis Pursuit [7], is significantly more approachable and can be solved with traditional linear programming techniques whose computational complexities are polynomial in NN.

There is no free lunch, however; according to the theory, more than K+1K+1 measurements are required in order to recover sparse signals via Basis Pursuit. Instead, one typically requires M≥cKM≥cK measurements, where c>1c>1 is an oversampling factor. As an example, we quote a result asymptotic in NN. For simplicity, we assume that the sparsity scales linearly with NN; that is, K=SNK=SN, where we call SS the sparsity rate.

Theorem 2

[13], [20], [17] Set K=SNK=SN with 0<S≪10<S≪1. Then there exists an oversampling factor c(S)=O(log(1/S))c(S)=O(log(1/S)), c(S)>1c(S)>1, such that, for a KK-sparse signal xx in the basis ΨΨ, the following statements hold:

1. The probability of recovering xx via Basis Pursuit from (c(S)+ϵ)K(c(S)+ϵ)K random projections, ϵ>0ϵ>0, converges to one as N→∞N→∞.
2. The probability of recovering xx via Basis Pursuit from (c(S)-ϵ)K(c(S)-ϵ)K random projections, ϵ>0ϵ>0, converges to zero as N→∞N→∞.

In an illuminating series of recent papers, Donoho and Tanner [17], [20], [21] have characterized the oversampling factor c(S)c(S) precisely (see also "The geometry of Compressed Sensing"). With appropriate oversampling, reconstruction via Basis Pursuit is also provably robust to measurement noise and quantization error [10].

We often use the abbreviated notation cc to describe the oversampling factor required in various settings even though c(S)c(S) depends on the sparsity KK and signal length NN.

A CS recovery example on the Cameraman test image is shown in Figure 1. In this case, with M=4KM=4K we achieve near-perfect recovery of the sparse measured image.

Figure 1: Compressive sensing reconstruction of the nonlinear approximation Cameraman image from (Reference)(b). Using M=16384M=16384 random measurements of the KK-term nonlinear approximation image (where K=4096K=4096), we solve an ℓ1ℓ1-minimization problem to obtain the reconstruction shown above. The MSE with respect to the measured image is 0.080.08, so the reconstruction is virtually perfect.

CS appears to be promising for a number of applications in signal acquisition and compression. Instead of sampling a KK-sparse signal NN times, only cKcK incoherent measurements suffice, where KK can be orders of magnitude less than NN. Therefore, a sensor can transmit far fewer measurements to a receiver, which can reconstruct the signal and then process it in any manner. Moreover, the cKcK measurements need not be manipulated in any way before being transmitted, except possibly for some quantization. Finally, independent and identically distributed (i.i.d.) Gaussian or Bernoulli/Rademacher (random ±1±1) vectors provide a useful universal basis that is incoherent with all others. Hence, when using a random basis, CS is universal in the sense that the sensor can apply the same measurement mechanism no matter what basis the signal is sparse in (and thus the coding algorithm is independent of the sparsity-inducing basis) [14], [18], [6].

These features of CS make it particularly intriguing for applications in remote sensing environments that might involve low-cost battery operated wireless sensors, which have limited computational and communication capabilities. Indeed, in many such environments one may be interested in sensing a collection of signals using a network of low-cost signals.

Other possible application areas of CS include imaging [28], medical imaging [10], [26], and RF environments (where high-bandwidth signals may contain low-dimensional structures such as radar chirps) [15]. As research continues into practical methods for signal recovery (see Section 3), additional work has focused on developing physical devices for acquiring random projections. Our group has developed, for example, a prototype digital CS camera based on a digital micromirror design [28]. Additional work suggests that standard components such as filters (with randomized impulse responses) could be useful in CS hardware devices [30].

It is important to note that the core theory of CS draws from a number of deep geometric arguments. For example, when viewed together, the CS encoding/decoding process can be interpreted as a linear projection Φ:RN↦RMΦ:RN↦RM followed by a nonlinear mapping Δ:RM↦RNΔ:RM↦RN. In a very general sense, one may naturally ask for a given class of signals F∈RNF∈RN (such as the set of KK-sparse signals or the set of signals with coefficients ∥α∥ℓp≤1∥α∥ℓp≤1), what encoder/decoder pair Φ,ΔΦ,Δ will ensure the best reconstruction (minimax distortion) of all signals in FF. This best-case performance is proportional to what is known as the Gluskin nn-width [24], [23] of FF (in our setting n=Mn=M), which in turn has a geometric interpretation. Roughly speaking, the Gluskin nn-width seeks the (N-n)(N-n)-dimensional slice through FF that yields signals of greatest energy. This nn-width bounds the best-case performance of CS on classes of compressible signals, and one of the hallmarks of CS is that, given a sufficient number of measurements this optimal performance is achieved (to within a constant) [18], [16].

Additionally, one may view the ℓ0/ℓ1ℓ0/ℓ1 equivalence problem geometrically. In particular, given the measurements y=Φxy=Φx, we have an (N-M)(N-M)-dimensional hyperplane Hy={x'∈RN:y=Φx'}=N(Φ)+xHy={x'∈RN:y=Φx'}=N(Φ)+x of feasible signals that could account for the measurements yy. Supposing the original signal xx is KK-sparse, the ℓ1ℓ1 recovery program will recover the correct solution xx if and only if ∥x'∥1>∥x∥1∥x'∥1>∥x∥1 for every other signal x'∈Hyx'∈Hy on the hyperplane. This happens only if the hyperplane HyHy (which passes through xx) does not “cut into” the ℓ1ℓ1-ball of radius ∥x∥1∥x∥1. This ℓ1ℓ1-ball is a polytope, on which xx belongs to a (K-1)(K-1)-dimensional “face.” If ΦΦ is a random matrix with i.i.d. Gaussian entries, then the hyperplane HyHy will have random orientation. To answer the question of how MM must relate to KK in order to ensure reliable recovery, it helps to observe that a randomly generated hyperplane HH will have greater chance to slice into the ℓ1ℓ1 ball as dim (H)=N-M dim (H)=N-M grows (or as MM shrinks) or as the dimension K-1K-1 of the face on which xx lives grows. Such geometric arguments have been made precise by Donoho and Tanner [17], [20], [21] and used to establish a series of sharp bounds on CS recovery.

We have also identified [6] a fundamental connection between the CS and the JL lemma. In order to make this connection, we considered the Restricted Isometry Property (RIP), which has been identified as a key property of the CS projection operator ΦΦ to ensure stable signal recovery. We say ΦΦ has RIP of order KK if for every KK-sparse signal xx,

While the JL lemma concerns pairwise distances within a finite cloud of points, the RIP concerns isometric embedding of an infinite number of points (comprising a union of KK-dimensional subspaces in RNRN). However, the RIP can in fact be derived by constructing an effective sampling of KK-sparse signals in RNRN, using the JL lemma to ensure isometric embeddings for each of these points, and then arguing that the RIP must hold true for all KK-sparse signals. (See [6] for the full details.)

Finally, we have also shown that the JL lemma can also lead to extensions of CS to other concise signal models. In particular, while conventional CS theory concerns sparse signal models, it is also possible to consider manifold-based signal models. Just as random projections can preserve the low- dimensional geometry (the union of hyperplanes) that corresponds to a sparse signal family, random projections can also guarantee a stable embedding of a low-dimensional signal manifold. We have the following result, which states that an RIP-like property holds for families of manifold-modeled signals.

The proof of this theorem appears in [1] and again involves the JL lemma. Due to the limited complexity of a manifold model, it is possible to adequately characterize the geometry using a sufficiently fine sampling of points drawn from the manifold and its tangent spaces. In essence, manifolds with higher volume or with greater curvature have more complexity and require a more dense covering for application of the JL lemma; this leads to an increased number of measurements. The theorem also indicates that the requisite number of measurements depends on the geodesic covering regularity of the manifold, a minor technical concept which is also discussed in [1].

This theorem establishes that, like the class of K K-sparse signals, a collection of signals described by a K K-dimensional manifold M ⊂ RN M⊂RN can have a stable embedding in an MM-dimensional measurement space. Moreover, the requisite number of random measurements M M is once again linearly proportional to the information level (or number of degrees of freedom) K K in the concise model. This has a number of possible implications for manifold-based signal processing. Manifold-modeled signals can be recovered from compressive measurements (using a customized recovery algorithm adapted to the manifold model, in contrast with sparsity-based recovery algorithms) [2], [4]; unknown parameters in parametric models can be estimated from compressive measurements; multi-class estimation/classification problems can be addressed [2] by considering multiple manifold models; and manifold learning algorithms may be efficiently executed by applying them simply to the projection of a manifold-modeled data set to a low-dimensional measurement space [3]. (As an example, (Reference)(d) shows the result of applying the ISOMAP algorithm on a random projection of a data set from R4096R4096 down to R15R15; the underlying parameterization of the manifold is extracted with little sacrifice in accuracy.) In all of this it is not necessary to adapt the sensing protocol to the model; the only change from sparsity-based CS would be the methods for processing or decoding the measurements. In the future, more sophisticated concise models will likely lead to further improvements in signal understanding from compressive measurements.