A Riemannian inexact Newton dogleg method for constructing a symmetric nonnegative matrix with prescribed spectrum. (English) Zbl 07676507
Summary: This paper is concerned with the inverse problem of constructing a symmetric nonnegative matrix from realizable spectrum. We reformulate the inverse problem as an underdetermined nonlinear matrix equation over a Riemannian product manifold. To solve it, we develop a Riemannian underdetermined inexact Newton dogleg method for solving a general underdetermined nonlinear equation defined between Riemannian manifolds and Euclidean spaces. The global and quadratic convergence of the proposed method is established under some mild assumptions. Then, we solve the inverse problem by applying the proposed method to its equivalent nonlinear matrix equation and a preconditioner for the perturbed normal Riemannian Newton equation is also constructed. Numerical tests show the efficiency of the proposed method for solving the inverse problem.
MSC:
| 65-XX | Numerical analysis |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
| 65F08 | Preconditioners for iterative methods |
| 65F18 | Numerical solutions to inverse eigenvalue problems |
| 65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
Keywords:
symmetric nonnegative inverse eigenvalue problem; underdetermined equation; Riemannian Newton dogleg method; preconditionerReferences:
| [1] | Absil, P-A; Mahony, R.; Sepulchre, R., Optimization Algorithms on Matrix Manifolds (2008), Princeton: Princeton University Press, Princeton · Zbl 1147.65043 |
| [2] | Bao, JF; Li, C.; Shen, WP; Yao, JC; Guu, SM, Approximate Gauss-Newton methods for solving underdetermined nonlinear least squares problems, Appl. Numer. Math., 111, 92-110 (2017) · Zbl 1353.65042 |
| [3] | Bapat, RB; Raghavan, TES, Nonnegative Matrices and Applications (1997), Cambridge: Cambridge University Press, Cambridge · Zbl 0879.15015 |
| [4] | Berman, A.; Plemmons, RJ, Nonnegative Matrices in the Mathematical Sciences (1979), New York: Academic Press, New York · Zbl 0484.15016 |
| [5] | Chen, X.; Liu, DL, Isospectral flow method for nonnegative inverse eigenvalue problem with prescribed structure, J. Comput. Appl. Math., 235, 3990-4002 (2011) · Zbl 1229.65067 |
| [6] | Chen, XJ; Yamamotob, T., Newton-like methods for solving underdetermined nonlinear equations with nondifferentiable terms, J. Comput. Appl. Math., 59, 311-324 (1994) · Zbl 0823.65048 |
| [7] | Chu, MT; Diele, F.; Sgura, I., Gradient flow method for matrix completion with prescribed eigenvalues, Linear Algebra Appl., 379, 85-112 (2004) · Zbl 1055.15026 |
| [8] | Chu, MT; Driessel, KR, Constructing symmetric nonnegative matrices with prescribed eigenvalues by differential equations, SIAM J. Math. Anal., 22, 1372-1387 (1991) · Zbl 0739.58053 |
| [9] | Chu, MT; Golub, GH, Structured inverse eigenvalue problems, Acta Numer., 11, 1-71 (2002) · Zbl 1105.65326 |
| [10] | Chu, MT; Golub, GH, Inverse Eigenvalue Problems: Theory, Algorithms, and Applications (2005), Oxford: Oxford University Press, Oxford · Zbl 1075.65058 |
| [11] | Chu, MT; Guo, Q., A numerical method for the inverse stochastic spectrum problem, SIAM J. Matrix Anal. Appl., 19, 1027-1039 (1998) · Zbl 0917.65037 |
| [12] | Echebest, N.; Schuverdt, ML; Vignau, RP, Two derivative-free methods for solving underdetermined nonlinear systems of equations, Comput. Appl. Math., 30, 217-245 (2011) · Zbl 1220.65060 |
| [13] | Echebest, N.; Schuverdt, ML; Vignau, RP, A derivative-free method for solving box-constrained underdetermined nonlinear systems of equations, Appl. Math. Comput., 219, 3198-3208 (2012) · Zbl 1309.65055 |
| [14] | Ellard, R.; S̆migoc, H., Connecting sufficient conditions for the symmetric nonnegative inverse eigenvalues problem, Linear Algebra Appl., 498, 521-552 (2016) · Zbl 1334.15028 |
| [15] | Eisenstat, SC; Walker, HF, Choosing the forcing terms in an inexact Newton method, SIAM J. Sci. Comput, 17, 16-32 (1996) · Zbl 0845.65021 |
| [16] | Egleston, PD; Lenker, TD; Narayan, SK, The nonnegative inverse eigenvalue problem, Linear Algebra Appl., 379, 475-490 (2004) · Zbl 1040.15009 |
| [17] | Francisco, JB; Krejić, N.; Martínez, JM, An interior point method for solving box-constrained underdetermined nonlinear systems, J. Comput. Appl. Math., 177, 67-88 (2005) · Zbl 1064.65035 |
| [18] | Golub, GH; Van Loan, CF, Matrix Computations (2013), Baltimore: Johns Hopkins University Press, Baltimore · Zbl 1268.65037 |
| [19] | Henderson, HV; Searle, SR, Vet and vech operators for matrices, with some uses in Jacobians and multivariate statistics, Canad. J. Statist., 7, 65-81 (1979) · Zbl 0435.15022 |
| [20] | Johnson, C.R., Marijuán, C., Paparella, P., Pisonero, M.: The NIEP. In: André, C., Bastos, A., Karlovich, A. Y., Silbermann, B., Zaballa, I. (eds.) Operator Theory, Operator Algebras, and Matrix Theory. Operator Theory: Advances and Applications, vol. 267, pp 199-220. Cham, Birkhäuser (2018) · Zbl 1427.15001 |
| [21] | Johnson, CR; Paparella, P., Perron spectratopes and the real nonnegative inverse eigenvalue problem, Linear Algebra Appl., 493, 281-300 (2016) · Zbl 1329.15028 |
| [22] | Karpelevic̆, FI, On the characteristic roots of matrices with nonnegative elements, Izv. Akad. Nauk SSSR Ser. Mat., 15, 361-383 (1951) · Zbl 0043.01603 |
| [23] | Laffey, TJ; Šmigoc, H., Nonnegative realization of spectra having negative real parts, Linear Algebra Appl., 416, 148-159 (2006) · Zbl 1103.15005 |
| [24] | Lin, MM, Fast recursive algorithm for constructing nonnegative matrices with prescribed real eigenvalues, Appl. Math. Comput., 256, 582-590 (2015) · Zbl 1338.65106 |
| [25] | Loewy, R.; London, D., A note on an inverse problems for nonnegative matrices, Linear Multilinear Algebra, 6, 83-90 (1978) · Zbl 0376.15006 |
| [26] | Luenberger, DG, Optimization by Vector Space Methods (1969), New York: Wiley, New York · Zbl 0176.12701 |
| [27] | Martinez, JM, Quasi-Newton methods for solving underdetermined nonlinear simultaneous equations, J. Comput. Appl. Math., 34, 171-190 (1991) · Zbl 0729.65035 |
| [28] | Minc, H., Nonnegative Matrices (1988), New York: Wiley, New York · Zbl 0638.15008 |
| [29] | de Oliveira, GN, Nonnegative matrices with prescribed spectrum, Linear Algebra Appl., 54, 117-121 (1983) |
| [30] | Orsi, R., Numerical methods for solving inverse eigenvalue problems for nonnegative matrices, SIAM J. Matrix Anal. Appl., 28, 190-212 (2006) · Zbl 1113.65034 |
| [31] | Paparella, P., Realizing Suleimanova-type spectra via permutative matrices, Electron J. Linear Algebra., 31, 306-312 (2016) · Zbl 1341.15008 |
| [32] | Pawlowski, RP; Simonis, JP; Walker, HF; Shadid, JN, Inexact Newton dogleg methods, SIAM J. Numer. Anal., 46, 2112-2132 (2008) · Zbl 1183.65055 |
| [33] | Reams, R., An inequality for nonnegative matrices and the inverse eigenvalue problem, Linear Multilinear Algebra, 41, 367-375 (1996) · Zbl 0887.15015 |
| [34] | Senata, E., Non-negative Matrices and Markov Chains, 2nd edn (2006), New York: Springer, New York · Zbl 1099.60004 |
| [35] | Soto, RL, Realizability criterion for the symmetric nonnegative inverse eigenvalue problem, Linear Algebra Appl., 416, 783-794 (2006) · Zbl 1097.15013 |
| [36] | Soto, RL, A family of realizability criteria for the real and symmetric nonnegative inverse eigenvalue problem, Numer. Linear Algebra Appl., 20, 336-348 (2013) · Zbl 1289.15052 |
| [37] | Soules, GW, Constructing symmetric nonnegative matrices, Linear Multilinear Alg., 13, 241-251 (1983) · Zbl 0516.15013 |
| [38] | Simons, J.P.: Inexact Newton methods applied to underdetermined systems, PhD thesis. Department of Mathematical Science Worcester Polytechnic Institute (2006) |
| [39] | Walker, HF; Watson, LT, Least-change secant update methods for underdetermined systems, SIAM J. Numer. Anal., 27, 1227-1262 (1990) · Zbl 0733.65032 |
| [40] | Wang, Y.; Zhao, Z.; Bai, ZJ, Riemannian Newton-CG methods for constructing a positive doubly stochastic matrix from spectral data, Inverse Probl., 36, 115006 (2020) · Zbl 1460.15023 |
| [41] | Xu, SF, An Introduction to Inverse Algebraic Eigenvalue Problems (1998), Braunschweig: Friedr Vieweg & Sohn, Braunschweig · Zbl 0927.65057 |
| [42] | Yao, TT; Bai, ZJ; Zhao, Z., A Riemannian variant of the Fletcher-Reeves conjugate gradient method for stochastic inverse eigenvalue problems with partial eigendata, Numer, Linear Algebra Appl., 26, e2221 (2019) · Zbl 1524.65174 |
| [43] | Yao, TT; Bai, ZJ; Zhao, Z.; Ching, WK, A Riemannian Fletcher-Reeves conjugate gradient method for doubly stochastic inverse eigenvalue problems, SIAM J. Matrix Anal. Appl., 37, 215-234 (2016) · Zbl 1376.65061 |
| [44] | Yasser, HA, Linear Algebra - Theorems and Applications (2012), Croatia: Intechopen, Croatia · Zbl 1351.15003 |
| [45] | Zhao, Z.; Bai, ZJ; Jin, XQ, A Riemannian inexact Newton-CG method for constructing a nonnegative matrix with prescribed realizable spectrum, Numer. Math., 140, 827-855 (2018) · Zbl 1416.65101 |
| [46] | Zhao, Z.; Jin, XQ; Bai, ZJ, A geometric nonlinear conjugate gradient method for stochastic inverse eigenvalue problems, SIAM J. Numer. Anal., 54, 2015-2035 (2016) · Zbl 1342.65119 |
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.
