Source-linked AI summary
Sparse Recovery with Orthogonal Matching Pursuit under RIP
Tong Zhang
TL;DR
The paper addresses how to recover sparse signals efficiently when the relevant constrained optimization is generally NP-hard. It analyzes a generalized, fully corrective OMP under convex objectives and RIP-related conditions. The main result shows recovery of a k̄-sparse signal in 2-norm under RIP at sparsity level O(k̄), implying O(k̄ ln d) random projections for uniform compressed-sensing recovery.
Problem
Recovering sparse signals through the relevant constrained optimization is generally NP-hard, motivating computationally efficient approximate algorithms such as OMP.
Method
The paper refines the analysis of a fully corrective greedy algorithm for general convex objectives, viewed as a generalization of OMP, and connects its condition to RIP for quadratic loss.
Results
RIP at sparsity level O(k̄) allows OMP to recover a k̄-sparse signal in 2-norm, with uniform recovery requiring n = O(k̄ ln d) random projections.
Takeaways & Limitations
The analysis supports uniform recovery of all k̄-sparse signals under RIP and improves on mutual-incoherence-based requirements of Ω(k̄^2 ln d) random projections.
Takeaways & Limitations
The result requires running OMP for more than k̄ iterations and therefore does not recover the ideal signal’s true support set.
Abstract
from arXiv · showhide
This paper presents a new analysis for the orthogonal matching pursuit (OMP) algorithm. It is shown that if the restricted isometry property (RIP) is satisfied at sparsity level $O(\bar{k})$, then OMP can recover a $\bar{k}$-sparse signal in 2-norm. For compressed sensing applications, this result implies that in order to uniformly recover a $\bar{k}$-sparse signal in $\Real^d$, only $O(\bar{k} \ln d)$ random projections are needed. This analysis improves earlier results on OMP that depend on stronger conditions such as mutual incoherence that can only be satisfied with $Ω(\bar{k}^2 \ln d)$ random projections.
I. INTRODUCTION
The paper motivates sparse recovery from underdetermined noisy linear measurements, where computationally efficient methods are needed because the relevant constrained optimization is generally NP-hard. It focuses on OMP for approximately optimizing the objective and recovering the sparse signal.
- The observations follow a noisy linear model, y = Ax̄ + noise, with A an n × d matrix.
- Estimating x̄ is formulated by minimizing an objective function Q(x) subject to appropriate constraints.
- When d > n, unconstrained estimation is non-unique, so additional assumptions such as sparsity are needed to estimate the signal.The paper considers signals satisfying ||x̄||_0 ≪ n.
- Sparse recovery can be achieved under appropriate conditions by solving the constrained optimization problem, but that problem is generally NP-hard.
- The paper studies OMP as a computationally efficient algorithm for approximately optimizing Q(x) and recovering the sparse signal x̄.
II. MAIN RESULT
The paper extends OMP analysis to fully corrective greedy optimization for general convex objectives, using restricted strong convexity and restricted-gradient conditions. It shows approximate sparse recovery under conditions related to RIP, including a quadratic-loss case with k = 30k̄ and sparsity level s = 31k̄.
- Generalized OMP: OMP is generalized from quadratic loss to fully corrective greedy optimization for a general convex objective Q(x).The same framework is also described as a version of boosting and assumes a predetermined iteration count k0.
- Assumptions: Sparse recovery requires the target x̄ to be sparse and to approximately optimize Q(x), with restricted gradient optimality measuring the deviation from stationarity.The restricted gradient optimal constant examines the gradient over vectors supported on at most s coordinates.
- Main theorem: The main theorem establishes approximate 2-norm recovery when a condition involving restricted strong convexity constants is satisfied.The required condition is closely related to RIP for the quadratic objective.
- Main theorem: The condition can hold when (ρ+(1)/ρ−(s)) ln(ρ+(k̄)/ρ−(s)) grows sub-linearly with s, even if restricted curvature ratios exceed 1 but remain bounded.This broader condition is relevant when ρ+(s)/ρ−(s) may be large, as in some machine-learning estimation problems.
- Quadratic-loss corollary: 30k̄ iterations and s = 31k̄ suffice under ρ+(k̄) ≤ 2ρ−(31k̄); for quadratic objectives, δ31k̄ ≤ 1/3 implies this condition.The curvature condition is analogous to RIP, with ρ+(k̄) ≤ 4/3 and ρ−(31k̄) ≥ 2/3 under the stated RIP bound.
- Comparison: Under these constants, the OMP guarantee is comparable in strength to results for more sophisticated greedy algorithms, although their constants may be more favorable.The comparison given is δs ≤ 1/3 with s = 31k̄ for OMP versus δs ≤ 0.1 with s = 4k̄ for CoSaMP.
III. DISCUSSION
The paper establishes uniform sparse-signal recovery under an RIP condition, improving measurement requirements relative to earlier OMP analyses while trading exact support recovery for stronger 2-norm recovery.
- O(k̄ ln d) random projections suffice for uniform recovery of every k̄-sparse signal in R^d under the paper’s RIP-based result.
- The RIP condition applies uniformly to all k̄-sparse signals, unlike earlier results that applied only to any fixed sparse signal.
- The paper’s stronger 2-norm recovery result requires running OMP for more than k̄ iterations, so it does not recover the ideal signal’s true support set.
- Ω(k̄^2 ln d) random projections may be required under the stronger mutual incoherence condition used in earlier uniform OMP results.
- Earlier RIP analyses could achieve exact support recovery in k̄ iterations only under stronger assumptions, while another result used O(k̄^1.6 ln d) measurements with more than k̄ iterations.
- OMP and Lasso have different theoretical RIP dependencies: OMP is more favorable for the upper strong convexity constant but more demanding for the lower one.
APPENDIX
The appendix develops the proof through lemmas that quantify greedy progress, propagate approximation bounds across nested supports, and establish the main iteration-dependent guarantee by induction.
- The proof uses technical lemmas to analyze greedy progress and establish bounds for the generalized OMP algorithm.
- A nested sequence of support sets is used to propagate approximation guarantees across progressively larger supports.
- The analysis compares the objective at support-constrained minimizers with the target objective value through quantities q_j that decrease along the nested sequence.
- Lemma A.5 proves the main bound by induction on the number of target-support elements missing from the initial selected set.
- The proof orders missing coefficients by decreasing magnitude and chooses a logarithmically bounded number of nested levels for the induction.
- The resulting guarantee holds after a bounded number of additional OMP iterations combined with the induction estimate.