論文の概要: DiffRed: Dimensionality Reduction guided by stable rank
- arxiv url: http://arxiv.org/abs/2403.05882v1
- Date: Sat, 9 Mar 2024 11:24:34 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-13 11:50:26.474665
- Title: DiffRed: Dimensionality Reduction guided by stable rank
- Title（参考訳）: 微分:安定階数に導かれる次元の縮小
- Authors: Prarabdh Shukla, Gagan Raj Gupta, Kunal Dutta
- Abstract要約: DiffRedは、よく知られた次元減少技術と比較して、M1のほぼゼロであり、ストレスの値がはるかに低いことが示される。
実世界の様々なデータセットに対する実験により、DiffRedは、よく知られた次元削減技術と比較して、M1のほぼ0とより低いストレス値を達成することを示した。
- 参考スコア（独自算出の注目度）: 0.1611401281366893
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: In this work, we propose a novel dimensionality reduction technique, DiffRed,
which first projects the data matrix, A, along first $k_1$ principal components
and the residual matrix $A^{*}$ (left after subtracting its $k_1$-rank
approximation) along $k_2$ Gaussian random vectors. We evaluate M1, the
distortion of mean-squared pair-wise distance, and Stress, the normalized value
of RMS of distortion of the pairwise distances. We rigorously prove that
DiffRed achieves a general upper bound of
$O\left(\sqrt{\frac{1-p}{k_2}}\right)$ on Stress and
$O\left(\frac{(1-p)}{\sqrt{k_2*\rho(A^{*})}}\right)$ on M1 where $p$ is the
fraction of variance explained by the first $k_1$ principal components and
$\rho(A^{*})$ is the stable rank of $A^{*}$. These bounds are tighter than the
currently known results for Random maps. Our extensive experiments on a variety
of real-world datasets demonstrate that DiffRed achieves near zero M1 and much
lower values of Stress as compared to the well-known dimensionality reduction
techniques. In particular, DiffRed can map a 6 million dimensional dataset to
10 dimensions with 54% lower Stress than PCA.
- Abstract（参考訳）: 本研究では,まずデータ行列 a を最初の $k_1$ 主成分と残差行列 $a^{*}$ (k_1$-rank 近似を減算した後) と $k_2$ gaussian のランダムベクトルに沿って投影する,新しい次元性低減手法 diffred を提案する。
本研究では,m1,平均二乗対距離の歪み,応力,対距離の歪みの正規化値を評価する。
DiffRedが$O\left(\sqrt {\frac{1-p}{k_2}}\right)$ on Stress と$O\left(\frac{(1-p)}{\sqrt{k_2*\rho(A^{*})}}\right)$ on M1 ここで$p$は最初の$k_1$主成分によって説明される分散の分数であり、$\rho(A^{*})$は$A^{*}$の安定ランクである。
これらの境界は、ランダムマップの現在知られている結果よりも厳密である。
実世界の様々なデータセットに関する広範な実験により、DiffRedは、よく知られた次元減少技術と比較して、M1のほぼ0とより低い値の応力を達成することを示した。
特にDiffRedは、600万の次元データセットをPCAよりも54%低い応力で10次元にマッピングすることができる。
関連論文リスト
- Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descent [17.73720530889677]
行列センシング問題の収束を早めるためのプレコンディショニング手法が提案されている。
本稿では,2因子パラメータを交互に更新するAPGDアルゴリズムを提案する。
理論的には、任意の乱数から始まる線形速度で APGD が準最適収束を達成することを証明している。
論文 参考訳（メタデータ） (2025-02-01T15:44:39Z) - 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) - Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit
Feedback and Unknown Transition [71.33787410075577]
線形関数近似,未知遷移,および逆損失を用いた強化学習について検討した。
我々は高い確率で$widetildeO(dsqrtHS3K + sqrtHSAK)$ regretを実現する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-03-07T15:03:50Z) - Perturbation Analysis of Randomized SVD and its Applications to
High-dimensional Statistics [8.90202564665576]
一般の「信号+雑音」の枠組みによるRSVDの統計特性について検討する。
3つの統計的推論問題に適用した場合、RSVDのほぼ最適性能保証を導出する。
論文 参考訳（メタデータ） (2022-03-19T07:26:45Z) - Consistent Estimation for PCA and Sparse Regression with Oblivious
Outliers [13.244654316770815]
我々は効率よく計算可能で一貫した推定器を設計する機械を開発する。
スパース回帰では、最適なサンプルサイズ$ngsim (klog d)/alpha2$の整合性を達成する。
PCAの文脈では、パラメータ行列上の広いスパイキネス仮定の下で最適な誤差を保証する。
論文 参考訳（メタデータ） (2021-11-04T15:59:44Z) - 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) - 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) - Compressed sensing of low-rank plus sparse matrices [3.8073142980733]
この写本は、ランクラパース行列と$sスパース行列の和として表現できる$mtimes n$が計算的に抽出可能な方法で復元可能であることを示す同様の保証を開発する。
その結果, 合成問題, 動的地上/静電分離, マルチスペクトルイメージング, ロバストPCAが得られた。
論文 参考訳（メタデータ） (2020-07-18T15:36:11Z) - 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) - Curse of Dimensionality on Randomized Smoothing for Certifiable
Robustness [151.67113334248464]
我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。
我々はCIFARに関する実験結果を示し,その理論を検証した。
論文 参考訳（メタデータ） (2020-02-08T22:02:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。