CS Paper Radar

Orientation Estimation of Cryo-EM Images for Molecules with Arbitrary Symmetry by Semidefinite Programming

Yunpeng Shi, Amit Singer, Jinxin Wang, Ruiyi Yang

cs.CV math.NAmath.OC ·submitted 2026-10-13 16:43 UTC · v1

Abstract

This paper extends the non-unique games framework introduced in Bandeira et al. (2020) to address symmetric structures. Precisely, we consider the problem \[ \begin{aligned} \underset{g_1,\ldots,g_n\in \mathcal{G}}{\operatorname{min}}\,\, \frac{1}{|S|}\sum_{i,j=1}^n \sum_{s\in S} f_{ij}(g_i s g_j^{-1}), \end{aligned} \] where $\mathcal{G}$ is a compact group, $S\subset \mathcal{G}$ is a finite subgroup of symmetry elements, and $f_{ij}:\mathcal{G}\rightarrow \mathbb{R}$ is a loss function. A notable example is common lines based orientation estimation of cryo-EM images for molecules with point group symmetry $S$, where $\mathcal{G}$ is the rotation group $\operatorname{SO}(3)$. With a semidefinite programming relaxation, we turn the problem into a convex program that is solved with the alternating direction method of multipliers. Unlike existing approaches which are tailored to specific symmetry groups, ours provides a unified computational framework for addressing all point group symmetries. We demonstrate the applicability of the proposed algorithm on the cryo-EM orientation estimation problem on both simulated and experimental datasets. In particular, our algorithm is effective in generating high-quality ab initio models from only a few class averages computed from experimental images.

Closest papers

Nearest neighbours by meaning across the whole index.

Learning Operators for Symmetry Discovery: From Lie Groups to Local Symmetry Geometry

cs.LG ·2026-10-12 ·Pavan Karjol, Scindhiya Laxmi, Prathosh AP
theory similarity 0.61
Abstract

Continuous symmetry discovery is typically formulated as a separate estimation problem for each function or dataset. We instead investigate whether the map from a function to its symmetry structure can be learned across a family of functions from finite observations. Using the infinitesimal differential characterization of continuous symmetries, we formulate this map as an inverse symmetry operator, analogous to an inverse PDE problem. For global Lie-group symmetries, we establish a representation-theoretic population characterization: the symmetry Lie algebra is the nullspace of a positive-semidefinite operator constructed from representation coefficients and the infinitesimal group action. We also show that the inverse symmetry operator is equivariant under coordinate changes through the adjoint action. This characterization separates the geometric symmetry map from finite-sample estimation, motivating a hybrid approach that amortizes statistically difficult components while retaining analytic structure. On SO(5) benchmarks, amortized equivariant estimation of harmonic coefficients improves symmetry recovery from sparse observations, whereas ordinary least squares suffices for SL(2,R). We extend this viewpoint to local symmetries, where symmetry directions form smoothly varying tangent distributions rather than a fixed Lie algebra. Under the Lie-bracket consistency condition, Frobenius' theorem guarantees local integral submanifolds along which observables remain unchanged. We recover this geometry using a hybrid estimator that learns observation weights while preserving analytic differential and geometric recovery. Across global, non-compact, local, and physically motivated synthetic benchmarks, our results support learning the statistically difficult finite-sample components while preserving the known geometric structure of symmetry recovery.

0.13

Beyond Procrustes distances: a multilinear Gromov-Wasserstein distance capturing chirality

cs.LG math.OC ·2026-08-27 ·Clément Soubrier, Geoffrey Woollard, Andrew Warren, Khanh Dao Duc
similarity 0.56
Abstract · 57 pages, 6 figures

Efficiently and robustly analyzing shape data is critical across many scientific disciplines. While chirality is a fundamental property in numerous applications - most notably in molecular science - existing shape analysis metrics fail to distinguish between a shape and its mirror image. To address this gap, we introduce a multilinear generalization of the Gromov-Wasserstein objective. Under mild assumptions, this objective yields a distance between shapes, represented as probability distributions quotiented by a symmetry group $G$. In particular, for $G = SO(d)$, we introduce the Chiral Gromov-Wasserstein ($\mathrm{CGW}$) distance, sensitive to chirality. We establish robustness properties for the multilinear Gromov-Wasserstein distances and develop efficient algorithms to compute them, reformulating the underlying optimization problem by projecting couplings onto a low-dimensional space. We derive algorithms for both local and approximate global solutions, yielding a fully polynomial-time approximation scheme for these problems. We validate the framework through numerical experiments that demonstrate the effectiveness of $\mathrm{CGW}$ as a shape metric for chiral objects.

0.24

Efficient Learning and Symmetry Discovery under Exact Invariances

