Pairwise Distortion Distribution with Graph-Based Importance Sampling for Quantization Error and Intrinsic Dimension Estimation

Quantifying the dimensionality of data is a fundamental need in machine learning and signal processing applications such as representation learning, data compression, and inverse problems, where the extrinsic dimension in which the data is presented can be very different from the intrinsic dimension that determines the operational performance. Various concepts, such as Rényi information dimension, rate-distortion dimension, and quantization dimension are useful here. Despite their theoretical significance, estimating these measures are challenging given their asymptotic definitions. Recent research has shown that analyzing the pairwise distortion distribution (PDD) of a data source can provide a tractable lower bound on the distortion of random codebook quantization, from which a tractable notion of intrinsic dimension can be derived. In this paper we extend this line of research in three main ways. First, we develop a related upper bound on distortion of random codebook quantization. Second, we improve the computability of both the lower and upper bounds, using a graph-based adaptive importance sampling approach. Third, we leverage the bounds to define new notions of intrinsic dimension which form upper and lower bounds on the Rényi information dimension, rate-distortion dimension, and quantization dimension, and which can be empirically estimated from unknown data sources. We illustrate the concepts by analyzing several artificial and empirical distributions.