Anderson acceleration of the alternating projections method for computing the nearest correlation matrix. (English) Zbl 1347.65074
Summary: In a wide range of applications it is required to compute the nearest correlation matrix in the Frobenius norm to a given symmetric but indefinite matrix. Of the available methods with guaranteed convergence to the unique solution of this problem the easiest to implement, and perhaps the most widely used, is the alternating projections method. However, the rate of convergence of this method is at best linear, and it can require a large number of iterations to converge to within a given tolerance. We show that Anderson acceleration (cf. [D. G. Anderson, J. Assoc. Comput. Mach. 12, 547–560 (1965; Zbl 0149.11503)]), a technique for accelerating the convergence of fixed-point iterations, can be applied to the alternating projections method and that in practice it brings a significant reduction in both the number of iterations and the computation time. We also show that Anderson acceleration remains effective, and indeed can provide even greater improvements, when it is applied to the variants of the nearest correlation matrix problem in which specified elements are fixed or a lower bound is imposed on the smallest eigenvalue. Alternating projections is a general method for finding a point in the intersection of several sets and ours appears to be the first demonstration that this class of methods can benefit from Anderson acceleration.
MSC:
| 65F30 | Other matrix algorithms (MSC2010) |
| 62H20 | Measures of association (correlation, canonical correlation, etc.) |
Keywords:
nearest correlation matrix; indefinite matrix; positive semidefinite matrix; Anderson acceleration; alternating projections method; Dykstra’s correction; numerical example; convergenceCitations:
Zbl 0149.11503References:
| [1] | Anderson, D.G.: Iterative procedures for nonlinear integral equations. J. Assoc. Comput. Mach. 12(4), 547-560 (1965). doi:10.1145/321296.321305 · Zbl 0149.11503 · doi:10.1145/321296.321305 |
| [2] | Anderson, G., Goldberg, L., Kercheval, A.N., Miller, G., Sorge, K.: On the aggregation of local risk models for global risk management. J. Risk 8(1), 25-40 (2005) |
| [3] | Aragón Artacho, F.J., Borwein, J.M., Tam, M.K.: Douglas-Rachford feasibility methods for matrix completion problems. The ANZIAM Journal 55, 299-326 (2014). doi:10.1017/S1446181114000145 · Zbl 1297.90182 · doi:10.1017/S1446181114000145 |
| [4] | Bhansali, V., Wise, M.B.: Forecasting portfolio risk in normal and stressed markets. J. Risk 4(1), 91-106 (2001) |
| [5] | Birgin, E.G., Raydan, M.: Robust stopping criteria for Dykstra’s algorithm. SIAM J. Sci. Comput. 26(4), 1405-1414 (2005). doi:10.1137/03060062X · Zbl 1149.90382 · doi:10.1137/03060062X |
| [6] | Blondes, M.S., Schuenemeyer, J.H., Olea, R.A., Drew, L.J.: Aggregation of carbon dioxide sequestration storage assessment units. Stoch. Environ. Res. Risk Assess. 27(8), 1839-1859 (2013). doi:10.1007/s00477-013-0718-x · doi:10.1007/s00477-013-0718-x |
| [7] | Borsdorf, R.: A Newton algorithm for the nearest correlation matrix. M.Sc. Thesis, The University of Manchester, Manchester, UK. MIMS EPrint 2008.49, Manchester Institute for Mathematical Sciences, The University of Manchester (2007) · Zbl 1188.65055 |
| [8] | Borsdorf, R., Higham, N.J.: A preconditioned Newton algorithm for the nearest correlation matrix. IMA J. Numer. Anal. 30(1), 94-107 (2010). doi:10.1093/imanum/drn085 · Zbl 1188.65055 · doi:10.1093/imanum/drn085 |
| [9] | Boyle, JP; Dykstra, RL; Dykstra, R. (ed.); Robertson, T. (ed.); Wright, F. (ed.), A method for finding projections onto the intersection of convex sets in Hilbert spaces, 28-47 (1986), New York · Zbl 0603.49024 · doi:10.1007/978-1-4613-9940-7_3 |
| [10] | Brezinski, C., Redivo-Zaglia, M.: Extrapolation Methods: Theory and Practice. Studies in Computational Mathematics, vol. 2. North-Holland, Amsterdam (1991) · Zbl 0744.65004 |
| [11] | Broyden, C.G.: A class of methods for solving nonlinear simultaneous equations. Math. Comp. 19, 577-593 (1965). doi:10.2307/2003941 · Zbl 0131.13905 · doi:10.2307/2003941 |
| [12] | Cheng, S.H., Higham, N.J.: A modified Cholesky algorithm based on a symmetric indefinite factorization. SIAM J. Matrix Anal. Appl. 19(4), 1097-1110 (1998). doi:10.1137/S0895479896302898 · Zbl 0949.65022 · doi:10.1137/S0895479896302898 |
| [13] | Demirtas, H., Hedeker, D., Mermelstein, R.J.: Simulation of massive public health data by power polynomials. Statist. Med. 31(27), 3337-3346 (2012). doi:10.1002/sim.5362 · Zbl 1238.62079 · doi:10.1002/sim.5362 |
| [14] | Dykstra, R.L.: An algorithm for restricted least squares regression. J. Amer. Statist. Assoc. 78, 837-842 (1983). doi:10.1080/01621459.1983.10477029 · Zbl 0535.62063 · doi:10.1080/01621459.1983.10477029 |
| [15] | Escalante, R., Raydan, M.: Alternating Projection Methods. Society for Industrial and Applied Mathematics, Philadelphia, PA (2011) · Zbl 1275.65031 · doi:10.1137/1.9781611971941 |
| [16] | Eyert, V.: A comparative study on methods for convergence acceleration of iterative vector sequences. J. Comput. Phys. 124(2), 271-285 (1996). doi:10.1006/jcph.1996.0059 · Zbl 0851.65003 · doi:10.1006/jcph.1996.0059 |
| [17] | Fang, H.R, Saad, Y.: Two classes of multisecant methods for nonlinear acceleration. Numer. Linear Algebra Appl. 16(3), 197-221 (2009). doi:10.1002/nla.617 · Zbl 1224.65134 · doi:10.1002/nla.617 |
| [18] | Finger, C.C.: A methodology to stress correlations. RiskMetrics Monitor Fourth Quarter, pp. 3-11 (1997) |
| [19] | Fripp, M.: Greenhouse gas emissions from operating reserves used to backup large-scale wind power. Environ. Sci. Technol. 45(21), 9405-9412 (2011). doi:10.1021/es200417b · doi:10.1021/es200417b |
| [20] | Gould, N.I.M.: How good are projection methods for convex feasibility problems? Comput. Optim. Appl. 40, 1-12 (2008). doi:10.1007/s10589-007-9073-5 · Zbl 1146.90039 · doi:10.1007/s10589-007-9073-5 |
| [21] | Hammarling, S., Lucas, C.: Updating the QR factorization and the least squares problem. MIMS EPrint 2008.111, Manchester Institute for Mathematical Sciences, The University of Manchester, UK (2008) · Zbl 1198.91091 |
| [22] | Hawkins, D.M., Eplett, W.J.R.: The Cholesky factorization of the inverse correlation or covariance matrix in multiple regression. Technometrics 24(3), 191-198 (1982) [http://www.jstor.org/stable/1268678] · Zbl 0498.62057 · doi:10.1080/00401706.1982.10487758 |
| [23] | Higham, N.J.: Computing a nearest symmetric positive semidefinite matrix. Linear Algebra Appl. 103, 103-118 (1988). doi:10.1016/0024-3795(88)90223-6 · Zbl 0649.65026 · doi:10.1016/0024-3795(88)90223-6 |
| [24] | Higham, N.J.: Computing the nearest correlation matrix—A problem from finance. IMA J. Numer. Anal. 22(3), 329-343 (2002). doi:10.1093/imanum/22.3.329 · Zbl 1006.65036 · doi:10.1093/imanum/22.3.329 |
| [25] | Higham, N.J.: The nearest correlation matrix. https://nickhigham.wordpress.com/2013/02/13/the-nearest-correlation-matrix (2013) |
| [26] | Kelley, C.T.: Iterative Methods for Linear and Nonlinear Equations. Society for Industrial and Applied Mathematics, Philadelphia, PA (1995). http://www.siam.org/books/textbooks/fr16_book.pdf · Zbl 0832.65046 · doi:10.1137/1.9781611970944 |
| [27] | Kercheval, A.N.: Optimal covariances in risk model aggregation. In: Proceedings of the 3rd IASTED International Conference on Financial Engineering and Applications, pp 30-35. ACTA Press, Calgary (2006) |
| [28] | Kvaalen, E.: A faster Broyden method. BIT 31(2), 369-372 (1991). doi:10.1007/BF01931297 · Zbl 0735.65034 · doi:10.1007/BF01931297 |
| [29] | López, W., Raydan, M.: An acceleration scheme for Dykstra’s algorithm. Comput. Optim. Appl. doi:10.1007/s10589-015-9768-y (2015) · Zbl 1343.90103 |
| [30] | Lucas, C.: Computing nearest covariance and correlation matrices. M.Sc. Thesis, University of Manchester, Manchester, England (2001) |
| [31] | Minabutdinov, A., Manaev, I., Bouev, M.: Finding the nearest valid covariance matrix: A FX market case. Working paper Ec-07/13, Department of Economics, European University at St. Petersburg, St. Petersburg, Russia. Revised June 2014 (2013) |
| [32] | NAG Library. NAG Ltd., Oxford, UK. http://www.nag.co.uk · Zbl 1022.68613 |
| [33] | Olshanskii, M., Tyrtyshnikov, E.: Iterative Methods for Linear Systems. Society for Industrial and Applied Mathematics, Philadelphia, PA (2014) · Zbl 1320.65050 · doi:10.1137/1.9781611973464 |
| [34] | Pezzulli, S., Frederic, P., Majithia, S., Sabbagh, S., Black, E., Sutton, R., Stephenson, D.: The seasonal forecast of electricity demand: a hierarchical Bayesian model with climatological weather generator. Appl. Stochastic Models Bus. Ind. 22(2), 113-125 (2006). doi:10.1002/asmb.622 · Zbl 1114.62135 · doi:10.1002/asmb.622 |
| [35] | Plasse, J.H.: The EM algorithm in multivariate Gaussian mixture models using Anderson acceleration. M.Sc. Thesis, Worcester Polytechnic Institute, 100 Institute Road, Worcester, MA. http://www.wpi.edu/Pubs/ETD/Available/etd-042513-091152/ (2013) · Zbl 1297.90182 |
| [36] | Potra, F.A., Engler, H.: A characterization of the behavior of the Anderson acceleration on linear problems. Linear Algebra Appl. 438(3), 1002-1011 (2013). doi:10.1016/j.laa.2012.09.008 · Zbl 1263.65036 · doi:10.1016/j.laa.2012.09.008 |
| [37] | Pourahmadi, M.: Joint mean-covariance models with applications to longitudinal data: unconstrained parameterisation. Biometrika 86(3), 677-690 (1999). http: //www.jstor.org/stable/2673662 · Zbl 0949.62066 · doi:10.1093/biomet/86.3.677 |
| [38] | Pulay, P.: Convergence acceleration of iterative sequences. The case of SCF iteration. Chem. Phys. Lett. 73(2), 393-398 (1980). doi:10.1016/0009-2614(80)80396-4 · doi:10.1016/0009-2614(80)80396-4 |
| [39] | Qi, H., Sun, D.: A quadratically convergent Newton method for computing the nearest correlation matrix. SIAM J. Matrix Anal. Appl. 28(2), 360-385 (2006). doi:10.1137/050624509 · Zbl 1120.65049 · doi:10.1137/050624509 |
| [40] | Qi, H., Sun, D.: Correlation stress testing for value-at-risk: an unconstrained convex optimization approach. Comput. Optim. Appl. 45(2), 427-462 (2010). doi:10.1007/s10589-008-9231-4 · Zbl 1198.91091 · doi:10.1007/s10589-008-9231-4 |
| [41] | Qi, H., Sun, D.: An augmented Lagrangian dual approach for the H-weighted nearest correlation matrix problem. IMA J. Numer. Anal. 31, 491-511 (2011). doi:10.1093/imanum/drp031 · Zbl 1218.65061 · doi:10.1093/imanum/drp031 |
| [42] | Raveh, A.: On the use of the inverse of the correlation matrix in multivariate data analysis. Am. Stat. 39(1), 39-42 (1985). doi:10.2307/2683904 · doi:10.2307/2683904 |
| [43] | Rohwedder, T., Schneider, R.: An analysis for the DIIS acceleration method used in quantum chemistry calculations. J. Math. Chem. 49(9), 1889-1914 (2011). doi:10.1007/s10910-011-9863-y · Zbl 1252.81135 · doi:10.1007/s10910-011-9863-y |
| [44] | Saad, Y., Schultz, M.H.: GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Statist. Comput. 7(3), 856-869 (1986). doi:10.1137/0907058 · Zbl 0599.65018 · doi:10.1137/0907058 |
| [45] | Toni, T., Tidor, B.: Combined model of intrinsic and extrinsic variability for computational network design with application to synthetic biology. PLoS Comput. Biol. 9(3), e1002,960 (2013). doi:10.1371/journal.pcbi.1002960 · doi:10.1371/journal.pcbi.1002960 |
| [46] | Toth, A., Kelley, C.T.: Convergence analysis for Anderson acceleration. SIAM J. Numer. Anal. 53(2), 805-819 (2015). doi:10.1137/130919398 · Zbl 1312.65083 · doi:10.1137/130919398 |
| [47] | Turkay, S., Epperlein, E., Christofides, N.: Correlation stress testing for value-at-risk. J. Risk 5(4), 75-89 (2003) |
| [48] | U.S. Geological Survey Geologic Carbon Dioxide Storage Resources Assessment Team: National Assessment of Geologic Carbon Dioxide Storage Resources—Results (Ver. 1.1, September, 2013). http://pubs.usgs.gov/circ/1386 (2013) |
| [49] | Walker, H.F.: Anderson acceleration: Algorithms and implementations. Tech. Rep. MS-6-15-50, Mathematical Sciences Department, Worcester Polytechnic Institute, Worcester, MA 01609, USA (2011) |
| [50] | Walker, H.F., Ni, P.: Anderson acceleration for fixed-point iterations. SIAM J. Numer. Anal. 49(4), 1715-1735 (2011). doi:10.1137/10078356X · Zbl 1254.65067 · doi:10.1137/10078356X |
| [51] | Wang, Q.J., Robertson, D.E., Chiew, F.H.S.: A Bayesian joint probability modeling approach for seasonal forecasting of streamflows at multiple sites. Water Resour. Res. 45(5) (2009). doi:10.1029/2008WR007355 |
| [52] | Wang, X., Anderson, E., Steenkiste, P., Bai, F.: Simulating spatial cross-correlation in vehicular networks. In: IEEE Vehicular Networking Conference (VNC), pp. 207-214 (2014), 10.1109/VNC.2014.7013350 · Zbl 0949.65022 |
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.
