Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time

In this work, the authors proposed the analysis of a robust and fast matrix completion algorithm based on the alternating minimization method. The total running time is linear in terms of the complexity of verifying the correctness of a completion.

The paper studies the low rank matrix completion problem using alternating minimization. Existing algorithms based on alternating minimization for this problem (Jain, Netrapalli and Sanghavi) takes time $\tilde{O}(|\Omega|k^2)$ time where $\Omega$ is the set of entries samples (nearly linear in $n$ for an $m \times n$ incoherent matrix $M$) and $k$ is the target rank $(k<<m,n)$. The main computational bottleneck in alternating minimization comes from solving two multiple response regressions per iteration (once for U and once for V). The algorithm presented in this paper proposes solving the regression problems approximately using off-the shelf sketching based solvers which take nearly linear time in input size per iteration and thus, the time for solving each regression problem reduces to $\tilde{O}(|\Omega|k)$ (with extra $\log(1/\epsilon)$ steps for convergence). However, this complicates the analysis of the algorithm as the solution at every iteration cannot be written exactly in factorized form (so the previous analysis doesn't carry through). This runtime is equal to verification time for the solution upto polylog factors. To analyze this, an inductive argument is presented which shows that at every step, the approximate solution for $U$ or $V$ is close to the optimal solution $U^*$ and $V^*$. Moreover, it is shown that the incoherence of the exact solutions to the regression problem is preserved. Finally, to show that the incoherence of the approximate solution is also preserved, some matrix perturbation bounds are developed which show that as long as any two matrices are very close in spectral norm and one matrix is incoherent, the other matrix will also be incoherent. The sample complexity for the proposed algorithm is the same as that of the old algorithm.

The authors give a nearly linear time algorithm (in the number of samples) for low-rank matrix completion. Specifically, they give a $O(|\Omega| k)$ time alternating-minimization based algorithm that converges to the original underlying rank-$k$, $\mu$-incoherent matrix $M \in \mathbb{R}^{m \times n}$ when $|\Omega| = \tilde{O}(\kappa^2 \mu^2 n k^{4.5})$ samples are drawn from it.

The running time guarantee improves on a line of works, starting with that of Jain et. al (2013), on the efficiency of each step in AM framework -- going from $O(|\Omega| k^2)$ running time to $O(|\Omega| k)$ time. This compares however to a recent paper (that uses a different approach altogether) by Kelner et. al (2023) also achieving a $O(|\Omega| k)$ running time with significantly fewer samples $|\Omega| = O(n k^{2 + o(1)})$.

The improvement comes from solving each multiple response regression problem (to obtain the low-rank factorization $UV$) approximately instead of exactly.

The authors main technical contribution is in analyzing the how the error introduced in solving for $U$ and $V$ approximately, propagates in the iterative process. Specifically they show, using a careful double induction argument and an incoherence bound on the perturbation of row norms of incoherent matrices that the incoherence of the approximate factors in the $t$-th iteration $\hat{U}_t, \hat{V}_t$ as well as the exact solutions they are approximating $U_t, V_t$ are incoherent as well as approach the true subspaces $U^*, V^*$.

References

Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi. Low-rank matrix completion using alternating minimization. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pp. 665–674, 2013

Jonathan Kelner, Jerry Li, Allen Liu, Aaron Sidford, and Kevin Tian. Matrix completion in almostverification time. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS’23, 2023

Dear reviewers,

We have updated our pdf draft on the open review, by incorporating suggestions and comments from you. Thank you all for your valuable insights and comments! Below is a list of modifications we have made:

1. We have presented an informal version of our main theorem at the end of Section 1, so that readers have a clearer picture on the main result earlier in the paper.

2. In Section 4.1 - 4.3, technique overviews, we have added more details. For example, in Section 4.1, we demonstrate the necessity of developing a perturbation theory --- as our induction step assumes the exact matrices $U_{t+1}, V_{t+1}$ are incoherent, but to further bound the distance, we need $\widehat U_{t+1}, \widehat V_{t+1}$ are incoherent. The later is hard to enforce in the induction step, but we alternatively assume the exact matrices are incoherent, and use perturbation to show that the approximate matrices are also incoherent. We similarly expand on the proof for perturbation in Section 4.2.

3. We included a detailed comparison with Kelner et al. (2023b) at the end of Section 4. In short, both of our algorithms have a runtime behavior of $\widetilde O(|\Omega| k)$, but theirs has a better sample complexity in terms of dependency on $k$ and $\kappa$. However, we also note that their algorithm is much more complicated than widely-used alternating minimization or (stochastic) gradient descent. To implement their algorithm, one has to resort to approximate singular values and spectral norms, use Nesterov's accelerated gradient descent and a complicated post-processing phase. It is unclear when deployed in practice, their algorithm will actually outperform alternating minimization or (S)GD.

4. In Appendix, Lemma B.5, we modified the proof and dropped the assumptions the matrix $A$ has full column rank. Our new proof is based on SVD and works for any non-full rank matrix. We also elaborate on we can apply Pythagorean theorem. In short, we prove that the subspace $A(A^\top A)^\dagger A^\top-I$ is orthogonal to the column space of $A$, and $Ax_{{\rm OPT}}-b=(A(A^\top A)^\dagger A^\top-I)b$ while $Ax'-Ax_{{\rm OPT}}=A(x'-x_{{\rm OPT}})$. Thus we can apply Pythagorean theorem. For more details, we refer you to page 26 - 27 of the draft.

5. In Appendix, Lemma G.3, we additionally require $\epsilon_0\leq \frac{1}{2}\sigma_{\min}(A)$ to make the proof easier to understand, and we further simplify the proof by using an argument based on difference of squares formula. This makes the proof logic cleaner and easier to follow. We refer you to page 51 - 52 for more details.

Dear Chairs and Reviewers,

We would like to kindly remind you that the discussion period is ending soon. We highly appreciate all the time and effort the reviewers have dedicated to our manuscript, along with their insightful suggestions. We have carefully considered these comments and believe we have addressed each of them. Should there be further concerns, we are eager to engage in further discussion with the reviewers.

Reviewer QBsW's primary concern revolves around the significance of our work in comparison to Kelner et al. (2023). We have provided a detailed explanation and discussion, not only in response to the reviewer but also within our manuscript (refer to page 9).

Reviewer CTEU has raised concerns about our proofs. We have provided detailed explanations addressing all of Reviewer CTEU's concerns and have defended the soundness of our proofs. Additionally, to enhance the presentation of our paper, we have made corresponding changes to the manuscript, aimed at ensuring future readers are more convinced of the solidity of our results.

Regarding Reviewer kPm7's suggestions, we have followed the advice to improve the manuscript's presentation by condensing Section 1 and enriching Sections 4.1 to 4.3 with more detailed discussions, thereby enhancing clarity in our technique overview. We also mainly focus on intuitions because the results are highly technical, and presenting intuition will enhance readability for our audience.

We believe that we have addressed all reviewers' comments and eagerly await their valuable responses. We are fully committed to revising our manuscript further to ensure its suitability in ICLR. Once again, we extend our gratitude to all the reviewers and the chair for considering our manuscript.

Best regards, Authors.

The paper provides a nearly linear time algorithm for low rank matrix completion using alternate minimization. Previous algorithms for this problem using alternate minimization were known, but they required exact minimization. The paper shows that this approach is robust to approximate updates. The lack of experiments was noted in the review, but the paper appears theoretically sound, interesting to sections of the ICLR community and the authors have addressed the reviewer concerns during the discussion period.

Accept (poster)