Speaker: Rong Ge
Affiliation: Microsoft Research New England

Title: New Algorithms for Learning Incoherent and Overcomplete Dictionary

Abstract:

In sparse recovery we are given a matrix A (“the dictionary”) and a vector of the form AX where X is sparse. and the goal is to recover X. This is a central notion in signal processing, statistics and machine learning. But in applications such as
sparse coding, the dictionary A is unknown and has to be learned from random examples of the form Y = AX where X is drawn from an appropriate distribution — this is the dictionary learning problem. In most settings, A is overcomplete: it has more columns
than rows. This talk presents a polynomial-time algorithm for learning overcomplete dictionaries; Our algorithm applies to incoherent dictionaries which have been a central object of study since they were introduced in seminal work of Donoho and Huo.

Based on joint work with Sanjeev Arora, Tengyu Ma and Ankur Moitra.

Bio:

Rong Ge is currently a post-doc at Microsoft Research, New England. He received his Ph.D. in Princeton University, advised by Prof. Sanjeev Arora. His main research interest is in applying algorithm design techniques from theoretical computer science to
machine learning problems, with the hope of provable algorithms and better understanding of the machine learning models.