When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?

Abstract

The weighted low-rank approximation problem is a fundamental numerical linear algebra problem and has many applications in machine learning. Given a $n\times n$ weight matrix $W$ and a $n\times n$ matrix $A$, the goal is to find two low-rank matrices $U,V\in {\mathbb{R}}^{n\times k}$ such that the cost of $\Vert W\circ (U{V}^{\top }-A){\Vert }_F^2$ is minimized. Previous work has to pay $\hat{I}\text{c◯}(n^2)$ time when matrices $A$ and $W$ are dense, e.g., having $\hat{I}\text{c◯}(n^2)$ non-zero entries. In this work, we show that there is a certain regime, even if $A$ and $W$ are dense, we can still hope to solve the weighted low-rank approximation problem in almost linear $n^{1+o(1)}$ time.

AIStats 2025