Machine Learning/Learning Center/Feature Selection & Sparse Learning/Compressive Sensing Fundamentals

Compressive Sensing Fundamentals

Discover how to recover complete signals from far fewer samples than traditional methods require. Learn the Restricted Isometry Property (RIP), understand signal sparsity assumptions, and master the sampling and reconstruction framework.

Module 6 of 8

Intermediate to Advanced

120-150 min

The Compressive Sensing Problem

Traditional signal processing requires sampling at the Nyquist rate (at least twice the highest frequency). Compressive sensing challenges this by showing that we can recover signals from far fewer samples if the signal is sparse in some domain.

Core Question

Can we recover an $n$ -dimensional signal $x$ from only $m \ll n$ measurements? The answer is yes, if $x$ is sparse!

Applications

• MRI reconstruction
• Sensor networks
• Image compression
• Data transmission
• Single-pixel cameras

Requirements

• Signal must be sparse
• Measurement matrix must satisfy RIP
• Requires optimization
• Sensitive to noise
• Computational complexity

Signal Sparsity Assumption

The fundamental assumption of compressive sensing is that the signal is sparse in some representation domain.

Sparsity Definition

A signal $x \in \mathbb{R}^n$ is k-sparse if it has at most $k$ non-zero elements:

\|x\|_0 = |\{i : x_i \neq 0\}| \leq k

where $\|\cdot\|_0$ is the L0 "norm" (count of non-zeros).

Transform Domain Sparsity

Often, signals are not sparse in their natural domain but sparse in a transform domain. For example, natural images are sparse in the wavelet or DCT domain:

x = \Psi s

where $\Psi$ is a transform matrix (e.g., Fourier, wavelet) and $s$ is a k-sparse vector.

Examples of Sparse Signals

Natural images: Sparse in wavelet/DCT domain (most coefficients near zero)
Audio signals: Sparse in frequency domain (few dominant frequencies)
Neural signals: Sparse in time domain (few active neurons)
Text documents: Sparse in word space (few relevant words)

Restricted Isometry Property (RIP)

RIP is the key property that measurement matrices must satisfy for successful compressive sensing recovery.

RIP Definition

A matrix $A \in \mathbb{R}^{m \times n}$ satisfies the Restricted Isometry Property of order $k$ with constant $\delta_k \in (0,1)$ if:

(1-\delta_k)\|s\|_2^2 \leq \|A_k s\|_2^2 \leq (1+\delta_k)\|s\|_2^2

for all k-sparse vectors $s$ , where $A_k$ is any $m \times k$ submatrix of $A$ (any k columns).

Interpretation

RIP ensures that the measurement matrix $A$ approximately preserves the norm of sparse vectors. This means:

• Different sparse vectors map to different measurements (injectivity)
• The measurement process doesn't lose critical information about sparse signals
• Recovery is theoretically possible from $m = O(k \log(n/k))$ measurements

Matrices Satisfying RIP

Common matrices that satisfy RIP with high probability:

Random Gaussian: Entries $A_{ij} \sim \mathcal{N}(0, 1/m)$
Random Bernoulli: Entries $A_{ij} = \pm 1/\sqrt{m}$ with equal probability
Subsampled Fourier: Random rows of the DFT matrix

These random matrices satisfy RIP with high probability when $m \geq C k \log(n/k)$ for some constant $C$ .

Sampling and Reconstruction Framework

The complete compressive sensing pipeline:

Step 1

Signal Representation

Original signal $x \in \mathbb{R}^n$ is sparse in transform domain:

x = \Psi s

where $\Psi$ is the transform matrix and $s$ is k-sparse.

Step 2

Low-Rate Sampling

Sample signal using measurement matrix $\Phi \in \mathbb{R}^{m \times n}$ :

y = \Phi x = \Phi \Psi s = A s

where $A = \Phi \Psi$ is the sensing matrix, and $y \in \mathbb{R}^m$ with $m \ll n$ .

Step 3

Sparse Recovery

Recover sparse vector $s$ from measurements $y$ :

\min \|s\|_0 \quad \text{s.t. } y = A s

This is NP-hard, but can be relaxed to L1 minimization (covered in next module).

Step 4

Signal Reconstruction

Reconstruct original signal: $\hat{x} = \Psi \hat{s}$ , where $\hat{s}$ is the recovered sparse vector.

Practical Example: MRI Reconstruction

Compressive sensing revolutionized MRI by enabling faster scans with fewer measurements.

Traditional MRI

Full k-space sampling requires $256 \times 256 = 65,536$ measurements. Scan time: 5-10 minutes.

Compressive Sensing MRI

Sample only $20\%$ of k-space ( $\approx 13,000$ measurements). Images are sparse in wavelet domain.

Result: 5x faster scans (1-2 minutes) with comparable image quality!

Impact

Enables real-time MRI, reduces patient discomfort, and increases scanner throughput. Critical for pediatric and emergency imaging.

Key Takeaways

Compressive sensing enables signal recovery from $m \ll n$ measurements when signals are sparse in some domain.

The Restricted Isometry Property (RIP) ensures measurement matrices preserve information about sparse signals, enabling recovery.

Random matrices (Gaussian, Bernoulli) satisfy RIP with high probability when $m = O(k \log(n/k))$ .

The sampling process: $y = \Phi x = A s$ where $A = \Phi \Psi$ is the sensing matrix.

Recovery requires solving L0 minimization (NP-hard), which is relaxed to L1 minimization in practice.

Applications include MRI, sensor networks, image compression, and any scenario where sampling is expensive or limited.

Next Module