cs.LGFeb 21, 2023

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

Authors: Yuzhou Gu, Zhao Song, Junze Yin, Lichen Zhang

Organizations: Institute of Advanced Study. · Adobe Research. · Boston University · Massachusetts Institute of Technology.

Abstract

Given a matrix M∈Rm×nM\in \mathbb{R}^{m\times n}, the low rank matrix completion problem asks us to find a rank-kk approximation of MM as UV⊤UV^\top for U∈Rm×kU\in \mathbb{R}^{m\times k} and V∈Rn×kV\in \mathbb{R}^{n\times k} by only observing a few entries specified by a set of entries Ω⊆[m]×[n]Ω\subseteq [m]\times [n]. In particular, we examine an approach that is widely used in practice -- the alternating minimization framework. Jain, Netrapalli, and Sanghavi [JNS13] showed that if MM has incoherent rows and columns, then alternating minimization provably recovers the matrix MM by observing a nearly linear in nn number of entries. While the sample complexity has been subsequently improved [GLZ17], alternating minimization steps are required to be computed exactly. This hinders the development of more efficient algorithms and fails to depict the practical implementation of alternating minimization, where the updates are usually performed approximately in favor of efficiency. In this paper, we take a major step towards a more efficient and error-robust alternating minimization framework. To this end, we develop an analytical framework for alternating minimization that can tolerate a moderate amount of errors caused by approximate updates. Moreover, our algorithm runs in time O~(∣Ω∣k)\widetilde O(|Ω| k), which is nearly linear in the time to verify the solution while preserving the sample complexity. This improves upon all prior known alternating minimization approaches which require O~(∣Ω∣k2)\widetilde O(|Ω| k^2) time.

Explore similar work

CardsList
  1. Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation

    Jun 7, 2023Zhao Song, Mingquan Ye, Junze Yin +1alternating minimizationLow-Rank Approximation

  2. Near-Optimal Nonconvex Matrix Completion

    Sep 15, 2026Jian-Feng Cai, Xiliang Lu, Juntao YouRiemannian OptimizationNonconvex Optimization

  3. Active multiple matrix completion with adaptive confidence sets

    May 4, 2026Andrea Locatelli, Alexandra Carpentier, Michal ValkoActive LearningMulti-Task Learning