In the recovery of sparse vectors from quadratic measurements, the presence of linear terms breaks the square root bottleneck

Augustin Cosse

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<…