Sparse Signal Recovery in Compressive Sensing

The ℓ₁ Minimization Algorithm: Theory, Formulation, and Guarantees

Based on Candès and Wakin, "An Introduction to Compressive Sampling," IEEE Signal Processing Magazine, March
2008

1. Introduction and Motivation

Conventional signal acquisition follows the Nyquist-Shannon theorem, which mandates sampling at least twice
the maximum signal frequency. Compressive Sensing (CS), introduced by Candès, Romberg, Tao, and
Donoho, fundamentally challenges this paradigm. CS theory asserts that a signal f ∈ Rⁿ that is sparse or
compressible in some basis can be recovered from only m ≪ n measurements — far fewer than the signal
dimension. This is made possible through two principles: sparsity (the signal has a concise representation in
a proper basis) and incoherence (the sensing waveforms are spread out in the sparsity domain). The recovery
mechanism that makes this mathematically exact and computationally tractable is ℓ₁ minimization, the central
algorithm this write-up analyzes.

2. Problem Formulation

2.1 The Sensing Model

Let f ∈ Rⁿ be the signal of interest. CS acquires information through m linear measurements of the form yₖ = ⟨f,
φₖ⟩, k = 1, …, m, where φₖ are sensing waveforms. In matrix form, the measurement model is:
y = Ax + z
where A ∈ Rᵐˣⁿ is the sensing matrix, x is the coefficient sequence of f in a sparsifying basis Ψ, and z is an
error/noise term. The key challenge: since m < n, this is an underdetermined system with infinitely many
solutions. Sparsity resolves this ambiguity.

2.2 Sparsity and Coherence

A signal is called S-sparse if it has at most S non-zero entries in its coefficient representation x = Ψᵀf. For
nearly sparse (compressible) signals, the best S-term approximation is xₛ, obtained by retaining only the S
largest coefficients. The error ǁf − fₛǁ is small when coefficients decay rapidly. The coherence μ(Φ, Ψ) between
sensing basis Φ and representation basis Ψ is defined as μ(Φ,Ψ) = √n · maxₖⱼ |⟨φₖ, ψⱼ⟩|, taking values in [1, √n].
Low coherence is essential: it guarantees each measurement captures a little information about every sparse
component.

3. The ℓ₁ Minimization Algorithm

3.1 The Ideal but Intractable Formulation

The most natural recovery formulation is ℓ₀ minimization: find the sparsest x consistent with y. However,
minimizing the ℓ₀ pseudo-norm (which counts non-zeros) is NP-hard, requiring exhaustive search over all C(n,S)
possible support sets. For n = 1000, S = 10, this exceeds 2.6 × 10²³ combinations — computationally infeasible.

3.2 The ℓ₁ Relaxation: Basis Pursuit

The key theoretical insight of CS is that the ℓ₁ norm — the tightest convex relaxation of ℓ₀ — yields the same
sparse solution under the right conditions. Given m incoherent measurements indexed by M ⊂ {1, …, n}, the
reconstruction f* = Ψx* is obtained by solving (Equation 5 of Candès and Wakin):
 min ‖x̃
‖₁ subject to yₖ = ⟨φₖ, x̃
⟩, ∀k ∈ M [Noiseless]
min ‖x̃
‖₁ subject to ‖Ax̃− y‖₂ ≤ ε [Noisy / LASSO]

3.3 Geometric Intuition: Why ℓ₁ Promotes Sparsity

The success of ℓ₁ minimization rests on a fundamental geometric fact. The ℓ₂ ball (sphere) is smooth: when
shrunk to touch the constraint hyperplane {Ax = y}, it contacts at a smooth interior point, yielding a non-sparse
solution. The ℓ₁ ball (cross-polytope/diamond shape) has sharp corners located precisely on the coordinate
axes. When shrunk to touch the constraint hyperplane, it almost always contacts at one of these corners — a
point with only one non-zero coordinate — producing a sparse solution. Figure 2 of the paper dramatically
illustrates this: ℓ₁ recovery is exact while ℓ₂ (minimum energy) gives a completely different, non-sparse answer.

3.4 Reduction to a Linear Program

Because the ℓ₁ norm involves absolute values, it is non-smooth but convex. Introducing auxiliary variables uᵢ ≥
0 with the constraints xᵢ̃ ≤ uᵢ and −xᵢ̃ ≤ uᵢ (so that uᵢ = |xᵢ̃ |), the problem becomes a standard Linear Program (LP)
with a linear objective Σ uᵢ, linear equality constraints Ax̃ = y, and linear inequality constraints. This LP is solvable
efficiently via interior-point methods, simplex, ADMM, or gradient projection — making ℓ₁ minimization
computationally tractable at scale.

3.5 Step-by-Step Algorithm

1. Acquire m measurements: y = Ax (or y = Ax + z with noise)
2. Select sensing matrix A with low coherence with Ψ (e.g., Gaussian random, Bernoulli ±1, or noiselets)
3. Formulate the ℓ₁ minimization LP and solve using a convex solver
4. Recover the signal: f* = Ψx*

4. Recovery Guarantees

4.1 Theorem 1: Exact Recovery via Incoherent Sampling

The first recovery guarantee (Theorem 1, Candès and Romberg 2007) establishes when ℓ₁ minimization is
exact with high probability:

Theorem 1 — Exact Recovery (Probabilistic)

