Wouaw, almost one year and half without any post here…. Shame on me! I’ll try to be more productive with shorter posts now 😉

I just found this interesting paper about concentration properties of submodular function (very common in “Graph Cut” methods for instance) on arxiv:

## A note on concentration of submodular functions. (arXiv:1005.2791v1 [cs.DM])

Jan Vondrak, May 18, 2010

We survey a few concentration inequalities for submodular and fractionally subadditive functions of independent random variables, implied by the entropy method for self-bounding functions. The power of these concentration bounds is that they are dimension-free, in particular implying standard deviation O(\sqrt{\E[f]}) rather than O(\sqrt{n}) which can be obtained for any 1-Lipschitz function of n variables.

In particular, the author shows some interesting concentration results in his corollary 3.2.

Without having performed any developments, I’m wondering if this result could serve to define a new class of matrices (or non-linear operators) satisfying either the Johnson-Lindenstrauss Lemma or the Restricted Isometry Property.

For instance, by starting from Bernoulli vectors , *i.e.*, the rows of a sensing matrix, and defining some specific submodular (or self-bounding) functions (e.g. for some sparse vector and a “kind” function ), I’m wondering if the concentration results above are better than those coming from the classical concentration inequalities (based on the Lipschitz properties of or . See e.g., the books of Ledoux and Talagrand)?

Ok, all this is perhaps just due to too early thoughts …. before my mug of black coffee 😉

Laurent,

Do you think that g could be behaving like the quantization function in the 1-bit compressive sensing approach of Petros ?

http://www.merl.com/reports/docs/TR2010-014.pdf

Cheers,

Igor.