On sketching the q to p norms

DOI10.4230/LIPICS.APPROX-RANDOM.2018.15MaRDI QIDQ5009507FDOQ5009507

Authors: Aditya Krishnan, Sidhanth Mohanty, David P. Woodruff 

Publication date: 4 August 2021

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

Recommendations

• On sketching matrix norms and the top singular vector
• On approximating matrix norms in data streams
• Embeddings of Schatten norms with applications to data streams
• Tight bounds for sketching the operator norm, Schatten norms, and subspace embeddings
• On the exact space complexity of sketching and streaming small norms

zbMATH Keywords

dimensionality reductionsketchingnormsstreaming

Mathematics Subject Classification ID

Randomized algorithms (68W20) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites Work

• Title not available (Why is that?)
• Limitations on quantum dimensionality reduction
• Optimal approximations of the frequency moments of data streams
• On the exact space complexity of sketching and streaming small norms
• Fast moment estimation in data streams in optimal space
• The best constants in the Khintchine inequality
• Title not available (Why is that?)
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• The positive semidefinite Grothendieck problem with rank constraint
• Tight hardness of the non-commutative Grothendieck problem
• Proceedings of the IEEE international symposium on information theory, ISIT 2012, Cambridge, MA, USA, July 1--6, 2012
• The Data Stream Space Complexity of Cascaded Norms
• Eigenvalues of a matrix in the streaming model
• Sketching and embedding are equivalent for norms
• Hypercontractivity, sum-of-squares proofs, and their applications
• The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into \(\ell_1\)
• Streaming algorithms via precision sampling
• Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
• Spectrum estimation from samples
• Tight bounds for sketching the operator norm, Schatten norms, and subspace embeddings
• On approximating functions of the singular values in a stream
• On sketching matrix norms and the top singular vector
• Approximate near neighbors for general symmetric norms
• Tight bounds for learning a mixture of two Gaussians (extended abstract)
• Streaming symmetric norms via measure concentration
• Embeddings of Schatten norms with applications to data streams
• A Tight Lower Bound for High Frequency Moment Estimation with Small Error
• Lower bounds for edit distance and product metrics via Poincaré-type inequalities
• Efficient Rounding for the Noncommutative Grothendieck Inequality
• Tight lower bound for linear sketches of moments

Cited In (3)

• Tight bounds for sketching the operator norm, Schatten norms, and subspace embeddings
• On sketching matrix norms and the top singular vector
• Embeddings of Schatten norms with applications to data streams

This page was built for publication: On sketching the \(q\) to \(p\) norms

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