論文の概要: Dictionary Learning for the Almost-Linear Sparsity Regime
- arxiv url: http://arxiv.org/abs/2210.10855v2
- Date: Mon, 27 Mar 2023 21:28:27 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-29 19:38:21.205355
- Title: Dictionary Learning for the Almost-Linear Sparsity Regime
- Title（参考訳）: ほぼ線形スパルシティーレジームのための辞書学習
- Authors: Alexei Novikov and Stephen White
- Abstract要約: 辞書学習は、信号処理やデータ科学における応用においてますます重要になっている。
SPORADIC (SPectral ORAcle DICtionary Learning) は、重み付けされた共分散行列の族に対する効率的なスペクトル法である。
高次元において、SPORADICはよく知られた制限等尺性(RIP)を満たす過剰完備(K > M$)辞書を復元できることを示す。
これらの精度保証は、未知のスパースベクトル $mathbfx_i$ の支持と符号が、高い確率で正確に復元され、任意に閉じることができるような「オラクル特性」を持つ。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Dictionary learning, the problem of recovering a sparsely used matrix
$\mathbf{D} \in \mathbb{R}^{M \times K}$ and $N$ $s$-sparse vectors
$\mathbf{x}_i \in \mathbb{R}^{K}$ from samples of the form $\mathbf{y}_i =
\mathbf{D}\mathbf{x}_i$, is of increasing importance to applications in signal
processing and data science. When the dictionary is known, recovery of
$\mathbf{x}_i$ is possible even for sparsity linear in dimension $M$, yet to
date, the only algorithms which provably succeed in the linear sparsity regime
are Riemannian trust-region methods, which are limited to orthogonal
dictionaries, and methods based on the sum-of-squares hierarchy, which requires
super-polynomial time in order to obtain an error which decays in $M$. In this
work, we introduce SPORADIC (SPectral ORAcle DICtionary Learning), an efficient
spectral method on family of reweighted covariance matrices. We prove that in
high enough dimensions, SPORADIC can recover overcomplete ($K > M$)
dictionaries satisfying the well-known restricted isometry property (RIP) even
when sparsity is linear in dimension up to logarithmic factors. Moreover, these
accuracy guarantees have an ``oracle property" that the support and signs of
the unknown sparse vectors $\mathbf{x}_i$ can be recovered exactly with high
probability, allowing for arbitrarily close estimation of $\mathbf{D}$ with
enough samples in polynomial time. To the author's knowledge, SPORADIC is the
first polynomial-time algorithm which provably enjoys such convergence
guarantees for overcomplete RIP matrices in the near-linear sparsity regime.
- Abstract（参考訳）: 辞書学習 (Dictionary learning) は、スパース的に使われる行列 $\mathbf{D} \in \mathbb{R}^{M \times K}$ と $N$ $s$-sparse vectors $\mathbf{x}_i \in \mathbb{R}^{K}$ を、形式 $\mathbf{y}_i = \mathbf{D}\mathbf{x}_i$ のサンプルから回収する問題である。
辞書が知られているとき、$\mathbf{x}_i$のリカバリは次元が$M$であっても可能であるが、現在まで線形疎性体系において確実に成功するアルゴリズムは、直交辞書に限られるリーマン的信頼領域法と、$M$で崩壊する誤差を得るために超多項式時間を必要とする総和-二乗階層に基づく方法のみである。
本研究では,再重み付け共分散行列の族に対する効率的なスペクトル法であるsporadic (spectral oracle dictionary learning)を提案する。
高次元において、SPORADICは、空間が対数因子まで線形である場合でも、よく知られた制限等尺性(RIP)を満たす過剰完備(K > M$)辞書を復元できることを示す。
さらに、これらの精度保証は、未知のスパースベクトル $\mathbf{x}_i$ の支持と符号を高い確率で正確に復元することができ、多項式時間で十分なサンプルで$\mathbf{D}$を任意に近似することができる ``oracle property' を持つ。
著者の知る限り、SPORADIC は多項式時間アルゴリズムとしては初めてのもので、ニア線形空間の過完全 RIP 行列に対する収束保証を確実に享受する。
関連論文リスト
- Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - On the well-spread property and its relation to linear regression [4.619541348328937]
頑健な線形回帰モデルにおけるパラメータベクトルの一貫した回復は情報理論上不可能であることを示す。
与えられた$n$-by-d$行列が、周囲の次元で観測回数が二次的である場合、適切に証明できることが示される。
論文 参考訳（メタデータ） (2022-06-16T11:17:44Z) - Semi-Random Sparse Recovery in Nearly-Linear Time [37.61139884826181]
生成モデル変更に対する高速スパース回収アルゴリズムの脆性について検討する。
提案手法は,半ランダム生成モデルに基づく証明可能な保証付き高速反復法とは異なる。
半ランダムモデルに対して確実に堅牢なスパースリカバリの幾何学に適合した新しい反復法を設計する。
論文 参考訳（メタデータ） (2022-03-08T10:56:46Z) - On Fast Johnson-Lindernstrauss Embeddings of Compact Submanifolds of
$\mathbb{R}^N$ with Boundary [0.4125187280299246]
mathbbRm × N$ のランダム行列 $A がバイリプシッツ函数 $A: MathcalM rightarrow mathbbRm$ とビリプシッツ定数が 1 に近い確率を考える。
我々は、$mathbbRN$ の十分低次元部分多様体を埋め込むための、高度に構造化された分布の新しいクラスを示す。
論文 参考訳（メタデータ） (2021-10-08T15:27:52Z) - Randomized Exploration for Reinforcement Learning with General Value
Function Approximation [122.70803181751135]
本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。
提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。
我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
論文 参考訳（メタデータ） (2021-06-15T02:23:07Z) - Multiscale regression on unknown manifolds [13.752772802705978]
マルチスケールで$mathcalM$に低次元座標を構築し、ローカルフィッティングによるマルチスケール回帰を行います。
本手法の一般化誤差を,事前のリッチクラス上で高い確率で有限サンプル境界を証明することによって解析する。
私たちのアルゴリズムは、サンプルサイズの準線形複雑性を持ち、定数は$D$で、指数は$d$です。
論文 参考訳（メタデータ） (2021-01-13T15:14:31Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳（メタデータ） (2020-12-14T18:14:08Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。
我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-30T19:10:32Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。