License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2013.466
URN: urn:nbn:de:0030-drops-39577
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/3957/
Go to the corresponding LIPIcs Volume Portal

Kutzkov, Konstantin

Deterministic algorithms for skewed matrix products

pdf-format:
45.pdf (0.6 MB)

Abstract

Recently, Pagh presented a randomized approximation algorithm for the multiplication of real-valued matrices building upon work for detecting the most frequent items in data streams. We continue this line of research and present new deterministic matrix multiplication algorithms.

Motivated by applications in data mining, we first consider the case of real-valued, nonnegative n-by-n input matrices A and B, and show how to obtain a deterministic approximation of the weights of individual entries, as well as the entrywise p-norm, of the product AB. The algorithm is simple, space efficient and runs in one pass over the input matrices. For a user defined b \in (0, n^2) the algorithm runs in time O(nb + n Sort(n)) and space O(n + b) and returns an approximation of the entries of AB within an additive factor of ||AB||_{E1}/b, where ||C||_{E1} = sum_{i, j} |C_{ij}| is the entrywise 1-norm of a matrix C and Sort(n) is the time required to sort n real numbers in linear space. Building upon a result by Berinde et al. we show that for skewed matrix products (a common situation in many real-life applications) the algorithm is more efficient and achieves better approximation guarantees than previously known randomized algorithms.

When the input matrices are not restricted to nonnegative entries, we present a new deterministic group testing algorithm detecting nonzero entries in the matrix product with large absolute value. The algorithm is clearly outperformed by randomized matrix multiplication algorithms, but as a byproduct we obtain the first O(n^{2 + epsilon})-time deterministic algorithm for matrix products with O(sqrt(n)) nonzero entries.

BibTeX - Entry

@InProceedings{kutzkov:LIPIcs:2013:3957,
  author =	{Konstantin Kutzkov},
  title =	{{Deterministic algorithms for skewed matrix products}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{466--477},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Natacha Portier and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/3957},
  URN =		{urn:nbn:de:0030-drops-39577},
  doi =		{10.4230/LIPIcs.STACS.2013.466},
  annote =	{Keywords: approximate deterministic memory-efficient matrix multiplication}
}

Keywords: approximate deterministic memory-efficient matrix multiplication
Collection: 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Issue Date: 2013
Date of publication: 26.02.2013

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