Compressed Sensing: Theory and Applications

Gitta KutyniokarXiv 2012 · arXiv

Abstract

Compressed sensing (CS) is a revolutionary mathematical framework that enables the reconstruction of high-dimensional signals from significantly fewer measurements than required by the Nyquist-Shannon sampling theorem. By leveraging the inherent sparsity of natural signals, CS utilizes convex optimization and random sensing matrices to solve underdetermined systems. This paper surveys the fundamental pillars of CS, including sparsity models, sensing matrix properties, and recovery algorithms, while highlighting its practical applications and current theoretical limitations.

Introduction

For decades, signal processing has been governed by the Nyquist-Shannon sampling theorem, which states that a signal must be sampled at twice its highest frequency to ensure perfect reconstruction. However, in the age of high-resolution imaging and massive data acquisition, this requirement imposes significant burdens on hardware, storage, and transmission. Compressed sensing addresses this challenge by asking a fundamental question: can we recover a signal $x \in \mathbb{R}^n$ from a measurement vector $y \in \mathbb{R}^m$ where $m \ll n$?

While such a system is mathematically underdetermined, CS demonstrates that if the signal is sparse—meaning it has few non-zero coefficients in a specific basis—the problem becomes solvable. This paradigm shift moves the complexity from the acquisition stage to the computational reconstruction stage, enabling more efficient data capture.

Theoretical Foundations

The success of compressed sensing rests on three core components: sparsity models, sensing matrices, and recovery algorithms.

Sparsity and Transform Domains

Most natural signals are not sparse in their raw form but become sparse when represented in an appropriate basis, such as wavelets or shearlets. Beyond simple $k$-sparsity, the field considers "compressible" signals where coefficients decay rapidly, and "structured sparsity," which accounts for the hierarchical relationships often found in transform coefficients.

Figure 2: (a) Original image of the Mathematics building at TU Berlin. (b) Wavelet and shearlet decomposition demonstrating the sparsity of natural images in transform domains.

Sensing Matrices

To ensure that information is not lost during dimension reduction, the measurement matrix $A$ must satisfy properties like the Restricted Isometry Property (RIP) and Mutual Coherence. A key insight of CS is that random matrices (e.g., Gaussian or Bernoulli) are near-optimal sensing tools because they are highly likely to satisfy these properties, ensuring that the signal's information is spread across all measurements.

Recovery Algorithms

Since finding the absolute sparsest solution ($L_0$ minimization) is computationally NP-hard, CS relies on convex relaxation. Replacing the $L_0$ norm with the $L_1$ norm leads to Basis Pursuit, which can be solved efficiently via linear programming. Alternatively, greedy algorithms like Orthogonal Matching Pursuit (OMP) provide faster, iterative approaches to signal reconstruction.

Key Insights and Results

One of the most profound discoveries in CS is the "magic" of the $L_1$ norm. Geometrically, the $L_1$ ball's "pointy" vertices make it highly probable that the solution to a linear system will lie on a coordinate axis, naturally yielding a sparse result.

Theoretical results show that for a signal of length $n$ with $k$ non-zero entries, perfect recovery is possible with only $m \approx C \cdot k \log(n/k)$ measurements. This has led to successful applications in data separation (e.g., distinguishing spikes from sinusoids) and the recovery of missing data in fields ranging from medical imaging to seismic analysis.

Limitations and Future Directions

Despite its success, several challenges remain:

  • Hardware Implementation: While random matrices are theoretically optimal, they are difficult to implement in physical hardware. Developing deterministic matrices with similar performance is an active area of research.
  • Continuum Theory: Most existing theory applies to discrete data, necessitating a more robust framework for analog or continuum signals.
  • Dictionary Learning: Identifying the optimal sparse representation (dictionary) for non-standard data types remains a complex task.

Conclusion

Compressed sensing has transformed our understanding of data acquisition by proving that we can capture more with less. By shifting the burden from hardware to mathematics, it opens new frontiers in efficient sensing and high-dimensional signal processing.

Summary updated

Abstract

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.
BibTeX
@misc{kutyniok2012compressed,
  author = {Gitta Kutyniok},
  title = {{Compressed Sensing: Theory and Applications}},
  year = {2012},
  eprint = {1203.3815},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1203.3815},
}
Figure