Month: September 2011

Talagrand has shown that there exists universal constants ${c,C>0}$ such that for any independent and identically distributed random variables ${X_1,\ldots,X_n}$ in the unit disk ${D}$ of ${\mathbb{C}}$, any convex and Lipschitz function ${f:D^n\rightarrow\mathbb{R}}$, and any real number ${r>0}$,

$$\mathbb{P}(|f(X_1,\ldots,X_n)-\mathbb{E}f(X_1,\ldots,X_n)|\geq r) \leq C\exp(-cr^2).$$

An accessible proof can be found in Ledoux's monograph on the concentration phenomenon (chapter 4). This inequality is useful for instance in order to control the distance of a random vector to a sub-vector space of controlled dimension. In many situations, one would like a similar concentration result, beyond these restrictive assumptions. Let us consider for instance a ${n\times n}$ random matrix ${M}$ with i.i.d. entries (standard Gaussian or symmetric Bernoulli ${\pm 1}$). Here are two open questions about concentration of measure for which the Talagrand inequality is not enough as is due to the lack of one of the assumptions:

• concentration for the function ${\log|\det(M)|=\log\det\sqrt{MM^*}=\sum_{i=1}^n\log(s_i(M))}$
• concentration for the least singular value ${s_n(M)=\min_{\left\Vert x\right\Vert=1}\left\Vert Mx\right\Vert_2}$