学术报告: Complete Dictionary Recovery over the Sphere

报告题目Complete Dictionary Recovery over the Sphere
报告人:Dr.Ju Sun, Electrical Engineering, Columbia University
主持人: 北邮模式识别实验室 李春光
时间:2015年9月2日 15:00-16:30
地点:教三810会议室

报告摘要:We consider the problem of recovering a complete (i.e., square and invertible) matrix $A_0$, from $Y \in R^{n\times p} with $Y = A_0X_0$, provided $X_0$ is sufficiently sparse. This recovery problem is central to the 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 $A_0$ when $X_0$ has $O (n)$ nonzeros per column, under suitable probability model for $X_0$. In contrast, prior results based on efficient algorithms provide recovery guarantees when $X_0$ has only $O (pn)$ nonzeros per column. 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. To show this apparently hard problem is tractable, we first provide a geometric characterization of the high-dimensional objective landscape, which shows that with high probability there are no “spurious” local minima. This particular geometric structure allows us to design a Riemannian trust region algorithm over the sphere that provably converges to one local minimizer with an arbitrary initialization, despite the presence of saddle points. The geometric approach we develop here may also shed light on other problems arising from nonconvex recovery of structured signals.

报告人简介:Ju Sun is now a five year PhD candidate (Advisor: Prof. John Wright) in the Department of Electrical Engineering, Columbia University in the City of New York. He works at the intersection of computer vision, machine learning, numerical optimization, signal/image processing, information theory, and compressive sensing, focusing on modeling, harnessing, and computing with structures in massive data, with provable guarantees and practical algorithms. His paper “Complete Dictionary Recovery over the Sphere” has recently received the best student paper award from SPARS 2015, which was held in Cambridge University.

详细信息请参阅
http://www.columbia.edu/~js4038/
http://sunju.org/

欢迎各位老师和同学积极参加!

发表评论

电子邮件地址不会被公开。 必填项已用*标注