cs.LG stat.ML ·2026-09-07 ·Ashkan Soleymani, Behrooz Tahmasebi, Patrick Jaillet, Stefanie Jegelka
top venuehighly cited similarity 0.56
Abstract · 29 pages. Published at COLT 2026

Learning with group invariances is central to many scientific and geometric learning problems, yet its computational foundations remain poorly understood. Even for classical supervised regression settings, it has been unclear whether one can efficiently compute a regression function that is exactly invariant to a given group action. Recent work showed that exact invariance can be enforced in polynomial time when the underlying group is finite and known, but left open the cases of infinite groups and unknown symmetries. In this paper, we resolve both challenges. First, we present the first polynomial-time algorithm for learning with exact group invariances that applies uniformly to finite and infinite groups. The runtime is polynomial in the data dimension and sample size, and independent of the group, while achieving strong generalization guarantees. This provides a computational explanation for the empirical success of invariant and equivariant methods in geometric machine learning and partially answers a recent open question in the literature. Second, we study learning in the symmetry discovery setting, where the invariance group is unknown. Focusing on the subgroup lattice of a finite group, we show that exact symmetries can be identified from data and exploited for learning in polynomial time. For regression over finite-dimensional feature spaces, our algorithm provably recovers the underlying symmetry, matches the minimax-optimal sample complexity of the known-symmetry setting, and runs in time polynomial in the data dimension and sample size. Our analysis relies on tools from random Cayley graphs and expander theory, which may be of independent interest.

0.78

Enforcing Symmetries on Pre-trained ML Models for Physics

cs.LG physics.comp-phstat.ML ·2026-11-06 ·Wenjie Zhou, Valentino F. Foit, David W. Hogg, Soledad Villar
similarity 0.55
Abstract · 32 pages, 5 figures, 9 tables

Post-hoc group averaging (or test-time augmentation) is a simple way to impose symmetry on a trained predictor without changing its architecture or retraining it. For finite and compact groups, averaging over a normalized Haar measure on the group gives the Reynolds operator: a canonical projection onto invariant or equivariant predictors with known non-increasing risk guarantees under certain assumptions. This paper provides numerical experiments on physics emulation models that demonstrate the effectiveness of the approach in this setting. We then extend this framework to non-compact group symmetries. For non-compact groups, the Haar measure cannot be normalized, so group averaging cannot be defined in the same way. We replace it with three alternatives: the Weyl unitary trick (which requires complexifying the space and extending the predictor), a data-dependent orthogonal projection (which involves a non-trivial optimization on the space of invariant or equivariant functions), and a frame averaging approach (which involves mapping each point to a set of orbit representatives). We illustrate the constructions theoretically and empirically on the unit-rescaling group and the Lorentz group. Our results show that in the non-compact case, the Weyl trick and frame averaging do not provide a consistent improvement over the baseline, except where the test data is out-of-distribution (an orders-of-magnitude improvement in this case) and, for the Weyl trick, in low-data regimes. The orthogonal projection can provide improvements in-distribution and out-of-distribution. We also observe that models trained directly on invariant features matched or beat the projection of an unconstrained one. We conclude that post-hoc symmetrization extends to non-compact groups, but it does not consistently outperform training a symmetric model.

0.50

A $G$-Invariant Erdős--Hanani Theorem with Applications to Optical Orthogonal and Constant-Weight Codes

cs.IT math.CO ·2026-10-07 ·Yeow Meng Chee
theory similarity 0.53
Abstract · 16 pages, 1 table

Let $k>t\ge 2$ be fixed integers, and let $G$ be a permutation group on a set of $v$ points. A $G$-invariant packing is free if every block has $|G|$ distinct images under $G$. We give two conditions on $G$ under which, as $v\to\infty$, there is a free $G$-invariant $t$-$(v,k,1)$ packing with $(1-o(1))\binom{v}{t}/\binom{k}{t}$ blocks. This is a $G$-invariant form of the Erdős--Hanani theorem on asymptotically optimal packings. For semiregular groups $G$, packings with these properties exist if and only if all but $o(v^t)$ of the $t$-subsets of points have trivial setwise stabiliser. This property is satisfied by every semiregular group for $t\ge 3$, and by every cyclic semiregular group for $t=2$. As a consequence, the Johnson bound is asymptotically attained at all lengths by optical orthogonal codes of constant weight $w$ and constant correlation $λ$ with $w\geλ+2$, by their multidimensional and signature pattern versions, and by cyclic and quasi-cyclic constant-weight codes. The same method gives a form of the theorem for group divisible packings that are invariant under a cyclic group. This determines the asymptotic maximum size of two-dimensional optical orthogonal codes with at most one pulse per wavelength.

0.28

Rubix: Global Correspondence-Free Point Set Alignment through Assignment Geometry

