論文の概要: Spectral Subspace Dictionary Learning
- arxiv url: http://arxiv.org/abs/2210.10855v1
- Date: Wed, 19 Oct 2022 19:35:50 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-21 16:03:05.628988
- Title: Spectral Subspace Dictionary Learning
- Title（参考訳）: スペクトル部分空間辞書学習
- Authors: Alexei Novikov and Stephen White
- Abstract要約: 証明可能な辞書学習は、信号処理とデータ科学の応用において重要性が増している。
我々は,各試料の支持部において,辞書原子が分散する部分空間の復元にスペクトル法を用いる。
適切なランダムモデルの下で、結果として得られるアルゴリズムは、ログ係数まで$M$の間隔線形化に間に合うように辞書を復元する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: \textit{Dictionary learning}, the problem of recovering a sparsely used
matrix $\mathbf{D} \in \mathbb{R}^{M \times K}$ and $N$ independent $K \times
1$ $s$-sparse vectors $\mathbf{X} \in \mathbb{R}^{K \times N}$ from samples of
the form $\mathbf{Y} = \mathbf{D}\mathbf{X}$, is of increasing importance to
applications in signal processing and data science. Early papers on provable
dictionary learning identified that one can detect whether two samples
$\mathbf{y}_i, \mathbf{y}_j$ share a common dictionary element by testing if
their absolute inner product (correlation) exceeds a certain threshold:
$|\left\langle \mathbf{y}_i, \mathbf{y}_j \right\rangle| > \tau$. These
correlation-based methods work well when sparsity is small, but suffer from
declining performance when sparsity grows faster than $\sqrt{M}$; as a result,
such methods were abandoned in the search for dictionary learning algorithms
when sparsity is nearly linear in $M$.
In this paper, we revisit correlation-based dictionary learning. Instead of
seeking to recover individual dictionary atoms, we employ a spectral method to
recover the subspace spanned by the dictionary atoms in the support of each
sample. This approach circumvents the primary challenge encountered by previous
correlation methods, namely that when sharing information between two samples
it is difficult to tell \textit{which} dictionary element the two samples
share. We prove that under a suitable random model the resulting algorithm
recovers dictionaries in polynomial time for sparsity linear in $M$ up to log
factors. Our results improve on the best known methods by achieving a decaying
error bound in dimension $M$; the best previously known results for the
overcomplete ($K > M$) setting achieve polynomial time linear regime only for
constant error bounds. Numerical simulations confirm our results.
- Abstract（参考訳）: \textit{dictionary learning}, スパースに使用される行列 $\mathbf{d} \in \mathbb{r}^{m \times k}$ and $n$ independent $k \times 1$ $s$-sparse vectors $\mathbf{x} \in \mathbb{r}^{k \times n}$ を$\mathbf{y} = \mathbf{d}\mathbf{x}$という形式のサンプルから復元する問題は、信号処理とデータサイエンスにおける応用の重要性を高めている。
証明可能な辞書学習に関する初期の論文では、2つのサンプル $\mathbf{y}_i, \mathbf{y}_j$ が、その絶対内積(相関)が一定のしきい値を超えるかどうかをテストすることによって共通の辞書要素を共有できるかどうかを特定できた: $|\left\langle \mathbf{y}_i, \mathbf{y}_j \right\rangle| > \tau$ 。
これらの相関に基づく手法は、間隔が小さい場合にはうまく機能するが、間隔が$\sqrt{M}$より速く成長すると性能が低下する。
本稿では,相関に基づく辞書学習について再考する。
個々の辞書原子を回収する代わりに、各サンプルの支持の下で辞書原子が分散した部分空間を復元するためにスペクトル法を用いる。
このアプローチは、2つのサンプル間で情報を共有する場合、 \textit{who}ディクショナリ要素が2つのサンプルを共有することは困難である。
適切なランダムモデルの下で、結果として得られるアルゴリズムは多項式時間で辞書を復元し、ログ係数まで$M$で線形化する。
提案手法は, 定数誤差境界に対してのみ多項式時間線形状態が得られるようなオーバーコンプリート(K > M$)設定の既知値として, 次元$M$の減衰誤差を達成し, 最良既知の手法を改良した。
数値シミュレーションは我々の結果を裏付ける。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。