A trust-region method for solving truncated complex singular value decomposition. (English) Zbl 07924444
Summary: The truncated singular value decomposition has been widely used in many areas of science including engineering, and statistics, etc. In this paper, the original truncated complex singular value decomposition problem is formulated as a Riemannian optimization problem on a product of two complex Stiefel manifolds, a practical algorithm based on the generic Riemannian trust-region method of Absil et al. is presented to solve the underlying problem, which enjoys the global convergence and local superlinear convergence rate. Numerical experiments are provided to illustrate the efficiency of the proposed method. Comparisons with some classical Riemannian gradient-type methods, the existing Riemannian version of limited-memory BFGS algorithms in the MATLAB toolbox Manopt and the Riemannian manifold optimization library ROPTLIB, and some latest infeasible methods for solving manifold optimization problems, are also provided to show the merits of the proposed approach.
MSC:
| 15A24 | Matrix equations and identities |
| 15A57 | Other types of matrices (MSC2000) |
| 65F10 | Iterative numerical methods for linear systems |
| 65F30 | Other matrix algorithms (MSC2010) |
References:
| [1] | P.A. Absil, C.G. Baker, and K.A. Gallivan, Trust-region methods on Riemannian manifolds with applications in numerical linear algebra, in: Proceedings of the 16th International Symposium on Mathematical Theory of Networks and Systems, Belgium, (2004). |
| [2] | P.A. Absil, C.G. Baker, and K.A. Gallivan, Trust-region methods on Riemannian manifolds, Found. Comput. Math., 7:3 (2007), 303-330. · Zbl 1129.65045 |
| [3] | P.A. Absil, R. Mahony, and R. Sepulchre, Optimization Algorithms on Matrix Manifolds, Princeton University Press, 2009. |
| [4] | P.A. Absil, R. Mahony, and J. Trumpf, An extrinsic look at the Riemannian Hessian, in: Inter-national Conference on Geometric Science of Information, 361-368, Springer, (2013). · Zbl 1323.53014 |
| [5] | K. Aihara and H. Sato, A matrix-free implementation of Riemannian Newton’s method on the Stiefel manifold, Optim. Lett., 11:8 (2017), 1729-1741. · Zbl 1386.90141 |
| [6] | H. Attouch, J. Bolte, P. Redont, and A. Soubeyran, Proximal alternating minimization and projec-tion methods for nonconvex problems: An approach based on the Kurdyka-Lojasiewicz inequality, Math. Oper. Res., 35:2 (2010), 438-457. · Zbl 1214.65036 |
| [7] | C.G. Baker, P.A. Absil, and K.A. Gallivan, An implicit trust-region method on Riemannian manifolds, IMA J. Numer. Anal., 28:4 (2008), 665-689. · Zbl 1158.65320 |
| [8] | J. Bolte, S. Sabach, and M. Teboulle, Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Math. Program., 146:1-2 (2014), 459-494. · Zbl 1297.90125 |
| [9] | N. Boumal and P.A. Absil, RTRMC: A Riemannian trust-region method for low-rank matrix completion, in: Advances in Neural Information Processing Systems, (2011), 406-414. |
| [10] | N. Boumal, B. Mishra, P.A. Absil, and R. Sepulchre, Manopt, a Matlab toolbox for optimization on manifolds, J. Mach. Learn. Res., 15:1 (2014), 1455-1459. · Zbl 1319.90003 |
| [11] | M. Brand, Fast low-rank modifications of the thin singular value decomposition, Linear Algebra Appl., 415:1 (2006), 20-30. · Zbl 1088.65037 |
| [12] | T.F. Chan and P.C. Hansen, Computing truncated singular value decomposition least squares solutions by rank revealing QR-factorizations, SIAM J. Sci. Comput., 11:3 (1990), 519-530. · Zbl 0699.65030 |
| [13] | W. Chen, Y. You, and H. Ji, An augented Lagrangian method for l1-regularized optimization problems with orthogonal constraints, SIAM J. Sci. Stat. Comput., 38:4 (2016), B570-B592. · Zbl 1386.65160 |
| [14] | Y. Chu, K. Xu, Y. Zhong, X. Ye, T. Zhou, X. Chen, and G. Wang, Fast microwave through wall imaging method with inhomogeneous background based on Levenberg-Marquardt algorithm, IEEE Trans. Microw. Theory Tech., 67:3 (2018), 1138-1147. |
| [15] | T.A. Davis and Y. Hu, The University of Florida sparse matrix collection, ACM Trans. Math. Softw., 38:1 (2011), 1-25. · Zbl 1365.65123 |
| [16] | S. Dogu, M.N. Akıncı, M. C ¸ayören, and İ. Akduman, Truncated singular value decomposition for through-the-wall microwave imaging application, IET Microw. Antennas Propag., 14:4 (2019), 260-267. |
| [17] | A. Edelman, T.A. Arias, and S.T. Smith, The geometry of algorithms with orthogonality con-straints, SIAM J. Matrix Anal. Appl., 20:2 (1998), 303-353. · Zbl 0928.65050 |
| [18] | G. Gennarelli and F. Soldovieri, A linear inverse scattering algorithm for radar imaging in multi-path environments, IEEE Geosci. Remote. Sens. Lett., 10:5 (2013), 1085-1089. |
| [19] | P.C. Hansen, Truncated singular value decomposition solutions to discrete ill-posed problems with ill-determined numerical rank, SIAM J. Sci. Stat. Comput., 11:3 (1990), 503-518. · Zbl 0699.65029 |
| [20] | G. Heidel and V. Schulz, A Riemannian trust-region method for low-rank tensor completion, Numer. Linear Algebra Appl., 25:6 (2018), e2175. · Zbl 1513.65197 |
| [21] | W. Huang, P.A. Absil, K.A. Gallivan, and P. Hand, ROPTLIB: An object-oriented C++ library for optimization on Riemannian manifolds, ACM Trans. Math. Softw., 44:4 (2018), 43.1-43.21. · Zbl 1484.65142 |
| [22] | W. Huang, K.A. Gallivan, and P.A. Absil, A broyden class of quasi-Newton methods for Rieman-nian optimization, SIAM J. Optim., 25:3 (2015), 1660-1685. · Zbl 1461.65156 |
| [23] | W. Huang, K.A. Gallivan, P.A. Absil, and P. Hand, ROPTLIB: Riemannian Manifold Optimiza-tion Library (User Manual), 2020. |
| [24] | M. Ishteva, P.A. Absil, S.V. Huffel, and L.D. Lathauwer, Best low multilinear rank approximation of higher-order tensors, based on the Riemannian trust-region scheme, SIAM J. Matrix Anal. Appl., 32:1 (2011), 115-135. · Zbl 1218.65041 |
| [25] | R. Lai and S. Osher, A splitting method for orthogonality constrained problems, J. Sci. Comput., 58:2 (2014), 431-449. · Zbl 1296.65087 |
| [26] | J.F. Li, W. Li, S.W. Vong, Q.L. Luo, and M. Xiao, A Riemannian optimization approach for solving the generalized eigenvalue problem for nonsquare matrix pencils, J. Sci. Comput., 82:3 (2020), 1-43. · Zbl 1439.65048 |
| [27] | H. Sato, Riemannian conjugate gradient method for complex singular value decomposition prob-lem, in: 53rd IEEE Conference on Decision and Control, IEEE, (2014), 5849-5854. |
| [28] | H. Sato, Joint singular value decomposition algorithm based on the Riemannian trust-region method, JSIAM Lett., 7 (2015), 13-16. · Zbl 07037336 |
| [29] | H. Sato, Riemannian Optimization and Its Applications, Springer Cham, 2021. · Zbl 1456.90001 |
| [30] | H. Sato and T. Iwai, A Riemannian optimization approach to the matrix singular value decom-position, SIAM J. Optim., 23:1 (2013), 188-212. · Zbl 1267.65070 |
| [31] | H. Sato, and T. Iwai, A complex singular value decomposition algorithm based on the Riemannian Newton method, in: 52nd IEEE Conference on Decision and Control, 2972-2978. IEEE, (2013). |
| [32] | K. Sato and H. Sato, Structure-preserving H 2 optimal model reduction based on the Riemannian trust-region method, IEEE Trans. Automat. Contr., 63:2 (2018), 505-512. · Zbl 1390.93190 |
| [33] | R. Scapaticci, O. Bucci, I. Catapano, and L. Crocco, Differential microwave imaging for brain stroke followup, Int. J. Antennas Propag., 2014 (2014), 1-11. |
| [34] | J.D. Shea, B.D.V. Veen, and S.C. Hagness, A TSVD analysis of microwave inverse scattering for breast imaging, IEEE Trans. Biomed. Eng., 59:4 (2011), 936-945. |
| [35] | F. Soldovieri, R. Solimene, and R. Pierri, A simple strategy to detect changes in through the wall imaging, Prog. Electromagn. Res. M, 7:3 (2009), 1-13. |
| [36] | R. Solimene, F. Ahmad, and F. Soldovieri, A novel CS-TSVD strategy to perform data reduction in linear inverse scattering problems, IEEE Geosci. Remote Sens. Lett., 9:5 (2012), 881-885. |
| [37] | R. Solimene, F. Soldovieri, A. Baratonia, and R. Pierri, Experimental validation of a linear inverse scattering TWI algorithm by a SF-CW radar, IEEE Antennas Wirel. Propag. Lett., 9 (2010), 506-509. |
| [38] | Z. Wen and W. Yin, A feasible method for optimization with orthogonality constraints, Math. Program., 142:1-2 (2013), 397-434. · Zbl 1281.49030 |
| [39] | P. Yang, Y.L. Jiang, and K.L. Xu, A trust-region method for H2 model reduction of bilinear systems on the Stiefel manifold, J. Franklin Inst., 356:4 (2019), 2258-2273. · Zbl 1409.93017 |
| [40] | J. Yu, F. Liu, L. Jiao, and X. He, Research on the reconstruction for bioluminescence tomography using truncated singular value decomposition method, J. Northwest Univ. Nat. Sci., 39:5 (2009), 755-760. |
| [41] | L.H. Zhang, Riemannian trust-region method for the maximal correlation problem, Numer. Funct. Anal. Optim., 33:3 (2012), 338-362. · Zbl 1296.62126 |
| [42] | X. Zhu, A Riemannian conjugate gradient method for optimization on the Stiefel manifold, Com-put. Optim. Appl., 67:1 (2017), 73-110. · Zbl 1401.90230 |
| [43] | H. Zhu, X. Zhang, D. Chu, and L.Z. Liao, Nonconvex and nonsmooth optimization with general-ized orthogonality constraints: An approximate augmented Lagrangian method, J. Sci. Comput., 72:1 (2017), 331-372. · Zbl 1373.65043 |
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.
