Let $A$ be an $n\times n$ random matrix with i.i.d. $N(0,\sigma)$ entries, for some $\sigma>0$ and let $x\in \mathbb{R}^n$. A direct computation shows that $Ax \sim N(0,\sigma x^{\top}x)$.


I would like to sample from $N(0,\sigma x^{\top}x)$ however, the trouble is that if $n$ is large then this storing the matrix $x^{\top}x$ on my machine is infeasible. So I'm wondering, are there known methods for sampling from such a distribution without storing $x^{\top}x$. Or are tere algorithms for sampling from the random product $Ax$?


**Idea:** For example, can we generate samples from $Ax$ if we only know the eigenvalues of $x^{\top}x$?



Algorithm for economically sampling method for Gaussian matrix product
You can sample from the product $Ax$ in the following way:


Sample a row of $A$ and multiply by $x$. To save memory, forget the row. Sample another row of $A$ and multiply by $x$. To save memory, forget the row. And so on.


An even faster way of sampling from $a^T x$ where $a$ is a row of $A$ is to simply sample from $N(0, \sigma |x|^2)$. This follows from the formula for the [sum of two normal distributions](https://en.wikipedia.org/wiki/Sum_of_normally_distributed_random_variables), which can be straightforwardly generalised to the sum of $n$ normal distributions.


