Low Rank Approximation Lower Bounds in Row-Update Streams
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
, where A k is the best rank-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.
This paper investigates the lower bound of the space complexity for a specific streaming algorithm. In this streaming algorithm, the goal is to find a matrix R such that the matrix A can be approximated by A*R^\dag*R, where R^\dag is the pseudo-inverse of the matrix R. Also in the streaming model the rows of the matrix A are presented at a time in an arbitrary order.The problem investigated in this paper is interesting. This paper gives a lower bound of space needed to compute the matrix R. Compared with existing work, the improvement of the space lower bound is impressive. Since the main result of this paper is the improved lower bound, it is a very theoretical paper. It is not very easy for me to follow the whole paper. Many proofs in this paper are provided in the supplementary file. I went through this paper but did not check all details of this paper. But the proof of this paper sounds good to me.In terms of quality and significance, I think this paper is above the borderline of NIPS. My only concern is that many proofs are provided in the supplementary file, which makes reading this paper not easy. The readability can be further improved. Minor comment: the proof of Lemma 6 can be revised. For example, "expanding the square" can be removed from the long equation.