Visit ShanghaiTech University | 中文 | How to find us
HOME > News and Events > Events
Complete Dictionary Recovery over the Sphere and Beyond
Date: 2015/9/8             Browse: 783

Speaker: Ju Sun

Time: Sept. 10th, 10:45am – 11:45am

Location: Room 220, Building 8


In this talk, I will focus on the problem of recovering a complete (i.e., square and invertible) dictionary A and coefficients X from Y = AX, provided X is sufficiently sparse. This recovery problem is central to the theoretical understanding of dictionary learning. I will describe an efficient algorithm that provably recovers A when X has O(n) nonzeros per column, under suitable probability model for X. Prior results based on efficient algorithms provide recovery guarantees when X has only O(n^{1/2}) nonzeros per column.

The algorithmic pipeline centers around solving a certain nonconvex optimization problem with a spherical constraint. We provide a geometric characterization of the high-dimensional objective landscape, which shows that with high probability there are no spurious local minima. This nice geometric structure allows us to design a Riemannian trust region algorithm that provably converges to one target minimizer with an arbitrary initialization, despite the presence of saddle points.


Ju Sun received his B. Eng. degree in computer engineering (with a minor in Mathematics) from the National University of Singapore in 2008. He has been working towards a PhD degree in the Department of Electrical Engineering, Columbia University, New York, since 2011. His research interests lie at the intersection of computer vision, machine learning, numerical optimization, signal/image processing, information theory, and compressive sensing, focused on modeling, harnessing, and computing with low-dimensional structures in massive data, with provable guarantees and practical algorithms. Recently, he is particularly interested in explaining the surprisingly effectiveness of nonconvex optimization heuristics arising in interesting practical problems, such as representation learning (He maintains a webpage dedicated to this topic: ) He received the best student paper award from SPARS'15.


SIST-Seminar 15040