Complete Dictionary Recovery Over the Sphere II: Recovery by Riemannian Trust-Region Method

Ju Sun, Qing Qu, John Wright

Research output: Contribution to journalArticlepeer-review

65 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. Our algorithmic pipeline centers around solving a certain nonconvex optimization problem with a spherical constraint, and hence is naturally phrased in the language of manifold optimization. In a companion paper, we have showed that with high probability, our nonconvex formulation has no "spurious" local minimizers and around any saddle point, the objective function has a negative directional curvature. In this paper, we take advantage of the particular geometric structure and describe a Riemannian trust region algorithm that provably converges to a local minimizer with from arbitrary initializations. Such minimizers give excellent approximations to the rows of X0. The rows are then recovered by a linear programming rounding and deflation.

Original languageEnglish (US)
Article number7755786
Pages (from-to)885-914
Number of pages30
JournalIEEE Transactions on Information Theory
Issue number2
StatePublished - Feb 2017
Externally publishedYes

Bibliographical note

Funding Information:
This work was supported in part by ONR under Grant N00014-13-1-0492, in part by NSF under Grant 1343282, Grant CCF 1527809, and Grant IIS 1546411, and in part by the Moore and Sloan Foundations.

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 II: Recovery by Riemannian Trust-Region Method'. Together they form a unique fingerprint.

Cite this