We study the problem of estimating a rank-one signal matrix from a noisy observed matrix corrupted by additive rotationally invariant noise. 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. At each iteration, these algorithms leverage prior knowledge about the noise structure by applying a nonlinear matrix denoiser to the eigenvalues of the observed matrix, and utilize prior information regarding the signal structure by applying a nonlinear iterate denoiser to the previous iterates generated by the algorithm. We derive the optimal choices for both the matrix and iterate denoisers and demonstrate that the resulting algorithm achieves the lowest possible asymptotic estimation error among a broad class of iterative algorithms under a fixed iteration budget.

Publication:

ANNALS OF STATISTICS

http://dx.doi.org/10.1214/25-AOS2575

Author:

RISHABH DUDEJA

Department of Statistics, University of Wisconsin, Madison

ardudeja@wisc.edu

SONGBIN LIU

Academy of Mathematics and Systems Science, Chinese Academy of Sciences

bliusongbin@lsec.cc.ac.cn

JUNJIE MA

Academy of Mathematics and Systems Science, Chinese Academy of Sciences

majunjie@lsec.cc.ac.cn