Universality of first-order methods on random and deterministic matrices

• URL: http://arxiv.org/abs/2604.11729v1
• Date: Mon, 13 Apr 2026 17:03:53 GMT
• Title: Universality of first-order methods on random and deterministic matrices
• Abstract summary: General first-order methods (GFOM) are a flexible class of iterative algorithms which update a state vector by matrix-vector multiplications and entrywise nonlinearities.<n>We analyze GFOM via the limiting traffic distribution of the input matrix, the collection of all limiting values of permutation-in-variants in the matrix entries.<n>We design a new AMP which unifies several previous AMP variants and generalizes to new input types, whose limiting dynamics are conditional on some latent random variables.
• Score: 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).

Related papers

• Quantum algorithm for differential equations via permutation matrix representation with application to the Burgers equation [0.1274452325287335]
  We develop a quantum algorithm for solving the dynamics of the nonlinear Burgers equation.<n>We show that our algorithm scales with the off-diagonal norm of the Carleman generator instead of the matrix norm.<n>We extend the PMR scheme to general fluid equations that may contain higher-order derivatives or nonlinear terms.
  arXiv  Detail & Related papers  (2026-08-19T23:52:03Z)
• Fundamental Limits of Matrix Sensing: Exact Asymptotics, Universality, and Applications [34.781211988554425]
  We provide rigorous equations characterizing the Bayes-optimal learning performance from a number of samples.<n>We mathematically establish predictions obtained via non-rigorous methods from statistical physics.
  arXiv  Detail & Related papers  (2025-03-18T10:36:30Z)
• Universal Sequence Preconditioning [15.021303911702121]
  We study the problem of preconditioning in sequential prediction.<n>We show that convolving the target sequence corresponds to applying a lens of the hidden transition matrix.<n>We prove that this approach reduces regret for prediction algorithms.
  arXiv  Detail & Related papers  (2025-02-10T15:10:06Z)
• Manifold Gaussian Variational Bayes on the Precision Matrix [70.44024861252554]
  We propose an optimization algorithm for Variational Inference (VI) in complex models. We develop an efficient algorithm for Gaussian Variational Inference whose updates satisfy the positive definite constraint on the variational covariance matrix. Due to its black-box nature, MGVBP stands as a ready-to-use solution for VI in complex models.
  arXiv  Detail & Related papers  (2022-10-26T10:12:31Z)
• Estimation in Rotationally Invariant Generalized Linear Models via Approximate Message Passing [21.871513580418604]
  We propose a novel family of approximate message passing (AMP) algorithms for signal estimation. We rigorously characterize their performance in the high-dimensional limit via a state evolution recursion.
  arXiv  Detail & Related papers  (2021-12-08T15:20:04Z)
• Robust 1-bit Compressive Sensing with Partial Gaussian Circulant Matrices and Generative Priors [54.936314353063494]
  We provide recovery guarantees for a correlation-based optimization algorithm for robust 1-bit compressive sensing. We make use of a practical iterative algorithm, and perform numerical experiments on image datasets to corroborate our results.
  arXiv  Detail & Related papers  (2021-08-08T05:28:06Z)
• Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time [46.31710224483631]
  We show how to bypass the main open question of Nelson and Nguyen (FOCS, 2013) regarding the logarithmic factors in the sketching dimension for existing constant factor approximation oblivious subspace embeddings. A key technique we use is an explicit mapping of Indyk based on uncertainty principles and extractors. For the fundamental problems of rank computation and finding a linearly independent subset of columns, our algorithms improve Cheung, Kwok, and Lau (JACM, 2013) and are optimal to within a constant factor and a $loglog(n)$-factor, respectively.
  arXiv  Detail & Related papers  (2021-07-16T19:34:10Z)
• A generalization of the randomized singular value decomposition [2.538209532048867]
  We generalize the theory of randomized SVD to multivariable Gaussian vectors, allowing one to incorporate prior knowledge of $A$ into the algorithm. We construct a new covariance kernel for GPs, based on weighted Jacobi algorithms, which allows us to rapidly sample the GP and control the smoothness of the randomly generated functions.
  arXiv  Detail & Related papers  (2021-05-27T10:39:37Z)
• Multi-View Spectral Clustering with High-Order Optimal Neighborhood Laplacian Matrix [57.11971786407279]
  Multi-view spectral clustering can effectively reveal the intrinsic cluster structure among data. This paper proposes a multi-view spectral clustering algorithm that learns a high-order optimal neighborhood Laplacian matrix. Our proposed algorithm generates the optimal Laplacian matrix by searching the neighborhood of the linear combination of both the first-order and high-order base.
  arXiv  Detail & Related papers  (2020-08-31T12:28:40Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  This class of algorithms encompasses several randomized methods among the fastest solvers for least-squares problems. We focus on two classical embeddings, namely, Gaussian projections and subsampled Hadamard transforms. Our resulting algorithm yields the best complexity known for solving least-squares problems with no condition number dependence.
  arXiv  Detail & Related papers  (2020-02-21T17:45:32Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  We study the performance of iterative sketching for least-squares problems. We show that the convergence rate for Haar and randomized Hadamard matrices are identical, andally improve upon random projections. These techniques may be applied to other algorithms that employ randomized dimension reduction.
  arXiv  Detail & Related papers  (2020-02-03T16:17:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.