PCA initialization for approximate message passing in rotationally invariant models

Mondelli M, Venkataramanan R. PCA initialization for approximate message passing in rotationally invariant models. 35th Conference on Neural Information Processing Systems. NeurIPS: Neural Information Processing Systems.

Conference Paper | Accepted | English
Author
Mondelli, MarcoISTA ; Venkataramanan, Ramji
Department
Abstract
We study the problem of estimating a rank-$1$ signal in the presence of rotationally invariant noise-a class of perturbations more general than Gaussian noise. Principal Component Analysis (PCA) provides a natural estimator, and sharp results on its performance have been obtained in the high-dimensional regime. Recently, an Approximate Message Passing (AMP) algorithm has been proposed as an alternative estimator with the potential to improve the accuracy of PCA. However, the existing analysis of AMP requires an initialization that is both correlated with the signal and independent of the noise, which is often unrealistic in practice. In this work, we combine the two methods, and propose to initialize AMP with PCA. Our main result is a rigorous asymptotic characterization of the performance of this estimator. Both the AMP algorithm and its analysis differ from those previously derived in the Gaussian setting: at every iteration, our AMP algorithm requires a specific term to account for PCA initialization, while in the Gaussian case, PCA initialization affects only the first iteration of AMP. The proof is based on a two-phase artificial AMP that first approximates the PCA estimator and then mimics the true AMP. Our numerical simulations show an excellent agreement between AMP results and theoretical predictions, and suggest an interesting open direction on achieving Bayes-optimal performance.
Publishing Year
Date Published
2021-12-01
Proceedings Title
35th Conference on Neural Information Processing Systems
Acknowledgement
M. Mondelli would like to thank László Erdős for helpful discussions. M. Mondelli was partially supported by the 2019 Lopez-Loreta Prize. R. Venkataramanan was partially supported by the Alan Turing Institute under the EPSRC grant EP/N510129/1.
Conference
NeurIPS: Neural Information Processing Systems
Conference Location
Virtual
Conference Date
2021-12-06 – 2021-12-14
IST-REx-ID

Cite this

Mondelli M, Venkataramanan R. PCA initialization for approximate message passing in rotationally invariant models. In: 35th Conference on Neural Information Processing Systems. NeurIPS.
Mondelli, M., & Venkataramanan, R. (n.d.). PCA initialization for approximate message passing in rotationally invariant models. In 35th Conference on Neural Information Processing Systems. Virtual: NeurIPS.
Mondelli, Marco, and Ramji Venkataramanan. “PCA Initialization for Approximate Message Passing in Rotationally Invariant Models.” In 35th Conference on Neural Information Processing Systems. NeurIPS, n.d.
M. Mondelli and R. Venkataramanan, “PCA initialization for approximate message passing in rotationally invariant models,” in 35th Conference on Neural Information Processing Systems, Virtual.
Mondelli M, Venkataramanan R. PCA initialization for approximate message passing in rotationally invariant models. 35th Conference on Neural Information Processing Systems. NeurIPS: Neural Information Processing Systems.
Mondelli, Marco, and Ramji Venkataramanan. “PCA Initialization for Approximate Message Passing in Rotationally Invariant Models.” 35th Conference on Neural Information Processing Systems, NeurIPS.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 2106.02356

Search this title in

Google Scholar