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

Chenyang Li, Yingyu Liang, Zhenmei Shi +1

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$…