×

Selective alternating projections to find the nearest SDD\(^{+}\) matrix. (English) Zbl 1032.65040

Summary: We extend and improve recently proposed algorithms to solve the problem of minimizing the distance from a given matrix to the cone of symmetric and diagonally dominant matrices with positive diagonal (SDD\(^+\)). We present a variety of criteria to select a subset of the supporting hyperplanes of the faces of SDD\(^+\), and also of the polar cone (SDD\(^+\))\(^0\), to then apply R. L. Dykstra’s alternating projection method [J. Am. Stat. Assoc. 78, 837-842 (1983; Zbl 0535.62063)]. These selections reduce the number of projections and therefore reduce the required computational work. In all our new algorithms, the symmetry and the diagonal dominance of the obtained matrix are guaranteed. Preliminary numerical experiments indicate that some of the selection criteria produce a significant reduction in CPU time.

MSC:

65F30 Other matrix algorithms (MSC2010)

Citations:

Zbl 0535.62063
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Mendoza, M.; Raydan, M.; Tarazaga, P., Computing the nearest diagonally dominant matrix, Numer. Linear Algebra Appl., 5, 461-474 (1998) · Zbl 0979.65035
[2] Boyle, J. P.; Dykstra, R. L., A method for finding projections onto the intersection of convex sets in hilbert spaces, Lecture Notes in Statistics, 37, 28-47 (1986)
[3] Dykstra, R. L., An algorithm for restricted least-squares regression, J. Am. Stat. Assoc., 78, 837-842 (1983) · Zbl 0535.62063
[4] Raydan, M.; Tarazaga, P., Primal and polar approach for computing the symmetric diagonally dominant projection, Numer. Linear Algebra Appl., 9, 333-345 (2002) · Zbl 1071.65055
[5] Moreau, J. J., Décomposition orthogonale d’un espace hilbertien selon deux cônes mutuellement polaires, C.R. Acad. Sci. Paris, 255, 238-240 (1962) · Zbl 0109.08105
[6] M. Monsalve, J. Moreno, Proyecciones alternas selectivas sobre conos poliedrales, Tesis de Pregrado, Facultad de Ciencias, Escuela de Computación, Universidad Central de Venezuela, Caracas, Venezuela, 2001; M. Monsalve, J. Moreno, Proyecciones alternas selectivas sobre conos poliedrales, Tesis de Pregrado, Facultad de Ciencias, Escuela de Computación, Universidad Central de Venezuela, Caracas, Venezuela, 2001
[7] Raydan, M.; Tarazaga, P., Computing the symmetric diagonally dominant projection via duality, (Barety, J. E.; Caceres, L. F.; Ramos, M., Proceedings of XV SIDIM (2000), University of Puerto Rico: University of Puerto Rico Mayaguez, Puerto Rico), 59-76
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.