We calculate Euclidean distance degrees for common manifold optimization types.
problem Optimizing on manifold structures.
method Closed-form expressions for stationary points of Euclidean distance function.
result Closed-form expressions for all stationary points on manifold optimization.
Study infinite Euclidean distance discriminants of algebraic varieties.
problem Understanding the structure of data points with infinitely many critical points in Euclidean distance correspondence.
method Developed computer code to compute discriminants and proved properties of fibers.
result Infinite Euclidean distance discriminants contain all data points with infinitely many critical points for the nearest-point problem.
Study robustness of polynomial neural networks using algebraic geometry.
problem Certify robustness radius of polynomial neural networks.
method Metric algebraic geometry, Euclidean distance degree, symbolic elimination, homotopy-continuation methods.
result Found decision boundaries with lower ED degree than generic cubic hypersurfaces.
Introduces Grassmann Distance Complexity to measure algebraic set nearest point problems.
problem Measuring complexity of finding nearest points in Grassmannian space.
method Uses Lipschitz critical point theory and o-minimal geometry.
result Establishes fundamental properties of GDC, including bounds and finiteness conditions.
We investigate some geometric properties of the real algebraic variety Δ of symmetric matrices with repeated eigenvalues. We explicitly compute the volume of its intersection with the sphere and prove a Eckart-Young-Mirsky-type theorem for the distance function from a generic matrix to points in Δ. We exhibit conne…
Classical multidimensional scaling only works well when the noisy distances observed in a high dimensional space can be faithfully represented by Euclidean distances in a low dimensional space. Advanced models such as Maximum Variance Unfolding (MVU) and Minimum Volume Embedding (MVE) use Semi-Definite Programming (SDP…
The study confirms conjectures about normals to convex polytopes in 3D space.
problem Concurrent normals problem for convex polytopes in 3D.
method Analyzes the PL concurrent normals problem for convex polytopes, proving conjectures for specific cases.
result Polytopes in 3D have points with 10 normals from interior points, confirmed for all tetrahedra and triangular prisms.
New spectral conditions ensure graph rigidity and global rigidity in the Euclidean plane.
problem Ensuring graph rigidity and global rigidity in the Euclidean plane.
method Improving algebraic connectivity bounds for graph rigidity and global rigidity.
result Every 6-connected graph is rigid and globally rigid if its algebraic connectivity exceeds specific thresholds.
Paper proposes a method to recover point configurations from noisy distance data.
problem Recovering point configurations from noisy distance data.
method Robust Euclidean Distance Geometry via Dual Basis (RoDEoDB) algorithm.
result Exact recovery guarantees for point configuration and Gram matrix under mild conditions.
We introduce two versions of a new sketch for approximately embedding the Gaussian kernel into Euclidean inner product space. These work by truncating infinite expansions of the Gaussian kernel, and carefully invoking the RecursiveTensorSketch [Ahle et al. SODA 2020]. After providing concentration and approximation pro…
Matrix profile has been recently proposed as a promising technique to the problem of all-pairs-similarity search on time series. Efficient algorithms have been proposed for computing it, e.g., STAMP, STOMP and SCRIMP++. All these algorithms use the z-normalized Euclidean distance to measure the distance between subsequ…
The study compares Euclidean and cosine distances in medical drug prescription prediction.
problem Comparing Euclidean and cosine distances in medical drug prescription prediction.
method Established geometric properties and compared distances in real-world medical data.
result Different distances lead to different optimizing nonlinear kernel embedding frameworks.
Revisits Isomap, showing it constructs Euclidean representations of geodesic structure.
problem Nonlinear dimension reduction of manifold data.
method Revisits Isomap's rationale, clarifying its approach to constructing Euclidean representations of geodesic structure.
result Convexity is not required for shortest path distances to converge to Riemannian distances.
Network Embeddings (NEs) map the nodes of a given network into d-dimensional Euclidean space Rd. Ideally, this mapping is such that `similar' nodes are mapped onto nearby points, such that the NE can be used for purposes such as link prediction (if `similar' means being `more likely to be connected') or c…
Extends manifold learning to non-Euclidean metrics.
problem Applying manifold learning to data in non-Euclidean spaces.
method Generalizes manifold learning to metric spaces and studies conditions for convergence.
result Conditions for the convergence of graph Laplacian in metric spaces.
Euclidean nets reveal properties of higher-dimensional manifolds.
problem Characterize the geometry of manifolds based on discrete Euclidean distances.
method Isometric embeddings and properties of geodesics.
result Manifolds share properties with Euclidean space in terms of geodesics and distances.
New Sliced-Wasserstein distances for non-Euclidean data.
problem Computational burden of Wasserstein distance on non-Euclidean manifolds.
method Derive Sliced-Wasserstein distances and flows on Cartan-Hadamard manifolds.
result General constructions and non-parametric schemes for minimizing new distances.
We address noisy Euclidean distances in high dimensions, estimating noise levels and correcting distances.
problem Distorted pairwise Euclidean distances due to heteroskedastic noise.
method Developed a hyperparameter-free approach to jointly estimate noise magnitudes and correct distances.
result Our method provides accurate noise magnitude estimates and corrected distances in high-dimensional settings.
Smooth maps preserve distances on specific revolution surfaces.
problem Existence of smooth maps on revolution surfaces.
method Proving existence of maps preserving distances on meridians and parallels.
result Smooth maps exist from revolution surfaces to Euclidean plane.
For time series comparisons, it has often been observed that z-score normalized Euclidean distances far outperform the unnormalized variant. In this paper we show that a z-score normalized, squared Euclidean Distance is, in fact, equal to a distance based on Pearson Correlation. This has profound impact on many distanc…
Paper tackles robust Euclidean distance estimation with sparse outliers.
problem Estimating point positions from corrupted distance measurements.
method Proposes a novel algorithm using Nyström method and robust PCA.
result Achieves accurate recovery with minimal anchors and sparse outliers.
Study rigidity by logarithmic capacity and related functions.
problem Rigidity phenomena in kernel functions and capacities.
method Exploration of Bergman kernel, logarithmic capacity, Green's function, and Euclidean distance/volume.
result Established rigidity theorems by logarithmic capacity.
A new method compares unaligned datasets using log-Euclidean signatures of SPD matrices.
problem Efficiently comparing datasets with unknown alignment.
method Diffusion operators, Riemannian geometry, log-Euclidean metric.
result LES distance recovers meaningful structural differences, outperforming existing methods.
The paper studies convexity of products of squared Euclidean distances.
problem Convexity of products of squared Euclidean distances.
method Proved a convexity principle and applied it to products of squared distances, computed Hessian-positive regions and exact convexity levels.
result Computed exact convexity and quasiconvexity truncation levels for the two-centre model.
We consider the family of the Bour's minimal surfaces in Euclidean 3-space, and compute their classes, degrees and integral free representations.
No regular algebraic hypersurfaces with non-zero constant mean curvature in Euclidean spaces are found.
problem Existence of regular algebraic hypersurfaces with non-zero constant mean curvature in Euclidean spaces.
method Analyzing polynomials defining hypersurfaces of various degrees and shapes.
result Hyperspheres and round cylinders are the only such hypersurfaces defined by polynomials of degree ≤3.
We study the use of power weighted shortest path distance functions for clustering high dimensional Euclidean data, under the assumption that the data is drawn from a collection of disjoint low dimensional manifolds. We argue, theoretically and experimentally, that this leads to higher clustering accuracy. We also pres…
We define a class of Euclidean distances on weighted graphs, enabling to perform thermodynamic soft graph clustering. The class can be constructed form the "raw coordinates" encountered in spectral clustering, and can be extended by means of higher-dimensional embeddings (Schoenberg transformations). Geographical flow …
Generating point clouds, e.g., molecular structures, in arbitrary rotations, translations, and enumerations remains a challenging task. Meanwhile, neural networks utilizing symmetry invariant layers have been shown to be able to optimize their training objective in a data-efficient way. In this spirit, we present an ar…
This paper addresses Gaussian Process regression over probability measures, revealing a non-stationarity issue between Euclidean and Wasserstein kernels.
problem Non-stationarity issue between Euclidean and Wasserstein kernels in Gaussian Process regression over probability measures.
method Assuming Euclidean input space, applying algebraic transformation based on uncovered non-stationarity relationship to create a non-stationary and Wasserstein-based Gaussian Process model.
result An algebraic transformation simplifies learning a non-stationary Gaussian Process model over probability measures.
The paper explores how different patterns of heterophily affect Graph Neural Networks.
problem Understanding the impact of heterophily on Graph Neural Networks.
method Theoretical analysis and experiments with Heterophilous Stochastic Block Models (HSBM).
result The impact of heterophily on classification depends on the Euclidean distance of neighborhood distributions and the averaged node degree.
The paper describes distances on Sol-type groups using novel geometric techniques.
problem Understanding distances on Sol-type groups.
method New technique of Euclidean curve surgery to describe uniformly roughly geodesic paths.
result The rough isometry type of distances on Sol-type groups is determined by a specific metric restriction.
The paper explores a new type of kernel using Wasserstein distance for better classification of shapes.
problem Improving kernel methods for shape classification.
method Defined and studied exponential kernels based on regularized Wasserstein distance.
result Wasserstein squared exponential kernels perform better on small shape datasets.
The study proves non-orientable surfaces can map to a torus.
problem Embedding non-orientable surfaces in 4D space.
method Proving mapping to a 2D torus for 2-convex surfaces.
result Projective plane and Klein bottle cannot be 2-convex in 4D space.
Enhances LDL by integrating distance and directional information for more robust label feature representation.
problem Lack of robust label feature representation in LDL tasks, especially with label ambiguity.
method Introduces Structural Anchor Points (SAPs) to capture inter-cluster interactions and a novel LSFs construction strategy, LIFT-SAP.
result Improves LDL performance by 15% on average across 15 real-world datasets.
Graph-based methods provide a powerful tool set for many non-parametric frameworks in Machine Learning. In general, the memory and computational complexity of these methods is quadratic in the number of examples in the data which makes them quickly infeasible for moderate to large scale datasets. A significant effort t…
APGD algorithm reconstructs point set from partial distance measurements.
problem Reconstructing point set configuration from partial Euclidean distance measurements.
method Asymmetric Projected Gradient Descent (APGD) for EDMC problem.
result Global convergence and exact recovery with O(μ2r3κ2nlogn) observations. Permutation invariant network learns Wasserstein metrics.
problem Understanding the space of probability measures and comparing distributions.
method Permutation invariant network mapping samples to a low-dimensional space.
result Network can generalize to compute distances between unseen densities and learn moments.
Stable density-based clustering via multiparameter persistence.
problem Density-based clustering stability to data perturbations.
method Degree-Rips construction, correspondence-interleaving distance, multiparameter stability analysis.
result Persistable pipeline yields stable, consistent density-based clustering.
In this paper we introduce three methods for re-scaling data sets aiming at improving the likelihood of clustering validity indexes to return the true number of spherical Gaussian clusters with additional noise features. Our method obtains feature re-scaling factors taking into account the structure of a given data set…
New bounds on cover degrees for Teichmüller distance between hyperbolic surfaces.
problem Finding optimal cover degrees for Teichmüller distance between hyperbolic surfaces.
method Proved the existence of a constant k>0 depending on M and N such that the covers MεoM and NεoN can be chosen to have degrees less than ε−k. result The bound ε−k is optimal for certain arithmetic Riemann surfaces. New method finds metrics on surfaces with prescribed curvatures using circle packings and surgery.
problem Finding piecewise Euclidean metrics on surfaces with prescribed combinatorial curvatures.
method Combinatorial curvature flows with surgery for inversive distance circle packings.
result Longtime existence and global convergence of combinatorial curvature flows with surgery.
Learning a distance function or metric on a given data manifold is of great importance in machine learning and pattern recognition. Many of the previous works first embed the manifold to Euclidean space and then learn the distance function. However, such a scheme might not faithfully preserve the distance function if t…
A fast binary embedding method preserves Euclidean distances in high-dimensional data.
problem Preserving Euclidean distances in high-dimensional datasets.
method Stable noise-shaping quantization of Ax with A a sparse Gaussian random matrix, followed by a linear transformation. result Euclidean distances are approximated by the ℓ1 norm on binary sequences, leading to accurate binary codes. The degree-d Chow parameters of a Boolean function f:{−1,1}n→R are its degree at most d Fourier coefficients. It is well-known that degree-d Chow parameters uniquely characterize degree-d polynomial threshold functions (PTFs) within the space of all bounded functions. In this paper, we prove …
A Euclidean (or hyperbolic) circle packing on a closed triangulated surface with prescribed inversive distance is locally determined by its cone angles. We prove this by applying a variational principle.
The class of Schoenberg transformations, embedding Euclidean distances into higher dimensional Euclidean spaces, is presented, and derived from theorems on positive definite and conditionally negative definite matrices. Original results on the arc lengths, angles and curvature of the transformations are proposed, and v…
Classifies rank-one submanifolds in Euclidean space.
problem Classifying submanifolds with singularities.
method Associate degree to ruled submanifolds and analyze singularities.
result An open and dense subset of rank-one submanifolds is the union of cylindrical, conical, and tangent regions.