# Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation

DevFeed: [Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation](<https://devfeed.tech/articles/efficient-alternating-minimization-with-applications-to-weighted-low-rank-approximation-132713.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2306.04169>)

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

Published: 2026-11-13T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Machine learning](<https://devfeed.tech/topics/machine-learning.md>)

Tags: [analysis](<https://devfeed.tech/tags/analysis.md>), [applications](<https://devfeed.tech/tags/applications.md>), [approximation](<https://devfeed.tech/tags/approximation.md>), [completion](<https://devfeed.tech/tags/completion.md>), [cost](<https://devfeed.tech/tags/cost.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [exponential-time-hypothesis](<https://devfeed.tech/tags/exponential-time-hypothesis.md>), [framework](<https://devfeed.tech/tags/framework.md>), [gaussian](<https://devfeed.tech/tags/gaussian.md>), [guarantees](<https://devfeed.tech/tags/guarantees.md>), [learning](<https://devfeed.tech/tags/learning.md>), [linear](<https://devfeed.tech/tags/linear.md>), [linear-algebra](<https://devfeed.tech/tags/linear-algebra.md>), [machine-learning](<https://devfeed.tech/tags/machine-learning.md>), [math-oc](<https://devfeed.tech/tags/math-oc.md>), [matrix](<https://devfeed.tech/tags/matrix.md>), [multiple](<https://devfeed.tech/tags/multiple.md>), [np-hard](<https://devfeed.tech/tags/np-hard.md>), [rank](<https://devfeed.tech/tags/rank.md>), [regression](<https://devfeed.tech/tags/regression.md>), [robust](<https://devfeed.tech/tags/robust.md>), [running](<https://devfeed.tech/tags/running.md>)

## AI overview

The paper presents an alternating-minimization framework for weighted low-rank approximation that permits approximate updates. A high-accuracy multiple-response regression solver and robust analysis reduce each iteration's cost from ‖W‖₀k² to ‖W‖₀k. The authors also replace a prior random initialization with subspace iteration from a Gaussian start, giving total running time Õ((‖W‖₀k + nk³) log(1/ε)), including initialization. The guarantee requires the weight matrix to be within spectral distance γn of the all-ones matrix, for γ polynomially small in n.

## Source excerpt

arXiv:2306.04169v4 Announce Type: replace 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 \in \mathbb{R}^{n \times n}$, a non-negative weight matrix $W \in \mathbb{R}_{\geq 0}^{n \times n}$, a parameter $k$, the goal is to output two matrices $X,Y\in \mathbb{R}^{n \times k}$ such that $\| 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\|_0k^2$ to $\|W\|_0 k$ where $\|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 $\widetilde O((\|W\|_0 k+nk^3)\log(1/\epsilon))$ includes the initialization. In exchange, our guarantee needs the weight matrix to be within spectral distance $\gamma n$ of the all-ones matrix for a $\gamma$ that is polynomially small in $n$.