Joint k-Step Analysis of Orthogonal Matching Pursuit and Orthogonal Least Squares

Charles Soussen, Rémi Gribonval, Jérôme Idier, Cédric HerzetIEEE Trans. Information Theory 2013 · OpenReview

TL;DR

This paper provides the first theoretical analysis of Orthogonal Least Squares (OLS) for exact support recovery in sparse signal recovery, extending existing work on Orthogonal Matching Pursuit (OMP). The authors show that OLS, like OMP, is guaranteed to recover the correct sparse support under the Exact Recovery Condition (ERC), and they introduce new conditions that characterize their behavior in more general scenarios, revealing distinct strengths and weaknesses for each algorithm, particularly with correlated dictionaries.

What Problem Does This Paper Address?

Sparse signal recovery, a fundamental problem in fields like signal processing and machine learning, aims to find a sparse representation of a signal from a set of measurements. Greedy algorithms like Orthogonal Matching Pursuit (OMP) and Orthogonal Least Squares (OLS) are popular methods for this task. While OMP has been extensively studied, with theoretical guarantees like Tropp's Exact Recovery Condition (ERC) providing insights into its performance, OLS, despite its practical use, has lacked a similar rigorous theoretical analysis for exact support recovery. This paper bridges this gap by providing the first theoretical framework for analyzing OLS's exact recovery capabilities, comparing it directly with OMP and uncovering nuanced differences in their behavior, especially when the ideal ERC is not met or when dictionary atoms are correlated.

Methods

The core of the paper lies in extending the theoretical framework of sparse recovery analysis to OLS. The authors build upon Tropp's Exact Recovery Condition (ERC) for OMP and generalize it to OLS. They introduce new conditions, termed ERC-OMP and ERC-OLS, which are specific to each algorithm and capture their recovery guarantees at different stages of the iterative process. The analysis involves:

  • Generalizing ERC: Extending the ERC to characterize the exact recovery conditions for both OMP and OLS, not just at the first iteration but at any iteration $q$.
  • Recursive Analysis: Developing recursive expressions for the ERC-OMP and ERC-OLS conditions to understand how they evolve as more atoms are selected.
  • Reachability Analysis: Investigating whether specific sparse supports can be recovered by OLS, a crucial aspect for understanding its exploration capabilities.
  • Bad Recovery Conditions: Defining and analyzing conditions under which OMP might fail to recover the correct support, even when OLS succeeds.
  • Numerical Simulations: Employing Monte Carlo simulations with various types of dictionaries (Gaussian, hybrid, and deconvolution) to empirically evaluate the theoretical conditions and compare the performance of OMP and OLS.

Datasets

The paper does not introduce new datasets. Instead, it uses synthetically generated dictionaries for evaluation:

  • Randomly Gaussian Dictionaries: Entries drawn from a standard Gaussian distribution, with atoms normalized to unit norm.
  • Hybrid Dictionaries: Atoms formed by a mixture of a deterministic component (a vector of ones) and a random Gaussian component, allowing for controlled mutual coherence.
  • Sparse Spike Train Deconvolution Dictionaries: Based on a Gaussian impulse response, these dictionaries are characterized by high coherence, simulating challenging inverse problems.

Key Insights and Ideas

  • OLS Recovery Guarantees: The paper establishes that OLS, like OMP, is guaranteed to achieve exact support recovery under the Exact Recovery Condition (ERC). This is a significant theoretical contribution for OLS.
  • Divergent Behavior Beyond ERC: When the ERC is not met, OMP and OLS exhibit distinct behaviors. The paper shows that OLS can sometimes recover supports that OMP fails to, and vice-versa, suggesting no uniform superiority.
  • OLS's Exploration Capability: OLS demonstrates a stronger ability to "explore" and reach various sparse supports compared to OMP, which can sometimes fail to reach certain supports regardless of the input signal.
  • Correlated Dictionaries Favor OLS: For dictionaries with strongly correlated atoms, OLS often achieves guaranteed exact recovery in fewer iterations than OMP. This is a key practical insight.
  • Bad Recovery in OMP: The paper identifies conditions (BRC-OMP) under which OMP is guaranteed to fail, particularly in scenarios with correlated atoms, highlighting a vulnerability not shared by OLS.

Key Results

  • Theorem 2: ERC is a sufficient condition for OLS to achieve exact recovery in at most $k$ steps.
  • Theorems 3 & Corollary 1: ERC-Oxx conditions (ERC-OMP and ERC-OLS) are sufficient for OLS and OMP to achieve exact recovery after $q$ successful iterations.
  • Theorems 4 & 5: ERC-Oxx conditions are shown to be necessary in a worst-case sense for OLS and OMP, respectively, under certain reachability assumptions.
  • Theorem 6: Guarantees that OLS will successfully recover the last true atom in the $k$-th iteration if the first $k-1$ iterations have selected true atoms.
  • Theorem 7 (BRC-OMP): Provides a sufficient condition for OMP to fail, particularly relevant for correlated dictionaries.
  • Empirical Findings: Simulations show that for correlated dictionaries, OLS often meets its recovery conditions earlier than OMP. For Gaussian dictionaries, their performance is more similar. The bad recovery condition for OMP is shown to be more frequently met with increasing dictionary correlation.

Limitations and Future Work

  • Theoretical vs. Practical: The authors acknowledge that the derived conditions are theoretical "success guarantees" and might not directly translate to practitioners' everyday use, but they strengthen confidence in the algorithms' underlying heuristics.
  • Reachability Assumption for OMP: The necessary condition for OMP (Theorem 5) requires an assumption that the target support is "reachable" by OMP, which is not required for OLS (Theorem 4). This highlights a potential limitation in OMP's analysis.
  • Future Work: The paper suggests further exploration of the "bad recovery condition" for OMP, especially in the context of convolutive problems with strongly correlated atoms. The empirical results also point towards further investigation into the phase transition behavior of these algorithms for various dictionary types and sparsity levels.

Summary updated

Abstract

Tropp's analysis of orthogonal matching pursuit (OMP) using the exact recovery condition (ERC) is extended to a first exact recovery analysis of orthogonal least squares (OLS). We show that when the ERC is met, OLS is guaranteed to exactly recover the unknown support in at most $k$ iterations where $k$ denotes the support cardinality. Moreover, we provide a closer look at the analysis of both OMP and OLS when the ERC is not fulfilled. The existence of dictionaries for which some subsets are never recovered by OMP is proved. This phenomenon also appears with basis pursuit where support recovery depends on the sign patterns, but it does not occur for OLS. Finally, numerical experiments show that none of the considered algorithms is uniformly better than the other but for correlated dictionaries, guaranteed exact recovery may be obtained after fewer iterations for OLS than for OMP.
BibTeX
@article{soussen2013joint,
  author = {Charles Soussen and Rémi Gribonval and Jérôme Idier and Cédric Herzet},
  title = {{Joint k-Step Analysis of Orthogonal Matching Pursuit and Orthogonal Least Squares}},
  journal = {IEEE Trans. Information Theory},
  year = {2013},
  url = {https://openreview.net/forum?id=sySR4ARal6},
}
Figure