Low Rank Approximation Lower Bounds in Row-Update Streams

David P. WoodruffNeurIPS 2014 · OpenReview

This paper, authored by David P. Woodruff, provides a definitive answer to a fundamental question in streaming numerical linear algebra: How much memory is strictly necessary to approximate a large matrix?

By establishing a rigorous theoretical "lower bound," Woodruff proves that the current state-of-the-art algorithms are essentially as efficient as they can possibly be, leaving little room for further optimization in terms of space complexity.

Executive Summary

This paper proves a tight lower bound of $\Omega(dk/\epsilon)$ bits of space for any streaming algorithm performing low-rank matrix approximation in the row-update model. It demonstrates that existing deterministic algorithms are nearly optimal, and that even allowing for randomization or a small probability of error cannot significantly reduce the memory required.

The Problem: Matrix Approximation in a Stream

In the era of "Big Data," we often deal with matrices so massive they cannot fit into a computer's RAM. To handle this, researchers use streaming algorithms, which process data in a single pass.

There are two main ways data arrives in a stream:

  1. Entry-update: Elements arrive one by one ($A_{i,j}$).
  2. Row-update: Entire rows arrive one at a time. This is common in practice, where each row represents a single entity (like a user's feature vector).

The goal is Low-Rank Approximation: given an $n \times d$ matrix $A$, find a much smaller $k \times d$ matrix $R$ that captures the "essence" of $A$. Specifically, we want the approximation error to be within a $(1+\epsilon)$ factor of the best possible rank-$k$ approximation (the Singular Value Decomposition, or SVD).

Previous work (by Liberty, Ghashami, and Phillips) provided algorithms using $O(dk/\epsilon)$ words of space. The open question was: Can we do better? Is there a clever randomized trick that uses significantly less memory?

Methodology: The Communication Complexity Approach

As a theoretical paper, this work uses Communication Complexity to prove its results rather than empirical datasets.

The author employs a classic "reduction" from a problem called the Index Problem. In this theoretical game:

  • Alice has a long bitstring $x$.
  • Bob has an index $i$ and wants to know the value of the $i$-th bit of Alice's string.
  • Alice can only send one message to Bob.

It is a known fundamental law of information theory that Alice must send a message roughly as long as her entire string for Bob to succeed.

Woodruff translates this into the matrix world: Alice constructs a matrix block based on her string, and Bob constructs a matrix block based on his index.

Matrix construction for the communication complexity reduction between Alice and Bob.

If a streaming algorithm existed that used very little space, Alice could simply process her rows and send the "state" of that algorithm to Bob. If Bob could then use that state to solve the Index Problem, it would contradict the known limits of communication. The mathematical heavy lifting of the paper is showing that a good low-rank approximation $R$ actually contains enough information to solve the Index Problem.

Key Insights and Ideas

  • The $1/\epsilon$ Factor is Mandatory: A simple lower bound of $\Omega(dk)$ is easy to show (you need to store the dimensions of the subspace). The breakthrough here is proving that the $1/\epsilon$ factor—which makes the space requirement explode as you demand higher precision—is a fundamental requirement of the problem, not a weakness of current algorithms.
  • Randomization Doesn't Help (Much): Often in computer science, allowing an algorithm to flip coins (randomization) or fail a fraction of the time allows for massive space savings. Woodruff shows that for this specific problem, the savings are negligible.
  • Information Leakage in Projections: The proof relies on the insight that even if an algorithm only outputs a projection matrix (the "directions" of the rows), that projection necessarily "leaks" enough information about the original rows to reconstruct specific bits of the input.

Key Results

  • Theorem 1: Any streaming algorithm (even randomized ones) that outputs a $(1+\epsilon)$ low-rank approximation in the row-update model must use $\Omega(kd/\epsilon)$ bits of space.
  • Optimality: This result matches the existing upper bounds (within the "word size" of the computer), proving that the algorithms developed by Liberty and others are optimal.
  • Precision Matters: The result shows that if you want to double your precision (halve $\epsilon$), you must roughly double your memory usage.

Limitations and Future Work

  • Single Pass vs. Multi-Pass: This lower bound applies specifically to single-pass streaming. The author notes that obtaining similar lower bounds for multi-pass algorithms is much more challenging and remains an open goal.
  • Word Size vs. Bits: There is a tiny technical gap between "bits" and "words" (a factor of $\log(nd)$). While the bound is "tight" for all practical purposes, theoretical purists might look to close this final logarithmic gap.
  • Distributed Computing: The author suggests these techniques could be useful for showing the optimality of communication protocols in distributed low-rank approximation, a growing field in cloud computing.

Summary updated

Abstract

We study low-rank approximation in the streaming model in which the rows of an $n \times 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 \times d$ matrix $R$ so that $\|A-AR^{\dagger}R\|_F^2 \leq (1+\eps)\|A-A_k\|_F^2$, 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/\epsilon)$ words of space. A natural question is if smaller space is possible. We give an almost matching lower bound of $\Omega(dk/\epsilon)$ 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 $\Omega(dk)$ space lower bound.
BibTeX
@inproceedings{woodruff2014low,
  author = {David P. Woodruff},
  title = {{Low Rank Approximation Lower Bounds in Row-Update Streams}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
  url = {https://openreview.net/forum?id=SkEFxv-OZB},
}
Figure