报告题目：Complete Dictionary Recovery over the Sphere and Beyond

报告人：孙举博士 

报告时间：2015年9月11日上午10：00 

报告地点：二号学科楼二楼图像实验室 

主持人：袁晓彤 

欢迎广大师生踊跃参加！ 

报告摘要： 

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: http://sunju.org/research/nonconvex/)  He received the best student paper award from SPARS'15.