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

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 $\mathrm{\parallel }W\circ (U{V}^{\mathrm{\top }}-A){\mathrm{\parallel }}_F^2$ is minimized. Previous work has to pay $\mathrm{\Omega }(n^2)$ time when matrices $A$ and $W$ are dense, e.g., having $\mathrm{\Omega }(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.