  This paper provides fundamental limits on the sample complexity of estimating
dictionaries for tensor data. The specific focus of this work is on $K$th-order
tensor data and the case where the underlying dictionary can be expressed in
terms of $K$ smaller dictionaries. It is assumed the data are generated by
linear combinations of these structured dictionary atoms and observed through
white Gaussian noise. This work first provides a general lower bound on the
minimax risk of dictionary learning for such tensor data and then adapts the
proof techniques for specialized results in the case of sparse and
sparse-Gaussian linear combinations. The results suggest the sample complexity
of dictionary learning for tensor data can be significantly lower than that for
unstructured data: for unstructured data it scales linearly with the product of
the dictionary dimensions, whereas for tensor-structured data the bound scales
linearly with the sum of the product of the dimensions of the (smaller)
component dictionaries. A partial converse is provided for the case of
2nd-order tensor data to show that the bounds in this paper can be tight. This
involves developing an algorithm for learning highly-structured dictionaries
from noisy tensor data. Finally, numerical experiments highlight the advantages
associated with explicitly accounting for tensor data structure during
dictionary learning.
