Factorization methods
Many forms of matrix factorization such as eigenvalue decomposition, LU factorization, Cholesky factorization etc., can be computed efficiently. The decomposition of the Kronecker product is the Kronecker product of the decompositions. We have overloaded some of the factorization functions from LinearAlgebra to compute the factorization of instances of AbstractKroneckerProduct.
Eigenvalue decomposition
The function eigen of LinearAlgebra is overloaded to compute the decomposition of AbstractKroneckerProducts. The result is a factorization of the Eigen type, containing a vector of the eigenvalues and a matrix with the eigenvectors. Just like long-time users would expect! The eigenvectors are structured as Kronecker products and can be processed accordingly.
The functions det, logdet, inv and \ are overloaded the make use of this decomposition.
The eigenvalue decomposition of matrices can be used to solve large systems of the form:
\[(A \otimes B + c\cdot I) \mathbf{x} = \mathbf{b}\]
The case where $A$ and $B$ are positive semi-definite frequently occurs in machine learning, for example in ridge regression.
julia> A, B = rand(10, 10), randn(4, 4);julia> As, Bs = (A, B) .|> X -> X * X'; # make positive definitejulia> K = As ⊗ Bs40×40 Kronecker.KroneckerProduct{Float64,Array{Float64,2},Array{Float64,2}}: 1.62639 1.25471 -1.63676 1.56681 … 0.967456 -1.26204 1.2081 1.25471 6.58116 4.46838 1.18069 5.07447 3.44539 0.910384 -1.63676 4.46838 8.08942 -1.97919 3.44539 6.23744 -1.52607 1.56681 1.18069 -1.97919 10.3125 0.910384 -1.52607 7.95156 1.09732 0.846546 -1.10431 1.05712 0.795376 -1.03756 0.993221 0.846546 4.44028 3.0148 0.796607 … 4.17189 2.83257 0.748456 -1.10431 3.0148 5.4579 -1.33535 2.83257 5.128 -1.25463 1.05712 0.796607 -1.33535 6.9578 0.748456 -1.25463 6.53724 1.07905 0.832449 -1.08592 1.03952 0.716351 -0.934476 0.894539 0.832449 4.36634 2.96459 0.783342 3.75739 2.55113 0.674092 ⋮ ⋱ 1.06578 0.803137 -1.3463 7.01484 0.782559 -1.3118 6.8351 1.46819 1.13266 -1.47755 1.4144 0.907994 -1.18447 1.13385 1.13266 5.941 4.03374 1.06584 4.76258 3.23363 0.85443 -1.47755 4.03374 7.30256 -1.78667 3.23363 5.85407 -1.43228 1.4144 1.06584 -1.78667 9.30939 … 0.85443 -1.43228 7.46284 1.25405 0.967456 -1.26204 1.2081 1.26638 -1.65198 1.58138 0.967456 5.07447 3.44539 0.910384 6.64238 4.50994 1.19167 -1.26204 3.44539 6.23744 -1.52607 4.50994 8.16467 -1.9976 1.2081 0.910384 -1.52607 7.95156 1.19167 -1.9976 10.4084julia> E = eigen(K)Eigen{Float64,Float64,Kronecker.KroneckerProduct{Float64,Array{Float64,2},Array{Float64,2}},Array{Float64,1}} values: 40-element Array{Float64,1}: 0.00018855191034974 0.00591704316659172 0.019378435025747986 0.022389383614321728 0.002695678826610023 0.0845944649976378 0.277048569249985 0.32009533734251927 0.005728423036084996 0.179766549795978 ⋮ 5.170568948615993 0.06385023538498764 2.0037166330971354 6.562212154157601 7.581824078300563 0.7670599905606486 24.071498756464617 78.8346411360074 91.08367214102876 vectors: 40×40 Kronecker.KroneckerProduct{Float64,Array{Float64,2},Array{Float64,2}}: -0.155475 -0.11018 0.0305046 … -0.197309 0.0546273 -0.0489688 0.0858264 -0.110409 0.109997 -0.19772 0.196981 0.142531 -0.080306 0.0938973 0.0554909 0.16815 0.0993725 0.251001 -0.00163364 0.0695979 0.147924 0.124635 0.2649 -0.190047 -0.192491 -0.136412 0.0377673 -0.157892 0.0437141 -0.0391861 0.10626 -0.136696 0.136185 … -0.15822 0.157629 0.114057 -0.0994258 0.116253 0.0687025 0.134558 0.0795204 0.200857 -0.00202258 0.0861683 0.183142 0.0997363 0.21198 -0.15208 -0.499753 -0.354158 0.0980528 -0.155279 0.0429908 -0.0385377 0.275877 -0.354895 0.353569 -0.155602 0.155021 0.11217 ⋮ ⋱ 4.33492e-5 -0.00184681 -0.00392522 0.100408 0.213408 -0.153105 0.294248 0.208524 -0.0577322 -0.208675 0.0577741 -0.0517897 -0.162433 0.208958 -0.208177 -0.209109 0.208328 0.150742 0.151985 -0.177708 -0.105021 0.177837 0.105097 0.26546 0.00309178 -0.131719 -0.279956 … 0.131815 0.28016 -0.200995 0.133188 0.094386 -0.0261318 -0.175492 0.048587 -0.0435542 -0.0735234 0.0945823 -0.0942289 -0.175857 0.1752 0.126771 0.0687944 -0.0804374 -0.0475364 0.149557 0.0883846 0.223247 0.00139946 -0.0596213 -0.126719 0.110854 0.235609 -0.169033julia> logdet(E)-40.974085191595016julia> b = randn(40);julia> (E + 0.1I) \ b # solve a system40-element Array{Float64,1}: -1.090662241404117 0.6865954194527603 -6.799330712197755 -0.19470456097731959 -1.1445986434758717 -4.792196354206688 -0.8239032678901995 -0.5041508924244695 -5.189759373577292 0.059954563138001744 ⋮ 0.21902049039945853 10.636978617004505 -0.18482527668763585 7.004163543648653 0.40280001129670295 5.659441431273249 -2.7350989388606815 4.885326760849022 -0.7931521452494137
LinearAlgebra.eigen — Functioneigen(K::AbstractKroneckerProduct)Wrapper around eigen from the LinearAlgebra package. If the matrices of an AbstractKroneckerProduct instance are square, performs Eigenvalue decompositon on them and returns an Eigen type. Otherwise, it collects the instance and runs eigen on the full matrix. The functions, \, inv, and logdet are overloaded to efficiently work with this type.
Missing docstring for +(E::Eigen, B::UniformScaling). Check Documenter's build log for details.
Missing docstring for +(::Eigen, ::UniformScaling). Check Documenter's build log for details.
LinearAlgebra.det — Methoddet(K::AbstractKroneckerProduct)Compute the determinant of a Kronecker product.
LinearAlgebra.logdet — Methodlogdet(K::Eigen)Compute the logarithm of the determinant of the eigenvalue decomp of a Kronecker product.
Base.inv — Methodinv(K::Eigen)Compute the inverse of the eigenvalue decomp of a Kronecker product. Returns another type of Eigen.
Cholesky factorization
Similar to the eigenvalue decomposition, cholesky has been overloaded to allow for efficient Cholesky decomposition of Kronecker products of symmetric and positive definite matrices.
julia> A, B = rand(10, 10), randn(4, 4);julia> As, Bs = (A, B) .|> X -> X * X'; # make positive definitejulia> K = As ⊗ Bs40×40 Kronecker.KroneckerProduct{Float64,Array{Float64,2},Array{Float64,2}}: 4.77015 1.42943 0.915443 … 1.91268 1.22493 1.28307 1.42943 2.44181 -0.0624311 3.26732 -0.0835373 0.207236 0.915443 -0.0624311 2.31109 -0.0835373 3.0924 0.504484 0.958895 0.154876 0.377023 0.207236 0.504484 6.89519 6.52029 1.95388 1.25131 3.20704 2.05387 2.15136 1.95388 3.33769 -0.0853366 … 5.4784 -0.140069 0.347477 1.25131 -0.0853366 3.15901 -0.140069 5.18511 0.84588 1.31071 0.211699 0.515349 0.347477 0.84588 11.5613 5.75129 1.72344 1.10373 2.70963 1.73532 1.81768 1.72344 2.94405 -0.0752721 4.62871 -0.118345 0.293584 ⋮ ⋱ 0.580641 0.0937825 0.228299 0.196256 0.477754 6.52986 3.00157 0.899452 0.576032 1.91603 1.22707 1.28532 0.899452 1.53648 -0.0392841 3.27304 -0.0836835 0.207598 0.576032 -0.0392841 1.45423 -0.0836835 3.09782 0.505366 0.603374 0.0974542 0.237237 … 0.207598 0.505366 6.90726 6.38281 1.91268 1.22493 3.89547 2.49476 2.61317 1.91268 3.26732 -0.0835373 6.6544 -0.170137 0.422067 1.22493 -0.0835373 3.0924 -0.170137 6.29816 1.02746 1.28307 0.207236 0.504484 0.422067 1.02746 14.0431julia> C = cholesky(K)40×40 CholeskyKronecker{Cholesky{Float64,Array{Float64,2}},Cholesky{Float64,Array{Float64,2}}} U factor: 40×40 Kronecker.KroneckerProduct{Float64,UpperTriangular{Float64,Array{Float64,2}},UpperTriangular{Float64,Array{Float64,2}}}: 2.18407 0.65448 0.419146 0.439041 … 0.560848 0.587468 0.0 1.41897 -0.237323 -0.0933546 -0.317555 -0.124915 0.0 0.0 1.4419 0.118486 1.92937 0.158543 0.0 0.0 0.0 2.22206 0.0 2.97328 0.0 0.0 0.0 0.0 0.170409 0.178498 0.0 0.0 -0.0 -0.0 … -0.0964868 -0.0379545 0.0 0.0 0.0 0.0 0.586225 0.0481721 0.0 0.0 0.0 0.0 0.0 0.90341 0.0 0.0 0.0 0.0 0.0116695 0.0122234 0.0 0.0 -0.0 -0.0 -0.00660737 -0.00259911 ⋮ ⋱ 0.0 0.0 0.0 0.0 -0.0 -0.330614 0.0 0.0 0.0 0.0 0.164031 0.171817 0.0 0.0 -0.0 -0.0 -0.0928755 -0.036534 0.0 0.0 0.0 0.0 0.564283 0.0463691 0.0 0.0 0.0 0.0 … 0.0 0.869597 0.0 0.0 0.0 0.0 0.157138 0.164596 0.0 0.0 -0.0 -0.0 -0.0889723 -0.0349986 0.0 0.0 0.0 0.0 0.540569 0.0444204 0.0 0.0 0.0 0.0 0.0 0.833051julia> logdet(C)8.373235233666012julia> inv(C)40×40 Kronecker.KroneckerProduct{Float64,Array{Float64,2},Array{Float64,2}}: 10.3334 -6.06019 -4.02088 … 2.01463 1.33669 0.480881 -6.06019 18.1597 2.82991 -6.03695 -0.940765 -0.124615 -4.02088 2.82991 17.153 -0.940765 -5.70228 0.196746 -1.44653 0.374852 -0.591829 -0.124615 0.196746 -2.39428 -3.5489 2.08131 1.38093 -0.214043 -0.142016 -0.051091 2.08131 -6.23677 -0.971903 … 0.641393 0.0999511 0.0132396 1.38093 -0.971903 -5.89102 0.0999511 0.605836 -0.0209031 0.496798 -0.128739 0.203258 0.0132396 -0.0209031 0.254378 -6.58593 3.86243 2.56268 -1.83677 -1.21868 -0.438428 3.86243 -11.574 -1.80362 5.50399 0.857712 0.113613 ⋮ ⋱ -0.442247 0.114603 -0.180939 -0.0175075 0.0276414 -0.336379 6.38211 -3.74289 -2.48337 1.36763 0.907407 0.326445 -3.74289 11.2158 1.7478 -4.09817 -0.638635 -0.0845943 -2.48337 1.7478 10.594 -0.638635 -3.87097 0.13356 -0.893407 0.231516 -0.365525 … -0.0845943 0.13356 -1.62535 -3.4352 2.01463 1.33669 -1.21249 -0.804476 -0.289415 2.01463 -6.03695 -0.940765 3.6333 0.566193 0.0749985 1.33669 -0.940765 -5.70228 0.566193 3.43188 -0.11841 0.480881 -0.124615 0.196746 0.0749985 -0.11841 1.44098
LinearAlgebra.cholesky — Functioncholesky(K::AbstractKroneckerProduct; check = true)Wrapper around cholesky from the LinearAlgebra package. Performs Cholesky on the matrices of a AbstractKroneckerProduct instances and returns a CholeskyKronecker type. Similar to Cholesky, size, \, inv, det, and logdet are overloaded to efficiently work with this type.