論文の概要: Non-Sparse PCA in High Dimensions via Cone Projected Power Iteration
- arxiv url: http://arxiv.org/abs/2005.07587v2
- Date: Sun, 28 Feb 2021 17:22:55 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-02 23:35:56.562503
- Title: Non-Sparse PCA in High Dimensions via Cone Projected Power Iteration
- Title(参考訳): コーン投影パワーイテレーションによる高次元非スパースPCA
- Authors: Yufei Yi, Matey Neykov
- Abstract要約: 雑音正の半定値行列から第1主固有ベクトルを復元するコーン投影パワーアルゴリズムを提案する。
シミュレーションおよび実データに関する数値実験により,本手法は通常の電力と疎結合な主成分分析アルゴリズムと比較して,実行時間と誤差が短いことを示す。
- 参考スコア(独自算出の注目度): 4.162663632560141
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we propose a cone projected power iteration algorithm to
recover the first principal eigenvector from a noisy positive semidefinite
matrix. When the true principal eigenvector is assumed to belong to a convex
cone, the proposed algorithm is fast and has a tractable error. Specifically,
the method achieves polynomial time complexity for certain convex cones
equipped with fast projection such as the monotone cone. It attains a small
error when the noisy matrix has a small cone-restricted operator norm. We
supplement the above results with a minimax lower bound of the error under the
spiked covariance model. Our numerical experiments on simulated and real data,
show that our method achieves shorter run time and smaller error in comparison
to the ordinary power iteration and some sparse principal component analysis
algorithms if the principal eigenvector is in a convex cone.
- Abstract(参考訳): 本稿では,雑音正の半定値行列から第1主固有ベクトルを復元するコーン投影電力反復アルゴリズムを提案する。
真の主固有ベクトルが凸錐に属すると仮定すると,提案アルゴリズムは高速かつトラクタブルな誤差を有する。
具体的には、モノトーンコーンのような高速射影を備えた凸錐に対して多項式時間複雑性を実現する。
雑音行列が小さい円錐制限作用素ノルムを持つ場合、小さな誤差が得られる。
以上の結果をスパイク共分散モデルの下で誤差の最小値下限で補足する。
シミュレーションおよび実データに関する数値実験により,主固有ベクトルが凸円錐内にある場合,本手法は通常の電力繰り返しと疎大な主成分分析アルゴリズムと比較して実行時間と誤差が短いことを示す。
関連論文リスト
- Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
ユークリッド球における高次元ベクトルの局所的プライベート平均推定の問題について検討する。
プライベート平均推定のための新しいアルゴリズムフレームワークであるProjUnitを提案する。
各ランダム化器はその入力をランダムな低次元部分空間に投影し、結果を正規化し、最適なアルゴリズムを実行する。
論文 参考訳(メタデータ) (2023-06-07T14:07:35Z) - Near optimal sample complexity for matrix and tensor normal models via
geodesic convexity [5.191641077435773]
いくつかの自然測度において、最大極大推定器(MLE)によって達成された誤差に対する漸近的境界を示す。
サンプルの複雑性境界と同じ条件下では、フリップフロップアルゴリズム(英語版)として知られるMLEを反復的に計算する手法が高い確率で線形に収束することを示す。
論文 参考訳(メタデータ) (2021-10-14T17:47:00Z) - Provable Low Rank Plus Sparse Matrix Separation Via Nonconvex
Regularizers [0.0]
本稿では,低ランク行列やスパースベクトルをある種の測定値から回収しようとする大問題について考察する。
凸偏差推定器に基づく手法は、ランクや空間の偏りに悩まされているが、非正則化器を用いる。
本稿では,このような問題に適用した近似交互バイアス降下アルゴリズムの新たな解析法を提案する。
論文 参考訳(メタデータ) (2021-09-26T22:09:42Z) - Minimax Estimation of Linear Functions of Eigenvectors in the Face of
Small Eigen-Gaps [95.62172085878132]
固有ベクトル摂動解析は様々な統計データ科学の応用において重要な役割を果たす。
未知の固有ベクトルの任意の線型関数の摂動を特徴付ける統計理論の一組を開発する。
自然の「プラグイン」推定器に固有の非無視バイアス問題を緩和するために,非バイアス推定器を開発する。
論文 参考訳(メタデータ) (2021-04-07T17:55:10Z) - Analysis of Truncated Orthogonal Iteration for Sparse Eigenvector
Problems [78.95866278697777]
本研究では,多元的固有ベクトルを分散制約で同時に計算するTruncated Orthogonal Iterationの2つの変種を提案する。
次に,我々のアルゴリズムを適用して,幅広いテストデータセットに対するスパース原理成分分析問題を解く。
論文 参考訳(メタデータ) (2021-03-24T23:11:32Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。
まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。
次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文 参考訳(メタデータ) (2021-01-19T04:24:23Z) - Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature
Selection [138.97647716793333]
再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。
提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
論文 参考訳(メタデータ) (2020-12-29T04:08:38Z) - Dynamical perturbation theory for eigenvalue problems [0.0]
提案アルゴリズムは,通常のレイリー=シュル・オーディンガー展開を3つの数で上回ることを示す。
また,本手法は汎用固有値ルーチンよりも行列のサイズがよい。
論文 参考訳(メタデータ) (2020-02-28T17:13:22Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳(メタデータ) (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。