Hardt–Price gap-independent approximation conjecture for the noisy power method

Let $\boldsymbol{A}$ be a matrix, let $\boldsymbol{A}_k$ be its best rank-$k$ approximation, and let $\boldsymbol{U}_k$ contain the top-$k$ left singular vectors of $\boldsymbol{A}$. Let $\boldsymbol{X}_L$ be the output after $L$ iterations of the noisy power method, with $p\geq2k$ columns, and let $\boldsymbol{G}_\ell$ denote the noise at iteration $\ell$. Hardt–Price gap-independent approximation conjecture. Fix $\epsilon\in(0,1)$. If, for every iteration $\ell=1,\ldots,L$,

$$\|\boldsymbol{G}_\ell\|_2=O(\epsilon\sigma_{k+1}),\qquad \|\boldsymbol{U}_k^\top\boldsymbol{G}_\ell\|_2=O\left(\epsilon\sigma_{k+1}\sqrt{k/d}\right),$$

then, with high probability, after $L=O(\log d/\epsilon)$ iterations,

$$\|\boldsymbol{A}-\boldsymbol{X}_L\boldsymbol{X}_L^\top\boldsymbol{A}\|_2\leq(1+O(\epsilon))\|\boldsymbol{A}-\boldsymbol{A}_k\|_2=(1+O(\epsilon))\sigma_{k+1}.$$

This is motivated by the fact that approximation error can remain small even when the top-$k$ eigenspace is not well defined because a spectral gap is small. The supplied text presents it as a conjecture attributed to Hardt and Price, and gives no resolution.