Map Estimation for Bayesian Mixture Models with Submodular Priors ( and slides Fourth Cargese Workshop on Combinatorial Optimization )

We saw submodularity here before, take for instance Francis Bach's slides (page 99 and up) on Structured sparsity through convex optimization , where he mentions the use of submodularity to find new regularizers).  Here is another way of using submodularity in compressive sensing: Map Estimation for Bayesian Mixture Models with Submodular Priors by Marwa El Halabi, Luca Baldassarre and Volkan Cevher

We propose a Bayesian approach where the signal structure can be represented by a mixture model with a submodular prior. We consider an observation model that leads to Lipschitz functions. Due to its combinatorial nature, computing the maximum a posteriori estimate for this model is NP-Hard, nonetheless our converging majorization-minimization scheme yields approximate estimates that, in practice, outperform state-of-the-art modular prior. We consider an observation model that leads to Lipschitz functions. Due to its combinatorial nature, computing the maximum a posteriori estimate for this model is NP-Hard, nonetheless our converging majorization-minimization scheme yields approximate estimates that, in practice, outperform state-of-the-art methods

why submodularity is a big deal, from the paper:

Submodularity is considered the discrete equivalent of convexity in the sense that submodular function minimization (SFM) admits efficient algorithms, with best known complexity of O(N5T+N6), where T is the function evaluation complexity [11]. In practice, however, the minimum-norm point algorithm is usually used whenever, the minimum-norm point algorithm is usually used, which commonly runs in O(N2), but has no known complexity [12]. Furthermore, for certain functions which are “graph representable” [13, 14], SFM is equivalent to the minimum s-t cut on an appropriate graph G(V,E), with time complexity 1 O(|E|min{|V|2/3,|E|1/2}) [15].

Relevant to the theme of submodularity are last year's Fourth Cargese Workshop on Combinatorial Optimization

Bach:

• Machine learning and convex optimization with submodular functions
  

Iwata:

• Submodular Functions and Discrete Convexity
  

• Submodular Functions in Graph Theory
  

• Submodular Function Minimization
  

• Minimizing Symmetric Submodular Functions
  

• Approximation Algorithms for Submodular Optimization
  

• Appications of Submodular Function Minimization
  

McCormick:

• Introduction to Submodular Functions
  

• Algorithms for Submodular Functions Minimization
  

• SFMin in an "Assemble to Order" inventory problem

Naor:

• Maximization of Submodular Functions
  

• Submodular Maximization: Lecture 2

• Submodular Maximization: Lecture 3

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.