Maximal correlation under cardinality constraints
2026-08-17 • Information Theory
Information Theory
AI summaryⓘ
The authors introduce a concept called quantized maximal correlation, which looks at correlations between simplified versions of two variables limited to a fixed number of outcomes. They find an upper limit for this correlation by connecting it to how well one can approximate a combination of these variables using fewer bits, measured by mean squared error. Using information theory tools and probability inequalities, they provide clear bounds that work independently of the data dimension for products of distributions. These findings also improve known results about certain properties of reversible Markov chains. Overall, the paper offers new ways to understand and bound correlations in simplified settings.
maximal correlationquantizationmean squared errorrate-distortion theoryanti-concentration inequalitiestensorizationproduct distributionsMarkov chainsisoperimetric constants
Authors
Dror Drach, Tomer Berg, Or Ordentlich, Ofer Shayevitz
Abstract
In this paper, we define and analyze the quantized maximal correlation, an extension of the notion of maximal correlation restricted to functions taking values in sets of bounded cardinality. We derive an upper bound on the quantized maximal correlation by showing that the correlation between any quantized functions of $X$ and $Y$ is related to the MMSE distortion in quantization of a particular linear combination of random variables. Following this, we leverage rate-distortion techniques and anti-concentration inequalities to further bound this MMSE, which results in explicit bounds on the quantized maximal correlation. Unlike the quantized maximal correlation itself, which does not generally tensorize, our bounds on the mean squared error do tensorize, resulting in a dimension-free upper bound on the quantized maximal correlation for product distributions. Our results also lead to improved bounds on the isoperimetric constants of reversible Markov chains and product chains, strengthening classical results such as those by Alon and Milman.