論文の概要: Optimal Spectral Recovery of a Planted Vector in a Subspace
- arxiv url: http://arxiv.org/abs/2105.15081v1
- Date: Mon, 31 May 2021 16:10:49 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-01 16:56:13.208496
- Title: Optimal Spectral Recovery of a Planted Vector in a Subspace
- Title（参考訳）: 部分空間における植込みベクトルの最適スペクトル回復
- Authors: Cheng Mao, Alexander S. Wein
- Abstract要約: 我々は、$ell_4$ノルムが同じ$ell$ノルムを持つガウスベクトルと異なるプラントベクトル$v$の効率的な推定と検出について研究する。
規則$n rho gg sqrtN$ では、大クラスのスペクトル法(そしてより一般的には、入力の低次法)は、植込みベクトルの検出に失敗する。
- 参考スコア（独自算出の注目度）: 80.02218763267992
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recovering a planted vector $v$ in an $n$-dimensional random subspace of
$\mathbb{R}^N$ is a generic task related to many problems in machine learning
and statistics, such as dictionary learning, subspace recovery, and principal
component analysis. In this work, we study computationally efficient estimation
and detection of a planted vector $v$ whose $\ell_4$ norm differs from that of
a Gaussian vector with the same $\ell_2$ norm. For instance, in the special
case of an $N \rho$-sparse vector $v$ with Rademacher nonzero entries, our
results include the following:
(1) We give an improved analysis of (a slight variant of) the spectral method
proposed by Hopkins, Schramm, Shi, and Steurer, showing that it approximately
recovers $v$ with high probability in the regime $n \rho \ll \sqrt{N}$. In
contrast, previous work required either $\rho \ll 1/\sqrt{n}$ or $n \sqrt{\rho}
\lesssim \sqrt{N}$ for polynomial-time recovery. Our result subsumes both of
these conditions (up to logarithmic factors) and also treats the dense case
$\rho = 1$ which was not previously considered.
(2) Akin to $\ell_\infty$ bounds for eigenvector perturbation, we establish
an entrywise error bound for the spectral estimator via a leave-one-out
analysis, from which it follows that thresholding recovers $v$ exactly.
(3) We study the associated detection problem and show that in the regime $n
\rho \gg \sqrt{N}$, any spectral method from a large class (and more generally,
any low-degree polynomial of the input) fails to detect the planted vector.
This establishes optimality of our upper bounds and offers evidence that no
polynomial-time algorithm can succeed when $n \rho \gg \sqrt{N}$.
- Abstract（参考訳）: プランテッドベクトル$v$を$\mathbb{R}^N$の$n$次元ランダム部分空間に復元することは、辞書学習、部分空間回復、主成分分析などの機械学習や統計学における多くの問題に関連する一般的なタスクである。
本研究では,同じ$\ell_2$ノルムを持つガウスベクトルと$\ell_4$ノルムが異なる植込みベクトル$v$の計算効率の高い推定と検出について検討する。
例えば、$N \rho$-sparse vector $v$ with Rademacher nonzero entry の特別な場合、以下の結果が成り立つ: 1) ホプキンス、シュラム、シー、シュテューラーによって提案されたスペクトル法の(わずかに不変な)改善された解析を行い、規則$n \rho \ll \sqrt{N}$ の確率の高い $v$ をほぼ回復することを示す。
対照的に、以前の研究は多項式時間回復のために$\rho \ll 1/\sqrt{n}$か$n \sqrt{\rho} \lesssim \sqrt{N}$のいずれかを必要とした。
この結果は(対数因子による)これらの条件の両方を仮定し、以前考慮されなかった密接なケース $\rho = 1$ を扱います。
(2) 固有ベクトルの摂動に対する$\ell_\infty$ 境界と同様に、スペクトル推定器に対する帰納的誤差は、残量1-アウト解析によって確定し、しきい値が正確に $v$ を回復する。
3) 関連する検出問題について検討し, 大規模クラス(より一般的には, 入力の低次多項式)からのスペクトル法では, 植込みベクトルを検出できないことを示した。
これは上界の最適性を確立し、$n \rho \gg \sqrt{N}$ で多項式時間アルゴリズムが成功できないことを示す。
関連論文リスト
- 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) - A Nearly-Optimal Bound for Fast Regression with $\ell_\infty$ Guarantee [16.409210914237086]
行列 $Ain mathbbRntimes d$ とテンソル $bin mathbbRn$ が与えられたとき、 $ell_infty$ の回帰問題を考える。
このような$ell_infty$レグレッションの保証を得るためには、濃密なスケッチ行列を使わなければならない。
我々はまた、OCE(Oblivious Coordinate-wise Embedding)特性を利用した $ell_infty$ guarantee regression のための新しい分析フレームワークを開発した。
論文 参考訳（メタデータ） (2023-02-01T05:22:40Z) - Overparametrized linear dimensionality reductions: From projection
pursuit to two-layer neural networks [10.368585938419619]
$mathbbRd$に$n$のデータポイントのクラウドが与えられると、$mathbbRd$の$m$次元部分空間へのすべての射影を考える。
この確率分布の集まりは、$n,d$が大きくなるとどのように見えるか?
この極限の低次元射影として生じる $mathbbRm$ の確率分布の集合の α$ を $mathscrF_m で表すと、$mathscrF_ に新たな内界と外界を確立する。
論文 参考訳（メタデータ） (2022-06-14T00:07:33Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳（メタデータ） (2021-11-09T00:20:01Z) - Spectral properties of sample covariance matrices arising from random
matrices with independent non identically distributed columns [50.053491972003656]
関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$.
ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
論文 参考訳（メタデータ） (2021-09-06T14:21:43Z) - Gap-Dependent Unsupervised Exploration for Reinforcement Learning [40.990467706237396]
タスクに依存しない強化学習のための効率的なアルゴリズムを提案する。
このアルゴリズムは1/epsilon cdot (H3SA / rho + H4 S2 A) の$widetildemathcalOのみを探索する。
情報理論上、この境界は$rho Theta (1/(HS))$と$H>1$に対してほぼ厳密であることを示す。
論文 参考訳（メタデータ） (2021-08-11T20:42:46Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳（メタデータ） (2021-05-17T16:40:48Z) - The Average-Case Time Complexity of Certifying the Restricted Isometry
Property [66.65353643599899]
圧縮センシングにおいて、100万倍のN$センシング行列上の制限等尺性(RIP)はスパースベクトルの効率的な再構成を保証する。
Mtimes N$ matrices with i.d.$mathcalN(0,1/M)$ entry。
論文 参考訳（メタデータ） (2020-05-22T16:55:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。