Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published December 2012 | Published
Book Section - Chapter Open

Recovery of Sparse Probability Measures via Convex Programming


We consider the problem of cardinality penalized optimization of a convex function over the probability simplex with additional convex constraints. The classical ℓ_1 regularizer fails to promote sparsity on the probability simplex since ℓ_1 norm on the probability simplex is trivially constant. We propose a direct relaxation of the minimum cardinality problem and show that it can be efficiently solved using convex programming. As a first application we consider recovering a sparse probability measure given moment constraints, in which our formulation becomes linear programming, hence can be solved very efficiently. A sufficient condition for exact recovery of the minimum cardinality solution is derived for arbitrary affine constraints. We then develop a penalized version for the noisy setting which can be solved using second order cone programs. The proposed method outperforms known rescaling heuristics based on ℓ_1 norm. As a second application we consider convex clustering using a sparse Gaussian mixture and compare our results with the well known soft k-means algorithm.

Additional Information

This work is partially supported by the National Science Foundation under Grants No. CMMI-0969923, FRG-1160319, and SES-0835531, as well as by a University of California CITRIS seed grant, and a NASA grant No. NAS2-03144. The authors would like to thank the Area Editor and the reviewers for their careful review of our submission.

Attached Files

Published - pec_sparsemeasures_nips12.pdf


Files (422.0 kB)
Name Size Download all
422.0 kB Preview Download

Additional details

August 19, 2023
October 20, 2023