SVDs of Kronecker Products. Our goal is to cheaply approximate the TSVD of a matrix. The Kronecker product decomposition (2.4) and approximation (2.5) help us achieve this goal. For now, we restrict ourselves back to a single Kronecker product, rather than a summation, to begin work towards a TSVD approximation based on the summation decomposition; Chapter 3 begins discussion of an approach based on the summation decomposition. We can cheaply take the SVD of matrices with a Kronecker product structure. A Given matrices A with singular value decomposition UAΣAV T and B with singular B value decomposition UBΣBV T , A B A ⊗ B = (UAΣAV T ) ⊗ (UBΣBV T ) A B = (UA ⊗ UB)(ΣA ⊗ ΣB)(V T ⊗ V T ) = (UA ⊗ UB)(ΣA ⊗ ΣB)(VA ⊗ VB)T . We call these matrices UA ⊗ UB = U , ΣA ⊗ ΣB = Σ, and VA ⊗ VB = V . Then the singular value decomposition of A ⊗ B = U ΣV T . The benefits in this derivation are masked by its simplicity. Recall that computing the SVD of a matrix is expensive, taking O(N 3) operations for a matrix of size N × N . By splitting the matrix into the Kronecker product of two n × n matrices and computing their SVDs independently, we have reduced the time complexity to O(N 2 ). For problems where N is huge, on the order of a million or larger, such as arises for the image deconvolution problem on a 1024 × 1024 image, this is a massive saving. Beyond the time complexity benefits, we also have improved the memory usage. As before, we do not form the results of the Kronecker products explicitly; instead, the Kronecker product components are stored and used for computations. The matrices U and V are normally size N × N , but are now stored as matrices of size n× n. This takes the memory complexity from O(N 2) = O(n4) down to O(n2). Matrices which are impossible to store in memory normally can be stored using a Kronecker product format. Storing Σ using Kronecker products provides an additional, small savings. Be- cause ΣA and ΣB are diagonal matrices, instead of storing O(n2) zeros, we can store the nonzero diagonal entries using vectors and not matrices. This reduces the mem- ory for storing Σ without using Kronecker structure from O(n2) to O(n) when we do exploit the structure. Once again, the restriction to a single term Kronecker product is not realistic for many applications. Chapter 3 begins to explore how we can expand the ease of computation afforded here into a summation of Kronecker products.
