  We consider the task of performing quantum state tomography on a $d$-state
spin qudit, using only measurements of spin projection onto different
quantization axes. By an exact mapping onto the classical problem of signal
recovery on the sphere, we prove that full reconstruction of arbitrary qudit
states requires a minimal number of measurement axes, $r_d^{\mathrm{min}}$,
that is bounded by $2d-1\le r_d^{\mathrm{min}}\le d^2$. We conjecture that
$r_d^{\mathrm{min}}=2d-1$, which we verify numerically for all $d\le200$. We
then provide algorithms with $O(rd^3)$ serial runtime, parallelizable down to
$O(rd^2)$, for (i) computing a priori upper bounds on the expected error with
which spin projection measurements along $r$ given axes can reconstruct an
unknown qudit state, and (ii) estimating a posteriori the statistical error in
a reconstructed state. Our algorithms motivate a simple randomized tomography
protocol, for which we find that using more measurement axes can yield
substantial benefits that plateau after $r\approx3d$.
