When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929728738295808 |
|---|---|
| author | Li, Chenyang Liang, Yingyu Shi, Zhenmei Song, Zhao |
| author_facet | Li, Chenyang Liang, Yingyu Shi, Zhenmei Song, Zhao |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_16912 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time? Li, Chenyang Liang, Yingyu Shi, Zhenmei Song, Zhao Computational Complexity Artificial Intelligence Machine Learning 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. |
| title | When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time? |
| topic | Computational Complexity Artificial Intelligence Machine Learning |
| url | https://arxiv.org/abs/2502.16912 |