KoPA: Automated Kronecker Product Approximation.

We consider matrix approximation induced by the Kronecker product decomposition. Similar as the low rank approximations, which seeks to approximate a given matrix by the sum of a few rank-1 matrices, we propose to use the approximation by the sum of a few Kronecker products, which we refer to as the Kronecker product approximation (KoPA). Although it can be transformed into an SVD problem, KoPA offers a greater flexibility over low rank approximation, since it allows the user to choose the configuration of the Kronecker product. On the other hand, the configuration (the dimensions of the two smaller matrices forming the Kronecker product) to be used is usually unknown, and has to be determined from the data in order to obtain optimal balance between accuracy and complexity. We propose to use an extended information criterion to select the configuration. Under the paradigm of high dimensionality, we show that the proposed procedure is able to select the true configuration with probability tending to one, under suitable conditions on the signal-to-noise ratio. We demonstrate the performance and superiority of KoPA over the low rank approximations thought numerical studies, and a real example in image analysis.