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