論文の概要: Tackling small eigen-gaps: Fine-grained eigenvector estimation and
inference under heteroscedastic noise
- arxiv url: http://arxiv.org/abs/2001.04620v3
- Date: Tue, 7 Sep 2021 21:23:43 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-11 14:05:21.706420
- Title: Tackling small eigen-gaps: Fine-grained eigenvector estimation and
inference under heteroscedastic noise
- Title（参考訳）: 小さな固有ギャップに対処する:非定常雑音下での微細な固有ベクトル推定と推論
- Authors: Chen Cheng, Yuting Wei, Yuxin Chen
- Abstract要約: ノイズの観測から、固有ベクトル推定と低ランク行列の推測に2つの根本的な課題が生じる。
未知固有ベクトルに対する推定と不確実性定量化手法を提案する。
未知固有値に対する信頼区間を構築するための最適手順を確立する。
- 参考スコア（独自算出の注目度）: 28.637772416856194
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper aims to address two fundamental challenges arising in eigenvector
estimation and inference for a low-rank matrix from noisy observations: (1) how
to estimate an unknown eigenvector when the eigen-gap (i.e. the spacing between
the associated eigenvalue and the rest of the spectrum) is particularly small;
(2) how to perform estimation and inference on linear functionals of an
eigenvector -- a sort of "fine-grained" statistical reasoning that goes far
beyond the usual $\ell_2$ analysis. We investigate how to address these
challenges in a setting where the unknown $n\times n$ matrix is symmetric and
the additive noise matrix contains independent (and non-symmetric) entries.
Based on eigen-decomposition of the asymmetric data matrix, we propose
estimation and uncertainty quantification procedures for an unknown
eigenvector, which further allow us to reason about linear functionals of an
unknown eigenvector. The proposed procedures and the accompanying theory enjoy
several important features: (1) distribution-free (i.e. prior knowledge about
the noise distributions is not needed); (2) adaptive to heteroscedastic noise;
(3) minimax optimal under Gaussian noise. Along the way, we establish optimal
procedures to construct confidence intervals for the unknown eigenvalues. All
this is guaranteed even in the presence of a small eigen-gap (up to
$O(\sqrt{n/\mathrm{poly}\log (n)})$ times smaller than the requirement in prior
theory), which goes significantly beyond what generic matrix perturbation
theory has to offer.
- Abstract（参考訳）: 本稿では,(1)固有ギャップが特に小さいとき,未知の固有ベクトルを推定する方法,(2)固有ベクトルの線形汎関数に対する推定と推論を行う方法,すなわち通常の$\ell_2$解析をはるかに超越した「きめ細かい」統計的推論という,低ランク行列の固有ベクトル推定と推論に起因する2つの基本的な課題に対処することを目的とする。
未知の$n\times n$行列が対称であり、加法的雑音行列が独立(および非対称)成分を含むような環境でこれらの問題にどう対処するかを検討する。
非対称なデータ行列の固有分解に基づいて、未知の固有ベクトルに対する推定および不確実な定量化手順を提案し、未知の固有ベクトルの線形関数を推論する。
提案手法と付随する理論は,(1)分布自由(すなわち,雑音分布に関する事前知識は不要),(2)ヘテロシドスティックノイズに適応する,(3)ガウス雑音下で最適なミニマックスという,いくつかの重要な特徴を享受する。
その過程で,未知固有値に対する信頼区間を構築するための最適手順を確立する。
これら全ては、小さな固有ギャップ($O(\sqrt{n/\mathrm{poly}\log (n)})$ 以前の理論の要件よりも小さい)が存在する場合でも保証される。
関連論文リスト
- Entrywise error bounds for low-rank approximations of kernel matrices [55.524284152242096]
切り抜き固有分解を用いて得られたカーネル行列の低ランク近似に対するエントリーワイド誤差境界を導出する。
重要な技術的革新は、小さな固有値に対応するカーネル行列の固有ベクトルの非局在化結果である。
我々は、合成および実世界のデータセットの集合に関する実証的研究により、我々の理論を検証した。
論文 参考訳（メタデータ） (2024-05-23T12:26:25Z) - Quantum Eigensolver for General Matrices [5.811990276393904]
本稿では,一般行列に対する固有値問題の解法に適した新しい量子アルゴリズム群を提案する。
我々のアルゴリズムはマルコフ連鎖の緩和時間の推定を含む様々な領域の応用を見出す。
これらの応用は、様々な分野にわたる問題に対する量子固有解法の重要性を浮き彫りにしている。
論文 参考訳（メタデータ） (2024-01-22T16:29:08Z) - Private Covariance Approximation and Eigenvalue-Gap Bounds for Complex
Gaussian Perturbations [28.431572772564518]
この機構によって出力される行列と最高ランクの$k$の近似との差のフロベニウスノルムが、およそ$tildeO(sqrtkd)$で有界であることを示す。
これは、$M$のすべてのトップ-$k$固有値間のギャップが、同じ境界に対して少なくとも$sqrtd$であることを要求する以前の作業を改善する。
論文 参考訳（メタデータ） (2023-06-29T03:18:53Z) - General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean
Estimation [58.03500081540042]
プライベート平均推定に対する古典的なアプローチは、真の平均を計算し、バイアスのないがおそらく相関のあるガウスノイズを加えることである。
すべての入力データセットに対して、集中的な差分プライバシーを満たす非バイアス平均推定器が、少なくとも多くのエラーをもたらすことを示す。
論文 参考訳（メタデータ） (2023-01-31T18:47:42Z) - On confidence intervals for precision matrices and the
eigendecomposition of covariance matrices [20.20416580970697]
本稿では,固定次元の共分散行列の固有ベクトルの個々のエントリに対する信頼性境界の計算に挑戦する。
逆共分散行列、いわゆる精度行列の成分を束縛する手法を導出する。
これらの結果の応用として,精度行列の非ゼロ値のテストを可能にする新しい統計テストを示す。
論文 参考訳（メタデータ） (2022-08-25T10:12:53Z) - Learning Linear Symmetries in Data Using Moment Matching [0.0]
データから直接、そのような対称性を学習する、教師なし、半教師なしの問題を考察する。
最悪の場合、この問題はグラフ自己同型問題と同じくらい難しい。
対称変換において固有ベクトルが固有値 -1 を持つべきものを選択する様々な方法の有効性を理論的および実証的に開発・比較する。
論文 参考訳（メタデータ） (2022-04-04T02:47:37Z) - When Random Tensors meet Random Matrices [50.568841545067144]
本稿では,ガウス雑音を伴う非対称次数-$d$スパイクテンソルモデルについて検討する。
検討したモデルの解析は、等価なスパイクされた対称テクシットブロック-ワイドランダム行列の解析に起因していることを示す。
論文 参考訳（メタデータ） (2021-12-23T04:05:01Z) - Minimax Estimation of Linear Functions of Eigenvectors in the Face of
Small Eigen-Gaps [95.62172085878132]
固有ベクトル摂動解析は様々な統計データ科学の応用において重要な役割を果たす。
未知の固有ベクトルの任意の線型関数の摂動を特徴付ける統計理論の一組を開発する。
自然の「プラグイン」推定器に固有の非無視バイアス問題を緩和するために,非バイアス推定器を開発する。
論文 参考訳（メタデータ） (2021-04-07T17:55:10Z) - Leveraged Matrix Completion with Noise [84.20092979053119]
未知の$ntimes n$ matrix of rank $r$ from just $mathcalO(nrlog2 (n))$ entry.
我々の証明は、ゴルフスキームに基づく十分な最適条件を記述する新しいアプローチによって支持されている。
論文 参考訳（メタデータ） (2020-11-11T16:25:45Z) - Understanding Implicit Regularization in Over-Parameterized Single Index
Model [55.41685740015095]
我々は高次元単一インデックスモデルのための正規化自由アルゴリズムを設計する。
暗黙正則化現象の理論的保証を提供する。
論文 参考訳（メタデータ） (2020-07-16T13:27:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。