Random Sampling of Sparse Trigonometric Polynomials, II. Orthogonal Matching Pursuit versus Basis Pursuit

Stefan Kunis, Holger Rauhut

TL;DR

This paper investigates the recovery of sparse trigonometric polynomials from random samples, comparing the performance of Basis Pursuit (BP) and greedy algorithms like Orthogonal Matching Pursuit (OMP) and Thresholding. The authors provide theoretical guarantees and numerical evidence suggesting that OMP offers a compelling alternative to BP, achieving similar recovery rates with significantly faster computation times.

What Problem Does This Paper Address?

The core problem addressed is compressed sensing applied to sparse trigonometric polynomials. Imagine you have a signal that can be represented as a sum of a few sine and cosine waves (a sparse trigonometric polynomial). You want to perfectly reconstruct this signal, but you can only measure it at a few randomly chosen points. The challenge is to determine how many samples are needed and which algorithms are most effective for this reconstruction. This is crucial in fields like signal processing, image reconstruction, and data analysis where signals are often sparse in some domain. While Basis Pursuit has been well-studied for this problem, the paper focuses on understanding the performance and theoretical guarantees of greedy algorithms, which are often computationally more efficient.

Methods

The paper compares three main algorithms for sparse recovery:

  • Basis Pursuit (BP): This is a convex optimization approach that minimizes the L1-norm of the signal's coefficients subject to the constraint that the reconstructed polynomial matches the observed samples. It's known for its theoretical guarantees but can be computationally intensive.
  • Orthogonal Matching Pursuit (OMP): A greedy algorithm that iteratively selects the Fourier coefficient that best explains the remaining signal. It's conceptually simpler and often faster than BP.
  • Thresholding: Another greedy algorithm that identifies the most significant Fourier coefficients and then reconstructs the signal based on these.

The authors analyze these algorithms under two probabilistic models for sampling points:

  1. Continuous Model: Samples are drawn independently and uniformly from the continuous cube $[0, 2\pi]^d$.
  2. Discrete Model: Samples are drawn uniformly from a finite grid, relevant for discrete Fourier transform scenarios.

Theoretical analysis relies on concepts like the restricted isometry property (RIP) and coherence of the measurement matrix, which quantify how well the matrix preserves distances for sparse vectors.

Datasets

The paper does not introduce new datasets. Instead, it uses synthetic data generated according to the two probabilistic sampling models described above. The experiments involve creating sparse trigonometric polynomials with varying sparsity levels (number of non-zero coefficients), dimensions, and coefficient distributions (e.g., complex coefficients with modulus one, or real and imaginary parts drawn from a normal distribution).

Key Insights and Ideas

  • OMP as a strong contender: The numerical experiments strongly suggest that OMP performs comparably to BP in terms of reconstruction success rates, often outperforming it, especially for larger dimensions.
  • Speed vs. Uniformity Trade-off: Greedy algorithms like OMP are significantly faster than BP. While BP offers a uniform recovery guarantee (meaning a single set of samples can recover any sparse signal of a certain sparsity), greedy algorithms provide a non-uniform guarantee (recovery is likely for a specific signal). For many practical applications, this non-uniform guarantee is sufficient.
  • Impact of Coefficient Distribution: The paper highlights that the dynamic range of coefficients (ratio of largest to smallest non-zero coefficient) can affect the performance of Thresholding, but OMP appears less sensitive to this.
  • Coherence is Key for Uniformity: Uniform recovery guarantees for OMP and BP can be achieved under conditions related to the coherence of the measurement matrix, but this often requires a higher number of samples, scaling quadratically with sparsity.

Key Results

  • Theoretical Guarantees: The paper provides theoretical results for Thresholding and OMP, establishing conditions on the number of samples ($N$) required for successful recovery based on sparsity ($M$) and dimension ($D$). For instance, Theorem 2.4 shows that OMP can recover the support of a sparse trigonometric polynomial in the first step if $N > CM \log(8D/\epsilon)$.
  • Numerical Performance:
    • Success Rate: OMP and BP achieve similar high success rates, often outperforming Thresholding, especially as sparsity increases. Surprisingly, OMP sometimes shows better success rates than BP for larger dimensions.
  • Computation Time: OMP is significantly faster than BP. The experiments show that OMP's computation time grows linearly with sparsity, while BP is orders of magnitude slower.
  • Sampling Models: Both continuous and discrete sampling models yield comparable results in practice.
  • Real vs. Complex Coefficients: For Basis Pursuit, assuming real-valued coefficients (instead of complex) can roughly halve the number of samples needed for recovery.

Limitations and Future Work

  • OMP Theoretical Analysis: While the paper provides theoretical results for the first step of OMP, a complete theoretical analysis of subsequent iterations is noted as difficult due to stochastic dependencies. This remains an open area for future work.
  • Non-uniform vs. Uniform Guarantees: The paper emphasizes the trade-off between the speed of greedy algorithms and the uniform recovery guarantees of BP. Future work could explore methods to bridge this gap or further understand the practical implications of non-uniform guarantees.
  • Comparison with Sublinear Algorithms: The paper mentions algorithms with sublinear time complexity in dimension $D$ but notes that they might require more samples than OMP and BP. A direct numerical comparison of these approaches would be valuable.
  • Noise Stability: While OMP shows promising stability under noise in preliminary experiments, a more thorough theoretical analysis is suggested.

Summary updated

Abstract

We investigate the problem of reconstructing sparse multivariate trigonometric polynomials from few randomly taken samples by Basis Pursuit and greedy algorithms such as Orthogonal Matching Pursuit (OMP) and Thresholding. While recovery by Basis Pursuit has recently been studied by several authors, we provide theoretical results on the success probability of reconstruction via Thresholding and OMP for both a continuous and a discrete probability model for the sampling points. We present numerical experiments, which indicate that usually Basis Pursuit is significantly slower than greedy algorithms, while the recovery rates are very similar.
BibTeX
@article{kunis2008random,
  author = {Stefan Kunis and Holger Rauhut},
  title = {{Random Sampling of Sparse Trigonometric Polynomials, II. Orthogonal Matching Pursuit versus Basis Pursuit}},
  journal = {Found. Comput. Math.},
  year = {2008},
  doi = {10.1007/s10208-007-9005-x},
}
Figure