Source-linked AI summary
Uniform Uncertainty Principle and signal recovery via Regularized Orthogonal Matching Pursuit
Deanna Needell, Roman Vershynin
TL;DR
Sparse recovery requires exact reconstruction of sparse signals from incomplete linear measurements, while existing L1-minimization and OMP methods offer different advantages and limitations. The paper introduces ROMP, a regularized OMP method, and shows that it achieves uniform exact recovery under RIC with at most n iterations.
Problem
Sparse recovery needs efficient exact reconstruction from incomplete linear measurements while bridging the differing guarantees and computational properties of L1-minimization and iterative matching-pursuit methods.
Method
The paper introduces Regularized Orthogonal Matching Pursuit, an iterative method that combines OMP’s support-selection framework with regularization.
Results
ROMP provides uniform exact sparse recovery for measurement matrices satisfying the Restricted Isometry Condition, recovering within at most n iterations and producing |I| ≤2n.
Takeaways & Limitations
ROMP extends the OMP approach to uniform recovery guarantees, including for Gaussian, Bernoulli, and partial Fourier measurement matrices with nearly linear measurement counts.
Takeaways & Limitations
OMP’s guarantees are non-uniform, while L1-minimization relies on linear-programming solvers whose running time depends on difficult-to-estimate condition numbers.
Abstract
from arXiv · showhide
This paper seeks to bridge the two major algorithmic approaches to sparse signal recovery from an incomplete set of linear measurements -- L_1-minimization methods and iterative methods (Matching Pursuits). We find a simple regularized version of the Orthogonal Matching Pursuit (ROMP) which has advantages of both approaches: the speed and transparency of OMP and the strong uniform guarantees of the L_1-minimization. Our algorithm ROMP reconstructs a sparse signal in a number of iterations linear in the sparsity (in practice even logarithmic), and the reconstruction is exact provided the linear measurements satisfy the Uniform Uncertainty Principle.
1. Introduction
Sparse recovery seeks efficient exact reconstruction of n-sparse signals from N ≪ d linear measurements. The paper proposes ROMP to combine OMP’s iterative efficiency with uniform recovery guarantees under the Restricted Isometry Condition.
- Problem: Sparse recovery reconstructs an unknown signal with at most n nonzero components from N ≪ d nonadaptive linear measurements.The measurements are Φv, where Φ is an N × d matrix.
- Compressed Sensing: N = n logO(1)(d) measurements can support exact sparse recovery for suitable measurement matrices.This measurement count is almost linear in the sparsity n.
- ROMP: ROMP is a regularized OMP variant designed to retain iterative efficiency while providing uniform guarantees for all sparse signals under RIC.The paper states that ROMP performs correctly for every matrix satisfying RIC and every sparse signal.
- Existing approaches: L1-minimization offers convex optimization and uniform recovery under RIC, while OMP identifies the support iteratively in n steps.Under RIC with parameters (3n, 0.2), every n-sparse vector is exactly recovered by L1; OMP’s standard guarantees are non-uniform.
- Existing approaches: OMP is fast and transparent but cannot be an isometry in the interesting undersampled regime, and its recovery guarantees are weaker.For Gaussian matrices, OMP recovers each fixed sparse signal with high probability when N ∼ n log d.
- ROMP: Under RIC with parameters (2n, ε), where ε = 0.03/√log n, ROMP recovers the support within at most n iterations using an index set of size at most 2n.The theorem guarantees supp(v) ⊂ I and |I| ≤ 2n.
- Scope: RIC-compatible measurement matrices include random Gaussian, Bernoulli, and partial Fourier matrices with measurement counts almost linear in n.For partial Fourier measurements, ROMP supplies sparse recovery with uniform guarantees.
2. Measurement matrices satisfying the Restricted Isometry Condition
This section identifies random matrix classes known to satisfy the Restricted Isometry Condition and states measurement regimes that guarantee exact sparse recovery with ROMP.
- Random subgaussian matrices and random partial bounded orthogonal matrices are the known classes satisfying the Restricted Isometry Condition in the stated measurement regime.Gaussian and Bernoulli matrices are examples of subgaussian matrices; partial Fourier matrices are examples of partial bounded orthogonal matrices.
- A subgaussian matrix has independent identically distributed subgaussian entries with variance 1, including Gaussian, Bernoulli, and bounded variables.
- A partial bounded orthogonal matrix samples N uniformly chosen rows from an orthogonal d × d matrix with bounded entries; partial Fourier measurements observe random signal frequencies.
- For subgaussian and partial bounded orthogonal matrices, Theorem 2.1 gives high-probability Restricted Isometry guarantees under stated conditions on N, n, ε, and δ.The theorem considers an N × d matrix, n ≥ 1, ε ∈ (0, 1/2), and δ ∈ (0, 1).
- N ∼n log5 d measurements guarantee exact sparse recovery using ROMP for the stated partial bounded orthogonal matrix setting.
3. Proof of Theorem 1.3
Under the Restricted Isometry Condition, ROMP’s regularized selections identify the support progressively: each iteration selects at least half correct support coordinates, yielding linear iteration complexity.
- Iteration invariant: 50% of each newly selected set J0 belongs to the signal support under the iteration invariant.The invariant also ensures J0 is nonempty and disjoint from previously selected indices.
- Iteration invariant: ROMP finds at least one new support coordinate in every iteration, while false selections remain fewer than correct selections.This establishes the theorem’s linear bound on the number of iterations.
- Use of the RIC: RIC provides local approximation and near-orthogonality properties for submatrices involving at most 2n coordinates.These properties support the analysis of residuals and observation vectors during each iteration.
- Residual and observation analysis: The residual is represented through projections onto complementary subspaces, allowing the remaining signal component to approximate the current observation.Approximation lemmas transfer information from the remaining support component to the residual observation.
- Regularization: ROMP regularizes the largest observed coordinates by selecting a comparable-magnitude subset with sufficient energy.The proof partitions coordinates into O(log n) magnitude ranges and uses one range with large energy.
4. Implementation and empirical performance of ROMP
ROMP combines efficient identification and regularization with least-squares updates, achieving the same O(dNn) running-time bound as OMP and strong empirical recovery performance.
- Running time: O(n) time suffices for ROMP’s regularization step by examining O(log n) candidate magnitude intervals.The identification step can be implemented by sorting the observation coordinates in O(d log d) time.
- Running time: O(dNn) is ROMP’s total running-time bound for unstructured matrices when N ≥ log d, matching OMP.ROMP terminates in at most 2n iterations; identification and least-squares costs determine the bound.
- Non-sparse signals: ROMP can be adapted to compressible signals by stopping after n repetitions or when the residual reaches zero.The paper separately notes stability and approximate recovery for noisy non-sparse signals as forthcoming work.
- Recovery experiments: 500-trial experiments found ROMP’s exact-recovery performance very similar to OMP for sparse flat and sparse compressible signals.The flat-signal experiments used d = 256 and varied the number of measurements and sparsity.
- Iteration experiments: 2 iterations sufficed for flat signals with sparsity n as high as 40, while p = 0.5 compressible signals required only 6 iterations at n as high as 20.Compressible signals generally required more iterations than flat signals, with smaller p associated with more rapid coefficient decay.