Data Compression and Fractal Dimension for Measures

open_access
Open Access
Author:
Wasson, Ryan Douglas
Graduate Program:
Mathematics
Degree:
Master of Arts
Document Type:
Master Thesis
Date of Defense:
August 31, 2015
Committee Members:
Jan Severin Reimann, Thesis Advisor/Co-Advisor
Keywords:
Kolmogorov complexity
Lempel-Ziv
fractal dimension
Hausdorff dimension
information dimension
multifractal spectrum
Abstract:
The ability to distinguish between data generated by random versus deterministic processes is necessary for scientific discovery. Various tools for achieving this goal exist in several different branches of mathematics, namely geometry and mathematical logic. The amount of irregularity in a data set can be measured using tools from the field of fractal geometry, such as fractal dimension in all its forms. Likewise, the field of algorithmic randomness, built on the foundation of mathematical logic, measures randomness using notions of complexity such as Kolmogorov complexity, a non-computable theoretical limit on the amount of information contained in an object. In the last fifteen years, it has been shown that the ideas from both these fields are strongly related. In this thesis, we summarize the results from the literature detailing this connection, and we demonstrate new numerical approaches for approximating Hausdorff dimension and information dimension using data compression. The validity of using various compression techniques, such as Lempel-Ziv and I-complexity, to approximate non-computable Kolmogorov complexity is also explored.