論文の概要: Matrix Completion in Almost-Verification Time
- arxiv url: http://arxiv.org/abs/2308.03661v1
- Date: Mon, 7 Aug 2023 15:24:49 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-08 13:03:40.124831
- Title: Matrix Completion in Almost-Verification Time
- Title（参考訳）: ほぼ検証時間でのマトリックス補完
- Authors: Jonathan A. Kelner, Jerry Li, Allen Liu, Aaron Sidford, Kevin Tian
- Abstract要約: 99%の行と列で$mathbfM$を完了するアルゴリズムを提供する。
本稿では,この部分完備保証を完全行列補完アルゴリズムに拡張する方法を示す。
- 参考スコア（独自算出の注目度）: 37.61139884826181
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give a new framework for solving the fundamental problem of low-rank
matrix completion, i.e., approximating a rank-$r$ matrix $\mathbf{M} \in
\mathbb{R}^{m \times n}$ (where $m \ge n$) from random observations. First, we
provide an algorithm which completes $\mathbf{M}$ on $99\%$ of rows and columns
under no further assumptions on $\mathbf{M}$ from $\approx mr$ samples and
using $\approx mr^2$ time. Then, assuming the row and column spans of
$\mathbf{M}$ satisfy additional regularity properties, we show how to boost
this partial completion guarantee to a full matrix completion algorithm by
aggregating solutions to regression problems involving the observations.
In the well-studied setting where $\mathbf{M}$ has incoherent row and column
spans, our algorithms complete $\mathbf{M}$ to high precision from
$mr^{2+o(1)}$ observations in $mr^{3 + o(1)}$ time (omitting logarithmic
factors in problem parameters), improving upon the prior state-of-the-art
[JN15] which used $\approx mr^5$ samples and $\approx mr^7$ time. Under an
assumption on the row and column spans of $\mathbf{M}$ we introduce (which is
satisfied by random subspaces with high probability), our sample complexity
improves to an almost information-theoretically optimal $mr^{1 + o(1)}$, and
our runtime improves to $mr^{2 + o(1)}$. Our runtimes have the appealing
property of matching the best known runtime to verify that a rank-$r$
decomposition $\mathbf{U}\mathbf{V}^\top$ agrees with the sampled observations.
We also provide robust variants of our algorithms that, given random
observations from $\mathbf{M} + \mathbf{N}$ with $\|\mathbf{N}\|_{F} \le
\Delta$, complete $\mathbf{M}$ to Frobenius norm distance $\approx
r^{1.5}\Delta$ in the same runtimes as the noiseless setting. Prior noisy
matrix completion algorithms [CP10] only guaranteed a distance of $\approx
\sqrt{n}\Delta$.
- Abstract（参考訳）: 低ランク行列完備化の基本的な問題を解決するための新しい枠組み、すなわち、ランダムな観測からランク-$r$行列 $\mathbf{M} \in \mathbb{R}^{m \times n}$ (ここでは$m \ge n$) を近似する。
まず、$\mathbf{m}$を$\approx mr$サンプルから$\approx mr^2$ timeで$\mathbf{m}$の仮定なしで$99\%$で行と列の$\mathbf{m}$を完了するアルゴリズムを提供する。
次に、$\mathbf{M}$の行と列が追加の正則性特性を満たすことを仮定し、この部分完備保証を、観測を含む回帰問題に対する解を集約することにより、完全な行列完備化アルゴリズムにどのように拡張するかを示す。
ここで、$\mathbf{m}$ の行と列のスパンが一致しないよく検討された設定では、アルゴリズムは$\mathbf{m}$ を$mr^{2+o(1)}$ から高い精度まで、$mr^{3 + o(1)}$ の観測時間(問題パラメータの対数係数を省略する)で満たし、$\approx mr^5$ サンプルと $\approx mr^7$ の以前の状態(jn15] を改善した。
我々が導入する$\mathbf{m}$(確率の高いランダムな部分空間によって満たされる)の行と列スパンの仮定の下で、サンプル複雑性は概情報理論上最適な$mr^{1 + o(1)}$に改善され、ランタイムは$mr^{2 + o(1)}$に改善されます。
我々のランタイムは、最もよく知られたランタイムとマッチングして、ランク-$r$分解 $\mathbf{U}\mathbf{V}^\top$がサンプル観測と一致することを検証する魅力的な特性を持っています。
また、アルゴリズムのロバストな変種も提供し、$\mathbf{m} + \mathbf{n}$ with $\|\mathbf{n}\|_{f} \le \delta$, complete $\mathbf{m}$ to frobeniusノルム距離$\approx r^{1.5}\delta$ が無ノイズ設定と同じランタイムで与えられる。
以前の騒がしい行列補完アルゴリズム [cp10] は、距離が$\approx \sqrt{n}\delta$ であった。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Sample-Efficient Linear Regression with Self-Selection Bias [7.605563562103568]
未知のインデックス設定における自己選択バイアスを伴う線形回帰の問題を考察する。
我々は,$mathbfw_1,ldots,mathbfw_kinを復元する,新しい,ほぼ最適なサンプル効率($k$)アルゴリズムを提案する。
このアルゴリズムは雑音の仮定をかなり緩めることに成功し、従って関連する最大線形回帰の設定にも成功している。
論文 参考訳（メタデータ） (2024-02-22T02:20:24Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - Optimal Estimator for Linear Regression with Shuffled Labels [17.99906229036223]
本稿では,シャッフルラベルを用いた線形回帰の課題について考察する。
mathbb Rntimes m の $mathbf Y、mathbb Rntimes p の mathbf Pi、mathbb Rptimes m$ の mathbf B、mathbb Rntimes m$ の $mathbf Win mathbb Rntimes m$ である。
論文 参考訳（メタデータ） (2023-10-02T16:44:47Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Randomized and Deterministic Attention Sparsification Algorithms for
Over-parameterized Feature Dimension [18.57735939471469]
我々は注意問題のスパシフィケーションを考慮する。
超大規模特徴量の場合、文の長さをほぼ線形に縮めることができる。
論文 参考訳（メタデータ） (2023-04-10T05:52:38Z) - A Nearly-Optimal Bound for Fast Regression with $\ell_\infty$ Guarantee [16.409210914237086]
行列 $Ain mathbbRntimes d$ とテンソル $bin mathbbRn$ が与えられたとき、 $ell_infty$ の回帰問題を考える。
このような$ell_infty$レグレッションの保証を得るためには、濃密なスケッチ行列を使わなければならない。
我々はまた、OCE(Oblivious Coordinate-wise Embedding)特性を利用した $ell_infty$ guarantee regression のための新しい分析フレームワークを開発した。
論文 参考訳（メタデータ） (2023-02-01T05:22:40Z) - Spectral properties of sample covariance matrices arising from random
matrices with independent non identically distributed columns [50.053491972003656]
関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$.
ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
論文 参考訳（メタデータ） (2021-09-06T14:21:43Z) - The Average-Case Time Complexity of Certifying the Restricted Isometry
Property [66.65353643599899]
圧縮センシングにおいて、100万倍のN$センシング行列上の制限等尺性(RIP)はスパースベクトルの効率的な再構成を保証する。
Mtimes N$ matrices with i.d.$mathcalN(0,1/M)$ entry。
論文 参考訳（メタデータ） (2020-05-22T16:55:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。