Complete Dictionary Recovery Using Nonconvex Optimization

author: John Wright, Department of Electrical Engineering, Columbia University
published: Sept. 27, 2015,   recorded: July 2015,   views: 2183

Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


We consider the problem of recovering a complete (i.e., square and invertible) dictionary mbA0, from mbY=mbA0mbX0 with mbY∈Rn×p. This recovery setting is central to the theoretical understanding of dictionary learning. We give the first efficient algorithm that provably recovers mbA0 when mbX0 has O(n) nonzeros per column, under suitable probability model for mbX0. Prior results provide recovery guarantees when mbX0 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. Experiments with synthetic data corroborate our theory. Full version of this paper is available online:

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: