論文の概要: Estimation of Shortest Path Covariance Matrices
- arxiv url: http://arxiv.org/abs/2011.09986v1
- Date: Thu, 19 Nov 2020 17:37:46 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-23 21:52:49.794624
- Title: Estimation of Shortest Path Covariance Matrices
- Title（参考訳）: 最短経路共分散行列の推定
- Authors: Raj Kumar Maity and Cameron Musco
- Abstract要約: 共分散行列 $mathbfSigma in mathbbRdtimes d$ of a distribution $mathcal D$ over $mathbbRd$ given independent sample。
単に$O(sqrtD)$エントリ複雑性と$tilde O(r)を使って、標準エラーまで$mathbfSigma$を推定するための非常に単純なアルゴリズムを提供する。
- 参考スコア（独自算出の注目度）: 21.772761365915176
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the sample complexity of estimating the covariance matrix
$\mathbf{\Sigma} \in \mathbb{R}^{d\times d}$ of a distribution $\mathcal D$
over $\mathbb{R}^d$ given independent samples, under the assumption that
$\mathbf{\Sigma}$ is graph-structured. In particular, we focus on shortest path
covariance matrices, where the covariance between any two measurements is
determined by the shortest path distance in an underlying graph with $d$ nodes.
Such matrices generalize Toeplitz and circulant covariance matrices and are
widely applied in signal processing applications, where the covariance between
two measurements depends on the (shortest path) distance between them in time
or space.
We focus on minimizing both the vector sample complexity: the number of
samples drawn from $\mathcal{D}$ and the entry sample complexity: the number of
entries read in each sample. The entry sample complexity corresponds to
measurement equipment costs in signal processing applications. We give a very
simple algorithm for estimating $\mathbf{\Sigma}$ up to spectral norm error
$\epsilon \left\|\mathbf{\Sigma}\right\|_2$ using just $O(\sqrt{D})$ entry
sample complexity and $\tilde O(r^2/\epsilon^2)$ vector sample complexity,
where $D$ is the diameter of the underlying graph and $r \le d$ is the rank of
$\mathbf{\Sigma}$. Our method is based on extending the widely applied idea of
sparse rulers for Toeplitz covariance estimation to the graph setting.
In the special case when $\mathbf{\Sigma}$ is a low-rank Toeplitz matrix, our
result matches the state-of-the-art, with a far simpler proof. We also give an
information theoretic lower bound matching our upper bound up to a factor $D$
and discuss some directions towards closing this gap.
- Abstract（参考訳）: 共分散行列 $\mathbf{\Sigma} \in \mathbb{R}^{d\times d}$ of a distribution $\mathcal D$ over $\mathbb{R}^d$ のサンプル複雑性を、$\mathbf{\Sigma}$がグラフ構造であると仮定して検討する。
特に,2つの測定値間の共分散が$d$ノードを持つグラフにおける最短経路距離によって決定される最短経路共分散行列に着目した。
このような行列はトエプリッツと循環共分散行列を一般化し、信号処理応用において広く適用され、2つの測定値の共分散は時間または空間におけるそれらの間の(最短経路)距離に依存する。
ベクトルサンプルの複雑さを最小化することに注力する:$\mathcal{D}$から引き出されたサンプルの数とエントリサンプルの複雑さ:各サンプルで読み込まれたエントリの数。
入力サンプルの複雑さは、信号処理応用における測定機器のコストに相当する。
スペクトルノルム誤差$\epsilon \left\|\mathbf{\sigma}\right\|_2$ just $o(\sqrt{d})$ entry sample complexity and $\tilde o(r^2/\epsilon^2)$ vector sample complexity ここで$d$は下層のグラフの直径、$r \le d$は$\mathbf{\sigma}$のランクである。
提案手法は,Toeplitz共分散推定のためのスパース定規をグラフ設定に拡張することに基づく。
特別な場合、$\mathbf{\Sigma}$ がローランクのToeplitz行列であるとき、我々の結果は最先端の証明と非常に単純な証明で一致する。
また、情報理論上の下限を上限値の$d$まで満たし、このギャップを閉じる方向についても議論します。
関連論文リスト
- Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-01T17:59:53Z) - Testing Closeness of Multivariate Distributions via Ramsey Theory [40.926523210945064]
多次元分布に対する近接性(あるいは等価性)検定の統計的課題について検討する。
具体的には、$mathbf p, mathbf q$ on $mathbb Rd$ に対して、$mathbf p=mathbf q$ と $|mathbf p-mathbf q|_A_k > epsilon$ の2つの未知の分布へのサンプルアクセスが与えられると、$mathbf p=mathbf q$ と $|mathbf p-mathbf q|_A_k > epsilon$ を区別する。
本研究の主な成果は,任意の固定次元におけるサブラーニングサンプルの複雑性を考慮に入れた,この問題に対する最初のクローズネステスタである。
論文 参考訳（メタデータ） (2023-11-22T04:34:09Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Perfect Sampling from Pairwise Comparisons [26.396901523831534]
分散分布$mathcalD$の与えられたアクセスから最適なサンプルを効率よく取得する方法を,サポート対象の要素のペア比較に限定して検討する。
固定分布が$mathcalD$と一致するマルコフ連鎖を設計し、過去からの結合技術を用いて正確なサンプルを得るアルゴリズムを提供する。
論文 参考訳（メタデータ） (2022-11-23T11:20:30Z) - Sample Complexity Bounds for Learning High-dimensional Simplices in
Noisy Regimes [5.526935605535376]
ノイズの多いサンプルから単純さを学習するために、サンプルの複雑さが結びついているのがわかります。
我々は、$mathrmSNRgeOmegaleft(K1/2right)$ である限り、ノイズのないシステムのサンプルの複雑さは、ノイズのないケースのそれと同じ順序であることを示す。
論文 参考訳（メタデータ） (2022-09-09T23:35:25Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - The Sample Complexity of Robust Covariance Testing [56.98280399449707]
i. i. d.
形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。
汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。
サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
論文 参考訳（メタデータ） (2020-12-31T18:24:41Z) - Multi-reference alignment in high dimensions: sample complexity and
phase transition [31.841289319809814]
マルチ参照アライメントは、円形にシフトしたノイズの多いコピーから$mathbbRL$のシグナルを推定する。
単一粒子の低温電子顕微鏡により、高次元状態における問題のサンプルの複雑さを解析した。
我々の分析では、パラメータ $alpha = L/(sigma2log L)$ で制御される相転移現象を発見し、$sigma2$ はノイズの分散である。
論文 参考訳（メタデータ） (2020-07-22T15:04:47Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。