SCIENCE@home

Frequent Directions: Simple and Deterministic Matrix Sketching

Mina Ghashami,Edo Liberty,J. M. Phillips,David P. Woodruff

Published 2015 in SIAM journal on computing (Print)

ABSTRACT

We describe a new algorithm called FrequentDirections for deterministic matrix sketching in the row-update model. The algorithm is presented an arbitrary input matrix A \in \mathbb{R}^{n \times d} one row at a time. It performs O(d\ell) operations per row and maintains a sketch matrix B \in \mathbb{R}^{\ell \times d} such that for any k < \ell, \|A^TA - B^TB \|_2 \leq \|A - A_k\|_F^2 / (\ell-k) {\;and\;} \|A - \pi_{B_k}(A)\|_F^2 \leq (1 + \frac{k}{\ell-k}) \|A-A_k\|_F^2. Here, A_k stands for the minimizer of \|A - A_k\|_F over all rank k matrices (similarly for B_k) and \pi_{B_k}(A) is the rank k matrix resulting from projecting A on the row span of B_k. We show that both of these bounds are the best possible for the space allowed. The summary is mergeable and hence trivially parallelizable. Moreover, FrequentDirections outperforms exemplar implementations of existing streaming algorithms in the space-error tradeoff. This paper combines, simplifies, and extends the results of Liberty [Proceedings of the 1...

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-55 of 55 references · Page 1 of 1

CITED BY

Showing 1-100 of 179 citing papers · Page 1 of 2

12
Next