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

Augustin Cosse

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…