Covariance of a Lipschitz function

240 Views Asked by At

Suppose $f:\mathbb{R}^n\rightarrow \mathbb{R}^n$ be an $L$-Lipschitz function i.e. for any vectors $v,u\in\mathbb{R}^n$, $\ell_2$ norms obey

$$\|f(u)-f(v)\|_{\ell_2}\leq L\|u-v\|_{\ell_2}.$$

Let $X\in\mathbb{R}^n$ be a random vector with covariance $\text{Cov}(X)$ defined as $\mathbb{E}[XX^T]-\mathbb{E}[X]\mathbb{E}[X]^T$. Is it always true that covariance of the Lipschitz function $f(X)$ obeys

$$\operatorname{Cov}(f(X))\preceq L^2\operatorname{Cov}(X)$$

1

There are 1 best solutions below

0
On

This is true only for $n=1$, where we deal with variance. Indeed, $$ \operatorname{Var} f(X) = \min_{c\in\mathbb{R}} E[ (f(X) - c)^2] \le E[(f(X)-f(EX))^2] \le L^2 E[(X-EX)^2] = L^2\operatorname{Var} X $$ A counterexample for $n=2$: let $X=(x_1, |x_1|)$ where $x_1$ is the standard normal. Then $$ \operatorname{Cov} X = \begin{pmatrix}1 & 0 \\ 0 & v\end{pmatrix} $$ where the exact value of $v = \operatorname{Var} (|x_1|)$ is unimportant. Let $f(x) = (|x_1|, x_2)$; this is a $1$-Lipschitz function. Then $f(X) = (|x_1|, |x_1|)$, with
$$ \operatorname{Cov} f(X) = \begin{pmatrix}v & v \\ v & v\end{pmatrix} $$ The matrix $$ \operatorname{Cov} X - \operatorname{Cov} f(X) = \begin{pmatrix}1-v & -v \\ -v & 0\end{pmatrix} $$ has negative determinant.