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

Jun 7, 2023

Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation

Weighted low rank approximation is a fundamental problem in numerical linear algebra, and it has many applications in machine learning. Given a matrix M∈Rn×nM \in \mathbb{R}^{n \times n}, a non-negative weight matrix W∈R≥0n×nW \in \mathbb{R}_{\geq 0}^{n \times n}, a parameter kk, the goal is to output two matrices X,Y∈Rn×kX,Y\in \mathbb{R}^{n \times k} such that ∥W∘(M−XY⊤)∥F\| W \circ (M - X Y^\top) \|_F is minimized, where ∘\circ denotes the Hadamard product. It naturally generalizes the well-studied low rank matrix completion problem. Such a problem is known to be NP-hard and even hard to approximate assuming the Exponential Time Hypothesis [GG11, RSW16]. Meanwhile, alternating minimization is a good heuristic solution for weighted low rank approximation. In particular, [LLR16] shows that, under mild assumptions, alternating minimization does provide provable guarantees. In this work, we develop an efficient and robust framework for alternating minimization that allows the alternating updates to be computed approximately. For weighted low rank approximation, this improves the cost of each iteration of [LLR16] from ∥W∥0k2\|W\|_0k^2 to ∥W∥0k\|W\|_0 k where ∥W∥0\|W\|_0 denotes the number of nonzero entries of the weight matrix. At the heart of our framework is a high-accuracy multiple response regression solver together with a robust analysis of alternating minimization. We also replace the random initialization of [LLR16], whose claimed guarantee fails, by subspace iteration from a Gaussian start, so our total running time of O~((∥W∥0k+nk3)log⁡(1/ε))\widetilde O((\|W\|_0 k+nk^3)\log(1/ε)) includes the initialization. In exchange, our guarantee needs the weight matrix to be within spectral distance γnγn of the all-ones matrix for a γγ that is polynomially small in nn.
Sep 15, 2026

Near-Optimal Nonconvex Matrix Completion

We study nonconvex methods for matrix completion, the problem of recovering a low-rank matrix from a subset of its entries. Convex methods achieve sample complexity linear in the matrix dimension and the rank, up to logarithmic factors, whereas global guarantees for commonly used nonconvex methods require a higher polynomial dependence on the rank. We close this gap by analyzing Riemannian gradient descent (RGD) and Riemannian Gauss--Newton (RGN) methods. For an n×nn\times n matrix of rank rr with incoherence parameter μμ and condition number κκ, the two methods achieve exact recovery with high probability from O(μnrlog⁡nlog⁡(nκ))O(μnr\log n\log(nκ)) and O(μnrlog⁡nlog⁡(2μrκ))O(μnr\log n\log(2μrκ)) observations, respectively. The methods use a multiscale residual initialization, while the analysis simultaneously controls the spectral error and incoherence. The resulting RGD iterates converge linearly, whereas RGN eventually converges Q-quadratically.
May 4, 2026

Active multiple matrix completion with adaptive confidence sets

In this work, we formulate a new multi-task active learning setting in which the learner's goal is to solve multiple matrix completion problems simultaneously. At each round, the learner can choose from which matrix it receives a sample from an entry drawn uniformly at random. Our main practical motivation is market segmentation, where the matrices represent different regions with different preferences of the customers. The challenge in this setting is that each of the matrices can be of a different size and also of a different rank which is unknown. We provide and analyze a new algorithm, MAlocate that is able to adapt to the unknown ranks of the different matrices. We then give a lower-bound showing that our strategy is minimax-optimal and demonstrate its performance with synthetic experiments.