Exact Recovery Conditions for Sparse Representations With Partial Support Information
From MaRDI portal
Abstract: We address the exact recovery of a k-sparse vector in the noiseless setting when some partial information on the support is available. This partial information takes the form of either a subset of the true support or an approximate subset including wrong atoms as well. We derive a new sufficient and worst-case necessary (in some sense) condition for the success of some procedures based on lp-relaxation, Orthogonal Matching Pursuit (OMP) and Orthogonal Least Squares (OLS). Our result is based on the coherence "mu" of the dictionary and relaxes the well-known condition mu<1/(2k-1) ensuring the recovery of any k-sparse vector in the non-informed setup. It reads mu<1/(2k-g+b-1) when the informed support is composed of g good atoms and b wrong atoms. We emphasize that our condition is complementary to some restricted-isometry based conditions by showing that none of them implies the other. Because this mutual coherence condition is common to all procedures, we carry out a finer analysis based on the Null Space Property (NSP) and the Exact Recovery Condition (ERC). Connections are established regarding the characterization of lp-relaxation procedures and OMP in the informed setup. First, we emphasize that the truncated NSP enjoys an ordering property when p is decreased. Second, the partial ERC for OMP (ERC-OMP) implies in turn the truncated NSP for the informed l1 problem, and the truncated NSP for p<1.
Cited in
(22)- Compressed sensing with structured sparsity and structured acquisition
- A simple recovery framework for signals with time-varying sparse support
- A new sufficient condition for sparse recovery with multiple orthogonal least squares
- Partial \(S\)-goodness for partially sparse signal recovery
- Computing and analyzing recoverable supports for sparse reconstruction
- Perfect Recovery Conditions for Non-negative Sparse Modeling
- A Sharp Condition for Exact Support Recovery With Orthogonal Matching Pursuit
- Information-Theoretic Limits on Sparsity Recovery in the High-Dimensional and Noisy Setting
- scientific article; zbMATH DE number 7572477 (Why is no real title available?)
- Support Recovery in the Phase Retrieval Model: Information-Theoretic Fundamental Limit
- Perturbation Analysis of Orthogonal Least Squares
- Quasi-linear compressed sensing
- A survey on compressive sensing: classical results and recent advancements
- Weighted _p-minimization for sparse signal recovery under arbitrary support prior
- Required Number of Iterations for Sparse Signal Recovery via Orthogonal Least Squares
- Theoretical analysis of GOMP based on RIP and ROC
- Optimality analysis on partial l₁-minimization recovery
- Binary sparse signal recovery with binary least squares
- A new analysis for support recovery of OLS and OMP with partial support information
- Theoretical analysis for \(\ell_{1}\)-\(\ell_{2}\) minimization with partial support information.
- A theoretical perspective of solving phaseless compressive sensing via its nonconvex relaxation
- Exact support recovery for sparse spikes deconvolution
This page was built for publication: Exact Recovery Conditions for Sparse Representations With Partial Support Information
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5346268)
