





















Motivated by recent results in the statistical physics of spin glasses, we study the recovery of a sparse vector $\mathbf{x}_0\in \mathbb{S}^{n-1}$, $\|\mathbf{x}_0\|_{\ell_0} = k<n$, from $m$ quadratic measurements of the form $ (1-λ)\langle \mathbf{A}_i, \mathbf{x}_0\mathbf{x}_0^T \rangle + λ\langle\mathbf{c}_i,\mathbf{x}_0 \rangle $ where $\mathbf{A}_{i}, \mathbf{c}_{i}$ have i.i.d Gaussian entries. This can be related to a constrained version of the 2-spin Hamiltonian with external field for which it was recently shown (in the absence of any structural constraint and in the asymptotic regime) that the geometry of the energy landscape becomes trivial above a certain threshold $λ> λ_c\in (0,1)$. Building on this idea we study the evolution of the so-called square root bottleneck for $λ\in [0,1]$ in the setting of the sparse rank one matrix recovery/sensing problem. We show that recovery of the vector $\mathbf{x}_0$ can be guaranteed as soon as $m\gtrsim k^2 (1-λ)^2/λ^2$, $λ\gtrsim k^{-1/2}$ provided that this vector satisfies a sufficiently strong incoherence condition, thus retrieving the linear regime for an external field $(1-λ)/λ\lesssim k^{-1/2}$. Our proof relies on an interpolation between the linear and quadratic settings, as well as on standard convex geometry arguments.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。