在特定条件下，稠密矩阵的加权低秩逼近可实现接近线性时间求解。
When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?
- 提出在特定条件下可突破传统二次时间瓶颈的方法。
- 证明稠密场景下仍存在近似线性 $n^{1+o(1)}$ 时间解法的可能。
- 适合关注高效数值算法与机器学习优化的科研人员。
加权低秩逼近是基础的数值线性代数问题，在机器学习中有广泛应用。给定 $n imes n$ 的权值矩阵 $W$ 与数据矩阵 $A$，目标是寻找两个 $n imes k$ 的低秩矩阵 $U, V$，使 $ig\| W igcirc (U V^ op - A) igig floor_F^2$ 最小化。以往工作在 $A$ 与 $W$ 均为稠密（即非零元素数量为 $Ω(n^2)$）时，时间复杂度下界为 $Ω(n^2)$。本文证明：在某些特定条件下，即使 $A$ 与 $W$ 稠密，仍可实现近乎线性时间 $n^{1+o(1)}$ 的求解。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。