Abstract

We consider the problem of recovering a complete (i.e., square and invertible) dictionary A0 , from This recovery setting is central to the theoretical understanding of dictionary learning. We give the first efficient al gorithm that provably recovers A0 when X0 has O (n) nonzeros per column, under suitable probability model for X0 . Prior results provide recovery guarantees when X0 has only nonzeros per column. Our algorithm is based on nonconvex optimization with a spherical constraint, and hence is naturally phrased in the language of manifold optimization. Our proofs give a geometric characterization of the high-dimensional objective landscape, which shows that with high probability there are no spurious local minima. Experiments with synthetic data corroborate our theory. Full version of this paper is available online http://arxiv.org/abs/1504.06785.