Asymptotic convergence-rate conjecture for iterative hard thresholding in matrix completion

Let $\bm H_n=\bm W_{pq}^{n}(\bm W_{pq}^{n})^{\top}$ be the matrix from Theorem~, where $\bm W_q^n=\bm V_{\perp}^{n_2}\otimes\bm U_{\perp}^{n_1}$ forms a concentrated sequence of semi-orthogonal matrices, and let $\rho$ be the linear rate defined in. As $m\to\infty$, assume the same setting as in Theorem~. Asymptotic convergence-rate conjecture. The linear rate $\rho$ converges almost surely to $p_\infty=1-\lambda^-$, where $\lambda^-$ is the lower endpoint of the limiting spectral distribution in, as given in. This conjecture predicts that the smallest eigenvalue of $\bm H_n$ converges to $\lambda^-$, so the asymptotic linear convergence rate is determined by the lower edge of the limiting spectrum. The preceding theorem establishes convergence of the empirical spectral distribution, but does not establish convergence of its smallest eigenvalue; the almost-sure convergence of $\rho$ therefore remains conjectural.