Pairwise Distortion Distribution with Graph-Based Importance Sampling for Quantization Error and Intrinsic Dimension Estimation
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.
Related
- Estimation, Sensitivity Analysis, and Optimization of Distortion Risk Measures via Simulation
- Input Estimation for Repetitive-Motion Plants via ILC Subject to Quantization Errors and Packet Dropouts
- LUCID: Local Understanding of Covariate Importance with Conditional Density Estimation
- Amortized ratio-estimation importance sampling and localized simulation-based calibration for intractable likelihoods
- Learning under Target Shift: Optimal Density Ratio Estimation and Importance-Weighted Regression
BibTeX
@misc{chen2026pairwise,
title = {{Pairwise Distortion Distribution with Graph-Based Importance Sampling for Quantization Error and Intrinsic Dimension Estimation}},
author = {Xi Chen and Carl Nuzman and Shirin Jalali},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.04341},
eprint = {2611.04341},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.04341},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Pairwise Distortion Distribution with Graph-Based Importance Sampling for Quantization Error and Intrinsic Dimension Estimation
AU - Xi Chen
AU - Carl Nuzman
AU - Shirin Jalali
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.04341
UR - https://arxiv.org/abs/2611.04341
AB - 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.
ER -