This paper provides novel results for the recovery of signals from undersampled measurements based on analysis @math -minimization, when the analysis operator is given by a frame. We both provide so-called uniform and nonuniform recovery guarantees for cosparse (analysis-sparse) signals using Gaussian random measurement matrices. The nonuniform result relies on a recovery condition via tangent cones and the uniform recovery guarantee is based on an analysis version of the null space property. Examining these conditions for Gaussian random matrices leads to precise bounds on the number of measurements required for successful recovery. In the special case of standard sparsity, our result improves a bound due to Rudelson and Vershynin concerning the exact reconstruction of sparse signals from Gaussian measurements with respect to the constant and extends it to stability under passing to approximately sparse signals and to robustness under noise on the measurements.
A recent contribution by Needell and Ward @cite_17 provides theoretical recovery guarantees for the special case of total variation minimization, which corresponds to analysis @math -minimization with a certain difference operator. Unfortunately, we cannot cover this situation with our main results because the difference operator is not a frame. Nevertheless, it would be interesting to pursue theoretical recovery guarantees for total variation minimization and Gaussian random matrices using the approach of this paper.
@cite_17
2054010646
This paper presents near-optimal guarantees for stable and robust image recovery from undersampled noisy measurements using total variation minimization. In particular, we show that from @math nonadaptive linear measurements, an image can be reconstructed to within the best @math -term approximation of its gradient up to a logarithmic factor, and this factor can be removed by taking slightly more measurements. Along the way, we prove a strengthened Sobolev inequality for functions lying in the null space of a suitably incoherent matrix.