4
$\begingroup$

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]$$

$\endgroup$
  • 4
    $\begingroup$ This function is bounded: it represents the amount by which the linear operator represented by $M$ changes the length of its argument $\eta$ and no linear operator can change lengths by infinite amounts. This is also a hint concerning how you can obtain an upper bound of the expectation. In the second part of the question, separately consider the cases where $M$ has nontrivial kernel and where it does not. $\endgroup$ – whuber Oct 7 '18 at 12:45
3
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ I think at least one of your upper bounds can be transformed to an exact bound (maximum). I’ll have a look at it next week. $\endgroup$ – DeltaIV Oct 13 '18 at 7:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.