Efficient quadratic entropy with distance sketches

Steve Huntsman

stat.MLOct 8, 2026

Efficient quadratic entropy with distance sketches

Authors: Steve Huntsman

Abstract

We detail scalable methods for approximating the quadratic entropy $p^T d p$ for arbitrary distributions $p$ and common distances $d$ of negative type. We focus on the Euclidean and spherical geodesic cases, which both use random feature embeddings and projections to dramatically improve computational complexity within a simple framework. Amortization of a single large matrix multiplication and control variates further enable computation at large scale with low memory and runtime in situations where $d$ is held constant while $p$ varies. We demonstrate this with a comparison against direct pair sampling and bibliometric/scientometric examples on Open Graph Benchmark datasets, revealing papers, fields, and institutions with both particularly narrow and broad interdisciplinary reach from their citations and text features alone.

Figures & tables

Figure 1: From left to right: for $\ell=0,\dots,10$ , relative errors over 100 trials for estimates of Euclidean quadratic entropies $\bar{Q}^{\textnormal{euc}}_{N}(p)$ with $p$ dense, given by normalizing $n$ IID $\mathcal{U}([0,1])$ random variables, and $d$ given by taking 10000 IID uniform points on $S^{m-1}$ for $m=2^{10}$ and forcing $2^{\ell}$ coordinates (chosen uniformly without replacement) to be positive. Error for $\bar{Q}^{\textnormal{euc}}_{N}$ is shown in red , while error using the Euclidean control variate described in § 4.2 is shown in blue . Note that relative errors are virtually independent of the concentration parameter $\ell$ .

Figure 2: As in Figure 1 , but for spherical geodesic ( versus Euclidean) distance $d$ . Note that as concentration increases (because the number $2^{\ell}$ of fixed signs on the sphere increases) from left ( $\ell=0$ ) to right ( $\ell=10$ ), the relative errors rapidly increase.

Figure 3: Both panels show the same ratio, of the per-pair variance $\sigma^{2}_{\mathrm{naive}}=p^{T}d^{\circ 2}p-Q^{2}$ (where we use the Hadamard product notation $(d^{\circ 2})_{jk}=d_{jk}^{2}$ ) of the pair-sampling estimator of § 1.2 to the measured per-direction variance $\sigma^{2}_{\mathrm{sketch}}=\mathrm{Var}(q^{\textnormal{geo}})=\frac{\pi^{2}}{4}\mathrm{Var}(s^{2})$ , for $n=10000$ points on $S^{m-1}$ for $m=2^{10}$ . Left: $p$ dense and random, with the geometry concentrated by forcing $2^{\ell}$ coordinates positive as in Figure 2 . Right: taking geometry and $p$ uniform on $\leq n$ points. The panels do not agree at their common corner ( $\ell=0$ versus $|\textrm{supp}(p)|=10000$ ) because $p$ is dense random on the left and exactly uniform on the right.

Panel of Figure 4 — Figure 4: Top: (estimated) quadratic entropies of the (one-step) distribution $p^{(j)}_{(1)}$ of citing papers for various bands of citation count $\chi$ and as a function of distinct subject areas of citing papers. Bottom: the same quadratic entropies, but as functions of Shannon entropy for the arXiv class distribution. Note that $d$ is agnostic to the arXiv class data and only depends on the skip-gram feature vectors for titles and abstracts.

Panel of Figure 5 — Figure 5: As in Figure 4 , but normalized.

$\chi$	$\#$	$f_{\times}$	$Q$	class	arXiv ID	title start
20	1	0.00	0.40	cs.IT	1705.06350	Wireless Information and Power Transfer over an AWGN channel…
21	11	0.86	0.65	cs.LG	cs/0011033	Web Mining Research: A Survey
41	1	0.00	0.45	cs.IT	0905.3109	Interference Channels with Source Cooperation
38	14	0.76	0.65	cs.LG	1404.1100	A Tutorial on Principal Component Analysis
78	1	0.00	0.56	cs.CV	1803.09786	Transferable Joint Attribute-Identity Deep Learning for Unsupervised…
78	18	0.55	0.72	cs.LG	1309.0238	API design for machine learning software: experiences from the scikit-…

Table 1: Narrow- and broad-reach exemplars at three target degrees. For each of two papers in the three target bands

[18,22)

[38,42)

, and

[75,85)

, we show the paper’s degree

\chi

, the number

\#

of distinct arXiv categories of citing papers, the cross-field fraction

f_{\times}

, the quadratic entropy

Q

, the primary class, arXiv identifier, and the beginning of the title. The broad-reach papers are respectively a survey, a tutorial, and a design document for the popular scikit-learn library.

Figure 6: Quadratic entropy/dispersion increases with the level of aggregation.

Panel of Figure 7 — Figure 7: Extremes of concentration (red) and dispersion (blue) among (top) fields at MAG concept hierarchy level 2 and (bottom) institutions, both with 5000 or more papers, with labels provided by OpenAlex [ 31 ] . Concentration appears to be correlated with specialization (at least at extremes).

Explore similar work

Entropy Equivalence Testing
May 22, 2026Clément L. Canonne, Yash Pote, Jonathan Scarlett +1Distribution Matching
University of Sydney · National University of Singapore
Clark Hash: Stateless Sparse Johnson-Lindenstrauss Quantization for Neural Embeddings
May 27, 2026Stanislav Kirdey, Clark Labs IncEmbedding Compression Neural Network Quantization
Clark Labs Inc.
Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation
May 19, 2026Peter Matthew Jacobs, Jeff M. PhillipsRandomized Sketching Approximation Algorithms
Department of Statistics University of Wisconsin-Madison Madison, WI 53706 · Kahlert School of Computing University of Utah Salt Lake City, UT 84101

May 22, 2026, cs.DSJ/K move · Enter open · S save

Entropy Equivalence Testing

Clément L. Canonne, Yash Pote, Jonathan Scarlett, Joy Qiping Yang

University of Sydney · National University of Singapore

Distribution Matching

Open paper AskPDF arXiv

We introduce the problem of \emph{entropy equivalence testing} for probability distributions, a relaxation of the well-studied closeness testing problem, where the distribution testing algorithm is now only required to distinguish, given samples from two unknown distributions

p,q

and a parameter

\varepsilon \in(0,1/2]

, between

p=q

and

|H(p)-H(q)| \geq \varepsilon

(where

H

denotes the Shannon entropy). We provide a time- and sample-efficient algorithm for this task, showing that the optimal sample complexity for this task can be significantly lower than that of closeness testing. As an application, we leverage this result to provide the first non-trivial testing algorithm for (standard) closeness of low-degree \emph{Bayesian networks}, which significantly improves on either the sample or time complexity of a baseline based on full learning.

Abstract

Explore similar work

Entropy Equivalence Testing

Clark Hash: Stateless Sparse Johnson-Lindenstrauss Quantization for Neural Embeddings

Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation