論文の概要: 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アルゴリズムの期待が示された。

関連論文リスト

• Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems [9.30306458153248]
  我々は、スペクトルテール条件数である$kappa_ell$を、システムを表す行列の最小特異値と$ell$2の比として定義する。 結果のいくつかの意味と$kappa_ell$の使用は、Conjugateメソッドのきめ細かい解析を直接改善することを含んでいる。
  論文  参考訳（メタデータ） (2024-05-09T14:56:49Z)
• 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)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  効率的なプライベート推定アルゴリズムを設計するための一般的なツール。 最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
  論文  参考訳（メタデータ） (2023-01-11T09:12:28Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• Scalable First-Order Bayesian Optimization via Structured Automatic Differentiation [4.061135251278187]
  広い範囲のカーネルが構造化行列を生じさせ、勾配観測のための正確な$mathcalO(n2d)$Matrix-vector multiplyとヘッセン観測のための$mathcalO(n2d2)$を可能にした。 提案手法は,ほぼすべての標準カーネルに適用され,ニューラルネットワーク,放射基底関数ネットワーク,スペクトル混合カーネルなどの複雑なカーネルに自動的に拡張される。
  論文  参考訳（メタデータ） (2022-06-16T17:59:48Z)
• 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)
• Multiplicative updates for symmetric-cone factorizations [0.0]
  コーンの分解を計算するための対称錐乗算更新(SCMU)アルゴリズムを導入,解析する。 SCMUアルゴリズムの軌道に沿って2乗損失目標が非減少していることを示す。
  論文  参考訳（メタデータ） (2021-08-02T09:23:39Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  最小二乗問題に対する反復スケッチの性能について検討する。 本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。 これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
  論文  参考訳（メタデータ） (2020-02-03T16:17:50Z)

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

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