The ubiquitous Kronecker product. (English) Zbl 0966.65039
The author gives a tutorial in applications of Kronecker product computations including linear matrix equation problems, fast linear transforms, various optimization problems, and preconditioning with Kronecker products.
Reviewer: Gabriele Steidl (Mannheim)
MSC:
| 65F30 | Other matrix algorithms (MSC2010) |
| 15A69 | Multilinear algebra, tensor calculus |
| 15A24 | Matrix equations and identities |
| 65T50 | Numerical methods for discrete and fast Fourier transforms |
| 65K05 | Numerical mathematical programming methods |
Keywords:
Kronecker product; linear matrix equation; fast linear transforms; optimization; preconditioningSoftware:
Algorithm 705References:
| [1] | Andre, T. F.; Nowak, R. D.; Van Veen, B. D., Low rank estimation of higher order statistics, IEEE Trans. Signal Process., 45, 673-685 (1997) |
| [2] | Andrews, H. C.; Kane, J., Kronecker matrices, computer implementation, and generalized spectra, J. Assoc. Comput. Mach., 17, 260-268 (1970) · Zbl 0196.17203 |
| [3] | Barham, R. H.; Drane, W., An algorithm for least squares estimation of nonlinear parameters when some of the parameters are linear, Technometrics, 14, 757-766 (1972) · Zbl 0237.62025 |
| [4] | Barrlund, A., Efficient solution of constrained least squares problems with Kronecker product structure, SIAM J. Matrix Anal. Appl., 19, 154-160 (1998) · Zbl 0913.65033 |
| [5] | Bartels, R. H.; Stewart, G. W., Solution of the equation \(AX + XB = C\), Comm. ACM, 15, 820-826 (1972) · Zbl 1372.65121 |
| [6] | Brewer, J. W., Kronecker products and matrix calculus in system theory, IEEE Trans. Circuits Systems, 25, 772-781 (1978) · Zbl 0397.93009 |
| [7] | Calvetti, D.; Reichel, L., Application of ADI iterative methods to the image restoration of noisy images, SIAM J. Matrix Anal. Appl., 17, 165-174 (1996) · Zbl 0849.65101 |
| [8] | Chan, T. F., An optimal circulant preconditioner for Toeplitz systems, SIAM J. Sci. Statist. Comput., 9, 766-771 (1988) · Zbl 0646.65042 |
| [9] | Chan, T. F.; Olkin, J. A., Preconditioners for Toeplitz-block matrices, Numer. Algorithms, 6, 89-101 (1993) · Zbl 0793.65020 |
| [10] | Chan, R.; Jin, X.-Q., A family of block preconditioners for block systems, SIAM J. Sci. Statist. Comput., 13, 1218-1235 (1992) · Zbl 0760.65027 |
| [12] | Cullum, J.; Willoughby, R. A., Lanczos Algorithms for Large Sparse Symmetric Eigenvalue Computations, Vol. I (Theory), II (Programs) (1985), Birkhauser: Birkhauser Boston · Zbl 0574.65028 |
| [13] | Datta, K., The matrix equation XA − \( BX = R\) and its applications, Linear Algebra Appl., 109, 91-105 (1988) · Zbl 0656.15006 |
| [14] | Davio, M., Kronecker products and shuffle algebra, IEEE Trans. Comput., c-30, 116-125 (1981) · Zbl 0455.94050 |
| [15] | Davis, P.; Rabinowitz, P., Numerical Integration (1967), Blaisdell: Blaisdell Waltham, MA · Zbl 0154.17802 |
| [16] | de Boor, C., A Practical Guide to Splines (1978), Springer: Springer New York · Zbl 0406.41003 |
| [17] | de Boor, C., Efficient computer manipulation of tensor products, ACM Trans. Math. Software, 5, 173-182 (1979) · Zbl 0405.65011 |
| [18] | Dorr, F. W., The direct solution of the discrete poisson equation on a rectangle, SIAM Rev., 12, 248-263 (1970) · Zbl 0208.42403 |
| [19] | Dutt, A.; Rokhlin, V., Fast fourier transforms for nonequispaced data, SIAM J. Sci. Comput., 14, 1368-1398 (1993) · Zbl 0791.65108 |
| [21] | Fausett, D. W.; Fulton, C. T., Large least squares problems involving Kronecker products, SIAM J. Matrix Anal., 15, 219-227 (1994) · Zbl 0798.65059 |
| [22] | Fausett, D. W.; Fulton, C. T.; Hashish, H., Improved parallel QR method for large least squares problems involving Kronecker products, J. Comput. Appl. Math. (1997) · Zbl 0868.65019 |
| [24] | Gardiner, J.; Wette, M. R.; Laub, A. J.; Amato, J. J.; Moler, C. B., Algorithm 705: a FORTRAN-77 software package for solving the Sylvester matrix equation \(AXB^T + CXD^T = E\), ACM Trans. Math. Software, 18, 232-238 (1992) · Zbl 0893.65027 |
| [25] | Golub, G. H., Some modified eigenvalue problems, SIAM Rev., 15, 318-344 (1973) · Zbl 0254.65027 |
| [26] | Golub, G. H.; Luk, F.; Overton, M., A block Lanzcos method for computing the singular values and corresponding singular vectors of a matrix, ACM Trans. Math. Software, 7, 149-169 (1981) · Zbl 0466.65022 |
| [27] | Golub, G. H.; Nash, S.; Van Loan, C., A Hessenberg-Schur method for the matrix problem \(AX + XB = C\), IEEE Trans. Automat. Control, AC-24, 909-913 (1979) · Zbl 0421.65022 |
| [28] | Golub, G. H.; Pereya, V., The differentiation of pseudoinverses and nonlinear least squares problems whose variables separate, SIAM J. Numer. Anal., 10, 413-432 (1973) · Zbl 0258.65045 |
| [29] | Golub, G. H.; Van Loan, C., Matrix Computations (1996), Johns Hopkins University Press: Johns Hopkins University Press Baltimore, MD · Zbl 0865.65009 |
| [30] | Graham, A., Kronecker Products and Matrix Calculus with Applications (1981), Ellis Horwood: Ellis Horwood Chichester, England · Zbl 0497.26005 |
| [31] | Granata, J.; Conner, M.; Tolimieri, R., Recursive fast algorithms and the role of the tensor product, IEEE Trans. Signal Process., 40, 2921-2930 (1992) · Zbl 0771.65098 |
| [32] | Granata, J.; Conner, M.; Tolimieri, R., The tensor product: a mathematical programming language for FFTs and other fast DSP operations, IEEE SP Mag., 40-48 (January 1992) |
| [33] | Greengard, L.; Strain, J., The fast Gauss transform, SIAM J. Sci. Statist. Comput., 12, 79-94 (1991) · Zbl 0721.65089 |
| [35] | Henderson, H. V.; Pukelsheim, F.; Searle, S. R., On the history of the Kronecker product, Linear Multilinear Algebra, 14, 113-120 (1983) · Zbl 0517.15017 |
| [36] | Henderson, H. V.; Searle, S. R., The vec-permutation matrix, the vec operator and Kronecker products: a review, Linear Multilinear Algebra, 9, 271-288 (1981) · Zbl 0458.15006 |
| [37] | Horn, R. A.; Johnson, C. A., Topics in Matrix Analysis (1991), Cambridge University Press: Cambridge University Press New York · Zbl 0729.15001 |
| [39] | Huang, C-H.; Johnson, J. R.; Johnson, R. W., Multilinear algebra and parallel programming, J. Supercomput., 5, 189-217 (1991) · Zbl 0748.65042 |
| [40] | Jain, A. K., Fundamentals of Digital Image Processing (1989), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0744.68134 |
| [41] | Johnson, J.; Johnson, R. W.; Rodriguez, D.; Tolimieri, R., A methodology for designing, modifying, and implementing fourier transform algorithms on various architectures, Circuits Systems Signal Process., 9, 449-500 (1990) · Zbl 0716.65131 |
| [42] | Kagstrom, B., Perturbation analysis of the generalized Sylvester equation (AR−LB,DR−LE) = \((C,F)\), SIAM J. Matrix Anal. Appl., 15, 1045-1060 (1994) · Zbl 0805.65045 |
| [46] | Kaufman, L., A variable projection method for solving separable nonlinear least squares problems, BIT, 15, 49-57 (1975) · Zbl 0307.65019 |
| [47] | Klaus, B.; Horn, P., Robot Vision (1990), MIT Press: MIT Press Cambridge, MA |
| [49] | Lancaster, P., Explicit solution of linear matrix equations, SIAM Rev., 12, 544-566 (1970) · Zbl 0209.06502 |
| [50] | Moler, C. B.; Stewart, G. W., An algorithm for generalized matrix eigenvalue problems, SIAM J. Numer. Anal., 10, 241-256 (1973) · Zbl 0253.65019 |
| [52] | Nagy, J. G.; O’Leary, D. P., Restoring images degraded by spatially-variant blur, SIAM J. Sci. Comput., 19, 1063-1082 (1998) · Zbl 0919.65091 |
| [53] | Nowak, R. D., Penalized least squares estimation of higher order statistics, IEEE Trans. Signal Process., 46, 419-428 (1998) |
| [54] | Nowak, R. D.; Van Veen, B., Tensor product basis approximations for Volterra filters, IEEE Trans Signal Process., 44, 36-50 (1996) |
| [55] | Pereyra, V.; Scherer, G., Efficient computer manipulation of tensor products with applications to multidimensional approximation, Math. Comp., 27, 595-604 (1973) · Zbl 0282.65019 |
| [57] | Pollard, J. H., On the use of the direct matrix product in analyzing certain stochastic population models, Biometrika, 53, 397-415 (1966) · Zbl 0144.43901 |
| [58] | Rauhala, U. A., Introduction to array algebra, Photogrammetric Eng. Remote Sensing, 46, 2, 177-182 (1980) |
| [59] | Rauhala, U. A.; Davis, D.; Baker, K., Automated DTM validation and progressive sampling algorithm of finite element array relaxation, Photogrammetric Eng. Remote Sensing, 55, 449-465 (1989) |
| [60] | Regalia, P. A.; Mitra, S., Kronecker products, unitary matrices, and signal processing applications, SIAM Rev., 31, 586-613 (1989) · Zbl 0687.15010 |
| [61] | Seberry, J.; Zhang, X-M., Some orthogonal matrices constructed by strong Kronecker product multiplication, Austral. J. Combin., 7, 213-224 (1993) · Zbl 0779.05013 |
| [62] | Snay, R. A., Applicability of array algebra, Rev. Geophys. Space Phys., 16, 459-464 (1978) |
| [63] | Steeb, W-H., Matrix Calculus and Kronecker Product with Applications and C++ Programs (1997), World Scientific Publishing: World Scientific Publishing Singapore · Zbl 0952.15019 |
| [64] | Stenger, F., Kronecker product extensions of linear operators, SIAM J. Numer. Anal., 5, 422-435 (1968) · Zbl 0165.17801 |
| [66] | Strohmer, T., Numerical algorithms for discrete gabor expansions, (Feichtinger, H. G.; Strohmer, T., Gabor Analysis and Algorithms (1998), Birkhauser: Birkhauser Basel), 267-294 · Zbl 0890.42013 |
| [67] | Swami, A.; Mendel, J., Time and lag recursive computation of cumulants from a state-space model, IEEE Trans. Automat. Control, 35, 4-17 (1990) · Zbl 0712.93070 |
| [70] | Tolimieri, R.; An, M.; Lu, C., Algorithms for Discrete Fourier Transform and Convolution (1989), Springer: Springer New York · Zbl 0705.65105 |
| [71] | Vandenberghe, L.; Boyd, S., Semidefinite Programming, SIAM Rev., 38, 27-48 (1996) |
| [72] | Van Loan, C., Computational Frameworks for the Fast Fourier Transform (1992), SIAM Publications: SIAM Publications Philadelphia, PA · Zbl 0757.65154 |
| [73] | Van Loan, C.; Pitsianis, N. P., Approximation with Kronecker products, (Moonen, M. S.; Golub, G. H., Linear Algebra for Large Scale and Real Time Applications (1992), Kluwer Publications: Kluwer Publications Dordrecht), 293-314 · Zbl 0813.65078 |
| [74] | Vetter, W. J., Vector structures, solutions of linear matrix equations, Linear Algebra Appl., 10, 181-188 (1975) · Zbl 0307.15003 |
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.
