Complete dictionary recovery over the sphere

By Ju Sun, Qing Qu, John Wright. 2015

198 citations recorded by the source corpus.

We consider the problem of recovering a complete (i.e., square and invertible) dictionary A0, from Y = A0X0 with Y ϵ Rn×p. This recovery setting is central to the theoretical understanding of dictionary 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. Prior results provide recovery guarantees when X0 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. This invited talk summarizes these results, presented in [1]. It also presents numerical experiments demonstrating their implications for practical problems in representation learning and the more general algorithmic problem of recovering matrix decompositions with structured factors.

Subfields: Computational Mechanics, Geophysics, Ocean Engineering, Mathematical Optimization, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Geophysics

In Ocean Engineering

In Mathematical Optimization

In Signal Processing

Citations in the corpus

Feature Purification: How Adversarial Training Performs Robust Deep Learning (2020, background): “There are many existing theoretical works studying algorithm for sparse coding [9, 17, 43, 47, 54, 68, 85, 91, 94], however, these algorithms share little similarity to training a neural network.”
Dual Principal Component Pursuit (2015, background): “In Qu et al. (2014); Sun et al. (2015b) (9) is approximately solved by alternating minimization, while a Riemannian trust-region approach is employed in Sun et al. (2015a).”
Gradient Descent Converges to Minimizers (2016, background): “, mirror descent and coordinate descent do not converge to saddle points under appropriate choices of step size. Indeed, convergence to minimizers has been empirically observed for the ADMM algorithm [26]. It is not clear if the step size restriction (α < 1/L) is necessary to avoid saddle points.”
Convergence Results for Neural Networks via Electrodynamics (2017, methodology): “deva@google.com. xGoogle Research. Email: alicsailmitedu@gmail.com. 1 arXiv:1702.00458v1 [cs.DS] 1 Feb 2017 A good overview of recent successes in the analysis of non-convex optimization in given in (Sun et al., 2015b). A non-convex analysis of the deep learning objective has been largely elusive an”
Learning Compact Neural Networks with Regularization (2018, methodology): “These include low-rank factorization and sparse approximation literature [19, 38, 50, 52, 57] as well as standard techniques [53, 58].”
Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems (2015, background): “(38) Here, one has (4− )‖h‖2 in (37) instead of 4‖h‖2 to account for the bias introduced by adaptive trimming, where is small as long as we only throw away a small fraction of data.”
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, background): “[151], [152] was perhaps the first “modern” example where benign landscape is analyzed, which exploits measure concentration of random data.”