Recovery guarantees for compressed sensing with unknown errors
For practitioners in compressed sensing and sparse regularization, this work removes the need for a priori noise estimates, making recovery guarantees more practical in real-world scenarios.
This work provides robust recovery guarantees for l1-minimization in compressed sensing when noise estimates are unavailable, focusing on quadratically constrained basis pursuit and random sampling in bounded orthonormal systems. The results enable applications in high-dimensional function approximation, infinite-dimensional sparse regularization, and non-Cartesian MRI.
From a numerical analysis perspective, assessing the robustness of l1-minimization is a fundamental issue in compressed sensing and sparse regularization. Yet, the recovery guarantees available in the literature usually depend on a priori estimates of the noise, which can be very hard to obtain in practice, especially when the noise term also includes unknown discrepancies between the finite model and data. In this work, we study the performance of l1-minimization when these estimates are not available, providing robust recovery guarantees for quadratically constrained basis pursuit and random sampling in bounded orthonormal systems. Several applications of this work are approximation of high-dimensional functions, infinite-dimensional sparse regularization for inverse problems, and fast algorithms for non-Cartesian Magnetic Resonance Imaging.