Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.15
URN: urn:nbn:de:0030-drops-94192
URL: https://drops.dagstuhl.de/opus/volltexte/2018/9419/
Krishnan, Aditya ; Mohanty, Sidhanth ; Woodruff, David P.
On Sketching the q to p Norms
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{krishnan_et_al:LIPIcs:2018:9419,
author = {Aditya Krishnan and Sidhanth Mohanty and David P. Woodruff},
title = {{On Sketching the q to p Norms}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
pages = {15:1--15:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-085-9},
ISSN = {1868-8969},
year = {2018},
volume = {116},
editor = {Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9419},
URN = {urn:nbn:de:0030-drops-94192},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.15},
annote = {Keywords: Dimensionality Reduction, Norms, Sketching, Streaming}
}
| Keywords: | Dimensionality Reduction, Norms, Sketching, Streaming | |
| Seminar: | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018) | |
| Issue date: | 2018 | |
| Date of publication: | 13.08.2018 |
