Publication
NeurIPS 2014
Conference paper

Low rank approximation lower bounds in row-update streams

Abstract

We study low-rank approximation in the streaming model in which the rows of an n × d matrix A are presented one at a time in an arbitrary order. At the end of the stream, the streaming algorithm should output a k × d matrix R so that ∥A - AR<sup>†</sup>R∥<sup>2</sup><inf>F</inf> ≤ (1 + ε)∥A - A<inf>k</inf>∥<sup>2</sup><inf>F</inf>, where A<inf>k</inf> is the bestrank-k approximation to A. A deterministic streaming algorithm of Liberty (KDD, 2013), with an improved analysis of Ghashami and Phillips (SODA, 2014), provides such a streaming algorithm using O(dk/ε) words of space. A natural question is if smaller space is possible. We give an almost matching lower bound of Ω(dk/ε) bits of space, even for randomized algorithms which succeed only with constant probability. Our lower bound matches the upper bound of Ghashami and Phillips up to the word size, improving on a simple Ω(dk) space lower bound.

Date

08 Dec 2014

Publication

NeurIPS 2014

Authors

Share