Minimax Lower Bounds for Kronecker-Structured Dictionary Learning

Dictionary learning has recently received significant attention due to the increased importance of finding sparse representations of signals/data. In dictionary learning, the goal is to construct an overcomplete basis using input signals such that each signal can be described by a small number of atoms (columns) [1]. Although the existing literature has focused on one-dimensional data, many signals in practice are multidimensional and have a tensor structure: examples include 2-dimensional images and 3-dimensional signals produced via magnetic resonance imaging or computed tomography systems. In traditional dictionary learning techniques, multidimensional data are processed after vectorizing of signals. This can result in poor sparse representations as the structure of the data is neglected [2]. In this paper we provide fundamental limits on learning dictionaries for multidimensional data with tensor structure: we call such dictionaries Kronecker-structured (KS). Several algorithms have been proposed to learn KS dictionaries [2]-[7] but there has been little work on the theoretical guarantees of such algorithms. The lower bounds we provide on the minimax risk of learning a KS dictionary give a measure to evaluate the performance of the existing algorithms.