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

2025/02/24 by Li, Chenyang, Liang, Yingyu, Shi, Zhenmei +1
#Artificial Intelligence (cs.AI) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2502.16912

Abstract

The weighted low-rank approximation problem is a fundamental numerical linear algebra problem and has many applications in machine learning. Given a n × n weight matrix W and a n × n matrix A, the goal is to find two low-rank matrices U, V ∈ ℝ^{n × k} such that the cost of ‖ W ∘ (U V^\top - A) ‖_F² is minimized. Previous work has to pay Ω(n²) time when matrices A and W are dense, e.g., having Ω(n²) 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.

Related

• Regularized Weighted Low Rank Approximation
• Approximation Algorithms for ℓ₀-Low Rank Approximation
• Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation
• Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices
• On Weighted Low-Rank Approximation