Given two sets of vectors, how can I find the rotation needed to rotate one set onto the other?
The sets are ordered and of same size, with vector n from set 1 corresponding to vector n from set 2.
(background info: I have a camera looking at some defined points in 3D space and I'm trying to find the orientation of the camera. So this is probably a minimization problem, but I don't know how to tackle it ... )
If there is a "perfect" rotation that carries your first set exactly to the second set, then the rotation is uniquely determined by choosing any two vectors and computing the matrix that rotates the two vectors to their two targets. A formula for the rotation should be easy to find, e.g. there is the Rodrigues formula to give a rotation matrix that rotates one vector direction to another.
For your general problem, note that a good solution should carry the mean of a subset of vectors (probably ideally pointed somewhat in the same direction) to the direction of the mean of the corresponding set of target vectors. So you could parametrize rotation matrices by the angles of rotation about fixed standard basis vectors, and then search for the standard-basis rotation angle parameters that give you the best average angular error when you choose a few subsets of vectors and rotate their means to the corresponding target means. Then you can refine the solution by initializing with your initially found solution, and using an even larger number of smaller sets of vectors to define the same kind of optimization problem. A programming language like matlab will make this very easy to implement, and it should run very fast and converge nicely if your input isn't too crazy and if you organize the successive optimization strategy properly.