cs.LGJun 7, 2023

Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation

Authors: Zhao Song, Mingquan Ye, Junze Yin, Lichen Zhang

Organizations: Simons Institute for the Theory of Computing, UC Berkeley · University of Illinois, Chicago · Rice University · Massachusetts Institute of Technology

Abstract

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.

Figures & tables

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Feb 21, 2023

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

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.
May 10, 2026

Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximation

The power method is one of the most fundamental tools for extracting top principal components from data through low-rank matrix approximation. Yet, when the target rank is large, the cost of matrix multiplication associated with this procedure becomes a major bottleneck. We develop an algorithmic and theoretical framework for accelerating the power method using fast sketching, which is a popular paradigm in randomized linear algebra. Our framework leads to simple and provably efficient methods for singular value decomposition, low-rank factorization, and Nyström approximation, which attain strong numerical performance on benchmark problems. The key novelty in our analysis is the use of regularized spectral approximation, a property of fast sketching methods which proves more flexible in generalizing power method guarantees than traditional arguments.
Oct 31, 2026

Unbiased Low-Rank Approximation for Repeated Matrix-Vector Multiplication: Stability and Optimal Sampling

Replacing the matrix in an iteration with random low-rank matrices can reduce the cost of matrix-vector multiplication. However, even if the sampled matrices equal the original matrix in expectation, the expected squared norm of the random iterates may grow while the original iteration converges. Under a fixed rank bound, we study how to choose the distribution of these random matrices to minimize this growth when sampling independently at each step. We derive an exact formula for the optimal asymptotic growth factor and use it to determine when the expected squared norm can converge to zero. We then characterize precisely when a fixed sampling distribution achieves this optimal factor and construct finite-support optimal distributions in every attainable case. These results determine the minimum rank required for stability and provide optimal sampling designs under the prescribed rank constraint.