Hybrid Kronecker Product Decomposition and Approximation

Discovering underlying low dimensional structure of a high-dimensional matrix is traditionally done through low rank matrix approximations in the form of a sum of rank-one matrices. In this article, we propose a new approach. We assume a high-dimensional matrix can be approximated by a sum of a small number of Kronecker products of matrices with potentially different configurations, named as a hybrid Kronecker outer Product Approximation (hKoPA). It provides an extremely flexible way of dimension reduction compared to the low-rank matrix approximation. Challenges arise in estimating a hKoPA when the configurations of component Kronecker products are different or unknown. We propose an estimation procedure when the set of configurations are given, and a joint configuration determination and component estimation procedure when the configurations are unknown. Specifically, a least squares backfitting algorithm is used when the configurations are given. When the configurations are unknown, an iterative greedy algorithm is developed. Both simulation and real image examples show that the proposed algorithms have promising performances. Some identifiability conditions are also provided. The hybrid Kronecker product approximation may have potentially wider applications in low dimensional representation of high-dimensional data. Supplementary materials for this article are available online.