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

May 22, 2026cs.DS

Entropy Equivalence Testing

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.

Clément L. Canonne, Yash Pote, Jonathan Scarlett +1

University of Sydney · National University of Singapore

Distribution Matching

Ask PDF

May 27, 2026cs.AI

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

Clark Hash is a small method for storing neural embeddings in less space. It normalizes each database vector, applies a deterministic sparse signed Johnson-Lindenstrauss projection, clips the result, and stores a fixed-width scalar-quantized code. Queries stay in floating point and are scored against the stored sketches. In the default 384-dimensional sentence-embedding setting, Clark Hash stores a cosine-search vector in 48 bytes instead of 1536 bytes for dense f32 storage. This is 32x smaller. The method does not need a training pass, learned codebooks, rotations, or corpus statistics before new vectors can be stored. We describe the codec, the Rust implementation, and a multilingual sentence-similarity evaluation on 9,304 labeled pairs from 29 subsets. With a multilingual MiniLM encoder, the 48-byte sketches reached 0.910 and 0.946 macro Pearson correlation with dense cosine scores on STS17 and STS22. Clark Hash is not a new Johnson-Lindenstrauss theorem and it is not a replacement for approximate nearest-neighbor indexes. It is a simple stateless codec for compact embedding storage.

Stanislav Kirdey, Clark Labs Inc

Clark Labs Inc.

Embedding Compression Neural Network Quantization

Ask PDF

May 19, 2026stat.ML

Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation

Squared Wasserstein distance is a frequently used tool to measure discrepancy between probability distributions. This distance is typically computed between empirical measures of size

n

from two underlying random samples. Unfortunately, even in lower dimensional Euclidean space problems

\left( d \in \{2,3\} \right)

, algorithms for Wasserstein distance computation with approximate or exact precision guarantees scale poorly in the runtime as a function of

n

and the desired precision. In response, we consider the computational-statistical runtime, where the goal is to estimate from samples the Wasserstein distance between potentially smooth measures up to

ε

-additive error in expectation with respect to the sampling; we allow

O(1)

computational cost for collecting a sample. Towards this, we develop a Sample-Sketch-Solve paradigm where we introduce a regular cartesian grid sketch of the samples. We show that (especially under

α

-Hölder smooth distributions) this can compress the data without increasing asymptotic error, and also regularizes the structure which enables faster exact algorithms. Ultimately, we approximate

W_2^2(P,Q)

within

ε

error in

ε^{-\max(2,\frac{d+1+o(1)}{1+α})}

time for

0 < α< 1

Hölder smooth distributions

P,Q

(0,1)^{d}

; an optimal

Θ(ε^{-2})

for

α> 1/2

when

d=2

and nearly optimal as

α\to 1

when

d = 3

Peter Matthew Jacobs, Jeff M. Phillips

Department of Statistics University of Wisconsin-Madison Madison, WI 53706 · Kahlert School of Computing University of Utah Salt Lake City, UT 84101

Randomized Sketching Approximation Algorithms Optimal Transport Wasserstein Distance

Ask PDF