  A matrix completion problem is to recover the missing entries in a partially
observed matrix. Most of the existing matrix completion methods assume a low
rank structure of the underlying complete matrix. In this paper, we introduce
an alternative and more general form of the underlying complete matrix, which
assumes a low Kronecker rank instead of a low regular rank, but includes the
latter as a special case. The extra flexibility allows for a much more
parsimonious representation of the underlying matrix, but also raises the
challenge of determining the proper Kronecker product configuration to be used.
We find that the configuration can be identified using the mean squared error
criterion as well as a modified cross-validation criterion. We establish the
consistency of this procedure under suitable conditions on the signal-to-noise
ratio. A aggregation procedure is also proposed to deal with special missing
patterns and complex underlying structures. Both numerical and empirical
studies are carried out to demonstrate the performance of the new method.
