Numerical strategies for recursive least squares solutions to the matrix equation \(AX = B\). (English) Zbl 1524.62381
Summary: The recursive solution to the Procrustes problem – with or without constraints – is thoroughly investigated. Given known matrices \(A\) and \(B\), the proposed solution minimizes the square of the Frobenius norm of the difference \(AX-B\) when rows or columns are added to \(A\) and \(B\). The proposed method is based on efficient strategies which reduce the computational cost by utilizing previous computations when new data are acquired. This is particularly useful in the iterative solution of an unbalanced orthogonal Procrustes problem. The results show that the computational efficiency of the proposed recursive algorithms is more significant when the dimensions of the matrices are large. This demonstrates the usefulness of the proposed algorithms in the presence of high-dimensional data sets. The practicality of the new method is demonstrated through an application in machine learning, namely feature extraction for image processing.
MSC:
| 62L12 | Sequential estimation |
| 15B10 | Orthogonal matrices |
| 15A23 | Factorization of matrices |
| 68U10 | Computing methodologies for image processing |
| 15A24 | Matrix equations and identities |
References:
| [1] | Anderson, E.; Bai, Z.; Dongarra, J., Generalized QR factorization and its applications, Linear Algebra Appl., 162-164(0), 243-271 (1992) · Zbl 0747.65022 |
| [2] | Bartels, R. H.; Stewart, G. W., Solution of the matrix equation AX + XB = C [F4], Commun. ACM, 15, 9, 820-826 (1972) · Zbl 1372.65121 |
| [3] | Brand, M., Fast low-rank modifications of the thin singular value decomposition, Linear Algebra Appl., 415, 1, 20-30 (2006) · Zbl 1088.65037 |
| [4] | Bunch, J. R.; Nielsen, C. P., Updating the singular value decomposition, Numer. Math., 31, 2, 111-129 (1978) · Zbl 0421.65028 |
| [5] | Cardoso, J. R.; Ziẹtak, K., On a sub-Stiefel procrustes problem arising in computer vision, Numer. Linear Algebra Appl., 22, 3, 523-547 (2015) · Zbl 1363.65031 |
| [6] | Chen, D., Cao, X., Wen, F., and Sun, J.. Blessing of dimensionality: High-dimensional feature and its efficient compression for face verification, in 2013 Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Portland, OR, USA, 2013, pp. 3025-3032. |
| [7] | Christensen, R.; Pearson, L. M.; Johnson, W., Case-deletion diagnostics for mixed models, Technometrics, 34, 1, 38-45 (1992) · Zbl 0761.62098 |
| [8] | Chu, K., Singular value and generalized singular value decompositions and the solution of linear matrix equations, Linear Algebra Appl., 88, 83-98 (1987) · Zbl 0612.15003 |
| [9] | Cook, R. D., Influential observations in linear regression, J. Am. Stat. Assoc., 74, 365, 169-174 (1979) · Zbl 0398.62057 |
| [10] | Eckart, C.; Young, G., The approximation of one matrix by another of lower rank, Psychometrika, 1, 3, 211-218 (1936) · JFM 62.1075.02 |
| [11] | Eldén, L.; Park, H., A procrustes problem on the Stiefel manifold, Numer. Math., 82, 4, 599-619 (1999) · Zbl 0934.65052 |
| [12] | Gong, Y.; Lazebnik, S.; Gordo, A.; Perronnin, F., Iterative quantization: A procrustean approach to learning binary codes for large-scale image retrieval, IEEE Trans. Pattern Anal. Mac. Intell., 35, 12, 2916-2929 (2013) |
| [13] | Gower, J. C., Generalized procrustes analysis, Psychometrika, 40, 1, 33-51 (1975) · Zbl 0305.62038 |
| [14] | Gower, J. C., Procrustes methods, Interdiscip. Rev. Comput. Stat., 2, 4, 503-508 (2010) |
| [15] | Green, B. F., The orthogonal approximation of an oblique structure in factor analysis, Psychometrika, 17, 4, 429-440 (1952) · Zbl 0049.37601 |
| [16] | Gu, M.; Eisenstat, S. C., Downdating the singular value decomposition, SIAM J. Matrix Anal. Appl., 16, 3, 793-810 (1995) · Zbl 0828.65039 |
| [17] | Hadjiantoni, S.; Kontoghiorghes, E. J., Estimating large-scale general linear and seemingly unrelated regressions models after deleting observations, Stat. Comput., 27, 2, 349-361 (2017) · Zbl 1505.62174 |
| [18] | Hadjiantoni, S.; Kontoghiorghes, E. J., A recursive three-stage least squares method for large-scale systems of simultaneous equations, Linear Algebra Appl., 536, 210-227 (2018) · Zbl 1393.65001 |
| [19] | Higham, N. J., The symmetric procrustes problem, BIT Numer. Math., 28, 1, 133-143 (1988) · Zbl 0641.65034 |
| [20] | Higham, N. J.; Strabić, N., Bounds for the distance to the nearest correlation matrix, SIAM J. Matrix Anal. Appl., 37, 3, 1088-1102 (2016) · Zbl 1347.65075 |
| [21] | Hua, D., On the symmetric solutions of linear matrix equations, Linear Algebra Appl., 131, 1-7 (1990) · Zbl 0712.15009 |
| [22] | Liao, A.-P.; Lei, Y., Least-squares solution with the minimum-norm for the matrix equation (AXB, GXH) = (C, D), Comput. Math. Appl., 50, 3, 539-549 (2005) · Zbl 1087.65040 |
| [23] | Liu, X., Hermitian and non-negative definite reflexive and anti-reflexive solutions to AX=B, Int. J. Comput. Math., 95, 8, 1666-1671 (2018) · Zbl 1499.15052 |
| [24] | Liu, Y. H., Ranks of least squares solutions of the matrix equation AXB=C, Comput. Math. Appl., 55, 6, 1270-1278 (2008) · Zbl 1157.15014 |
| [25] | Magnus, J. R.; Neudecker, H., Matrix Differential Calculus with Applications in Statistics and Econometrics (2007), Wiley: Wiley, Chichester, UK |
| [26] | Markley, F. L., Attitude determination using vector observations and the singular value decomposition, J. Astronaut. Sci., 36, 3, 245-258 (1988) |
| [27] | Meng, C.; Hu, X.; Zhang, L., The skew-symmetric orthogonal solutions of the matrix equation AX=B, Linear Algebra Appl., 402, 303-318 (2005) · Zbl 1128.15301 |
| [28] | Mosier, C. I., Determining a simple structure when loadings for certain tests are known, Psychometrika, 4, 2, 149-162 (1939) · JFM 65.0604.03 |
| [29] | Peng, X. Y.; Hu, X. Y.; Zhang, L., The reflexive and anti-reflexive solutions of the matrix equation AHXB=C, J. Comput. Appl. Math., 200, 2, 749-760 (2007) · Zbl 1115.15014 |
| [30] | Peng, Y.; Kong, W.; Yang, B., Orthogonal extreme learning machine for image classification, Neurocomputing, 266, 458-464 (2017) |
| [31] | Qiu, Y.; Wang, A., Solving balanced procrustes problem with some constraints by eigenvalue decomposition, J. Comput. Appl. Math., 233, 11, 2916-2924 (2010) · Zbl 1185.65065 |
| [32] | Rubin, M. B.; Solav, D., Unphysical properties of the rotation tensor estimated by least squares optimization with specific application to biomechanics, Int. J. Eng. Sci., 103, 11-18 (2016) · Zbl 1423.74629 |
| [33] | Schönemann, P. H., A generalized solution of the orthogonal procrustes problem, Psychometrika, 31, 1, 1-10 (1966) · Zbl 0147.19401 |
| [34] | Simoncini, V., Computational methods for linear matrix equations, SIAM Rev., 58, 3, 377-441 (2016) · Zbl 1386.65124 |
| [35] | Snyders, J.; Zakai, M., On nonnegative solutions of the equation \(####\), SIAM J. Appl. Math., 18, 3, 704-714 (1970) · Zbl 0203.33401 |
| [36] | Sun, Y.; Vandenberghe, L., Decomposition methods for sparse matrix nearness problems, SIAM J. Matrix Anal. Appl., 36, 4, 1691-1717 (2015) · Zbl 1342.90128 |
| [37] | Tai, Y.; Yang, J.; Zhang, Y.; Luo, L.; Qian, J.; Chen, Y., Face recognition with pose variations and misalignment via orthogonal procrustes regression, IEEE Trans. Image Process., 25, 6, 2673-2683 (2016) · Zbl 1408.94628 |
| [38] | Tian, Y.; Takane, Y., On consistency, natural restrictions and estimability under classical and extended growth curve models, J. Stat. Plan. Inference, 139, 7, 2445-2458 (2009) · Zbl 1160.62051 |
| [39] | Tropp, J. A.; Yurtsever, A.; Udell, M.; Cevher, V., Practical sketching algorithms for low-rank matrix approximation, SIAM J. Matrix Anal. Appl., 38, 4, 1454-1485 (2017) · Zbl 1379.65026 |
| [40] | Vetter, W. J., Vector structures and solutions of linear matrix equations, Linear Algebra Appl., 10, 2, 181-188 (1975) · Zbl 0307.15003 |
| [41] | Wahba, G., A least squares estimate of satellite attitude, SIAM Rev., 7, 3, 409-409 (1965) |
| [42] | Young, P. C., Recursive Estimation and Time-Series Analysis (2011), Springer-Verlag: Springer-Verlag, Berlin Heidelberg · Zbl 1266.62072 |
| [43] | Zhao, H.; Wang, Z.; Nie, F., Orthogonal least squares regression for feature extraction, Neurocomputing, 216, 200-207 (2016) |
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.
