CS Paper Radar

Efficient quadratic entropy with distance sketches

Steve Huntsman

cs.LG stat.MLmath.STstat.CO ·submitted 2026-10-08 13:52 UTC · v2
benchmark

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.

Comment
Code for reproducing results in LaTeX comments; removed submission checklist from v1

Closest papers

Nearest neighbours by meaning across the whole index.

Low-Dimensional Embeddings for Gaussian Kernels on Manifolds

cs.CG cs.LG ·2026-09-14 ·Soumik Dutta, Kunal Dutta
theory similarity 0.58
Abstract · 57 pages, 3 figures

The Gaussian kernel is a widely used similarity measure underlying kernel methods such as kernel PCA and spectral clustering, but computing Gaussian kernel distances for many pairs of points can be expensive. Using Random Fourier Features (RFF), Chen and Phillips [ALT 2017] showed that for points in a $d$-dimensional Euclidean ball in ${\mathbb R}^N$, $t=Ω((d/\varepsilon^2)\log(dR/\varepsilon))$ features suffice to preserve all pairwise Gaussian kernel distances within a $(1\pm\varepsilon)$ factor with high probability. We establish a uniform relative-error embedding theorem for the more general setting of an arbitrary positive-reach submanifold $\mathcal M\subset{\mathbb R}^N$ of intrinsic dimension $d$. We show that $t=O((d/\varepsilon^2)\log(\operatorname{vol}(\mathcal M)^2N^{2d}/(\operatorname{vol}(B_1^d(0))^2\operatorname{rch}(\mathcal M)^{2d}\varepsilon^{2d+1}δ)))$, or approximately $O((d^2/\varepsilon^2)(\log N+\log(1/(\varepsilonδ))))$, RFFs suffice, with probability $1-δ$, to preserve the Gaussian kernel distance between every pair of manifold points up to relative error $\varepsilon$. Thus the bound depends only logarithmically on the ambient dimension and on manifold parameters such as volume and reach, while retaining the $1/\varepsilon^2$ Euclidean rate. We also prove a topological consequence: under the same RFF embedding, persistent homology is preserved in the sense that weighted Cech and Rips filtrations built from Gaussian kernel power distance are $(1\pm\varepsilon_\star)$-interleaved, where $\varepsilon_\star$ accounts for both distance distortion and kernel-weight approximation.

0.22

Weakly Supervised Adaptation of Scientific Embeddings for Exploratory Literature Mapping

cs.DL cs.IR ·2026-10-18 ·Roman Neruda, Petra Vidnerová, Jiří Šejnoha, Jakub Mihálik, Tomáš Marvan
hot direction similarity 0.57
Abstract

Scientific document embeddings such as SPECTER2 are optimized for retrieval over large, heterogeneous corpora. On a small specialized corpus their similarity distributions can become highly compressed, which limits their usefulness for exploratory literature mapping. We study whether weakly supervised in-domain adaptation, using only metadata already available in open citation databases, changes this geometry. On ArtCon, a curated corpus of 704 publications on artificial and machine consciousness, we adapt the SPECTER2 proximity model with a lightweight LoRA adapter trained on positive pairs derived from bibliographic coupling in OpenAlex, using no manually annotated similarity labels. We compare the adapted embeddings with lexical (TF-IDF), citation-based (bibliographic coupling) and generic semantic (SPECTER2) representations under thresholded, fixed-density and symmetric k-nearest-neighbour graph constructions. Adaptation substantially decompresses the similarity distribution (mean pairwise cosine similarity 0.9104 to 0.8663, standard deviation 0.0259 to 0.0594) and yields graphs with markedly higher Louvain modularity and better connectivity than the base encoder under matched edge and neighbourhood budgets. The effect is stable across all three graph constructions and is therefore not an artefact of a single sparsification choice. We report this as a case study on one corpus, and we are explicit about what it does not establish: the clustering indices used here are computed against community labels derived from each representation's own similarity graph, so they measure internal geometric self-consistency rather than agreement with an external topical ground truth, and adaptation and evaluation use the same documents. Evaluation against independent labels, on held-out documents, and against geometric controls is ongoing work.

