Complete Dictionary Recovery Using Nonconvex Optimization
published: Sept. 27, 2015, recorded: July 2015, views: 89
Report a problem or upload filesIf 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.
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: http://arxiv.org/abs/1504.06785.
Link this pageWould you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !