arXiv preprint ·
Pairwise Distortion Distribution with Graph-Based Importance Sampling for Quantization Error and Intrinsic Dimension Estimation
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Information Theory
Hardware-Efficient Reinforcement-Learned Scheduling for Quantum LDPC Decoders
Hotplug Coded Caching: Embedding the YMA and Interference Elimination Schemes via Reed--Muller Codes
Optimal Communication for Distributed Sparse Histogram Aggregation
Functional inequalities from the fundamental limits of Bayesian estimation
A Complete Characterization of $q$-Ary $2$-Designs in Doubly-Extended Reed-Solomon Codes
Get the few papers worth your time in Information Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.