Relative Errors for Deterministic Low-Rank Matrix Approximations

Mina Ghashami, Jeff M. Phillips

Abstract

We consider processing an n x d matrix A in a stream with row-wise updates according to a recent algorithm called Frequent Directions (Liberty, KDD 2013). This algorithm maintains an l x d matrix Q deterministically, processing each row in O(d l^2) time; the processing time can be decreased to O(d l) with a slight modification in the algorithm and a constant increase in space. We show that if one sets l = k+ k/eps and returns Q_k, a k x d matrix that is the best rank k approximation to Q, then we achieve the following properties: ||A - A_k||_F^2 <= ||A||_F^2 - ||Q_k||_F^2 <= (1+eps) ||A - A_k||_F^2 and where pi_{Q_k}(A) is the projection of A onto the rowspace of Q_k then ||A - pi_{Q_k}(A)||_F^2 <= (1+eps) ||A - A_k||_F^2. We also show that Frequent Directions cannot be adapted to a sparse version in an obvious way that retains the l original rows of the matrix, as opposed to a linear combination or sketch of the rows.
BibTeX
@inproceedings{ghashami2014relative,
  author = {Mina Ghashami and Jeff M. Phillips},
  title = {{Relative Errors for Deterministic Low-Rank Matrix Approximations}},
  booktitle = {SODA},
  year = {2014},
  url = {https://openreview.net/forum?id=NycJhgBYL-},
}

Loading related content...

Figure