Study optimizes estimation of orthogonal and rotation matrices from noisy data.
problem Estimating orthogonal and rotation matrices from noisy data.
method Iterative polar decomposition algorithm initialized by spectral methods.
result Algorithm achieves optimal error rate of $(1+o(1)) rac{σ^2 d(d-1)}{2np}$.
Spectral methods achieve near-optimal performance in orthogonal and permutation group synchronization.
problem Recovering group elements from pairwise measurements in computer vision.
method Spectral methods applied with the leave-one-out technique.
result Near-optimal performance bounds for orthogonal and permutation group synchronization established.
Spectral method for joint community detection and group synchronization.
problem Jointly detecting communities and synchronizing orthogonal groups in graphs.
method Spectral decomposition followed by CPQR factorization.
result Near-optimal guarantees for exact and stable recovery of cluster memberships and orthogonal transforms.
NS-RGS improves orthogonal group synchronization with faster convergence.
problem Orthogonal group synchronization from pairwise measurements.
method Newton-Schulz iteration for Riemannian gradient optimization.
result NS-RGS achieves linear convergence and near-optimal accuracy.
Paper addresses group synchronization with incomplete measurements and proves linear convergence of GPM.
problem Orthogonal group synchronization with incomplete measurements and additive noise.
method Generalized power method (GPM) with local error bound analysis.
result Linear convergence of GPM to a global maximizer under general additive noise model.
Novel higher-order group synchronization for noisy local measurements on hypergraphs.
problem Synchronizing higher-order local measurements on hyperedges to global estimates on nodes.
method Message passing algorithm for global synchronization of higher-order measurements.
result Higher-order method outperforms standard pairwise synchronization methods in certain applications.
New method solves group synchronization with cycle-edge message passing.
problem Solving group synchronization with adversarial or uniform corruption and small noise.
method Cycle-edge message passing procedure using cycle consistency information.
result Exact recovery and linear convergence guarantees under adversarial corruption.
New method uses neural networks for accurate angle estimation in noisy conditions.
problem Accurately estimate angles from noisy measurements in various applications.
method Directed Graph Neural Networks (GNNSync) for end-to-end trainable framework.
result GNNSync achieves competitive performance, even at high noise levels.
Efficiently estimates rotations with corrupted data.
problem Rotation synchronization under high corruption and noise.
method Message passing algorithm with reweighted least squares.
result Superior performance over state-of-the-art methods.
Transitive consistency is an intrinsic property for collections of linear invertible transformations between Euclidean coordinate frames. In practice, when the transformations are estimated from data, this property is lacking. This work addresses the problem of synchronizing transformations that are not transitively co…
Novel method solves group synchronization with robust corruption tolerance.
problem Group synchronization with high corruption tolerance.
method Quadratic programming formulation exploiting cycle consistency.
result Global minimum recovers corruption levels under mild conditions.
Paper proposes GPM for simultaneous community detection and group synchronization.
problem Simultaneous community detection and group synchronization in networks.
method Generalized Power Method (GPM) for non-convex optimization.
result GPM achieves exact recovery in O(nlog2n) time, outperforming SDP. Extends angular synchronization to heterogeneous groups, improving accuracy in multiple applications.
problem Recovering angles from noisy pairwise measurements in a heterogeneous setting.
method Probabilistic generative model and spectral algorithm with robustness analysis.
result Spectral algorithm provides improved recovery accuracy in various parameter regimes.
Adapts pivoting technique to circle homeomorphisms for proofs.
problem Probabilistic Tits alternative and exponential synchronization.
method Adapts Gou{ë}zel's pivoting technique.
result Different proofs of probabilistic Tits alternative and exponential synchronization.
Study isotropy groups for complex orthogonal and skew-symmetric matrices.
problem Understanding isotropy subgroups of orthogonal similarity transformations.
method Analysis of group structure of nonsingular block matrices.
result Group structure of isotropy subgroups related to block Toeplitz matrices.
DS-Sync improves distributed DNN training efficiency by 94% with minimal accuracy loss.
problem Network bottlenecks in distributed DNN training.
method Divide workers into non-overlapping groups for independent synchronization, then shuffle workers among groups iteratively.
result DS-Sync achieves up to 94% improvement in training time with minimal accuracy loss.
The present paper considers distributed consensus algorithms that involve N agents evolving on a connected compact homogeneous manifold. The agents track no external reference and communicate their relative state according to a communication graph. The consensus problem is formulated in terms of the extrema of a cost f…
Various alignment problems arising in cryo-electron microscopy, community detection, time synchronization, computer vision, and other fields fall into a common framework of synchronization problems over compact groups such as Z/L, U(1), or SO(3). The goal of such problems is to estimate an unknown vector of group eleme…
In this paper, we show synchronization for a group of output passive agents that communicate with each other according to an underlying communication graph to achieve a common goal. We propose a distributed event-triggered control framework that will guarantee synchronization and considerably decrease the required comm…
Detects synchronized behavior in streaming data.
problem Tracking synchronized behavior in time-stamped tuples.
method AugSplicing algorithm for streaming dense block detection.
result Effective and robust in detecting anomalous behavior.
We consider the classic problem of establishing a statistical ranking of a set of n items given a set of inconsistent and incomplete pairwise comparisons between such items. Instantiations of this problem occur in numerous applications in data analysis (e.g., ranking teams in sports data), computer vision, and machine …
Formula for Laplace-Beltrami on orthogonal group in Euclidean coords.
problem Computing Laplace-Beltrami on constrained submanifolds.
method Embedded gradient vector field method, explicit formula derivation.
result Explicit formula for Laplace-Beltrami on orthogonal group.
A Lie group is called orthogonal if it carries a bi-invariant pseudo Riemannian metric. Oscillator Lie groups constitutes a subclass of the class of orthogonal Lie groups. In this paper, we determine the Lie bialgebra structures and the solutions of the classical Yang-Baxter equation on a generic class of oscillator Li…
Algorithm finds isotropy subgroups of orthogonal similarity on symmetric matrices.
problem Computing isotropy subgroups of orthogonal similarity on symmetric matrices.
method Algorithmic procedure solving a Toeplitz matrix equation.
result Structure of isotropy subgroups described.
Computes isotropy subgroups of orthogonal matrices acting on Hermitian matrices.
problem Computing isotropy subgroups of orthogonal matrices acting on Hermitian matrices.
method Algorithm for solving a matrix equation to compute isotropy subgroups.
result Computed isotropy subgroups of orthogonal matrices acting on Hermitian matrices.
Integrable geodesics found on special orthogonal group.
problem Analyzing normal geodesics on the special orthogonal group.
method Adapted Lax pair and bi-Hamiltonian structure.
result Almost all normal geodesics are completely integrable.
We introduce a novel approach to perform first-order optimization with orthogonal and unitary constraints. This approach is based on a parametrization stemming from Lie group theory through the exponential map. The parametrization transforms the constrained optimization problem into an unconstrained one over a Euclidea…
We prove that a polar orthogonal representation of a real reductive algebraic group has the same closed orbits as the isotropy representation of a pseudo-Riemannian symmetric space. We also develop a partial structural theory of polar orthogonal representations of real reductive algebraic groups which slightly generali…
We construct an explicit topological model (similar to the topological Springer fibers appearing in work of Khovanov and Russell) for every two-row Springer fiber associated with the even orthogonal group and prove that the respective topological model is homeomorphic to its corresponding Springer fiber. This confirms …
New optimization algorithms on orthogonal group for machine learning.
problem Efficient optimization on the orthogonal group for machine learning tasks.
method Stochastic geometric algorithms on Lie groups.
result Strong performance on diverse machine learning tasks.
Paper derives local Plücker formulas for special orthogonal groups.
problem Deriving Plücker formulas for special orthogonal groups.
method Reduction to classical A_n case.
result Local Plücker formulas for special orthogonal groups derived.
An algorithm for efficient computation of equivariant neural network layers.
problem Efficiently computing with Brauer's group equivariant neural network layers.
method Category theoretic constructions and Kronecker product matrices.
result Significant reduction in computational cost compared to naive implementation.
We study the Chern-Simons partition function of orthogonal quantum group invariants, and propose a new orthogonal Labastida-Mariño-Ooguri-Vafa conjecture as well as degree conjecture for free energy associated to the orthogonal Chern-Simons partition function. We prove the degree conjecture and some interesting cases o…
In every dimension n≥3 we introduce a class of orthogonal graph-manifolds and prove that the fundamental group of any orthogonal graph-manifold quasi-isometrically embeds into a product of n trees. As a consequence, we obtain that asymptotic and linearly-controlled asymptotic dimensions of such group are equal t…
Compact holonomy groups found in symmetric spaces.
problem Characterizing holonomy groups in symmetric spaces.
method Analyzing the holonomy group structure of locally symmetric spaces.
result Holonomy groups are compact and have finite index in the orthogonal group.
The space Z of leftinvariant orthogonal almost complex structures, keeping the orientation, on 6-dimensional Lie groups is researched. To get explicit view of this space elements the isomorphism of Z and CP3 is used. The explicit formula for arbitrary leftinvariant orthogonal almost …
Curious structure of special orthogonal, unitary, and symplectic groups as products of Grassmannians discovered.
problem Understanding the structure of special orthogonal, unitary, and symplectic groups.
method Expressing these groups as products of Grassmannians realized as involution matrices.
result Special orthogonal, special unitary, and symplectic groups can be expressed as products of their corresponding Grassmannians.
The sectoral synchronization observed for the Japanese business cycle in the Indices of Industrial Production data is an example of synchronization. The stability of this synchronization under a shock, e.g., fluctuation of supply or demand, is a matter of interest in physics and economics. We consider an economic syste…
Hybrid approach for large-scale network synchronization using KF and PTP.
problem Synchronization of large-scale networks in 5G.
method Combines Kalman Filtering and PTP for pairwise synchronization, and Factor Graphs and Belief Propagation for end-to-end synchronization.
result Error in offset estimation remains below 5 ns in simulations.
New algorithm improves PPS for multi-object matching.
problem Efficiently synchronize partial permutations for multi-object matching.
method Proposed CEMP-Partial algorithm for partial permutation synchronization (PPS). Uses sparse matrix operations and nonconvex weighted projected power method.
result Proves CEMP-Partial can exactly classify corrupted and clean partial permutations under adversarial corruption.
We analyze how an observer synchronizes to the internal state of a finite-state information source, using the epsilon-machine causal representation. Here, we treat the case of exact synchronization, when it is possible for the observer to synchronize completely after a finite number of observations. The more difficult …
New Einstein metrics found on orthogonal groups without natural reductivity.
problem Finding non-naturally reductive Einstein metrics on orthogonal groups.
method Using real flag manifolds and symmetry assumptions on left-invariant metrics.
result Obtained new invariant Einstein metrics on $\SO(n)$.
Characterizes group-equivariant neural networks for three groups.
problem Understanding equivariant neural networks for orthogonal, special orthogonal, and symplectic groups.
method Characterized all possible group-equivariant neural networks for three groups.
result Found spanning sets of matrices for learnable, linear equivariant layer functions.
In this paper we study contact structure on 2-step nilpotent, Heisenberg type Lie groups. We decompose this Lie groups to center and orthogonal complement, then investigate properties of both orthogonal Lie subgroups. Finally, we provide a connection between matchings in groups and field extensions and 2-step nilpotent…
New method explains computational barriers in high-dimensional statistical models.
problem Understanding detection-recovery gaps in high-dimensional inference.
method Combining algorithmic contiguity and cross-validation reduction to obtain conditional computational lower bounds.
result Mild control of low-degree advantage is sufficient to explain computational barriers for recovery.
New measures on orbit spaces for orthogonal groups identified.
problem Characterizing measures on orbit spaces of orthogonal groups.
method Constructing Hilbert measures on orbit spaces of coregular representations of orthogonal groups.
result Hilbert measures have singularities if and only if the number of copies equals the dimension.
New algorithm uses PSO to optimize DNN training parameters in distributed systems.
problem Reducing synchronization frequency in DNN training leads to poor convergence.
method Integrates PSO into distributed training to automatically compute new parameters.
result Proposed algorithm outperforms synchronous methods in distributed DNN training.
ShadowSync separates background synchronization for scalable distributed training.
problem Reducing synchronization overhead in distributed training for high scalability.
method Separates synchronization from training and runs it in the background.
result Achieves both high throughput and excellent model quality at scale.