In the field of Compressive Sensing (CS), the goal is to recover a sparse signal from a small number of linear measurements. To guarantee that this recovery is even possible, the sensing matrix must satisfy a condition known as the Restricted Isometry Property (RIP).
Intuitively, RIP ensures that the sensing matrix acts like a near-isometry for all sparse vectors. If a matrix has the RIP, it means it doesn't "squash" two different sparse signals into the same measurement, preserving the distance between them so they can be uniquely identified. However, a recurring theme across recent research is a fundamental tension: while RIP is the gold standard for theoretical proofs, it is practically impossible to verify for any specific matrix.
The NP-Hardness Wall
The primary challenge identified by researchers like Frank de Hoog and Mingrui Yang in New Coherence and RIP Analysis for Weak Orthogonal Matching Pursuit is that calculating the Restricted Isometry Constant for an arbitrary matrix is an NP-hard problem.
To check if a matrix satisfies RIP, one would theoretically need to examine every possible subset of columns (the "support") to ensure they are nearly orthogonal. As the signal dimension grows, the number of combinations explodes combinatorially. This creates a significant gap between theory and practice:
- Theory: "If the matrix satisfies RIP, the algorithm will work."
- Practice: "We have a matrix, but we cannot check if it satisfies RIP."
This computational barrier, also highlighted in the lecture notes by Eric W. Tramel et al. in Statistical Estimation: From Denoising to Sparse Regression and Hidden Cliques, prevents engineers from verifying the reliability of real-world measurement systems in real-time.
Bridging the Gap with Greedy Algorithms
Because we cannot easily verify RIP, research has shifted toward finding the "tightest" possible theoretical bounds for specific recovery algorithms. If we can lower the requirement for how "good" a matrix needs to be, we increase the likelihood that a random or real-world matrix will suffice.
For example, Junhan Kim and Jian Wang 0016 focused on the Orthogonal Least Squares (OLS) algorithm. In On the Fundamental Recovery Limit of Orthogonal Least Squares, they refined the mathematical bounds of RIP to provide an optimal condition for exact recovery. By sharpening these bounds, they reduce the "safety margin" required by the theory, bringing it closer to the empirical performance seen in practice.
Similarly, Jie Ding and colleagues analyzed Orthogonal Matching Pursuit (OMP) for multiple measurement vectors. Their work in Performance of Orthogonal Matching Pursuit for Multiple Measurement Vectors demonstrates that even when the sensing matrix is corrupted by noise, OMP can still identify the signal's support under specific RIP-based conditions.
Robustness Against General Perturbations
If we cannot verify RIP, we must at least ensure that our algorithms are robust when the RIP conditions are only approximately met or when the data is noisy. Laming Chen and Yuantao Gu have explored this through the lens of "general perturbations."
In Oracle-Order Recovery Performance of Greedy Pursuits With Replacement Against General Perturbations, they show that greedy algorithms like CoSaMP and Subspace Pursuit achieve "oracle-order" performance. This means that even if the matrix isn't perfect and the measurements are noisy, the recovery error is comparable to a scenario where we already knew which parts of the signal were important. This robustness provides a practical safety net: even if we can't prove a matrix is perfect (due to NP-hardness), we know our algorithms won't catastrophically fail under slight deviations.
From Bounds to Exact Analysis
While much of the field relies on these difficult-to-calculate RIP bounds, some researchers are seeking alternative paths. Giulio Coluccia, Aline Roumy, and Enrico Magli moved away from "loose" RIP bounds entirely in Exact performance analysis of the oracle receiver for compressed sensing reconstruction.
By using Wishart random matrix theory, they derived exact closed-form expressions for reconstruction error. This suggests a potential future for the field: moving away from the NP-hard task of verifying properties for individual matrices and instead focusing on the statistical properties of classes of matrices, where exact performance can be mathematically guaranteed.