On sketching the q to p norms

DOI10.4230/LIPICS.APPROX-RANDOM.2018.15MaRDI QIDQ5009507zbMATH OpenFDO

Authors Aditya Krishnan, Sidhanth Mohanty, David P. Woodruff

Publication date 4 August 2021

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

zbMATH Keywords

dimensionality reductionsketchingnormsstreaming

Mathematics Subject Classification ID

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

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

Cites work

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