論文の概要: Metric Transforms and Low Rank Matrices via Representation Theory of the
Real Hyperrectangle
- arxiv url: http://arxiv.org/abs/2011.11503v2
- Date: Thu, 5 Aug 2021 03:52:41 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-22 03:31:23.545707
- Title: Metric Transforms and Low Rank Matrices via Representation Theory of the
Real Hyperrectangle
- Title（参考訳）: 実超矩形表現理論による計量変換と低ランク行列
- Authors: Josh Alman, Timothy Chu, Gary Miller, Shyam Narayanan, Mark Sellke,
Zhao Song
- Abstract要約: ハイパー矩形から生じる行列の固有ベクトルと固有値の計算方法を示す。
次に、これらの接続と共に新しい手法を使用して、いくつかの新しい構造結果を示す。
- 参考スコア（独自算出の注目度）: 17.808087068037985
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: In this paper, we develop a new technique which we call representation theory
of the real hyperrectangle, which describes how to compute the eigenvectors and
eigenvalues of certain matrices arising from hyperrectangles. We show that
these matrices arise naturally when analyzing a number of different algorithmic
tasks such as kernel methods, neural network training, natural language
processing, and the design of algorithms using the polynomial method. We then
use our new technique along with these connections to prove several new
structural results in these areas, including:
$\bullet$ A function is a positive definite Manhattan kernel if and only if
it is a completely monotone function. These kernels are widely used across
machine learning; one example is the Laplace kernel which is widely used in
machine learning for chemistry.
$\bullet$ A function transforms Manhattan distances to Manhattan distances if
and only if it is a Bernstein function. This completes the theory of Manhattan
to Manhattan metric transforms initiated by Assouad in 1980.
$\bullet$ A function applied entry-wise to any square matrix of rank $r$
always results in a matrix of rank $< 2^{r-1}$ if and only if it is a
polynomial of sufficiently low degree. This gives a converse to a key lemma
used by the polynomial method in algorithm design.
Our work includes a sophisticated combination of techniques from different
fields, including metric embeddings, the polynomial method, and group
representation theory.
- Abstract（参考訳）: 本稿では、超矩形から生じる行列の固有ベクトルと固有値を計算する方法を記述する、実超矩形表現論と呼ばれる新しい手法を開発した。
これらの行列は、カーネル法、ニューラルネットワークトレーニング、自然言語処理、多項式法を用いたアルゴリズムの設計など、多くの異なるアルゴリズムタスクを解析する際に自然に発生することを示す。
次に、これらの領域におけるいくつかの新しい構造結果を証明するために、これらの接続と共に我々の新しい手法を使用します。 $\bullet$A関数は正定値のマンハッタンカーネルである。
これらのカーネルは機械学習で広く使われており、例えばLaplaceカーネルは化学の機械学習で広く使われている。
$\bullet$ 関数は、それがベルンシュタイン関数である場合に限って、マンハッタン距離をマンハッタン距離に変換する。
これは1980年にアスードによって開始されたマンハッタン-マンハッタン計量変換の理論を完成させる。
$\bullet$ ランクの任意の正方行列にエントリー的に適用される関数 $r$ は常にランクの行列 $<2^{r-1}$ となる。
これは、アルゴリズム設計において多項式法で使われるキー補題に逆を与える。
我々の研究には、計量埋め込み、多項式法、群表現理論など、異なる分野の技法の洗練された組み合わせが含まれている。
関連論文リスト
- Conv-Basis: A New Paradigm for Efficient Attention Inference and Gradient Computation in Transformers [27.54512534985192]
我々は、注目行列の畳み込み様構造を利用して、畳み込み行列を用いた注目の効率的な近似法を開発する。
我々のアルゴリズムは、ほぼ線形時間、すなわち$n1+o(1)$を達成する。
この作業は、アプリケーションがより長いコンテキストに到達できるように、トランスフォーマーにおける注意計算を加速するための新しいパラダイムを提供する。
論文 参考訳（メタデータ） (2024-05-08T17:11:38Z) - Bauer's Spectral Factorization Method for Low Order Multiwavelet Filter
Design [0.6138671548064355]
本稿では,Bauer$'$s法に基づく行列スペクトルの高速分解法を提案する。
バウアー法を非線形行列方程式(NME)に変換する
NMEは2つの異なる数値アルゴリズムによって解決される。
論文 参考訳（メタデータ） (2023-12-09T00:26:52Z) - Exploring and Learning in Sparse Linear MDPs without Computationally
Intractable Oracles [39.10180309328293]
本稿では,特徴選択の観点から線形MDPを再考する。
我々の主な成果は、この問題に対する最初のアルゴリズムである。
コンベックスプログラミングによって効率よく計算できることを示す。
論文 参考訳（メタデータ） (2023-09-18T03:35:48Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Data-Driven Linear Complexity Low-Rank Approximation of General Kernel
Matrices: A Geometric Approach [0.9453554184019107]
K_ij = kappa(x_i,y_j)$ ここで $kappa(x,y)$ はカーネル関数である。
我々は、点の集合 X$ と $Y$ が大きいカーネル行列に対する低ランク近似を求める。
論文 参考訳（メタデータ） (2022-12-24T07:15:00Z) - 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) - Fast Differentiable Matrix Square Root [65.67315418971688]
微分可能な行列平方根を計算するために、より効率的な2つの変種を提案する。
前方伝播には, Matrix Taylor Polynomial (MTP) を用いる方法がある。
もう1つの方法は Matrix Pad'e Approximants (MPA) を使うことである。
論文 参考訳（メタデータ） (2022-01-21T12:18:06Z) - A Practical Method for Constructing Equivariant Multilayer Perceptrons
for Arbitrary Matrix Groups [115.58550697886987]
行列群の同変層を解くための完全一般的なアルゴリズムを提供する。
他作品からのソリューションを特殊ケースとして回収するだけでなく、これまで取り組んだことのない複数のグループと等価な多層パーセプトロンを構築します。
提案手法は, 粒子物理学および力学系への応用により, 非同変基底線より優れる。
論文 参考訳（メタデータ） (2021-04-19T17:21:54Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳（メタデータ） (2020-12-14T18:14:08Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Sketching Transformed Matrices with Applications to Natural Language
Processing [76.6222695417524]
本稿では, 変換行列を用いて, 与えられた小さな行列の積を計算するための空間効率のよいスケッチアルゴリズムを提案する。
提案手法は誤差が小さく,空間と時間の両方で効率がよいことを示す。
論文 参考訳（メタデータ） (2020-02-23T03:07:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。