2013 SimpleandDeterministicMatrixSke

• (Liberty, 2013) ⇒ Edo Liberty. (2013). “Simple and Deterministic Matrix Sketching.” In: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ISBN:978-1-4503-2174-7 doi:10.1145/2487575.2487623

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222013%22+Simple+and+Deterministic+Matrix+Sketching
• http://dl.acm.org/citation.cfm?id=2487575.2487623&preflayout=flat#citedby

Quotes

Author Keywords

• Singular value decomposition; sketching; streaming

Abstract

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 only be processed 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 ε ℜ ^{n x m} one after the other in a streaming fashion. It maintains a sketch B ℜ ^{l x m} containing only l << n rows but still guarantees that A^TA B^TB. More accurately, ∀ x|| x,|| =1 0≤|| Ax|| ² -|| Bx|| ² ≤ 2|| A|| _ f ² l Or B^TB prec A^TA and|| A^TA - [[B^TB]]|| ≤ 2|| A|| f ² l.

This gives a streaming algorithm whose error decays proportional to 1 / l using O (ml) space. For 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 to implement and elementary to prove.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2013 SimpleandDeterministicMatrixSke	Edo Liberty			Simple and Deterministic Matrix Sketching				10.1145/2487575.2487623		2013