# uniform sampling of the sphere w.r.t. inner products other than the usual one

I will have a small (usually 2 or 3, probably no bigger than 6) positive integer $n$
and symmetric positive-definite real $n$-by-$n$ matrices $A$,
and will want to sample an $\:\mathbf{R}^n$-valued$\:$ random variable $\mathbf{x}$ such that

for any/all linear map(s) $\: f : \mathbf{R}^n \to \mathbf{R}^n \:$ such that $\Big[$for all vectors $v$, $\;\;v^{\hspace{0.015 in}T} Av\:=\:\left(||f(v)||_2\right)^2\;\;\Big]$,
$\big[||f(\mathbf{x})||_2 = 1 \:$ almost surely$\big]$ and $\big[f(\mathbf{x})$ is distributed uniformly on the unit sphere$\big]$

.

The way I thought of to do this is to Gram-Schmidt orthonormalize the standard basis
with respect to the inner product induced by $A$, and then take the linear combination with
coefficients given as the entries of a uniform sample from the unit sphere. $\:$ However, since I
will be sampling from $\mathbf{x}$ only once for each $A$, I'm hoping for a rather more efficient method.

Is there any faster way to do the sampling I want?

(The matrices will be changing somewhat slowly, which might help.)

-
 If I understand correctly, you want to sample the set $S = \{v: v^TAv=1\}$ in such a way that the distribution is uniform when $S$ is linearly mapped to a sphere? Then it should be $v^TAv=\|f(v)\|_2^2$, given that the left-hand side is quadratic in $v$, right? Sorry, I don't have an answer to your actual question. – Rahul Narain Aug 25 '12 at 9:20 Yes, and I corrected the equation. $\:$ – Ricky Demer Aug 25 '12 at 10:11

I think we can dispense with the "all linear maps" part, since all such linear maps are given by one such map followed by an arbitrary rotation of the unit sphere, which doesn't affect the uniform distribution; thus we can focus on a particular such map, $f(x)=A^{1/2}x$.
The problem is that you can easily apply $A$, but not $A^{-1/2}$. If the eigenvalues of $A$ are sufficiently similar and you have an efficient way to bound the least eigenvalue $\def\lmin{\lambda_{\text{min}}}\lmin\gt\kappa$ of $A$, you can get around this using rejection sampling: sample $x$ uniformly from the unit ball, reject the sample if $x^\top Ax\gt\kappa$, else divide it by $\sqrt{x^\top Ax}$ and use it. (Ideally, if you know $\lmin$, then $\kappa=\lmin$ yields the lowest rejection rate.)
 Your first paragraph is the reason I wrote "any/all". $\:$ – Ricky Demer Aug 26 '12 at 3:49