License: 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9419/
Go to the corresponding LIPIcs Volume Portal

Krishnan, Aditya ; Mohanty, Sidhanth ; Woodruff, David P.

On Sketching the q to p Norms

pdf-format:
LIPIcs-APPROX-RANDOM-2018-15.pdf (0.6 MB)

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
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Issue Date: 2018
Date of publication: 13.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI