Complete Dictionary Recovery Using Nonconvex Optimization

We consider the problem of recovering a complete (i.e., square and invertible) dictionary mb A_0, from mb Y = mb A_0 mb X_0 with mb Y ∈\mathbb R^n \times p. This recovery setting is central to the theoretical understanding of dictionary learning. We give the first efficient algorithm that provably recovers mb A_0 when mb X_0 has O(n) nonzeros per column, under suitable probability model for mb X_0. Prior results provide recovery guarantees when mb X_0 has only O(\sqrtn) 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: \urlhttp://arxiv.org/abs/1504.06785.