8.4 Compressed sensing

Compressed sensing revolutionizes signal processing by efficiently acquiring and reconstructing sparse signals. It samples below the Nyquist rate while maintaining accuracy, leveraging signal structure through sparsity, incoherent sampling, and the restricted isometry property.

This technique has wide-ranging applications in medical imaging, radar, wireless networks, and more. It offers advantages like reduced sampling rates and simplified hardware, though it requires signals to be sparse or compressible in a known basis.

Compressed sensing fundamentals

• Compressed sensing is a signal processing technique that enables the efficient acquisition and reconstruction of sparse or compressible signals
• Leverages the inherent structure of signals to sample them at a rate significantly below the Nyquist rate while still allowing for accurate recovery
• Fundamental principles of compressed sensing include sparsity, incoherent sampling, and the restricted isometry property

Sparsity and compressibility

Top images from around the web for Sparsity and compressibility

• 

  GWRA: grey wolf based reconstruction algorithm for compressive sensing signals [PeerJ] View original

  Is this image relevant?

• 

  Structure of copper sites in zeolites examined by Fourier and wavelet transform analysis of ... View original

  Is this image relevant?

• 

  frequency spectrum - How do I interpret the result of a Fourier Transform? - Signal Processing ... View original

  Is this image relevant?

• 

  GWRA: grey wolf based reconstruction algorithm for compressive sensing signals [PeerJ] View original

  Is this image relevant?

• 

  Structure of copper sites in zeolites examined by Fourier and wavelet transform analysis of ... View original

  Is this image relevant?

1 of 3

Top images from around the web for Sparsity and compressibility

• 

  GWRA: grey wolf based reconstruction algorithm for compressive sensing signals [PeerJ] View original

  Is this image relevant?

• 

  Structure of copper sites in zeolites examined by Fourier and wavelet transform analysis of ... View original

  Is this image relevant?

• 

  frequency spectrum - How do I interpret the result of a Fourier Transform? - Signal Processing ... View original

  Is this image relevant?

• 

  GWRA: grey wolf based reconstruction algorithm for compressive sensing signals [PeerJ] View original

  Is this image relevant?

• 

  Structure of copper sites in zeolites examined by Fourier and wavelet transform analysis of ... View original

  Is this image relevant?

1 of 3

• Sparsity refers to the property of a signal having a small number of non-zero coefficients in a certain basis or dictionary
  • Example: A sine wave is sparse in the Fourier basis, as it can be represented by a single non-zero coefficient
• Compressibility is a more general concept, where a signal can be well-approximated by a sparse representation
  • Example: Natural images are often compressible in the wavelet domain, as most wavelet coefficients are close to zero
• Exploiting sparsity or compressibility is key to the success of compressed sensing, as it allows for significant reduction in the number of measurements required for signal recovery

Incoherent sampling

• Incoherent sampling ensures that the measurement basis is not aligned with the sparsity basis, enabling the capture of maximum information about the signal with minimal measurements
• Randomized sampling matrices, such as Gaussian or Bernoulli matrices, exhibit low coherence with most sparsity bases
  • Example: A random Gaussian matrix is incoherent with the canonical basis, making it suitable for compressed sensing
• Incoherent sampling enables the spreading of the signal information across the measurements, facilitating robust signal recovery

Restricted isometry property

• The restricted isometry property (RIP) characterizes the ability of a measurement matrix to preserve the distances between sparse signals
• A matrix satisfies the RIP if it acts as a near-isometry on sparse vectors, meaning that it approximately preserves their Euclidean lengths
  • Example: A random Gaussian matrix with a sufficient number of rows satisfies the RIP with high probability
• The RIP ensures that distinct sparse signals remain distinguishable after projection onto the measurement basis, enabling stable and robust signal recovery

Compressed sensing algorithms

• Compressed sensing algorithms aim to recover the original sparse or compressible signal from the compressed measurements
• These algorithms exploit the sparsity prior and the incoherence of the sampling process to efficiently solve the underdetermined system of linear equations
• Key categories of compressed sensing algorithms include basis pursuit, greedy algorithms, iterative thresholding, and convex optimization approaches

Basis pursuit

• Basis pursuit is a convex optimization approach that seeks the sparsest solution consistent with the measurements
• It formulates the signal recovery problem as a minimization of the $\ell_1$-norm of the signal coefficients subject to the measurement constraints
  • Example: $\min_x \|x\|_1$ subject to $y = Ax$, where $x$ is the sparse signal, $y$ is the measurement vector, and $A$ is the measurement matrix
• Basis pursuit can be solved efficiently using linear programming techniques, such as interior-point methods or the simplex algorithm

Greedy algorithms

• Greedy algorithms iteratively identify the support (non-zero locations) of the sparse signal and estimate the corresponding coefficients
• Examples of greedy algorithms include Orthogonal Matching Pursuit (OMP), Compressive Sampling Matching Pursuit (CoSaMP), and Subspace Pursuit (SP)
• These algorithms typically have lower computational complexity compared to basis pursuit but may require more measurements for accurate recovery

Iterative thresholding

