On sketching matrix norms and the top singular vector

DOI10.1137/1.9781611973402.114MaRDI QIDQ5384076zbMATH OpenOpenAlexFDO

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

Publication date 20 June 2019

Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/25b5bff249f9e130c9e0c38e66c355587e05956c

Mathematics Subject Classification ID

Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Approximation algorithms (68W25)

Recommendations

• On approximating matrix norms in data streams
• On sketching the \(q\) to \(p\) norms
• Embeddings of Schatten norms with applications to data streams
• Tight bounds for sketching the operator norm, Schatten norms, and subspace embeddings
• Numerical linear algebra in the streaming model

Cited in

(24)

• Structural results on matching estimation with applications to streaming
• Smoothness of Schatten norms and sliding-window matrix streams
• Monte Carlo estimators for the Schatten \(p\)-norm of symmetric positive semidefinite matrices
• Frequent directions: simple and deterministic matrix sketching
• Zero-one rounding of singular vectors
• Improved practical matrix sketching with guarantees
• Sketching and embedding are equivalent for norms
• Fast estimation of \(\mathrm{tr}(f(A))\) via stochastic Lanczos quadrature
• scientific article; zbMATH DE number 7049740 (Why is no real title available?)
• Tight bounds for sketching the operator norm, Schatten norms, and subspace embeddings
• Distances between random orthogonal matrices and independent normals
• Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
• High probability frequency moment sketches
• 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
• Randomized numerical linear algebra: Foundations and algorithms
• Optimal eigenvalue approximation via sketching
• Optimal estimation of Schatten norms of a rectangular matrix
• On the variance of Schatten p-norm estimation with Gaussian sketching matrices
• Improved bounds for randomized Schatten norm estimation of numerically low-rank matrices
• Near neighbor search via efficient average distortion embeddings
• Matrix-free stochastic calculation of operator norms without using adjoints

This page was built for publication: On sketching matrix norms and the top singular vector

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