In this paper we demonstrate how the geometrically motivated algorithm to determine whether a two generator real Mobius group acting on the Poincare plane is or is not discrete can be interpreted as a non-Euclidean Euclidean algorithm. That is, the algorithm can be viewed as an application of the Euclidean division alg…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,742 papers · 148 categories
Trend · papers per month
48 results for “Euclidean algorithm”
This paper proposes a spectral clustering algorithm for hyperbolic spaces, improving efficiency over Euclidean methods.
problem Inefficient clustering in Euclidean spaces for complex data structures.
method Developed a spectral clustering algorithm using hyperbolic similarity matrices.
result The algorithm converges at least as fast as Euclidean spectral clustering and performs better on complex datasets.
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 paper discusses algorithms for reconstructing curves with given Euclidean or affine curvatures.
problem Reconstructing planar curves with specified Euclidean or affine curvatures.
method The paper presents algorithms for curve reconstruction under the special Euclidean and equi-affine groups.
result The reconstructed curves are close to the original curves in terms of the specified curvatures.
A new optimization method handles Euclidean bounds efficiently.
problem Optimization problems with Euclidean bounds.
method Riemannian limited-memory BFGS method combining quasi-Newton and Riemannian adaptations.
result Outperforms existing methods by several orders of magnitude.
New method turns optimization algorithms into uniformly stable learning algorithms for non-Euclidean norms.
problem Non-Euclidean norms in binary classification problems.
method Black-box reduction method using uniformly convex regularizers.
result Achieves optimal statistical risk bounds on excess risk for non-Euclidean norms.
New approach uses isotropic geometry to solve Euclidean problems.
problem Solving systems of constraints in Euclidean geometry.
method Start with analogous problems in isotropic geometry to initialize optimization algorithms.
result Solutions in isotropic geometry provide insight and initialize Euclidean problem solutions.
A new algorithm simplifies number theory and geometry problems.
problem Constructing explicit Dirichlet domains for Kleinian subgroups.
method Generalized Euclidean algorithm for rings with involution.
result Orders with the algorithm have class number 1.
An Algorithm to perform Covariance-Adjusted Support Vector Classification in Non-Euclidean Spacescs.LG
Algorithm improves SVM classification in non-Euclidean spaces.
problem Limitations of traditional SVM in non-Euclidean spaces.
method Covariance-adjusted SVM using Cholesky Decomposition.
result Cholesky-SVM outperforms traditional SVM in non-Euclidean spaces.
Improves hierarchical clustering in Euclidean space using autoencoders.
problem Lack of unsupervised methods for learning hierarchical structure in Euclidean space.
method Variational autoencoder with Gaussian mixture prior, rescaling latent space, and Ward's linkage.
result Improved dendrogram purity and Moseley-Wang cost function results.
Non-Euclidean BPM extends optimization theory to non-Euclidean norms.
problem Extending BPM's convergence theory to non-Euclidean norms.
method Iteratively minimizing over norm balls in non-Euclidean geometry.
result Most BPM guarantees carry over to non-Euclidean norms.
Unified framework for non-Euclidean CPD under scalable stochastic mirror descent.
problem Handling non-Euclidean losses in tensor decomposition.
method Tensor fiber sampling strategy-based stochastic mirror descent.
result Global convergence to a stationary point under reasonable conditions.
An algorithm for the Euclidean cell decomposition of a cusped strictly convex projective surfacemath.GT
Cooper and Long generalised Epstein and Penner's Euclidean cell decomposition of cusped hyperbolic manifolds of finite volume to non-compact strictly convex projective manifolds of finite volume. We show that Weeks' algorithm to compute this decomposition for a hyperbolic surface generalises to strictly convex projecti…
Estimates modes and ridges in mixed Euclidean and directional spaces.
problem Estimating local modes and density ridges in product spaces combining Euclidean and directional metrics.
method Extends mean shift algorithm to product spaces, addressing challenges in generalization.
result Established convergence of the proposed methods and demonstrated effectiveness on real-world datasets.
We construct a Kirby diagram of the rational homology ball used in "generalized rational blow-down" developed by Jongil Park. The diagram consists of a dotted circle and a torus knot. The link is simpler, but the parameters are a little complicate. Euclidean Algorithm is used three times in the construction and the pro…
New algorithms optimize convex functions with high-order derivatives.
problem Optimizing convex functions with high-order derivatives under various norms.
method Developed a non-Euclidean inexact accelerated proximal point method using an inexact uniformly convex regularizer.
result Showed nearly optimal algorithms for high dimensions in the black-box oracle model for -settings and all .
Adaptive step-size improves optimization in complex geometries.
problem Optimizing functions with non-Euclidean geometries.
method Adaptive step-size strategy for optimization algorithms.
result Guaranteed convergence for Adaptive Conditional Gradient Descent.
Riemannian algorithms converge at Euclidean rates for geodesically convex-concave problems.
problem Min-max optimization on Riemannian manifolds.
method RCEG method and RGDA for geodesically strongly-convex-concave problems.
result RCEG achieves linear convergence rate in geodesically strongly-convex-concave cases.
A hyperbolic space has been shown to be more capable of modeling complex networks than a Euclidean space. This paper proposes an explicit update rule along geodesics in a hyperbolic space. The convergence of our algorithm is theoretically guaranteed, and the convergence rate is better than the conventional Euclidean gr…
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…
New optimization method combines gradient clipping and non-Euclidean smoothness.
problem Improving optimization in non-Euclidean spaces for machine learning.
method Hybrid of steepest descent and conditional gradient, incorporating weight decay.
result Achieves optimal convergence rate and demonstrates effectiveness in deep learning.
Paper improves SOMs for non-Euclidean data modeling.
problem Traditional SOMs assume Euclidean data, limiting their applicability.
method Introduces topology-related extensions to traditional SOM algorithm.
result Improves SOMs for non-Euclidean data, enhancing data modeling.
Fibered simple knotsmath.GT
Simple knots in lens spaces fiber if their order doesn't divide certain Euclidean remainders.
problem Characterizing fibered simple knots in lens spaces.
method Direct, combinatorial, and geometric methods.
result Conditions for fibered simple knots in lens spaces are determined.
New algorithm for nonconvex optimization on constrained Riemannian manifolds converges quickly.
problem Optimization on constrained Riemannian manifolds.
method Block majorization-minimization (BMM) for smooth nonconvex objectives with Riemannian constraints.
result Converges to stationary points within iterations.
Paper proves linear convergence of SCMS algorithm for directional data.
problem Identifying density ridges in directional data.
method Generalized SCMS algorithm to directional data, derived from SCGA with adaptive step size.
result Linear convergence of the proposed directional SCMS algorithm.
Fast convergence of the Expectation Maximization algorithm under a logarithmic Sobolev inequalitystat.ML
New framework improves EM algorithm convergence under log-Sobolev inequality.
problem Improving convergence of the EM algorithm.
method Extending gradient flow techniques to EM algorithm, using free energy representation.
result Exponential convergence of EM algorithm under log-Sobolev inequality.
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 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…
New findings show Bregman proximal algorithms can get stuck near non-stationary points.
problem Bregman proximal algorithms can get stuck near non-stationary points, misleadingly suggesting convergence.
method Analysis of Bregman proximal algorithms and their behavior near non-stationary points.
result Bregman proximal algorithms can get stuck near spurious stationary points, even in convex problems.
An Objective for Hierarchical Clustering in Euclidean Space and its Connection to Bisecting K-meanscs.LG
Paper develops a new objective for hierarchical clustering in Euclidean space.
problem Hierarchical clustering in Euclidean space with dissimilarity scores.
method Develops a new global objective and connects it to bisecting k-means.
result Optimal 2-means solution approximates the new objective, proving bisecting k-means optimizes a natural global objective.
We introduce an approach based on moving frames for polygon recognition and symmetry detection. We present detailed algorithms for recognition of polygons modulo the special Euclidean, Euclidean, equi-affine, skewed-affine and similarity Lie groups, and explain the procedure for a generic Lie group. The time complexity…
FastMap-D embeds directed graphs using potential fields.
problem Embedding directed graphs in Euclidean space.
method Generalization of FastMap to handle directed graphs using a potential field and machine learning.
result FastMap-D outperforms other approaches in embedding directed graphs.
Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Timecs.LG
New algorithm achieves optimal privacy and efficiency in non-Euclidean convex optimization.
problem Optimizing convex functions while maintaining privacy in non-Euclidean settings.
method Developed a linear-time algorithm for -setups, leveraging geometric properties.
result Optimal excess risk achieved in linear time for .
Optimizes Euclidean functions on Riemannian manifolds with warped metrics.
problem Optimizing functions in high-dimensional Euclidean spaces.
method Riemannian geometry, warped metric, geodesic curves, Taylor approximations, retraction maps.
result Efficient optimization of functions using third-order approximations of geodesics.
Finding the diameter of a dataset in multidimensional Euclidean space is a well-established problem, with well-known algorithms. However, most of the algorithms found in the literature do not scale well with large values of data dimension, so the time complexity grows exponentially in most cases, which makes these algo…
Study on private algorithms for saddle point and variational inequalities, improving efficiency and applicability.
problem Private algorithms for solving saddle point and variational inequalities under differential privacy constraints.
method Developed a recursive regularization algorithm for both Euclidean and non-Euclidean setups, providing bounds on strong SP-gap and VI-gap.
result Achieved nearly optimal rates for strong SP-gap and VI-gap under -differential privacy, applicable to various setups.
In order to cope with the increased data volumes generated by modern radio interferometers such as LOFAR (Low Frequency Array) or SKA (Square Kilometre Array), fast and efficient calibration algorithms are essential. Traditional radio interferometric calibration is performed using nonlinear optimization techniques such…
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.
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…
Topolow embeds dissimilarity data into Euclidean space robustly against non-metricity and sparsity.
problem Embedding dissimilarity data into Euclidean space when dissimilarities are non-metric or sparse.
method Topolow uses a physics-inspired, gradient-free optimization framework to maximize likelihood under a Laplace error model.
result Topolow outperforms standard MDS methods in reconstructing sparse and non-Euclidean data.
In this paper, we consider the problem of fast and efficient indexing techniques for sequences evolving in non-Euclidean spaces. This problem has several applications in the areas of human activity analysis, where there is a need to perform fast search, and recognition in very high dimensional spaces. The problem is ma…
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.
We provide an elementary proof of a simple, efficient algorithm for computing the Euclidean projection of a point onto the probability simplex. We also show an application in Laplacian K-modes clustering.
A simple method makes Euclidean patterns look like Escher's art.
problem Transforming Euclidean patterns into Circle Limit-style art.
method A simple, parallelizable algorithm using conformal maps.
result A simple method is highly efficient and can be parallelized.
EF21-Muon optimizes deep learning with error feedback, improving efficiency and accuracy.
problem Lack of principled distributed frameworks for non-Euclidean LMO-based optimizers.
method Introduces EF21-Muon, a communication-efficient, non-Euclidean LMO-based optimizer with convergence guarantees.
result First efficient distributed implementation of non-Euclidean LMO-based optimizers, achieving up to 7x communication savings.
The last decade has witnessed an explosion in the development of models, theory and computational algorithms for "big data" analysis. In particular, distributed computing has served as a natural and dominating paradigm for statistical inference. However, the existing literature on parallel inference almost exclusively …
Combinatorial curvature flows with surgery for inversive distance circle packings on surfacesmath.DG
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.
Ray-marching method visualizes 8 Thurston geometries in real-time.
problem Accurately rendering and visualizing Thurston geometries in real-time.
method Ray-marching algorithms with theoretical framework for non-Euclidean geometries.
result Accurate interactive real-time views of Thurston geometries achieved.