  Algorithms for learning a dictionary to sparsely represent a given dataset
typically alternate between sparse coding and dictionary update stages. Methods
for dictionary update aim to minimise expansion error by updating dictionary
vectors and expansion coefficients given patterns of non-zero coefficients
obtained in the sparse coding stage. We propose a block total least squares
(BLOTLESS) algorithm for dictionary update. BLOTLESS updates a block of
dictionary elements and the corresponding sparse coefficients simultaneously.
In the error free case, three necessary conditions for exact recovery are
identified. Lower bounds on the number of training data are established so that
the necessary conditions hold with high probability. Numerical simulations show
that the bounds approximate well the number of training data needed for exact
dictionary recovery. Numerical experiments further demonstrate several benefits
of dictionary learning with BLOTLESS update compared with state-of-the-art
algorithms especially when the amount of training data is small.
