論文の概要: Sparse Recovery with Shuffled Labels: Statistical Limits and Practical
Estimators
- arxiv url: http://arxiv.org/abs/2303.11233v1
- Date: Mon, 20 Mar 2023 16:14:58 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-21 14:41:50.370501
- Title: Sparse Recovery with Shuffled Labels: Statistical Limits and Practical
Estimators
- Title（参考訳）: シャッフルラベルによるスパース回復:統計的限界と実用的推定
- Authors: Hang Zhang and Ping Li
- Abstract要約: 置換行列 $bPitrue$ とスパース信号 $bbetatrue$ をシャッフルラベルから再構成する。
提案した推定器は, 穏やかな条件下で, 基本トラス$(bPitrue, supp(bbetatrue))$が得られることを示す。
- 参考スコア（独自算出の注目度）: 23.313461266708877
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper considers the sparse recovery with shuffled labels, i.e., $\by =
\bPitrue \bX \bbetatrue + \bw$, where $\by \in \RR^n$, $\bPi\in \RR^{n\times
n}$, $\bX\in \RR^{n\times p}$, $\bbetatrue\in \RR^p$, $\bw \in \RR^n$ denote
the sensing result, the unknown permutation matrix, the design matrix, the
sparse signal, and the additive noise, respectively. Our goal is to reconstruct
both the permutation matrix $\bPitrue$ and the sparse signal $\bbetatrue$. We
investigate this problem from both the statistical and computational aspects.
From the statistical aspect, we first establish the minimax lower bounds on the
sample number $n$ and the \emph{signal-to-noise ratio} ($\snr$) for the correct
recovery of permutation matrix $\bPitrue$ and the support set
$\supp(\bbetatrue)$, to be more specific, $n \gtrsim k\log p$ and $\log\snr
\gtrsim \log n + \frac{k\log p}{n}$. Then, we confirm the tightness of these
minimax lower bounds by presenting an exhaustive-search based estimator whose
performance matches the lower bounds thereof up to some multiplicative
constants. From the computational aspect, we impose a parsimonious assumption
on the number of permuted rows and propose a computationally-efficient
estimator accordingly. Moreover, we show that our proposed estimator can obtain
the ground-truth $(\bPitrue, \supp(\bbetatrue))$ under mild conditions.
Furthermore, we provide numerical experiments to corroborate our claims.
- Abstract（参考訳）: 本稿では,シャッフルラベルを用いたスパースリカバリ,すなわち $\by = \bPitrue \bX \bbetatrue + \bw$, where $\by \in \RR^n$, $\bPi\in \RR^{n\times n}$, $\bX\in \RR^{n\times p}$, $\bbetatrue\in \RR^p$, $\bw \in \RR^n$は,検出結果,未知の置換行列,設計行列,スパース信号,加算雑音を表す。
我々の目標は、置換行列 $\bpitrue$ とスパース信号 $\bbetatrue$ の両方を再構成することである。
この問題を統計学と計算学の両面から検討する。
統計学的観点から、まず、置換行列 $\bpitrue$ の正しい回復のために、サンプル数 $n$ と \emph{signal-to-noise ratio} (\snr$) のミニマックス下限を定め、さらに具体的には、$n \gtrsim k\log p$ と $\log\snr \gtrsim \log n + \frac{k\log p}{n}$ でサポートセット $\supp(\bbetatrue)$ を設定した。
次に,この最小値下限の厳密性を確認するために,いくつかの乗算定数まで下限と性能が一致する排他的探索に基づく推定器を提示する。
計算の面から,置換行数に控えめな仮定を課し,それに応じて計算効率の高い推定器を提案する。
さらに, 提案した推定器は, 穏やかな条件下で, 基底トラス$(\bPitrue, \supp(\bbetatrue))$が得られることを示す。
さらに,我々の主張を裏付ける数値実験を行う。
関連論文リスト
- 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) - Optimal Estimator for Linear Regression with Shuffled Labels [17.99906229036223]
本稿では,シャッフルラベルを用いた線形回帰の課題について考察する。
mathbb Rntimes m の $mathbf Y、mathbb Rntimes p の mathbf Pi、mathbb Rptimes m$ の mathbf B、mathbb Rntimes m$ の $mathbf Win mathbb Rntimes m$ である。
論文 参考訳（メタデータ） (2023-10-02T16:44:47Z) - A spectral least-squares-type method for heavy-tailed corrupted
regression with unknown covariance \& heterogeneous noise [2.019622939313173]
重み付き最小二乗線形回帰は、少なくとも$epsilon n$ arbitrary outliersの$n$のラベル特徴サンプルを破損させたと仮定して再検討する。
本稿では,$(Sigma,Xi) や $Xi$ の演算ノルムに関する知識を前提に,電力法に基づくほぼ最適に計算可能な推定器を提案する。
論文 参考訳（メタデータ） (2022-09-06T23:37:31Z) - 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) - List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering [42.526664955704746]
そこで我々は,リストデコダブルなスパース平均推定のための,新しい,概念的にシンプルな手法を開発した。
特に、$k$-sparse方向の「確実に有界な」$t-thモーメントを持つ分布の場合、このアルゴリズムは、サンプル複雑性$m = (klog(n))O(t)/alpha(mnt)$の誤差を1/alpha(O (1/t)$で達成する。
Gaussian inliers の特別な場合、我々のアルゴリズムは $Theta (sqrtlog) の最適誤差を保証する。
論文 参考訳（メタデータ） (2022-06-10T17:38:18Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳（メタデータ） (2021-11-09T00:20:01Z) - L1 Regression with Lewis Weights Subsampling [10.796388585158184]
Lewisの重みに従って$X$からサンプリングし、経験的最小化器を出力すると、1-delta$$$mの確率で成功することを示す。
また、対応する$Omega(fracdvarepsilon2 + (d + frac1varepsilon2) logfrac1delta)$も与えます。
論文 参考訳（メタデータ） (2021-05-19T23:15:00Z) - Sparse sketches with small inversion bias [79.77110958547695]
逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。
本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。
スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
論文 参考訳（メタデータ） (2020-11-21T01:33:15Z) - Thresholded Lasso Bandit [70.17389393497125]
Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。
一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
論文 参考訳（メタデータ） (2020-10-22T19:14:37Z) - 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) - On the robustness of the minimum $\ell_2$ interpolator [2.918940961856197]
一般高次元線形回帰フレームワークにおいて最小$ell$-norm$hatbeta$で補間を解析する。
高い確率で、この推定器の予測損失は、上から$(|beta*|2r_cn(Sigma)vee |xi|2)/n$で有界であることを証明する。
論文 参考訳（メタデータ） (2020-03-12T15:12:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。