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

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

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

(20)

• Distances between random orthogonal matrices and independent normals
• scientific article; zbMATH DE number 7049740 (Why is no real title available?)
• Querying a Matrix Through Matrix-Vector Products.
• Improved practical matrix sketching with guarantees
• Randomized numerical linear algebra: Foundations and algorithms
• Structural results on matching estimation with applications to streaming
• Tight bounds for sketching the operator norm, Schatten norms, and subspace embeddings
• Frequent directions: simple and deterministic matrix sketching
• On approximating matrix norms in data streams
• Sketching and embedding are equivalent for norms
• Zero-one rounding of singular vectors
• Optimal estimation of Schatten norms of a rectangular matrix
• Smoothness of Schatten norms and sliding-window matrix streams
• Embeddings of Schatten norms with applications to data streams
• Monte Carlo estimators for the Schatten \(p\)-norm of symmetric positive semidefinite matrices
• Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
• Optimal eigenvalue approximation via sketching
• High probability frequency moment sketches
• On sketching the \(q\) to \(p\) norms
• Fast estimation of \(\mathrm{tr}(f(A))\) via stochastic Lanczos quadrature

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)