論文の概要: Multiresolution kernel matrix algebra
- arxiv url: http://arxiv.org/abs/2211.11681v2
- Date: Wed, 3 May 2023 21:27:15 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-05 19:19:46.519715
- Title: Multiresolution kernel matrix algebra
- Title（参考訳）: 多分解能カーネル行列代数
- Authors: H. Harbrecht, M. Multerer, O. Schenk, and Ch. Schwab
- Abstract要約: 本研究では, あるS形式において, 最適スパース行列を生成するサンプルレットを用いて, カーネル行列の圧縮を示す。
カーネル行列の逆数(もし存在するなら)は S-形式でも圧縮可能である。
行列代数は擬微分計算によって数学的に正当化される。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a sparse algebra for samplet compressed kernel matrices, to enable
efficient scattered data analysis. We show the compression of kernel matrices
by means of samplets produces optimally sparse matrices in a certain S-format.
It can be performed in cost and memory that scale essentially linearly with the
matrix size $N$, for kernels of finite differentiability, along with addition
and multiplication of S-formatted matrices. We prove and exploit the fact that
the inverse of a kernel matrix (if it exists) is compressible in the S-format
as well. Selected inversion allows to directly compute the entries in the
corresponding sparsity pattern. The S-formatted matrix operations enable the
efficient, approximate computation of more complicated matrix functions such as
${\bm A}^\alpha$ or $\exp({\bm A})$. The matrix algebra is justified
mathematically by pseudo differential calculus. As an application, efficient
Gaussian process learning algorithms for spatial statistics is considered.
Numerical results are presented to illustrate and quantify our findings.
- Abstract（参考訳）: 本稿では,効率的な分散データ解析を実現するために,サンプル圧縮カーネル行列のスパース代数を提案する。
本研究では, あるS形式において, 最適スパース行列を生成するサンプルレットを用いて, カーネル行列の圧縮を示す。
S型行列の追加と乗算とともに、有限微分性のカーネルに対して、基本的に行列サイズ$N$と線形にスケールするコストとメモリで実行できる。
我々は、(もし存在すれば)カーネル行列の逆元がs形式でも圧縮可能であることを証明し、活用する。
選択インバージョンでは、対応するsparsityパターンのエントリを直接計算することができる。
S型行列演算は、${\bm A}^\alpha$や$\exp({\bm A})$のようなより複雑な行列関数の効率的で近似的な計算を可能にする。
行列代数は擬微分計算によって数学的に正当化される。
応用として,空間統計学における効率的なガウス過程学習アルゴリズムを検討する。
数値的な結果を示し,その結果を定量化する。
関連論文リスト
- Optimal Quantization for Matrix Multiplication [35.007966885532724]
我々は、ネスト格子に基づく普遍量化器を、任意の(非ランダムな)行列対に対する近似誤差の明示的な保証付きで、フロベニウスノルム$|A|_F, |B|_F$, $|Atop B|_F$のみの観点から、$A$, $B$とする。
論文 参考訳（メタデータ） (2024-10-17T17:19:48Z) - Block-encoding dense and full-rank kernels using hierarchical matrices:
applications in quantum numerical linear algebra [6.338178373376447]
本稿では,量子コンピュータ上の階層行列構造のブロック符号化方式を提案する。
我々の手法は、次元$N$から$O(kappa operatornamepolylog(fracNvarepsilon))$の量子線型系を解くランタイムを改善することができる。
論文 参考訳（メタデータ） (2022-01-27T05:24:02Z) - Sublinear Time Approximation of Text Similarity Matrices [50.73398637380375]
一般的なNystr"om法を不確定な設定に一般化する。
我々のアルゴリズムは任意の類似性行列に適用でき、行列のサイズでサブ線形時間で実行される。
本手法は,CUR分解の単純な変種とともに,様々な類似性行列の近似において非常によく機能することを示す。
論文 参考訳（メタデータ） (2021-12-17T17:04:34Z) - Learning in High-Dimensional Feature Spaces Using ANOVA-Based Fast
Matrix-Vector Multiplication [0.0]
カーネル行列は一般に密度が高く大規模である。特徴空間の次元によっては、合理的な時間における全てのエントリの計算さえも難しい課題となる。
そこで我々は,ANOVAカーネルを用いて低次元の特徴空間に基づいて複数のカーネルを構築し,行列ベクトル積を実現する高速アルゴリズムを提案する。
特徴グループ化アプローチに基づいて,カーネルリッジ回帰と事前条件付き共役勾配解法を選択する学習手法に,高速な行列ベクトル積を組み込む方法を示す。
論文 参考訳（メタデータ） (2021-11-19T10:29:39Z) - Sparse Factorization of Large Square Matrices [10.94053598642913]
本稿では,大面積の正方行列とスパースフルランク行列の積を近似する。
近似では、我々の手法は$Ntimes N$ full matrix に対して$N(log N)2$ non-zero number しか必要としない。
近似行列がスパースかつハイランクである場合,本手法により近似精度が向上することを示す。
論文 参考訳（メタデータ） (2021-09-16T18:42:21Z) - Robust 1-bit Compressive Sensing with Partial Gaussian Circulant
Matrices and Generative Priors [54.936314353063494]
我々は,ロバストな1ビット圧縮センシングのための相関に基づく最適化アルゴリズムのリカバリ保証を提供する。
我々は,実用的な反復アルゴリズムを用いて,画像データセットの数値実験を行い,結果の相関付けを行う。
論文 参考訳（メタデータ） (2021-08-08T05:28:06Z) - Non-PSD Matrix Sketching with Applications to Regression and
Optimization [56.730993511802865]
非PSDおよび2乗根行列の次元削減法を提案する。
複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
論文 参考訳（メタデータ） (2021-06-16T04:07:48Z) - Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。
我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-30T19:10:32Z) - Sketching Transformed Matrices with Applications to Natural Language
Processing [76.6222695417524]
本稿では, 変換行列を用いて, 与えられた小さな行列の積を計算するための空間効率のよいスケッチアルゴリズムを提案する。
提案手法は誤差が小さく,空間と時間の両方で効率がよいことを示す。
論文 参考訳（メタデータ） (2020-02-23T03:07:31Z) - Optimal Iterative Sketching with the Subsampled Randomized Hadamard
Transform [64.90148466525754]
最小二乗問題に対する反復スケッチの性能について検討する。
本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。
これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
論文 参考訳（メタデータ） (2020-02-03T16:17:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。