About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
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.