Exact Recovery Conditions for Sparse Representations With Partial Support Information

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 ℓ_p-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 any k-sparse vector in the noninformed setup. It reads μ <; 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 ℓ_p-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 ℓ₁ problem, and the truncated NSP for p <; 1 .