論文の概要: A Decomposition Framework for Certifiably Optimal Orthogonal Sparse PCA
- arxiv url: http://arxiv.org/abs/2603.01144v1
- Date: Sun, 01 Mar 2026 15:09:37 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-03 19:50:56.53402
- Title: A Decomposition Framework for Certifiably Optimal Orthogonal Sparse PCA
- Title（参考訳）: 最適直交スパースPCAのための分解フレームワーク
- Authors: Difei Cheng, Qiao Hu,
- Abstract要約: 我々はtextscGS-SPCA (SPCA with Gram-Schmidt Orthogonalization) と呼ばれる新しいスパース主成分分析アルゴリズムを導入する。
この戦略を取り入れることで、精度と効率のトレードオフのある$varepsilon$-Optimalソリューションを得ることができる。
- 参考スコア（独自算出の注目度）: 1.8252316736244685
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Sparse Principal Component Analysis (SPCA) is an important technique for high-dimensional data analysis, improving interpretability by imposing sparsity on principal components. However, existing methods often fail to simultaneously guarantee sparsity, orthogonality, and optimality of the principal components. To address this challenge, this work introduces a novel Sparse Principal Component Analysis (SPCA) algorithm called \textsc{GS-SPCA} (SPCA with Gram-Schmidt Orthogonalization), which simultaneously enforces sparsity, orthogonality, and optimality. However, the original GS-SPCA algorithm is computationally expensive due to the inherent $\ell_0$-norm constraint. To address this issue, we propose two acceleration strategies: First, we combine \textbf{Branch-and-Bound} with the GS-SPCA algorithm. By incorporating this strategy, we are able to obtain $\varepsilon$-optimal solutions with a trade-off between precision and efficiency, significantly improving computational speed. Second, we propose a \textbf{decomposition framework} for efficiently solving \textbf{multiple} principal components. This framework approximates the covariance matrix using a block-diagonal matrix through a thresholding method, reducing the original SPCA problem to a set of block-wise subproblems on approximately block-diagonal matrices.
- Abstract（参考訳）: スパース主成分分析(SPCA)は高次元データ解析において重要な手法であり、主成分に空間性を与えることにより解釈性を向上させる。
しかし、既存の手法は、主成分の空間性、直交性、最適性を同時に保証しないことが多い。
この課題に対処するために、新しいスパース主成分分析 (SPCA) アルゴリズムである \textsc{GS-SPCA} (SPCA with Gram-Schmidt Orthogonalization, SPCA with Gram-Schmidt Orthogonalization) を導入する。
しかし、元のGS-SPCAアルゴリズムは本質的に$\ell_0$-norm制約のため計算コストがかかる。
この問題に対処するために、まず、 \textbf{Branch-and-Bound} と GS-SPCA アルゴリズムを組み合わせる。
この戦略を取り入れることで、精度と効率のトレードオフを生かした$\varepsilon$-Optimalソリューションが得られ、計算速度が大幅に向上する。
次に,主成分を効率的に解けるためのフレームワークを提案する。
この枠組みは, ブロック対角行列をしきい値法により近似し, ブロック対角行列上のブロック対角行列の集合に元のSPCA問題を還元する。
関連論文リスト
- Algorithms for the Shortest Vector Problem in $2$-dimensional Lattices, Revisited [4.843809993270313]
2次元格子における最短ベクトル問題(SVP)の効率的な解法は、暗号や計算幾何学において実際的な重要性を持つ。
我々は、ユークリッドアルゴリズムを次元にわたって戦略的に適用する効率的な適応格子削減アルゴリズム textbfCrossEuc を開発した。
textbfHVecを反復的に呼び出すことによって、最適化されたアルゴリズム textbfHVecSBP は、ビット長$n$の任意の入力ベースに対して$O(log n M(n) )$ time の還元基底を得る。
論文 参考訳（メタデータ） (2025-04-17T13:50:51Z) - Solve sparse PCA problem by employing Hamiltonian system and leapfrog method [0.0]
そこで本研究では,スムーズなL1ペナルティを通したスパースPCAアルゴリズムを提案する。
k-アネレスト近傍とカーネルリッジ回帰の両方を用いた顔認識データセットの実験的評価-提案したスパースPCA法は従来のPCA法よりも高い分類精度を一貫して達成している。
論文 参考訳（メタデータ） (2025-03-30T06:39:11Z) - Scalable First-order Method for Certifying Optimal k-Sparse GLMs [9.613635592922174]
そこで本研究では,BnBフレームワークの視点緩和を解くために,一階近位勾配アルゴリズムを提案する。
提案手法は双有界計算を著しく高速化し,大規模問題に対する最適性証明の提供に極めて有効であることを示す。
論文 参考訳（メタデータ） (2025-02-13T17:14:18Z) - Accelerated sparse Kernel Spectral Clustering for large scale data
clustering problems [0.27257174044950283]
本稿では、スパースマルチウェイカーネルスペクトルクラスタリング(KSC)の改良版について述べる。
元のアルゴリズムは、プライマリ・デュアルの最小二乗サポートベクターマシン(LS-SVM)フレームワークで定式化された重み付きカーネル主成分分析から導かれる。
次に、不完全コレスキー分解(ICD)に基づくカーネル行列の低階近似といわゆるreduced set法を組み合わせることにより、スパーシリティが達成される。
論文 参考訳（メタデータ） (2023-10-20T09:51:42Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - Deep Unrolling for Nonconvex Robust Principal Component Analysis [75.32013242448151]
我々はロバスト成分分析のためのアルゴリズムを設計する(A)
行列を低主行列とスパース主行列の和に分解する。
論文 参考訳（メタデータ） (2023-07-12T03:48:26Z) - A Deep Unrolling Model with Hybrid Optimization Structure for Hyperspectral Image Deconvolution [50.13564338607482]
本稿では,DeepMixと呼ばれるハイパースペクトルデコンボリューション問題に対する新しい最適化フレームワークを提案する。
これは3つの異なるモジュール、すなわちデータ一貫性モジュール、手作りの正規化器の効果を強制するモジュール、および装飾モジュールで構成されている。
本研究は,他のモジュールの協調作業によって達成される進歩を維持するために設計された,文脈を考慮した認知型モジュールを提案する。
論文 参考訳（メタデータ） (2023-06-10T08:25:16Z) - Extending Kernel PCA through Dualization: Sparsity, Robustness and Fast
Algorithms [14.964073009670194]
本稿では,凸関数の差分を二重化することによりカーネル主成分分析(KPCA)を再検討する。
これにより、KPCAを複数の目的関数に自然に拡張することができ、グラム行列の高価なSVDを避けるために効率的な勾配ベースのアルゴリズムが導かれる。
論文 参考訳（メタデータ） (2023-06-09T11:27:35Z) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳（メタデータ） (2023-02-24T18:41:48Z) - Exploring the Algorithm-Dependent Generalization of AUPRC Optimization
with List Stability [107.65337427333064]
AUPRC(Area Under the Precision-Recall Curve)の最適化は、機械学習にとって重要な問題である。
本研究では, AUPRC最適化の単依存一般化における最初の試行について述べる。
3つの画像検索データセットの実験は、我々のフレームワークの有効性と健全性に言及する。
論文 参考訳（メタデータ） (2022-09-27T09:06:37Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳（メタデータ） (2021-10-20T02:57:21Z) - Spike and slab Bayesian sparse principal component analysis [0.6599344783327054]
本稿では,パラメータ拡張座標の漸近変動推論(PX-CAVI)アルゴリズムを提案する。
PX-CAVIアルゴリズムは2つのSPCA手法より優れていることを示す。
このアルゴリズムは肺がん遺伝子発現データセットの研究に応用される。
論文 参考訳（メタデータ） (2021-01-30T20:28:30Z) - Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
主成分分析(PCA)は、機械学習と統計学において広く使われている次元削減手法である。
スパース主成分分析(Sparse principal Component Analysis)と呼ばれる,スパース主成分負荷を求める様々な手法が提案されている。
本研究では,SPCA問題に対するしきい値の精度,時間,近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-23T04:25:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。