In this thesis we consider the Weighted Low Rank Approximation problem. For an m × n matrix A, we give a row-sampling algorithm algorithm running in O(nnz(A)log n+(m+n) ⋅ poly(log n, k, 1/w, 1/ε, 1/κ(A))) time, where all weights in the weight matrix are within a ratio of 1/w, κ (A) denotes the condition number of matrix A, and nnz(A) denotes the number of non-zero entries of A. Our algorithm is bicriteria, and outputs a matrix of rank O(k² ⁄ w²ε²κ²(A)) and achieves a multiplicative (1 + ε)-approximation to the cost of the best rank-κ matrix. Compared to prior work of Bhaskara et al. (PMLR, 2021), our algorithm achieves multiplicative rather than additive error, outputs a low rank approximation with right factor corresponding to an actual subset of rows of A, has leading order term in the running time of nnz(A) rather than at least nnz(A) ⋅ κ/ε², and has the same bicriteria rank in the worst case. We also show the 1/ω factor is necessary in the bicriteria rank of any row subset selection algorithm.

34 pages

Thesis Committee:
David P. Woodruff (Chair)
Richard Peng (University of Waterloo)

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu