Tight Bounds for the Subspace Sketch Problem with Applications

DOI10.1137/20M1311831OpenAlexW3191037578MaRDI QIDQ5009789

David P. Woodruff, Ruosong Wang, Yi Li

Publication date: 6 August 2021

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

Full work available at URL: https://arxiv.org/abs/1904.05543

zbMATH Keywords

sketchinglower bound\(M\)-estimatorprojective clusteringsubspace sketch

Mathematics Subject Classification ID

Local theory of Banach spaces (46B07) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science (46B85) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (1)

New subset selection algorithms for low rank approximation: offline and online

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
• Smaller coresets for \(k\)-median and \(k\)-means clustering
• Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
• On data structures and asymmetric communication complexity
• Introduction to calculus and analysis. Volume I.
• Approximation of zonoids by zonotopes
• Finding frequent items in data streams
• On Sketching Quadratic Forms
• The Fast Cauchy Transform and Faster Robust Linear Regression
• Zero-one frequency laws
• Computational Advertising: Techniques for Targeting Relevant Ads
• Quantile Regression for Large-Scale Applications
• L _p Row Sampling by Lewis Weights
• On the Construction of Binary Sequence Families With Low Correlation and Large Sizes
• Tight embedding of subspaces of 𝐿_{𝑝} in ℓ_{𝑝}ⁿ for even 𝑝
• Embedding Subspaces of L 1 into l N 1
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• Generalized Jacobi Weights, Christoffel Functions, and Jacobi Polynomials
• High-Dimensional Probability
• High Probability Frequency Moment Sketches
• Optimal Lower Bounds for Sketching Graph Cuts
• Fast moment estimation in data streams in optimal space
• A Class of Convex Bodies
• Compressed matrix multiplication
• Concentration of Measure for the Analysis of Randomized Algorithms

This page was built for publication: Tight Bounds for the Subspace Sketch Problem with Applications