On Approximating Matrix Norms in Data Streams
From MaRDI portal
Publication:5244397
DOI10.1137/17M1152255zbMath1493.68400WikidataQ126791665 ScholiaQ126791665MaRDI QIDQ5244397
Huy L. Nguyen, Yi Li, David P. Woodruff
Publication date: 21 November 2019
Published in: SIAM Journal on Computing (Search for Journal in Brave)
approximation algorithmnumerical linear algebramatrix normSchatten normstreaming algorithmsketching algorithm
Numerical computation of matrix norms, conditioning, scaling (65F35) Approximation algorithms (68W25) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)
Related Items (2)
Monte Carlo estimators for the Schatten \(p\)-norm of symmetric positive semidefinite matrices ⋮ Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An information statistics approach to data stream and communication complexity
- Spectral norm of products of random and deterministic matrices
- Probabilistic counting algorithms for data base applications
- Approximate distributions of order statistics. With applications to nonparametric statistics
- The space complexity of approximating the frequency moments
- Spectrum estimation from samples
- Adaptive estimation of a quadratic functional by model selection.
- Nonparametric goodness-of-fit testing under Gaussian models
- Rate of convergence in probability to the Marchenko-Pastur law
- Finding frequent items in data streams
- The Littlewood-Offord problem and invertibility of random matrices
- Exact matrix completion via convex optimization
- A Tight Lower Bound for High Frequency Moment Estimation with Small Error
- Sketching and Embedding are Equivalent for Norms
- An Optimal Algorithm for Large Frequency Moments Using O(n^(1-2/k)) Bits
- Periodicity and Cyclic Shifts via Linear Sketches
- Randomized Algorithms for Matrices and Data
- Low-Rank Approximation and Regression in Input Sparsity Time
- Taylor Polynomial Estimator for Estimating Frequency Moments
- Sublinear Estimation of Weighted Matchings in Dynamic Data Streams
- Stable distributions, pseudorandom generators, embeddings, and data stream computation
- Exponential separation of quantum and classical one-way communication complexity
- Optimal approximations of the frequency moments of data streams
- Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND
- On Estimating Maximum Matching Size in Graph Streams
- An improved data stream summary: the count-min sketch and its applications
- The Minimum in the Gamma Function
- Fully homomorphic encryption using ideal lattices
- Turnstile streaming algorithms might as well be linear sketches
- Optimal Shrinkage of Singular Values
- Tight Lower Bound for Linear Sketches of Moments
- Fast moment estimation in data streams in optimal space
- Sketching Information Divergences
- Graph Connectivities, Network Coding, and Expander Graphs
- Streaming Algorithms via Precision Sampling
- Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
- Eigenvalues of a matrix in the streaming model
- Finding the Largest Low-Rank Clusters With Ky Fan $2$-$k$-Norm and $\ell_1$-Norm
- Information Theory and Statistics: A Tutorial
- On sum of powers of the Laplacian eigenvalues of graphs
This page was built for publication: On Approximating Matrix Norms in Data Streams