On optimizing the sum of the Rayleigh quotient and the generalized Rayleigh quotient on the unit sphere
详细信息 查看全文
- 作者：Lei-Hong Zhang (1)
- 关键词：Rayleigh quotient ; The generalized Rayleigh quotient ; The nonlinear eigenvalue problem ; Trust ; region method ; Linear discriminant analysis
- 刊名：Computational Optimization and Applications
- 出版年：2013
- 出版时间：January 2013
- 年：2013
- 卷：54
- 期：1
- 页码：111-139
- 全文大小：2983KB
- 参考文献：1. Abraham, R., Marsden, J.E., Ratiu, T.: Manifolds, Tensor Analysis, and Applications, 2nd edn. Applied Mathematical Sciences, vol. 75. Springer, New York (1988) CrossRef
2. Absil, P.-A., Gallivan, K.A.: Accelerated line-search and trust-region methods. SIAM J. Numer. Anal. 47, 997-018 (2009) CrossRef
3. Absil, P.-A., Baker, C.G., Gallivan, K.A.: A truncated-CG style method for symmetric generalized eigenvalue problems. J. Comput. Appl. Math. 189, 274-85 (2006) CrossRef
4. Absil, P.-A., Baker, C.G., Gallivan, K.A.: Trust-region methods on Riemannian manifolds. Found. Comput. Math. 7, 303-30 (2007) CrossRef
5. Absil, P.-A., Mahony, R., Sepulchre, R.: Optimization Algorithms on Matrix Manifolds. Princeton University Press, Princeton (2008)
6. Adler, R.L., Dedieu, J.-P., Margulies, J.Y., Martens, M., Shub, M.: Newton’s method on Riemannian manifolds and a geometric model for the human spine. IMA J. Numer. Anal. 22, 359-90 (2002) CrossRef
7. Bishop, C.M.: Pattern Recognition and Machine Learning. Springer, Berlin (2006)
8. Bonnans, J.F., Shapiro, A.: Perturbation Analysis of Optimization Problems. Springer, New York (2000)
9. Chu, M.T., Driessel, K.R.: The projected gradient method for least squares matrix approximations with spectral constraints. SIAM J. Numer. Anal. 27, 1050-060 (1990) CrossRef
10. Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust-Region Methods. SIAM, Philadelphia (2000) CrossRef
11. Duchene, L., Leclerq, S.: An optimal transformation for discriminant and principal component analysis. IEEE Trans. Pattern Anal. Mach. Intell. 10, 978-83 (1988) CrossRef
12. Dundar, M.M., Fung, G., Bi, J., Sandilya, S., Rao, B.: Sparse fisher discriminant analysis for computer aided detection. In: Proceedings of SIAM International Conference on Data Mining (2005)
13. Edelman, A., Arias, T.A., Smith, S.T.: The geometry of algorithms with orthogonality constraints. SIAM J. Matrix Anal. Appl. 20, 303-53 (1998) CrossRef
14. Fan, J., Li, R.: Variable selection via nonconcave penalized likelihood and its oracle properties. J. Am. Stat. Assoc. 96, 1348-360 (2001) CrossRef
15. Fisher, R.A.: The use of multiple measurements in taxonomic problems. Annu. Eugen. 7, 179-88 (1936)
16. Foley, D., Sammon, J.: An optimal set of discriminant vectors. IEEE Trans. Comput. 24, 281-89 (1975) CrossRef
17. Friedman, J.: Regularized discriminant analysis. J. Am. Stat. Assoc. 84, 165-75 (1989) CrossRef
18. Fukunaga, K.: Introduction to Statistical Pattern Classification. Academic Press, San Diego (1990)
19. Fung, E., Ng, M.: On sparse fisher discriminant method for microarray data analysis. Bioinformation 2, 230-34 (2007) CrossRef
20. Gao, X.B., Golub, G.H., Liao, L.-Z.: Continuous methods for symmetric generalized eigenvalue problems. Linear Algebra Appl. 428, 676-96 (2008) CrossRef
21. Golub, G.H., Liao, L.-Z.: Continuous methods for extreme and interior eigenvalue problems. Linear Algebra Appl. 415, 31-1 (2006) CrossRef
22. Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. Johns Hopkins University Press, Baltimore (1996)
23. Helmke, U., Moore, J.B.: Optimization and Dynamical Systems. Springer, London (1994) CrossRef
24. Howland, P., Jeon, M., Park, H.: Structure preserving dimension reduction for clustered text data based on the generalized singular value decomposition. SIAM J. Matrix Anal. Appl. 25, 165-79 (2003) CrossRef
25. Hunter, D.R., Li, R.: Variable selection using MM algorithms. Ann. Stat. 33, 1617-642 (2005) CrossRef
26. Kelley, C.T.: Iterative Methods for Linear and Nonlinear Equations. SIAM, Philadelphia (1995) CrossRef
27. Lehoucq, R.B., Sorensen, D.C.: Deflation techniques for an implicitly re-started Arnoldi iteration. SIAM J. Matrix Anal. Appl. 17, 789-21 (1996) CrossRef
28. Lehoucq, R.B., Sorensen, D.C., Yang, C.: ARPACK Users-Guide: Solution of Large-Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods. SIAM, Philadelphia (1998) CrossRef
29. Ng, M.K., Liao, L.-Z., Zhang, L.-H.: On sparse linear discriminant analysis for high-dimensional data. Numer. Linear Algebra Appl. 18, 223-35 (2011) CrossRef
30. Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer, New York (2006)
31. Parlett, B.N.: The Rayleigh quotient iteration and some generalizations for nonnormal matrices. Math. Comput. 28, 679-93 (1974) CrossRef
32. Parlett, B.N.: The Symmetric Eigenvalue Problem. Classics Appl. Math., vol. 20. SIAM, Philadelphia (1998) CrossRef
33. Primolevo, G., Simeone, O., Spagnolini, U.: Towards a joint optimization of scheduling and beamforming for MIMO downlink. In: IEEE Ninth International Symposium on Spread Spectrum Techniques and Applications, pp. 493-97 (2006) CrossRef
34. Saad, Y.: Numerical Methods for Large Eigenvalue Problems. Algorithms and Architectures for Advanced Scientific Computing. Manchester University Press, Manchester (1992)
35. Steihaug, T.: The conjugate gradient method and trust regions in large scale optimization. SIAM J. Numer. Anal. 20, 626-37 (1983) CrossRef
36. Toint, P.L.: Towards an efficient sparsity exploiting newton method for minimization. In: Duff, I.S. (ed.) Sparse Matrices and Their Uses, pp. 57-8. Academic Press, London (1981)
37. Wu, M.C., Zhang, L.S., Wang, Z.X., Christiani, D.C., Lin, X.H.: Sparse linear discriminant analysis for simultaneous testing for the significance of a gene set/pathway and gene selection. Bioinformatics 25, 1145-151 (2009) CrossRef
38. Ye, J.-P., Janardan, R., Park, C., Park, H.: An optimization criterion for generalized discriminant analysis on undersampled problems. IEEE Trans. Pattern Anal. Mach. Intell. 26, 982-94 (2004) CrossRef
39. Zhang, L.-H.: Uncorrected trace ratio LDA for undersampled problems. Pattern Recognit. Lett. 32, 476-84 (2011) CrossRef
40. Zhang, L.-H., Liao, L.-Z., Ng, M.K.: Fast algorithms for the generalized Foley-Sammon discriminant analysis. SIAM J. Matrix Anal. Appl. 31, 1584-605 (2010) CrossRef - 作者单位：Lei-Hong Zhang (1)
1. Department of Applied Mathematics, Shanghai University of Finance and Economics, 777 Guoding Road, Shanghai, 200433, People’s Republic of China - ISSN：1573-2894
文摘
Given symmetric matrices B,D∈? n×n and a symmetric positive definite matrix W∈? n×n , maximizing the sum of the Rayleigh quotient x ⊿/sup> D x and the generalized Rayleigh quotient $\frac{\mathbf{x}^{\top}B \mathbf{x}}{\vphantom{\mathrm{I}^{\mathrm{I}}}\mathbf{x}^{\top}W\mathbf{x}}$ on the unit sphere not only is of mathematical interest in its own right, but also finds applications in practice. In this paper, we first present a real world application arising from the sparse Fisher discriminant analysis. To tackle this problem, our first effort is to characterize the local and global maxima by investigating the optimality conditions. Our results reveal that finding the global solution is closely related with a special extreme nonlinear eigenvalue problem, and in the special case D=μW?(μ>0), the set of the global solutions is essentially an eigenspace corresponding to the largest eigenvalue of a specially-defined matrix. The characterization of the global solution not only sheds some lights on the maximization problem, but motives a starting point strategy to obtain the global maximizer for any monotonically convergent iteration. Our second part then realizes the Riemannian trust-region method of Absil, Baker and Gallivan (Found. Comput. Math. 7:303-30, 2007) into a practical algorithm to solve this problem, which enjoys the nice convergence properties: global convergence and local superlinear convergence. Preliminary numerical tests are carried out and empirical evaluation of its performance is reported.