Robustness of Sparse Recovery via -minimization: A Topological Viewpoint
arXiv:1301.0093 · doi:10.1109/TIT.2015.2438302
Abstract
A recent trend in compressed sensing is to consider non-convex optimization techniques for sparse recovery. The important case of -minimization has become of particular interest, for which the exact reconstruction condition (ERC) in the noiseless setting can be precisely characterized by the null space property (NSP). However, little work has been done concerning its robust reconstruction condition (RRC) in the noisy setting. We look at the null space of the measurement matrix as a point on the Grassmann manifold, and then study the relation between the ERC and RRC sets, denoted as and , respectively. It is shown that is the interior of , from which a previous result of the equivalence of ERC and RRC for -minimization follows easily as a special case. Moreover, when is non-decreasing, it is shown that $\overlineΩ_J\setminus\interior(Ω_J)$ is a set of measure zero and of the first category. As a consequence, the probabilities of ERC and RRC are the same if the measurement matrix is randomly generated according to a continuous distribution. Quantitatively, if the null space lies in the "-interior" of , then RRC will be satisfied with the robustness constant ; and conversely if RRC holds with , then must lie in -interior of . We also present several rules for comparing the performances of different cost functions. Finally, these results are capitalized to derive achievable tradeoffs between the measurement rate and robustness with the aid of Gordon's escape through the mesh theorem or a connection between NSP and the restricted eigenvalue condition.
arXiv comment39 pages
References in corpus (9)
- Nearly unbiased variable selection under minimax concave penalty
- Simultaneous analysis of Lasso and Dantzig selector
- A fast approach for overcomplete sparse decomposition based on smoothed L0 norm
- Observed Universality of Phase Transitions in High-Dimensional Geometry, with Implications for Modern Data Analysis and Signal Processing
- Universality in polytope phase transitions and message passing algorithms
- A stochastic gradient approach on compressive sensing signal reconstruction based on adaptive filtering framework
- On the stable recovery of the sparsest overcomplete representations in presence of noise
- Proof of Convergence and Performance Analysis for Sparse Recovery via Zero-point Attracting Projection
- Under-determined linear systems and -optimization thresholds