Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices

MaRDI QIDQ6285394arXivFDO

Authors Cameron Musco, David P. Woodruff

Publication date 11 April 2017

Published in arXiv

arXiv classification

cs.DScs.LGmath.NA

Abstract: We show how to compute a relative-error low-rank approximation to any positive semidefinite (PSD) matrix in sublinear time, i.e., for any $nimesn$ PSD matrix $A$, in $ildeO(ncdotpoly(k/epsilon))$ time we output a rank-$k$ matrix $B$, in factored form, for which $|A-B{|}_F^{2}leq(1+epsilon)|A-A_k{|}_F^2$, where $A_k$ is the best rank-$k$ approximation to $A$. When $k$ and $1/epsilon$ are not too large compared to the sparsity of $A$, our algorithm does not need to read all entries of the matrix. Hence, we significantly improve upon previous $nnz(A)$ time algorithms based on oblivious subspace embeddings, and bypass an $nnz(A)$ time lower bound for general matrices (where $nnz(A)$ denotes the number of non-zero entries in the matrix). We prove time lower bounds for low-rank approximation of PSD matrices, showing that our algorithm is close to optimal. Finally, we extend our techniques to give sublinear time algorithms for low-rank approximation of $A$ in the (often stronger) spectral norm metric $|A-B{|}_2^2$ and for ridge regression on PSD matrices.

Cited in

(1)

• A new analysis of the randomly pivoted Cholesky algorithm

This page was built for publication: Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6285394)