論文の概要: Polynomial-Time Optimal Group Selection via the Double-Commutator Eigenvalue Problem
- arxiv url: http://arxiv.org/abs/2605.00834v1
- Date: Sat, 04 Apr 2026 09:02:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-11 06:56:26.437056
- Title: Polynomial-Time Optimal Group Selection via the Double-Commutator Eigenvalue Problem
- Title（参考訳）: 二重共役固有値問題による多項式時間最適群選択
- Authors: Mitchell A. Thornton,
- Abstract要約: 本稿では,新しいクラスリンク群理論,行列解析,統計的推定について述べる。
この問題は計算複雑性の標準的なカタログには現れない。
- 参考スコア（独自算出の注目度）: 1.3537117504260623
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The algebraic diversity framework replaces temporal averaging over multiple observations with 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.
- Abstract（参考訳）: 代数的多様性フレームワークは、時間平均化を2次統計推定のための単一の観測における代数的グループ作用に置き換える。
このフレームワークの中心的な開問題は$\textit{group selection}$: 未知の共分散構造を持つ$M$次元の観測が与えられたとき、スペクトル分解が共分散に最もよく一致する有限群を見つける。
対称群 $S_M$ のすべての部分群のネーブ列挙は、指数時間$M$ を必要とする。
この組合せ問題は共分散行列の二重可換子から導かれる一般化固有値問題に還元され、複雑性$O(d^2M^2 + d^3)$の多項式時間アルゴリズムが生成される。
二重可換行列の最小固有ベクトルは、反復最適化のない閉形式で最適群生成器を直接構成する。
倍変換器の最小固有値が 0 であることと、最適発生器が基底のスパンにある場合に限り、その大きさが証明可能な最適性ギャップを与える。
この問題は計算複雑性の標準的なカタログには現れず(Garey and Johnson, 1979)、新しいクラスリンク群理論、行列解析、統計的推定を表している。
独立成分分析 (JADE) や構造行列近接問題, 同時行列対角化との接続を確立し, 同時に多項式時間, 閉形式, 証明可能な一意的なアプローチであることを示す。
関連論文リスト
- Learnable Similarity and Dissimilarity Guided Symmetric Non-Negative Matrix Factorization [18.53944578996308]
学習可能な重み付き$k$-NNグラフを構築し、各$k$-th NNの信頼性を反映する。
識別的類似度行列を得るために,類似度行列の二重構造を持つ相似性行列を導入する。
提案したモデルを解決するために,効率的な代替最適化アルゴリズムを設計する。
論文 参考訳（メタデータ） (2024-12-05T11:32:53Z) - Optimization without Retraction on the Random Generalized Stiefel Manifold [13.718350570423267]
本稿では,B$のランダムな推定値にのみアクセスしながら,最適化問題を解く,安価な反復手法を提案する。
我々の方法はすべての反復において制約を強制するのではなく、予想で定義される一般化されたスティーフェル多様体上の臨界点に収束する反復を生成する。
論文 参考訳（メタデータ） (2024-05-02T19:55:30Z) - Automatic Solver Generator for Systems of Laurent Polynomial Equations [1.7188280334580197]
同じ単項構造であるが様々な係数を持つ三角系(ローラン系)が与えられたとき、任意の族に対する解をできるだけ早く計算する解法を見つける。
ローラン方程式系に対する自動解法生成器を提案する。
論文 参考訳（メタデータ） (2023-07-01T12:12:52Z) - Optimal N-ary ECOC Matrices for Ensemble Classification [1.3561997774592662]
アンサンブル分類法における誤り訂正出力符号(ECOC)の新たな構成について述べる。
任意の素数$N$が与えられたとき、この決定論的構成は基底-$N$対称二乗行列を$M$で生成する。
論文 参考訳（メタデータ） (2021-10-05T16:50:15Z) - Sparse Quadratic Optimisation over the Stiefel Manifold with Application
to Permutation Synchronisation [71.27989298860481]
二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。
そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-30T19:17:35Z) - Optimal Orthogonal Group Synchronization and Rotation Group
Synchronization [19.909352968029584]
本稿では,Z*$を推定するための反復極分解アルゴリズムを解析する。
一致したミニマックス下界が確立され、提案アルゴリズムの最適性が導かれる。
論文 参考訳（メタデータ） (2021-09-28T05:10:20Z) - A Practical Method for Constructing Equivariant Multilayer Perceptrons
for Arbitrary Matrix Groups [115.58550697886987]
行列群の同変層を解くための完全一般的なアルゴリズムを提供する。
他作品からのソリューションを特殊ケースとして回収するだけでなく、これまで取り組んだことのない複数のグループと等価な多層パーセプトロンを構築します。
提案手法は, 粒子物理学および力学系への応用により, 非同変基底線より優れる。
論文 参考訳（メタデータ） (2021-04-19T17:21:54Z) - Self-supervised Symmetric Nonnegative Matrix Factorization [82.59905231819685]
シンメトリー非負係数行列(SNMF)は、データクラスタリングの強力な方法であることを示した。
より良いクラスタリング結果を求めるアンサンブルクラスタリングにインスパイアされた,自己監視型SNMF(S$3$NMF)を提案する。
SNMFのコード特性に対する感度を、追加情報に頼らずに活用しています。
論文 参考訳（メタデータ） (2021-03-02T12:47:40Z) - Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature
Selection [138.97647716793333]
再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。
提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
論文 参考訳（メタデータ） (2020-12-29T04:08:38Z) - Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。
我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-30T19:10:32Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。