How can I uniformly draw points from an ellipsoid?

Specifically, given a positive definite matrix $A \in \mathbb{R}^{n \times n}$, how can I efficiently generate points $x \in \mathbb{R}^n$ that satisfy $x^TAx \leq 1$? I know how to do this when the matrix is just the identity, because then this question reduces to simply generating uniformly from the unit ball. However, I am not sure how to extend this to drawing from a general ellipsoid (if that is the correct term?).

For a ball centered at the origin with radius r, I would simply generate $Z_1, \dots, Z_n$ all iid $N(0,1)$ random variables. Then if $Z := (Z_1, \dots, Z_n)$ and $U$ is $UNIF(0,r)$ then we have that

$$\frac{UZ}{\|Z\|} \sim UNIF(B_r(0))$$

However I am not sure how to generalize this process to an ellipsoid...

• You can draw uniform numbers in any bounding box of the ellipsoid and keep those such that $x^TAx \leq 1$. – Yves Daoust Nov 17 '14 at 7:51
• Yes but this method wouldn't be very efficient. I want one that scales decently well with n. The method you propose would be quite bad for n = 100 (for example) since the probability of accepting points would be very low. – Bob Nov 17 '14 at 8:35
• That's right, for $n=100$, the probability would be infinitesimal. – Yves Daoust Nov 17 '14 at 9:09

Diagonalize $A$, then compute the eigenvectors which will be orthogonal. The inverses of the square roots of the corresponding eigenvalues will be the lengths of the three semiaxes. You can now simply draw vectors from the unit ball and interpret their coefficients in terms of the eigenbasis; scaling each coefficient by the length of the corresponding semiaxis will "fill the ellipsoid", so to speak.