Submodular Function Optimization: sfo_lovaszext(F,V,w) - File Exchange

Code covered by the BSD License

Highlights from
Submodular Function Optimization

C=sfo_setdiff_fast(A,B) Helper for quickly computing the set difference
C=sfo_unique_fast(A) Helper for quickly computing the unique set representation
[P,Agreedy]=sfo_mi_cluster(si... Example program for clustering using mutual information
sfo_balance(F,V,m,k,opt) Andreas Krause (krausea@cs.cmu.edu)
sfo_celf(F,V,B,opt) The CELF algorithm from Leskovec et al, KDD '07
sfo_charvector(V,A) returns characteristic vector of A
sfo_chol_downdate(R,j) Andreas Krause (krausea@gmail.com)
sfo_chol_update(sigma, A, new... Andreas Krause (krausea@gmail.com)
sfo_cover(F,V,Q,opt) Andreas Krause (krausea@gmail.com)
sfo_dist(coords) Andreas Krause (krausea@gmail.com)
sfo_eval_maxvar(sigma,set) computes the Gaussian maximum posterior variance after conditioning on
sfo_greedy_lazy(F,V,B,opt) Andreas Krause (krausea@gmail.com)
sfo_greedy_splitting(E,V,k) Implements Greedy splitting by Zhao et al
sfo_greedy_welfare(Fs,V,k) Andreas Krause (krausea@gmail.com)
sfo_inv_downdate(prec,k) Andreas Krause (krausea@gmail.com)
sfo_inv_update(prec,sigma_Ax,... Andreas Krause (krausea@gmail.com)
sfo_logdet(sigma) Compute the log determinant of a positive definite matrix using stable
sfo_lovaszext(F,V,w) The Lovasz extension [Lovasz '83]
sfo_ls_lazy(F,V,opt) Andreas Krause (krausea@gmail.com)
sfo_max_dca_lazy(F,V,opt) The data-correcting algorithm for maximizing general submodular functions
sfo_max_delta_lazy(F,S,T,pm,b... Helper routine for computing lazy increments / decrements
sfo_maxbound(F,V,A,B,C) Getting an online bound on the optimal solution for budgeted maximization
sfo_maxbound_welfare(F,V,As) Getting an online bound on the optimal solution for submodular welfare
sfo_min_norm_point(F,V, opt) Finding the minimum of a submodular function using Wolfe's min norm point
sfo_min_norm_point_tutorial_c... Helper callback function for visualizing inference in Ising model
sfo_minbound(F,V,A) Get bound on suboptimality / certificate of optimality [Edmonds '71]
sfo_octavize(F_input) Helper function that makes an sfo_fn_* object Octave ready
sfo_opt(vals) Andreas Krause (krausea@cs.cmu.edu)
sfo_opt_get(opt,name,default) Andreas Krause (krausea@cs.cmu.edu)
sfo_plot_subgraph(coords,edge... Plots a subgraph on known coordinates
sfo_polyhedrongreedy(F,V,w) The polyhedron greedy algorithm [Edmonds '71]
sfo_pspiel(F,V,Q,D,opt) Andreas Krause (krausea@gmail.com)
sfo_pspiel_get_cost(A,D,dists... Andreas Krause (krausea@gmail.com)
sfo_pspiel_get_path(set,D,Vro... Andreas Krause (krausea@gmail.com)
sfo_pspiel_orienteering(F,V,B... Andreas Krause (krausea@gmail.com)
sfo_queyranne(F,V) implements Queyranne's algorithm for minimizing symmetric submodular
sfo_s_t_mincut(F,V,s,t,opt) Finding the minimum A of a submodular function such that s in A and t not in A
sfo_saturate(F,V,k,task,opt) Andreas Krause (krausea@cs.cmu.edu)
sfo_ssp(F,G,V,opt) The submodular-supermodular procedure of Narasimhan & Bilmes
sfo_fn Base class for set function objects
sfo_fn_cutfun(G) Implementation of a (directed) cut function
sfo_fn_detect(detmat,V) Implementation by Andreas Krause (krausea@gmail.com)
sfo_fn_entropy(sigma,V) Computes the Gaussian entropy
sfo_fn_example The example from the tutorial slides at www.submodularity.org
sfo_fn_infogain(sigma,V,noise) Computes the Gaussian entropy
sfo_fn_invert(oldF,V) Implementation by Andreas Krause (krausea@gmail.com)
sfo_fn_ising(img,coeffPix,coe... Energy function for ising model for image denoising
sfo_fn_iwata(n) Evaluate Iwata's test function (taken from Fujishige et al '06)
sfo_fn_lincomb(Fs,weights) Implementation by Andreas Krause (krausea@gmail.com)
sfo_fn_mi(sigma,V) Computes the Gaussian mutual information between a set and its complement
sfo_fn_residual(oldF,sset) Implementation by Andreas Krause (krausea@gmail.com)
sfo_fn_trunc(oldF,thresh) Implementation by Andreas Krause (krausea@gmail.com)
sfo_fn_varred(sigma,V) Implementation by Andreas Krause (krausea@gmail.com)
sfo_fn_varred_trunc(sigma,V,t... Implementation by Andreas Krause (krausea@gmail.com)
sfo_fn_welfare(Fs) Implementation by Andreas Krause (krausea@gmail.com)
sfo_fn_wrapper(fn) Implementation by Andreas Krause (krausea@gmail.com)
sfo_tutorial.m
sfo_tutorial_octave.m
View all files

from Submodular Function Optimization by Andreas Krause
This toolbox provides functions for maximizing and minimizing submodular set functions.

sfo_lovaszext(F,V,w)

% The Lovasz extension [Lovasz '83]
% Implementation by Andreas Krause (krausea@gmail.com)
%
% function x = sfo_lovaszext(F,V,w)
% F: Submodular function
% V: index set
% w: weight vector to evaluate Lovasz extension at
%
% Example: x = sfo_lovaszext(@sfo_fn_example,1:2,[0,1])

function x = sfo_lovaszext(F,V,w)
x = w*sfo_polyhedrongreedy(F,V,w)';

Highlights from Submodular Function Optimization

Highlights from
Submodular Function Optimization