論文の概要: Householder Dice: A Matrix-Free Algorithm for Simulating Dynamics on
Gaussian and Random Orthogonal Ensembles
- arxiv url: http://arxiv.org/abs/2101.07464v2
- Date: Fri, 22 Jan 2021 00:15:14 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-26 07:55:13.687615
- Title: Householder Dice: A Matrix-Free Algorithm for Simulating Dynamics on
Gaussian and Random Orthogonal Ensembles
- Title（参考訳）: Houseer Dice:ガウスおよびランダム直交アンサンブルのダイナミクスをマトリックスフリーでシミュレーションするアルゴリズム
- Authors: Yue M. Lu
- Abstract要約: Householder Dice (HD) は、高密度ランダム行列アンサンブルのダイナミクスを翻訳不変特性でシミュレートするアルゴリズムである。
HDアルゴリズムのメモリとコストはそれぞれ$mathcalO(nT)$と$mathcalO(nT2)$である。
数値結果は、高次元ランダムシステムの研究における新しい計算ツールとしてのHDアルゴリズムの約束を示しています。
- 参考スコア（独自算出の注目度）: 12.005731086591139
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper proposes a new algorithm, named Householder Dice (HD), for
simulating dynamics on dense random matrix ensembles with translation-invariant
properties. Examples include the Gaussian ensemble, the Haar-distributed random
orthogonal ensemble, and their complex-valued counterparts. A "direct" approach
to the simulation, where one first generates a dense $n \times n$ matrix from
the ensemble, requires at least $\mathcal{O}(n^2)$ resource in space and time.
The HD algorithm overcomes this $\mathcal{O}(n^2)$ bottleneck by using the
principle of deferred decisions: rather than fixing the entire random matrix in
advance, it lets the randomness unfold with the dynamics. At the heart of this
matrix-free algorithm is an adaptive and recursive construction of (random)
Householder reflectors. These orthogonal transformations exploit the group
symmetry of the matrix ensembles, while simultaneously maintaining the
statistical correlations induced by the dynamics. The memory and computation
costs of the HD algorithm are $\mathcal{O}(nT)$ and $\mathcal{O}(nT^2)$,
respectively, with $T$ being the number of iterations. When $T \ll n$, which is
nearly always the case in practice, the new algorithm leads to significant
reductions in runtime and memory footprint. Numerical results demonstrate the
promise of the HD algorithm as a new computational tool in the study of
high-dimensional random systems.
- Abstract（参考訳）: 本稿では,変換不変な性質を持つ密度乱数行列アンサンブルのダイナミクスをシミュレートする,houseer dice (hd) という新しいアルゴリズムを提案する。
例えば、ガウスアンサンブル、ハール分布のランダム直交アンサンブル、それらの複素値アンサンブルなどがある。
最初にアンサンブルから密な$n \times n$行列を生成するシミュレーションへの「直接」アプローチは、空間と時間において少なくとも$\mathcal{o}(n^2)$リソースを必要とする。
hdアルゴリズムは、遅延決定の原理を用いて、この$\mathcal{o}(n^2)$のボトルネックを克服する。
このマトリクスフリーアルゴリズムの中心は、(ランダムな)ハウスリフレクターの適応的かつ再帰的な構成である。
これらの直交変換は行列アンサンブルの群対称性を利用し、同時にダイナミクスによって引き起こされる統計相関を維持している。
HDアルゴリズムのメモリと計算コストはそれぞれ$\mathcal{O}(nT)$と$\mathcal{O}(nT^2)$であり、$T$は反復数である。
ほぼ常にそうである$T \ll n$の場合、新しいアルゴリズムは実行時とメモリフットプリントを大幅に削減する。
数値実験により,高次元ランダム系の研究における新しい計算ツールとしてのhdアルゴリズムの期待が示された。
- 全文 参考訳へのリンク
関連論文リスト
- Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Perturbation Analysis of Randomized SVD and its Applications to
High-dimensional Statistics [8.90202564665576]
一般の「信号+雑音」の枠組みによるRSVDの統計特性について検討する。
3つの統計的推論問題に適用した場合、RSVDのほぼ最適性能保証を導出する。
論文 参考訳（メタデータ） (2022-03-19T07:26:45Z) - Kernel Packet: An Exact and Scalable Algorithm for Gaussian Process
Regression with Mat\'ern Correlations [23.560067934682294]
マタン相関を用いた1次元ガウス過程回帰のための正確でスケーラブルなアルゴリズムを開発した。
提案アルゴリズムは,計算時間と予測精度の両方において,既存の代替手法よりもはるかに優れている。
論文 参考訳（メタデータ） (2022-03-07T03:30:35Z) - Sublinear Time Approximation of Text Similarity Matrices [50.73398637380375]
一般的なNystr"om法を不確定な設定に一般化する。
我々のアルゴリズムは任意の類似性行列に適用でき、行列のサイズでサブ線形時間で実行される。
本手法は,CUR分解の単純な変種とともに,様々な類似性行列の近似において非常によく機能することを示す。
論文 参考訳（メタデータ） (2021-12-17T17:04:34Z) - 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) - Multiplicative updates for symmetric-cone factorizations [0.0]
コーンの分解を計算するための対称錐乗算更新(SCMU)アルゴリズムを導入,解析する。
SCMUアルゴリズムの軌道に沿って2乗損失目標が非減少していることを示す。
論文 参考訳（メタデータ） (2021-08-02T09:23:39Z) - Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix
Factorization [49.090785356633695]
非対称な低ランク分解問題: [mathbbRm min d , mathbfU$ および MathV$ について検討する。
論文 参考訳（メタデータ） (2021-06-27T17:25:24Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Randomized Exploration for Reinforcement Learning with General Value
Function Approximation [122.70803181751135]
本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。
提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。
我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
論文 参考訳（メタデータ） (2021-06-15T02:23:07Z) - A generalization of the randomized singular value decomposition [2.538209532048867]
確率化SVDの理論を多変数ガウスベクトルに一般化し、A$の事前知識をアルゴリズムに組み込むことができる。
重み付きヤコビアルゴリズムに基づくGPの新しい共分散カーネルを構築し、GPを迅速にサンプリングし、ランダムに生成された関数の滑らかさを制御する。
論文 参考訳（メタデータ） (2021-05-27T10:39:37Z) - Analysis of One-Hidden-Layer Neural Networks via the Resolvent Method [0.0]
ランダムニューラルネットワークによって動機づけられた確率行列 $M = Y Yast$ と $Y = f(WX)$ を考える。
制限スペクトル分布のStieltjes変換は、いくつかの誤差項まで準自己整合方程式を満たすことを証明している。
さらに、前回の結果を加法バイアス $Y=f(WX+B)$ の場合に拡張し、$B$ は独立なランク1のガウス確率行列である。
論文 参考訳（メタデータ） (2021-05-11T15:17:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。