Chapter 137. Compressed Sensing

137.1 Introduction

Compressed sensing is a method for recovering sparse or compressible signals from fewer linear measurements than ordinary sampling theory might suggest.

The central idea is simple. If a signal has only a small amount of essential information, then it may be possible to recover it from a small number of carefully chosen measurements. The recovery problem is underdetermined, but sparsity makes the problem solvable.

Compressed sensing studies systems of the form

where:

Usually,

with

Thus there are fewer equations than unknowns. Without additional structure, the system has many solutions. Compressed sensing uses sparsity to select the correct one. This is why the subject belongs naturally to linear algebra, optimization, probability, and signal processing. Compressed sensing is commonly described as recovery from underdetermined linear systems by exploiting sparsity and incoherence.

137.2 Sparse Signals

A vector

is called $k$-sparse if it has at most $k$ nonzero entries.

The number of nonzero entries is written

Thus $x$ is $k$-sparse if

The notation $\|\cdot\|_0$ is common but slightly misleading. It is not a norm. It counts nonzero coordinates.

For example,

is $2$-sparse.

Sparse vectors appear when most coordinates carry no information. In applications, many signals are not sparse in their original coordinates but become sparse after a change of basis.

137.3 Compressible Signals

A signal is compressible if it is well approximated by a sparse signal.

For example, a vector may have many nonzero entries, but most of them may be small. Keeping only the largest $k$ entries gives a sparse approximation.

Let $x_k$ denote the best $k$-sparse approximation to $x$. Then the approximation error is

Compressed sensing is useful when this error is small.

Compressibility is important because real data is rarely exactly sparse. Images, audio, physical signals, and scientific data usually have many small coefficients rather than exactly zero coefficients.

137.4 Sparse Bases

A signal may be sparse in one basis and dense in another.

Let

be a basis matrix. A signal $x$ can be written as

where $s$ is the coefficient vector.

If $s$ is sparse, then $x$ is sparse in the basis $\Psi$.

Common sparsifying systems include:

Thus compressed sensing often recovers sparse coefficients rather than raw signal coordinates.

137.5 Linear Measurements

Compressed sensing takes measurements of the form

where $a_i$ is the $i$-th sensing vector.

Collecting all measurements gives

Each row of $A$ defines one linear measurement.

If $m<n$, the system is underdetermined. The null space of $A$ has positive dimension, so many vectors satisfy the same measurement equation.

The goal is not to recover every vector. The goal is to recover sparse vectors.

137.6 The Recovery Problem

The ideal sparse recovery problem is:

subject to

This asks for the sparsest vector consistent with the measurements.

However, $\ell_0$-minimization is computationally difficult in general. The problem is combinatorial because it searches over possible support sets.

A common relaxation replaces $\|z\|_0$ with the $\ell^1$-norm:

subject to

Here

The $\ell^1$-problem is convex and can be solved by standard optimization methods. The use of $\ell^1$-relaxation is a central technique in compressed sensing.

137.7 Basis Pursuit

The problem

is called basis pursuit.

It is the standard noiseless recovery method.

The geometric reason basis pursuit works is that the $\ell^1$-ball has corners aligned with coordinate axes. Sparse vectors lie on these corners. When the affine space

intersects the $\ell^1$-ball, the first point of contact is often sparse.

This is a linear-algebraic and convex-geometric phenomenon.

137.8 Noisy Measurements

In practice, measurements contain noise:

where $e$ is an error vector.

The recovery problem becomes:

subject to

This is called basis pursuit denoising.

The constraint allows the reconstructed signal to fit the measurements up to the expected noise level.

Compressed sensing theory distinguishes two properties:

Stable recovery is essential for real applications. Standard compressed sensing theory treats both noisy measurements and signals that are only approximately sparse.

137.9 The Null Space View

The null space of $A$ determines whether sparse recovery is possible.

Suppose

If $h\in\ker A$, then

Thus $x$ and $x+h$ produce the same measurements.

For recovery to succeed, no nonzero vector in the null space should allow one sparse vector to be confused with another sparse vector.

The null space property gives a necessary and sufficient condition for exact sparse recovery by $\ell^1$-minimization. It is important theoretically, although it may be difficult to verify directly.

137.10 Restricted Isometry Property

The restricted isometry property, or RIP, is one of the main sufficient conditions for compressed sensing.

