Approximating subadditive Hadamard functions on implicit matrices

DOI10.4230/LIPICS.APPROX-RANDOM.2016.25zbMATH Open1398.68662arXiv1511.00838OpenAlexW2963476071MaRDI QIDQ4636458FDOQ4636458

Authors: Vladimir Braverman, Alan Roytman, Gregory Vorsanger 

Publication date: 19 April 2018

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 (2014) 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 vectors in the streaming model. The previous state of the art algorithm of Braverman and Ostrovsky (2010) gave a $(1pmepsilon)$-approximation for the $L_1$ distance between the product and joint distributions, using space $O(lo{g}^{1024}(nm)epsilo{n}^{-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(lo{g}^{12}(n)lo{g}^2(nmoverepsilon)epsilo{n}^{-7})$.

Full work available at URL: https://arxiv.org/abs/1511.00838

Recommendations

• Measuring independence of datasets
• AMS without 4-wise independence on product domains
• Numerical linear algebra in the streaming model
• On approximating functions of the singular values in a stream
• Adaptive Matrix Vector Product

zbMATH Keywords

streaming algorithmsHadamard functionsimplicit matricesmeasuring independence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Cited In (2)

• Improved matrix algorithms via the subsampled randomized Hadamard transform
• AMS without 4-wise independence on product domains

This page was built for publication: Approximating subadditive Hadamard functions on implicit matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4636458)