Abstract
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, 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.
Article PDF
Similar content being viewed by others
References
Anderson, D.G.: Iterative procedures for nonlinear integral equations. J. Assoc. Comput. Mach. 12(4), 547–560 (1965). doi:10.1145/321296.321305
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)
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
Bhansali, V., Wise, M.B.: Forecasting portfolio risk in normal and stressed markets. J. Risk 4(1), 91–106 (2001)
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
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
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)
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
Boyle, J.P., Dykstra, R.L.: A method for finding projections onto the intersection of convex sets in Hilbert spaces. In: Dykstra, R., Robertson, T., Wright, F. (eds.) Advances in Order Restricted Statistical Inference, Lecture Notes in Statistics, vol. 37, pp 28–47. Springer, New York (1986), 10.1007/978-1-4613-9940-7_3
Brezinski, C., Redivo-Zaglia, M.: Extrapolation Methods: Theory and Practice. Studies in Computational Mathematics, vol. 2. North-Holland, Amsterdam (1991)
Broyden, C.G.: A class of methods for solving nonlinear simultaneous equations. Math. Comp. 19, 577–593 (1965). doi:10.2307/2003941
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
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
Dykstra, R.L.: An algorithm for restricted least squares regression. J. Amer. Statist. Assoc. 78, 837–842 (1983). doi:10.1080/01621459.1983.10477029
Escalante, R., Raydan, M.: Alternating Projection Methods. Society for Industrial and Applied Mathematics, Philadelphia, PA (2011)
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
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
Finger, C.C.: A methodology to stress correlations. RiskMetrics Monitor Fourth Quarter, pp. 3–11 (1997)
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
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
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)
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]
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
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
Higham, N.J.: The nearest correlation matrix. https://nickhigham.wordpress.com/2013/02/13/the-nearest-correlation-matrix (2013)
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
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)
Kvaalen, E.: A faster Broyden method. BIT 31(2), 369–372 (1991). doi:10.1007/BF01931297
López, W., Raydan, M.: An acceleration scheme for Dykstra’s algorithm. Comput. Optim. Appl. doi:10.1007/s10589-015-9768-y (2015)
Lucas, C.: Computing nearest covariance and correlation matrices. M.Sc. Thesis, University of Manchester, Manchester, England (2001)
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)
NAG Library. NAG Ltd., Oxford, UK. http://www.nag.co.uk
Olshanskii, M., Tyrtyshnikov, E.: Iterative Methods for Linear Systems. Society for Industrial and Applied Mathematics, Philadelphia, PA (2014)
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
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)
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
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
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
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
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
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
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
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
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
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
Toth, A., Kelley, C.T.: Convergence analysis for Anderson acceleration. SIAM J. Numer. Anal. 53(2), 805–819 (2015). doi:10.1137/130919398
Turkay, S., Epperlein, E., Christofides, N.: Correlation stress testing for value-at-risk. J. Risk 5(4), 75–89 (2003)
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)
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)
Walker, H.F., Ni, P.: Anderson acceleration for fixed-point iterations. SIAM J. Numer. Anal. 49(4), 1715–1735 (2011). doi:10.1137/10078356X
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
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
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was supported by European Research Council Advanced Grant MATFUN (267526). The first author was also supported by Engineering and Physical Sciences Research Council grant EP/I01912X/1.
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
About this article
Cite this article
Higham, N.J., Strabić, N. Anderson acceleration of the alternating projections method for computing the nearest correlation matrix. Numer Algor 72, 1021–1042 (2016). https://doi.org/10.1007/s11075-015-0078-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-015-0078-3
Keywords
- Nearest correlation matrix
- Indefinite matrix
- Positive semidefinite matrix
- Anderson acceleration
- Alternating projections method
- Dykstra’s correction