Source-linked AI summary
A remark on the Restricted Isometry Property in Orthogonal Matching Pursuit
Qun Mo, Yi Shen
TL;DR
The paper studies when OMP can recover every K-sparse signal in K iterations under restricted-isometry conditions. It proves a sufficient recovery condition and constructs a matrix at a contrasting constant for which OMP fails, confirming the stated conjecture.
Problem
The paper addresses whether restricted-isometry conditions can characterize exact recovery and failure of OMP for K-sparse signals in K iterations.
Method
The paper analyzes OMP using restricted-isometry arguments and constructs a measurement matrix and K-sparse signal for the failure case.
Results
OMP recovers every K-sparse signal in K iterations under the paper’s sufficient condition, while the constructed matrix causes failure for at least one K-sparse signal in K iterations.
Takeaways & Limitations
The results positively verify the Dai–Milenkovic conjecture about an OMP recovery boundary.
Abstract
from arXiv · showhide
This paper demonstrates that if the restricted isometry constant $δ_{K+1}$ of the measurement matrix $A$ satisfies $$ δ_{K+1} < \frac{1}{\sqrt{K}+1}, $$ then a greedy algorithm called Orthogonal Matching Pursuit (OMP) can recover every $K$--sparse signal $\mathbf{x}$ in $K$ iterations from $A\x$. By contrast, a matrix is also constructed with the restricted isometry constant $$ δ_{K+1} = \frac{1}{\sqrt{K}} $$ such that OMP can not recover some $K$-sparse signal $\mathbf{x}$ in $K$ iterations. This result positively verifies the conjecture given by Dai and Milenkovic in 2009.
I. INTRODUCTION
The introduction frames sparse recovery through compressed sensing and motivates OMP guarantees based on the restricted isometry property. It presents the paper’s two main results: a sufficient condition for exact recovery and a matching failure construction.
- Motivation: Compressed sensing seeks to reconstruct sparse signals from measurements that may otherwise be insufficient for unique recovery.The paper assumes sparsity and additional structure in the signal and measurement matrix.
- Restricted isometry property: The restricted isometry property provides conditions intended to ensure uniqueness of sparse solutions.The introduction connects this property to both l0 and l1 recovery guarantees.
- Orthogonal Matching Pursuit: OMP is introduced as a greedy method for seeking an l0-minimization solution by iteratively selecting columns and updating residuals.Each iteration adds a selected index, solves a least-squares problem on the selected columns, and recomputes the residual.
- Related work: Earlier work progressively improved sufficient restricted-isometry conditions, while Dai and Milenkovic conjectured a boundary at which OMP can fail.The conjecture had previously been confirmed numerically for K = 2.
- Main results: The paper establishes both a sufficient condition under which OMP exactly recovers every K-sparse signal in K iterations and a construction where recovery fails.These results address the conjectured boundary described in the introduction.
II. PRELIMINARIES
The preliminaries fix notation for a K-sparse signal and define an auxiliary maximum correlation quantity used in the analysis. A lemma then establishes that the first K candidate quantities dominate all later ones.
- Notation: The analysis assumes x is a K-sparse signal in R^n and represents its nonzero entries explicitly.The number of nonzero entries is k, with k ≤ K.
- Notation: The nonzero coordinates satisfy x_i ≠ 0 for i = 1, 2, ..., k, with k ≤ K.This identifies the support size used in the subsequent definitions.
- Auxiliary quantities: The quantity S0 is defined as the maximum of |S_i| over i in {1, ..., K}.This auxiliary quantity is used to compare candidate indices in the OMP analysis.
- Auxiliary quantities: Lemma 2.1 concludes that S0 > |S_i| for every i > K under its restricted-isometry assumption.The result separates the largest first-K quantity from all later quantities.
III. MAIN RESULTS
The main results establish a sufficient RIP condition guaranteeing OMP recovery of every K-sparse signal in K iterations, and construct a boundary example where OMP fails. The proofs analyze first-iteration selection and extend it across iterations, while the counterexample shows failure can begin immediately.
- OMP’s first iteration succeeds when the sufficient correlation inequality S0 > |Si| holds for all i > K.The proof then uses orthogonal projection and induction to show that each iteration selects a different support index.
- For every K ≥ 2, there exist a K-sparse signal and a matrix with the stated restricted isometry constant for which OMP fails in K iterations.The construction provides the converse example to the recovery guarantee.
- Equal correlations Si = ⟨Aei, Ax⟩ = 1 for all i ∈ {1, …, K + 1} imply that OMP fails in its first iteration.Because OMP chooses one index per iteration, this yields failure in K iterations for the constructed matrix and signal.
- A very small δK+1 is difficult to achieve, and the counterexample shows that this requirement is necessary for the stated OMP guarantee.Selecting multiple indices per iteration can recover the counterexample signal in K iterations.