Computer Science – Learning
Scientific paper
2010-12-07
Computer Science
Learning
Scientific paper
We consider a class of sparsity-inducing regularization terms based on submodular functions. While previous work has focused on non-decreasing functions, we explore symmetric submodular functions and their \lova extensions. We show that the Lovasz extension may be seen as the convex envelope of a function that depends on level sets (i.e., the set of indices whose corresponding components of the underlying predictor are greater than a given constant): this leads to a class of convex structured regularization terms that impose prior knowledge on the level sets, and not only on the supports of the underlying predictors. We provide a unified set of optimization algorithms, such as proximal operators, and theoretical guarantees (allowed level sets and recovery conditions). By selecting specific submodular functions, we give a new interpretation to known norms, such as the total variation; we also define new norms, in particular ones that are based on order statistics with application to clustering and outlier detection, and on noisy cuts in graphs with application to change point detection in the presence of outliers.
No associations
LandOfFree
Shaping Level Sets with Submodular Functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Shaping Level Sets with Submodular Functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Shaping Level Sets with Submodular Functions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-480806