• Iterative thresholding algorithms alternate between a gradient descent step and a thresholding operation to promote sparsity
• The gradient descent step minimizes the residual error between the measurements and the estimated signal, while the thresholding step sets small coefficients to zero
  • Example: Iterative Hard Thresholding (IHT) updates the signal estimate as $x^{k+1} = H_s(x^k + A^T(y - Ax^k))$, where $H_s$ is the hard thresholding operator that keeps the $s$ largest coefficients
• Iterative thresholding algorithms are computationally efficient and can handle large-scale problems

Convex optimization approaches

• Convex optimization approaches formulate the signal recovery problem as a convex program, which can be solved efficiently using standard optimization techniques
• Examples include the Least Absolute Shrinkage and Selection Operator (LASSO) and the Dantzig selector
• These approaches often incorporate additional regularization terms to promote desired properties such as sparsity or smoothness
  • Example: The LASSO minimizes the sum of squared errors plus an $\ell_1$-norm penalty on the coefficients, promoting sparsity: $\min_x \|y - Ax\|_2^2 + \lambda \|x\|_1$

Signal recovery guarantees

• Signal recovery guarantees provide theoretical assurances on the conditions under which compressed sensing algorithms can accurately recover the original signal from the compressed measurements
• These guarantees typically involve the sparsity level of the signal, the number of measurements, the coherence of the sampling matrix, and the presence of noise
• Key aspects of signal recovery guarantees include exact recovery conditions, stability and robustness, and the impact of noisy measurements

Exact recovery conditions

• Exact recovery conditions specify the sufficient conditions under which a compressed sensing algorithm can perfectly recover the original sparse signal
• These conditions often involve the restricted isometry property (RIP) of the measurement matrix and the sparsity level of the signal
  • Example: If the measurement matrix satisfies the RIP with a constant $\delta_{2s} < \sqrt{2} - 1$, then basis pursuit can exactly recover any $s$-sparse signal
• Exact recovery guarantees provide confidence in the ability of compressed sensing to accurately reconstruct sparse signals under ideal conditions

Stability and robustness

• Stability and robustness guarantees ensure that compressed sensing algorithms can recover signals that are approximately sparse or subject to perturbations
• Stability refers to the property that the recovered signal is close to the original signal when the measurements are slightly perturbed
  • Example: If the measurement matrix satisfies the RIP and the measurements are corrupted by bounded noise, then the recovered signal is within a certain distance of the original signal
• Robustness implies that the recovery algorithm can handle signals that are not exactly sparse but can be well-approximated by a sparse representation
  • Example: If a signal is compressible in a certain basis, then compressed sensing algorithms can recover a close approximation to the original signal

Noisy measurements

• In practical scenarios, measurements are often corrupted by noise, which can impact the accuracy of signal recovery
• Compressed sensing algorithms can be modified to handle noisy measurements by incorporating noise models and regularization techniques
  • Example: The Basis Pursuit Denoising (BPDN) algorithm minimizes the $\ell_1$-norm of the signal coefficients subject to a constraint on the $\ell_2$-norm of the residual error, accounting for Gaussian noise
• Theoretical guarantees for noisy compressed sensing provide bounds on the recovery error in terms of the noise level and the sparsity of the signal

Applications of compressed sensing

• Compressed sensing has found numerous applications across various fields, where the acquisition of high-dimensional signals can be costly, time-consuming, or limited by physical constraints
• By exploiting the sparsity or compressibility of signals, compressed sensing enables the efficient acquisition and processing of data in these applications
• Notable applications of compressed sensing include medical imaging, radar and remote sensing, wireless sensor networks, and compressive imaging

Medical imaging

• Compressed sensing has been applied to various medical imaging modalities, such as magnetic resonance imaging (MRI), computed tomography (CT), and ultrasound
• In MRI, compressed sensing allows for faster scan times by undersampling the k-space data and reconstructing the image using sparsity-based algorithms
  • Example: Compressed sensing MRI can reduce scan times by 30-50% while maintaining image quality, benefiting patient comfort and throughput
• Compressed sensing techniques have also been used to reduce radiation dose in CT imaging by acquiring fewer projections and reconstructing the image using prior knowledge of its sparsity

Radar and remote sensing

• Compressed sensing has been employed in radar and remote sensing applications to improve the resolution and reduce the data acquisition requirements
• In radar imaging, compressed sensing enables the use of fewer measurements to reconstruct high-resolution images of targets
  • Example: Compressive radar imaging can achieve sub-Nyquist sampling rates while maintaining the ability to detect and locate targets
• Compressed sensing techniques have also been applied to hyperspectral remote sensing, where the high-dimensional spectral data can be efficiently acquired and processed using sparse representations

Wireless sensor networks

• Wireless sensor networks often face challenges related to limited power, bandwidth, and computational resources
• Compressed sensing allows for the efficient acquisition and transmission of sensor data by exploiting the sparsity of the monitored signals
  • Example: Compressive sensing can be used to reduce the number of samples transmitted by each sensor node, prolonging the network lifetime and reducing communication overhead
• Compressed sensing techniques have been applied to various sensing tasks, such as environmental monitoring, structural health monitoring, and event detection

Compressive imaging

• Compressive imaging refers to the acquisition of images using a reduced number of measurements compared to traditional imaging systems
• Compressed sensing principles are employed to design imaging systems that directly acquire compressed measurements of the scene
  • Example: The single-pixel camera uses a spatial light modulator to perform random projections of the scene onto a single photodetector, enabling the reconstruction of an image from a small number of measurements
• Compressive imaging has applications in areas such as hyperspectral imaging, terahertz imaging, and microscopy, where the acquisition of high-dimensional data can be challenging or expensive

Compressed sensing vs traditional sampling

• Compressed sensing represents a paradigm shift from traditional sampling methods, such as Nyquist sampling, which require a sampling rate at least twice the highest frequency component of the signal
• By exploiting the sparsity or compressibility of signals, compressed sensing enables the acquisition of signals at rates significantly below the Nyquist rate
• Key aspects of compressed sensing compared to traditional sampling include sampling rate reduction, advantages and limitations, and hardware implementations

Sampling rate reduction

• Compressed sensing allows for the reduction of the sampling rate below the Nyquist rate while still enabling accurate signal recovery
• The required sampling rate depends on the sparsity level of the signal and the incoherence of the sampling process
  • Example: If a signal has only $k$ non-zero coefficients in a certain basis, compressed sensing can recover the signal from approximately $k \log(n/k)$ measurements, where $n$ is the signal dimension
• Sampling rate reduction has significant implications for applications where high-rate sampling is costly, impractical, or limited by physical constraints

Advantages and limitations

• Compressed sensing offers several advantages over traditional sampling methods:
  • Reduced sampling rate, leading to faster data acquisition and lower storage requirements
  • Simplified hardware design, as the sampling process can be performed using random projections
  • Robustness to measurement noise and signal perturbations
• However, compressed sensing also has some limitations:
  • The signal must be sparse or compressible in a known basis or dictionary
  • The reconstruction algorithms can be computationally intensive, especially for large-scale problems
  • The design of incoherent sampling matrices and the implementation of compressed sensing hardware can be challenging

Hardware implementations

• Compressed sensing principles have been implemented in various hardware systems to realize the benefits of reduced sampling rates and simplified acquisition
• Examples of compressed sensing hardware include:
  • Random demodulation, which uses a random modulation sequence and low-pass filtering to acquire compressed measurements of sparse analog signals
  • Compressive imaging systems, such as the single-pixel camera, which employ spatial light modulators to perform random projections of the scene
• The design of compressed sensing hardware involves considerations such as the generation of random sampling patterns, the implementation of analog-to-digital converters, and the integration with reconstruction algorithms

Extensions and variations

• Compressed sensing has been extended and adapted to various settings beyond the standard sparse signal recovery problem
• These extensions and variations aim to address more complex signal structures, incorporate additional prior knowledge, or handle specific application scenarios
• Notable extensions and variations of compressed sensing include structured sparsity models, dictionary learning, matrix completion, and low-rank matrix recovery

Structured sparsity models

• Structured sparsity models capture the dependencies and correlations among the non-zero coefficients of a sparse signal
• Examples of structured sparsity models include:
  • Group sparsity, where coefficients are organized into groups, and the entire group is encouraged to be either zero or non-zero
  • Tree sparsity, where the non-zero coefficients are assumed to follow a tree-structured pattern
• Structured sparsity models can lead to improved recovery performance and interpretability of the results
  • Example: In image compression, structured sparsity models can exploit the spatial correlations among wavelet coefficients to achieve better compression rates

Dictionary learning

• Dictionary learning aims to adapt the sparsifying basis or dictionary to the specific signal class of interest
• Instead of using a fixed basis, such as wavelets or Fourier, dictionary learning algorithms jointly estimate the dictionary and the sparse signal representations
  • Example: The K-SVD algorithm alternates between sparse coding and dictionary update steps to learn an overcomplete dictionary that best represents the training signals
• Learned dictionaries can provide more compact and expressive representations of signals, leading to improved sparse recovery and classification performance

Matrix completion

• Matrix completion deals with the recovery of a low-rank matrix from a subset of its entries
• Compressed sensing techniques can be applied to matrix completion by treating the matrix as a sparse signal in the singular value domain
  • Example: In collaborative filtering for recommender systems, matrix completion can be used to estimate missing ratings based on a partially observed user-item matrix
• Matrix completion has applications in various domains, such as image and video processing, sensor network localization, and bioinformatics

Low-rank matrix recovery

• Low-rank matrix recovery aims to reconstruct a low-rank matrix from linear measurements or observations
• Compressed sensing principles can be extended to handle low-rank matrices by exploiting the sparsity of the matrix in the singular value domain
  • Example: The matrix Dantzig selector estimates a low-rank matrix by minimizing the nuclear norm (sum of singular values) subject to measurement constraints
• Low-rank matrix recovery has applications in areas such as system identification, quantum state tomography, and phase retrieval
• The extension of compressed sensing to low-rank matrix recovery has led to the development of efficient algorithms and theoretical guarantees for recovering low-rank matrices from incomplete or noisy measurements