論文の概要: Two-way kernel matrix puncturing: towards resource-efficient PCA and spectral clustering

• arxiv url: http://arxiv.org/abs/2102.12293v2
• Date: Thu, 25 Feb 2021 16:16:06 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-26 11:36:50.837438
• Title: Two-way kernel matrix puncturing: towards resource-efficient PCA and spectral clustering
• Title（参考訳）: two-way kernel matrix puncturing: 資源効率の高いpcaとスペクトルクラスタリングに向けて
• Authors: Romain Couillet and Florent Chatelain and Nicolas Le Bihan
• Abstract要約: この方法は、データマトリックス$XinmathbbCptimes n$と対応するカーネル(Gram)マトリックス$K$の両方をBernoulliマスクを介してランダムに「切断」する。 我々は、GAN生成した画像データベースを実証的に確認し、データを劇的にパンクし、巨大な計算とストレージのゲインを提供することができることを確認した。
• 参考スコア（独自算出の注目度）: 43.50783459690612
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The article introduces an elementary cost and storage reduction method for spectral clustering and principal component analysis. The method consists in randomly "puncturing" both the data matrix $X\in\mathbb{C}^{p\times n}$ (or $\mathbb{R}^{p\times n}$) and its corresponding kernel (Gram) matrix $K$ through Bernoulli masks: $S\in\{0,1\}^{p\times n}$ for $X$ and $B\in\{0,1\}^{n\times n}$ for $K$. The resulting "two-way punctured" kernel is thus given by $K=\frac{1}{p}[(X \odot S)^{\sf H} (X \odot S)] \odot B$. We demonstrate that, for $X$ composed of independent columns drawn from a Gaussian mixture model, as $n,p\to\infty$ with $p/n\to c_0\in(0,\infty)$, the spectral behavior of $K$ -- its limiting eigenvalue distribution, as well as its isolated eigenvalues and eigenvectors -- is fully tractable and exhibits a series of counter-intuitive phenomena. We notably prove, and empirically confirm on GAN-generated image databases, that it is possible to drastically puncture the data, thereby providing possibly huge computational and storage gains, for a virtually constant (clustering of PCA) performance. This preliminary study opens as such the path towards rethinking, from a large dimensional standpoint, computational and storage costs in elementary machine learning models.
• Abstract（参考訳）: 本稿では,スペクトルクラスタリングと主成分分析のための基本コスト削減手法を提案する。 この方法は、データ行列$X\in\mathbb{C}^{p\times n}$(または$\mathbb{R}^{p\times n}$)とその対応するカーネル(Gram)行列$K$ through Bernoulli masks:$S\in\{0,1\}^{p\times n}$ for $X$ and $B\in\{0,1\}^{n\times n}$ for $K$からなる。 結果として得られる「二方向切断」カーネルは、$K=\frac{1}{p}[(X \odot S)^{\sf H} (X \odot S)] \odot B$ によって与えられる。 ガウス混合モデルから引き出された独立列からなる$X$に対して、$n,p\to\infty$ with $p/n\to c_0\in(0,\infty)$,$K$のスペクトル挙動(固有値分布の制限)とその孤立固有値と固有ベクトルは、完全に抽出可能であり、反直観現象の連続を示す。 我々は、GAN生成画像データベースにおいて、データを劇的に切り離すことが可能であることを実証し、実証し、実証し、事実上一定の(PCAのクラスタリング)パフォーマンスのために、おそらく巨大な計算およびストレージの利益を提供する。 この予備的な研究は、基本機械学習モデルにおける計算コストとストレージコストの大規模な観点から、再考への道を開く。

関連論文リスト

• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。 我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。 我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
  論文  参考訳（メタデータ） (2022-08-19T18:00:34Z)
• Classical shadows of fermions with particle number symmetry [0.0]
  我々は、$mathcalO(k2eta)$classic complexityを持つ任意の$k$-RDMに対する推定器を提供する。 ハーフフィリングの最悪の場合、我々の手法はサンプルの複雑さに4k$の利点をもたらす。
  論文  参考訳（メタデータ） (2022-08-18T17:11:12Z)
• An Equivalence Principle for the Spectrum of Random Inner-Product Kernel Matrices with Polynomial Scalings [21.727073594338297]
  この研究は、機械学習と統計学の応用によって動機付けられている。 スケーリングシステムにおいて,これらのランダム行列の経験的分布の弱い限界を確立する。 我々の結果は、マルテンコ・パストゥル法と半円法の間の自由加法的畳み込みとして特徴づけられる。
  論文  参考訳（メタデータ） (2022-05-12T18:50:21Z)
• Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regression [3.997680012976965]
  カーネル行列はその次数-$ell$近似によってよく近似される。 行列のスペクトルが分布に収束することを示す。
  論文  参考訳（メタデータ） (2022-04-21T22:20:52Z)
• 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)
• 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)
• Optimal Spectral Recovery of a Planted Vector in a Subspace [80.02218763267992]
  我々は、$ell_4$ノルムが同じ$ell$ノルムを持つガウスベクトルと異なるプラントベクトル$v$の効率的な推定と検出について研究する。 規則$n rho gg sqrtN$ では、大クラスのスペクトル法(そしてより一般的には、入力の低次法)は、植込みベクトルの検出に失敗する。
  論文  参考訳（メタデータ） (2021-05-31T16:10:49Z)
• Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
  エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。 代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
  論文  参考訳（メタデータ） (2020-06-12T10:21:40Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。