# On approximating functions of the singular values in a stream

@article{Li2016OnAF, title={On approximating functions of the singular values in a stream}, author={Yi Li and David P. Woodruff}, journal={Proceedings of the forty-eighth annual ACM symposium on Theory of Computing}, year={2016} }

For any real number p > 0, we nearly completely characterize the space complexity of estimating ||A||pp = ∑i=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… Expand

#### 27 Citations

Embeddings of Schatten Norms with Applications to Data Streams

- Mathematics, Computer Science
- ICALP
- 2017

The upper bounds of the Schatten 1-norm are oblivious, meaning that R and S do not depend on the A_i, while the lower bounds hold even if R andS depend onThe A-i, for every p, q >= 1. Expand

Spectrum Estimation from a Few Entries

- Mathematics, Computer Science
- J. Mach. Learn. Res.
- 2019

This work proposes a novel unbiased estimator based on counting small structures in a graph and provides guarantees that match its empirical performance and significantly improves upon a competing approach of using matrix completion methods. Expand

Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings

- Mathematics, Computer Science
- APPROX-RANDOM
- 2016

For sketching the operator norm up to a factor of alpha, where alpha - 1 = \Omega(1), a tight k = Omega(n^2/alpha^4) bound is obtained, matching the upper bound of Andoni and Nguyen (SODA, 2013) and improving the previous lower bound. Expand

Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness

- Mathematics, Computer Science
- ITCS
- 2018

It is shown that precisely computing all effective resistances in a graph in less than matrix multiplication time is likely difficult, barring a major algorithmic breakthrough, and it is proved that achieving milder $\epsilon$ dependencies in algorithms would imply faster than Matrix multiplication time triangle detection for general graphs. Expand

Matrix Norm Estimation from a Few Entries

- Computer Science, Mathematics
- NIPS
- 2017

A novel unbiased estimator based on counting small structures in a graph and provide guarantees that match its empirical performances is introduced and shows that Schatten norms can be recovered accurately from strictly smaller number of samples compared to what is needed to recover the underlying low-rank matrix. Expand

Schatten Norms in Matrix Streams: Hello Sparsity, Goodbye Dimension

- Computer Science, Mathematics
- ICML
- 2020

The first algorithms whose space requirement is independent of the matrix dimension are provided, assuming the matrix is doubly-sparse and presented in row-order, and extensions of the primary technique are shown, including a trade-off between space requirements and number of passes. Expand

Querying a Matrix through Matrix-Vector Products

- ACM Transactions on Algorithms
- 2021

We consider algorithms with access to an unknown matrix M ε F n×d via matrix-vector products, namely, the algorithm chooses vectors v1, ⃛ , vq, and observes Mv1, ⃛ , Mvq. Here the vi can be… Expand

Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order

- Computer Science, Mathematics
- ICML
- 2018

A number of aspects of estimating matrix norms in a stream that have not previously been considered are considered, and a near-complete characterization of the memory required of row-order algorithms for estimating Schatten-norms of sparse matrices is obtained. Expand

Multi-resolution Hashing for Fast Pairwise Summations

- Computer Science, Physics
- 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)
- 2019

This work provides a general framework for designing data structures through hashing that reaches far beyond what previous techniques allowed, and leads to data structures with sub-linear query time that significantly improve upon random sampling and can be used for Kernel Density, Partition Function Estimation and sampling. Expand

Sublinear Time Eigenvalue Approximation via Random Sampling

- Computer Science, Mathematics
- ArXiv
- 2021

This work presents a simple sublinear time algorithm that approximates all eigenvalues of A up to additive error ± n using those of a randomly sampled Õ( 1 4)× Õ ( 1 4 ) principal submatrix. Expand

#### References

SHOWING 1-10 OF 71 REFERENCES

Streaming Space Complexity of Nearly All Functions of One Variable on Frequency Vectors

- Mathematics, Computer Science
- PODS
- 2016

For nearly all functions of one variable, the open question of which functions on a stream can be approximated in sublinear, and especially sub-polynomial or poly-logarithmic, space is answered. Expand

A Tight Lower Bound for High Frequency Moment Estimation with Small Error

- Mathematics, Computer Science
- APPROX-RANDOM
- 2013

This lower bound matches the space complexity of an upper bound of Ganguly for any e 2 and e ≥ 1/n 1/p and is optimal for e < 1/log O(1) n. Expand

On Sketching Matrix Norms and the Top Singular Vector

- Computer Science, Mathematics
- SODA
- 2014

This paper studies the problem of sketching matrix norms, and gives separations in the sketching complexity of Schatten-p norms with the corresponding vector p-norms, and rule out a table lookup nearest-neighbor search for p = 1, making progress on a question of Andoni. Expand

A Lower Bound for Estimating High Moments of a Data Stream

- Computer Science, Mathematics
- ArXiv
- 2012

An improved lower bound for the Fp estimation problem in a data stream setting for p>2 is shown and an Omega(p^2 n-1-2/p} \epsilon^{-2}/\log (n) bits space bound is shown. Expand

Zero-one frequency laws

- Mathematics, Computer Science
- STOC '10
- 2010

This paper provides the first zero-one law in the streaming model for a wide class of functions, and shows a lower bound that requires greater then polylog memory for computing an approximation to Σi∈ [n] G(mi) by any one-pass streaming algorithm. Expand

An Optimal Algorithm for Large Frequency Moments Using O(n^(1-2/k)) Bits

- Mathematics, Computer Science
- APPROX-RANDOM
- 2014

This paper provides an upper bound on the space required to find a k-th frequency moment of O(n^(1-2/k) bits that matches, up to a constant factor, the lower bound of Woodruff et. Expand

Eigenvalues of a matrix in the streaming model

- Computer Science, Mathematics
- SODA
- 2013

What is shown can be seen as a form of a bi-linear dimensionality reduction: if the authors multiply an input matrix with projection matrices on both sides, the resulting matrix preserves the top eigenvalues and the residual Frobenius norm. Expand

Improved testing of low rank matrices

- Mathematics, Computer Science
- KDD
- 2014

This work studies the problem of quickly estimating the rank or stable rank of A, the latter often providing a more robust measure of the rank, and proves an Ω(d/ε) lower bound on the number of rows that need to be read, even for adaptive algorithms. Expand

Numerical linear algebra in the streaming model

- Mathematics, Computer Science
- STOC '09
- 2009

Near-optimal space bounds are given in the streaming model for linear algebra problems that include estimation of matrix products, linear regression, low-rank approximation, and approximation of matrix rank; results for turnstile updates are proved. Expand

On Estimating Frequency Moments of Data Streams

- Mathematics, Computer Science
- APPROX-RANDOM
- 2007

The technique trades an $O(\frac{1}{\epsilon^p})$ factor in space for much more efficient processing of stream updates, and presents a stand-alone iterative estimator for F 1. Expand