Orthogonal Approximate Message Passing with Optimal Spectral Initializations for Rectangular Spiked Matrix Models

• URL: http://arxiv.org/abs/2512.19334v1
• Date: Mon, 22 Dec 2025 12:28:53 GMT
• Title: Orthogonal Approximate Message Passing with Optimal Spectral Initializations for Rectangular Spiked Matrix Models
• Authors: Haohua Chen, Songbin Liu, Junjie Ma,
• Abstract summary: We propose an approximate message passing (OAMP) algorithm for signal estimation in the rectangular spiked matrix model.<n>We establish a rigorous state evolution that precisely characterizes the algorithm's high-dimensional dynamics.<n>We conjecture that it is statistically optimal within a broad class of iterative estimation methods.
• Score: 4.705915211123485
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose an orthogonal approximate message passing (OAMP) algorithm for signal estimation in the rectangular spiked matrix model with general rotationally invariant (RI) noise. We establish a rigorous state evolution that precisely characterizes the algorithm's high-dimensional dynamics and enables the construction of iteration-wise optimal denoisers. Within this framework, we accommodate spectral initializations under minimal assumptions on the empirical noise spectrum. In the rectangular setting, where a single rank-one component typically generates multiple informative outliers, we further propose a procedure for combining these outliers under mild non-Gaussian signal assumptions. For general RI noise models, the predicted performance of the proposed optimal OAMP algorithm agrees with replica-symmetric predictions for the associated Bayes-optimal estimator, and we conjecture that it is statistically optimal within a broad class of iterative estimation methods.

Related papers

• Optimal Estimation in Orthogonally Invariant Generalized Linear Models: Spectral Initialization and Approximate Message Passing [36.35215381372567]
  This paper proposes optimal spectral estimators and an approximate message passing (AMP) algorithm.<n>Building on the paradigm of spectrally-d iterative optimization, this paper proposes optimal spectral estimators and an approximate message passing (AMP) algorithm.
  arXiv  Detail & Related papers  (2026-02-09T22:08:09Z)
• Orthogonal Approximate Message Passing Algorithms for Rectangular Spiked Matrix Models with Rotationally Invariant Noise [4.705915211123485]
  We propose an approximate message passing (OAMP) algorithm for signal estimation in the rectangular spiked matrix model.<n>We establish a rigorous state evolution that exactly characterizes the high-dimensional dynamics of the algorithm.<n>Building on this framework, we derive an optimal variant of OAMP that minimizes the predicted mean-squared error at each iteration.
  arXiv  Detail & Related papers  (2026-02-03T09:06:20Z)
• Optimality of Approximate Message Passing Algorithms for Spiked Matrix Models with Rotationally Invariant Noise [8.032235780123429]
  We study the problem of estimating a rank one signal matrix from an observed matrix generated by corrupting the signal with additive rotationally invariant noise.<n>We develop a new class of approximate message-passing algorithms for this problem and provide a simple and concise characterization of their dynamics in the high-dimensional limit.
  arXiv  Detail & Related papers  (2024-05-28T11:42:51Z)
• Differentially Private Optimization with Sparse Gradients [60.853074897282625]
  We study differentially private (DP) optimization problems under sparsity of individual gradients. Building on this, we obtain pure- and approximate-DP algorithms with almost optimal rates for convex optimization with sparse gradients.
  arXiv  Detail & Related papers  (2024-04-16T20:01:10Z)
• A Random Matrix Approach to Low-Multilinear-Rank Tensor Approximation [24.558241146742205]
  We characterize the large-dimensional spectral behavior of the unfoldings of the data tensor and exhibit relevant signal-to-noise ratios governing the detectability of the principal directions of the signal.<n>Results allow to accurately predict the reconstruction performance of truncated multilinear SVD (MLSVD) in the non-trivial regime.
  arXiv  Detail & Related papers  (2024-02-05T16:38:30Z)
• Approximate Message Passing for the Matrix Tensor Product Model [8.206394018475708]
  We propose and analyze an approximate message passing (AMP) algorithm for the matrix tensor product model. Building upon an convergence theorem for non-separable functions, we prove a state evolution for non-separable functions. We leverage this state evolution result to provide necessary and sufficient conditions for recovery of the signal of interest.
  arXiv  Detail & Related papers  (2023-06-27T16:03:56Z)
• Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
  We derive an approximate message-passing algorithm (AMP) for the inhomogeneous problem. We identify in particular the existence of a statistical-to-computational gap where known algorithms require a signal-to-noise ratio bigger than the information-theoretic threshold to perform better than random.
  arXiv  Detail & Related papers  (2023-02-13T19:57:17Z)
• Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability [107.65337427333064]
  optimization of the Area Under the Precision-Recall Curve (AUPRC) is a crucial problem for machine learning. In this work, we present the first trial in the single-dependent generalization of AUPRC optimization. Experiments on three image retrieval datasets on speak to the effectiveness and soundness of our framework.
  arXiv  Detail & Related papers  (2022-09-27T09:06:37Z)
• Sparse high-dimensional linear regression with a partitioned empirical Bayes ECM algorithm [62.997667081978825]
  We propose a computationally efficient and powerful Bayesian approach for sparse high-dimensional linear regression. Minimal prior assumptions on the parameters are used through the use of plug-in empirical Bayes estimates. The proposed approach is implemented in the R package probe.
  arXiv  Detail & Related papers  (2022-09-16T19:15:50Z)
• Optimizing Information-theoretical Generalization Bounds via Anisotropic Noise in SGLD [73.55632827932101]
  We optimize the information-theoretical generalization bound by manipulating the noise structure in SGLD. We prove that with constraint to guarantee low empirical risk, the optimal noise covariance is the square root of the expected gradient covariance.
  arXiv  Detail & Related papers  (2021-10-26T15:02:27Z)
• Plug-And-Play Learned Gaussian-mixture Approximate Message Passing [71.74028918819046]
  We propose a plug-and-play compressed sensing (CS) recovery algorithm suitable for any i.i.d. source prior. Our algorithm builds upon Borgerding's learned AMP (LAMP), yet significantly improves it by adopting a universal denoising function within the algorithm. Numerical evaluation shows that the L-GM-AMP algorithm achieves state-of-the-art performance without any knowledge of the source prior.
  arXiv  Detail & Related papers  (2020-11-18T16:40:45Z)

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.