論文の概要: Perturbation Bounds for Low-Rank Inverse Approximations under Noise
- arxiv url: http://arxiv.org/abs/2510.25571v1
- Date: Wed, 29 Oct 2025 14:40:12 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-30 15:50:45.707218
- Title: Perturbation Bounds for Low-Rank Inverse Approximations under Noise
- Title（参考訳）: 低域逆近似の雑音下での摂動境界
- Authors: Phuc Tran, Nisheeth K. Vishnoi,
- Abstract要約: スペクトルノルム誤差 $| (tildeA-1)_p - A_p-1 |$ for a $ntimes n$ symmetric matrix $A$, where $A_p-1$ is the best rank-(p) approximation of $A-1$, and $tildeA = A + E$ is a noisy observed。
ノイズの軽度な仮定の下で、固有ギャップ、スペクトル崩壊とどのように誤差がスケールするかを明らかにする鋭い非漸近境界を導出する。
- 参考スコア（独自算出の注目度）: 14.907968476859219
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Low-rank pseudoinverses are widely used to approximate matrix inverses in scalable machine learning, optimization, and scientific computing. However, real-world matrices are often observed with noise, arising from sampling, sketching, and quantization. The spectral-norm robustness of low-rank inverse approximations remains poorly understood. We systematically study the spectral-norm error $\| (\tilde{A}^{-1})_p - A_p^{-1} \|$ for an $n\times n$ symmetric matrix $A$, where $A_p^{-1}$ denotes the best rank-\(p\) approximation of $A^{-1}$, and $\tilde{A} = A + E$ is a noisy observation. Under mild assumptions on the noise, we derive sharp non-asymptotic perturbation bounds that reveal how the error scales with the eigengap, spectral decay, and noise alignment with low-curvature directions of $A$. Our analysis introduces a novel application of contour integral techniques to the \emph{non-entire} function $f(z) = 1/z$, yielding bounds that improve over naive adaptations of classical full-inverse bounds by up to a factor of $\sqrt{n}$. Empirically, our bounds closely track the true perturbation error across a variety of real-world and synthetic matrices, while estimates based on classical results tend to significantly overpredict. These findings offer practical, spectrum-aware guarantees for low-rank inverse approximations in noisy computational environments.
- Abstract（参考訳）: 低ランクの擬似逆数は、スケーラブルな機械学習、最適化、科学計算において行列逆を近似するために広く使われている。
しかし、実世界の行列はサンプリング、スケッチ、量子化によって生じるノイズでしばしば観察される。
低ランク逆近似のスペクトル-ノルムロバスト性は未だよく理解されていない。
スペクトルノルム誤差 $\| (\tilde{A}^{-1})_p - A_p^{-1} \|$ for a $n\times n$ symmetric matrix $A$, where $A_p^{-1}$ is the best rank-\(p\) approximation of $A^{-1}$, and $\tilde{A} = A + E$ is a noisy observed。
ノイズの軽度な仮定の下では、誤差が固有ギャップ、スペクトル減衰、低曲率方向のノイズアライメントでどのようにスケールするかを明らかにする、鋭い非漸近摂動境界を導出する。
本分析では,古典的全逆有界のネーブな適応を最大$\sqrt{n}$まで向上させるような有界化を得られるような,等角積分の新たな応用を,emph{non-entire} 関数 $f(z) = 1/z$ に導入する。
経験的に、我々の境界は、様々な実世界および合成行列における真の摂動誤差をよく追跡するが、古典的な結果に基づく推定は、かなり過大評価される傾向がある。
これらの結果は、雑音の多い計算環境における低ランク逆近似の実用的なスペクトル認識保証を提供する。
関連論文リスト
- Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy [13.264499801590583]
mathbbRn 倍 n$ の対称行列 $A と任意の対称摂動 E$ に対して、新しい高確率スペクトル-ノルム摂動境界を導入する。
穏やかな固有ギャップとノルム条件の下では、我々の境界は$|(A + E)_p - A_p|$に対して鋭い推定値を得るが、最大で$sqrtn$となる。
応用として,PCAの実用性保証の改善を導出し,文献の未解決問題を解消する。
論文 参考訳（メタデータ） (2025-10-29T16:36:00Z) - Private Low-Rank Approximation for Covariance Matrices, Dyson Brownian Motion, and Eigenvalue-Gap Bounds for Gaussian Perturbations [29.212403229351253]
ガウス機構の複素変項を解析し、この機構によって出力される行列と最高のランク-k$近似との差のフロベニウスノルムの上界を求める。
ガウス雑音によって摂動される行列の固有値$M$は高い確率で大きなギャップを持つことを示す。
論文 参考訳（メタデータ） (2025-02-11T15:46:03Z) - Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping [21.865728815935665]
重み付き雑音下での最初の収束を提供するが、切断はしない。
また、テールインデックス$mathfrakp$が事前に不明な場合には、最初の$mathcalO(Tfrac1-mathfrakp3mathfrakp-2)$収束率も設定する。
論文 参考訳（メタデータ） (2024-12-27T08:46:46Z) - Some Constructions of Private, Efficient, and Optimal $K$-Norm and Elliptic Gaussian Noise [54.34628844260993]
微分プライベートな計算は、しばしば$d$次元統計学の感度に束縛されて始まる。
純粋な微分プライバシーのために、$K$-normメカニズムは統計学の感度空間に合わせた規範を用いてこのアプローチを改善することができる。
本稿では,総和,数,投票の単純な統計量について両問題を解く。
論文 参考訳（メタデータ） (2023-09-27T17:09:36Z) - General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean
Estimation [58.03500081540042]
プライベート平均推定に対する古典的なアプローチは、真の平均を計算し、バイアスのないがおそらく相関のあるガウスノイズを加えることである。
すべての入力データセットに対して、集中的な差分プライバシーを満たす非バイアス平均推定器が、少なくとも多くのエラーをもたらすことを示す。
論文 参考訳（メタデータ） (2023-01-31T18:47:42Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。
我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
論文 参考訳（メタデータ） (2022-03-18T18:50:52Z) - Optimal Online Generalized Linear Regression with Stochastic Noise and
Its Application to Heteroscedastic Bandits [88.6139446295537]
一般化線形モデルの設定におけるオンライン一般化線形回帰の問題について検討する。
ラベルノイズに対処するため、古典的追従正規化リーダ(FTRL)アルゴリズムを鋭く解析する。
本稿では,FTRLに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-28T08:25:26Z) - Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization
under Infinite Noise Variance [17.199063087458907]
我々は一様凸ミラーマップのクラスを用いてミラーDescentアルゴリズムの収束率を定量化する。
このアルゴリズムは明確な勾配クリッピングや正規化を必要としない。
我々は,1次オラクルのみを用いた他のアルゴリズムでは改善率を達成できないことを示す情報理論の下界を補完する。
論文 参考訳（メタデータ） (2022-02-23T17:08:40Z) - Noise Regularizes Over-parameterized Rank One Matrix Recovery, Provably [42.427869499882206]
階数 1 の行列 $Y*$ by $XXtop$ をパラメータ化します。
次に,2乗損失関数を用いたランダムな摂動勾配降下法により得られた推定値の平均2乗誤差が$O(sigma2/d)$であることを示す。
対照的に、ランダムな摂動を伴わない勾配降下から得られる推定器は、平均2乗誤差が$O(sigma2)$となる。
論文 参考訳（メタデータ） (2022-02-07T21:53:51Z) - Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳（メタデータ） (2021-12-23T18:47:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。