Complete Dictionary Recovery Over the Sphere I: Overview and the Geometric Picture

Ju Sun, Qing Qu, John Wright

Research output: Contribution to journalArticlepeer-review

141 Scopus citations


We consider the problem of recovering a complete (i.e., square and invertible) matrix A0, from Y ∈ ℝn × p with Y = A0 X0, provided X0 is sufficiently sparse. This recovery problem is central to theoretical understanding of dictionary learning, which seeks a sparse representation for a collection of input signals and finds numerous applications in modern signal processing and machine learning. We give the first efficient algorithm that provably recovers A0 when X0 has O (n) nonzeros per column, under suitable probability model for X0. In contrast, prior results based on efficient algorithms either only guarantee recovery when X0 has O(√n) zeros per column, or require multiple rounds of semidefinite programming relaxation to work when X0 has O(n) nonzeros per column. Our algorithmic pipeline centers around solving a certain nonconvex optimization problem with a spherical constraint. In this paper, we provide a geometric characterization of the objective landscape. In particular, we show that the problem is highly structured with high probability: 1) there are no "spurious" local minimizers and 2) around all saddle points the objective has a negative directional curvature. This distinctive structure makes the problem amenable to efficient optimization algorithms. In a companion paper, we design a second-order trust-region algorithm over the sphere that provably converges to a local minimizer from arbitrary initializations, despite the presence of saddle points.

Original languageEnglish (US)
Article number7755794
Pages (from-to)853-884
Number of pages32
JournalIEEE Transactions on Information Theory
Issue number2
StatePublished - Feb 2017
Externally publishedYes

Bibliographical note

Publisher Copyright:
© 2016 IEEE.


  • Dictionary learning
  • escaping saddle points
  • function landscape
  • inverse problems
  • manifold optimization
  • nonconvex optimization
  • nonlinear approximation
  • second-order geometry
  • spherical constraint
  • structured signals
  • trust-region method


Dive into the research topics of 'Complete Dictionary Recovery Over the Sphere I: Overview and the Geometric Picture'. Together they form a unique fingerprint.

Cite this