Compressed Sensing

The foundational principle of Compressed Sensing is the ability to sample well below the Nyquist rate while still enabling perfect signal reconstruction. Unlike uniform sampling, CS acquires random linear combinations of the signal through a measurement matrix. The number of measurements required, M, scales logarithmically with the signal dimension N and linearly with the sparsity level K: M ≈ O(K log(N/K)). This enables dramatic reductions in sampling hardware, analog-to-digital converter (ADC) bandwidth, and data storage requirements in applications like wideband spectrum sensing and radar.

CS relies on two fundamental mathematical conditions. First, the signal must be K-sparse in some known basis or dictionary Ψ, meaning it can be represented with only K non-zero coefficients. Second, the sensing matrix Φ and the sparsity basis Ψ must be incoherent—the rows of Φ cannot sparsely represent the columns of Ψ and vice versa. Random matrices (Gaussian, Bernoulli) exhibit high incoherence with any fixed basis with overwhelming probability, making them universal CS measurement operators. In massive MIMO, the angular domain sparsity of the channel provides the necessary compressibility.

Signal reconstruction from compressed measurements is an underdetermined inverse problem. While finding the sparsest solution via L0-norm minimization is NP-hard, CS theory proves that L1-norm minimization (basis pursuit) yields the exact sparse solution under the Restricted Isometry Property (RIP). The convex optimization problem: min ||x||₁ subject to y = Φx can be solved efficiently using interior-point methods. This is the theoretical backbone for algorithms like LASSO and forms the benchmark against which greedy and deep learning-based recovery methods are evaluated.

For real-time applications where convex optimization is too slow, greedy iterative algorithms provide computationally efficient alternatives. Algorithms like Orthogonal Matching Pursuit (OMP), Compressive Sampling Matching Pursuit (CoSaMP), and Iterative Hard Thresholding (IHT) build the sparse support set one atom at a time by correlating the residual with the sensing matrix columns. While lacking the theoretical elegance of L1 minimization, these methods offer orders-of-magnitude faster reconstruction and are widely deployed in practical CS systems, including early CSI feedback schemes in massive MIMO.

A modern paradigm bridging model-based and data-driven methods, deep unfolding maps the iterative steps of a sparse recovery algorithm (e.g., ISTA) into the layers of a neural network. Each layer performs a gradient descent step followed by a learnable soft-thresholding operation: x^(k+1) = η_θ(x^(k) + ρΦᵀ(y - Φx^(k))). The step size ρ and threshold θ are learned end-to-end from data. This approach achieves 10-100x faster convergence than classical iterative methods while maintaining theoretical interpretability, making it ideal for latency-sensitive CSI reconstruction in 5G.

The Restricted Isometry Property (RIP) is the central theoretical condition that guarantees robust CS recovery. A measurement matrix Φ satisfies the RIP of order K with constant δ_K if for all K-sparse vectors x: (1-δ_K)||x||₂² ≤ ||Φx||₂² ≤ (1+δ_K)||x||₂². Intuitively, RIP ensures that Φ approximately preserves the Euclidean distance between any two K-sparse signals, preventing distinct sparse vectors from mapping to the same measurement. Random matrices with sufficiently many rows satisfy RIP with high probability, providing the mathematical foundation for CS guarantees.

Compressed sensing exploits sparsity in a known transform domain to recover signals from under-sampled measurements. In wireless channels, the angular domain sparsity of massive MIMO means the channel matrix has only a few significant multipath components. Algorithms like Orthogonal Matching Pursuit (OMP) and Basis Pursuit Denoising solve the ℓ₁-minimization problem to reconstruct the full channel from compressed pilot observations, dramatically reducing the number of required measurements below the Nyquist rate.

In FDD massive MIMO systems, the UE must report downlink CSI back to the base station, creating enormous feedback overhead proportional to the number of antennas. Compressed sensing reduces this by encoding the sparse angular-domain representation instead of the full channel matrix. The seminal CsiNet architecture later improved upon this by using deep autoencoders, but the theoretical foundation remains compressive sensing: exploiting the inherent low-rank structure of the channel to achieve compression ratios of 4x to 16x with minimal NMSE degradation.

The measurement process in compressed sensing uses a sensing matrix that must satisfy the Restricted Isometry Property (RIP) to guarantee stable recovery. Common choices include:

• Gaussian random matrices: Optimal RIP properties but impractical for hardware
• Bernoulli matrices: Binary ±1 entries, easier to implement
• Partial Fourier matrices: Naturally suited for OFDM systems where pilot subcarriers serve as the measurement basis In 5G NR, the structured placement of CSI-RS pilots effectively implements a deterministic sensing matrix for channel estimation.