A matrix $A$ satisfies the restricted isometry property of order $k$ if there exists a number $\delta_k\in(0,1)$ such that

for every $k$-sparse vector $x$.

This says that $A$ approximately preserves the lengths of all $k$-sparse vectors.

If $A$ preserves distances between sparse vectors, then sparse vectors remain distinguishable after measurement.

RIP connects compressed sensing with geometry. The sensing matrix acts almost like an isometry on sparse subspaces.

137.11 Incoherence

Incoherence measures how poorly aligned the measurement system is with the sparsifying system.

If the signal is sparse in basis $\Psi$, and measurements are taken in another system $\Phi$, then compressed sensing works best when $\Phi$ and $\Psi$ are incoherent.

Informally, each measurement should see many coordinates of the sparse representation rather than only one.

Random measurements are often incoherent with fixed sparse bases.

This explains why random sensing matrices appear frequently in compressed sensing theory.

137.12 Random Sensing Matrices

Random matrices are common sensing matrices.

Examples include:

Random matrices often satisfy RIP with high probability when

is proportional to

This means that the number of measurements depends mainly on sparsity $k$, not ambient dimension $n$.

Many random designs give near-optimal sample complexity for sparse recovery.

137.13 Measurement Complexity

A guiding estimate in compressed sensing is:

Here:

The logarithmic factor appears because the support of a sparse vector is unknown.

There are

possible support sets.

The measurements must identify both the values on the support and the support itself.

This estimate explains the power of compressed sensing. When $k\ll n$, far fewer than $n$ measurements may be enough.

137.14 Support Recovery

The support of a vector is the set of indices where it is nonzero:

Recovering a sparse vector involves two tasks:

1. Identify the support,
2. Estimate the nonzero values.

If the support were known, recovery would reduce to an ordinary least squares problem using the corresponding columns of $A$.

The difficulty is that the support is unknown.

Many algorithms can be understood as different strategies for finding or approximating the support.

137.15 Greedy Algorithms

Greedy algorithms recover sparse signals by selecting columns of $A$ step by step.

Important examples include:

Greedy methods are often faster than convex optimization methods.

They are useful when large-scale computation is more important than solving a convex program exactly.

137.16 Orthogonal Matching Pursuit

Orthogonal Matching Pursuit, or OMP, builds a support set iteratively.

At each step:

1. Compute the residual

2. Find the column of $A$ most correlated with $r$.
3. Add that column to the active set.
4. Solve a least squares problem on the active set.
5. Update the residual.

The algorithm stops when the residual is small or when a desired sparsity level is reached.

OMP is simple, interpretable, and often effective.

137.17 Lasso

The Lasso solves the penalized problem

The first term measures data fit. The second term promotes sparsity.

The parameter

controls the tradeoff.

Large $\lambda$ produces sparser solutions. Small $\lambda$ fits the data more closely.

Lasso is widely used in statistics and machine learning.

It is closely related to basis pursuit denoising.

137.18 Geometry of $\ell^1$-Minimization

The $\ell^1$-norm promotes sparsity because its unit ball has sharp corners.

In two dimensions, the $\ell^1$-unit ball is a diamond:

In higher dimensions, the corners correspond to sparse coordinate patterns.

When minimizing $\ell^1$ over an affine space, the solution often occurs at a low-dimensional face of the $\ell^1$-ball. Such faces correspond to sparse vectors.

This geometric fact explains why a convex norm can recover sparse solutions.

137.19 Dictionaries

A dictionary is a collection of atoms used to represent signals.

Let

be a dictionary matrix. A signal is represented as

The coefficient vector $\alpha$ may be sparse even when $D$ has more columns than rows.

If

the dictionary is overcomplete.

Compressed sensing with dictionaries solves

and attempts to recover sparse $\alpha$.

Dictionaries may be fixed, such as wavelets, or learned from data.

137.20 Applications

Compressed sensing appears in many areas.

MRI is one of the standard application areas, since many medical images are sparse or compressible in transform domains and the measurements are naturally related to Fourier samples.

137.21 Summary

Compressed sensing studies recovery of sparse signals from undersampled linear measurements.

The main concepts are:

Compressed sensing shows that linear systems with fewer equations than unknowns can still be solvable when the unknown vector has sparse structure. It combines linear algebra, convex geometry, probability, and optimization into a theory of efficient acquisition and reconstruction.