論文の概要: Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA
- arxiv url: http://arxiv.org/abs/2305.02544v1
- Date: Thu, 4 May 2023 04:45:16 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-05 17:09:32.038496
- Title: Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA
- Title（参考訳）: 外乱PCAの近距離時間とストリーミングアルゴリズム
- Authors: Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia, Thanasis Pittas
- Abstract要約: ほぼ最適誤差保証付き頑健なPCAのためのニア線形時間アルゴリズムを開発した。
また,メモリ使用量にほぼ線形なロバストPCAのためのシングルパスストリーミングアルゴリズムを開発した。
- 参考スコア（独自算出の注目度）: 43.106438224356175
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study principal component analysis (PCA), where given a dataset in
$\mathbb{R}^d$ from a distribution, the task is to find a unit vector $v$ that
approximately maximizes the variance of the distribution after being projected
along $v$. Despite being a classical task, standard estimators fail drastically
if the data contains even a small fraction of outliers, motivating the problem
of robust PCA. Recent work has developed computationally-efficient algorithms
for robust PCA that either take super-linear time or have sub-optimal error
guarantees. Our main contribution is to develop a nearly-linear time algorithm
for robust PCA with near-optimal error guarantees. We also develop a
single-pass streaming algorithm for robust PCA with memory usage nearly-linear
in the dimension.
- Abstract（参考訳）: 主成分分析 (pca) を研究し、分散から$\mathbb{r}^d$ のデータセットを与えられたとき、そのタスクは、$v$ に沿って投影された後に分布の分散をほぼ最大化する単位ベクトル $v$ を見つけることである。
古典的なタスクであるにもかかわらず、データがごく少数の外れ値を含む場合、標準推定器は大幅に失敗し、ロバストPCAの問題を動機付けている。
最近の研究は、超線形時間か準最適誤差保証を持つロバストPCAのための計算効率のよいアルゴリズムを開発した。
我々の主な貢献は、ほぼ最適誤差保証付きロバストPCAのためのニア線形時間アルゴリズムを開発することである。
また,メモリ使用量にほぼ線形なロバストPCAのためのシングルパスストリーミングアルゴリズムを開発した。
関連論文リスト
- Improved Privacy-Preserving PCA Using Optimized Homomorphic Matrix
Multiplication [0.0]
主成分分析(英: principal Component Analysis、PCA)は、機械学習とデータ分析の領域で広く利用されている重要な技術である。
近年,セキュアなクラウドコンピューティングシナリオにおいて,プライバシ保護型PCAアルゴリズムの同型暗号化を活用する取り組みが進められている。
本稿では,これらの制約に対処するプライバシー保護PCAに対して,従来の手法に比べて効率,精度,拡張性に優れる新たなアプローチを提案する。
論文 参考訳（メタデータ） (2023-05-27T02:51:20Z) - Streaming Kernel PCA Algorithm With Small Space [24.003544967343615]
近年,大規模なデータセットを効率的に処理できるため,ストリーミングPCAが注目されている。
我々はOjaの従来のスキームに基づくKernel問題に対するストリーミングアルゴリズムを提案する。
提案アルゴリズムは,PCAのメモリ使用量を削減するとともに,その精度を維持するという課題に対処する。
論文 参考訳（メタデータ） (2023-03-08T13:13:33Z) - Sparse PCA on fixed-rank matrices [0.05076419064097732]
共分散行列のランクが固定値であれば、大域的最適性に対してスパースPCAを解くアルゴリズムが存在することを示す。
また,主成分の非結合性を必要とするスパースPCAについても同様の結果が得られた。
論文 参考訳（メタデータ） (2022-01-07T15:05:32Z) - Robust factored principal component analysis for matrix-valued outlier
accommodation and detection [4.228971753938522]
Factored PCA (FPCA) は行列データに対するPCAの確率的拡張である。
行列データに対するFPCA(RFPCA)の堅牢な拡張を提案する。
RFPCAは適応的に減量し、ロバストな推定値が得られる。
論文 参考訳（メタデータ） (2021-12-13T16:12:22Z) - AgFlow: Fast Model Selection of Penalized PCA via Implicit
Regularization Effects of Gradient Flow [64.81110234990888]
主成分分析(PCA)は特徴抽出と次元減少の有効な手法として広く用いられている。
High Dimension Low Sample Size (HDLSS) 設定では、ペナル化ロードを備えた修正主成分が好まれる。
ペナル化PCAの高速モデル選択法として近似勾配流(AgFlow)を提案する。
論文 参考訳（メタデータ） (2021-10-07T08:57:46Z) - Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
空間的制約が存在する場合の高次元統計量と非破壊的最適化の関連について検討する。
これらの問題に対する新規で簡単な最適化法を開発した。
結論として、効率よくステーションに収束する一階法は、これらのタスクに対して効率的なアルゴリズムを導出する。
論文 参考訳（メタデータ） (2021-09-23T17:38:24Z) - FAST-PCA: A Fast and Exact Algorithm for Distributed Principal Component
Analysis [12.91948651812873]
主成分分析(PCA)は、機械学習の世界における基本的なデータ前処理ツールである。
本稿では,FAST-PCA (Fast and exact distributed PCA) と呼ばれる分散PCAアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-08-27T16:10:59Z) - Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature
Selection [138.97647716793333]
再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。
提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
論文 参考訳（メタデータ） (2020-12-29T04:08:38Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
主成分分析(PCA)は、機械学習と統計学において広く使われている次元削減手法である。
スパース主成分分析(Sparse principal Component Analysis)と呼ばれる,スパース主成分負荷を求める様々な手法が提案されている。
本研究では,SPCA問題に対するしきい値の精度,時間,近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-23T04:25:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。