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.2016.25
URN: urn:nbn:de:0030-drops-66483
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6648/
Go to the corresponding LIPIcs Volume Portal

Braverman, Vladimir ; Roytman, Alan ; Vorsanger, Gregory

Approximating Subadditive Hadamard Functions on Implicit Matrices

pdf-format:
LIPIcs-APPROX-RANDOM-2016-25.pdf (0.6 MB)

Abstract

An important challenge in the streaming model is to maintain small-space approximations of entrywise functions performed on a matrix that is generated by the outer product of two vectors given as a stream. In other works, streams typically define matrices in a standard way via a sequence of updates, as in the
work of Woodruff [22] and others. We describe the matrix formed by the outer product, and other matrices that do not fall into this category, as implicit matrices. As such, we consider the general problem of computing over such implicit matrices with Hadamard functions, which are functions applied entrywise on a matrix. In this paper, we apply this generalization to provide new techniques for identifying independence between two data streams. The previous state of the art algorithm of Braverman and Ostrovsky [9] gave a (1 +- epsilon)-approximation for the L_1 distance between the joint and product of the marginal distributions, using space O(log^{1024}(nm) epsilon^{-1024}), where m is the length of the stream and n denotes the size of the universe from which stream elements are drawn. Our general techniques include the L_1 distance as a special case, and we give an improved space bound of O(log^{12}(n) log^{2}({nm}/epsilon) epsilon^{-7}).

BibTeX - Entry

@InProceedings{braverman_et_al:LIPIcs:2016:6648,
  author =	{Vladimir Braverman and Alan Roytman and Gregory Vorsanger},
  title =	{{Approximating Subadditive Hadamard Functions on Implicit Matrices}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{25:1--25:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Klaus Jansen and Claire Mathieu and Jos{\'e} D. P. Rolim and Chris Umans},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6648},
  URN =		{urn:nbn:de:0030-drops-66483},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.25},
  annote =	{Keywords: Streaming Algorithms, Measuring Independence, Hadamard Functions, Implicit Matrices}
}

Keywords: Streaming Algorithms, Measuring Independence, Hadamard Functions, Implicit Matrices
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Issue Date: 2016
Date of publication: 06.09.2016

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