0.21

Sliced Wasserstein Sketches with Error Certificates

cs.LG ·2026-10-14 ·Elaheh Akbari, James Liu, Keaton Hamm, Soheil Kolouri
similarity 0.56
Abstract

Compact representations that support geometrically meaningful comparisons are valuable for learning from probability distributions. We study optimal, free-weight $M$-atom quantization of one-dimensional probability measures in quadratic Wasserstein distance and extend it to higher dimensions via slicing. Using $L$ shared projections yields a sketch with $O(LM)$ comparison time. Our main result is an exact decomposition of squared distance error into residual and partition-mismatch terms, yielding computable certificates for arbitrary centroid sketches. For optimal sketches, a finite $(2+δ)$ moment for some $δ>0$ guarantees $O(M^{-1})$ error in the finite-direction sliced distance, while equal-mass sketches can converge more slowly. Each slice preserves its mean, while storing residual energies enables covariance recovery from sufficiently many generic directions. Experiments on document, point-cloud, and flow-cytometry benchmarks show that optimal sketches substantially reduce storage while preserving the classification performance of uncompressed sliced distances. They also improve generalization from few labelled subjects and support end-to-end learning as compact pooling layers.

0.23

Unlocking Geodesic Gromov-Wasserstein Distances for 3D Modeling

cs.CV cs.DSeess.IV ·2026-09-26 ·Krzysztof Marcin Choromanski, Derek Long, Ananya Parashar, Dwaipayan Saha
similarity 0.55
Abstract

\textit{Gromov-Wasserstein Distances} (GWDs) provide quantitative ways of comparing probabilistic distributions defined on different metric spaces by applying techniques from the optimal transport theory. As such, GWD can be potentially useful in a large variety of applications ranging from graph matching problems to 3D object detection. However its practical use at scale is significantly limited by cubic time complexity computations involving dense intra-space distance matrices. Even though in the Euclidean metric spaces several techniques (e.g. involving scalable kernel methods) were proposed to address it, to the best of our knowledge, analogous techniques for general geodesic distances on manifolds, or shortest-path distance on graphs in their discretized variants, were not developed. In this paper, we present \textbf{E}fficient \textbf{G}eodesic \textbf{Gro}mov-\textbf{W}asserstein methods (EGGroW), a new class of efficient algorithms designed to calculate geodesic Gromov-Wasserstein distances with entropic Sinkhorn-like approaches, leveraging recently introduced \textit{GenusSink} methods \citep{genussink} and the theory of random features. We provide important downstream applications, namely: 3D pose estimation and 3D template detection. In the latter setting, we formulate a partial 3D template recovery as a staged problem: capacity-constrained scene selection is followed by semi-relaxed recovery of template visibility and correspondence. Our empirical findings show that EGGroW provides accurate solutions when standard Euclidean-based techniques fail and is characterized by light computational footprint, as our theoretical analysis predicts.

0.25

Fast Approximate $\ell_p$ Chamfer Distance via Lopsided Embeddings and Structured JL

cs.DS cs.LG ·2026-11-08 ·Ying Feng, David P. Woodruff
top venue similarity 0.55
Abstract · Accepted at NeurIPS 2026

For two $d$-dimensional point sets $A, B$ of size $n$, the Chamfer distance from $A$ to $B$ is defined as $\text{CH}(A,B)=\sum_{a \in A} \min_{b \in B} \mathsf{dist}(a, b)$, where $\mathsf{dist}$ is some underlying distance measure. We present efficient algorithms for approximating the Chamfer distance under the $\ell_p$ norm for $1 < p \le 2$. For the general case $1 < p < 2$, we utilize lopsided $\ell_p$ to $\ell_1$ embeddings with weak guarantees. We show that they are sufficient for preserving the Chamfer distance. In the high-dimensional regime, we use Fast Matrix Multiplication techniques to speed up the lopsided embeddings. These lead to $O(nd\cdot \mathrm{poly}(\log \log n, \log(1/\varepsilon))/\varepsilon^2)$ total time. For the specific Euclidean case ($p=2$), we leverage the Fast Johnson-Lindenstrauss Transform based on Toeplitz matrices and re-analyze the previous $\ell_1$-specific Chamfer algorithm in $\ell_2$. These achieve a runtime matching the recent state-of-the-art $\ell_1$ result of $O(nd(\log \log n + \log (1/\varepsilon))/\varepsilon^2)$, improving upon the previous $O(nd \log n/\varepsilon^2)$ bound for $\ell_2$. We also give additional results for the angular distance and upper and lower bounds in the streaming setting.

