近線形計算複雑性における高密度カーネル行列の圧縮,反転および近似PCA【JST・京大機械翻訳】

Schaefer Florian; Sullivan T. J.; Owhadi Houman

プレプリント

J-GLOBAL ID：202202210226049869 整理番号：22P0041008

近線形計算複雑性における高密度カーネル行列の圧縮,反転および近似PCA【JST・京大機械翻訳】

Compression, inversion, and approximate PCA of dense kernel matrices at near-linear computational complexity

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (3件)： , ,
資料名：
発行年： 2017年06月07日プレプリントサーバーでの情報更新日： 2020年10月30日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

位置{x_i}_1≦i≦N≡R ̄dにおける共分散関数Gの点評価から得た高密度カーネル行列ΔR ̄N×Nは,統計,機械学習,および数値解析において生じる。楕円境界値問題と均一分布サンプリング点のGreen関数である共分散関数に対して,スパース行列Θ_ij1_(i,j)∈Sのゼロフィルイン不完全Cholesky因数分解がΘのε近似であるように,#S=O(Nlog(N)log ̄d(N/ε))を用いて部分集合S≡1,s,N} ̄2を同定する方法を示した。この因数分解を,空間およびO(Nlog ̄2(N)log ̄2d(N/ε))における複雑性O(Nlog(N)log ̄d(N/ε))において,時間的に得ることができ,一般的楕円演算子に対する最先端状態を改善した。さらに,dが周囲空間よりもデータセットの固有次元であるとの数値的証拠を提示した。アルゴリズムはx_iの空間構成を知る必要があり,Gの解析的表現を必要としない。さらに,この因数分解により,オペレータノルムにおける収束の最適速度を有する近似的スパースPCAを直接提供した。したがって,サブサンプリングと不完全なCholesky因数分解を用いて,著者らは,ほぼ線形の複雑度で,大きなクラスの共分散行列の圧縮,反転,および近似PCAを得た。Cholesky因数分解の次数を反転することにより,空間およびO(Nlog ̄2d(N/ε))における計算量O(Nlog ̄d(N/ε))を有する楕円PDEに対するソルバーも求め,一般的楕円演算子に対する最先端状態を改善した。【JST・京大機械翻訳】

, , , , , , , , , ,
, , , , 【Automatic Indexing@JST】

数値計算 , 計算理論

, , , , , ,

前のページに戻る