PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient quadratic entropy with distance sketches

Steve Huntsman

arXiv:2610.11976v1stat.MLcs.LGmath.STstat.COstat.TH

TL;DR

The paper targets quadratic-entropy computation for many distributions on a shared large point set, where explicitly forming the distance matrix is prohibitive. It uses scalable estimators and a cached sketch for Euclidean and spherical geodesic distances; its citation examples show that feature-based quadratic entropy captures semantic dispersion defined by arXiv subject areas.

  • Problem

    For many distributions on the same large point set, explicitly forming the shared distance matrix is prohibitive.

    Source: §1 · p. 1

  • Method

    The paper gives unbiased Monte Carlo estimators and uses a single cached sketch to amortize computation for Euclidean and spherical geodesic distances as p varies.

    Source: §1 · p. 1, §1.2 · p. 2

  • Results

    Feature-based quadratic entropy captures ground-truth semantic dispersion of citing papers defined by arXiv subject areas.

    Source: §5 · p. 7

  • Takeaways & Limitations

    For citation analysis, quadratic entropy measures readership dispersion beyond citation counts, and normalization focuses on geometry while controlling for citation counts.

    Source: §5 · p. 7

    The spherical control variate is less effective than the Euclidean case for concentrated data because sign-only information discards too much.

    Source: §4.2 · p. 7

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper develops scalable unbiased estimators for quadratic entropy across common negative-type distances, targeting many distributions on a fixed, large point set where explicitly forming the distance matrix is prohibitive. It places the estimators alongside prior approaches and motivates shared-sketch computation for Euclidean and spherical geodesic distances.

1 INTRODUCTION

  • The estimators target millions of arbitrary distributions on the same large point set, where explicitly forming the distance matrix is prohibitive.The setting includes hundreds or more feature dimensions and hundreds of thousands or more points.Source: §1 · p. 1

1.2 Related work

  • Direct pair sampling has O(1/N) variance but a worse constant for spread-out p, cannot amortize across distributions, and can work better for concentrated data.It also does not express Q as a functional linear in p, limiting deployment at scale.Source: §1.2 · p. 1
  • The introduction positions quadratic entropy within diversity and comparison functionals, while noting that much related work does not address computation at scale.Quadratic entropy is related to two-sample maximum mean discrepancy and energy-distance comparison functionals.Source: §1.2 · p. 1
  • For Euclidean distance, the paper distinguishes its estimator through a relative error bound on Q and a squared-Euclidean control variate with mean computable in O(mn).The closest cited work establishes a sliced identity with a Bernstein-type error bound [5].Source: §1.2 · p. 2
  • For spherical geodesic distance, random-projection signs reduce quadratic entropy to one scalar per direction, avoiding infeasible high-dimensional spherical harmonics.The method uses the Goemans-Williamson representation; deterministic Gram-matrix expansion has prohibitively growing rank, while prior spherical slicing compares measures by projection rather than linearizing geodesic distance.Source: §1.2 · p. 2
  • A single cached sketch U^T X supports amortized quadratic-entropy computation for Euclidean and spherical geodesic distances as p varies.The distance geometry is held constant while calculations are reused across distributions.Source: §1.2 · p. 2
  • The paper’s error bounds are independent of ambient dimension m, unlike compared direction counts that scale linearly in m.Some related arc-cosine methods tie feature budget N to m and provide no finite-sample guarantee for N much smaller than m [28, 5].Source: §1.2 · p. 2

1.3 Paper organization

  • The paper organizes its treatment around negative-type distances and embeddings, efficient estimators, scaling techniques, and real-data experiments.Appendix A contains proofs, and the source comments contain code for exact reproduction.Source: §1.3 · p. 2

2 NEGATIVE TYPE DISTANCES AND FEATURE EMBEDDINGS

Negative-type distances admit Euclidean feature representations that support the paper’s quadratic-entropy computations. The section characterizes these distances and connects them to a centered Gram matrix and its factorization.

2 NEGATIVE TYPE DISTANCES AND FEATURE EMBEDDINGS

  • A symmetric, nonnegative, zero-diagonal matrix d is negative type when a^T d a ≤ 0 for every a with 1^T a = 0.Strict negative type requires strict inequality for every nonzero such a; Euclidean distances are strict negative type, and spherical geodesic distances are strict when no points are antipodal.Source: §2 · p. 2
  • Schoenberg’s result characterizes negative type by feature vectors whose squared Euclidean distances equal the entries of d.The centered matrix G = -1/2 J^T dJ is positive semidefinite, and its Cholesky factorization yields the feature vectors.Source: §2 · pp. 2–3
  • Conversely, a squared-Euclidean distance matrix is negative type because its quadratic form is nonpositive for every zero-sum coefficient vector.The passage derives this from the squared norm of the weighted sum of feature vectors.Source: §2 · p. 3

3 EFFICIENT QUADRATIC ENTROPY COMPUTATIONS FOR COMMON DISTANCES OF NEGATIVE TYPE

Squared Euclidean and cosine distances allow straightforward quadratic-entropy computations, while Euclidean and spherical geodesic distances require random-feature estimators. The section develops their estimation guarantees and compares geodesic sketching with pair sampling.

3.1 Squared Euclidean distance

  • Squared Euclidean distance makes the computation trivial by taking each feature map as the input point itself.The section also identifies cosine distance as a special case of squared Euclidean distance.Source: §3.1 · p. 3, §3 · p. 3

3.2 Cosine distance on Sm−1

  • Cosine distance on the sphere is treated as a special case of squared Euclidean distance.Source: §3.2 · p. 3, §3 · p. 3

3.3 Euclidean distance

  • The Euclidean estimator uses an expected absolute random projection to estimate the exact quadratic entropy, rather than a proxy distance between distributions.Sorting reduces the mean absolute-difference computation to O(n log n); averaging N sampled Gaussian projections yields the estimator.Source: §3.3 · p. 3
  • With IID Gaussian inputs, the Euclidean estimate is unbiased for Q, and its relative-error bound is tight for two uniformly weighted points.The examples suggest the exponential tail bound is loose in practice and that small N can yield meaningful estimates.Source: §3.3 · p. 3

3.4 Geodesic distance on Sm−1

  • For spherical geodesic distance, random sign features linearize the angle, reducing the entropy calculation to a scalar evaluated over random directions.The scalar can be amortized when the distance is reused.Source: §3.4 · p. 4
  • The geodesic estimator is unbiased for Q; its reported relative errors rise rapidly as spherical concentration increases.The examples suggest the exponential tail bound is loose in practice and small N can suffice for meaningful estimates.Source: §3.4 · p. 4, Figure 2 · p. 5

3.4.1 A relative bound

  • The geodesic variance bound is tight in a two-point uniform example and sharper than the earlier bound when Q is small.The example has points separated by angle θ and Q = θ/2.Source: §3.4.1 · p. 5

3.4.2 Comparison with a pair-sampling baseline

  • Compared with pair sampling, sketching loses its advantage as geometry concentration increases, while larger uniform support raises the variance ratio but leaves it above 1 in the examples.The sketch variance increases toward its bound with concentration, whereas pair-sampling variance is agnostic to concentration.Source: §3.4.2 · p. 5

4 SCALING

The section reduces the cost of quadratic-entropy computation through faster distance-specific runtimes, amortization across distributions, and control variates. It also describes a relative-error guarantee and conditions where a geodesic control variate is less effective.

4 SCALING

  • Squared Euclidean and cosine cases run in O(mn), Euclidean in O((m + log n)nN), and spherical geodesic in O(mnN), improving on O(mn^2) when N ≪ n.Amortization and a Euclidean control variate can further improve performance.Source: §4 · p. 5

4.1 Amortization

  • Amortization replaces repeated dense work with one O(mnN) sketch construction followed by O(nN) per quadratic-entropy evaluation.The same product U^T X can be reused across distributions when X and d are preserved.Source: §4.1 · pp. 5–6
  • The amortized relative-error guarantee for Q holds independently of p with probability at least 1 − δ.The section also states that the spherical-geodesic result is similar but weaker.Source: §4.1 · p. 6

4.2 Control variates

  • For Euclidean entropy, a squared-Euclidean control variate has a mean computable in O(mn) versus O(mnN); the geodesic control variate is less effective on concentrated data.In that regime, using signs alone throws away too much information.Source: §4.2 · pp. 6–7

5 EXAMPLES AT SCALE

The examples use citation-walk distributions and text features to assess the dispersion of papers’ readership, with quadratic entropy capturing subject-area dispersion while controlling for citation count. A second dataset extends the analysis across aggregation levels and identifies concentrated and dispersed fields and institutions.

5 EXAMPLES AT SCALE

  • The citation-walk example uses 128 skip-gram title and abstract features and also evaluates spherical geodesic distance on normalized features.Papers without citations receive unit mass on themselves; for uniform cross-class citations, quadratic entropy measures average distance between distinct citing papers, not just their count.Source: §5 · p. 7
  • Feature-based quadratic entropy captures citing-paper dispersion by arXiv subject area while controlling for citation count.The figures stratify papers into citation-count bands; Table 1 gives narrow- and broad-reach examples at three target degrees.Source: §5 · p. 7, Table 1 · p. 8
  • Figure 4 plots estimated quadratic entropies, while Figure 5 applies a normalization intended to control for citation counts and focus on geometry.Both figures stratify citation counts and compare entropy with distinct citing subject areas and citing-paper Shannon entropy.Source: §5 · p. 7, Figure 4 · p. 7, Figure 5 · p. 7
  • For 169,343 arXiv papers, the dense distance matrix would require roughly 57 GB, while a 2,500-direction bit-packed sketch uses roughly 1,000 times less storage.Sketch construction took 3.76 seconds and computing all entropies took 18.6 seconds; loading the dataset took 1.82 seconds.Source: §5 · pp. 7–8

5.1 A larger-scale example

  • On ogbn-mag, quadratic entropy or dispersion increases with aggregation level, and the analysis identifies concentrated and dispersed fields and institutions with at least 5,000 papers.Dispersion across papers, authors, coauthors, fields, and institutions is computed from one sketch; the matrix multiplication took under two seconds.Source: §5.1 · p. 8, Figure 6 · p. 8, Figure 7 · p. 8

AI use statement

  • The author reports using Claude Opus 5 across conceptual, mathematical, methodological, experimental, and writing tasks.The author says AI-assisted work was reviewed, including rewriting proofs and independently checking data analyses and results.Source: AI use statement · pp. 8–9
  • The author states that all writing and responsibility remain theirs.The author also reports reviewing AI-assisted work through proof rewriting, code-output checks, and independent analyses.Source: AI use statement · p. 9

CHECKLIST

The checklist records that the paper supplies its mathematical setup, assumptions, proofs, and algorithmic complexity analysis. It also documents empirical-result and asset reporting, while marking human-subjects requirements not applicable.

CHECKLIST

  • The checklist marks the mathematical setting, assumptions, theoretical claims, proofs, and explanations of assumptions as included.It describes the mathematical setup as the backbone of the paper.Source: CHECKLIST · p. 11
  • The checklist marks empirical-result reproduction materials, measure and error-bar definitions, and computing infrastructure as included.The stated infrastructure is a MacBook Pro (M3 Max).Source: CHECKLIST · p. 11
  • The checklist marks creator citations for existing assets as included and reports license and new-asset information as not applicable.It also marks data-provider consent and sensitive-content discussion as not applicable for the arXiv paper information.Source: CHECKLIST · p. 11
  • The checklist marks crowdsourcing and human-subjects requirements, including participant instructions, risks, and compensation, as not applicable.Source: CHECKLIST · p. 11

A.1 Proof of Proposition 3.1

The proof excerpt invokes Gaussian random-variable algebra for a projected vector and then a substitution; it says these steps establish equation (6) and lead to equation (7).

