The Orthogonal Procrustes Problem
The exact, closed-form way to align two shapes or embedding spaces via SVD.
On this page
Beginner: imagine you have two versions of the same shape — one rotated relative to the other — and you want to find the exact rotation that lines them up as closely as possible. The orthogonal Procrustes problem is precisely this: find the best rotation (or reflection) matrix that aligns one set of points to another, minimizing the total squared distance between corresponding points.
Intermediate: remarkably, this has an exact, closed-form answer, and it comes directly from the SVD (section 1.10): compute the cross-covariance matrix between the two point sets, take its SVD UΣVᵀ, and the optimal rotation is simply R = UVᵀ — no iterative optimization needed at all.
Advanced: this is the standard tool for embedding alignment — for instance, aligning word-embedding spaces trained independently on two different languages, so that a word and its translation end up at (approximately) the same point after applying the optimal rotation.
Minimizing ‖AR − B‖²_F over rotations R is equivalent to maximizing a simpler quantity. Expand the squared Frobenius norm using ‖X‖²_F = trace(XᵀX) (section 1.20):
The first term equals trace(AᵀA) by the cyclic property (section 1.23) since RᵀR = I, and the last term doesn't involve R at all — so minimizing the whole expression over R is exactly equivalent to maximizing trace(RᵀAᵀB) = trace(RᵀM) where M = AᵀB = UΣVᵀ. Substitute the SVD and use cyclic invariance again:
Z is a product of orthogonal matrices, so it's orthogonal too, meaning every entry of Z satisfies |Z_{ii}| ≤ 1. Since Σ has non-negative diagonal entries, trace(ZΣ) = Σᵢ Z_{ii}σᵢ is maximized exactly when every Z_{ii} = 1, i.e. when Z = I. Solve VᵀRᵀU = I for R: left-multiply by V to get RᵀU = V (using VVᵀ = I), then right-multiply by Uᵀ to get Rᵀ = VUᵀ (using UUᵀ = I). Transposing both sides gives R = UVᵀ — the closed form, derived entirely from properties of trace and orthogonal matrices already covered in this chapter, with no iterative search required.
Where this is used: every cross-lingual embedding alignment pipeline and shape-registration tool that calls this a "one-line SVD solution" is relying on exactly this proof — it's also why the reflection-vs-rotation subtlety noted below is unavoidable: the proof only ever concluded Z = I, not that det(R) = +1.
Drag to rotate the orange shape by hand, or let the closed-form SVD solution snap it into perfect alignment instantly.
Three lines after the SVD call, and the alignment is exact — this is the entire algorithm used in real embedding-alignment pipelines. The from-scratch tabs get the same 2x2 SVD by hand, via the closed-form eigendecomposition of MᵀM.
#include <cmath>
#include <cstdio>
#include <vector>
#include <random>
#include <array>
using Mat2 = std::array<std::array<double, 2>, 2>;
using Vec2 = std::array<double, 2>;
using Points = std::vector<Vec2>;
Points matmulPts(const Points& X, const Mat2& Y) {
Points R(X.size());
for (size_t i = 0; i < X.size(); ++i)
for (int j = 0; j < 2; ++j)
R[i][j] = X[i][0] * Y[0][j] + X[i][1] * Y[1][j];
return R;
}
Mat2 crossCov(const Points& A, const Points& B) {
// A^T B, a 2x2 matrix.
Mat2 M{};
for (size_t i = 0; i < A.size(); ++i)
for (int r = 0; r < 2; ++r)
for (int c = 0; c < 2; ++c) M[r][c] += A[i][r] * B[i][c];
return M;
}
Mat2 matmul2(const Mat2& X, const Mat2& Y) {
Mat2 R{};
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j)
for (int k = 0; k < 2; ++k) R[i][j] += X[i][k] * Y[k][j];
return R;
}
Mat2 transpose2(const Mat2& X) {
return {{{X[0][0], X[1][0]}, {X[0][1], X[1][1]}}};
}
void eigSymmetric2x2(const Mat2& M, double lambda[2], Vec2 vec[2]) {
double a = M[0][0], b = M[0][1], d = M[1][1];
double tr = a + d, det = a * d - b * b;
double disc = std::sqrt(std::max(tr * tr - 4 * det, 0.0));
lambda[0] = (tr + disc) / 2;
lambda[1] = (tr - disc) / 2;
for (int k = 0; k < 2; ++k) {
Vec2 v = std::fabs(b) > 1e-12 ? Vec2{b, lambda[k] - a} : Vec2{1.0, 0.0};
double norm = std::sqrt(v[0] * v[0] + v[1] * v[1]);
vec[k] = {v[0] / norm, v[1] / norm};
}
}
int main() {
std::mt19937 rng(0);
std::normal_distribution<double> gauss(0.0, 1.0);
Points target(20);
for (auto& p : target) { p[0] = gauss(rng); p[1] = gauss(rng); }
double theta = 0.7;
Mat2 rot = {{{std::cos(theta), -std::sin(theta)}, {std::sin(theta), std::cos(theta)}}};
Points source = matmulPts(target, transpose2(rot)); // a rotated copy of the same shape
Mat2 M = crossCov(source, target);
Mat2 MtM = matmul2(transpose2(M), M);
double lambda[2];
Vec2 eigvec[2];
eigSymmetric2x2(MtM, lambda, eigvec);
int order[2] = {lambda[0] > lambda[1] ? 0 : 1, lambda[0] > lambda[1] ? 1 : 0};
double S[2];
Mat2 V{}, U{};
for (int idx = 0; idx < 2; ++idx) {
int k = order[idx];
S[idx] = std::sqrt(std::max(lambda[k], 0.0));
V[0][idx] = eigvec[k][0];
V[1][idx] = eigvec[k][1];
double Mv0 = M[0][0] * eigvec[k][0] + M[0][1] * eigvec[k][1];
double Mv1 = M[1][0] * eigvec[k][0] + M[1][1] * eigvec[k][1];
U[0][idx] = Mv0 / S[idx];
U[1][idx] = Mv1 / S[idx];
}
Mat2 R = matmul2(U, transpose2(V)); // the optimal alignment rotation
Points aligned = matmulPts(source, R);
double maxErr = 0.0;
for (size_t i = 0; i < target.size(); ++i)
for (int j = 0; j < 2; ++j)
maxErr = std::max(maxErr, std::fabs(aligned[i][j] - target[i][j]));
std::printf("max alignment error: %.10f\n", maxErr); // ~0 -- perfect recovery
return 0;
}- Cross-lingual word embeddings — aligning independently trained embedding spaces from two languages using a small bilingual dictionary as anchor points, then applying Procrustes to the rest of the vocabulary.
- Shape analysis and computer vision — comparing 3D scanned objects or anatomical landmarks that were captured at arbitrary orientations.
- Comparing neural network representations across different training runs or random seeds — Procrustes alignment is a standard tool for checking whether two networks learned "the same" internal representation, just rotated.
- Forgetting the two point sets must already be correctly matched (point i in set A corresponds to point i in set B) — Procrustes solves for the best rotation given a known correspondence, it does not discover the correspondence itself.
- Swapping the order to
R = VUᵀ— the correct formula depends on which matrix the cross-covariance is built from; withM = AᵀB = UΣVᵀas defined above the answer isR = UVᵀ, notVUᵀ(defining the cross-covariance the other way round,BᵀA, would swap U and V and flip which order is correct) — always double-check against a known test case.
Going deeper
A subtlety: the raw SVD solution can produce a reflection rather than a pure rotation if the determinant of UVᵀ comes out negative — the standard fix flips the sign of the last column of V (or the corresponding singular value) to force a proper rotation when one is specifically required.
At the master level: Procrustes analysis more generally also allows solving for an optimal scale factor and translation alongside the rotation (full "similarity transformation" Procrustes) — the rotation piece is unchanged, computed exactly as above, with scale and translation solved for separately in closed form once the optimal rotation is known.