Complete Dictionary Recovery Using Nonconvex Optimization

We consider the problem of recovering a complete (i.e., square and invertible) dictionary mbA0, from mbY=mbA0mbX0 with mbY∈Rn×p. This recovery setting is central to the theoretical understanding of dictionary learning. We give the first efficient algorithm that provably recovers mbA0 when mbX0 has O(n) nonzeros per column, under suitable probability model for mbX0. Prior results provide recovery guarantees when mbX0 has only O(n√) 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.