On the Computational Intractability of Exact and Approximate Dictionary
  Learning
  The efficient sparse coding and reconstruction of signal vectors via linear
observations has received a tremendous amount of attention over the last
decade. In this context, the automated learning of a suitable basis or
overcomplete dictionary from training data sets of certain signal classes for
use in sparse representations has turned out to be of particular importance
regarding practical signal processing applications. Most popular dictionary
learning algorithms involve NP-hard sparse recovery problems in each iteration,
which may give some indication about the complexity of dictionary learning but
does not constitute an actual proof of computational intractability. In this
technical note, we show that learning a dictionary with which a given set of
training signals can be represented as sparsely as possible is indeed NP-hard.
Moreover, we also establish hardness of approximating the solution to within
large factors of the optimal sparsity level. Furthermore, we give NP-hardness
and non-approximability results for a recent dictionary learning variation
called the sensor permutation problem. Along the way, we also obtain a new
non-approximability result for the classical sparse recovery problem from
compressed sensing.
