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

Improve this question
$\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
    Commented 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
    Commented Nov 11, 2020 at 13:10

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented 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
    Commented 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
    Commented Nov 11, 2020 at 12:15
  • $\begingroup$ Actually, this works great. Thank you ogogmad! $\endgroup$
    – ABIM
    Commented 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
    Commented Nov 11, 2020 at 12:32

You must log in to answer this question.

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