論文の概要: Noisy $\ell^{0}$-Sparse Subspace Clustering on Dimensionality Reduced
Data
- arxiv url: http://arxiv.org/abs/2206.11079v1
- Date: Wed, 22 Jun 2022 13:45:43 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-23 14:56:51.434921
- Title: Noisy $\ell^{0}$-Sparse Subspace Clustering on Dimensionality Reduced
Data
- Title（参考訳）: 次元縮小データ上のノイズ$\ell^{0}$-スパース部分空間クラスタリング
- Authors: Yingzhen Yang, Ping Li
- Abstract要約: 実データはしばしばノイズに悩まされ、部分空間に近づきやすい。
本稿では,ノイズ$ell0$-SSCの最適化問題に対する最適解が,部分空間検出特性(SDP)を実現することを示す。
ノイズ-DR-$ell0$-SSC はまずランダムな投影により低次元空間にデータを投影し、次に予測されたデータに対してノイズ$ell0$-SSC を実行して効率を向上する。
- 参考スコア（独自算出の注目度）: 22.232788341658924
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Sparse subspace clustering methods with sparsity induced by $\ell^{0}$-norm,
such as $\ell^{0}$-Sparse Subspace Clustering
($\ell^{0}$-SSC)~\citep{YangFJYH16-L0SSC-ijcv}, are demonstrated to be more
effective than its $\ell^{1}$ counterpart such as Sparse Subspace Clustering
(SSC)~\citep{ElhamifarV13}. However, the theoretical analysis of $\ell^{0}$-SSC
is restricted to clean data that lie exactly in subspaces. Real data often
suffer from noise and they may lie close to subspaces. In this paper, we show
that an optimal solution to the optimization problem of noisy $\ell^{0}$-SSC
achieves subspace detection property (SDP), a key element with which data from
different subspaces are separated, under deterministic and semi-random model.
Our results provide theoretical guarantee on the correctness of noisy
$\ell^{0}$-SSC in terms of SDP on noisy data for the first time, which reveals
the advantage of noisy $\ell^{0}$-SSC in terms of much less restrictive
condition on subspace affinity. In order to improve the efficiency of noisy
$\ell^{0}$-SSC, we propose Noisy-DR-$\ell^{0}$-SSC which provably recovers the
subspaces on dimensionality reduced data. Noisy-DR-$\ell^{0}$-SSC first
projects the data onto a lower dimensional space by random projection, then
performs noisy $\ell^{0}$-SSC on the projected data for improved efficiency.
Experimental results demonstrate the effectiveness of Noisy-DR-$\ell^{0}$-SSC.
- Abstract（参考訳）: $\ell^{0}$-norm(例えば $\ell^{0}$-Sparse Subspace Clustering ($\ell^{0}$-SSC)~\citep{YangFJYH16-L0SSC-ijcv})のように、sparse Subspace Clustering (SSC)~\citep{ElhamifarV13}(英語版)のような、sparse subspace Clustering (SSC)$-normによって誘導されるスパース部分空間クラスタリング法は、より効果的であることが示されている。
しかし、$\ell^{0}$-SSC の理論解析は、部分空間に完全に属するクリーンなデータに制限される。
実データはしばしばノイズに悩まされ、部分空間に近接している。
本稿では,決定論的および半ランダムモデルの下で,異なる部分空間からデータを分離する鍵要素である部分空間検出特性(SDP)を,雑音の$\ell^{0}$-SSCの最適化問題に対する最適解として達成することを示す。
本研究は, 雑音データに対するsdpによるノイズの正しさを理論的に保証するものであり, 部分空間の親和性に対する制約条件がはるかに小さいことから, 雑音データに対して, 初めてsscの正しさを理論的に保証するものである。
本研究では, ノイズの多い$\ell^{0}$-SSCの効率を改善するために, 次元減少データ上の部分空間を確実に復元するNoisy-DR-$\ell^{0}$-SSCを提案する。
ノイズ-DR-$\ell^{0}$-SSC は、まずランダム射影により下次元空間にデータを投影し、次に、予測されたデータに対してノイズ$\ell^{0}$-SSC を実行して効率を向上させる。
実験により, ノイズDR-$\ell^{0}$-SSCの有効性が示された。
関連論文リスト
- A Combinatorial Approach to Robust PCA [18.740048806623037]
敵の汚職下でのガウスデータの回復問題について検討する。
ガウスノイズは未知の$k$-次元部分空間$U subseteq mathbbRd$と、各データポイントのランダムに選択された座標が敵の制御に該当すると仮定する。
我々の主な結果は、$ks2 = O(d)$のとき、期待して$tilde O(ks/d)$のほぼ最適エラーまですべてのデータポイントを復元する効率的なアルゴリズムです。
論文 参考訳（メタデータ） (2023-11-28T01:49:51Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCA [17.75853665586128]
本稿では,汚染されたデータからmathbbRn_1times n$の低ランク行列$boldsymbolXstarの列部分空間を推定することに関心がある。
信号-雑音比 (SNR) の広帯域化を図りながら, 最適な統計的精度を得る方法は困難である。
論文 参考訳（メタデータ） (2023-03-10T20:22:18Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - DP-PCA: Statistically Optimal and Differentially Private PCA [44.22319983246645]
DP-PCAは、両方の制限を克服するシングルパスアルゴリズムである。
準ガウスデータに対しては、$n=tilde O(d)$ であっても、ほぼ最適な統計的誤差率を提供する。
論文 参考訳（メタデータ） (2022-05-27T02:02:17Z) - Settling the Sample Complexity of Model-Based Offline Reinforcement
Learning [50.5790774201146]
オフライン強化学習(RL)は、事前収集されたデータを用いて、さらなる探索を行わずに学習する。
事前のアルゴリズムや分析は、最適なサンプルの複雑さに悩まされるか、サンプルの最適性に到達するために高いバーンインコストがかかるかのいずれかである。
モデルベース(あるいは"プラグイン")アプローチは,バーンインコストを伴わずに,最小限のサンプル複雑性を実現することを実証する。
論文 参考訳（メタデータ） (2022-04-11T17:26:19Z) - Locally Differentially Private Reinforcement Learning for Linear Mixture
Markov Decision Processes [78.27542864367821]
強化学習(RL)アルゴリズムは、ユーザのプライベートで機密性の高いデータに依存するパーソナライズされたサービスを提供するために使用することができる。
ユーザのプライバシを保護するために、プライバシ保護RLアルゴリズムが要求されている。
線形混合MDPと呼ばれるマルコフ決定過程(MDP)のクラスを学習するための新しい$(varepsilon, delta)$-LDPアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-10-19T17:44:09Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳（メタデータ） (2021-10-05T09:33:49Z) - Cascading Bandit under Differential Privacy [21.936577816668944]
本研究では,カスケードバンドにおける自己差分プライバシー(DP)と局所差分プライバシー(LDP)について検討する。
DPでは,$epsilon$-indistinguishability を保証し,$mathcalO(fraclog3 Tepsilon)$を任意の小さな$xi$に対して後悔するアルゴリズムを提案する。
Epsilon$,$delta$)-LDPの下では、プライバシの予算とエラー確率のトレードオフを通じて、K2$依存を緩和します。
論文 参考訳（メタデータ） (2021-05-24T07:19:01Z) - Stochastic Linear Bandits with Protected Subspace [51.43660657268171]
線形目的関数を最適化するが、報酬は未知の部分空間にのみ得られる線形帯域問題の変種について検討する。
特に、各ラウンドでは、学習者は、目的または保護されたサブスペースを、アクションの選択とともにクエリするかどうかを選択する必要がある。
提案アルゴリズムはOFULの原理から導かれるもので,保護された空間を推定するためにクエリのいくつかを利用する。
論文 参考訳（メタデータ） (2020-11-02T14:59:39Z) - Fast Dimension Independent Private AdaGrad on Publicly Estimated
Subspaces [24.52697154861819]
AdaGradは、従来のAdaGradに匹敵する後悔と、ノイズによるよく制御された用語を達成していることを示す。
我々は制約付きおよび制約なしの最小化において一般凸関数で操作する。
論文 参考訳（メタデータ） (2020-08-14T20:46:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。