Fugu-MT 論文翻訳(概要): Compressive Recovery of Sparse Precision Matrices

論文の概要: Compressive Recovery of Sparse Precision Matrices

arxiv url: http://arxiv.org/abs/2311.04673v3
Date: Tue, 12 Dec 2023 09:52:54 GMT
ステータス: 処理完了
システム内更新日: 2023-12-13 12:50:54.725273
Title: Compressive Recovery of Sparse Precision Matrices
Title（参考訳）: スパース精密行列の圧縮回復
Authors: Titouan Vayer, Etienne Lasalle, R\'emi Gribonval and Paulo Gon\c{c}alves
Abstract要約: 我々は,$d$変数の統計的関係を,mathbbRn times d$の$n$サンプル$Xのデータセットからモデル化するグラフの学習問題を考察する。サイズ $m=Omegaleft((d+2k)log(d)right)$ ここで、$k$は基礎となるグラフのエッジの最大数である。本稿では, グラフィカルラッソに基づく反復アルゴリズムを用いて, 具体的デノイザとみなす実用的リカバリを実現する可能性について検討する。
参考スコア（独自算出の注目度）: 5.557600489035657
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We consider the problem of learning a graph modeling the statistical relations of the $d$ variables from a dataset with $n$ samples $X \in \mathbb{R}^{n \times d}$. Standard approaches amount to searching for a precision matrix $\Theta$ representative of a Gaussian graphical model that adequately explains the data. However, most maximum likelihood-based estimators usually require storing the $d^{2}$ values of the empirical covariance matrix, which can become prohibitive in a high-dimensional setting. In this work, we adopt a compressive viewpoint and aim to estimate a sparse $\Theta$ from a \emph{sketch} of the data, i.e. a low-dimensional vector of size $m \ll d^{2}$ carefully designed from $X$ using non-linear random features. Under certain assumptions on the spectrum of $\Theta$ (or its condition number), we show that it is possible to estimate it from a sketch of size $m=\Omega\left((d+2k)\log(d)\right)$ where $k$ is the maximal number of edges of the underlying graph. These information-theoretic guarantees are inspired by compressed sensing theory and involve restricted isometry properties and instance optimal decoders. We investigate the possibility of achieving practical recovery with an iterative algorithm based on the graphical lasso, viewed as a specific denoiser. We compare our approach and graphical lasso on synthetic datasets, demonstrating its favorable performance even when the dataset is compressed.
Abstract（参考訳）: 我々は、$d$変数の統計的関係をデータセットからモデル化するグラフを、$n$サンプル$X \in \mathbb{R}^{n \times d}$で学習する問題を考える。標準的アプローチは、データを適切に説明するガウスのグラフィカルモデルの精度行列 $\theta$ を探索する量である。しかし、ほとんどの最大確率に基づく推定値は、通常経験的共分散行列の$d^{2}$の値を保存する必要がある。本研究では, 圧縮的視点を採用し, 非線形乱数特徴を用いた$X$ から低次元ベクトル $m \ll d^{2}$ を慎重に設計し, データの \emph{sketch} からスパース $\Theta$ を推定することを目的とする。例えば、$\Theta$(あるいは条件番号)のスペクトル上の特定の仮定の下で、$m=\Omega\left((d+2k)\log(d)\right)$のスケッチから、$k$が基礎となるグラフのエッジの最大数であることを示す。これらの情報理論的な保証は圧縮センシング理論に触発され、制限された等長性とインスタンス最適デコーダを含む。本研究では,グラフィカルラッソに基づく反復アルゴリズムを具体的デノイザーとして,実用的リカバリを実現する可能性について検討する。合成データセットに対する我々のアプローチとグラフィカルラッソを比較し、データセットを圧縮しても良好な性能を示す。

関連論文リスト

Conditional regression for the Nonlinear Single-Variable Model [4.565636963872865]
F(X):=f(Pi_gamma):mathbbRdto[0,rmlen_gamma]$ ここで$Pi_gamma: [0,rmlen_gamma]tomathbbRd$と$f:[0,rmlen_gamma]tomathbbR1$を考える。条件回帰に基づく非パラメトリック推定器を提案し、$one$-dimensionalOptimical min-maxレートを実現できることを示す。
論文参考訳（メタデータ） (2024-11-14T18:53:51Z)
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)
Turnstile $\ell_p$ leverage score sampling with applications [56.403488578703865]
我々は,行列$AinmathbbRntimes d$の行をサンプリングする新しいアルゴリズムを開発した。我々のアルゴリズムはサンプル行インデックスのセットを返すだけでなく、わずかに乱れた行を $tildea_i approx a_i$ で返却し、サンプリング確率を $varepsilon$ の相対誤差に近似する。ロジスティック回帰のために、我々のフレームワークは$を達成した最初のアルゴリズムを得る。
論文参考訳（メタデータ） (2024-06-01T07:33:41Z)
Sparse Gaussian Graphical Models with Discrete Optimization: Computational and Statistical Perspectives [8.403841349300103]
本研究では,無向ガウス図形モデルに基づくスパースグラフの学習問題を考察する。擬似微分関数の $ell_0$-penalized バージョンに基づく新しい推定器 GraphL0BnB を提案する。実/合成データセットに関する数値実験により,本手法がほぼ最適に,p = 104$の問題を解けることが示唆された。
論文参考訳（メタデータ） (2023-07-18T15:49:02Z)
Effective Minkowski Dimension of Deep Nonparametric Regression: Function Approximation and Statistical Theories [70.90012822736988]
ディープ非パラメトリック回帰に関する既存の理論は、入力データが低次元多様体上にある場合、ディープニューラルネットワークは本質的なデータ構造に適応できることを示した。本稿では,$mathcalS$で表される$mathbbRd$のサブセットに入力データが集中するという緩和された仮定を導入する。
論文参考訳（メタデータ） (2023-06-26T17:13:31Z)
Structure Learning in Graphical Models from Indirect Observations [17.521712510832558]
本稿では、パラメータ法と非パラメトリック法の両方を用いて、Rp$における$p$次元ランダムベクトル$Xのグラフィカル構造を学習する。温和な条件下では、グラフ構造推定器が正しい構造を得ることができることを示す。
論文参考訳（メタデータ） (2022-05-06T19:24:44Z)
Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
論文参考訳（メタデータ） (2022-03-18T18:50:52Z)
Random Graph Matching in Geometric Models: the Case of Complete Graphs [21.689343447798677]
本稿では, エッジ重み付き2つの完全グラフが潜在測地によって相関する問題について検討する。近似最大極大推定器を導出し、高い確率で$pi*$の完全回復を確実に達成する。副次的な発見として、[Ume88] の有望なスペクトルアルゴリズムが幾何モデルにおける最大可能性のさらなる近似として現れることを示す。
論文参考訳（メタデータ） (2022-02-22T04:14:45Z)
Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。 3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文参考訳（メタデータ） (2021-10-05T09:33:49Z)
Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative GLASSO and Projection [58.5350491065936]
グラフ Laplacian 行列 $L$ 上の構造的仮定を考える。最初の$K$ eigenvectors of $L$は、例えばドメイン固有の基準に基づいて事前選択される。本稿では,H_u+$$$$barC$で最も適切なグラフラプラシアン行列$L*を計算するために,効率的なハイブリッドグラフラッソ/投影アルゴリズムを設計する。
論文参考訳（メタデータ） (2020-10-25T18:12:50Z)

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

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