Sparse recovery from quadratic equations, part II: hardness and incoherence

Augustin CossearXiv 2024 · OpenReview

TL;DR

This paper tackles the "square root bottleneck" in recovering sparse signals from quadratic measurements, a problem fundamental to areas like phase retrieval. The authors provide a new initialization strategy that improves recovery guarantees for certain signal types and offers theoretical evidence for why some regimes of this problem are computationally hard, linking it to the Overlap Gap Property from statistical physics.

What Problem Does This Paper Address?

Recovering a sparse signal $\mathbf{x}_0$ (a vector with few non-zero entries) from measurements of the form $\langle \mathbf{A}_i, \mathbf{x}\mathbf{x}^\intercal \rangle = \langle \mathbf{A}_i, \mathbf{x}_0\mathbf{x}_0^\intercal \rangle + \varepsilon_i$, where $\mathbf{A}_i$ are random matrices and $\varepsilon_i$ are noise terms, is a challenging problem. While theory suggests we only need $O(k)$ measurements (where $k$ is the sparsity) to uniquely identify $\mathbf{x}_0$, existing polynomial-time algorithms typically require $m = \Omega(k^2)$ measurements. This gap is known as the "square root bottleneck." Previous work has linked this bottleneck to the difficulty of initializing iterative algorithms. This paper aims to bridge this gap by developing a better initialization strategy and providing theoretical insights into the inherent hardness of certain parameter regimes.

Methods

The paper introduces a novel initialization procedure that leverages the entire set of measurements, unlike prior methods that might use thresholding. This initialization is then combined with existing algorithms like truncated gradient descent and a sparse power factorization method to achieve improved recovery guarantees. A key theoretical contribution is the demonstration of the Overlap Gap Property (OGP) in a specific parameter regime ($m = o(k^2)$ for maximally incoherent signals). The OGP is a topological property of the optimization landscape that is conjectured to indicate algorithmic intractability. The proof of the OGP relies on a lower bound on the tail of chi-squared random variables, derived from moderate deviation theory.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis with synthetic data generated from specific random matrix models (e.g., Gaussian).

Key Insights and Ideas

  • Bridging the Initialization Gap: The paper proposes a more robust initialization for sparse recovery from quadratic measurements, which is crucial for breaking the $\Omega(k^2)$ sample complexity barrier. This initialization is more general than previous approaches and is shown to work for both quadratic recovery and phase retrieval.
  • Topological Evidence for Hardness: The authors provide theoretical evidence for why certain settings of sparse recovery are computationally hard. By demonstrating the Overlap Gap Property (OGP) in a challenging regime, they connect the problem to known indicators of algorithmic intractability in statistical physics.
  • The Role of Incoherence: The paper highlights how the "incoherence" of the sparse signal (measured by $\mu_0 = \|\mathbf{x}_0\|_\infty / \|\mathbf{x}_0\|_2$) significantly impacts the required number of measurements and the hardness of recovery. Lower incoherence (larger $\mu_0$) generally leads to better recovery guarantees.
  • Moderate Deviations for Proofs: The use of moderate deviation principles for chi-squared random variables is a key technical ingredient for proving the OGP, showcasing its power in analyzing complex optimization landscapes.

Key Results

  • Improved Recovery Guarantees: The paper establishes that for $k$-sparse vectors with incoherence $\mu_0$, recovery is possible with $m \gtrsim \mu_0^{-2}k \vee \mu_0^{-4}$ measurements (up to log factors) using the proposed initialization and standard descent algorithms. This improves upon previous results, especially for less incoherent signals.
  • Phase Retrieval Connection: The initialization strategy is shown to be applicable to phase retrieval, achieving sample complexity that matches the current optimal bounds.
  • Evidence of Algorithmic Hardness: For maximally incoherent signals ($\mu_0^{-2} = k$) and $m = o(k^2)$, the paper provides evidence for topological hardness by showing the Overlap Gap Property (OGP) holds for a specific level of over-parametrization. This suggests that algorithms might struggle in this regime.

Limitations and Future Work

  • Computational Complexity: While the paper provides theoretical guarantees for recovery, the computational complexity of the proposed initialization and the subsequent algorithms is not always explicitly analyzed in polynomial time terms for all regimes.
  • Over-parametrization for OGP: The demonstration of the OGP relies on a specific form of over-parametrization, which is a technique to "smooth" the optimization landscape. Understanding the necessity and impact of this over-parametrization in other contexts could be a future direction.
  • Practical Performance: The paper focuses on theoretical guarantees. Empirical validation and comparison with existing practical algorithms would be valuable.
  • Generalization to other signal models: The current work focuses on sparse signals. Extending the analysis to other signal structures or measurement models could be a fruitful avenue.

Summary updated

Abstract

We study the square root bottleneck in the recovery of sparse vectors from quadratic equations. It is acknowledged that a sparse vector $ \mathbf x_0\in \mathbb{R}^n$, $\| \mathbf x_0\|_0 = k$ can in theory be recovered from as few as $O(k)$ generic quadratic equations but no polynomial time algorithm is known for this task unless $m = \Omega(k^2)$. This bottleneck was in fact shown in previous work to be essentially related to the initialization of descent algorithms. Starting such algorithms sufficiently close to the planted signal is known to imply convergence to this signal. In this paper, we show that as soon as $m\gtrsim \mu_0^{-2}k \vee \mu_0^{-4}$ (up to log factors) where $\mu_0 = \| \mathbf x_0\|_\infty/\| \mathbf x_0\|_2$, it is possible to recover a $k$-sparse vector $ \mathbf x_0\in \mathbb{R}^n$ from $m$ quadratic equations of the form $\langle \mathbf A_i, \mathbf x \mathbf x^\intercal\rangle = \langle \mathbf A_i, \mathbf x_0 \mathbf x_0^\intercal\rangle + \varepsilon_i $ by minimizing the classical empirical loss. The proof idea carries over to the phase retrieval setting for which it provides an original initialization that matches the current optimal sample complexity (see e.g. [Cai 2023]). In the maximally incoherent regime $\mu_0^{-2}=k$, and for $m=o(k^2)$ we provide evidence for topological hardness by showing that a property known as the Overlap Gap Property (OGP), which originated in spin glass theory and is conjectured to be indicative of algorithmic intractability when optimizing over random structures, holds for a particular level of overparametrization. The key ingredient of the proof is a lower bound on the tail of chi-squared random variables which follows from the theory of moderate deviations.
BibTeX
@misc{cosse2024sparse,
  author = {Augustin Cosse},
  title = {{Sparse recovery from quadratic equations, part II: hardness and incoherence}},
  year = {2024},
  eprint = {2412.19341},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2412.19341},
}
Figure