Traditional iterative sparse recovery algorithms like ISTA (Iterative Shrinkage-Thresholding Algorithm) require many iterations to converge. Deep unfolding maps each iteration into a neural network layer with learnable parameters, reducing the required iterations from hundreds to 5-10 layers while improving accuracy. This model-driven approach combines the theoretical guarantees of compressed sensing with the speed of deep learning, enabling real-time channel estimation within the strict latency budgets of 5G transmission time intervals.

The number of pilots required for channel estimation scales with the number of antennas in classical methods. Compressed sensing breaks this scaling by exploiting joint sparsity across the antenna array. When multiple antennas observe the same sparse multipath environment, the channel vectors share a common support set. Techniques like Distributed Compressed Sensing and Multiple Measurement Vector (MMV) recovery jointly estimate all antenna channels from a reduced pilot set, cutting pilot overhead by 50-75% in typical urban macro-cell deployments.

While modern systems increasingly use deep learning for CSI compression, compressed sensing offers distinct advantages:

• Theoretical guarantees: RIP-based recovery bounds provide worst-case performance assurances
• Interpretability: The sparse basis and sensing matrix are physically meaningful
• Generalization: Model-based methods do not require retraining for new channel conditions Hybrid approaches like deep unfolding combine the best of both worlds, using learned shrinkage functions within a compressive sensing framework to achieve state-of-the-art NMSE performance below -15 dB at high compression ratios.

The fundamental property that makes compressed sensing possible. A signal is sparse if it can be represented with a small number of non-zero coefficients in a specific transform domain, such as the angular domain or delay-Doppler domain.

• K-sparse: A signal with at most K non-zero components.
• Compressible: A signal whose sorted coefficients decay rapidly following a power law.
• In massive MIMO, the channel matrix exhibits angular domain sparsity because multipath components arrive from a limited set of discrete angles.

Incoherence quantifies the maximum correlation between the sensing matrix (how you measure) and the sparsifying basis (where the signal is sparse). Low incoherence is essential for successful recovery.

• Measured by the mutual coherence constant μ.
• Random sensing matrices (e.g., Gaussian, Bernoulli) exhibit low incoherence with any fixed basis with high probability.
• In CSI feedback, the design of the pilot pattern and the compression matrix must ensure incoherence with the angular-domain channel representation.

A condition on the sensing matrix that guarantees stable and robust recovery of sparse signals. A matrix A satisfies the RIP of order K if it approximately preserves the Euclidean length of all K-sparse vectors.

• The restricted isometry constant δ_K must be sufficiently small (δ_2K < √2 - 1 for exact recovery).
• Verifying RIP for a given matrix is NP-hard, but random matrices satisfy it with overwhelming probability.
• RIP provides the theoretical guarantee that ℓ₁-minimization will recover the true sparse signal.

The convex optimization problem at the heart of sparse recovery. Instead of solving the NP-hard ℓ₀-minimization (counting non-zero entries), compressed sensing solves the tractable ℓ₁-norm minimization.

• Basis Pursuit: min ||x||₁ subject to y = Ax.
• Basis Pursuit Denoising (BPDN): min ||x||₁ subject to ||y - Ax||₂ ≤ ε, for noisy measurements.
• The ℓ₁-norm acts as a convex surrogate for sparsity, promoting solutions with few non-zero coefficients.

Iterative algorithms that build a sparse solution by selecting one or more support elements per iteration. They offer lower computational complexity than convex optimization at the cost of slightly weaker recovery guarantees.

• Orthogonal Matching Pursuit (OMP): Selects the column most correlated with the residual, then projects the measurement onto the span of all selected columns.
• Compressive Sampling Matching Pursuit (CoSaMP): Selects 2K candidates per iteration, solves a least-squares problem, and prunes back to K.
• Iterative Hard Thresholding (IHT): A gradient-descent approach with a hard-thresholding step to enforce sparsity.

A model-driven deep learning approach that maps the iterative steps of a sparse recovery algorithm (like ISTA) into the layers of a neural network. Each layer corresponds to one iteration, with learnable parameters replacing hand-tuned thresholds.

• LISTA (Learned ISTA): Unfolds the Iterative Shrinkage-Thresholding Algorithm, dramatically reducing the number of iterations needed.
• Combines the interpretability of optimization with the speed of neural networks.
• Directly applicable to CSI compression, where the unfolding network learns to reconstruct the channel from compressed measurements with fewer iterations than classical solvers.