On sketching matrix norms and the top singular vector

DOI10.1137/1.9781611973402.114zbMATH Open1422.68305OpenAlexW4253094038MaRDI QIDQ5384076FDOQ5384076

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

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

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)

Cited In (20)

• Title not available (Why is that?)
• 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
• Optimal eigenvalue approximation via sketching
• Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
• High probability frequency moment sketches
• On sketching the \(q\) to \(p\) norms
• Fast estimation of \(\mathrm{tr}(f(A))\) via stochastic Lanczos quadrature
• Distances between random orthogonal matrices and independent normals

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)