論文の概要: Universality of first-order methods on random and deterministic matrices

• arxiv url: http://arxiv.org/abs/2604.11729v1
• Date: Mon, 13 Apr 2026 17:03:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-14 20:13:16.702312
• Title: Universality of first-order methods on random and deterministic matrices
• Title（参考訳）: ランダム行列および決定論的行列上の一階法の普遍性
• Authors: Nicola Gorini, Chris Jones, Dmitriy Kunisky, Lucas Pesenti,
• Abstract要約: 一般一階法(英: General First-order method、GFOM)は、行列ベクトル乗算とエントリーワイド非線形性によって状態ベクトルを更新するフレキシブルな反復アルゴリズムのクラスである。 本稿では,入力行列の制限トラフィック分布,行列エントリ中の置換不変量の制限値の収集を通じて,GFOMを解析する。 我々は、いくつかの従来のAMP変種を統一して新しい入力タイプに一般化する新しいAMPを設計する。
• 参考スコア（独自算出の注目度）: 3.358511427906668
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: General first-order methods (GFOM) are a flexible class of iterative algorithms which update a state vector by matrix-vector multiplications and entrywise nonlinearities. A long line of work has sought to understand the large-n dynamics of GFOM, mostly focusing on "very random" input matrices and the approximate message passing (AMP) special case of GFOM whose state is asymptotically Gaussian. Yet, it has long remained unknown how to construct iterative algorithms that retain this Gaussianity for more structured inputs, or why existing AMP algorithms can be as effective for some deterministic matrices as they are for random matrices. We analyze diagrammatic expansions of GFOM via the limiting traffic distribution of the input matrix, the collection of all limiting values of permutation-invariant polynomials in the matrix entries, to obtain the following results: 1. We calculate the traffic distribution for the first non-trivial deterministic matrices, including (minor variants of) the Walsh-Hadamard and discrete sine and cosine transform matrices. This determines the limiting dynamics of GFOM on these inputs, resolving parts of longstanding conjectures of Marinari, Parisi, and Ritort (1994). 2. We design a new AMP iteration which unifies several previous AMP variants and generalizes to new input types, whose limiting dynamics are Gaussian conditional on some latent random variables. The asymptotic dynamics hold for a large and natural class of traffic distributions (encompassing both random and deterministic input matrices) and the algorithm's analysis gives a simple combinatorial interpretation of the Onsager correction, answering questions posed recently by Wang, Zhong, and Fan (2022).
• Abstract（参考訳）: 一般一階法(英: General First-order method、GFOM)は、行列ベクトル乗算とエントリーワイド非線形性によって状態ベクトルを更新するフレキシブルな反復アルゴリズムのクラスである。 GFOMの「非常にランダム」な入力行列と、漸近的にガウス的であるGFOMの近似メッセージパッシング(AMP)特別なケースに主に焦点をあてて、GFOMの大きなnのダイナミクスを理解するための長い研究が進められている。 しかし、より構造化された入力に対してガウス性を保持する反復アルゴリズムを構築する方法や、なぜ既存のAMPアルゴリズムがランダム行列のように決定論的行列に対して有効であるのかは、長い間分かっていない。 我々は,GFOMの図式展開を,入力行列の制限トラフィック分布,行列エントリ内の置換不変多項式の全ての制限値の収集を通じて解析し,次の結果を得る: 1) ウォルシュ・ハダマールおよび離散正弦変換行列を含む最初の非自明な決定論的行列に対するトラフィック分布を計算する。 これはこれらの入力に対する GFOM の極限力学を決定づけ、マリナリ、パリ、リトルトの長年の予想の一部を解いた(1994年)。 2) 従来のAMPの変種を統一して新しい入力型に一般化する新しいAMPイテレーションを設計する。 漸近力学は、大規模で自然なトラフィック分布のクラス(ランダムな入力行列と決定論的入力行列の両方を包含する)を保ち、アルゴリズムの分析は、最近Wang, Zhong, Fan (2022) によって提起された質問に答えるOnsager補正の単純な組合せ解釈を与える。

関連論文リスト

• Fundamental Limits of Matrix Sensing: Exact Asymptotics, Universality, and Applications [34.781211988554425]
  複数のサンプルからベイズ最適学習性能を特徴付ける厳密な方程式を提案する。 我々は統計物理学から非厳密な手法を用いて得られた予測を数学的に確立する。
  論文  参考訳（メタデータ） (2025-03-18T10:36:30Z)
• Universal Sequence Preconditioning [15.021303911702121]
  逐次予測におけるプレコンディショニングの問題について検討する。 対象シーケンスを畳むと、隠れた遷移行列のレンズを適用することが示される。 我々は,この手法が予測アルゴリズムの後悔を軽減することを証明した。
  論文  参考訳（メタデータ） (2025-02-10T15:10:06Z)
• Manifold Gaussian Variational Bayes on the Precision Matrix [70.44024861252554]
  複雑なモデルにおける変分推論(VI)の最適化アルゴリズムを提案する。 本研究では,変分行列上の正定値制約を満たすガウス変分推論の効率的なアルゴリズムを開発した。 MGVBPはブラックボックスの性質のため、複雑なモデルにおけるVIのための準備が整ったソリューションである。
  論文  参考訳（メタデータ） (2022-10-26T10:12:31Z)
• Estimation in Rotationally Invariant Generalized Linear Models via Approximate Message Passing [21.871513580418604]
  本稿では,信号推定のための近接メッセージパッシング(AMP)アルゴリズムの新たなファミリーを提案する。 我々は、状態進化再帰を通じて高次元の限界におけるそれらの性能を厳格に特徴づける。
  論文  参考訳（メタデータ） (2021-12-08T15:20:04Z)
• Robust 1-bit Compressive Sensing with Partial Gaussian Circulant Matrices and Generative Priors [54.936314353063494]
  我々は,ロバストな1ビット圧縮センシングのための相関に基づく最適化アルゴリズムのリカバリ保証を提供する。 我々は,実用的な反復アルゴリズムを用いて,画像データセットの数値実験を行い,結果の相関付けを行う。
  論文  参考訳（メタデータ） (2021-08-08T05:28:06Z)
• Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time [46.31710224483631]
  既存の定数係数近似のスケッチ次元における対数的要素について、Nelson and Nguyen (FOCS, 2013) の主な開問題を回避する方法を示す。 私たちが使用している重要なテクニックは、不確実性原理と抽出子に基づくIndykの明示的なマッピングです。 ランク計算と列の線形独立部分集合の探索という基本的な問題に対して、我々のアルゴリズムはCheung, Kwok, Lau (JACM, 2013)を改良し、それぞれ定数係数と$log(n)$-factorの範囲内で最適である。
  論文  参考訳（メタデータ） (2021-07-16T19:34:10Z)
• A generalization of the randomized singular value decomposition [2.538209532048867]
  確率化SVDの理論を多変数ガウスベクトルに一般化し、A$の事前知識をアルゴリズムに組み込むことができる。 重み付きヤコビアルゴリズムに基づくGPの新しい共分散カーネルを構築し、GPを迅速にサンプリングし、ランダムに生成された関数の滑らかさを制御する。
  論文  参考訳（メタデータ） (2021-05-27T10:39:37Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  最小二乗問題に対する反復スケッチの性能について検討する。 本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。 これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
  論文  参考訳（メタデータ） (2020-02-03T16:17:50Z)

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

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