論文の概要: A Combinatorial Approach to Robust PCA
- arxiv url: http://arxiv.org/abs/2311.16416v1
- Date: Tue, 28 Nov 2023 01:49:51 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-29 20:36:49.626760
- Title: A Combinatorial Approach to Robust PCA
- Title（参考訳）: ロバストPCAに対する組合せ的アプローチ
- Authors: Weihao Kong, Mingda Qiao, Rajat Sen
- Abstract要約: 敵の汚職下でのガウスデータの回復問題について検討する。
ガウスノイズは未知の$k$-次元部分空間$U subseteq mathbbRd$と、各データポイントのランダムに選択された座標が敵の制御に該当すると仮定する。
我々の主な結果は、$ks2 = O(d)$のとき、期待して$tilde O(ks/d)$のほぼ最適エラーまですべてのデータポイントを復元する効率的なアルゴリズムです。
- 参考スコア（独自算出の注目度）: 18.740048806623037
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of recovering Gaussian data under adversarial
corruptions when the noises are low-rank and the corruptions are on the
coordinate level. Concretely, we assume that the Gaussian noises lie in an
unknown $k$-dimensional subspace $U \subseteq \mathbb{R}^d$, and $s$ randomly
chosen coordinates of each data point fall into the control of an adversary.
This setting models the scenario of learning from high-dimensional yet
structured data that are transmitted through a highly-noisy channel, so that
the data points are unlikely to be entirely clean.
Our main result is an efficient algorithm that, when $ks^2 = O(d)$, recovers
every single data point up to a nearly-optimal $\ell_1$ error of $\tilde
O(ks/d)$ in expectation. At the core of our proof is a new analysis of the
well-known Basis Pursuit (BP) method for recovering a sparse signal, which is
known to succeed under additional assumptions (e.g., incoherence or the
restricted isometry property) on the underlying subspace $U$. In contrast, we
present a novel approach via studying a natural combinatorial problem and show
that, over the randomness in the support of the sparse signal, a
high-probability error bound is possible even if the subspace $U$ is arbitrary.
- Abstract（参考訳）: 雑音が低く, 汚職が座標レベルにある場合に, 逆汚職の下でガウスデータを復元する問題について検討する。
具体的には、ガウスノイズは未知の$k$-次元部分空間 $u \subseteq \mathbb{r}^d$ にあり、各データポイントのランダムに選択された座標は敵の制御下に入ると仮定する。
この設定は、高度にノイズの多いチャネルを介して送信される高次元で構造化されたデータから学習するシナリオをモデル化する。
我々の主な結果は、$ks^2 = O(d)$ のとき、ほぼ最適の $\ell_1$ エラーの $\tilde O(ks/d)$ まで全てのデータポイントを復元する効率的なアルゴリズムである。
我々の証明の核心は、基礎となる部分空間 u$ 上の追加の仮定(例えば、非一貫性や制限された等長性)で成功するスパース信号の回復のためのよく知られた基底追跡法 (bp) の新しい分析である。
対照的に、自然組合せ問題の研究を通じて新しいアプローチを提案し、スパース信号の支持におけるランダム性よりも、サブスペース$U$が任意であっても高い確率誤差境界が可能であることを示す。
関連論文リスト
- Adaptive $k$-nearest neighbor classifier based on the local estimation of the shape operator [49.87315310656657]
我々は, 局所曲率をサンプルで探索し, 周辺面積を適応的に定義する適応型$k$-nearest(kK$-NN)アルゴリズムを提案する。
多くの実世界のデータセットから、新しい$kK$-NNアルゴリズムは、確立された$k$-NN法と比較してバランスの取れた精度が優れていることが示されている。
論文 参考訳（メタデータ） (2024-09-08T13:08:45Z) - Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing [47.32366699399839]
近似第二エピシロン依存(SOSP)の発見は、よく研究され基礎的な問題である。
本稿では,低次元センサマシン最適化問題に適用する。
論文 参考訳（メタデータ） (2024-03-12T01:27:44Z) - Corruption-Robust Offline Reinforcement Learning with General Function
Approximation [60.91257031278004]
一般関数近似を用いたオフライン強化学習(RL)における劣化問題について検討する。
我々のゴールは、崩壊しないマルコフ決定プロセス(MDP)の最適方針に関して、このような腐敗に対して堅牢で、最適でないギャップを最小限に抑える政策を見つけることである。
論文 参考訳（メタデータ） (2023-10-23T04:07:26Z) - Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCA [17.75853665586128]
本稿では,汚染されたデータからmathbbRn_1times n$の低ランク行列$boldsymbolXstarの列部分空間を推定することに関心がある。
信号-雑音比 (SNR) の広帯域化を図りながら, 最適な統計的精度を得る方法は困難である。
論文 参考訳（メタデータ） (2023-03-10T20:22:18Z) - Subspace Recovery from Heterogeneous Data with Non-isotropic Noise [43.44371292901258]
この問題の基本的な定式化について研究する:主成分分析(PCA)
私たちの目標は、すべてのユーザからのデータポイントを使用して、$mu_i$で共有される線形部分空間を復元することです。
非球面およびユーザ依存雑音下で効率よく計算可能な推定器を設計する。
論文 参考訳（メタデータ） (2022-10-24T18:00:08Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Minimax Rates for Robust Community Detection [19.229475414802213]
逆ノードの破損を伴うブロックモデルにおけるコミュニティ検出の問題点について検討する。
我々の主な結果は、$epsilon$-fraction of corruption and unbounded error $O(epsilon) + e-fracC2 (1 pm o(1))$ where $C = (sqrta - sqrtb)2$ is the signal-to-noise ratio。
アルゴリズムがさらに機能するという意味では、我々のアルゴリズムは2倍に損なわれていることを示す。
論文 参考訳（メタデータ） (2022-07-25T04:45:16Z) - Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。
我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
論文 参考訳（メタデータ） (2022-03-18T18:50:52Z) - Robust Mean Estimation on Highly Incomplete Data with Arbitrary Outliers [7.224832132296238]
我々は,$N$の例として,$d$次元分布の平均を頑健に推定する問題について検討する。
ほぼ線形時間における情報理論的に最適な次元非依存誤差保証を用いて分布の平均を推定するアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-08-18T17:53:34Z) - 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) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。