The Ubiquitous Kronecker Product: Algebra and Applications
The Kronecker product is a matrix operation with rich algebraic properties that support fast algorithms in various scientific computing fields. This article explores its role in signal processing, image processing, quantum computing, and more, highlighting its importance in sparse factorizations and high-dimensional problems. Basic properties and applications are discussed, emphasizing the structure and factorizations inherited by Kronecker products.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
The ubiquitous Kronecker product Charles F. Van Loan Journal of Computational and Applied Mathematics 123 pp. 85-100 (2000) Department of Computer Science, Cornell University, Ithaca, New York 14853, USA Presenter: Syuan- Zong Ciou Date:2015/10/20
Abstract The Kronecker product has a rich and very pleasing algebra that supports a wide range of fast, elegant, and practical algorithms. Several trends in scientific computing suggest that this important matrix operation will have an increasingly greater role to play in the future. First, the application areas where Kronecker products abound are all thriving. These include signal processing, image processing, semidefinite programming, and quantum computing.
Abstract Second, sparse factorizations and Kronecker products are proving to be a very effective way to look at fast linear transforms. Researchers have taken the Kronecker methodology as developed for the fast Fourier transform and used it to build exciting alternatives. Third, as computers get more powerful, researchers are more willing to entertain problems of high dimension and this leads to Kronecker products whenever low-dimension techniques are tensored together.
Basic properties 1 4 7 2 5 8 6 15 24 3 6 9 2 8 4 10 16 8 20 32 6 12 18 12 24 36 1 4 7 2 5 8 3 6 9 14 4 16 28 1 3 2 4 = 3 9 12 21 18 27
Basic properties The basicproperties of the Kronecker product are quite predictable: ? ? ? = ? ? ? ? ? ? ? ? ? ? 1 ? 1 = ?? ?? = ?? 1 ?? 1= ? B.C are invertible ( ? ? ) 1= ? 1 ? 1 ( ? ? )?= ?? ??
Basic properties ? ? ? ? However, ? ? and ? ? are related by a permutation. The permutation involved is in fact the ??????? ? ?????. If ?,? and ? = ??, then (p,q) perfect shuffle is r r matrix. 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 ??( 1 ? ?,:) ??( 2 ? ?,:) ??( ? ? ?,:) ??,?= ?2,3= ? ? ? = ??1,?2( ? ? )??1,?2 ? ??? ? ?1 ?1, ? ?2 ?2
Basic properties Particularly important in computational work are the issues theat surround the exploitation pf structure and the application of matrix factorizations. By and large, Kronecker product inherits structure from its factors.
Basic properties With respect to factorizations, the LU-with-partial-pivoting, Cholesky, and QR factorizations of ? ? merely require the corresponding factorizations of B and C. ????? ????? = ( ?? ??)?(?? ??)(?? ??) ? ? = ?? ?? T= GB GC GB GCT T GCGC ? ? = GBGB B C = ???? ???? = ?? ?? ?? ?? The same is true for the singular value and Schur decompositions if we disregard ordering issues.
Basic properties In kronecker product work, matrices are sometimes regarded as vectors and vectors are sometimes made into into matrices. ? =? ? ? ????= ? ? ? ??? ? = ???(?) ? ? ? ? ? ??? ? = ? ? ? = ? ?? ?,? ? ?,then x can be obtained in ?(?3)flops
Matrix equations To researchers in numerical linear algebra, the most familiar problem, where Kronecker products arise is the Sylvester matrix equation problem. ? ? ?,? ? ?,??? ? ? ???? ? ? ??? ? ?? ?? + ???= ? To find X is equivalent to solving the mn mn linear system ?? ? + ? ?? ??? ? = ???(?)
The nearest Kronecker product problem Suppose ? ? ?is given with ? = ?1?2,? = ?1?2. For these integer factorizations the NKP problem inbolves minimizing ? ?,? = ||? ? ?||? ? ?1 ?1,? ?2 ?2 ???( ?11)? ???( ?21)? ???( ?31)? ???( ?12)? ???( ?22)? ???( ?32)? ? = ? ?,? = ? ??? ? ???(?)? ?
1 5 9 2 6 3 7 4 8 12 16 20 24 1 3 5 2 4 6 1 2 4 10 14 18 22 11 15 19 23 ? ?,? = 13 17 21 3 ? 2 4 6 8 14 16 22 24 1 3 9 11 17 19 5 7 1 3 5 2 4 6 10 12 18 20 13 15 21 23 ? ?,? = 1 3 2 4 ?
The nearest Kronecker product problem The act of minimizing ? is wquivalent to finding a nearest rank-1 matrix to ? . The nearest rank-1 matrix problem has a SVD solution. ?? ? ? = Set ??? ???? = ? = ? ? ? + ? 1 ?1,: If ? has rank r, then ?1? :,1 ??? ???? = = ???(???)?, ? = 1:?,? = 1:? . ?1? :,1 ? ? = ???? ?? ?=1
