Eigenvalues of a matrix in the streaming model
Lists
Only you see this
Abstract
We study the question of estimating the eigenvalues of a matrix in the streaming model, addressing a question posed in [Mut05]. We show that the eigenvalue “heavy hitters” of a matrix can be computed in a single pass. In particular, we show that the φ-heavy hitters (in the ℓ or ℓ2 norms) can be estimated in space proportional to . Such a dependence on is optimal. We also show how the same techniques may give an estimate of the residual error tail of a rank-k approximation of the matrix (in the Frobenius norm), in space proportional to k2. All our algorithms are linear and hence can support arbitrary updates to the matrix in the stream. In fact, what we show can be seen as a form of a bi-linear dimensionality reduction: if we multiply an input matrix with projection matrices on both sides, the resulting matrix preserves the top eigenvalues and the residual Frobenius norm.
BibTeX
@inproceedings{andoni2013eigenvalues,
author = {Alexandr Andoni and Huy L. Nguyen},
title = {{Eigenvalues of a matrix in the streaming model}},
booktitle = {SODA},
year = {2013},
doi = {10.1137/1.9781611973105.124},
}Loading related content...