0
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ The usual convention is that the normal distribution is parametrised as $N(0, \sigma^2)$ where $\sigma$ is the standard deviation. You're using $\sigma$ instead of $\sigma^2$. Is this on purpose? $\endgroup$
    – wlad
    Nov 11, 2020 at 13:04
  • $\begingroup$ Oh, ya its on purpouse but for my purpouse it didn't matter. I can equally well-take the $\sigma^2$ convention. $\endgroup$
    – ABIM
    Nov 11, 2020 at 13:10

1 Answer 1

1
$\begingroup$

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, which can be straightforwardly generalised to the sum of $n$ normal distributions.

$\endgroup$
7
  • $\begingroup$ I like this idea. However, it may take a long time to loop over. Would you happen to know of another way? $\endgroup$
    – ABIM
    Nov 11, 2020 at 12:07
  • $\begingroup$ @Zorn'sLama Is there a way to sample from $a^T x$ where $a$ is a vector of iid samples from $N(0, \sigma)$? I'll try and think about this $\endgroup$
    – wlad
    Nov 11, 2020 at 12:10
  • $\begingroup$ Ah, $a$ follows an axis-symmetric distribution. So I think that to sample from $a^T x$, you need only to sample from $N(0, \sigma)$ and multiply by $|x|$. Does that make sense? $\endgroup$
    – wlad
    Nov 11, 2020 at 12:15
  • $\begingroup$ Actually, this works great. Thank you ogogmad! $\endgroup$
    – ABIM
    Nov 11, 2020 at 12:23
  • 1
    $\begingroup$ It follows from the rotational symmetry of $N(0, \sigma \oplus \sigma \oplus \dotsb \oplus \sigma)$. Consider the case when $x$ is parallel to one of the coordinate axes; it's clear that $a^T x$ follows the same distribution as $N(0, \sigma |x|)$. Now using rotational symmetry of the distribution of $a$, simply change coordinates so that $x$ is parallel to one of the coordinate axes $\endgroup$
    – wlad
    Nov 11, 2020 at 12:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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