I have two sets of points, P and Q, where Q is a transformation of P (rotation, translation and scaling). The pairing of points is unknown. How would I go about computing an estimate of the transform?
If your point clouds are truly similar, you can
center them on their centroid,
rescale them so that the average distance to the origin is unit,
rotate them so that the main axis of their ellipse of inertia is horizontal.
Then they will perfectly overlap. The transformation can be retrieved from the difference between the angles, scales and translation vectors.
Unfortunately, this method falls short when the two axis of inertia have the same length. In such a case you can try other moments, but I can't give you a bulletproof procedure (the main reason is that in symmetrical cases, the rotation cannot be uniquely determined).
If the two point clouds are significantly non-similar, the above will fail. You can try a RANSAC approach instead, by matching two random pairs of points, computing the similarity transformation and the total matching error (or perform full ICP from this tentative transformation).