Complete dictionary recovery using nonconvex optimization

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