When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?
This addresses a fundamental computational bottleneck in numerical linear algebra and machine learning applications, offering a significant speedup for dense matrix scenarios.
The paper tackles the weighted low-rank approximation problem for dense matrices, showing that in a certain regime, it can be solved in almost linear time of n^(1+o(1)), improving upon previous Ω(n^2) time requirements.
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 $\| W \circ (U V^\top - A) \|_F^2$ is minimized. Previous work has to pay $Ω(n^2)$ time when matrices $A$ and $W$ are dense, e.g., having $Ω(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.