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 $\ell_p$-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 $\ell_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 $\ell_1$ problem, and the truncated NSP for $p < 1$.
Introduction
In the field of compressed sensing and sparse representation, the fundamental challenge is to reconstruct a signal that has only a few non-zero components (a $k$-sparse signal) from a limited set of linear measurements. While finding the absolute sparsest solution is an NP-hard problem, researchers typically rely on "greedy" algorithms or convex optimization as computationally feasible shortcuts.
Standard mathematical guarantees for these algorithms are often pessimistic because they assume zero prior knowledge about the signal's support. However, in many practical applications—such as video compression, where signals change incrementally between frames, or medical imaging—we often possess a "hint" or a guess about which components of the signal are active. This paper bridges the gap in understanding how these hints, even when imperfect, can be leveraged to guarantee perfect signal reconstruction.
The Informed Recovery Framework
The authors analyze three primary classes of algorithms within a "partially-informed" setting:
- $\ell_p$-relaxation: A method that replaces the discrete sparsity count with a continuous mathematical function to facilitate optimization.
- Orthogonal Matching Pursuit (OMP): A greedy algorithm that iteratively selects the best-fitting components.
- Orthogonal Least Squares (OLS): A more sophisticated greedy approach that re-evaluates the fit of all selected components at every step.
The "hint" is defined as an informed support set containing $g$ "good" atoms (correctly identified components of the true support) and $b$ "bad" atoms (incorrectly identified components).
Key Theoretical Contributions
1. The Generalized Coherence Bound
The most significant result is the derivation of a new recovery condition based on the Mutual Coherence ($\mu$), which measures the maximum similarity between any two columns (atoms) in the measurement dictionary.
In a standard, uninformed search, the condition for guaranteed recovery is $\mu < 1/(2k - 1)$. This paper relaxes that bound to: $$\mu < \frac{1}{2k - g + b - 1}$$
This formula quantifies the "hint bonus." If the provided information is more than 50% accurate ($g > b$), the denominator decreases, making the condition significantly easier to satisfy. The authors further prove that this bound is "tight" by constructing specific worst-case scenarios where recovery fails immediately upon violating this condition.
2. The Nesting Property of $\ell_p$ Minimization
The research explores the Null Space Property (NSP), a condition on the measurement matrix that ensures sparse vectors are not lost in the matrix's null space. The authors demonstrate that the "truncated" NSP (adapted for informed recovery) enjoys an ordering property: if a signal can be recovered using standard $\ell_1$ minimization (Basis Pursuit), it is guaranteed to be recoverable using $\ell_p$ minimization for any $p < 1$. This suggests that non-convex methods are theoretically more robust for recovery, even if they present greater optimization challenges.
3. Algorithm Hierarchy
The paper establishes a clear hierarchy between greedy methods and relaxation methods in the informed setup. Specifically, the Exact Recovery Condition (ERC) for OMP is shown to be stricter than the conditions for $\ell_1$ success. If OMP is guaranteed to succeed given a specific hint, then $\ell_1$ minimization is also guaranteed to succeed, but the inverse is not necessarily true.
4. Complementarity with RIP
Finally, the authors compare their coherence-based bounds with those derived from the Restricted Isometry Property (RIP). They demonstrate that these two types of guarantees are complementary; neither strictly implies the other. Depending on the structure of the measurement matrix, one bound may provide a much stronger guarantee than the other.
Conclusion and Future Directions
This work provides a rigorous theoretical foundation for using prior information in sparse recovery. By showing that even imperfect hints can significantly lower the requirements for exact reconstruction, it validates the use of temporal or structural priors in practical sensing systems.
However, some limitations remain. The current analysis assumes a noiseless setting, and extending these conditions to account for measurement noise is a critical next step. Additionally, while $\ell_p$ relaxation ($p < 1$) offers superior theoretical recovery bounds, finding the global minimum of these non-convex problems remains computationally difficult in practice. Future research may focus on deriving Restricted Isometry Constants (RIC) specifically for OLS, which remains an open challenge in the literature.
Summary updated