Robustness of Sparse Recovery via <inline-formula> <tex-math notation="LaTeX">F </tex-math></inline-formula>-Minimization: A Topological Viewpoint

DOI10.1109/TIT.2015.2438302MaRDI QIDQ2977386zbMATH OpenOpenAlexFDO

Authors Jingbo Liu, Jian Jin, Y. T. Gu

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.0093

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: A recent trend in compressed sensing is to consider non-convex optimization techniques for sparse recovery. The important case of $F$-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 $Omeg{a}_J$ and $Omeg{a}_J^r$, respectively. It is shown that $Omeg{a}_J^r$ is the interior of $Omeg{a}_J$, from which a previous result of the equivalence of ERC and RRC for $el{l}_p$-minimization follows easily as a special case. Moreover, when $F$ is non-decreasing, it is shown that $overline{Omega}_{J}setminusinterior(Omeg{a}_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 $mathbfA$ is randomly generated according to a continuous distribution. Quantitatively, if the null space $$ lies in the "$d$-interior" of $Omeg{a}_J$, then RRC will be satisfied with the robustness constant $C=frac2+2ddsigm{a}_{min}(mathbf{A}^{op})$; and conversely if RRC holds with $C=frac2-2ddsigm{a}_{max}(mathbf{A}^{op})$, then $$ must lie in $d$-interior of $Omeg{a}_J$. 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.

Recommendations

• Weakly Convex Regularized Robust Sparse Recovery Methods With Theoretical Guarantees
• Robust sparse recovery via a novel convex model
• Robust Nonnegative Sparse Recovery and the Nullspace Property of 0/1 Measurements
• Stable recovery of sparse signals via \(\ell_p\)-minimization
• Weak stability of \(\ell_1\)-minimization methods in sparse data reconstruction
• On the Performance of Sparse Recovery Via \ell_p-Minimization (0 \leq p \leq 1)
• A note on guaranteed sparse recovery via \(\ell_1\)-minimization
• On Recovery of Sparse Signals Via $\ell _{1}$ Minimization
• Robust analysis ℓ₁-recovery from Gaussian measurements and total variation minimization
• Stable Recovery of Sparse Signals Via Regularized Minimization

Cited in

(5)

• Stability of 1-bit compressed sensing in sparse data reconstruction
• Robust analysis ℓ₁-recovery from Gaussian measurements and total variation minimization
• Sparse recovery based on the generalized error function
• Low-rank tensor recovery based on nonconvex logarithmic regularization factor
• Foundations of bare-simulation optimization of distances

This page was built for publication: Robustness of Sparse Recovery via <inline-formula> <tex-math notation="LaTeX">$F$ </tex-math></inline-formula>-Minimization: A Topological Viewpoint

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2977386)