The condensation method for recovering the circle of camera angles from the COIL image dataset is demonstrated, where a standard PCA pipeline produces spurious homology, and the quotient of views of a tetrahedron in the SYMSOL pose-estimation benchmark is demonstrated.
Abstract
Point clouds arising in image collections, samples from Markov chain Monte Carlo, or states of a random walk, often have a simple underlying geometry which is obscured by noise, high ambient dimension, and the failure of Euclidean distance to reflect similarity. Methods such as UMAP and t-SNE condense such data into usable form, but rely on heuristic choices and provide no guarantee that the output reflects the topology of the input. We introduce a condensation method that comes with such a guarantee. Encoding the data as a positive $m\times n$ stochastic matrix $Q=(q_{ij})$, for instance the transition matrix of a random walk on the point cloud, we define a potential function $\psi(p)=\log \sum_{i} \exp(-KL(p,q_{i\bullet}))$ on the probability simplex $\Delta_n$, where $KL(p,q)$ is the Kullback-Leibler divergence, and prove that $\psi$ is $c$-convex in the sense of Optimal Transport Theory for the cost function $c(p,q)=KL(p,q)$. The associated transport map collapses noisy directions while provably preserving topology: the super-level sets of $\psi$ are homotopy equivalent to those of a $c$-conjugate function, whose image is a condensed, resampleable family of topological spaces which can be interpreted as a continuous analog of an alpha shape. We demonstrate the method by recovering the circle of camera angles from the COIL image dataset, where a standard PCA pipeline produces spurious homology, and the quotient $SO(3)/A_4$ from $45{,}000$ views of a tetrahedron in the SYMSOL pose-estimation benchmark.
We study the problem of recovering the correspondence between a collection of $n$ points in $\mathbb{R}^d$ and a noisy, permuted version of those points. In the high-dimensional regime $d=\omega(\log n)$, under a Gaussian model with noise variance $\sigma^2=d/(b\log n)$, prior work identifies $b=2$ as the threshold for almost exact recovery. We prove that this threshold is all-or-nothing: for every fixed $b<2$, no estimator recovers a positive fraction of the matching, and even estimating the matched point cloud in Euclidean distance is asymptotically no better than ignoring the correspondence. On the other hand, we consider a multi-view generalization of the problem where $K$ noisy, independently permuted copies of the same latent point cloud are observed. Here we show that a simple polynomial-time procedure recovers all relative matchings up to $o(n)$ errors whenever $b>K/(K-1)$. Thus multiple views can break the impossibility barrier $b=2$ for the original matching problem: in particular, for $3/2<b<2$, the two-view model has no nontrivial recovery, but a third view makes all latent correspondences efficiently recoverable.
Timothy L. H. Wee, Kaylee Yingxi Yang, Zhou Fan et al.· 0 citations
The spherical random geometric graph $G(n,d,p)$ is obtained by sampling $n$ independent points uniformly on the unit sphere $\mathbb{S}^{d-1}\subseteq\mathbb{R}^d$ and joining pairs of points which are sufficiently close, where the threshold is chosen so that the edge probability is $p$. The central question related to this model, and to a broad class of other models, is the following: when does the underlying geometry affect the resulting graph in a way which makes it distinguishable from the Erd\H{o}s--R\'enyi random graph $G(n,p)$, as measured in total variation distance? The precise answer to this question was conjectured by Bubeck, Ding, Eldan, and R\'acz, who predicted that $G(n,d,p)$ and $G(n,p)$ are indistinguishable precisely when $d \gg n^3p^3(\log p^{-1})^3$, and provided a test for distinguishing these models in the low-dimensional regime. Although this conjecture attracted considerable attention from researchers in probability, theoretical computer science, and high-dimensional statistics, it was previously fully proved only in the constant-density case. In this paper, we resolve the distinguishability conjecture in the broad range $1/3 \geq p \geq n^{-1/5} \text{polylog}(n)$. The key ingredient of our proof is a stronger statement which gives a precise asymptotic formula for the probability that $G(n,d,p)$ realizes a prescribed graph $H$: above the conjectured threshold, this probability is at most $(1+o(1))$ times the corresponding probability for $G(n,p)$, with the signed triangle count of $H$ appearing as the leading correction term.
We study the problem of recovering latent inner products from a random geometric graph with anisotropic Gaussian latent points. More precisely, for an i.i.d. sample $x_1, \dots, x_n \sim N(0,\Sigma)$ where $\Sigma \in \mathbb{R}^{d \times d}$, an edge $(i,j)$ is present in the graph if and only if $\langle x_i, x_j \rangle \ge \zeta$ for a threshold $\zeta$. We assume the threshold $\zeta$ to be chosen such that the average edge density of the graph is of constant order. To address the undesired degree fluctuations amplified by the anisotropy of the latent points, we consider the doubly centered adjacency matrix of the graph, and estimate the latent inner products using a rank-$d$ spectral approximation of the doubly centered matrix. The estimator obtains a mean squared error with a rate involving the stable rank of the covariance matrix $\Sigma$. Notably, the rate of estimation matches the state of the art for the isotropic case $\Sigma = I_d$, and permits an ill-conditioned covariance matrix with a diverging condition number. The analysis of the spectral method proceeds via the entrywise Hermite expansion of the doubly centered adjacency matrix with respect to the latent inner products. Instead of the standard trace method, it uses a decoupling argument recently introduced by Kaushik, Romberg, and Muthukumar (2025) to control nonlinear error terms.
The distance matrix of a finite point cloud can be visualized as a heatmap. When the data arise from a time series, the sublevel sets of this image are known as recurrence plots and are widely used in time series analysis. Motivated by this perspective, we establish a relationship between the distance-matrix filtration of the time series and the \v{C}ech (or Vietoris--Rips) filtration of its state-space embedding in the form of a degree-one chain map. We study the induced maps in homology, showing that the map from $H_0$ into $H_1$ is essentially surjective and providing an example where the map from $H_1$ into $H_2$ is nontrivial. These chain maps can be applied to simplify image persistence computations arising in the computation of cycling signatures, a topological tool for time series analysis. Moreover, these computations yield finer information that allows the analysis of transitions between different types of cycling motion.
A GPU port of the full query engine (OpenACC): the 3pCF, 4pCF, and parity-decomposed 4pCF kernels run on a single consumer GPU with measured speedups of $2.6\times$ (3pCF) to $9\times$ (4pCF) over a 64-thread CPU node, and an out-of-core tiling scheme allows graphs far exceeding device memory.
We consider the problem of graphically local metric embedding, i.e. embedding points from an arbitrary finite metric space into a target metric space while preserving, up to a small distortion, only a subset of the pairwise distances specified by a bounded degree graph $G$. We provide a general reduction showing that, in many cases, this is no easier than embedding the points while approximately preserving all pairwise distances. As an illustration of our general reduction, we show that there exists a Euclidean metric space $X$ on $n$ points along with a graph $G = (X,E)$ of maximum degree $3$ such that any embedding of $X$ into $\ell_2^m$ which only preserves distances specified by $E$ up to a relative error of $(1+\varepsilon)$ must satisfy $m = \Omega(\varepsilon^{-2}\log n)$. Our lower bound matches the upper bound on the dimension coming from the Johnson-Lindenstrauss lemma for approximately preserving all pairwise distances; previously, such a lower bound was known only for the class of noncontracting embeddings [Schechtman-Shraibman, Discrete&Computational Geometry, 2009]. Moreover, the condition that the maximum degree of the graph is $3$ is best possible: for graphs $G$ of maximum degree $2$ (or more generally, treewidth at most $2$), any metric space embeds $G$-isometrically into any two-dimensional normed space.