On approximating matrix norms in data streams

DOI10.1137/17M1152255zbMATH Open1493.68400WikidataQ126791665 ScholiaQ126791665MaRDI QIDQ5244397FDOQ5244397

Authors: Yi Li, Huy L. Nguyen, David P. Woodruff 

Publication date: 21 November 2019

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Recommendations

• On approximating functions of the singular values in a stream
• Embeddings of Schatten norms with applications to data streams
• On sketching matrix norms and the top singular vector
• Numerical linear algebra in the streaming model
• On the exact space complexity of sketching and streaming small norms

zbMATH Keywords

streaming algorithmapproximation algorithmmatrix normnumerical linear algebraSchatten normsketching algorithm

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Randomized algorithms (68W20) Numerical computation of matrix norms, conditioning, scaling (65F35) Approximation algorithms (68W25)

Cites Work

• Fully homomorphic encryption using ideal lattices
• Exact matrix completion via convex optimization
• The space complexity of approximating the frequency moments
• Adaptive estimation of a quadratic functional by model selection.
• Nonparametric goodness-of-fit testing under Gaussian models
• Low-Rank Approximation and Regression in Input Sparsity Time
• Title not available (Why is that?)
• Randomized Algorithms for Matrices and Data
• Title not available (Why is that?)
• Title not available (Why is that?)
• Finding frequent items in data streams
• Exponential separation of quantum and classical one-way communication complexity
• Optimal approximations of the frequency moments of data streams
• An improved data stream summary: the count-min sketch and its applications
• On the exact space complexity of sketching and streaming small norms
• Fast moment estimation in data streams in optimal space
• Information Theory and Statistics: A Tutorial
• Approximate distributions of order statistics. With applications to nonparametric statistics
• Multivariate normal approximation using exchangeable pairs
• Title not available (Why is that?)
• Spectral norm of products of random and deterministic matrices
• The Littlewood-Offord problem and invertibility of random matrices
• Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND
• Optimal Shrinkage of Singular Values
• An information statistics approach to data stream and communication complexity
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• Rate of convergence in probability to the Marchenko-Pastur law
• On sum of powers of the Laplacian eigenvalues of graphs
• Probabilistic counting algorithms for data base applications
• Exponential separations for one-way quantum communication complexity, with applications to cryptography
• The Minimum in the Gamma Function
• Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
• Eigenvalues of a matrix in the streaming model
• Title not available (Why is that?)
• Sketching and embedding are equivalent for norms
• Sketching Information Divergences
• On the sum of powers of normalized Laplacian eigenvalues of graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Streaming algorithms via precision sampling
• An Optimal Algorithm for Large Frequency Moments Using O(n^(1-2/k)) Bits
• On Estimating Maximum Matching Size in Graph Streams
• Spectrum estimation from samples
• Sublinear estimation of weighted matchings in dynamic data streams
• Title not available (Why is that?)
• Title not available (Why is that?)
• Finding the largest low-rank clusters with Ky Fan \(2\)-\(k\)-norm and \(\ell_1\)-norm
• 1-pass relative-error \(L_p\)-sampling with applications
• Title not available (Why is that?)
• A Tight Lower Bound for High Frequency Moment Estimation with Small Error
• Graph Connectivities, Network Coding, and Expander Graphs
• Periodicity and cyclic shifts via linear sketches
• Taylor polynomial estimator for estimating frequency moments
• Turnstile streaming algorithms might as well be linear sketches
• Tight lower bound for linear sketches of moments

Cited In (10)

• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• On deterministic sketching and streaming for sparse recovery and norm estimation
• On the exact space complexity of sketching and streaming small norms
• Title not available (Why is that?)
• Smoothness of Schatten norms and sliding-window matrix streams
• An approximate \(L^p\) difference algorithm for massive data streams
• Monte Carlo estimators for the Schatten \(p\)-norm of symmetric positive semidefinite matrices
• Optimal eigenvalue approximation via sketching
• Numerical linear algebra in the streaming model
• Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems

Uses Software

• MathOverflow

This page was built for publication: On approximating matrix norms in data streams

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