Let $A_{k \times n}$ be a matrix where each element is a independent random normal distribution defined by $\mathcal{N}(0, \frac{1}{k})$, and $x \in \mathbb{R}^n$.

Each $j$-th element of resulting vector $Ax \in \mathbb{R}^k$ is given by the distribution $\mathcal{N}(0, \frac{\sum_{i=1}^d x_i^2}{k})$. Since \begin{equation} ((Ax)_j)^2 = \left( \sum_{i=1}^d A_{ji} x_i \right)^2 \end{equation}

Then, in particular for $j=1$ we have. \begin{equation} \mathbb{E} \left[ \| A x \|_2^2 \right] = k \;\mathbb{E} \left[ \left( (A x)_1 \right)^2 \right] = k \frac{\| x \|_2^2}{k} = \| x \|_2^2 \end{equation}

In the last equality, I could not understand how

\begin{equation} \mathbb{E} \left[ \left( (A x)_1 \right)^2 \right] = \frac{\| x \|_2^2}{k} \end{equation}

This claim was taken from MIT 6.854 Spring 2016 Lecture 5: Johnson Lindenstrauss Lemma and Extensions.

I understand that for a $X$ random variable:

\begin{equation} \mathbb{E}(X) = \sum_{i=1}^{n} \lambda_i x_i\quad\text{and}\quad\sum_{i=1}^n \lambda_i = 1 \end{equation}

The matrix $A_{k \times d}$, vector $x_{d \times 1}$ product is given by \begin{equation} Ax = \begin{bmatrix} \langle A_1, x \rangle \\ \langle A_2, x \rangle \\ \vdots \\ \langle A_k, x \rangle \\ \end{bmatrix}_{k \times 1} \end{equation}

And the vector norm \begin{equation} \| X \|_2^2 = \sum_{i=1}^n x_i^2 \end{equation}


1 Answer 1


After working a little with definitions I got the answer.

The definition of a variance is given by:

\begin{equation} Var(X) = \mathbb{E}(X^2) - (\mathbb{E}(X))^2 \end{equation}


\begin{equation} \mathbb{E}(X^2) = Var(X) +(\mathbb{E}(X))^2 \end{equation}

For centered gaussian distribution we have $\mathbb{E}(X) = 0 \implies (\mathbb{E}(X))^2 = 0$. Leading to

\begin{equation} \mathbb{E}(X^2) = Var(X) \end{equation}

This last statement implies that square of a centered gaussian distribution is equal to it's variance.

From OP as variance is given by

\begin{equation} \frac{\sum_{i=1}^d x_i^2}{k} \end{equation} and by definition \begin{equation} \| X\|_2^2 = \sum x_i^2 \end{equation} that is exactly the numerator part of variance we can substitute, giving \begin{equation} \frac{\sum_{i=1}^d x_i^2}{k} = \frac{\| X\|_2^2}{k} \end{equation}



You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .