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 $\\|{W} \circ (U V^\top - A) \\|_F^2$ is minimized. Previous work has to pay $\Omega(n^2)$ time when matrices $A$ and $W$ are dense, e.g., having $\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.
Cite
Text
Li et al. "When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?." Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, 2025.Markdown
[Li et al. "When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?." Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, 2025.](https://mlanthology.org/aistats/2025/li2025aistats-we/)BibTeX
@inproceedings{li2025aistats-we,
title = {{When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?}},
author = {Li, Chenyang and Liang, Yingyu and Shi, Zhenmei and Song, Zhao},
booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics},
year = {2025},
pages = {2710-2718},
volume = {258},
url = {https://mlanthology.org/aistats/2025/li2025aistats-we/}
}