Polynomial-Time Optimal Group Selection via the Double-Commutator Eigenvalue Problem

Mitchell A. Thornton

cs.LGApr 4, 2026

Polynomial-Time Optimal Group Selection via the Double-Commutator Eigenvalue Problem

Authors: Mitchell A. Thornton

Organizations: Richardson, TX 75080 USA

Abstract

The algebraic diversity framework generalizes temporal averaging over multiple observations to algebraic group action on a single observation for second-order statistical estimation. The central open problem in this framework is $\textit{group selection}$ : given an $M$ -dimensional observation with unknown covariance structure, find the finite group whose spectral decomposition best matches the covariance. Naive enumeration of all subgroups of the symmetric group $S_M$ requires exponential time in $M$ . We prove that this combinatorial problem reduces to a generalized eigenvalue problem derived from the double commutator of the covariance matrix, yielding a polynomial-time algorithm with complexity $O(d^2M^2 + d^3)$ , where $d$ is the dimension of a generator basis. The minimum eigenvector of the double-commutator matrix directly constructs the optimal group generator in closed form, with no iterative optimization. The reduction is exact: the double-commutator minimum eigenvalue is zero if and only if the optimal generator lies in the span of the basis, and its magnitude provides a certifiable optimality gap when it does not. This problem does not appear in the standard catalogs of computational complexity (Garey and Johnson, 1979) and represents a new class linking group theory, matrix analysis, and statistical estimation. We establish connections to independent component analysis (JADE), structured matrix nearness problems, and simultaneous matrix diagonalization, and we show that the double-commutator formulation is the unique approach that is simultaneously polynomial-time, closed-form, and certifiable. We extend the framework to non-Abelian symmetry recovery via a Sequential GEVP with deflation, and add two identifiability theorems characterizing the commutant-lattice ambiguity and the dichotomy on whether $\mathrm{Aut}(\mathbf{R})$ recovers a generative subgroup or only a supergroup.

Figures & tables

Method	Complexity	Cert.
Enumerate $S_{M}$	$O(M!\cdot M^{2})$	Yes
Library search	$O(\|\mathcal{G}\|\cdot M^{3})$	No
Spectral conc. $\psi$	$O(\|\mathcal{G}\|\cdot M^{3})$	No
JADE (4th-order)	$O(M^{4})$	No
Simult. diag. (Jacobi)	$O(M^{3}\cdot\text{iter})$	No
DC-GEVP (ours)	$O(d^{2}M^{2}+d^{3})$	Yes

Table 1: Complexity of group selection methods

Panel of Figure 1 — Figure 1: Single-generator DC-GEVP graph automorphism identification (Part 1). Commutativity residual $\delta$ for five generic permutation generators on three graphs: cycle $C_{6}$ ( $D_{6}$ , $|\mathrm{Aut}|=12$ ), complete $K_{4}$ ( $S_{4}$ , $|\mathrm{Aut}|=24$ ), and path $P_{6}$ ( $\mathbb{Z}_{2}$ , $|\mathrm{Aut}|=2$ ). Green bars: generators that are graph automorphisms ( $\delta=0$ ). Red bars: non-automorphisms ( $\delta>0$ ). The minimum- $\delta$ generator is an automorphism in every case shown. No graph-specific information is used. The single-generator DC-GEVP identifies one automorphism per graph; full $\mathrm{Aut}(\mathcal{G})$ recovery for the non-Abelian-symmetry cases ( $C_{6}$ and $K_{4}$ ) is the subject of the Sequential GEVP (Algorithm 2 , Section 8 ).

Panel of Figure 2 — Figure 2: Single-generator DC-GEVP graph automorphism identification (Part 2). Triangular prism ( $D_{6}$ , $|\mathrm{Aut}|=12$ ), complete $K_{3}$ ( $S_{3}$ , $|\mathrm{Aut}|=6$ ), and star $S_{5}$ ( $S_{4}$ , $|\mathrm{Aut}|=24$ ). The pattern is consistent: at least one automorphism is identified with $\delta=0$ , non-automorphisms have $\delta>0$ , and the separation is unambiguous in every case. This validates the Automorphism Characterization Theorem constructively at the single-generator level. All three graphs have non-Abelian automorphism groups, so the discovered generator is one element of an $\mathrm{Aut}(\mathcal{G})$ whose full description requires multiple non-commuting generators; full recovery is the subject of Section 8 .