0.45

Computation-Friendly Compression of Matrices: Speeding up Linear and Boolean Algebra

cs.DS ·2026-10-26 ·Gonzalo Navarro
survey similarity 0.54
Abstract

Large sparse matrices---adjacency matrices of web and social graphs, feature matrices of machine-learning pipelines, the relations of graph databases---are routinely compressed to save space. Classical compressors, however, force the matrix to be decompressed before it can be used, so the space savings often yield a computational overhead. A recent line of work studies \emph{computation-friendly} compression: formats that are not only small, but let us carry out matrix--vector products, and in some cases matrix--matrix products, sums and closures, directly on the compressed representation {\em in time proportional to that compressed size}. This survey organizes that literature around the kind of redundancy each format exploits: spatial clustering of the nonzeros ($k^2$-trees and their variants), similarity between rows (Boldi--Vigna-style referencing and set-difference compression), repeated substrings (grammar compression), and dense bipartite substructures (bicliques). For each family we describe the representation, the algorithms, the theoretical guarantees and the empirical performance. Further, we show that the last three families are instances of a single general scheme, which we call a {\em sparse straight-line factorization} of the matrix, whose forward and backward substitutions evaluate right and left products in time proportional to the size of the representation, and that the product of two such factorizations is again one, which gives matrix--matrix products with a compressed output. We also relate the model to linear circuits, give simple recompression steps, and study the size of the smallest factorization: worst-case bounds, separations from each family, and parallelism. We close with a cross-family comparison and a list of open problems.

0.40

Computation and Applications of Euclidean and Normed Representations of Massive Data

cs.DS math.OC ·2026-09-06 ·Max Ovsiankin
similarity 0.53
Abstract · PhD dissertation

This thesis investigates Euclidean-space and $\ell_p$-norm representations of different forms of data, with a focus on efficient algorithms for computing these representations in settings where the amount of data is very large. The applications of such representations are also discussed: they may be used to summarize the data in a more compact form for downstream tasks while preserving its most salient properties; and further, they may also be used to extract insights about the data that may not be apparent in its original form. This thesis presents novel algorithms for computing Euclidean representations in the case where the data comes with linear structure, as well as in the case where the data comes only with metric, or distance structure. In addition, we give algorithms for computing $\ell_p$-norm representations in linear structured cases. The analyses of these algorithms use tools from geometry, probability, and optimization, and these tools are used to illuminate other algorithms for similar problems.

0.41

On the SoS Certifiability of Log-Concave Distributions

cs.LG cs.CCmath.PR ·2026-09-24 ·Aleksandr Storozhenko
theoryhot direction similarity 0.53
Abstract

We prove that for every isotropic log-concave distribution $P$ on $\mathbb{R}^d$ and every even $m\ge2$, the polynomial $(Cm)^m\|v\|_2^m - \mathbb{E}_{X\sim P}\langle X,v\rangle^m$ is a sum of squares, where $C>0$ is a universal constant. This improves on the Poincaré-dependent bounds (Kothari and Steinhardt, 2017), recovering the optimal moment bounds for log-concave distributions. As an immediate corollary, we obtain computationally efficient algorithms with dimension-free error guarantees for a wide range of statistical estimation problems. Our proof proceeds by using stochastic localization to decompose $P$ as an average of strongly log-concave measures, whose centered moments admit the subgaussian certificates (Diakonikolas et al., 2025). With a covariance-adapted choice of localization, we show that a fourth-moment certificate derived from the variance inequality for quadratic forms (Letwin, 2026) suffices to control this averaging at every even degree.

0.55