×

Setting up alternating least squares and iterative majorization algorithms for solving various matrix optimization problems. (English) Zbl 1018.65074

Summary: A general procedure is described for setting up monotonically convergent algorithms to solve some general matrix optimization problems, if desired, subject to a wide variety of constraints. An overview is given of a number of ready-made building blocks (derived in earlier publications) from which concrete algorithms are set-up with little effort. These algorithms are based on alternating least squares (block relaxation) and iterative majorization. It is demonstrated how the construction of an algorithm for a particular problem that falls in one of the classes of optimization problems under study, reduces to a simple combination of tools. Also, a procedure is reviewed for setting up a weighted least squares algorithm for any problem for which an unweighted least squares solution is available. All procedures are illustrated by means of examples.

MSC:

65K05 Numerical mathematical programming methods
90C20 Quadratic programming
65F20 Numerical solutions to overdetermined systems, pseudoinverses
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Andrews, D. F.; Herzberg, A. M.: Data. (1985) · Zbl 0567.62002
[2] Cliff, N.: Orthogonal rotation to congruence. Psychometrika 31, 33-42 (1966)
[3] De Leeuw, J.: Convergence of the majorization method for multidimensional scaling. J. classification 5, 163-180 (1988) · Zbl 0692.62056
[4] De Leeuw, J.: Block relaxation algorithms in statistics. Information systems and data analysis, 308-325 (1994) · Zbl 0829.65144
[5] Deutsch, F.: Best approximation in inner product spaces. (2001) · Zbl 0980.41025
[6] Groenen, P. J. F.: The majorization approach to multidimensional scaling: some problems and extensions. (1993) · Zbl 0898.62080
[7] Groenen, P.J.F., Heiser, W.J., 1991. An improved tunnelling function for finding a decreasing series of local minima in MDS. Research report RR-91-06, Department of Data Theory, Leiden.
[8] Heiser, W. J.: Convergent computation by iterative majorization: theory and applications in multidimensional data analysis. Recent advances in descriptive multivariate analysis, 157-189 (1995)
[9] Keller, J. B.: Factorization of matrices by least squares. Biometrika 49, 239-242 (1962) · Zbl 0106.34402
[10] Kiers, H. A. L.: Majorization as a tool for optimizing a class of matrix functions. Psychometrika 55, 417-428 (1990) · Zbl 0733.62067
[11] Kiers, H. A. L.: An alternating least squares algorithm for PARAFAC2 and DEDICOM3. Comput. statist. Data anal. 16, 103-118 (1993) · Zbl 0875.62260
[12] Kiers, H. A. L.: Maximization of sums of quotients of quadratic forms and some generalizations. Psychometrika 60, 221-245 (1995) · Zbl 0833.62052
[13] Kiers, H. A. L.: Discrimination by means of components that are orthogonal in the data space. J. chemometrics 11, 533-545 (1997)
[14] Kiers, H. A. L.: Weighted least squares Fitting using iterative ordinary least squares algorithms. Psychometrika 62, 251-266 (1997) · Zbl 0873.62058
[15] Kiers, H. A. L.; Berge, J. M. F. Ten: Minimization of a class of matrix trace functions by means of refined majorization. Psychometrika 57, 371-382 (1992) · Zbl 0782.62067
[16] Kiers, H. A. L.; Berge, J. M. F. Ten: Hierarchical relations between methods for simultaneous component analysis and a technique for rotation to a simple simultaneous structure. British J. Math. statist. Psych. 47, 109-126 (1994) · Zbl 0825.62512
[17] Krzanowski, W.: Orthogonal canonical variates for discrimination and classification. J. chemometrics 9, 509-520 (1995)
[18] Lange, K.; Hunter, D. R.; Yang, I.: Optimization transfer using surrogate objective functions. Journal of computational and graphical statistics 9, 1-20 (2000)
[19] Lawson, C. L.; Hanson, R. J.: Solving least squares problems. (1974) · Zbl 0860.65028
[20] Ortega, J. M.: Numerical analysis: A second course. (1990) · Zbl 0701.65002
[21] Penrose, R.: On best approximate solutions of linear matrix equations. Proceedings of the Cambridge philosophical society 52, 17-19 (1956) · Zbl 0070.12501
[22] Stewart, G. W.; Sun, J.: Matrix perturbation theory. (1990) · Zbl 0706.65013
[23] Berge, J. M. F. Ten: Least squares optimization in multivariate analysis. (1993)
[24] Berge, J. M. F. Ten; Nevels, K.: A general solution to mosier’s oblique procrustes problem. Psychometrika 42, 593-600 (1977) · Zbl 0387.62086
[25] Von Neumann, J., 1933. Functional Operators, Annals of Mathematics Studies No. 22. Princeton University Press, 1950, reprint of mimeographed lecture notes first distributed in 1933.
[26] Von Neumann, J.: Some matrix inequalities and metrization of matrix space. Tomsk university review 1, 286-300 (1937) · JFM 63.0037.03
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.