# New class of RIP matrices?

Wow, 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{\mathbb 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 $$X$$, i.e., the rows of a sensing matrix, and defining some specific submodular (or self-bounding) functions $$f$$ (e.g., $$f(X_1,\cdots, X_n) = g(X^T a)$$ for some sparse vector $$a$$ and a “kind” function $$g$$), I’m wondering if the concentration results above are better than those coming from the classical concentration inequalities (based on the Lipschitz properties of $$f$$ or $$g$$. See e.g., the books of Ledoux and Talagrand)?

Ok, all this is perhaps just too hasty thoughts …. written before a mug of black coffee ;-)