Gromov-Wasserstein Quantization and Clustering: Structure, Rates, and Algorithms

Group Invariant Spectral Embedding

Spectral embedding methods are widely used for dimensionality reduction and clustering of high-dimensional datasets with intrinsic low-dimensional structures. Although many datasets of practical interest exhibit invariance under symmetries such as rotations, standard spectral embedding methods do not account for this, treating symmetry-related data points as unrelated. Our approach to this problem is to incorporate the symmetries directly into the affinity kernels used for spectral embedding. We analyze the case of a Riemannian data manifold $M$ with symmetries given by a compact Lie group~$G$ and prove that, under suitable conditions, graph Laplacians constructed from three types of invariant kernels converge pointwise to explicit second-order differential operators on the quotient space $M/G$. Our analysis implies improved convergence rates, as the effective dimension drops according to the dimension of the group. We validate our approach on datasets with $\mathrm{SO}(2)$ or $\mathrm{SO}(3)$ symmetry, and show that $G$-invariant spectral embedding recovers the intrinsic geometry of the data, in contrast to standard spectral embedding, which fails to do so even in the limit of infinite data.

Global Fr´echet Manifold Learning for Random Objects, With Application to Low-Dimensional Wasserstein Representations of Distributional Data

Distributional Matching for Vector Quantization: A Unified Theoretical and Empirical Framework

The effectiveness of modern visual representation learning and autoregressive models critically depends on vector quantization (VQ), which discretizes continuous feature representations using a learnable codebook. Despite its widespread use, existing VQ methods often suffer from training instability and codebook collapse, arising from gradient mismatch induced by the straight-through estimator and the under-utilization of code vectors. In this work, we show that both issues can be traced to a fundamental mismatch between the distributions of feature vectors and code vectors, leading to inefficient representation and information loss. Building on this observation, we propose a distributional matching framework for vector quantization. We introduce principled criteria for desirable VQ behavior and demonstrate through theoretical analysis and empirical evaluation that aligning feature and code vector distributions provides a unifying mechanism for mitigating training instability and codebook collapse. We instantiate this framework using a Wasserstein-based objective with an efficient closed-form under a mild Gaussian approximation, and further show that a nonparametric alternative based on maximum mean discrepancy yields comparable performance. Extensive experiments on visual tokenization benchmarks support the effectiveness and robustness of the proposed approach.

Metric Geometry of Lebesgue, Wasserstein, and Gromov-Wasserstein Spaces: Submetries, Curvature, and Geodesics

A metric space $Z$ gives rise to three natural classes of infinite-dimensional metric spaces associated to $Z$: $p$-Wasserstein spaces of probability measures on $Z$, nonlinear Lebesgue $L^p$-spaces of $Z$-valued maps, and $p$-Gromov-Wasserstein spaces of $Z$-valued kernels. The latter class, referred to as $Z$-Gromov-Wasserstein ($Z$-GW) spaces, extends the classical Gromov-Wasserstein framework from metric measure spaces to more general, possibly attributed, network-like structures, and unifies many GW-type distances that nowadays play a significant role in metric geometry, data science and machine learning. In this article we develop a unified metric-geometric theory of these three classes of spaces, with a particular focus on the $Z$-GW spaces. Our first main result identifies a fundamental submetry structure linking them: the nonlinear Lebesgue space maps via a submetry onto the $Z$-GW space, which in turn maps via a submetry onto the Wasserstein space. This structure provides a mechanism for transferring geometric information among the three spaces. We apply this framework to geodesics and Alexandrov curvature. For $1<p<\infty$, we prove that geodesicity of $Z$ is equivalent to geodesicity of each of the three associated spaces; in the endpoint case $p=1$, all three associated spaces are geodesic, even when $Z$ is not. We also characterize geodesics in the $Z$-GW space as generalized interpolations, extending a known characterization in the classical setting due to Sturm. Finally, we give a complete classification of Alexandrov curvature bounds for these spaces in terms of the curvature of $Z$. Thus, while the main focus of the paper is a new metric-geometric theory of $Z$-GW spaces, the submetry framework also extends classical theorems for Wasserstein and Gromov-Wasserstein spaces and yields new geometric consequences for nonlinear Lebesgue spaces.

Default-Distance Entropy and Metric Dimension in Finite Geometries

A resolving set in a graph is a set of landmarks whose distance vectors distinguish all vertices. We use information theory to prove lower bounds for metric dimension and class dimension in distance-regular graphs and association schemes arising from finite geometry. The core idea is that, for a fixed landmark, a random object usually lies in one overwhelmingly likely distance or relation class. For classical dual polar graphs, with rank and type fixed and $q\to\infty$ through the admissible field orders, we prove $\mu(\Gamma(q,d,e))=\Theta_{d,e}(q^e)$ for $d\geq 2$ and $e>0$. The lower bound uses opposition as the typical distance. For the upper bound, we take, for each of a constant number of $(d-1)$-dimensional singular subspaces, all generators containing it. For Grassmann graphs, bilinear forms graphs, and attenuated-space schemes, we obtain lower bounds of the same exponential order as the known incidence constructions.

Lloyd's $K$-Means Clustering Algorithm Is Frank-Wolfe in Disguise

Lloyd's $K$-means algorithm, also known as na\"{i}ve $K$-means, is a widely used ad hoc optimization heuristic, designed to minimize the sum of squared errors (SSE) across all $K$-partitions of a dataset via iterative cluster refinement. In this work, we establish a novel connection between Lloyd's algorithm and the Frank-Wolfe (FW) algorithm, a prominent first-order method for projection-free optimization. We demonstrate that Lloyd's algorithm is a special case of FW. Leveraging recent advances in FW methods for concave objectives, we derive a non-asymptotic $\mathcal{O}(1/t)$ convergence rate to a local minimum of the SSE objective. To account for empty clusters, an outcome possible under Lloyd's greedy assignment, we develop an FW variant for semismooth objectives while retaining the same convergence rate that is solely controlled by the initial SSE value. We illustrate our findings with a simulation study for spherical Gaussian mixtures and a real-world image segmentation dataset.