Abstract: Compressive Sensing (CS) relies on sparse signal recovery, often using greedy algorithms like Orthogonal Matching Pursuit (OMP). A critical challenge in these methods is determining the optimal stopping point without prior knowledge of signal sparsity or noise levels. This paper introduces a theoretical framework for Cross Validation (CV) as a data-driven stopping criterion. We demonstrate that the OMP-CV algorithm, which splits measurements into reconstruction and validation sets, achieves performance comparable to "oracle" methods that possess perfect information.
Introduction
In Compressive Sensing, we aim to reconstruct a $k$-sparse signal from $M$ linear measurements. Greedy algorithms like OMP are popular due to their computational efficiency, but they suffer from a significant weakness: the stopping condition. To function correctly, these algorithms typically require the exact signal sparsity ($k$) or the noise floor ($\sigma$). In real-world applications, these parameters are rarely known, leading to either underfitting (stopping too early) or overfitting (stopping too late).
The OMP-CV Algorithm
The authors propose using Cross Validation (CV) as a data-driven, "blind" stopping criterion. The core methodology involves splitting the available measurements ($M$) into two distinct groups: a reconstruction set ($m$) used to build the signal model, and a CV set ($m_{cv}$) used to validate it.
Instead of stopping based on a fixed threshold, the OMP-CV algorithm runs for a predefined maximum number of iterations. At each step, it calculates a "CV residual"—the error between the actual CV measurements and the current model's predictions. The final output is the reconstructed signal from the iteration that yielded the minimum CV residual.
Theoretical Foundations
The paper's primary contribution is a rigorous mathematical framework proving that the CV residual is a statistically consistent estimator of the true recovery error. Utilizing the Restricted Isometry Property (RIP), the authors derive the probability distribution of CV residuals. A key finding is that the high correlation between successive iterations in greedy algorithms actually improves the success probability of CV in identifying the correct stopping point.
Performance Evaluation
The study validates these findings using synthetic datasets featuring Gaussian sensing matrices and additive white Gaussian noise.
As illustrated in the figure above, the CV residual serves as an excellent proxy for the unobservable recovery error. While the standard residual continues to drop as the model begins to fit the noise, the CV residual reaches a clear minimum that coincides with the lowest recovery error. Quantitative results show that OMP-CV stays within 0.4dB of "oracle" performance (where sparsity is known) in over 84% of trials.
Conclusion
OMP-CV effectively eliminates the need for prior knowledge of signal parameters in Compressive Sensing. While splitting measurements slightly reduces the data available for reconstruction, this "sacrifice" is more than compensated for by the massive improvement in stopping accuracy. The algorithm provides a robust, practical solution for deploying greedy recovery methods in real-world scenarios where noise and sparsity are unknown.
Summary updated