Figure 3: DC-GEVP blind chirp rate estimation ( $M=64$ , SNR $=10$ dB). The minimum eigenvalue $\lambda_{\min}(\psi)$ of the DC-GEVP is plotted as a function of the chirp parameter $\psi$ . The global minimum at $\psi=\psi_{0}=0.15$ confirms that the conjugated cyclic group with the correct chirp rate exactly commutes with the covariance (Proposition 7 ). The sharpness of the minimum indicates high sensitivity to chirp rate mismatch, enabling precise blind estimation.

Covariance Estimation

Covariance estimation develops methods for learning dependence and uncertainty structure from noisy, incomplete, or high-dimensional data.

See all 60 papers

Apr 4, 2026

Algebraic Diversity: Group-Theoretic Spectral Estimation from Single Observations

We establish that temporal averaging over multiple observations is the degenerate case of algebraic group action with the trivial group

G=\{e\}

. A General Replacement Theorem proves that a group-averaged estimator from one snapshot achieves equivalent subspace decomposition to multi-snapshot covariance estimation. The Trivial Group Embedding Theorem proves that the sample covariance is the accumulation of trivial-group estimates, with variance governed by a

(G,L)

continuum as

1/(|G|\cdot L)

. The processing gain

10\log_{10}(M)

dB equals the classical beamforming gain, establishing that this gain is a property of group order, not sensor count. The DFT, DCT, and KLT are unified as group-matched special cases. We conjecture a General Algebraic Averaging Theorem extending these results to arbitrary statistics, with variance governed by the effective group order

d_{\mathrm{eff}}

. Monte Carlo experiments on the first four sample moments across five group types confirm the conjecture to four-digit precision. The framework exploits the

structure

of information (representation-theoretic symmetry of the data object) rather than the content, complementing Shannon's theory. Five applications are demonstrated: single-snapshot MUSIC, massive MIMO, single-pulse waveform classification, graph signal processing, and analysis of transformer LLMs. Techniques for blind group matching are described.

Mitchell A. Thornton

Richardson, TX 75080 USA

Spectral Methods

Ask PDF

Sep 7, 2026

Efficient Learning and Symmetry Discovery under Exact Invariances

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.

Ashkan Soleymani, Behrooz Tahmasebi, Patrick Jaillet +1

MIT Laboratory for Information and Decision Systems (LIDS) · Harvard John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, MA 02138, USA · Technical University of Munich (CIT, MCML, MDSI) and MIT Computer Science and Artificial Intelligence Laboratory (CSAIL)

Symmetry Discovery Invariant Representation Learning Statistical Learning Theory

Ask PDF

May 19, 2026

Group-Aware Matrix Estimation and Latent Subspace Recovery

Modern matrix completion problems often involve heterogeneous data whose rows simultaneously belong to many meta-categories, such as demographic and age groups in recommendation systems, or region and recording session labels in neural electrophysiological experiments. Standard low-rank estimators impose a single global latent geometry, which can recover average structure but may smooth away subgroup-specific variation, especially when observations are unevenly distributed across groups. We introduce Group-Aware Matrix Estimation (GAME), a convex estimator for overlapping subgroup-wise low-rank matrix estimation. GAME regularizes category-specific submatrices through overlapping nuclear-norm penalties, allowing related groups to borrow information while preserving local latent structure in a shared coordinate system. We provide finite-sample guarantees for both reconstruction error and subgroup-specific subspace recovery, showing how performance depends on sampling density, subgroup rank, and overlap structure. Experiments on synthetic, recommendation, ecological, and neuroscience datasets show that GAME is most beneficial in structured missingness regimes, where subgroup-aware regularization improves both reconstruction accuracy and latent subspace fidelity. Across these benchmarks, GAME is competitive or best among global low-rank, side-information, and modern imputation baselines, with the largest gains when subgroups exhibit distinct low-rank structure.

Hamza Golubovic, Matthew Shen, Genevera I. Allen +1

Department of Statistics, Columbia University New York, NY 10027 · Department of Statistics, Irving Institute for Cellular Dynamics, Zuckerman Institute Columbia University New York, NY 10027 · School of Data and Information Sciences, University of North Carolina at Chapel Hill Chapel Hill, NC 27599

Low-Rank Matrix Decomposition Nuclear Norm Minimization Low-Rank Approximation Matrix Completion Matrix Factorization

Ask PDF

Abstract

Covariance Estimation

Explore similar work

Algebraic Diversity: Group-Theoretic Spectral Estimation from Single Observations

Efficient Learning and Symmetry Discovery under Exact Invariances

Group-Aware Matrix Estimation and Latent Subspace Recovery