論文の概要: Rank $2r$ iterative least squares: efficient recovery of ill-conditioned
low rank matrices from few entries
- arxiv url: http://arxiv.org/abs/2002.01849v2
- Date: Wed, 28 Oct 2020 17:10:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-03 21:56:37.744989
- Title: Rank $2r$ iterative least squares: efficient recovery of ill-conditioned
low rank matrices from few entries
- Title（参考訳）: ランク2r$反復最小二乗:少ないエントリから不条件下階行列の効率的な回復
- Authors: Jonathan Bauch, Boaz Nadler and Pini Zilber
- Abstract要約: 低階行列補完のための新しい,単純で,計算効率のよい反復法を提案する。
我々のアルゴリズムは、R2RILS(R2RILS for rank $2r$peterative least squares)と呼ばれ、メモリ要件が低い。
- 参考スコア（独自算出の注目度）: 4.230158563771147
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a new, simple and computationally efficient iterative method for
low rank matrix completion. Our method is inspired by the class of
factorization-type iterative algorithms, but substantially differs from them in
the way the problem is cast. Precisely, given a target rank $r$, instead of
optimizing on the manifold of rank $r$ matrices, we allow our interim estimated
matrix to have a specific over-parametrized rank $2r$ structure. Our algorithm,
denoted R2RILS for rank $2r$ iterative least squares, has low memory
requirements, and at each iteration it solves a computationally cheap sparse
least-squares problem. We motivate our algorithm by its theoretical analysis
for the simplified case of a rank-1 matrix. Empirically, R2RILS is able to
recover ill conditioned low rank matrices from very few observations -- near
the information limit, and it is stable to additive noise.
- Abstract（参考訳）: 低階行列補完のための新しい,単純で,計算効率のよい反復法を提案する。
本手法は因子分解型反復アルゴリズムのクラスに着想を得たものであるが,問題のキャスティング方法とは大きく異なる。
正確には、対象の階数 $r$ が与えられたとき、階数 $r$ の多様体を最適化する代わりに、中間推定行列が特定の過度な階数 $2r$ 構造を持つようにします。
r2rils for rank $2r$ iterative least squaresと表記されたこのアルゴリズムは、メモリ要件が低く、各イテレーションで計算コストの低い最小二乗問題を解く。
ランク-1行列の簡素な場合に対する理論解析により, アルゴリズムの動機付けを行う。
経験的に、R2RILSは情報限界に近い非常に少数の観測結果から、条件の悪い低ランク行列を復元することができ、付加雑音に対して安定である。
関連論文リスト
- Model-free Low-Rank Reinforcement Learning via Leveraged Entry-wise Matrix Estimation [48.92318828548911]
政策改善と政策評価の段階を交互に行うモデルフリー学習アルゴリズムであるLoRa-PI(Low-Rank Policy Iteration)を提案する。
LoRa-PIは$widetildeO(S+Aover mathrmpoly (1-gamma)varepsilon2)$サンプルを使用して$varepsilon$-optimal Policyを学習する。
論文 参考訳（メタデータ） (2024-10-30T20:22:17Z) - 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) - One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
行列の欠落値を$XTX$で計算する自然アルゴリズムを提案する。
合成データの一方の回収と低被覆ゲノムシークエンシングについて,本アルゴリズムの評価を行った。
論文 参考訳（メタデータ） (2023-06-06T22:35:16Z) - Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time [8.808780937701522]
我々は、より効率的でエラーの少ない最小化フレームワークに向けて、大きな一歩を踏み出します。
我々のアルゴリズムは時間$widetilde O(|Omega| k)$で実行され、解の検証にはほぼ線形である。
論文 参考訳（メタデータ） (2023-02-21T23:49:36Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Unique sparse decomposition of low rank matrices [17.037882881652617]
低階行列Yin mathbbRrtimes n$ のユニークな分解が見つかる。
我々は、ある$Yin MathRrtimes n$が$Xin mathbbRrtimes n$のスパースワイズ分解であることを示す。
論文 参考訳（メタデータ） (2021-06-14T20:05:59Z) - Hutch++: Optimal Stochastic Trace Estimation [75.45968495410048]
我々は、任意の正半定値(PSD)$A$に対して、$(1 pm epsilon)$を$tr(A)$に近似する新しいランダム化アルゴリズムであるHutch++を導入する。
実験ではハッチンソン法を著しく上回る結果を得た。
論文 参考訳（メタデータ） (2020-10-19T16:45:37Z) - Fast algorithms for robust principal component analysis with an upper
bound on the rank [12.668565749446476]
堅牢な主成分分析(RPCA)は、データマトリックスをローランク部とスパース部に分解する。
最初のタイプのアルゴリズムは、行列の特異値に対して正規化項を適用して低ランク行列を得る。
2つ目のアルゴリズムは、2つの小さな行列の乗算として低ランク行列を置き換える。
論文 参考訳（メタデータ） (2020-08-18T15:07:57Z) - Optimal Exact Matrix Completion Under new Parametrization [0.0]
適応サンプリング法を用いて、$m倍 n$ の階数 $r$ の行列の正確な完備化の問題を研究した。
対象行列を正確に復元する行列補完アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-02-06T18:31:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。