Additive Error Guarantees for Weighted Low Rank Approximation

Low Rank Approximation • Classic formulation: Given matrix A, find a rank-k matrix L that minimizes . Can be solved efficiently (e.g., SVD). • Natural variants are NP hard: e.g., different importance for different entries. • Weighted LRA: Given matrix A and weight matrix W of the same size, find a rank-k matrix L that minimizes