論文の概要: On Unbiased Low-Rank Approximation with Minimum Distortion

• arxiv url: http://arxiv.org/abs/2505.09647v1
• Date: Mon, 12 May 2025 20:52:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-16 22:29:06.031805
• Title: On Unbiased Low-Rank Approximation with Minimum Distortion
• Title（参考訳）: 最小歪みをもつ非偏平低ランク近似について
• Authors: Leighton Pate Barnes, Stephen Cameron, Benjamin Howard,
• Abstract要約: 固定されたターゲット行列を最もよく近似する低ランクランダム行列 $Q$ をサンプリングするアルゴリズムを次のように説明する: $Q$ is unbiased, すなわち$mathbbE[Q] = P$; $mathsfrank(Q)leq r$; $Q$は期待されるフロベニウスノルム誤差 $mathbbE|P-Q|_F2$ を最小化する。
• 参考スコア（独自算出の注目度）: 1.2016264781280588
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We describe an algorithm for sampling a low-rank random matrix $Q$ that best approximates a fixed target matrix $P\in\mathbb{C}^{n\times m}$ in the following sense: $Q$ is unbiased, i.e., $\mathbb{E}[Q] = P$; $\mathsf{rank}(Q)\leq r$; and $Q$ minimizes the expected Frobenius norm error $\mathbb{E}\|P-Q\|_F^2$. Our algorithm mirrors the solution to the efficient unbiased sparsification problem for vectors, except applied to the singular components of the matrix $P$. Optimality is proven by showing that our algorithm matches the error from an existing lower bound.
• Abstract（参考訳）: 低ランクランダム行列 $Q$ をサンプリングするアルゴリズムについて説明する: $Q$ is unbiased, すなわち $\mathbb{E}[Q] = P$; $\mathsf{rank}(Q)\leq r$; $Q$ は期待されるフロベニウスノルム誤差 $\mathbb{E}\|P-Q\|_F^2$ を最小化する。 我々のアルゴリズムは、行列の特異成分である$P$を除いたベクトルに対する効率的な非偏化問題の解を反映する。 最適性は、我々のアルゴリズムが既存の下界の誤差と一致することを示すことによって証明される。

関連論文リスト

• 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)
• Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation [9.10876982856809]
  我々は,更新を概ね計算できる最小化の交互化フレームワークを開発した。 我々のフレームワークの核心は、反復最小化の堅牢な解析とともに、高精度な多重応答回帰解法である。
  論文  参考訳（メタデータ） (2023-06-07T05:38:55Z)
• List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering [42.526664955704746]
  そこで我々は,リストデコダブルなスパース平均推定のための,新しい,概念的にシンプルな手法を開発した。 特に、$k$-sparse方向の「確実に有界な」$t-thモーメントを持つ分布の場合、このアルゴリズムは、サンプル複雑性$m = (klog(n))O(t)/alpha(mnt)$の誤差を1/alpha(O (1/t)$で達成する。 Gaussian inliers の特別な場合、我々のアルゴリズムは $Theta (sqrtlog) の最適誤差を保証する。
  論文  参考訳（メタデータ） (2022-06-10T17:38:18Z)
• Nonparametric Matrix Estimation with One-Sided Covariates [5.457150493905064]
  mathbbRntimes m$ のデータセット $X をスパシティ $p$ で観測する行列推定のタスクを考える。 我々は,行数が小さすぎる場合に,各行を別々に推定することで,アルゴリズムの精度が向上することを示すアルゴリズムと解析を提供する。
  論文  参考訳（メタデータ） (2021-10-26T19:11:45Z)
• 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)
• Unique sparse decomposition of low rank matrices [17.037882881652617]
  低階行列Yin mathbbRrtimes n$ のユニークな分解が見つかる。 我々は、ある$Yin MathRrtimes n$が$Xin mathbbRrtimes n$のスパースワイズ分解であることを示す。
  論文  参考訳（メタデータ） (2021-06-14T20:05:59Z)
• Sparse sketches with small inversion bias [79.77110958547695]
  逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。 本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。 スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
  論文  参考訳（メタデータ） (2020-11-21T01:33:15Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)

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

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