Fugu-MT 論文翻訳(概要): Randomly Pivoted Partial Cholesky: Random How?

論文の概要: Randomly Pivoted Partial Cholesky: Random How?

arxiv url: http://arxiv.org/abs/2404.11487v1
Date: Wed, 17 Apr 2024 15:45:31 GMT
ステータス: 処理完了
システム内更新日: 2024-04-18 13:25:44.192243
Title: Randomly Pivoted Partial Cholesky: Random How?
Title（参考訳）: Randomly Pivoted Partial Cholesky:Random How?
Authors: Stefan Steinerberger,
Abstract要約: A_ii$ に比例する確率の $i-$th 列を選択するランダムにピボットされた部分チョレスキーアルゴリズムは、トレースノルムの普遍的収縮をもたらすことを示す。 A_ii2$ 1 に比例して $i-$th 行を選択すると、フロベニウスノルムにおいて同じ結果が得られる(シャッテン 2-ノルム)。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We consider the problem of finding good low rank approximations of symmetric, positive-definite $A \in \mathbb{R}^{n \times n}$. Chen-Epperly-Tropp-Webber showed, among many other things, that the randomly pivoted partial Cholesky algorithm that chooses the $i-$th row with probability proportional to the diagonal entry $A_{ii}$ leads to a universal contraction of the trace norm (the Schatten 1-norm) in expectation for each step. We show that if one chooses the $i-$th row with likelihood proportional to $A_{ii}^2$ one obtains the same result in the Frobenius norm (the Schatten 2-norm). Implications for the greedy pivoting rule and pivot selection strategies are discussed.
Abstract（参考訳）: 我々は、対称で正定値な$A \in \mathbb{R}^{n \times n}$の良好な低階近似を求める問題を考える。 Chen-Epperly-Tropp-Webber は、無作為に選択されたColeskyアルゴリズムは、各ステップに期待するトレースノルム (Schatten 1-norm) を普遍的に収縮させることを示した。 A_{ii}^2$ 1 に比例して $i-$th 列を選択すると、フロベニウスノルム (Schatten 2-norm) において同じ結果が得られることを示す。グリーディ・ピボット・ルールとピボット・セレクション・ストラテジーの意義について論じる。

関連論文リスト

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)
Revisiting Step-Size Assumptions in Stochastic Approximation [1.3654846342364308]
この論文は、一般的なマルコフ的な設定でステップサイズの選択を再考する。大きな結論は、$rho =0$ または $rho1/2$ の選択は、選択した設定でのみ正当化されるということである。
論文参考訳（メタデータ） (2024-05-28T05:11:05Z)
$L^1$ Estimation: On the Optimality of Linear Estimators [64.76492306585168]
この研究は、条件中央値の線型性を誘導する$X$上の唯一の先行分布がガウス分布であることを示している。特に、条件分布 $P_X|Y=y$ がすべての$y$に対して対称であるなら、$X$ はガウス分布に従う必要がある。
論文参考訳（メタデータ） (2023-09-17T01:45:13Z)
Fitting an ellipsoid to a quadratic number of random points [10.208117253395342]
問題 $(mathrmP)$ が $n$ の標準ガウス確率ベクトルを $mathbbRd$ で中心楕円体の境界に収まることを $n, d to infty$ とみなす。任意の$varepsilon > 0$ に対して、$n leq (1 - varepsilon) d2 / 4$ ならば、$(mathrmP)$ は高い確率の解を持つ。
論文参考訳（メタデータ） (2023-07-03T17:46:23Z)
Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文参考訳（メタデータ） (2022-08-19T18:00:34Z)
Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文参考訳（メタデータ） (2022-08-11T04:12:50Z)
Risk-averse Contextual Multi-armed Bandit Problem with Linear Payoffs [7.125769932993104]
リスク・逆条件下での線形ペイオフに対するコンテキスト多重武装バンディット問題について考察する。各ラウンドにおいて、各アームのコンテキストが明らかにされ、意思決定者は1つのアームを選択して、対応する報酬を受け取ります。解離モデルに対してトンプソンサンプリングアルゴリズムを適用し,提案アルゴリズムの変種に対する包括的後悔解析を行う。
論文参考訳（メタデータ） (2022-06-24T18:48:35Z)
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)
Multivariate mean estimation with direction-dependent accuracy [8.147652597876862]
独立な同一分布観測に基づくランダムベクトルの平均を推定する問題を考察する。確率ベクトルの1次元辺の分散があまり小さくない全ての方向において、ほぼ最適誤差を持つ推定器を証明した。
論文参考訳（メタデータ） (2020-10-22T17:52:45Z)
Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。我々はCIFARに関する実験結果を示し,その理論を検証した。
論文参考訳（メタデータ） (2020-02-08T22:02:14Z)

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