Answers are grounded in this paper and cite their sources.
We address the exact recovery of ak-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ₚ-relaxation, orthogonal matching pursuit (OMP), and orthogonal least squares (OLS). Our result is based on the coherenceμof the dictionary and relaxes the well-known conditionμ < 1/(2k-1)ensuring the recovery of anyk-sparse vector in the noninformed setup. It readsμ < 1/(2k-g+b-1)when the informed support is composed ofggood atoms andbwrong 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ₚ-relaxation procedures and OMP in the informed setup. First, we emphasize that the truncated NSP enjoys an ordering property whenpis decreased. Second, the partial ERC for OMP (ERC-OMP) implies in turn the truncated NSP for the informed₁problem, and the truncated NSP for$p< 1$.
No takes yet. Share an insight, caveat, or question.
Herzet et al. (2013) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: