Can I read Simple and Deterministic Matrix Sketching on EtoBox?

Simple and Deterministic Matrix Sketching by Edo Liberty is a scholarly article available to read on EtoBox.

What is Simple and Deterministic Matrix Sketching about?

A sketch of a matrix A is another matrix B which is significantly smaller than A, but still approximates it well. Finding such sketches efficiently is an important building block in modern algorithms for approximating, for example, the PCA of massive matrices. This task is made more challenging in the streaming model, where each row of the input matrix can be processed only once and storage is severely limited. In this paper, we adapt a well known streaming algorithm for approximating item frequencies to the matrix sketching setting. The algorithm receives n rows of a large matrix A ∈ R n×m one after the other, in a streaming fashion. It maintains a sketch B ∈ R l×m containing only l ≪ n rows but still guarantees that f /l . This algorithm's error decays proportionally to 1/l using O(ml) space. In comparison, random-projection, hashing or sampling based algorithms produce convergence bounds proportional to 1/ √ l. Sketch updates per row in A require amortized O(ml) operations and the algorithm is perfectly parallelizable. Our experiments corroborate the algorithm's scalability and improved convergence rate. The presented algorithm also stands out in that it is deterministic, simple

Author

Edo Liberty

Publisher

ACM

Published

2013

Language

EN