Source-linked AI summary
Theory and Applications of Compressed Sensing
Gitta Kutyniok
TL;DR
This survey treats compressed sensing and sparse recovery interchangeably, addressing underdetermined linear systems when the unknown vector is sparse but its support is unknown. It reviews recovery conditions, including an RIP guarantee for recovering all k-sparse vectors with (P1).
Problem
Underdetermined linear measurements leave the unknown vector’s support unavailable, so sparsity must serve as prior information for recovery.
Source: §1.1 · p. 2Method
The survey broadly treats compressed sensing as sparse recovery and reviews recovery conditions and algorithms for signals sparse in a basis or frame.
Source: §1 · p. 2, §1.1 · p. 2, §5.2 · p. 15Results
δ2k < 0.473 guarantees that (P1) recovers all k-sparse vectors when the measurement matrix satisfies that RIP condition.
Source: §3.2.2 · p. 12Takeaways & Limitations
Extending OMPR with locality sensitive hashing yields the first provably sub-linear algorithm for sparse recovery [40].
Source: §5.2 · p. 15Generalizations of vector sparsity such as low-rank matrix models for matrix completion are beyond this survey’s scope.
Source: §2.2 · p. 8
Abstract
from arXiv · showhide
Compressed sensing is a novel research area, which was introduced in 2006, and since then has already become a key concept in various areas of applied mathematics, computer science, and electrical engineering. It surprisingly predicts that high-dimensional signals, which allow a sparse representation by a suitable basis or, more generally, a frame, can be recovered from what was previously considered highly incomplete linear measurements by using efficient algorithms. This article shall serve as an introduction to and a survey about compressed sensing.
1 Introduction
The introduction frames compressed sensing as sparse recovery from few linear measurements and previews the survey’s models, recovery theory, sensing matrices, algorithms, and applications.
1.1 The Compressed Sensing Problem
- The core problem is recovering a sparse signal or its sparse coefficients from an underdetermined system when its support is unknown, raising model, sensing, and algorithm questions.Source: §1.1 · p. 2
1.2 Sparsity: A Reasonable Assumption?
- Natural images can be sparse in wavelets, while communication and genomics may be intrinsically sparse; approximate and structured models address less ideal cases.Source: §1.2 · pp. 3–4
1.3 Recovery Algorithms: Optimization Theory and More
- Because ℓ0 search is NP-hard, Basis Pursuit substitutes convex ℓ1 minimization; large problems also motivate convex, greedy, and combinatorial alternatives.Source: §1.3 · p. 4
1.4 Sensing Matrices: How Much Freedom is Allowed?
- Freely chosen sensing matrices favor random ensembles, but applications often impose structure, and deterministic matrices with similar properties remain an open question.Source: §1.4 · p. 5
1.5 Compressed Sensing: Quo Vadis?
- Research directions include structured sparsity, extensions such as matrix completion, continuum recovery, analysis-versus-synthesis formulations, and frame-based sparsification.Source: §1.5 · pp. 5–6
1.6 Outline
- The survey proceeds from sparsity models and ℓ1 recovery conditions through sensing matrices and alternative algorithms to applications including data separation.Source: §1.6 · p. 6
2 Signal Models
The section treats sparsity as prior information for signal models, moving from exact and approximate sparsity to structured models and representations that make signals sparse.
2.1 Sparsity
- A k-sparse vector has at most k nonzero coefficients, while p-compressibility describes vectors whose best k-term approximation error decays as C k^-r in ℓp.The survey presents compressibility as one possible weaker notion, not necessarily the most appropriate one.Source: §2.1 · p. 7
2.2 Structured Sparsity
- Structured models capture coefficient patterns such as wavelet trees and generalize sparsity to unions of subspaces, fusion frames, and nonlinear manifolds; low-rank matrix models remain outside scope.Fusion frames analyze signals through projections onto subspaces, while the manifold model treats signals as k-sparse in a nonlinear k-dimensional manifold.Source: §2.2 · pp. 7–8
2.3 Sparsifying Dictionaries and Dictionary Learning
- Known systems such as Fourier bases, wavelets, and shearlets offer mathematical properties and fast transforms, though their achieved sparsity may not be optimal.A frame can provide more flexibility than an orthonormal basis because of its redundancy.Source: §2.3 · pp. 8–9
- Adaptive dictionary learning can improve sparsity, but K-SVD has few known convergence results and learned dictionaries lack exploitable structure for analysis and fast transforms.The learning process uses a test set of signals to fit a dictionary adapted to the signals at hand.Source: §2.3 · p. 9
3 Conditions for Sparse Recovery
The section surveys conditions for exact sparse recovery, focusing on ℓ1 minimization and how recovery depends on both signal sparsity and sensing-matrix properties. It presents uniqueness criteria, sufficient conditions, and a geometric characterization of when (P0) and (P1) coincide.
3 Conditions for Sparse Recovery
- The section focuses on ℓ1 minimization, introduces sensing-matrix incoherence conditions, and notes that many results extend to additive measurement noise.The stated noise model is y = Ax + ν with ∥ν∥2 ≤ ε.Source: §3 · p. 9
3.1 Uniqueness Conditions for Minimization Problems
- The section introduces uniqueness conditions for the solutions of (P0) and (P1).It then treats the two minimization problems separately.Source: §3.1 · p. 9
3.1.1 Uniqueness of (P0)
- A solution of (P0) with at most k nonzeros is unique exactly when k < spark(A)/2.The spark is the smallest number of linearly dependent columns of A.Source: §3.1.1 · pp. 9–10
3.1.2 Uniqueness of (P1)
- A solution of (P1) with at most k nonzeros is unique if and only if A satisfies the null space property of order k.The section frames this criterion for an underdetermined recovery problem whose analysis uses the null space of A.Source: §3.1.2 · p. 10
3.2 Sufficient Conditions
- Mutual coherence measures the smallest angle between pairs of matrix columns; its lower bound is attained by optimal Grassmannian frames.The maximal coherence is 1 when two columns are linearly dependent.Source: §3.2.1 · p. 11
3.2.1 Mutual Coherence
- A sparsity bound expressed through mutual coherence is sufficient for a nonzero solution of (P0) to be the unique solution of both (P0) and (P1).The theorem is attributed to.Source: §3.2.1 · p. 11
3.2.2 Restricted Isometry Property
- The best-known stated RIP condition guarantees (P1) recovery of all k-sparse vectors when δ2k < 0.473.RIP measures how closely submatrices formed from k columns act as isometries, and the section also discusses error estimates for noisy data.Source: §3.2.2 · pp. 11–12
3.3 Necessary Conditions
- For polytope P = ACn, (P0) = (P1) if and only if P and Cn have the same number of k-faces.The face count corresponds to indexing sets whose supported vectors can be recovered via (P1); Donoho and Tanner also describe phase transitions across n/m and k/n [27].Source: §3.3 · p. 12
4 Sensing Matrices
Sensing matrices are assessed through spark, null space properties (NSP), mutual coherence, and the restricted isometry property (RIP), with relations among these measures guiding construction. Random Gaussian and Bernoulli matrices achieve RIP with a measurement bound whose dependence on sparsity and dimension is stated to be optimal up to constants.
4.1 Relations between Spark, NSP, Mutual Coherence, and RIP
- For normalized columns, spark is bounded below by 1 + 1/µ(A), and RIP of order 2k implies NSP of order 2k.The section also relates mutual coherence to RIP: δk = kµ(A) for k < µ(A)^−1.Source: §4.1 · p. 13
4.2 Spark and Mutual Coherence
- The discussed sensing matrices satisfy spark(A) = m + 1, but become badly conditioned as n → ∞.Other constructions generated from the Alltop sequence [38] or using Grassmannian frames [63] attain the optimal lower bound for m × m2 sensing matrices.Source: §4.2 · p. 13
- For the discussed mutual-coherence construction, k-sparse recovery requires m = O(k^2 log n) measurements.The survey’s ideal matrix properties—high spark, low mutual coherence, and small RIP constant—can be difficult to achieve, and computing the RIP constant is generally intractable.Source: §4 · p. 12, §4.2 · p. 13
4.3 RIP
- Deterministic RIP constructions still require measurements scaling quadratically in k, which the survey says is typically infeasible for applications.The cited constructions include DeVore’s m ≳ k^2 and Bourgain et al.’s m ≳ k^(2−α) for small α,.Source: §4.3 · p. 14
- If the distribution generating m × n matrices A satisfies concentration inequality (2) with ε = δ, there exist constants c1, c2 such that A satisfies RIP of order k with δ, with probability ≤ 1 − 2e^(−c2δ²m), for all k ≤ c1δ²m/log(n/k).Source: §4.3 · p. 14
- Gaussian and Bernoulli matrices satisfy RIP of order k with δ when m ≳ δ^-2k log(n/k), and this dependence on k and n is optimal up to a constant.The optimality claim follows from lower bounds for Gelfand widths of ℓ1-balls.Source: §4.3 · p. 14
5 Recovery Algorithms
The survey compares recovery algorithms by measurement requirements and computational cost: convex optimization uses few measurements but is more computationally complex, while combinatorial methods can be fast but may require many measurements. Greedy methods offer a compromise, and the section reviews convex, greedy, and combinatorial approaches.
5.1 Convex Optimization
- Convex optimization requires few measurements but is more computationally complex; research has somewhat reduced its computational disadvantage relative to greedy methods.Compressed-sensing algorithms include interior-point methods, projected gradient methods, and iterative thresholding [16].Source: §5 · p. 14, §5.1 · p. 15
- For noisy measurements, the convex optimization constraint must be conic, and a suitable regularization parameter gives an equivalent unconstrained formulation.The unconstrained objective is 1/2 ∥Ax − y∥_2^2 + λ∥x∥_1.Source: §5.1 · p. 15
5.2 Greedy Algorithms
- Greedy algorithms iteratively approximate signal coefficients and support, offering a speed and implementation advantage with theoretical guarantees often similar to ℓ1 minimization.Orthogonal Matching Pursuit (OMP) is a prominent example, described as approximating the solution of (P0).Source: §5.2 · p. 15, Figure 4 · p. 16
- OMPR includes most iterative hard-thresholding algorithms as special cases and permits the tightest known analysis in terms of RIP conditions.Extending OMPR with locality-sensitive hashing gives the first provably sub-linear sparse-recovery algorithm [40].Source: §5.2 · p. 15
5.3 Combinatorial Algorithms
- Combinatorial algorithms use group testing on highly structured samples and are less used than convex and greedy methods; examples include HHS pursuit and a sub-linear Fourier transform.Source: §5.3 · p. 16
6 Applications
The survey presents data separation and missing-data recovery as compressed sensing applications, using sparse representations to formulate both problems. It treats orthonormal bases and redundant frames, then notes additional application areas.
6.1 Data Separation
- Data separation asks how to extract x1 and x2 from their sum x when only x is given.The setup has two unknown components but only one observed datum.Source: §6.1 · p. 16
6.1.1 An Orthonormal Basis Approach
- With orthonormal bases, sparse coefficient vectors and an incoherent combined system frame data separation; Theorem 6.1 states a sparsity threshold of 1/2(1 + √n).The threshold applies to the sum of the two coefficient-vector sparsities.Source: §6.1.1 · p. 17
6.1.2 A Frame Approach
- For redundant Parseval frames, analysis-side ℓ1 minimization avoids searching infinitely many synthesis coefficients, which can cause numerical instabilities at high redundancy.The recovery analysis uses relative sparsity and cluster coherence; the theorem assumes δ-relative sparsity with respect to selected index sets.Source: §6.1.2 · p. 18
6.2 Recovery of Missing Data
- Missing-data recovery seeks the unknown x from its known component xK, a task the text describes as infeasible without additional information.The setup decomposes x into xK in W and xM in W⊥.Source: §6.2 · p. 19
6.2.1 An Orthonormal Basis Approach
- With an orthonormal sparsifying basis, recovery uses a sufficient condition requiring ∥Φ^T x∥0 < 1/2(1 + µ(PWΦ)^-1).The text identifies the recovered signal as x = Φc, where c is the sparse solution.Source: §6.2.1 · p. 20
6.2.2 A Frame Approach
- For a redundant Parseval frame, the missing-data approach places the ℓ1 norm on the analysis side and derives error analysis using relative sparsity and cluster coherence.Theorem 6.4 assumes δ-relative sparsity with respect to an index set.Source: §6.2.2 · p. 20
6.3 Further Applications
- The survey lists coding, machine learning, imaging, geophysical analysis, biology, remote sensing, radar, robotics, control, and A/D conversion among further applications.The authors refer readers elsewhere for an elaborate discussion of these topics.Source: §6.3 · p. 20