Structured low-rank approximation and its applications. (English) Zbl 1283.93061
Summary: Fitting data by a bounded complexity linear model is equivalent to low-rank approximation of a matrix constructed from the data. The data matrix being Hankel structured is equivalent to the existence of a linear time-invariant system that fits the data and the rank constraint is related to a bound on the model complexity. In the special case of fitting by a static model, the data matrix and its low-rank approximation are unstructured.
We outline applications in system theory (approximate realization, model reduction, output error, and errors-in-variables identification), signal processing (harmonic retrieval, sum-of-damped exponentials, and finite impulse response modeling), and computer algebra (approximate common divisor). Algorithms based on heuristics and local optimization methods are presented. Generalizations of the low-rank approximation problem result from different approximation criteria (e.g., weighted norm) and constraints on the data matrix (e.g., nonnegativity). Related problems are rank minimization and structured pseudospectra.
We outline applications in system theory (approximate realization, model reduction, output error, and errors-in-variables identification), signal processing (harmonic retrieval, sum-of-damped exponentials, and finite impulse response modeling), and computer algebra (approximate common divisor). Algorithms based on heuristics and local optimization methods are presented. Generalizations of the low-rank approximation problem result from different approximation criteria (e.g., weighted norm) and constraints on the data matrix (e.g., nonnegativity). Related problems are rank minimization and structured pseudospectra.
MSC:
| 93B11 | System structure simplification |
| 93B30 | System identification |
| 93B40 | Computational methods in systems theory (MSC2010) |
Keywords:
low-rank approximation; total least squares; system identification; errors-in-variables modeling; behaviorsReferences:
| [1] | Beck, A.; Ben-Tal, A., A global solution for the structured total least squares problem with block circulant matrices, SIAM Journal of Matrix Analysis and Applications, 27, 1, 238-255 (2006) · Zbl 1106.65034 |
| [2] | Berman, A.; Shaked-Monderer, N., Completely positive matrices (2003), World Scientific: World Scientific Singapore · Zbl 1030.15022 |
| [3] | Boyd, S.; Vandenberghe, L., Convex optimization (2004), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1058.90049 |
| [4] | Chandrasekaran, S.; Gu, M.; Sayed, A., A stable and efficient algorithm for the indefinite linear least-squares problem, SIAM Journal of Matrix Analysis and Applications, 20, 2, 354-362 (1998) · Zbl 0920.65024 |
| [5] | De Moor, B., Structured total least squares and \(L_2\) approximation problems, Linear Algebra and Its Applications, 188-189, 163-207 (1993) · Zbl 0781.65028 |
| [6] | De Moor, B., Total least squares for affinely structured matrices and the noisy realization problem, IEEE Transactions on Signal Processing, 42, 11, 3104-3113 (1994) |
| [7] | De Moor B. (2005), Dalsy: Database for the identification of systems\( \langle\) www.esat.kuleuven.ac.be/sista.daisy/\( \rangle \); De Moor B. (2005), Dalsy: Database for the identification of systems\( \langle\) www.esat.kuleuven.ac.be/sista.daisy/\( \rangle \) |
| [8] | Degroat, R.; Dowling, E., The data least squares problem and channel equalization, IEEE Transactions on Signal Processing, 41, 407-411 (1991) |
| [9] | Eckart, G.; Young, G., The approximation of one matrix by another of lower rank, Psychometrika, 1, 211-218 (1936) · JFM 62.1075.02 |
| [10] | Fazel, M. (2002). Matrix rank minimization with applications; Fazel, M. (2002). Matrix rank minimization with applications |
| [11] | Golub, G.; Pereyra, V., Separable nonlinear least squares: The variable projection method and its applications, Institute of Physics, Inverse Problems, 19, 1-26 (2003) · Zbl 1022.65014 |
| [12] | Golub, G.; Van Loan, C., An analysis of the total least squares problem, SIAM Journal on Numerical Analysis, 17, 883-893 (1980) · Zbl 0468.65011 |
| [13] | Graillat, S., A note on structured pseudospectra, Journal of Computational and Applied Mathematics, 191, 68-76 (2006) · Zbl 1097.15010 |
| [14] | Ho, B. L.; Kalman, R. E., Effective construction of linear state-variable models from input/output functions, Regelungstechnik, 14, 12, 545-592 (1966) · Zbl 0145.12701 |
| [15] | Kukush, A.; Markovsky, I.; Van Huffel, S., Consistency of the structured total least squares estimator in a multivariate errors-in-variables model, Journal of Statistical Planning and Inference, 133, 2, 315-358 (2005) · Zbl 1213.62097 |
| [16] | Kung, S. (1978). A new identification method and model reduction algorithm via singular value decomposition. In Proceedings of theth Asilomar conference on circuitssystemsand computers; Kung, S. (1978). A new identification method and model reduction algorithm via singular value decomposition. In Proceedings of theth Asilomar conference on circuitssystemsand computers |
| [17] | Lee, D.; Seung, H., Learning the parts of objects by non-negative matrix factorization, Nature, 401, 788-791 (1999) · Zbl 1369.68285 |
| [18] | Ljung, L., System identification: Theory for the user (1999), Prentice-Hall: Prentice-Hall Upper Saddle River, NJ |
| [19] | Manton, J.; Mahony, R.; Hua, Y., The geometry of weighted low-rank approximations, IEEE Transactions on Signal Processing, 51, 2, 500-514 (2003) · Zbl 1369.94221 |
| [20] | Markovsky, I.; Van Huffel, S., High-performance numerical algorithms and software for structured total least squares, Journal of Computational and Applied Mathematics, 180, 2, 311-331 (2005) · Zbl 1070.65025 |
| [21] | Markovsky, I.; Van Huffel, S., Left vs right representations for solving weighted low rank approximation problems, Linear Algebra and Its Applications, 422, 540-552 (2007) · Zbl 1115.65047 |
| [22] | Markovsky, I.; Van Huffel, S.; Pintelon, R., Block-Toeplitz/Hankel structured total least squares, SIAM Journal of Matrix Analysis and Applications, 26, 4, 1083-1099 (2005) · Zbl 1085.65035 |
| [23] | Markovsky, I., Willems, J. C., De Moor, B. (2006). Comparison of identification algorithms on the database for system identification DAISY. In Proceedings of the 17th symposium on mathematical theory of networks and systems; Markovsky, I., Willems, J. C., De Moor, B. (2006). Comparison of identification algorithms on the database for system identification DAISY. In Proceedings of the 17th symposium on mathematical theory of networks and systems |
| [24] | Markovsky, I.; Willems, J. C.; Rapisarda, P.; De Moor, B., Algorithms for deterministic balanced subspace identification, Automatica, 41, 5, 755-766 (2005) · Zbl 1093.93006 |
| [25] | Markovsky, I., Willems, J. C., Van Huffel, S., De Moor, B. (2006). Exact and approximate modeling of linear systems: A behavioral approach. In Monographs on mathematical modeling and computation; Markovsky, I., Willems, J. C., Van Huffel, S., De Moor, B. (2006). Exact and approximate modeling of linear systems: A behavioral approach. In Monographs on mathematical modeling and computation · Zbl 1116.93002 |
| [26] | Markovsky, I.; Willems, J. C.; Van Huffel, S.; De Moor, B.; Pintelon, R., Application of structured total least squares for system identification and model reduction, IEEE Transactions on Automatic Control, 50, 10, 1490-1500 (2005) · Zbl 1365.93527 |
| [27] | Pintelon, R.; Schoukens, J., System identification: A frequency domain approach (2001), IEEE Press: IEEE Press Piscataway, NJ · Zbl 0970.93514 |
| [28] | Polderman, J.; Willems, J. C., Introduction to mathematical systems theory (1998), Springer: Springer New York |
| [29] | Roorda, B., Algorithms for global total least squares modelling of finite multivariable time series, Automatica, 31, 3, 391-404 (1995) · Zbl 0824.93063 |
| [30] | Roorda, B.; Heij, C., Global total least squares modeling of multivariate time series, IEEE Transactions on Automatic Control, 40, 1, 50-63 (1995) · Zbl 0819.93008 |
| [31] | Rump, S., Structured perturbations part I: Normwise distances, SIAM Journal of Matrix Analysis and Applications, 25, 1-30 (2003) · Zbl 1061.15004 |
| [32] | Söderström, T., Errors-in-variables methods in system identification, Automatica, 43, 939-958 (2007) · Zbl 1193.93090 |
| [33] | Söderström, T.; Stoica, P., System identification (1989), Prentice-Hall: Prentice-Hall NJ · Zbl 0714.93056 |
| [34] | Trefethen, L. N.; Embree, M., Spectra and pseudospectra: The behavior of nonnormal matrices and operators (1999), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 1085.15009 |
| [35] | Van Huffel, S.; Van dewalle, J., The total least squares problem: Computational aspects and analysis (1991), SIAM: SIAM Philadelphia · Zbl 0789.62054 |
| [36] | Van Overschee, P.; De Moor, B., Subspace identification for linear systems: theory, implementation, applications (1996), Kluwer: Kluwer Boston · Zbl 0888.93001 |
| [37] | Vanluyten, B., Willems, J. C., De Moor, B. (2005). Model reduction of systems with symmetries. In Proceedings of the 44th IEEE conference on decision and control; Vanluyten, B., Willems, J. C., De Moor, B. (2005). Model reduction of systems with symmetries. In Proceedings of the 44th IEEE conference on decision and control |
| [38] | Vanluyten, B., Willems, J. C., & De Moor, B. (2006). Matrix factorization and stochastic state representations. In Proceedings of the 45th IEEE conference on decision and control; Vanluyten, B., Willems, J. C., & De Moor, B. (2006). Matrix factorization and stochastic state representations. In Proceedings of the 45th IEEE conference on decision and control |
| [39] | Wentzell, P.; Andrews, D.; Hamilton, D.; Faber, K.; Kowalski, B., Maximum likelihood principle component analysis, Journal of Chemometrics, 11, 339-366 (1997) |
| [40] | Willems, J. C. (1986, 1987). From time series to linear system—Part I. Finite dimensional linear time invariant systems, Part II. Exact modelling, Part III. Approximate modelling. Automatica2223; Willems, J. C. (1986, 1987). From time series to linear system—Part I. Finite dimensional linear time invariant systems, Part II. Exact modelling, Part III. Approximate modelling. Automatica2223 · Zbl 0604.62090 |
| [41] | Willems, J. C., Paradigms and puzzles in the theory of dynamical systems, IEEE Transactions on Automatic Control, 36, 3, 259-294 (1991) · Zbl 0737.93004 |
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.