Condition: m ≥ C · μ²(Φ,Ψ) · S · log n measurements selected uniformly at random from the Φ
domain.
Conclusion: The ℓ₁ solution f* = Ψx* equals f exactly with probability exceeding 1 − δ (where m ≥ C ·
μ² · S · log(n/δ)).

Three critical observations: (1) The coherence μ appears as μ² — lower coherence means fewer measurements
needed, motivating the use of random matrices with μ ≈ √(2 log n). (2) Only O(S log n) samples are required
instead of n — an exponential saving when S ≪ n. (3) The algorithm requires no prior knowledge of the sparsity
level S, the locations of non-zeros, or their amplitudes. A practical four-to-one rule emerges: approximately 4
incoherent measurements per unknown non-zero coefficient suffice empirically (confirmed by the paper’s
megapixel image example: 25,000 non-zero wavelet coefficients recovered from 96,000 measurements).

4.2 Theorem 2: Oracle-Quality Recovery (Deterministic)

When the sensing matrix A satisfies the Restricted Isometry Property (RIP) — meaning all subsets of S columns
of A are nearly orthogonal — a stronger deterministic guarantee holds:

Theorem 2 — RIP-Based Recovery (Deterministic, Noiseless)

 Condition: δ₂s < √2 − 1 ≈ 0.414, where δ₂s is the isometry constant of A at order 2S.
Conclusion: ǁx* − xǁ₂ ≤ C₀ · ǁx − xsǁ₁ / √S and ǁx* − xǁ₁ ≤ C₀ · ǁx − xsǁ₁ for some constant C₀.

This theorem is deterministic — no probability of failure. If x is exactly S-sparse, then x = xₛ so ǁx − xₛǁ₁ = 0,

giving perfect recovery. If x is only approximately sparse, the reconstruction error is bounded by the tail energy
of the S-sparse approximation — matching what an oracle that knows in advance the S largest components
could achieve. This oracle-optimality is the strongest possible performance benchmark.

4.3 Theorem 3: Robust Recovery Under Noise

For practical deployment, Theorem 3 extends the guarantee to the noisy setting using the LASSO formulation
(Equation 11):

Theorem 3 — Robust Recovery (Noisy Data)

Condition: δ₂s < √2 − 1, noise bounded by ǁzǁ₂ ≤ ε.
Conclusion: ǁx* − xǁ₂ ≤ C₀ · ǁx − xsǁ₁ / √S + C₁ · ε. With δ₂s = 1/4: C₀ ≤ 5.5, C₁ ≤ 6.

The error decomposes cleanly into two interpretable terms: the first is the irreducible approximation error from
the signal’s non-sparsity (identical to the noiseless bound), and the second is directly proportional to the noise
level. The constants are small and known explicitly. This establishes CS as a practically viable sensing
mechanism.

5. Sensing Matrix Design and the RIP

For the RIP condition δ₂s < √2 − 1 to hold, the number of measurements must satisfy (Equation 13):
m ≥ C · S · log(n/S)
Four classes of random matrices satisfy this with exponentially small failure probability:
• Uniform Sphere: Columns sampled uniformly at random on the unit sphere of Rᵐ
• Gaussian: Entries drawn i.i.d. from N(0, 1/m)
• Bernoulli ±1: Entries drawn i.i.d. from symmetric Bernoulli (P(Aᵢⱼ = ±1/√m) = 1/2)
• Random Projections: Random projections P, normalized as A = √(n/m) · P

Crucially, these random matrices are universal: the sparsifying basis Ψ need not be known when designing
the measurement system. This universality has profound implications for distributed sensing, where different
sensors can use independent random projections without coordination. Noiselets are a notable structured
alternative: they achieve coherence √2 with Haar wavelets and have O(n) transforms, making them highly
efficient for image CS implementations.

6. Applications
The practical reach of ℓ₁ minimization for sparse recovery spans several domains identified by Candès and
Wakin: MR Angiography, where Φ records Fourier coefficients and the image is sparse in wavelet domain,
allowing dramatic scan time reduction; the Single-Pixel Camera, which uses a digital micromirror array and a
single photosensitive element instead of millions; Analog-to-Information (A/I) Conversion, where two
architectures — the Nonuniform Sampler (NUS) and the Random Modulation Preintegrator (RMPI) — directly
acquire incoherent measurements of high-bandwidth analog signals at sub-Nyquist rates; and distributed
sensor networks, where universality of random projections enables independent encoding without shared
basis knowledge.

7. Conclusion
The ℓ₁ minimization algorithm transforms the intractable ℓ₀ sparse recovery problem into a convex linear
program. Under two conditions — low coherence between the sensing and sparsity bases (Theorem 1) or the
Restricted Isometry Property on the sensing matrix (Theorems 2 and 3) — it achieves exact recovery of S-
sparse signals from only O(S log n) measurements, oracle-quality recovery of approximately sparse signals,
and stable, bounded recovery in the presence of noise. Random sensing matrices satisfying the RIP with m ≥
C · S log(n/S) measurements make this a universal and near-optimal sensing strategy. The four-to-one
empirical rule — approximately four incoherent measurements per non-zero coefficient — makes the theory
directly actionable. Together, these results establish compressive sensing as a coherent, complete framework
that redefines the fundamental limits of signal acquisition.

Reference: E. J. Candès and M. B. Wakin, "An Introduction to Compressive Sampling," IEEE Signal Processing Magazine, vol. 25, no. 2,
pp. 21–30, March 2008.