On approximating functions of the singular values in a stream

DOI10.1145/2897518.2897581MaRDI QIDQ5361874zbMATH OpenOpenAlexFDO

Authors Yi Li, David P. Woodruff

Publication date 29 September 2017

Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.08679

zbMATH Keywords

algorithmscomplexitydata streamsmatrix normsSchatten norms

Mathematics Subject Classification ID

Numerical computation of matrix norms, conditioning, scaling (65F35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Abstract: For any real number $p>0$, we nearly completely characterize the space complexity of estimating $|A{|}_p^p=su{m}_{i=1}^{n}sigm{a}_i^p$ for $nimesn$ 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 $sigm{a}_i$ are the singular values of $A$, and when $pgeq1$, $|A{|}_p^p$ is the $p$-th power of the Schatten $p$-norm. We show that when $p$ is not an even integer, to obtain a $(1+epsilon)$-approximation to $|A{|}_p^p$ with constant probability, any $1$-pass algorithm requires $n^{1-g(epsilon)}$ bits of space, where $g(epsilon)ightarrow0$ as $epsilonightarrow0$ and $epsilon>0$ is a constant independent of $n$. However, when $p$ is an even integer, we give an upper bound of $n^{1-2/p}extrmpoly(epsilo{n}^{-1}logn)$ bits of space, which holds even in the turnstile data stream model. The latter is optimal up to $extrmpoly(epsilo{n}^{-1}logn)$ factors. Our results considerably strengthen lower bounds in previous work for arbitrary (not necessarily sparse) matrices $A$: the previous best lower bound was $Omega(logn)$ for $pin(0,1)$, $Omega(n^{1/p-1/2}/logn)$ for $pin[1,2)$ and $Omega(n^{1-2/p})$ for $pin(2,infty)$. We note for $pin(2,infty)$, while our lower bound for even integers is the same, for other $p$ in this range our lower bound is $n^{1-g(epsilon)}$, which is considerably stronger than the previous $n^{1-2/p}$ for small enough constant $epsilon>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.

Recommendations

• On approximating matrix norms in data streams
• Embeddings of Schatten norms with applications to data streams
• Numerical linear algebra in the streaming model
• On the exact space complexity of sketching and streaming small norms
• Eigenvalues of a matrix in the streaming model

Cited in

(15)

• Structural results on matching estimation with applications to streaming
• Smoothness of Schatten norms and sliding-window matrix streams
• scientific article; zbMATH DE number 7049740 (Why is no real title available?)
• Approximating subadditive Hadamard functions on implicit matrices
• Streaming symmetric norms via measure concentration
• Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
• On sketching the \(q\) to \(p\) norms
• Querying a Matrix Through Matrix-Vector Products.
• Embeddings of Schatten norms with applications to data streams
• On approximating matrix norms in data streams
• On the exact space complexity of sketching and streaming small norms
• Eigenvalues of a matrix in the streaming model
• (Noisy) gap cycle counting strikes back: random order streaming lower bounds for connected components and beyond
• Near neighbor search via efficient average distortion embeddings
• Almost optimal superconstant-pass streaming lower bounds for reachability

This page was built for publication: On approximating functions of the singular values in a stream

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5361874)