  This paper focuses on complete dictionary learning problem, where the goal is
to reparametrize a set of given signals as linear combinations of atoms from a
learned dictionary. There are two main challenges faced by theoretical and
practical studies of dictionary learning: the lack of theoretical guarantees
for practically-used heuristic algorithms, and their poor scalability when
dealing with huge-scale datasets. Towards addressing these issues, we show that
when the dictionary to be learned is orthogonal, that an alternating
minimization method directly applied to the nonconvex and discrete formulation
of the problem exactly recovers the ground truth. For the huge-scale,
potentially online setting, we propose a minibatch version of our algorithm,
which can provably learn a complete dictionary from a huge-scale dataset with
minimal sample complexity, linear sparsity level, and linear convergence rate,
thereby negating the need for any convex relaxation for the problem. Our
numerical experiments showcase the superiority of our method compared with the
existing techniques when applied to tasks on real data.
