Double-variable trace maximization for extreme generalized singular quartets of a matrix pair: A geometric method
HTML articles powered by AMS MathViewer
- by Wei-Wei Xu and Zheng-Jian Bai;
- Math. Comp. 93 (2024), 2331-2359
- DOI: https://doi.org/10.1090/mcom/3936
- Published electronically: February 16, 2024
- HTML | PDF | Request permission
Abstract:
In this paper, we consider the problem of computing an arbitrary generalized singular value of a Grassman or real matrix pair and a triplet of associated generalized singular vectors. Based on the QR factorization, the problem is reformulated as two novel trace maximization problems, each of which has double variables with unitary constraints or orthogonal constraints. Theoretically, we show that the arbitrarily prescribed extreme generalized singular values and associated triplets of generalized singular vectors can be determined by the global solutions of the constrained trace optimization problems. Then we propose a geometric inexact Newton–conjugate gradient (Newton-CG) method for solving their equivalent trace minimization problems over the Riemannian manifold of all fixed-rank partial isometries. The proposed method can extract not only the prescribed extreme generalized singular values but also associated triplets of generalized singular vectors. Under some mild assumptions, we establish the global and quadratic convergence of the proposed method. Finally, numerical experiments on both synthetic and real data sets show the effectiveness and high accuracy of our method.References
- P.-A. Absil, R. Mahony, and R. Sepulchre, Optimization algorithms on matrix manifolds, Princeton University Press, Princeton, NJ, 2008. With a foreword by Paul Van Dooren. MR 2364186, DOI 10.1515/9781400830244
- P.-A. Absil and Jérôme Malick, Projection-like retractions on matrix manifolds, SIAM J. Optim. 22 (2012), no. 1, 135–158. MR 2902688, DOI 10.1137/100802529
- Kensuke Aihara and Hiroyuki Sato, A matrix-free implementation of Riemannian Newton’s method on the Stiefel manifold, Optim. Lett. 11 (2017), no. 8, 1729–1741. MR 3722247, DOI 10.1007/s11590-016-1090-9
- O. Alter, P. O. Brown, and D. Botstein, Generalized singular decomposition for comparative analysis of genome-scale expression data sets of two different organisms, Proc. Natl. Acad. Sci. USA 100 (2003), 3351–3356.
- Zhaojun Bai and James W. Demmel, Computing the generalized singular value decomposition, SIAM J. Sci. Comput. 14 (1993), no. 6, 1464–1486. MR 1241595, DOI 10.1137/0914085
- Zhaojun Bai and Hong Yuan Zha, A new preprocessing algorithm for the computation of the generalized singular value decomposition, SIAM J. Sci. Comput. 14 (1993), no. 4, 1007–1012. MR 1223284, DOI 10.1137/0914060
- Jesse L. Barlow, Error analysis and implementation aspects of deferred correction for equality constrained least squares problems, SIAM J. Numer. Anal. 25 (1988), no. 6, 1340–1358. MR 972458, DOI 10.1137/0725076
- Nicolas Boumal, An introduction to optimization on smooth manifolds, Cambridge University Press, Cambridge, 2023. MR 4533407, DOI 10.1017/9781009166164
- T. P. Cason, P.-A. Absil, and P. Van Dooren, Comparing two matrices by means of isometric projections, Numerical linear algebra in signals, systems and control, Lect. Notes Electr. Eng., vol. 80, Springer, Dordrecht, 2011, pp. 77–93. MR 3288252, DOI 10.1007/978-94-007-0602-6_{4}
- Z. Chen, Z. Ding, X. Dai, R. Schober, Asymptotic performance analysis of GSVD-NOMA systems with a large-scale antenna array, IEEE Trans. Wireless Commun. 18 (2019), 575–590.
- Zlatko Drmač, A tangent algorithm for computing the generalized singular value decomposition, SIAM J. Numer. Anal. 35 (1998), no. 5, 1804–1832. MR 1639946, DOI 10.1137/S0036142995289883
- Shmuel Friedland, A new approach to generalized singular value decomposition, SIAM J. Matrix Anal. Appl. 27 (2005), no. 2, 434–444. MR 2179681, DOI 10.1137/S0895479804439791
- Gene H. Golub and Charles F. Van Loan, Matrix computations, 4th ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 2013. MR 3024913, DOI 10.56021/9781421407944
- M. F. Hanif and Z. Ding, Robust power allocation in MIMO-NOMA systems, IEEE Wireless Commun. Lett. 8 (2019), 1541–1545.
- Per Christian Hansen, Rank-deficient and discrete ill-posed problems, SIAM Monographs on Mathematical Modeling and Computation, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1998. Numerical aspects of linear inversion. MR 1486577, DOI 10.1137/1.9780898719697
- Diyari Hassan, Soydan Redif, John G. McWhirter, and Sangarapillai Lambotharan, Polynomial GSVD beamforming for two-user frequency-selective MIMO channels, IEEE Trans. Signal Process. 69 (2021), 948–959. MR 4213392, DOI 10.1109/TSP.2021.3052040
- Roger A. Horn and Charles R. Johnson, Topics in matrix analysis, Cambridge University Press, Cambridge, 1991. MR 1091716, DOI 10.1017/CBO9780511840371
- Roger A. Horn and Charles R. Johnson, Matrix analysis, 2nd ed., Cambridge University Press, Cambridge, 2013. MR 2978290
- C. H. Lee, B. O. Alpert, P. Sankaranarayanan, and O. Alter, GSVD comparison of patient-matched normal and tumor aCGH profiles reveals global copy-number alterations predicting glioblastoma multiforme survival, PLoS ONE 7 (2012), e30098.
- L. Lu, G. Y. Li, A. L. Swindlehurst, A. Ashikhmin, and R. Zhang, An overview of massive MIMO: Benefits and challenges, IEEE J. Sel. Topics Signal Process. 8 (2014), 742–758.
- Jonathan H. Manton, Optimization algorithms exploiting unitary constraints, IEEE Trans. Signal Process. 50 (2002), no. 3, 635–650. MR 1895067, DOI 10.1109/78.984753
- L. Mirsky, A trace inequality of John von Neumann, Monatsh. Math. 79 (1975), no. 4, 303–306. MR 371930, DOI 10.1007/BF01647331
- C. C. Paige, The general linear model and the generalized singular value decomposition, Linear Algebra Appl. 70 (1985), 269–284. MR 808548, DOI 10.1016/0024-3795(85)90059-X
- C. C. Paige, Computing the generalized singular value decomposition, SIAM J. Sci. Statist. Comput. 7 (1986), no. 4, 1126–1146. MR 857786, DOI 10.1137/0907077
- C. C. Paige and M. A. Saunders, Towards a generalized singular value decomposition, SIAM J. Numer. Anal. 18 (1981), no. 3, 398–405. MR 615522, DOI 10.1137/0718026
- C. Rao, Z. Ding, and X. Dai, GSVD-based MIMO-NOMA security transmission, IEEE Wireless Commun. Lett. 10 (2021), 1484–1487.
- Hiroyuki Sato and Toshihiro Iwai, A Riemannian optimization approach to the matrix singular value decomposition, SIAM J. Optim. 23 (2013), no. 1, 188–212. MR 3033104, DOI 10.1137/120872887
- D. Senaratne and C. Tellambura, Generalized singular value decomposition for coordinated beamforming in MIMO systems, IEEE Global Telecommunications Conference GLOBECOM, 2010, pp. 1–6.
- D. Senaratne and C. Tellambura, GSVD beamforming for two-user MIMO downlink channel, IEEE Trans. Veh. Technol. 62 (2013), 2596–2606.
- J. M. Speiser and C. F. Van Loan, Signal processing computations using the generalized singular value decomposition, Proc. SPIE, Vol. 495, Real-Time Signal Processing VII, pp. 47–55, 1984.
- G. W. Stewart, Computing the $CS$ decomposition of a partitioned orthonormal matrix, Numer. Math. 40 (1982), no. 3, 297–306. MR 695598, DOI 10.1007/BF01396447
- Ji Guang Sun, Perturbation analysis for the generalized singular value problem, SIAM J. Numer. Anal. 20 (1983), no. 3, 611–625. MR 701101, DOI 10.1137/0720041
- M. Vaezi, W. Shin, and H. V. Poor, Optimal beamforming for Gaussian MIMO wiretap channels with two transmit antennas, IEEE Trans. Wireless Commun. 16 (2017), 6726–6735.
- Sabine Van Huffel and Joos Vandewalle, Analysis and properties of the generalized total least squares problem $AX\approx B$ when some or all columns in $A$ are subject to error, SIAM J. Matrix Anal. Appl. 10 (1989), no. 3, 294–315. MR 1003101, DOI 10.1137/0610023
- Charles F. Van Loan, Generalizing the singular value decomposition, SIAM J. Numer. Anal. 13 (1976), no. 1, 76–83. MR 411152, DOI 10.1137/0713009
- Charles Van Loan, On the method of weighting for equality-constrained least-squares problems, SIAM J. Numer. Anal. 22 (1985), no. 5, 851–864. MR 799116, DOI 10.1137/0722051
- Charles Van Loan, Computing the CS and the generalized singular value decompositions, Numer. Math. 46 (1985), no. 4, 479–491. MR 796639, DOI 10.1007/BF01389653
- Weiwei Xu, Wen Li, Lei Zhu, and Xueping Huang, The analytic solutions of a class of constrained matrix minimization and maximization problems with applications, SIAM J. Optim. 29 (2019), no. 2, 1657–1686. MR 3968259, DOI 10.1137/17M1140777
- Wei-Wei Xu, Michael K. Ng, and Zheng-Jian Bai, Geometric inexact Newton method for generalized singular values of Grassmann matrix pair, SIAM J. Matrix Anal. Appl. 43 (2022), no. 2, 535–560. MR 4403549, DOI 10.1137/20M1383720
- Zhi Zhao, Zheng-Jian Bai, and Xiao-Qing Jin, A Riemannian Newton algorithm for nonlinear eigenvalue problems, SIAM J. Matrix Anal. Appl. 36 (2015), no. 2, 752–774. MR 3355771, DOI 10.1137/140967994
- Guifang Zhou, Rank-constrained optimization: A Riemannian manifold approach, ProQuest LLC, Ann Arbor, MI, 2015. Thesis (Ph.D.)–The Florida State University. MR 3438909
Bibliographic Information
- Wei-Wei Xu
- Affiliation: School of Mathematics and Statistics, Nanjing University of Information Science and Technology, Nanjing 210044; The Peng Cheng Laboratory, Shenzhen 518055; and The Pazhou Laboratory (Huangpu), Guangzhou 510555, People’s Republic of China
- Email: wwxu@nuist.edu.cn
- Zheng-Jian Bai
- Affiliation: School of Mathematical Sciences, Xiamen University, Xiamen 361005, People’s Republic of China
- Email: zjbai@xmu.edu.cn
- Received by editor(s): March 20, 2023
- Received by editor(s) in revised form: September 19, 2023
- Published electronically: February 16, 2024
- Additional Notes: Conflict of interest statement. The authors declare that they have no conflict of interest.
The first author was partially supported by the major key project of Peng Cheng Laboratory under grant PCL2023AS1-2 and the National Natural Science Foundation of China grant 11971243. The second author was partially supported by the National Natural Science Foundation of China grant 12371382.
The second author is the corresponding author - © Copyright 2024 American Mathematical Society
- Journal: Math. Comp. 93 (2024), 2331-2359
- MSC (2020): Primary 49M37, 49Q99, 65F15, 90C30
- DOI: https://doi.org/10.1090/mcom/3936
- MathSciNet review: 4759377