On Approximating Matrix Norms in Data Streams

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

MathOverflow

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