# On Approximating Functions of the Singular Values in a Stream

arXiv: https://arxiv.org/abs/1604.08679 · HTML: https://mlsanity.com/paper/1604.08679/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Apr 2016.

## Built on by (most cited first, 3 of 3)

- [Low-Rank Approximation with 1/ε1/3 Matrix-Vector Products](https://mlsanity.com/paper/2202.05120/) (2022)
- [Turnstile ℓp leverage score sampling with applications](https://mlsanity.com/paper/2406.00339/) (2024)
- [Krylov Methods are (nearly) Optimal for Low-Rank Approximation](https://mlsanity.com/paper/2304.03191/) (2023)

## Abstract (arXiv)

For any real number p > 0, we nearly completely characterize the space complexity of estimating |A|pp = sumi=1n σip for n × n matrices A in which each row and each column has O(1) non-zero entries and whose entries are presented one at a time in a data stream model. Here the σi are the singular values of A, and when p ≥ 1, |A|pp is the p-th power of the Schatten p-norm. We show that when p is not an even integer, to obtain a (1+ε)-approximation to |A|pp with constant probability, any 1-pass algorithm requires n1-g(ε) bits of space, where g(ε) rightarrow 0 as ε rightarrow 0 and ε > 0 is a constant independent of n. However, when p is an even integer, we give an upper bound of n1-2/p textrmpoly(ε-1log n) bits of space, which holds even in the turnstile data stream model. The latter is optimal up to textrmpoly(ε-1 log n) factors. Our results considerably strengthen lower bounds in previous work for arbitrary (not necessarily sparse) matrices A: the previous best lower bound was Omega(log n) for p∈ (0,1), Omega(n1/p-1/2/log n) for p∈ [1,2) and Omega(n1-2/p) for p∈ (2,∞). We note for p ∈ (2, ∞), while our lower bound for even integers is the same, for other p in this range our lower bound is n1-g(ε), which is considerably stronger than the previous n1-2/p for small enough constant ε > 0. We obtain similar near-linear lower bounds for Ky-Fan norms, SVD entropy, eigenvalue shrinkers, and M-estimators, many of which could have been solvable in logarithmic space prior to our work.