Compute the mean of normalized norms of linear transformations of Gaussian random vectors

by DeltaIV   Last Updated October 07, 2018 08:19 AM

if $M$ is a $m\times n$ constant matrix and $\eta\sim\mathcal{N}(0,I)$, then does $$\mathbf{E}_{\eta\sim\mathcal{N}}\left[\frac{\lVert M\eta\rVert}{\lVert\eta\rVert}\right]$$ exist? Also, let $x\in \mathbb{R}^n_{\ne 0}$ be an arbitrary non-zero vector. Is it possible to compute the maximum (or at least to find a tight upper-bound) over all $x$, of the quantity $$\mathbf{E}_{\eta\sim\mathcal{N}}\left[\frac{\lVert M(x+\lVert x\rVert \eta)-Mx\rVert}{\lVert Mx \rVert}\right]=\lVert x\rVert\mathbf{E}_{\eta\sim\mathcal{N}}\left[\frac{\lVert M \eta\rVert}{\lVert Mx \rVert}\right]$$

Answers 1

Here is an algebraic answer. Each of these steps has a geometric interpretation that I'm sure could give you a simpler overall explanation for someone who thinks that way....

Take the singular value decomposition of $M$ as $M = U \Sigma V^T$. Here $U \in \mathbb R^{m \times m}$ and $V \in \mathbb R^{n \times n}$ are orthogonal matrices ($V^T V = V V^T = I$), and $\Sigma \in \mathbb R^{m \times n}$ has $\Sigma_{ii} = \sigma_i$ (the singular values) and all other entries are zero.

Now, $$ \lVert M \eta \rVert^2 = \lVert U \Sigma V^T \eta \rVert^2 = \eta^T V \Sigma^T U^T U \Sigma V^T \eta = \eta^T V \Sigma^T \Sigma V^T \eta = \lVert \Sigma V^T \eta \rVert^2 .$$

Because $\eta \sim \mathcal N(0, I)$, we have that $V^T \eta \sim \mathcal N(V^T 0, V^T V) = \mathcal N(0, I)$. Also notice that $$ \lVert V^T \eta \rVert^2 = \eta^T V V^T \eta = \eta^T \eta = \lVert \eta \rVert^2 .$$ So we can do a change of variables to $V^T \eta = X = A W$, with $X \sim \mathcal N(0, I)$ and $A = \lVert X \rVert \sim \chi_1(n)$ and $W = X / A$ is uniform on the unit sphere $\{ x : \lVert x \rVert = 1 \}$: $$ \mathbf E_{\eta \sim \mathcal N(0, I)}\left[ \frac{\lVert M \eta \rVert}{\lVert \eta \rVert} \right] = \mathbf E_{A, W}\left[ \frac{\lVert \Sigma A W \rVert}{\lVert A W \rVert} \right] = \mathbf E_{A, W}\left[ \frac{\lVert \Sigma W \rVert}{\lVert W \rVert} \right] = \mathbf E_{W}\left[ \lVert \Sigma W \rVert \right] .$$ This is not trivial to evaluate exactly in general. But we can find an easy upper bound via Jensen's inequality: $$ \mathbf E_{W}\left[ \lVert \Sigma W \rVert \right] \le \sqrt{\mathbf E_{W}\left[ \lVert \Sigma W \rVert^2 \right]} = \sqrt{ \mathbf E_{W}\left[ \sum_{i=1}^{\min(m, n)} \sigma_i^2 W_i^2 \right] } = \sqrt{ \sum_{i=1}^{\min(m, n)} \sigma_i^2 \,\mathbf E_{W}\left[ W_i^2 \right] } .$$ We have that $\mathbf E_W[ W_i^2 ] = 1/n$ as shown e.g. here, and $\sqrt{ \sum_{i=1}^{\min(m, n)} \sigma_i^2 }$ is exactly the Frobenius norm, $\lVert M \rVert_F = \sqrt{ \sum_{ij} M_{ij}^2 }$. Thus $$ \mathbf E_{\eta \sim \mathcal N(0, I)}\left[ \frac{\lVert M \eta \rVert}{\lVert \eta \rVert} \right] \le \frac{1}{\sqrt n} \lVert M \rVert_F .$$

Your second question is slightly different: $$ \lVert x\rVert \mathbf{E}_{\eta\sim\mathcal{N}(0, I)}\left[ \frac{\lVert M \eta\rVert}{\lVert Mx \rVert}\right] = \frac{\lVert x\rVert}{\lVert M x \rVert} \mathbf{E}_{\eta\sim\mathcal{N}(0, I)}\left[ \lVert M \eta\rVert \right] .$$ Observing that $M \eta \sim \mathcal N(0, M M^T)$, this question reduces to finding the expected norm of a multivariate normal. A quick Jensen bound as before gives \begin{align} \mathbf{E}_{\eta\sim\mathcal{N}(0, I)}\left[ \lVert M \eta\rVert \right] &\le \sqrt{ \mathbf{E}_{\eta\sim\mathcal{N}(0, I)}\left[ \lVert M \eta\rVert^2 \right] } \\&= \sqrt{ \mathbf{E}_{\eta\sim\mathcal{N}(0, I)}\left[ \eta^T M^T M \eta \right] } \\&= \sqrt{ \mathbf{E}_{\eta\sim\mathcal{N}(0, I)}\left[ \operatorname{tr}\left( \eta \eta^T M^T M \right) \right] } \\&= \sqrt{ \operatorname{tr}\left( \mathbf{E}_{\eta\sim\mathcal{N}(0, I)}\left[ \eta \eta^T \right] M^T M \right) } \\&= \sqrt{\operatorname{tr}(M^T M)} \\&= \lVert M \rVert_F .\end{align} The (very ugly) exact solution is also available in the links from here or here. (One could also maybe derive the exact answer for the first question with these techniques as well.)

October 12, 2018 17:09 PM

Related Questions

Projecting a 1xn matrix to 3D space

Updated May 11, 2017 08:19 AM

Why Normality assumption in linear regression

Updated March 01, 2019 04:19 AM

Gaussian covariance matrix basic concept

Updated August 24, 2016 08:08 AM