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

Chenyang Li, Yingyu Liang, Zhenmei Shi, Zhao Song · 2025

Read When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time? by Chenyang Li, Yingyu Liang, Zhenmei Shi, Zhao Song (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-16912.txt.

Description

Chenyang Li, Yingyu Liang, Zhenmei Shi, and Zhao Song ask when weighted low-rank approximation can beat quadratic time in 2025. The problem asks for two thin factors whose product nears a given matrix, with each entry weighted. It sits at the core of many learning tools.

Dense inputs seemed to force at least quadratic time in all prior work. The authors show a regime where near-linear time still works, even when both matrices are dense. The result cuts the cost from order n squared to just above n. The regime limits rest on the weight and rank structure, which the paper pins down. The finding opens faster paths for large dense fitting tasks.

Catalog record

CREATORChenyang Li, Yingyu Liang, Zhenmei Shi, Zhao Song
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE40 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-16912

Browse the full library · About the Tower of Babel