Low Rank Approximation Lower Bounds in Row-Update Streams
Authors: David Woodruff
NeurIPS 2014 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 R 2 F (1+ϵ) A Ak 2 F , where Ak 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. |
| Researcher Affiliation | Industry | David P. Woodruff IBM Research Almaden dpwoodru@us.ibm.com |
| Pseudocode | No | The paper contains mathematical proofs and derivations but no structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper is theoretical and does not provide any information about releasing or linking to source code. |
| Open Datasets | No | The paper is theoretical and does not use or mention any datasets for training or public availability. |
| Dataset Splits | No | The paper is theoretical and does not discuss dataset splits for validation. |
| Hardware Specification | No | The paper is theoretical and does not conduct experiments, therefore no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not list any software dependencies with specific version numbers. |
| Experiment Setup | No | The paper is theoretical and does not conduct experiments, therefore no experimental setup details are provided. |