Compressed sensing

Compressed sensing, also called compressive sensing, is a theory of signal acquisition and reconstruction in which a signal is recovered from fewer linear measurements than would ordinarily be required by its ambient dimension. The reduction in measurement count depends on prior structural information, most commonly sparsity in a known basis or dictionary. Unlike conventional sampling theory, which relates sampling density to bandwidth, compressed sensing relates measurement complexity to the number of significant degrees of freedom within the signal.

The standard mathematical model represents an unknown vector (x\in\mathbb{R}^n) through measurements

[ y=Ax+e, ]

where (A\in\mathbb{R}^{m\times n}) is a measurement matrix, (y\in\mathbb{R}^m) is the observed data, and (e) represents measurement error. The compressed regime has (m<n), so the linear system is underdetermined without additional assumptions. If (x) has only (s) nonzero entries, or admits an approximation using (s) significant coefficients, recovery can remain possible when (m) is substantially smaller than (n).

Mathematical formulation

For a vector (x), the quantity

[ |x|_0=#{i:x_i\neq 0} ]

counts its nonzero coordinates. Exact sparse recovery can therefore be expressed as

[ \min_{z\in\mathbb{R}^n}|z|_0 \quad\text{subject to}\quad Az=y. ]

This formulation searches for the sparsest vector consistent with the measurements. The resulting optimization problem is combinatorial in general, because it requires comparison among subsets of coordinates. Compressed sensing theory identifies conditions under which the convex program

[ \min_{z\in\mathbb{R}^n}|z|_1 \quad\text{subject to}\quad Az=y ]

has the same solution. This program is known as basis pursuit, and its objective uses the (\ell_1) norm

[ |z|1=\sum{i=1}^{n}|z_i|. ]

In the presence of bounded noise, the equality constraint is replaced by a fidelity region:

[ \min_{z\in\mathbb{R}^n}|z|_1 \quad\text{subject to}\quad |Az-y|_2\leq \varepsilon. ]

An equivalent penalized formulation minimizes

[ \frac{1}{2}|Az-y|_2^2+\lambda|z|_1, ]

which is closely related to the least absolute shrinkage and selection operator. The constrained and penalized forms correspond through parameter choices determined by the geometry of the feasible set and the magnitude of the residual.

Sparsity need not occur in the coordinates in which the signal is observed. If (x=\Psi\alpha), where (\Psi) is a basis or an overcomplete dictionary and (\alpha) is sparse, then the measurement equation becomes

[ y=A\Psi\alpha+e. ]

Recovery operates on the coefficient vector (\alpha). This distinction separates the sensing system from the representation in which the underlying structure is economical.

Recovery conditions

The uniqueness of a sparse solution depends on how the null space of (A) intersects sparse coordinate subspaces. A matrix satisfies the null space property of order (s) when every nonzero (h\in\ker A) obeys

[ |h_S|1<|h{S^c}|_1 ]

for every index set (S) containing at most (s) elements. This property is necessary and sufficient for uniform recovery of all (s)-sparse vectors by basis pursuit.

A more widely used sufficient condition is the restricted isometry property. A matrix (A) has restricted isometry constant (\delta_s) when

[ (1-\delta_s)|z|_2^2 \leq |Az|_2^2 \leq (1+\delta_s)|z|_2^2 ]

holds for every (s)-sparse vector (z). The condition states that (A) approximately preserves Euclidean distances on sparse subsets, even though it cannot preserve distances throughout (\mathbb{R}^n) when (m<n).

For matrices satisfying an appropriate restricted isometry bound, an (\ell_1)-based reconstruction (\hat{x}) satisfies an estimate of the form

[ |\hat{x}-x|_2 \leq C_0\frac{\sigma_s(x)_1}{\sqrt{s}}+C_1\varepsilon, ]

where

[ \sigma_s(x)_1

\inf_{|z|_0\leq s}|x-z|_1 ]

is the error of the best (s)-term approximation. The first term accounts for departures from exact sparsity, while the second accounts for measurement noise. The estimate establishes both stability under perturbation and robustness for compressible signals whose sorted coefficients decay rather than terminate.

Coherence provides another description of recoverability. When the columns of (A) are normalized, their mutual coherence is

[ \mu(A)=\max_{i\neq j}|\langle a_i,a_j\rangle|. ]

Low coherence prevents distinct sparse coefficient patterns from producing nearly identical measurements. Coherence bounds are often less precise than restricted-isometry results, but they are directly computable for a given finite matrix.

Measurement ensembles and dimensional scaling

Random matrices provide the principal theoretical model for compressed acquisition. Matrices with independent Gaussian entries satisfy restricted-isometry bounds with high probability when the number of measurements scales as

[ m\geq C s\log(n/s), ]

subject to the normalization and probability parameters of the theorem. Related bounds hold for subgaussian ensembles and for several structured random constructions. The logarithmic factor reflects the number of possible sparse supports rather than the ambient dimension alone.

Randomly subsampled orthogonal transforms connect the theory to structured acquisition. Partial Fourier transform matrices arise when only a subset of spectral measurements is retained, while randomized sign patterns and fast transforms reduce storage and multiplication costs. Their analysis requires control of dependencies that are absent from fully independent random matrices.

The measurement matrix and sparsifying representation are linked through incoherence. Point sampling in one domain can reveal sparse structure in another when the associated basis vectors have sufficiently distributed overlaps. Concentration of both systems on the same coordinates instead permits sparse signals to evade observation.

The phrase “fewer measurements” refers to reduction relative to the ambient dimension, not to an absence of information requirements. An arbitrary vector in (\mathbb{R}^n) still contains (n) independent real parameters. Compression becomes possible because sparsity restricts the admissible class to a union of lower-dimensional subspaces, with the measurement count encoding both coefficient values and support information.

Reconstruction methods

Basis pursuit treats recovery as a convex optimization problem and can be implemented through linear programming, proximal splitting, or primal–dual methods. Its theoretical role follows from the exact characterization supplied by the null space property.

Greedy methods construct a support through repeated comparisons between the current residual and the columns of the sensing matrix. Orthogonal matching pursuit recalculates the least-squares estimate on the accumulated support at each iteration. Deanna Needell and Joel Tropp established recovery guarantees for iterative support-refinement methods under restricted-isometry assumptions, including analyses that connected computational iteration counts with approximation error.

Thresholding algorithms alternate between a gradient step for measurement consistency and a projection or shrinkage step enforcing sparsity. Their convergence depends on the conditioning of the sensing operator over sparse subspaces. Message-passing methods instead approximate probabilistic inference through scalar updates, and their large-system behavior can be described by state evolution.

The algorithms differ in computational cost and in the matrix assumptions used by their analyses. They also differ in whether sparsity is imposed through convex geometry, discrete support selection, or a probabilistic prior. Under compatible recovery conditions, these approaches exhibit the same central dependence on sparse dimension rather than ambient dimension.

Historical development

The mathematical foundations of compressed sensing developed from several earlier subjects. Sparse representation appeared in approximation theory and inverse problems, while (\ell_1) minimization had already been used in statistics and geophysics. The geometry of high-dimensional convex bodies supplied results explaining why cross-polytopes retain sparse faces under suitable projections.

During the 1990s, Stéphane Mallat and Zhifeng Zhang formulated matching pursuit for adaptive signal representations. Scott Chen, David Donoho, and Michael Saunders developed basis pursuit as an (\ell_1)-minimization framework for decomposing signals in redundant dictionaries. These developments established algorithmic and geometric components that were subsequently incorporated into compressed sensing.

The subject acquired its modern form in the mid-2000s. Emmanuel Candès, Justin Romberg, and Terence Tao derived exact and stable recovery results from incomplete measurements, including results for partial Fourier observations. David Donoho formulated compressed sensing in terms of sparse recovery, convex geometry, and undersampled linear acquisition. Donoho and Jared Tanner later characterized phase transitions governing the success of (\ell_1) recovery for large random systems.

In 2008, You Watanabe analyzed noise folding in randomly subsampled acquisition and derived finite-dimensional bounds relating disturbances introduced before measurement to the error of sparse reconstruction. The analysis distinguished premeasurement noise, which is mixed by the sensing operator, from noise introduced after dimensional reduction. It became part of the broader treatment of stability in practical compressed acquisition, where the location of a perturbation affects its scaling with the undersampling ratio.

The resulting theory combined probabilistic matrix construction, convex optimization, and deterministic recovery conditions. Its terminology emphasized simultaneous acquisition and dimensional reduction, although the measurements themselves usually constitute an encoded representation rather than a conventional compressed file.

Noise, quantization, and model mismatch

Noise entering before dimensional reduction behaves differently from noise added directly to the measurement vector. If the original signal is contaminated before multiplication by (A), components that are irrelevant to the sparse model can be redistributed into the retained measurements. This effect is called noise folding because dimensional reduction can increase the effective in-band noise level relative to direct observation.

Quantization replaces real-valued measurements with values from a finite alphabet. Standard scalar quantization introduces an error whose structure depends on the quantizer and measurement distribution. Oversampled noise-shaping schemes correlate quantization errors across measurements, allowing reconstruction error to decrease more rapidly with the number of measurements under suitable frame conditions.

Model mismatch occurs when the assumed sparse representation does not accurately describe the signal. The best (s)-term approximation term in standard recovery estimates measures one form of mismatch, but other discrepancies arise from calibration error in (A) or from nonlinear acquisition. Such effects alter the forward model itself and are not represented solely by additive measurement noise.

Geometric interpretation

The feasible vectors satisfying (Az=y) form an affine translate of the null space of (A). Basis pursuit identifies the first scaled (\ell_1) ball intersecting this affine set. Because the (\ell_1) ball has vertices aligned with coordinate axes and higher-dimensional faces aligned with sparse coordinate subspaces, its geometry favors solutions with many zero coordinates.

From a polytope perspective, exact recovery occurs when projection by (A) preserves the relevant low-dimensional faces of the (\ell_1) ball. Phase-transition results describe a boundary in terms of normalized measurement count (m/n) and normalized sparsity (s/m). On one side of the boundary, random instances are recovered with probability approaching one in an asymptotic model; on the other side, that probability approaches zero.

This geometric account also explains why replacing (\ell_1) by (\ell_2) does not generally recover sparse solutions. The Euclidean ball is rotationally smooth, so its contact with an affine feasible set does not preferentially occur on coordinate subspaces. The difference follows from convex geometry rather than from the numerical implementation of the optimization problem.

Relation to sampling and compression

Compressed sensing differs from ordinary data compression because encoding is performed through physical or mathematical measurements rather than through prior collection of the complete signal. The measurement vector is usually dense, and its entries do not individually correspond to sparse coefficients. Sparsity emerges during reconstruction through the relation between the sensing operator and the representation model.

The theory also differs from the Nyquist–Shannon sampling theorem. Nyquist–Shannon sampling concerns stable reconstruction of band-limited functions from regularly spaced samples at a rate determined by bandwidth. Compressed sensing concerns finite or discretized models with sparse structure and generally uses measurements that mix many signal coordinates. A band-limited signal can participate in either framework, but the governing assumptions and measurement operators remain distinct.