×

Decomposition methods for sparse matrix nearness problems. (English) Zbl 1342.90128

Summary: We discuss three types of sparse matrix nearness problems: given a sparse symmetric matrix, find the matrix with the same sparsity pattern that is closest to it in Frobenius norm and (1) is positive semidefinite, (2) has a positive semidefinite completion, or (3) has a Euclidean distance matrix completion. Several proximal splitting and decomposition algorithms for these problems are presented and their performance is compared on a set of test problems. A key feature of the methods is that they involve a series of projections on small dense positive semidefinite or Euclidean distance matrix cones, corresponding to the cliques in a triangulation of the sparsity graph. The methods discussed include the dual block coordinate ascent algorithm (or Dykstra’s method), the dual projected gradient and accelerated projected gradient algorithms, and a primal and a dual application of the Douglas-Rachford splitting algorithm.

MSC:

90C22 Semidefinite programming
65F50 Computational methods for sparse matrices
15A83 Matrix completion problems
90C25 Convex programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J. Agler, J. W. Helton, S. McCullough, and L. Rodman, {\it Positive semidefinite matrices with a given sparsity pattern}, Linear Algebra Appl., 107 (1988), pp. 101-149. · Zbl 0655.15016
[2] S. Al-Homidan and M. AlQarni, {\it Structure methods for solving the nearest correlation matrix problem}, Positivity, 16 (2012), pp. 497-508. · Zbl 1334.90094
[3] S. Al-Homidan and H. Wolkowicz, {\it Approximate and exact completion problems for Euclidean distance matrices using semidefinite programming}, Linear Algebra Appl., 406 (2005), pp. 109-141. · Zbl 1081.15011
[4] C. M. Alaíz, F. Dinuzzo, and S. Sra, {\it Correlation matrix nearness and completion under observation uncertainty}, IMA J. Numer. Anal., 35 (2015), pp. 325-340. · Zbl 1309.65066
[5] A. Y. Alfakih, A. Khandani, and H. Wolkowicz, {\it Solving Euclidean distance matrix completion problems via semidefinite programming}, Comput. Optim. Appl., 12 (1999), pp. 13-30. · Zbl 1040.90537
[6] B. Alipanahi, N. Krislock, A. Ghodsi, H. Wolkowicz, L. Donaldson, and M. Li, {\it Determining protein structures from NOESY distance constraints by semidefinite programming}, J. Comput. Biol., 20 (2013), pp. 296-310.
[7] M. Bakonyi and C. R. Johnson, {\it The Euclidian distance matrix completion problem}, SIAM J. Matrix Anal. Appl., 16 (1995), pp. 646-654. · Zbl 0823.15012
[8] H. H. Bauschke and P. L. Combettes, {\it Convex Analysis and Monotone Operator Theory in Hilbert Spaces}, Springer, New York, 2011. · Zbl 1218.47001
[9] A. Beck and M. Teboulle, {\it A fast iterative shrinkage-thresholding algorithm for linear inverse problems}, SIAM J. Imaging Sci., 2 (2009), pp. 183-202. · Zbl 1175.94009
[10] A. Beck and M. Teboulle, {\it A fast dual proximal gradient algorithm for convex minimization and applications}, Oper. Res. Lett., 42 (2014), pp. 1-6. · Zbl 1408.90232
[11] A. Beck and L. Tetruashvili, {\it On the convergence of block coordinate descent type methods}, SIAM J. Optim., 23 (2013), pp. 2037-2060. · Zbl 1297.90113
[12] D. P. Bertsekas and J. N. Tsitsiklis, {\it Parallel and Distributed Computation: Numerical Methods}, Athena Scientific, Belmont, MA, 1997. · Zbl 0743.65107
[13] E. G. Birgin and M. Raydan, {\it Robust stopping criteria for Dykstra’s algorithm}, SIAM J. Sci. Comput., 26 (2005), pp. 1405-1414. · Zbl 1149.90382
[14] P. Biswas and Y. Ye, {\it Semidefinite programming for ad hoc wireless sensor network localization}, in Third International Symposium on Information Processing in Sensor Networks, IPSN’04, ACM, New York, 2004, pp. 46-54.
[15] J. R. S. Blair and B. Peyton, {\it An introduction to chordal graphs and clique trees}, in Graph Theory and Sparse Matrix Computation, A. George, J. R. Gilbert, and J. W. H. Liu, eds., Springer-Verlag, New York, 1993. · Zbl 0803.68081
[16] R. Borsdorf, N. J. Higham, and M. Raydan, {\it Computing a nearest correlation matrix with factor structure}, SIAM J. Matrix Anal. Appl., 31 (2010), pp. 2603-2622. · Zbl 1213.65022
[17] S. Boyd and L. Xiao, {\it Least-squares covariance matrix adjustment}, SIAM J. Matrix Anal. Appl., 27 (2005), pp. 532-546. · Zbl 1099.65039
[18] J. P. Boyle and R. L. Dykstra, {\it A method for finding projections onto the intersection of convex sets in Hilbert spaces}, in Advances in Order Restricted Statistical Inference, R. Dykstra, T. Robertson, and F. T. Wright, eds., Lecture Notes in Statist. 37, Springer-Verlag, New York, 1986, pp. 28-47. · Zbl 0603.49024
[19] Y. Censor and S. A. Zenios, {\it Parallel Optimization: Theory, Algorithms, and Applications}, Numerical Math. Sci. Comput., Oxford University Press, New York, 1997. · Zbl 0945.90064
[20] A. Chambolle and C. Dossal, {\it On the convergence of the iterates of the “Fast Iterative Shrinkage/Thresholding Algorithm”}. J. Optim. Theory Appl., 166 (2015), pp. 968-982. · Zbl 1371.65047
[21] D. Davis and W. Yin, {\it Convergence Rate Analysis of Several Splitting Schemes}, preprint, arXiv:1406.4834, 2014.
[22] D. Davis and W. Yin, {\it Faster Convergence Rates of Relaxed Peaceman-Rachford and ADMM Under Regularity Assumptions}, preprint, arXiv:1407.5210, 2014. · Zbl 1379.65035
[23] T. A. Davis, {\it Direct Methods for Sparse Linear Systems}, Fundam. Algorithms, SIAM, Philadelphia, 2006. · Zbl 1119.65021
[24] T. A. Davis and Y. Hu, {\it The University of Florida sparse matrix collection}, ACM Trans. Math. Software, 38 (2011), 1. · Zbl 1365.65123
[25] D. Drusvyatskiy, G. Pataki, and H. Wolkowicz, {\it Coordinate shadows of semidefinite and Euclidean distance matrices}, SIAM J. Optim., 25 (2015), pp. 1160-1178. · Zbl 1320.90054
[26] R. L. Dykstra, {\it An algorithm for restricted least squares regression}, J. Amer. Statist. Assoc., 78 (1983), pp. 837-842. · Zbl 0535.62063
[27] J. Eckstein and D. Bertsekas, {\it On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators}, Math. Program., 55 (1992), pp. 293-318. · Zbl 0765.90073
[28] N. Gaffke and R. Mathar, {\it A cyclic projection algorithm via duality}, Metrika, 36 (1989), pp. 29-54. · Zbl 0676.90054
[29] W. Glunt, T. L. Hayden, S. Hong, and J. Wells, {\it An alternating projection algorithm for computing the nearest Euclidean distance matrix}, SIAM J. Matrix Anal. Appl., 11 (1990), pp. 589-600. · Zbl 0728.65034
[30] A. Griewank and P. L. Toint, {\it On the existence of convex decompositions of partially separable functions}, Math. Program., 28 (1984), pp. 25-49. · Zbl 0561.65045
[31] R. Grone, C. R. Johnson, E. M. Sá, and H. Wolkowicz, {\it Positive definite completions of partial Hermitian matrices}, Linear Algebra Appl., 58 (1984), pp. 109-124. · Zbl 0547.15011
[32] S.-P. Han, {\it A successive projection method}, Math. Program., 40 (1988), pp. 1-14. · Zbl 0685.90074
[33] S.-P. Han and G. Lou, {\it A parallel algorithm for a class of convex programs}, SIAM J. Control Optim., 26 (1988), pp. 345-355. · Zbl 0644.90068
[34] T. Hayden and J. Wells, {\it Approximation by matrices positive semidefinite on a subspace}, Linear Algebra Appl., 109 (1988), pp. 115-130. · Zbl 0667.15020
[35] P. Heggernes, {\it Minimal triangulation of graphs: A survey}, Discrete Math., 306 (2006), pp. 297-317. · Zbl 1086.05069
[36] D. Henrion and J. Malick, {\it Projection methods for conic feasibility problems: applications to polynomial sum-of-squares decompositions}, Optim. Methods Softw., 26 (2011), pp. 23-46. · Zbl 1228.90071
[37] D. Henrion and J. Malick, {\it Projection methods in conic optimization}, in Handbook on Semidefinite, Conic and Polynomial Optimization, M. F. Anjos and J. B. Lasserre, eds., Springer, New York, 2012, pp. 565-600. · Zbl 1334.90105
[38] N. Higham, {\it Computing a nearest symmetric positive semidefinite matrix}, Linear Algebra Appl., 103 (1988), pp. 103-118. · Zbl 0649.65026
[39] N. Higham, {\it Computing the nearest correlation matrix–a problem from finance}, IMA J. Numer. Anal., 22 (2002), pp. 329-343. · Zbl 1006.65036
[40] N. Krislock and H. Wolkowicz, {\it Euclidean distance matrices and applications}, in Handbook on Semidefinite, Conic and Polynomial Optimization, M. F. Angos and J. B. Lasserre, eds., Springer, New York, 2012, pp. 879-914. · Zbl 1334.90109
[41] P. L. Lions and B. Mercier, {\it Splitting algorithms for the sum of two nonlinear operators}, SIAM J. Numer. Anal., 16 (1979), pp. 964-979. · Zbl 0426.65050
[42] J. Malick, {\it A dual approach to semidefinite least-squares problems}, SIAM J. Matrix Anal. Appl., 26 (2004), pp. 272-284. · Zbl 1080.65027
[43] J. J. Moreau, {\it Proximité et dualité dans un espace hilbertien}, Bull. Soc. Math. France, 93 (1965), pp. 273-299. · Zbl 0136.12101
[44] Y. Nesterov, {\it A method of solving a convex programming problem with convergence rate \(O(1/k^2)\)}, Sov. Math. Dokl., 27 (1983), pp. 372-376. · Zbl 0535.90071
[45] Y. Nesterov, {\it Introductory Lectures on Convex Optimization}, Kluwer Academic, Dordrecht, The Netherlands, 2004. · Zbl 1086.90045
[46] B. T. Polyak, {\it Introduction to Optimization}, Optimization Software, New York, 1987.
[47] H. Qi and D. Sun, {\it A quadratically convergent Newton method for computing the nearest correlation matrix}, SIAM J. Matrix Anal. Appl., 28 (2006), pp. 360-385. · Zbl 1120.65049
[48] H. Qi and D. Sun, {\it Correlation stress testing for value-at-risk: An unconstrained convex optimization approach}, Comput. Optim. Appl., 45 (2010), pp. 427-462. · Zbl 1198.91091
[49] H. Qi and D. Sun, {\it An augmented Lagrangian dual approach for the {\it H}-weighted nearest correlation matrix problem}, IMA J. Numer. Anal., 31 (2011), pp. 491-511. · Zbl 1218.65061
[50] H.-D. Qi, {\it A semismooth Newton method for the nearest Euclidean distance matrix problem}, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 67-93. · Zbl 1266.49052
[51] H.-D. Qi, N. Xiu, and X. Yuan, {\it A Lagrangian dual approach to the single-source localization problem}, IEEE Trans. Signal Process., 61 (2013), pp. 3815-3826. · Zbl 1393.94401
[52] R. Rebonato and P. Jäckel, {\it The Most General Methodology to Create a Valid Correlation Matrix for Risk Management and Option Pricing Purposes}, Quantitative Research Centre of the NatWest Group, Royal Bank of Scotland, 1999.
[53] R. T. Rockafellar, {\it Convex Analysis}, 2nd ed., Princeton University Press, Princeton, NJ, 1970. · Zbl 0193.18401
[54] D. J. Rose, {\it Triangulated graphs and the elimination process}, J. Math. Anal. Appl., 32 (1970), pp. 597-609. · Zbl 0216.02602
[55] I. J. Schoenberg, {\it Remarks to Maurice Fréchet’s article “Sur la définition axiomatique d”une classe d’espaces vectoriels distanciés applicables vectoriellement sur l’espace de Hilbert”}, Ann. Math., 36 (1935), pp. 724-732. · Zbl 0012.30703
[56] J. E. Spingarn, {\it Partial inverse of a monotone operator}, Appl. Math. Optim., 10 (1983), pp. 247-265. · Zbl 0524.90072
[57] J. E. Spingarn, {\it Applications of the method of partial inverses to convex programming: Decomposition}, Math. Program., 32 (1985), pp. 199-223. · Zbl 0565.90058
[58] Y. Sun, M. S. Andersen, and L. Vandenberghe, {\it Decomposition in conic optimization with partially separable structure}, SIAM J. Optim., 24 (2014), pp. 873-897. · Zbl 1297.90111
[59] M. W. Trosset, {\it Applications of Multidimensional Scaling to Molecular Conformation}, Technical report, Rice University, Houston, TX, 1997.
[60] P. Tseng, {\it Further applications of a splitting algorithm to decomposition in variational inequalities and convex programming}, Math. Program., 48 (1990), pp. 249-263. · Zbl 0725.90079
[61] P. Tseng, {\it Applications of a splitting algorithm to decomposition in convex programming and variational inequalities}, SIAM J. Control Optim., 29 (1991), pp. 119-138. · Zbl 0737.90048
[62] P. Tseng, {\it Dual coordinate ascent methods for non-strictly convex minimization}, Math. Program., 59 (1993), pp. 231-247. · Zbl 0782.90073
[63] P. Tseng, {\it On Accelerated Proximal Gradient Methods for Convex-Concave Optimization}, manuscript, 2008.
[64] K. Wüthrich, {\it Protein structure determination in solution by nuclear magnetic resonance spectroscopy}, Science, 243 (1989), pp. 45-50.
[65] M. Yannakakis, {\it Computing the minimum fill-in is NP-complete}, SIAM J. Algebraic Discrete Meth., 2 (1981), pp. 77-79. · Zbl 0496.68033
[66] F. W. Young, {\it Multidimensional Scaling: History, Theory, and Applications}, Psychology Press, Hoboken, NJ, 2013.
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.