Submodular set function: Difference between revisions

Revision as of 13:38, 5 October 2011

Revision as of 20:11, 5 October 2011

Line 11:

A submodular function is also a [[subadditive]] function, but a subadditive function need not be submodular.

==ExamplesTypes==

===Monotone Submodular function===

A submodular function <math>f</math> is said to be monotone if for every <math>T\subseteq S</math> we have that <math>f(T)\leq f(S)</math>.

:Examples of Monotone Submodular function

# Linear functions

#: Any function of the form <math>f(S)=\sum_{i\in S}w_i</math> is called a linear function. Additionally if <math>\forall i,w_i\geq 0</math> then f is montone.

Line 20 ⟶ 23:

# [[Entropy (information theory)|Entropy]]

#:Let <math>\Omega=\{X_1,X_2,\ldots,X_n\}</math> be a set of [[random variables]]. Then for any <math>S\subseteq \Omega</math> we have that <math>H(S)</math> is a submodular function, where <math>H(S)</math> is the entropy of the set of random variables <math>S</math>

# [[Matroid]] rank functions

#:Let <math>\Omega=\{e_1,e_2,\dots,e_n\}</math> be the ground set on which a matroid is defined. Then the rank function of the matroid is a submodular function.

=== Non-monotone Submodular function===

A submodular function <math>f</math> which is not necessarily monotone is called as Non-monotone Submodular function.

====Symmetric Non-monotone Submodular function====

A submodular function <math>f</math> is called symmetric if for every <math>S\subseteq \Omega</math> we have that <math>f(S)=f(\Omega-S)</math>

:Examples of Symmetric Non-Monotone Submodular function

# Graph cuts

#:Let <math>\Omega=\{v_1,v_2,\dots,v_n\}</math> be the vertices of a [[graph]]. For any set of vertices <math>S\subseteq \Omega</math> let <math>f(S)</math> denote the number of edges <math>e=(u,v)</math> such that <math>u\in S</math> and <math>v\in \Omega-S</math>.

# [[Mutual information]]

#:Let <math>\Omega=\{X_1,X_2,\ldots,X_n\}</math> be a set of [[random variable]]s. Then for any <math>S\subseteq \Omega</math> we have that <math>f(S)=I(S;\Omega-S)</math> is a submodular function, where <math>I(S;\Omega-S)</math> is the mutual information.

====Asymmetric Non-monotone Submodular function====

# [[Matroid]] rank functions

A submodular function <math>f</math> is called Asymmetric if it is not necessarily symmetric.

#:Let <math>\Omega=\{e_1,e_2,\dots,e_n\}</math> be the ground set on which a matroid is defined. Then the rank function of the matroid is a submodular function.

:Examples of Symmetric Non-Monotone Submodular function

# Directed graph cuts

#:Let <math>\Omega=\{v_1,v_2,\dots,v_n\}</math> be the vertices of a [[directed graph]]. For any set of vertices <math>S\subseteq \Omega</math> let <math>f(S)</math> denote the number of edges <math>e=(u,v)</math> such that <math>u\in S</math> and <math>v\in \Omega-S</math>.

==Continuous extensions==

===Lovasz extension===

Consider any vector <math>\bold{x}=\{x_1,x_2,\dots,x_n\}</math> such that each <math>0\leq x_i\leq 1</math>. Then the lovasz extension is defined as <math>f^L(\bold{x})=\mathbb{E}(f(\{i|x_i\geq \lambda\}))</math> where the expectation is over choosing <math>\lambda</math> uniformly in <math>[0,1]</math>. It can be shown that Lovasz extension is a convex function.

===Multilinear extension===

Consider any vector <math>\bold{x}=\{x_1,x_2,\ldots,x_n\}</math> such that each <math>0\leq x_i\leq 1</math>. Then the multilinear extension is defined as <math>F(\bold{x})=\sum_{S\subseteq \Omega} f(S) \prod_{i\in S} x_i \prod_{i\notin S} (1-x_i)</math>

===Convex Closure===

Consider any vector <math>\bold{x}=\{x_1,x_2,\dots,x_n\}</math> such that each <math>0\leq x_i\leq 1</math>. Then the convex closure is defined as <math>f^-(\bold{x})=min(\sum_S \alpha_S f(S):\sum_S \alpha_S 1_S=\bold{x},\sum_S \alpha_S=1,\alpha_S\geq 0)</math>. It can be shown that <math>f^L(\bold{x})=f^-(\bold{x})</math>

===Concave Closure===

Consider any vector <math>\bold{x}=\{x_1,x_2,\dots,x_n\}</math> such that each <math>0\leq x_i\leq 1</math>. Then the convex closure is defined as <math>f^+(\bold{x})=max(\sum_S \alpha_S f(S):\sum_S \alpha_S 1_S=\bold{x},\sum_S \alpha_S=1,\alpha_S\geq 0)</math>.

==Optimization problems==