Braverman, Vladimir ;
Roytman, Alan ;
Vorsanger, Gregory
Approximating Subadditive Hadamard Functions on Implicit Matrices
Abstract
An important challenge in the streaming model is to maintain smallspace 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:125:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770187},
ISSN = {18688969},
year = {2016},
volume = {60},
editor = {Klaus Jansen and Claire Mathieu and Jos{\'e} D. P. Rolim and Chris Umans},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6648},
URN = {urn:nbn:de:0030drops66483},
doi = {10.4230/LIPIcs.APPROXRANDOM.2016.25},
annote = {Keywords: Streaming Algorithms, Measuring Independence, Hadamard Functions, Implicit Matrices}
}
06.09.2016
Keywords: 

Streaming Algorithms, Measuring Independence, Hadamard Functions, Implicit Matrices 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Issue date: 

2016 
Date of publication: 

06.09.2016 