提出多项式时间算法解决统计估计中的群选择难题。
Polynomial-Time Optimal Group Selection via the Double-Commutator Eigenvalue Problem
- 将群选择转化为双交换子特征值问题，实现闭式求解。
- 算法复杂度为O(d²M² + d³)，可精确计算最优群生成元。
- 适用于需要高效、可验证对称性恢复的统计建模场景。
代数多样性框架将多观测时间平均推广至单个观测上的代数群作用，用于二阶统计估计。该框架的核心开放问题为‘群选择’：给定维度为M的观测，其协方差结构未知时，需找出谱分解最匹配协方差的有限群。朴素枚举对称群SM的所有子群需指数时间。本文证明该组合问题可化归为由协方差矩阵双交换子导出的广义特征值问题，从而获得复杂度为O(d²M² + d³)的多项式时间算法，其中d为生成元基的维数。双交换子矩阵的最小特征向量可直接构造最优群生成元，无需迭代优化。该约化是精确的：当且仅当最优生成元位于基张成空间内时，双交换子最小特征值为零；否则其大小提供可验证的最优性间隙。该问题未见于标准计算复杂性分类（Garey and Johnson, 1979），构成群论、矩阵分析与统计估计的新交叉领域。我们建立了与独立成分分析（JADE）、结构矩阵逼近及同时对角化的关系，并证明双交换子形式是唯一同时具备多项式时间、闭式解和可验证性的方法。进一步扩展至非阿贝尔对称性恢复，采用带降阶的序列广义特征值问题，并给出两个可辨识性定理，刻画换位子格模糊性及Aut(R)恢复生成子群或超群的二分性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。