cs.CV cs.CGcs.LGcs.RO+1 ·2026-10-07 ·Subhransu S. Bhattacharjee, Dylan Campbell, Rahul Shome
theory similarity 0.53
Abstract · 67 pages, 20 figures. Includes full proofs and experimental appendices

Procrustes-Wasserstein alignment jointly estimates a matching and rotation without supplied correspondences, but alternating minimization can stop at suboptimal solutions. Rubix solves the equally weighted planar problem globally under squared Euclidean loss. Each matching $σ$ of two centered $n$-point sets defines a complex correlation $z_σ=\sum_i\bar x_i y_{σ(i)}$. Their convex hull is the permutation polygon: supporting vertices give optimal matchings at fixed rotations, and the farthest vertex gives the global alignment. We prove the sharp bound of $n(n-1)$ vertices for $n\ge2$, answering Rote's rotation-assignment open problem. In exact arithmetic, assignment queries recover the polygon in $\mathcal O(n^5)$ operations. Assignment-based bounds extend the approach to three-dimensional rotations and partial matching at a supplied translation through branch-and-bound. On timed MPEG-7 shape pairs, Rubix attains every numerical reference value in 12 ms on average, 50 times faster than a rotation grid at the same accuracy. Its distances improve gravity-aligned matching of real 3D scans, shape retrieval and noisy crystal classification over alternating minimization.

0.25

FAST-Sync: Fast Group Synchronization for any Matrix Lie Group

cs.RO ·2026-09-29 ·Shane Holmes, Yiran Luo, Firat Taxpulat, David M. Rosen, Frank Dellaert
top venue similarity 0.53
Abstract · 8 pages, 10 figures, 1 table

Group synchronization (GS) is the problem of estimating a set of $N$ unknown elements $g_1,\ldots, g_N \in \mathcal{G}$ in a group $\mathcal{G}$, given noisy measurements of a subset of their pairwise ratios $g_i^{-1} g_j$. GS problems lie at the core of many state estimation tasks in robotics and computer vision, including 3D vision, robotic mapping, inertial navigation, and molecular reconstruction. Unfortunately, GS problems are typically both high-dimensional and non-convex, and therefore hard to solve in general. In this paper, we present Fast-Sync, a fast linear approximation method for GS that is suitable for initializing local manifold-based optimizers or certifiable global methods. Our approach generalizes chordal initialization to arbitrary matrix Lie groups, and additionally proposes two new key algorithmic enhancements: we show how to exploit both the Kronecker-product structure in the problem data matrix and the topology of the synchronization graph to improve speed, scalability, and accuracy. Experimental evaluation across several GS tasks demonstrates that Fast-Sync provides high-quality initializations that enable local optimizers to efficiently recover globally optimal GS solutions, achieving high success rates even with considerable measurement noise.

0.69

Learning a Group Element from Its Action: Galois Correspondences, Optimal ERM, and an Abel-Ruffini Threshold for the Natarajan Dimension

cs.LG math.GRstat.ML ·2026-10-13 ·Xiaoyu Li
theory similarity 0.51
Abstract · 55 pages, 5 figures. The abstract has been shortened to meet arXiv's submission requirements

We study learning an unknown element $g$ of a group acting with finite orbits on a countable set, from examples $(x,gx)$. After a sample on $A$, the consistent hypotheses are the restrictions of a coset of the pointwise stabilizer of $A$, and the sample forces exactly the labels of points this stabilizer fixes; for a Galois group, they form the field generated by the data. Through this correspondence, multiclass dimensions become group invariants: the DS and graph dimensions equal the height, the Littlestone dimension the longest irredundant sequence length, and the teaching dimension the minimal base size. Among deterministic learners, symmetry makes empirical risk minimization optimal: on nondegenerate classes every consistent learner, whatever its tie-breaking, attains the optimal realizable sample complexity up to constant factors, and every consistent online learner the optimal mistake bound. Agnostically, every ERM's sample complexity exceeds the known lower bound by at most the DS-to-Natarajan ratio, up to constants. For finite Galois extensions of countable fields, the Natarajan dimension equals a group invariant, the coset-cube number, which is at least the number of complemented factors of any chief series of any subgroup. Hence the dimensions coincide for every solvable Galois group, while for the groups $A_5$ and $S_5$ of the quintic they are $2<3$ and $3<4$, and $A_5$ is the smallest group with a gap. For the Galois group $S_n$ of the general equation of degree $n$, they coincide exactly when $n\le 4$, i.e., in characteristic zero, exactly when the equation is solvable by radicals; the implication is one-way, as the simple group $\mathrm{PSL}(2,8)$ has no gap. For linear, orthogonal and unitary maps of $\mathbb R^d$ or $\mathbb C^d$ both dimensions equal $d$, and a two-fibered pseudo-cube is a disjoint union of Natarajan cubes exactly when its monodromy group is abelian.

0.25