Approximate message passing algorithms for rotationally invariant matrices. (English) Zbl 1486.94026
Summary: Approximate Message Passing (AMP) algorithms have seen widespread use across a variety of applications. However, the precise forms for their Onsager corrections and state evolutions depend on properties of the underlying random matrix ensemble, limiting the extent to which AMP algorithms derived for white noise may be applicable to data matrices that arise in practice.
In this work, we study more general AMP algorithms for random matrices \(\mathbf{W}\) that satisfy orthogonal rotational invariance in law, where \(\mathbf{W}\) may have a spectral distribution that is different from the semicircle and Marcenko-Pastur laws characteristic of white noise. The Onsager corrections and state evolutions in these algorithms are defined by the free cumulants or rectangular free cumulants of the spectral distribution of \(\mathbf{W}\). Their forms were derived previously by Opper, Çakmak and Winther using nonrigorous dynamic functional theory techniques, and we provide rigorous proofs.
Our motivating application is a Bayes-AMP algorithm for Principal Components Analysis, when there is prior structure for the principal components (PCs) and possibly nonwhite noise. For sufficiently large signal strengths and any non-Gaussian prior distributions for the PCs, we show that this algorithm provably achieves higher estimation accuracy than the sample PCs.
In this work, we study more general AMP algorithms for random matrices \(\mathbf{W}\) that satisfy orthogonal rotational invariance in law, where \(\mathbf{W}\) may have a spectral distribution that is different from the semicircle and Marcenko-Pastur laws characteristic of white noise. The Onsager corrections and state evolutions in these algorithms are defined by the free cumulants or rectangular free cumulants of the spectral distribution of \(\mathbf{W}\). Their forms were derived previously by Opper, Çakmak and Winther using nonrigorous dynamic functional theory techniques, and we provide rigorous proofs.
Our motivating application is a Bayes-AMP algorithm for Principal Components Analysis, when there is prior structure for the principal components (PCs) and possibly nonwhite noise. For sufficiently large signal strengths and any non-Gaussian prior distributions for the PCs, we show that this algorithm provably achieves higher estimation accuracy than the sample PCs.
MSC:
| 94A12 | Signal theory (characterization, reconstruction, filtering, etc.) |
| 05C90 | Applications of graph theory |
| 60B20 | Random matrices (probabilistic aspects) |
| 62J07 | Ridge regression; shrinkage estimators (Lasso) |
| 62H12 | Estimation in multivariate analysis |
| 62H25 | Factor analysis and principal components; correspondence analysis |
References:
| [1] | ALAOUI, A. E., MONTANARI, A. and SELLKE, M. (2020). Optimization of mean-field spin glasses. Preprint. Available at arXiv:2001.00904. · Zbl 07467487 |
| [2] | Bayati, M., Lelarge, M. and Montanari, A. (2015). Universality in polytope phase transitions and message passing algorithms. Ann. Appl. Probab. 25 753-822. · Zbl 1322.60207 · doi:10.1214/14-AAP1010 |
| [3] | Bayati, M. and Montanari, A. (2011). The dynamics of message passing on dense graphs, with applications to compressed sensing. IEEE Trans. Inf. Theory 57 764-785. · Zbl 1366.94079 · doi:10.1109/TIT.2010.2094817 |
| [4] | Bayati, M. and Montanari, A. (2012). The LASSO risk for Gaussian matrices. IEEE Trans. Inf. Theory 58 1997-2017. · Zbl 1365.62196 · doi:10.1109/TIT.2011.2174612 |
| [5] | Benaych-Georges, F. (2009). Rectangular random matrices, related convolution. Probab. Theory Related Fields 144 471-515. · Zbl 1171.15022 · doi:10.1007/s00440-008-0152-z |
| [6] | BENAYCH-GEORGES, F. (2009). Rectangular random matrices, entropy, and Fisher’s information. J. Operator Theory 62 371-419. · Zbl 1224.46121 |
| [7] | BENAYCH-GEORGES, F. (2011). Rectangular \(R\)-transform as the limit of rectangular spherical integrals. J. Theoret. Probab. 24 969-987. · Zbl 1237.15031 · doi:10.1007/s10959-011-0362-7 |
| [8] | Benaych-Georges, F. and Nadakuditi, R. R. (2011). The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices. Adv. Math. 227 494-521. · Zbl 1226.15023 · doi:10.1016/j.aim.2011.02.007 |
| [9] | Benaych-Georges, F. and Nadakuditi, R. R. (2012). The singular values and vectors of low rank perturbations of large rectangular random matrices. J. Multivariate Anal. 111 120-135. · Zbl 1252.15039 · doi:10.1016/j.jmva.2012.04.019 |
| [10] | Berthier, R., Montanari, A. and Nguyen, P.-M. (2020). State evolution for approximate message passing with non-separable functions. Inf. Inference 9 33-79. · Zbl 1470.94003 · doi:10.1093/imaiai/iay021 |
| [11] | Bolthausen, E. (2014). An iterative construction of solutions of the TAP equations for the Sherrington-Kirkpatrick model. Comm. Math. Phys. 325 333-366. · Zbl 1288.82038 · doi:10.1007/s00220-013-1862-3 |
| [12] | BORGERDING, M. and SCHNITER, P. (2016). Onsager-corrected deep learning for sparse linear inverse problems. In 2016 IEEE Global Conference on Signal and Information Processing (GlobalSIP) 227-231. IEEE, New York. |
| [13] | BORGERDING, M., SCHNITER, P. and RANGAN, S. (2017). AMP-inspired deep networks for sparse linear inverse problems. IEEE Trans. Signal Process. 65 4293-4308. · Zbl 1414.94083 · doi:10.1109/TSP.2017.2708040 |
| [14] | BU, Z., KLUSOWSKI, J., RUSH, C. and SU, W. (2019). Algorithmic analysis and statistical estimation of SLOPE via approximate message passing. In Advances in Neural Information Processing Systems 9366-9376. · Zbl 1473.62238 |
| [15] | ÇAKMAK, B. and OPPER, M. (2019). Memory-free dynamics for the Thouless-Anderson-Palmer equations of Ising models with arbitrary rotation-invariant ensembles of random coupling matrices. Phys. Rev. E 99 062140. |
| [16] | ÇAKMAK, B. and OPPER, M. (2020). A dynamical mean-field theory for learning in restricted Boltzmann machines. J. Stat. Mech. Theory Exp. 10 103303. · Zbl 1459.82167 · doi:10.1088/1742-5468/abb8c9 |
| [17] | CAKMAK, B., WINTHER, O. and FLEURY, B. H. (2014). S-AMP: Approximate message passing for general matrix ensembles. In 2014 IEEE Information Theory Workshop (ITW 2014) 192-196. IEEE, New York. |
| [18] | CALTAGIRONE, F., ZDEBOROVÁ, L. and KRZAKALA, F. (2014). On convergence of approximate message passing. In 2014 IEEE International Symposium on Information Theory 1812-1816. IEEE, New York. |
| [19] | CHEN, W.-K. and LAM, W.-K. (2021). Universality of approximate message passing algorithms. Electron. J. Probab. 26 Paper No. 36. · Zbl 1483.60007 |
| [20] | Collins, B. (2003). Moments and cumulants of polynomial random variables on unitary groups, the Itzykson-Zuber integral, and free probability. Int. Math. Res. Not. 17 953-982. · Zbl 1049.60091 · doi:10.1155/S107379280320917X |
| [21] | Deshpande, Y., Abbe, E. and Montanari, A. (2017). Asymptotic mutual information for the balanced binary stochastic block model. Inf. Inference 6 125-170. · Zbl 1383.62021 · doi:10.1093/imaiai/iaw017 |
| [22] | DESHPANDE, Y. and MONTANARI, A. (2014). Information-theoretically optimal sparse PCA. In 2014 IEEE International Symposium on Information Theory 2197-2201. IEEE, New York. |
| [23] | DIA, M., MACRIS, N., KRZAKALA, F., LESIEUR, T. and ZDEBOROVÁ, L. (2016). Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula. In Advances in Neural Information Processing Systems 424-432. |
| [24] | Donoho, D. and Montanari, A. (2016). High dimensional robust M-estimation: Asymptotic variance via approximate message passing. Probab. Theory Related Fields 166 935-969. · Zbl 1357.62220 · doi:10.1007/s00440-015-0675-z |
| [25] | DONOHO, D. L., JAVANMARD, A. and MONTANARI, A. (2013). Information-theoretically optimal compressed sensing via spatial coupling and approximate message passing. IEEE Trans. Inf. Theory 59 7434-7464. · Zbl 1364.94120 · doi:10.1109/TIT.2013.2274513 |
| [26] | Donoho, D. L., Maleki, A. and Montanari, A. (2009). Message-passing algorithms for compressed sensing. Proc. Natl. Acad. Sci. USA 106 18914-18919. |
| [27] | DONOHO, D. L., MALEKI, A. and MONTANARI, A. (2010a). Message passing algorithms for compressed sensing: I. Motivation and construction. In 2010 IEEE Information Theory Workshop on Information Theory (ITW 2010, Cairo) 1-5. IEEE. |
| [28] | DONOHO, D. L., MALEKI, A. and MONTANARI, A. (2010b). Message passing algorithms for compressed sensing: II. Analysis and validation. In 2010 IEEE Information Theory Workshop on Information Theory (ITW 2010, Cairo) 1-5. IEEE. |
| [29] | FAN, Z. (2022). Supplement to “Approximate Message Passing algorithms for rotationally invariant matrices.” https://doi.org/10.1214/21-AOS2101SUPP |
| [30] | FENG, O. Y., VENKATARAMANAN, R., RUSH, C. and SAMWORTH, R. J. (2021). A unifying tutorial on Approximate Message Passing. Preprint. Available at arXiv:2105.02180. |
| [31] | FLETCHER, A., SAHRAEE-ARDAKAN, M., RANGAN, S. and SCHNITER, P. (2016). Expectation consistent approximate inference: Generalizations and convergence. In 2016 IEEE International Symposium on Information Theory (ISIT) 190-194. IEEE. |
| [32] | Gamarnik, D. and Jagannath, A. (2021). The overlap gap property and approximate message passing algorithms for \(p\)-spin models. Ann. Probab. 49 180-205. · Zbl 1470.60277 · doi:10.1214/20-AOP1448 |
| [33] | GUIONNET, A. and MAÏDA, M. (2005). A Fourier view on the \(R\)-transform and related asymptotics of spherical integrals. J. Funct. Anal. 222 435-490. · Zbl 1065.60023 · doi:10.1016/j.jfa.2004.09.015 |
| [34] | Javanmard, A. and Montanari, A. (2013). State evolution for general approximate message passing algorithms, with applications to spatial coupling. Inf. Inference 2 115-144. · Zbl 1335.94015 · doi:10.1093/imaiai/iat004 |
| [35] | KABASHIMA, Y. (2003). A CDMA multiuser detection algorithm on the basis of belief propagation. J. Phys. A: Math. Gen. 36 11111. · Zbl 1081.94509 |
| [36] | KABASHIMA, Y. and VEHKAPERÄ, M. (2014). Signal recovery using expectation consistent approximation for linear observations. In 2014 IEEE International Symposium on Information Theory 226-230. IEEE, New York. |
| [37] | MA, J. and PING, L. (2017). Orthogonal AMP. IEEE Access 5 2020-2033. |
| [38] | MAILLARD, A., FOINI, L., LAGE CASTELLANOS, A., KRZAKALA, F., MÉZARD, M. and ZDEBOROVÁ, L. (2019). High-temperature expansions and message passing algorithms. J. Stat. Mech. Theory Exp. 11 113301. · Zbl 1459.82094 · doi:10.1088/1742-5468/ab4bbb |
| [39] | MALEKI, A., ANITORI, L., YANG, Z. and BARANIUK, R. G. (2013). Asymptotic analysis of complex LASSO via complex approximate message passing (CAMP). IEEE Trans. Inf. Theory 59 4290-4308. · Zbl 1364.62188 · doi:10.1109/TIT.2013.2252232 |
| [40] | METZLER, C., MOUSAVI, A. and BARANIUK, R. (2017). Learned D-AMP: Principled neural network based compressive image recovery. In Advances in Neural Information Processing Systems 1772-1783. |
| [41] | MINKA, T. P. (2001). A family of algorithms for approximate Bayesian inference. Ph.D. thesis, Massachusetts Institute of Technology. |
| [42] | MONTANARI, A. (2019). Optimization of the Sherrington-Kirkpatrick Hamiltonian. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) 1417-1433. IEEE, New York. |
| [43] | Montanari, A. and Richard, E. (2016). Non-negative principal component analysis: Message passing algorithms and sharp asymptotics. IEEE Trans. Inf. Theory 62 1458-1484. · Zbl 1359.62224 · doi:10.1109/TIT.2015.2457942 |
| [44] | MONTANARI, A. and VENKATARAMANAN, R. (2021). Estimation of low-rank matrices via approximate message passing. Ann. Statist. 49 321-345. · Zbl 1461.62070 · doi:10.1214/20-AOS1958 |
| [45] | MOUSAVI, A., MALEKI, A. and BARANIUK, R. G. (2018). Consistent parameter estimation for LASSO and approximate message passing. Ann. Statist. 46 119-148. · Zbl 1401.62116 · doi:10.1214/17-AOS1544 |
| [46] | NOVAK, J. (2014). Three lectures on free probability. Random matrix theory, interacting particle systems, and integrable systems 65 13. · Zbl 1318.81009 |
| [47] | OPPER, M., ÇAKMAK, B. and WINTHER, O. (2016). A theory of solving TAP equations for Ising models with general invariant random matrices. J. Phys. A 49 114002. · Zbl 1342.82042 · doi:10.1088/1751-8113/49/11/114002 |
| [48] | OPPER, M. and WINTHER, O. (2001). Adaptive and self-averaging Thouless-Anderson-Palmer mean-field theory for probabilistic modeling. Phys. Rev. E 64 056131. · Zbl 1022.68606 |
| [49] | OPPER, M. and WINTHER, O. (2001). Tractable approximations for probabilistic models: The adaptive Thouless-Anderson-Palmer mean field approach. Phys. Rev. Lett. 86 3695-3699. · doi:10.1103/PhysRevLett.86.3695 |
| [50] | OPPER, M. and WINTHER, O. (2005). Expectation consistent approximate inference. J. Mach. Learn. Res. 6 2177-2204. · Zbl 1222.68278 |
| [51] | PERRY, A., WEIN, A. S., BANDEIRA, A. S. and MOITRA, A. (2018). Message-passing algorithms for synchronization problems over compact groups. Comm. Pure Appl. Math. 71 2275-2322. · Zbl 1439.62143 · doi:10.1002/cpa.21750 |
| [52] | RANGAN, S. (2011). Generalized approximate message passing for estimation with random linear mixing. In 2011 IEEE International Symposium on Information Theory Proceedings 2168-2172. IEEE, New York. |
| [53] | RANGAN, S. and FLETCHER, A. K. (2012). Iterative estimation of constrained rank-one matrices in noise. In 2012 IEEE International Symposium on Information Theory Proceedings 1246-1250. IEEE. |
| [54] | RANGAN, S., SCHNITER, P. and FLETCHER, A. K. (2019). Vector approximate message passing. IEEE Trans. Inf. Theory 65 6664-6684. · Zbl 1432.94036 · doi:10.1109/TIT.2019.2916359 |
| [55] | RANGAN, S., SCHNITER, P., FLETCHER, A. K. and SARKAR, S. (2019). On the convergence of approximate message passing with arbitrary matrices. IEEE Trans. Inf. Theory 65 5339-5351. · Zbl 1432.94037 · doi:10.1109/TIT.2019.2913109 |
| [56] | Schniter, P. and Rangan, S. (2015). Compressive phase retrieval via generalized approximate message passing. IEEE Trans. Signal Process. 63 1043-1055. · Zbl 1394.94506 · doi:10.1109/TSP.2014.2386294 |
| [57] | SCHNITER, P., RANGAN, S. and FLETCHER, A. K. (2016). Vector approximate message passing for the generalized linear model. In 2016 50th Asilomar Conference on Signals, Systems and Computers 1525-1529. IEEE. |
| [58] | SPEICHER, R. (1998). Combinatorial Theory of the Free Product with Amalgamation and Operator-Valued Free Probability Theory 627. AMS, Providence. · Zbl 0935.46056 |
| [59] | SU, W., BOGDAN, M. and CANDÈS, E. (2017). False discoveries occur early on the Lasso path. Ann. Statist. 45 2133-2150. · Zbl 1459.62142 · doi:10.1214/16-AOS1521 |
| [60] | Sur, P. and Candès, E. J. (2019). A modern maximum-likelihood theory for high-dimensional logistic regression. Proc. Natl. Acad. Sci. USA 116 14516-14525. · Zbl 1431.62084 · doi:10.1073/pnas.1810420116 |
| [61] | SUR, P., CHEN, Y. and CANDÈS, E. J. (2019). The likelihood ratio test in high-dimensional logistic regression is asymptotically a rescaled chi-square. Probab. Theory Related Fields 175 487-558. · Zbl 1431.62319 · doi:10.1007/s00440-018-00896-9 |
| [62] | TAKEUCHI, K. (2017). Rigorous dynamics of expectation-propagation-based signal recovery from unitarily invariant measurements. In 2017 IEEE International Symposium on Information Theory (ISIT) 501-505. IEEE, New York. |
| [63] | TAKEUCHI, K. (2019). A unified framework of state evolution for message-passing algorithms. In 2019 IEEE International Symposium on Information Theory (ISIT) 151-155. IEEE, New York. |
| [64] | TAKEUCHI, K. (2020). Convolutional approximate message-passing. IEEE Signal Process. Lett. 27 416-420. |
| [65] | TAKEUCHI, K. (2020). Bayes-optimal convolutional AMP. Preprint. Available at arXiv:2003.12245. · Zbl 1475.94045 |
| [66] | Villani, C. (2009). Optimal Transport: Old and New. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] 338. Springer, Berlin · Zbl 1156.53003 · doi:10.1007/978-3-540-71050-9 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
