論文の概要: Probabilistic Analysis of Least Squares, Orthogonal Projection, and QR Factorization Algorithms Subject to Gaussian Noise

• arxiv url: http://arxiv.org/abs/2409.18905v1
• Date: Fri, 27 Sep 2024 16:44:43 GMT
• ステータス: 処理完了
• システム内更新日: 2024-10-01 07:51:30.150210
• Title: Probabilistic Analysis of Least Squares, Orthogonal Projection, and QR Factorization Algorithms Subject to Gaussian Noise
• Title（参考訳）: ガウス雑音下における最小二乗・直交射影・QR分解アルゴリズムの確率論的解析
• Authors: Ali Lotfi, Julien Langou, Mohammad Meysami,
• Abstract要約: Liesen et al. (2002) を拡張し、正則行列 Q の条件数が列が加わったときにどのように変化するかを分析する。 これらの結果は、QR分解アルゴリズムのような数値法にこれらの結果を適用する際に強い仮定であるQの正確な算術と正則性を仮定する。 本研究では, 完全正則性を仮定することなく, 行列 B の条件数増加に関する境界を導出することにより, このギャップに対処する。
• 参考スコア（独自算出の注目度）: 1.0923877073891446
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we extend the work of Liesen et al. (2002), which analyzes how the condition number of an orthonormal matrix Q changes when a column is added ([Q, c]), particularly focusing on the perpendicularity of c to the span of Q. Their result, presented in Theorem 2.3 of Liesen et al. (2002), assumes exact arithmetic and orthonormality of Q, which is a strong assumption when applying these results to numerical methods such as QR factorization algorithms. In our work, we address this gap by deriving bounds on the condition number increase for a matrix B without assuming perfect orthonormality, even when a column is not perfectly orthogonal to the span of B. This framework allows us to analyze QR factorization methods where orthogonalization is imperfect and subject to Gaussian noise. We also provide results on the performance of orthogonal projection and least squares under Gaussian noise, further supporting the development of this theory.
• Abstract（参考訳）: 本稿では、列が加わったとき([Q, c])に正則行列 Q の条件数がどのように変化するかを解析する Liesen et al (2002) の研究を拡張し、特に C の垂直度を Q のスパンに焦点をあてて、その結果を Liesen et al (2002) の Theorem 2.3 に示した。 本研究は, 行列 B が完全直交ではない場合でも, 完全直交性を前提とせず, 行列 B の条件数増加に関する境界を導出することにより, このギャップを解消するものである。 また、ガウス雑音下での直交射影と最小四角形の性能についての結果も提示し、この理論の発展を後押しする。

関連論文リスト

• Intrinsic Bayesian Cramér-Rao Bound with an Application to Covariance Matrix Estimation [49.67011673289242]
  本稿では, 推定パラメータが滑らかな多様体内にある推定問題に対して, 新たな性能境界を提案する。 これはパラメータ多様体の幾何学と推定誤差測度の本質的な概念を誘導する。
  論文  参考訳（メタデータ） (2023-11-08T15:17:13Z)
• Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability [107.65337427333064]
  AUPRC(Area Under the Precision-Recall Curve)の最適化は、機械学習にとって重要な問題である。 本研究では, AUPRC最適化の単依存一般化における最初の試行について述べる。 3つの画像検索データセットの実験は、我々のフレームワークの有効性と健全性に言及する。
  論文  参考訳（メタデータ） (2022-09-27T09:06:37Z)
• Robust Matrix Completion with Heavy-tailed Noise [0.5837881923712392]
  本稿では,重み付き潜在的非対称雑音の存在下での低ランク行列の完全性について検討する。 本稿では,大規模かつ非対称な誤りに対して頑健な重み付き雑音に適応するハマー損失を適応的に適用する。 誤差の2番目のモーメント条件下では、ユークリッド誤差は最小値の統計的推定誤差に到達するまで幾何的に早く落ちることが証明される。
  論文  参考訳（メタデータ） (2022-06-09T04:48:48Z)
• Square Root Marginalization for Sliding-Window Bundle Adjustment [53.34552451834707]
  実時間オドメトリーに適合する新しい正方形根のすべり窓束の調整法を提案する。 提案した平方根辺化は、ヘシアン上でのシュール補数(SC)の従来の使用と代数的に等価であることを示す。 実世界のデータセットにおける視覚的および視覚的慣性オドメトリーの評価は,提案した推定器がベースラインよりも36%高速であることを示す。
  論文  参考訳（メタデータ） (2021-09-05T23:22:38Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。 次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
  論文  参考訳（メタデータ） (2021-05-03T16:36:27Z)
• Symmetric Boolean Factor Analysis with Applications to InstaHide [18.143740528953142]
  InstaHideは、中程度に大規模なkに対する再構築攻撃に対して、ある種の「きめ細かいセキュリティ」を持っていることを示す。 我々のアルゴリズムはテンソル分解に基づいており、m は r において少なくとも準線形である必要がある。 この結果は、k-スパースベクトルの集合が任意に選択される問題の最悪のケース設定のための準ポリノミカル時間アルゴリズムで補完する。
  論文  参考訳（メタデータ） (2021-02-02T15:52:52Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)
• Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximation [4.817429789586127]
  基礎となるマルコフ連鎖が可逆で幾何学的にエルゴードである場合でも、誤差列に有界なホーフディングを得ることはできない。 平均二乗誤差は、ステップサイズシーケンスの条件の下で、$O(1/n)$の最適率を達成する。
  論文  参考訳（メタデータ） (2020-02-07T01:52:21Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  最小二乗問題に対する反復スケッチの性能について検討する。 本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。 これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
  論文  参考訳（メタデータ） (2020-02-03T16:17:50Z)
• Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Data [20.31071912733189]
  本稿では,低ランク行列推定における凸プログラミング手法の理論的保証を改良した。 原理的凸プログラムはユークリッド損失とell_infty$損失の両方の観点から、ほぼ最適統計精度を達成することを示す。
  論文  参考訳（メタデータ） (2020-01-15T18:54:29Z)

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

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