論文の概要: Fast algorithms for robust principal component analysis with an upper bound on the rank

• arxiv url: http://arxiv.org/abs/2008.07972v2
• Date: Thu, 3 Sep 2020 18:04:29 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-27 22:05:26.023263
• Title: Fast algorithms for robust principal component analysis with an upper bound on the rank
• Title（参考訳）: ランク上の上限を持つ頑健な主成分分析のための高速アルゴリズム
• Authors: Ningyu Sha and Lei Shi and Ming Yan
• Abstract要約: 堅牢な主成分分析(RPCA)は、データマトリックスをローランク部とスパース部に分解する。 最初のタイプのアルゴリズムは、行列の特異値に対して正規化項を適用して低ランク行列を得る。 2つ目のアルゴリズムは、2つの小さな行列の乗算として低ランク行列を置き換える。
• 参考スコア（独自算出の注目度）: 12.668565749446476
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The robust principal component analysis (RPCA) decomposes a data matrix into a low-rank part and a sparse part. There are mainly two types of algorithms for RPCA. The first type of algorithm applies regularization terms on the singular values of a matrix to obtain a low-rank matrix. However, calculating singular values can be very expensive for large matrices. The second type of algorithm replaces the low-rank matrix as the multiplication of two small matrices. They are faster than the first type because no singular value decomposition (SVD) is required. However, the rank of the low-rank matrix is required, and an accurate rank estimation is needed to obtain a reasonable solution. In this paper, we propose algorithms that combine both types. Our proposed algorithms require an upper bound of the rank and SVD on small matrices. First, they are faster than the first type because the cost of SVD on small matrices is negligible. Second, they are more robust than the second type because an upper bound of the rank instead of the exact rank is required. Furthermore, we apply the Gauss-Newton method to increase the speed of our algorithms. Numerical experiments show the better performance of our proposed algorithms.
• Abstract（参考訳）: 堅牢な主成分分析(RPCA)は、データマトリックスをローランク部とスパース部に分解する。 RPCAには2種類のアルゴリズムがある。 第1のアルゴリズムは、行列の特異値に対して正規化項を適用して低ランク行列を得る。 しかし、特異値を計算することは大きな行列にとって非常に高価である。 第2のアルゴリズムは、低ランク行列を2つの小さな行列の乗法として置き換える。 特異値分解(SVD)は不要であるため、最初の型よりも高速である。 しかし、低ランク行列の階数が必要であり、妥当な解を得るには正確な階数推定が必要である。 本稿では,両タイプを組み合わせたアルゴリズムを提案する。 提案アルゴリズムでは,小行列上でのランクとSVDの上限を求める。 第一に、小行列でのSVDのコストが無視できるため、最初のタイプよりも高速である。 第二に、正確なランクの代わりにランクの上限が必要となるため、それらは第二の型よりも頑健である。 さらに,アルゴリズムの高速化にgauss-newton法を適用した。 数値実験により提案アルゴリズムの性能が向上した。

関連論文リスト

• Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning [53.445068584013896]
  低ランク構造を持つ強化学習(RL)における行列推定問題について検討した。 低ランク帯では、回収される行列は期待される腕の報酬を指定し、低ランクマルコフ決定プロセス(MDP)では、例えばMDPの遷移カーネルを特徴付ける。 簡単なスペクトルベースの行列推定手法は,行列の特異部分空間を効率よく復元し,ほぼ最小の入力誤差を示すことを示す。
  論文  参考訳（メタデータ） (2023-10-10T17:06:41Z)
• Learning the Positions in CountSketch [49.57951567374372]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-11T07:28:35Z)
• Fundamental Machine Learning Routines as Quantum Algorithms on a Superconducting Quantum Computer [0.0]
  Harrow-Hassidim-Lloydアルゴリズムは、量子デバイス上の線形方程式のシステムを解くことを目的としている。 本稿では,これらの特徴が完全に一致しない場合のアルゴリズムの性能に関する数値的研究を行う。
  論文  参考訳（メタデータ） (2021-09-17T15:22:06Z)
• Sparse Factorization of Large Square Matrices [10.94053598642913]
  本稿では,大面積の正方行列とスパースフルランク行列の積を近似する。 近似では、我々の手法は$Ntimes N$ full matrix に対して$N(log N)2$ non-zero number しか必要としない。 近似行列がスパースかつハイランクである場合,本手法により近似精度が向上することを示す。
  論文  参考訳（メタデータ） (2021-09-16T18:42:21Z)
• Robust 1-bit Compressive Sensing with Partial Gaussian Circulant Matrices and Generative Priors [54.936314353063494]
  我々は,ロバストな1ビット圧縮センシングのための相関に基づく最適化アルゴリズムのリカバリ保証を提供する。 我々は,実用的な反復アルゴリズムを用いて,画像データセットの数値実験を行い,結果の相関付けを行う。
  論文  参考訳（メタデータ） (2021-08-08T05:28:06Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)
• Ranky : An Approach to Solve Distributed SVD on Large Sparse Matrices [0.0]
  特異値分解(SVD)は、多くの分野や応用分野においてよく研究されている研究トピックである。 そこで我々は,大小行列のランク問題を分散的に解く手法であるRandyを提案する。
  論文  参考訳（メタデータ） (2020-09-21T11:36:28Z)
• Rank $2r$ iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entries [4.230158563771147]
  低階行列補完のための新しい,単純で,計算効率のよい反復法を提案する。 我々のアルゴリズムは、R2RILS(R2RILS for rank $2r$peterative least squares)と呼ばれ、メモリ要件が低い。
  論文  参考訳（メタデータ） (2020-02-05T16:20:58Z)
• Fast Generalized Matrix Regression with Applications in Machine Learning [46.79740387890322]
  スケッチ技術を用いてGMR問題を効率的に解く高速一般化行列回帰アルゴリズム(Fast GMR)を提案する。 我々は,Fast GMRアルゴリズムを対称正定値行列近似と単一パス特異値分解に適用する。
  論文  参考訳（メタデータ） (2019-12-27T07:03:37Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。