2026-07-23T18:19:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9419 2024-03-06T10:44:21Z ddc:004 open_access

On Sketching the q to p Norms Krishnan, Aditya Mohanty, Sidhanth Woodruff, David P. Dimensionality Reduction Norms Sketching Streaming We initiate the study of data dimensionality reduction, or sketching, for the q -> p norms. Given an n x d matrix A, the q -> p norm, denoted |A |_{q -> p} = sup_{x in R^d \ 0} |Ax |_p / |x |_q, is a natural generalization of several matrix and vector norms studied in the data stream and sketching models, with applications to datamining, hardness of approximation, and oblivious routing. We say a distribution S on random matrices L in R^{nd} - > R^k is a (k,alpha)-sketching family if from L(A), one can approximate |A |_{q -> p} up to a factor alpha with constant probability. We provide upper and lower bounds on the sketching dimension k for every p, q in [1, infty], and in a number of cases our bounds are tight. While we mostly focus on constant alpha, we also consider large approximation factors alpha, as well as other variants of the problem such as when A has low rank. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aditya Krishnan and Sidhanth Mohanty and David P. Woodruff 2018 Is Part Of LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2018.15 urn:nbn:de:0030-drops-94192 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.15 eng https://creativecommons.org/licenses/by/3.0/legalcode