We consider the task of performing quantum state tomography on a d-level spin qudit, using only measurements of spin projection onto different quantization axes. After introducing a basis of operators closely related to the spherical harmonics, which obey the rotational symmetries of spin qudits, we map our quantum tomography task onto the classical problem of signal recovery on the sphere. We then provide algorithms with O(rd3) serial runtime, parallelizable down to O(rd2) 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≈3d.