Intrinsic Dimension Estimation using Simplex Volumes

Abstract

In this thesis, we introduce a novel approach for the estimation of the intrinsic dimension of high-dimensional datasets. For this purpose, the volumes of high-dimensional simplices, with vertex points sampled from local subsets, are analyzed to yield precise estimates for a wide range of values of the intrinsic dimension.<br /> In the first part, we discuss particular characteristics and challenges of high-dimensional data analysis and further describe the interplay between dimensionality reduction and intrinsic dimension estimation in the context of data mining. The main part summarizes and compares both the most relevant definitions of dimension as well as a selection of diverse existing approaches for the task of intrinsic dimension estimation. Next, the theoretical foundations and precise algorithmic implementations of two variants of our new method, called "Sample Simplex Volumes", are presented, including considerations on noise and complexity. A comprehensive numerical analysis with synthetic and real-world data finally reveals the competitive accuracy of our estimators.