arxiv: 2605.00834 · v2 · submitted 2026-04-04 · 💻 cs.LG · cs.CC· cs.IT· math.IT

Recognition: no theorem link

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

Mitchell A. Thornton

Pith reviewed 2026-05-13 18:36 UTC · model grok-4.3

classification 💻 cs.LG cs.CCcs.ITmath.IT

keywords group selectiondouble commutatorgeneralized eigenvalue problemcovariance estimationpolynomial-time algorithmalgebraic group actionsymmetry recoverymatrix nearness

0 comments

The pith

Group selection for covariance estimation reduces to finding the minimum eigenvector of a double-commutator matrix in polynomial time.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that the combinatorial task of choosing the finite group whose action best matches an observed covariance matrix, previously requiring exponential enumeration over subgroups of the symmetric group, reduces exactly to a generalized eigenvalue problem built from the double commutator of that matrix. The minimum eigenvector of this derived matrix directly yields the optimal group generator in closed form. This produces an algorithm whose complexity is quadratic in the observation dimension times the generator basis size plus a cubic term, with the minimum eigenvalue serving as both an exact optimality certificate when it reaches zero and a quantifiable gap otherwise. The result links algebraic group actions to standard matrix problems and supplies identifiability conditions for when the recovered symmetry is a subgroup or only a supergroup.

Core claim

The combinatorial group-selection problem reduces to a generalized eigenvalue problem whose matrix is formed from the double commutator of the covariance matrix. The eigenvector belonging to the smallest eigenvalue directly constructs the optimal generator. The reduction is exact: the minimum eigenvalue is zero if and only if the optimal generator lies inside the chosen basis span, and its positive magnitude supplies a certifiable optimality gap when the generator must be approximated.

What carries the argument

The double-commutator matrix constructed from the covariance matrix, whose smallest-eigenvalue eigenvector supplies the optimal group generator in closed form.

If this is right

Optimal groups are obtained without enumerating subgroups of the symmetric group.
The same formulation recovers non-Abelian symmetries by sequential generalized eigenvalue problems with deflation.
The minimum eigenvalue supplies a numerical certificate of how far the chosen basis is from containing the true optimum.
The approach unifies connections to independent-component analysis, simultaneous matrix diagonalization, and structured matrix nearness problems.
Two identifiability theorems characterize when the commutant recovers a generative subgroup versus only a supergroup.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same double-commutator construction might be tested on covariance matrices drawn from other symmetry groups not previously enumerated in the algebraic-diversity setting.
If the basis dimension d remains modest while observation dimension M grows, the method could support online symmetry recovery in streaming data applications.
The eigenvalue gap could serve as a diagnostic for model mismatch when the assumed group action is only approximate.
Extensions to continuous Lie-group actions would require replacing the finite basis with a discretized generator algebra while preserving the commutator structure.

Load-bearing premise

A finite-dimensional basis for the generator span can be chosen so that the optimal group element lies inside that span and the covariance matrix exactly admits the desired group action.

What would settle it

Compute the double-commutator matrix from a covariance known to be generated by a specific group element inside the chosen basis; the minimum eigenvalue must be exactly zero and the recovered eigenvector must reproduce that generator up to scaling.

Figures

Figures reproduced from arXiv: 2605.00834 by Mitchell A. Thornton.

**Figure 2.** Figure 2: Single-generator DC-GEVP graph automorphism identification (Part 2). Triangular prism ( [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

**Figure 3.** Figure 3: DC-GEVP blind chirp rate estimation (M = 64, SNR = 10 dB). The minimum eigenvalue λmin(ψ) of the DC-GEVP is plotted as a function of the chirp parameter ψ. The global minimum at ψ = ψ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 p… view at source ↗

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper reduces combinatorial group selection to a double-commutator GEVP with a closed-form solution and certifiable gap, but the polynomial-time guarantee only holds inside a pre-chosen basis whose selection is left open.

read the letter

The main point is that this work turns the exponential enumeration of subgroups of S_M into a generalized eigenvalue problem built from the double commutator of the covariance matrix. The minimum eigenvector is supposed to give the optimal generator directly, and a zero eigenvalue certifies that the solution sits inside the chosen span. That algebraic move is the genuinely new piece, and it sits at the intersection of group representations, simultaneous diagonalization, and structured matrix problems. The connections to JADE and ICA are drawn cleanly, and the extension to non-Abelian cases via sequential GEVP with deflation is a reasonable next step. The two identifiability theorems on commutant-lattice ambiguity also give some handle on when the recovered symmetry is generative versus merely a supergroup. Those parts are worth having on record. The soft spot is exactly where the stress-test note flags it. The stated complexity O(d²M² + d³) is polynomial only once d is fixed or grows slowly, yet the exactness claim requires that the optimal generator already lies in the d-dimensional basis. The manuscript gives no algorithm for constructing or bounding that basis from the covariance alone, and for subgroups of S_M the Lie-algebra dimension can grow with M. Without that step the combinatorial cost is displaced rather than removed. If a universal low-dimensional basis works for the cases people actually care about, the result is strong; if not, the practical payoff shrinks. The paper is aimed at readers who already work with algebraic methods for covariance structure or symmetry recovery and who are comfortable supplying or verifying a generator basis. Someone looking for an off-the-shelf replacement for brute-force search will still need to solve the basis problem separately. It is coherent on its own terms and engages the literature without obvious internal contradictions, so it deserves a serious referee to check the derivations and see whether the basis issue can be closed or bounded. I would send it to review rather than desk-reject.

Referee Report

3 major / 1 minor

Summary. The paper claims that the combinatorial group selection problem—finding the finite group whose spectral decomposition best matches an unknown covariance structure in the algebraic diversity framework—reduces exactly to a generalized eigenvalue problem derived from the double commutator of the covariance matrix. This yields a polynomial-time algorithm of complexity O(d²M² + d³) whose minimum eigenvector constructs the optimal group generator in closed form, with the minimum eigenvalue serving as a certifiable optimality gap when the generator does not lie in the chosen d-dimensional basis span. The work further extends the approach to non-Abelian symmetry recovery via sequential GEVP with deflation and provides two identifiability theorems on commutant-lattice ambiguity and Aut(R) recovery.

Significance. If the reduction holds with a polynomial-time basis construction, the result would be significant: it supplies the first polynomial-time, closed-form, and certifiable solution to an apparently new combinatorial problem linking group representation theory, matrix analysis, and second-order statistical estimation, while establishing concrete connections to JADE-style ICA and simultaneous matrix diagonalization.

major comments (3)

[Abstract] Abstract: The stated complexity O(d²M² + d³) is polynomial in M only when d remains small or polynomial; however, the manuscript provides no algorithm or bound for constructing a suitable finite-dimensional basis for the Lie-algebra generators of subgroups of S_M from the covariance matrix alone. Without such a step, the combinatorial cost is displaced rather than eliminated, rendering the polynomial-time claim conditional on a pre-specified basis that contains the optimal generator.
[Abstract] Abstract: The exactness claim—that the double-commutator minimum eigenvalue is zero if and only if the optimal generator lies in the span, and otherwise quantifies a certifiable optimality gap—depends on the basis choice and the assumption that the covariance exactly admits the desired group action. No explicit error analysis or handling of incomplete spans is indicated, which is load-bearing for the central reduction.
[Abstract] Abstract: The extension to non-Abelian symmetry recovery via Sequential GEVP with deflation must demonstrate that deflation preserves both the polynomial-time guarantee and the exactness/optimality-gap properties; otherwise the non-Abelian case reintroduces iterative or combinatorial overhead.

minor comments (1)

[Abstract] The abstract references Garey and Johnson (1979) for complexity catalogs but does not clarify why this specific problem is absent from them; a brief justification would strengthen the novelty claim.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address each major comment below, indicating where revisions will be made to clarify assumptions and strengthen the presentation.

read point-by-point responses

Referee: [Abstract] Abstract: The stated complexity O(d²M² + d³) is polynomial in M only when d remains small or polynomial; however, the manuscript provides no algorithm or bound for constructing a suitable finite-dimensional basis for the Lie-algebra generators of subgroups of S_M from the covariance matrix alone. Without such a step, the combinatorial cost is displaced rather than eliminated, rendering the polynomial-time claim conditional on a pre-specified basis that contains the optimal generator.

Authors: We agree that the manuscript focuses on the group-selection step assuming a generator basis of dimension d is already available (e.g., via representation-theoretic enumeration of low-dimensional Lie-algebra elements for subgroups of S_M or domain knowledge). The O(d²M² + d³) bound therefore applies to that step; the basis-construction cost is outside the claimed reduction. We will revise the abstract and Section 2 to state this assumption explicitly and add a brief discussion in the conclusion on practical basis construction via covariance-driven search over candidate generators (e.g., solving small commutator equations), while noting that a fully general polynomial-time basis algorithm remains open. revision: partial
Referee: [Abstract] Abstract: The exactness claim—that the double-commutator minimum eigenvalue is zero if and only if the optimal generator lies in the span, and otherwise quantifies a certifiable optimality gap—depends on the basis choice and the assumption that the covariance exactly admits the desired group action. No explicit error analysis or handling of incomplete spans is indicated, which is load-bearing for the central reduction.

Authors: The exactness and zero-eigenvalue characterization hold when the covariance is exactly group-invariant and the generator lies in the chosen span, as formalized in the two identifiability theorems. When the span is incomplete the minimum eigenvalue supplies a computable lower bound on the residual mismatch. We will add a new subsection (and supporting lemma) providing a first-order perturbation analysis for the eigenvalue gap under small deviations from exact invariance or under span truncation, thereby making the certificate explicit for the incomplete-span case. revision: yes
Referee: [Abstract] Abstract: The extension to non-Abelian symmetry recovery via Sequential GEVP with deflation must demonstrate that deflation preserves both the polynomial-time guarantee and the exactness/optimality-gap properties; otherwise the non-Abelian case reintroduces iterative or combinatorial overhead.

Authors: Each deflation step consists of an orthogonal projection onto the orthogonal complement of the previously recovered generator, which is O(d³) and does not increase the per-step GEVP cost. With at most d steps the overall complexity remains O(d²M² + d³). Because the double-commutator operator is linear, the projection preserves the algebraic structure, so the zero-eigenvalue test and optimality-gap certificate continue to apply to the deflated problem. We will insert a short proof in the appendix confirming these invariance properties. revision: yes

Circularity Check

0 steps flagged

Core reduction to double-commutator GEVP is algebraically self-contained; only minor self-reference to prior framework

full rationale

The manuscript derives the claimed polynomial-time reduction of group selection to a generalized eigenvalue problem on the double commutator of the covariance matrix using standard Lie-algebra and commutator identities. No step equates the output generator to a fitted parameter or renames an input as a prediction. The algebraic diversity framework is invoked as background, but the central GEVP construction and exactness claim (minimum eigenvalue zero iff generator in span) are developed independently within the paper via matrix analysis. The conditional nature of the basis span is stated explicitly rather than smuggled in by self-citation. This yields at most a score of 2 for routine self-reference to the author's prior framework definition.

Axiom & Free-Parameter Ledger

1 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard linear-algebraic properties of commutators together with the domain assumption that the covariance admits an exact finite-group action representable in a chosen generator basis.

free parameters (1)

d
Dimension of the chosen generator basis; selected as part of problem setup rather than fitted to data.

axioms (2)

domain assumption Covariance matrix admits a representation by a finite group action
Invoked throughout the algebraic diversity framework and the reduction.
standard math Double-commutator operator yields a generalized eigenvalue problem whose minimum eigenvector recovers the group generator
Core algebraic identity used to obtain the polynomial-time algorithm.

pith-pipeline@v0.9.0 · 5625 in / 1300 out tokens · 42955 ms · 2026-05-13T18:36:15.418657+00:00 · methodology

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Unification of Signal Transform Theory
eess.SP 2026-05 unverdicted novelty 6.0

Signal transforms are unified as group representation eigenbases, with an algorithm to find the matched group from empirical covariances.

Reference graph

Works this paper leans on

9 extracted references · 9 canonical work pages · cited by 1 Pith paper · 2 internal anchors

[1]

Algebraic Diversity: Group-Theoretic Spectral Estimation from Single Observations

M. A. Thornton, “Algebraic diversity: Group- theoretic spectral estimation from single observa- tions,” arXiv:2604.03634, April 2026

work page internal anchor Pith review Pith/arXiv arXiv 2026
[2]

Algebraic Diversity: Principles of a Group-Theoretic Approach to Signal Processing

M. A. Thornton, “Algebraic Diversity: Principles of a Group-Theoretic Approach to Signal Processing,” arXiv:2604.19983 [eess.SP], April 2026

work page internal anchor Pith review Pith/arXiv arXiv 2026
[3]

The Karhunen–Lo` eve transform of discrete MVL functions,

M. A. Thornton, “The Karhunen–Lo` eve transform of discrete MVL functions,” inProc. 35th Int. Symp. Multiple-Valued Logic (ISMVL), pp. 194–199, 2005

work page 2005
[4]

Blind beamform- ing for non-Gaussian signals,

J.-F. Cardoso and A. Souloumiac, “Blind beamform- ing for non-Gaussian signals,”IEE Proc.-F Radar Signal Process., vol. 140, no. 6, pp. 362–370, 1993

work page 1993
[5]

Group symmetry and covariance regularization,

P. Shah and V. Chandrasekaran, “Group symmetry and covariance regularization,”Electron. J. Statist., vol. 6, pp. 1600–1640, 2012

work page 2012
[6]

Numerical methods for simultaneous diagonaliza- tion,

A. Bunse-Gerstner, R. Byers, and V. Mehrmann, “Numerical methods for simultaneous diagonaliza- tion,”SIAM J. Matrix Anal. Appl., vol. 14, no. 4, pp. 927–949, 1993

work page 1993
[7]

Almost commuting selfadjoint matrices and applications,

H. Lin, “Almost commuting selfadjoint matrices and applications,” inOperator Algebras and Their Ap- plications, Fields Institute Communications, vol. 13, pp. 193–233, 1997

work page 1997
[8]

M. R. Garey and D. S. Johnson,Computers and Intractability: A Guide to the Theory of NP- Completeness. San Francisco: Freeman, 1979

work page 1979
[9]

Decoding by linear pro- gramming,

E. J. Cand` es and T. Tao, “Decoding by linear pro- gramming,”IEEE Trans. Inform. Theory, vol. 51, no. 12, pp. 4203–4215, 2005. 11

work page 2005