論文の概要: On Recovering the Best Rank-r Approximation from Few Entries

• arxiv url: http://arxiv.org/abs/2111.06302v1
• Date: Thu, 11 Nov 2021 16:40:18 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-12 15:05:25.592549
• Title: On Recovering the Best Rank-r Approximation from Few Entries
• Title（参考訳）: 最良ランクr近似の最小エントリからの復元について
• Authors: Shun Xu, Ming Yuan
• Abstract要約: 少数のエントリから大行列の最高の階数-r$近似を再構成する。 誤差は行列が低ランクであることの近さに依存することを示す。
• 参考スコア（独自算出の注目度）: 10.166435679260015
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this note, we investigate how well we can reconstruct the best rank-$r$ approximation of a large matrix from a small number of its entries. We show that even if a data matrix is of full rank and cannot be approximated well by a low-rank matrix, its best low-rank approximations may still be reliably computed or estimated from a small number of its entries. This is especially relevant from a statistical viewpoint: the best low-rank approximations to a data matrix are often of more interest than itself because they capture the more stable and oftentimes more reproducible properties of an otherwise complicated data-generating model. In particular, we investigate two agnostic approaches: the first is based on spectral truncation; and the second is a projected gradient descent based optimization procedure. We argue that, while the first approach is intuitive and reasonably effective, the latter has far superior performance in general. We show that the error depends on how close the matrix is to being of low rank. Both theoretical and numerical evidence is presented to demonstrate the effectiveness of the proposed approaches.
• Abstract（参考訳）: 本稿では,大行列の最大ランク-$r$近似を少数のエントリからいかにうまく再構築できるかについて検討する。 本研究では,データ行列が全ランクであり,低ランク行列では近似できない場合でも,その最良な低ランク近似は,少数のエントリから確実に計算されるか,あるいは推定できることを示す。 データマトリックスに対する最高の低ランク近似は、しばしばそれ自身よりも興味を引いている。なぜなら、より安定で、しばしば、より複雑なデータ生成モデルの再現可能な特性を捉えるからである。 特に、スペクトルトランケーションに基づく2つの非依存的アプローチと、投射された勾配降下に基づく最適化手法について検討する。 第一のアプローチは直感的で合理的に有効であるが、後者は一般にはるかに優れた性能を持つ。 誤差は行列が低位であることにどの程度近いかに依存することを示した。 理論的および数値的な証拠はともに提案手法の有効性を示すものである。

関連論文リスト

• Entrywise error bounds for low-rank approximations of kernel matrices [55.524284152242096]
  切り抜き固有分解を用いて得られたカーネル行列の低ランク近似に対するエントリーワイド誤差境界を導出する。 重要な技術的革新は、小さな固有値に対応するカーネル行列の固有ベクトルの非局在化結果である。 我々は、合成および実世界のデータセットの集合に関する実証的研究により、我々の理論を検証した。
  論文  参考訳（メタデータ） (2024-05-23T12:26:25Z)
• Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning [53.445068584013896]
  低ランク構造を持つ強化学習(RL)における行列推定問題について検討した。 低ランク帯では、回収される行列は期待される腕の報酬を指定し、低ランクマルコフ決定プロセス(MDP)では、例えばMDPの遷移カーネルを特徴付ける。 簡単なスペクトルベースの行列推定手法は,行列の特異部分空間を効率よく復元し,ほぼ最小の入力誤差を示すことを示す。
  論文  参考訳（メタデータ） (2023-10-10T17:06:41Z)
• Sparse Factorization of Large Square Matrices [10.94053598642913]
  本稿では,大面積の正方行列とスパースフルランク行列の積を近似する。 近似では、我々の手法は$Ntimes N$ full matrix に対して$N(log N)2$ non-zero number しか必要としない。 近似行列がスパースかつハイランクである場合,本手法により近似精度が向上することを示す。
  論文  参考訳（メタデータ） (2021-09-16T18:42:21Z)
• Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
  任意のランクの正方形密度あるいはスパース行列の統計レバレッジスコアを推定するアルゴリズムについて検討した。 提案手法は,高密度およびスパースなランダム化次元性還元変換の合成と階調明細化法を組み合わせることに基づく。
  論文  参考訳（メタデータ） (2021-05-23T19:21:55Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。 提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
  論文  参考訳（メタデータ） (2020-12-29T04:08:38Z)
• Robust Low-rank Matrix Completion via an Alternating Manifold Proximal Gradient Continuation Method [47.80060761046752]
  ロバスト低ランク行列補完(RMC)は、コンピュータビジョン、信号処理、機械学習アプリケーションのために広く研究されている。 この問題は、部分的に観察された行列を低ランク行列とスパース行列の重ね合わせに分解することを目的とした。 RMCに取り組むために広く用いられるアプローチは、低ランク行列の核ノルム(低ランク性を促進するために)とスパース行列のl1ノルム(空間性を促進するために)を最小化する凸定式化を考えることである。 本稿では、近年のローワークの動機付けについて述べる。
  論文  参考訳（メタデータ） (2020-08-18T04:46:22Z)
• Median Matrix Completion: from Embarrassment to Optimality [16.667260586938234]
  絶対偏差損失を持つ行列の完全性を考察し,中央値行列の推定値を求める。 中央値のいくつかの魅力的な性質にもかかわらず、非滑らかな絶対偏差損失は計算に挑戦する。 そこで我々は,非効率な推定器を(最適に近い)行列補完手順に変換する改良ステップを提案する。
  論文  参考訳（メタデータ） (2020-06-18T10:01:22Z)
• Robust Matrix Completion with Mixed Data Types [0.0]
  我々は,データ型が混在する部分的なエントリを持つ構造的低ランク行列を復元する問題を考察する。 ほとんどのアプローチは、基礎となる分布は1つしかないと仮定し、低階の制約は、行列 Satten Norm によって正則化される。 本稿では, 並列化に適したアルゴリズムフレームワークとともに, 高い回復保証を有する計算可能な統計手法を提案し, 混合データ型に対する部分的に観測されたエントリを持つ低階行列を1ステップで復元する。
  論文  参考訳（メタデータ） (2020-05-25T21:35:10Z)
• Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent [34.0533596121548]
  低ランク行列推定は凸問題を収束させ、信号処理、機械学習、画像科学に多くの応用を見出す。 低ランク行列の個数の観点から,ScaledGDが最良となることを示す。 我々の分析は、低ランク勾配降下に類似した一般損失にも適用できる。
  論文  参考訳（メタデータ） (2020-05-18T17:17:16Z)
• Discrete-Valued Latent Preference Matrix Estimation with Graph Side Information [12.836994708337144]
  最適なサンプルの複雑さにマッチするアルゴリズムを開発する。 我々のアルゴリズムはエラーをモデル化し、予測性能の点で既存のアルゴリズムより優れている。
  論文  参考訳（メタデータ） (2020-03-16T06:29:24Z)
• Improved guarantees and a multiple-descent curve for Column Subset Selection and the Nystr\"om method [76.73096213472897]
  我々は,データ行列のスペクトル特性を利用して近似保証を改良する手法を開発した。 我々のアプローチは、特異値減衰の既知の速度を持つデータセットのバウンダリが大幅に向上する。 RBFパラメータを変更すれば,改良された境界線と多重発振曲線の両方を実データセット上で観測できることが示される。
  論文  参考訳（メタデータ） (2020-02-21T00:43:06Z)

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

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