Cross Validation in Compressive Sensing and its Application of OMP-CV Algorithm

Jinye Zhang, Laming Chen, Petros T. Boufounos, Yuantao GuarXiv 2016 · arXiv

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.

Comparison of Residual, CV Residual, and Recovery Error across iterations. The CV residual (red dashed line) accurately tracks the true recovery error (black dash-dot line), reaching a minimum at the optimal iteration, while the standard residual (blue solid line) continues to decrease due to overfitting.

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

Abstract

Compressive sensing (CS) is a data acquisition technique that measures sparse or compressible signals at a sampling rate lower than their Nyquist rate. Results show that sparse signals can be reconstructed using greedy algorithms, often requiring prior knowledge such as the signal sparsity or the noise level. As a substitute to prior knowledge, cross validation (CV), a statistical method that examines whether a model overfits its data, has been proposed to determine the stopping condition of greedy algorithms. This paper first analyzes cross validation in a general compressive sensing framework and developed general cross validation techniques which could be used to understand CV-based sparse recovery algorithms. Furthermore, we provide theoretical analysis for OMP-CV, a cross validation modification of orthogonal matching pursuit, which has very good sparse recovery performance. Finally, numerical experiments are given to validate our theoretical results and investigate the behaviors of OMP-CV.
BibTeX
@misc{zhang2016cross,
  author = {Jinye Zhang and Laming Chen and Petros T. Boufounos and Yuantao Gu},
  title = {{Cross Validation in Compressive Sensing and its Application of OMP-CV Algorithm}},
  year = {2016},
  eprint = {1602.06373},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1602.06373},
}
Figure