A.1 Proof of Proposition 3.1

  • The proof states that u^T x has a zero-mean normal distribution with variance ||x||^2.It attributes this step to standard Gaussian random-variable algebra.Source: §A.1 · p. 12
  • A substitution t = z^2/(2||x||^2) is used in the proof’s next step.The proof says this establishes equation (6).Source: §A.1 · p. 12
  • The proof then states that the resulting expression is precisely equation (7).Source: §A.1 · p. 12

A.2 Proof of Proposition 3.2

The proof excerpt invokes the sorted order of the v_j and attributes a final equality to P_n.

A.2 Proof of Proposition 3.2

  • The proof uses the fact that the v_j are sorted in the displayed step.Source: §A.2 · p. 12
  • The two stated justifications in the excerpt are sorted v_j and the final equality’s connection to P_n.Source: §A.2 · p. 12
  • The excerpt attributes its final equality to P_n.Source: §A.2 · p. 12

A.3 Proof of Theorem 3.3

The proof bounds the Euclidean estimator's sensitivity and variance, then applies Gaussian concentration to its projected average.

A.3 Proof of Theorem 3.3

  • The Euclidean quadratic-entropy quantity is Lipschitz with constant at most pπ, and this property also holds for its averaged form.The proof invokes the reverse triangle inequality and Cauchy–Schwarz for the bound.Source: §A.3 · p. 13
  • The proof applies Gaussian concentration to the averaged estimator and substitutes ε := t/Q to obtain bound (10).It identifies the number of projections N with Q before applying the concentration inequality.Source: §A.3 · p. 13
  • For a Gaussian projection u and vector v, E[(u^T v)^2] = ∥v∥^2 and Var(|u^T v|) = (1 − 2/π)∥v∥^2.The proof also gives E|u^T v| and uses Minkowski’s L2 inequality in the variance calculation.Source: §A.3 · p. 13

A.4 Proof of Proposition 3.5

These appendix proofs establish variance and concentration bounds for the geodesic estimator and pairwise sketch, using bounded-variable or Gaussian concentration and union bounds.

A.4 Proof of Proposition 3.5

  • The expected squared difference between two sign features equals θjk, using the identity in (14).The proof writes 4 E_u[(s_j − s_k)^2] = π/2 (1 − E_u[s_js_k]) = θjk.Source: §A.4 · p. 14

A.6 Proof of Theorem 3.8

  • Hoeffding’s inequality gives concentration for qgeo, which lies in [0, π/2], and the proof also bounds its variance by π²/16.The variance bound is used again to obtain (18).Source: §A.6 · p. 14

A.7 Proof of Proposition 3.9

  • Because the sign-feature mixture lies in [−1, 1], the proof bounds its fourth moment by its second moment and uses μ(1 − μ) ≤ 1/4.It notes alternatively that π² Q − Q² is maximized at Q = π/4, where it equals π²/16.Source: §A.7 · p. 14

A.8 Proof of Lemma 3.11

  • The proof applies Theorem 3.10 with ν := Nσ² and c := R/3, chooses τ to control S at the prescribed level, then uses a union bound and sign symmetry.The constant R/3 follows from the inequality that holds for ℓ ≥ 3, with equality at ℓ = 3.Source: §A.8 · pp. 14–15

A.9 Proof of Theorem 3.12

  • For the geodesic estimator, the centered IID variables ζi are bounded in absolute value by π/2, with variance input supplied by Proposition 3.9.The proof sets ζi := qgeo(u(i)) − Q and uses qgeo(u), Q ∈ [0, π/2].Source: §A.9 · p. 15

A.10 Proof of Lemma 4.1

  • For the pairwise Euclidean sketch, Gaussian concentration bounds the error and a union bound over unordered pairs yields the required projection count.The proof then solves for N.Source: §A.10 · pp. 15–16

A.11 Proof of Lemma 4.2

  • For each pair, Hoeffding’s inequality bounds the sign-based estimate’s deviation, followed by a union bound.The per-projection quantity takes values in {0, π} and has mean θjk.Source: §A.11 · p. 16
Loading 2610.11976v1…