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.116
URN: urn:nbn:de:0030-drops-39270
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/3927/
Go to the corresponding LIPIcs Volume Portal

Case, Adam ; Lutz, Jack H.

Mutual Dimension

pdf-format:
15.pdf (0.5 MB)

Abstract

We define the lower and upper mutual dimensions mdim(x:y) and Mdim(x:y) between any two points x and y in Euclidean space. Intuitively these are the lower and upper densities of the algorithmic information shared by x and y. We show that these quantities satisfy the main desiderata for a satisfactory measure of mutual algorithmic information. Our main theorem, the data processing inequality for mutual dimension, says that, if f : R^m -> R^n is computable and Lipschitz, then the inequalities mdim(f(x):y) <= mdim(x:y) and Mdim(f(x):y) <= Mdim(x:y) hold for all x \in R^m and y \in R^t. We use this inequality and related inequalities that we prove in like fashion to establish conditions under which various classes of computable functions on Euclidean space preserve or otherwise transform mutual dimensions between points.

BibTeX - Entry

@InProceedings{case_et_al:LIPIcs:2013:3927,
  author =	{Adam Case and Jack H. Lutz},
  title =	{{Mutual Dimension}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{116--126},
  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/3927},
  URN =		{urn:nbn:de:0030-drops-39270},
  doi =		{10.4230/LIPIcs.STACS.2013.116},
  annote =	{Keywords: computable analysis, data processing inequality, effective fractal dimensions, Kolmogorov complexity, mutual information}
}

Keywords: computable analysis, data processing inequality, effective fractal dimensions, Kolmogorov complexity, mutual information
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