Source-linked AI summary
Signal Recovery from Incomplete and Inaccurate Measurements via Regularized Orthogonal Matching Pursuit
Deanna Needell, Roman Vershynin
TL;DR
Sparse recovery requires reconstructing signals from incomplete and potentially inaccurate measurements, while the stability of greedy methods was not well understood. The paper introduces ROMP as a greedy recovery algorithm and proves stability comparable to convex programming. Its guarantees extend to approximately sparse signals, with numerical examples supporting the theoretical results, while a logarithmic factor remains conjectured to be removable.
Problem
The stability of greedy sparse-recovery algorithms under inaccurate measurements was not well understood, despite the practical need to recover signals from noisy observations.
Method
ROMP greedily processes the measurement vector, producing an index set and reconstructed vector through at most n iterations involving least-squares problems.
Results
ROMP is proved as stable as convex programming, and its stability result extends to approximately sparse signals.
Takeaways & Limitations
ROMP combines the speed and implementation advantages of greedy methods with recovery guarantees comparable to convex programming.
Takeaways & Limitations
The authors conjecture that the logarithmic factor in ROMP’s stability bound is unnecessary, whereas the corresponding convex-programming bound does not require it.
Abstract
from arXiv · showhide
We demonstrate a simple greedy algorithm that can reliably recover a d-dimensional vector v from incomplete and inaccurate measurements x. Here our measurement matrix is an N by d matrix with N much smaller than d. Our algorithm, Regularized Orthogonal Matching Pursuit (ROMP), seeks to close the gap between two major approaches to sparse recovery. It combines the speed and ease of implementation of the greedy methods with the strong guarantees of the convex programming methods. For any measurement matrix that satisfies a Uniform Uncertainty Principle, ROMP recovers a signal with O(n) nonzeros from its inaccurate measurements x in at most n iterations, where each iteration amounts to solving a Least Squares Problem. The noise level of the recovery is proportional to the norm of the error, up to a log factor. In particular, if the error vanishes the reconstruction is exact. This stability result extends naturally to the very accurate recovery of approximately sparse signals.
1. Introduction
Compressed sensing enables recovery of sparse signals from incomplete observations, but stable recovery from inaccurate measurements remained less understood for greedy methods. ROMP addresses this gap by combining greedy computation with recovery guarantees comparable to convex programming.
- Compressed sensing recovers sparse and compressible signals from incomplete observations.
- N ≪ d nonadaptive linear measurements x = Φv are used to recover an n-sparse d-dimensional signal efficiently.
- The Restricted Isometry Condition supports exact sparse recovery through convex programming and is satisfied by several natural random matrix ensembles.
- Greedy algorithms are fast and easy to implement; OMP finds an n-sparse support in n iterations, each requiring one least-squares problem.
- ROMP exactly recovers an n-sparse signal under a Restricted Isometry Condition with parameters (2n, 0.03/√log n).
- Before this work, the stability of greedy sparse-recovery algorithms lacked theoretical results, motivating the paper’s analysis of ROMP under inaccurate measurements.
- The paper proves that ROMP is as stable as the convex program, narrowing the gap between greedy and convex approaches.
Regularized Orthogonal Matching Pursuit (ROMP)
ROMP is a greedy recovery algorithm that iteratively selects and regularizes coordinates, then solves a least-squares problem to update the reconstruction. Under a Restricted Isometry Condition, it is stable to measurement errors, exact without noise, and extends to approximately sparse signals.
- Algorithm: ROMP initializes an empty support and residual, then repeats identification, regularization, and least-squares updating for up to n iterations or until the support reaches size 2n.It selects the n largest coordinates of Φ*r, retains a comparable-coordinate subset with maximal energy, and updates the residual after least-squares reconstruction.
- Stability guarantees: Under the Restricted Isometry Condition with parameters (4n, ε), where ε = 0.01/√log n, ROMP provides stability for n-sparse signals corrupted by measurement error.The theorem considers measurements x = Φv + e for an n-sparse vector v.
- Stability guarantees: In the noiseless case, ROMP reconstructs the signal exactly: ˆv = v.This is the e = 0 case of the stability theorem.
- Approximately sparse signals: ROMP’s stability result extends to approximately sparse signals by approximating an arbitrary vector through its largest 2n coordinates.The term v2n can be replaced by v(1+δ)n for any δ > 0, changing only constant terms.
- Comparison and scope: Unlike the convex programming method, ROMP requires no prior knowledge of the error vector’s magnitude, although the paper conjectures its logarithmic stability factor may be unnecessary.The convex approach is described as noise-aware, whereas ROMP is not; the conjecture concerns the factor in ROMP’s results.
- Approximately sparse signals: ROMP can approximately compute a 2n-sparse vector close to the best 2n-term approximation of an arbitrary signal.Retaining the 2n largest coordinates of the reconstructed vector yields this approximation guarantee.
- Approximately sparse signals: For compressible vectors whose coefficients obey a power law, the resulting reconstruction bound is optimal up to a logarithmic factor.The paper states that no algorithm can perform fundamentally better within that logarithmic factor.
2. Proof of Theorem 1.2
The proof establishes ROMP’s recovery guarantee through an iteration invariant: each iteration either identifies substantial support or already satisfies the error bound. Restricted Isometry consequences control residual and observation approximations, enabling the theorem’s case analysis.
- ROMP’s iteration invariant states that at least 50% of newly selected coordinates belong to the signal support, or the error bound already holds.
- The proof assumes a Restricted Isometry Condition with parameters (4n, ε) for ε = 0.01/√log n.
- If the error-bound case occurs, it persists through later iterations and implies Theorem 1.2; otherwise, support identification continues until the signal support is contained in the selected set.
- Restricted Isometry consequences show that relevant measurement subspaces are almost orthogonal, supporting approximation of the residual and observation vectors.
- The residual approximation satisfies ∥x0 − r∥2 ≤ 2.3ε∥v0∥2 + ∥e∥2.
3. Approximately sparse vectors and best n-term approximations
The paper extends ROMP’s stability guarantee from exactly sparse signals to approximately sparse vectors by separating the largest 2n coordinates from the tail. Truncating the reconstruction yields a close 2n-sparse approximation and supports a whole-signal bound.
- The signal is decomposed as x = Φv2n + Φ(v − v2n) + e to apply the sparse-signal stability theorem to its largest 2n coordinates.
- ROMP’s stability result is combined with a norm comparison relating a vector’s tail to its 1-norm.
- Truncating the reconstructed vector produces a 2n-sparse vector very close to the original signal.
- The best m-sparse approximation zm consists of the m largest coordinates of z in absolute value.
- The resulting approximation can be combined with the stability corollary to estimate an error bound for the whole signal.
4. Numerical Examples
Experiments test ROMP under perturbed measurements and Gaussian signal perturbations using repeated random trials. The figures agree with the theoretical stability results and suggest that some logarithmic or square-root factors may be unnecessary.
- The experiments evaluate recovery error for both perturbed measurements and perturbed signals.
- Each experimental setting uses 500 trials with random Gaussian measurement matrices and randomly generated n-sparse signals.
- For d = 256, Figure 1 varies the number of measurements N and sparsity n while plotting average normalized recovery error under perturbed measurements.
- Figure 1 confirms Theorem 1.2 and suggests its bound may be improved by removing a square-root factor.
- Figure 2 confirms Corollary 1.3 for Gaussian signal perturbations and suggests that its logarithmic factor is unnecessary.