論文の概要: A Randomized Algorithm for Sparse PCA based on the Basic SDP Relaxation
- arxiv url: http://arxiv.org/abs/2507.09148v1
- Date: Sat, 12 Jul 2025 05:43:56 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-15 18:48:22.558325
- Title: A Randomized Algorithm for Sparse PCA based on the Basic SDP Relaxation
- Title（参考訳）: 基本SDP緩和に基づくスパースPCAのランダム化アルゴリズム
- Authors: Alberto Del Pia, Dekun Zhou,
- Abstract要約: 基本的SDP緩和に基づくSPCAのランダム化近似アルゴリズムを提案する。
我々のアルゴリズムは、十分な時間で呼ばれる場合、最も高い確率で空間定数の近似比を持つ。
実世界のデータセット上での数値計算によるアルゴリズムの有効性を実証する。
- 参考スコア（独自算出の注目度）: 1.3044677039636754
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Sparse Principal Component Analysis (SPCA) is a fundamental technique for dimensionality reduction, and is NP-hard. In this paper, we introduce a randomized approximation algorithm for SPCA, which is based on the basic SDP relaxation. Our algorithm has an approximation ratio of at most the sparsity constant with high probability, if called enough times. Under a technical assumption, which is consistently satisfied in our numerical tests, the average approximation ratio is also bounded by $\mathcal{O}(\log{d})$, where $d$ is the number of features. We show that this technical assumption is satisfied if the SDP solution is low-rank, or has exponentially decaying eigenvalues. We then present a broad class of instances for which this technical assumption holds. We also demonstrate that in a covariance model, which generalizes the spiked Wishart model, our proposed algorithm achieves a near-optimal approximation ratio. We demonstrate the efficacy of our algorithm through numerical results on real-world datasets.
- Abstract（参考訳）: スパース主成分分析(SPCA)は次元減少の基本的な手法であり、NPハードである。
本稿では,SDP緩和に基づくSPCAのランダム化近似アルゴリズムを提案する。
我々のアルゴリズムは、十分な時間で呼ばれる場合、最も高い確率で空間定数の近似比を持つ。
数値テストで一貫して満足する技術的仮定の下では、平均近似比は$\mathcal{O}(\log{d})$で束縛され、$d$は特徴数である。
この技術的仮定は、SDP解が低ランクであるか、指数関数的に固有値が減衰しているかで満たされることを示す。
次に、この技術的な仮定が成立する幅広い種類の例を示す。
また、スパイクされたウィッシュアートモデルを一般化した共分散モデルにおいて、提案アルゴリズムは近似の近似比をほぼ最適に達成することを示した。
実世界のデータセット上での数値計算によるアルゴリズムの有効性を実証する。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Private Geometric Median [10.359525525715421]
データセットの幾何中央値(GM)を計算するための差分プライベート(DP)アルゴリズムについて検討する。
我々の主な貢献は、データポイントの有効直径でスケールする過剰なエラー保証を備えたプライベートGMのタスクのためのDPアルゴリズムのペアである。
論文 参考訳（メタデータ） (2024-06-11T16:13:09Z) - Differentially Private Optimization with Sparse Gradients [60.853074897282625]
微分プライベート(DP)最適化問題を個人勾配の空間性の下で検討する。
これに基づいて、スパース勾配の凸最適化にほぼ最適な速度で純粋および近似DPアルゴリズムを得る。
論文 参考訳（メタデータ） (2024-04-16T20:01:10Z) - Privately Estimating a Gaussian: Efficient, Robust and Optimal [6.901744415870126]
純微分プライバシー(DP)モデルと近似微分プライバシー(DP)モデルの両方において、ガウス分布をプライベートに推定する効率的なアルゴリズムを提供する。
純粋なDP設定では、未知の$d$次元ガウス分布を任意の全変分誤差まで推定する効率的なアルゴリズムを与える。
平均推定の特別な場合、我々のアルゴリズムは$widetilde O(d1.5)$の最適なサンプル複雑性を達成し、以前の作業から$widetilde O(d1.5)$のバウンドを改善する。
論文 参考訳（メタデータ） (2022-12-15T18:27:39Z) - Efficient One Sided Kolmogorov Approximation [7.657378889055477]
本研究の主な応用は, 時系列並列スケジュールにおいて, 欠落する確率を推定することである。
これらの確率の正確な計算はNPハードであるため,本論文で記述したアルゴリズムを用いて近似を求める。
論文 参考訳（メタデータ） (2022-07-14T10:03:02Z) - Alternating Mahalanobis Distance Minimization for Stable and Accurate CP
Decomposition [4.847980206213335]
本稿では, テンソルの特異値とベクトルを導出するための新しい定式化を導入する。
このアルゴリズムのサブスウィープは、既知のランクの正確なCPDに対して超線形収束率を達成することができることを示す。
すると、アルゴリズムは各因子に対するマハラノビス距離を最適化するものであり、基底距離は他の因子に依存していると見なす。
論文 参考訳（メタデータ） (2022-04-14T19:56:36Z) - Complexity of Inexact Proximal Point Algorithm for minimizing convex functions with Holderian Growth [1.9643748953805935]
コンベックス関数を$gamma-$Holderian成長下で最小化するために、完全かつ不正確なPPAの漸近複雑性を導出する。
数値実験では, 既存の再起動バージョンよりも改善が見られた。
論文 参考訳（メタデータ） (2021-08-10T07:15:07Z) - Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
任意のランクの正方形密度あるいはスパース行列の統計レバレッジスコアを推定するアルゴリズムについて検討した。
提案手法は,高密度およびスパースなランダム化次元性還元変換の合成と階調明細化法を組み合わせることに基づく。
論文 参考訳（メタデータ） (2021-05-23T19:21:55Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳（メタデータ） (2020-06-24T06:01:24Z) - Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
主成分分析(PCA)は、機械学習と統計学において広く使われている次元削減手法である。
スパース主成分分析(Sparse principal Component Analysis)と呼ばれる,スパース主成分負荷を求める様々な手法が提案されている。
本研究では,SPCA問題に対するしきい値の精度,時間,近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-23T04:25:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。