On noisy pattern matching under geometrical constraints

Least-squares pattern matching over the Euclidean space E ⁿ for unordered sets of cardinality p is commonly formulated as a combinatorial optimization problem having complexity p times p!, p≫n. Since p may be 10³ or larger in typical applications, less than satisfactory suboptimal methods are usually used. A powerful hybrid approach is described which casts the pattern matching problem in a differentiable setting using rigid motion constraints which often apply and reduces the complexity to l₂₁n⁴ +l₁₂p³, where l ₁₂ and l₂₁ are the number of iterations required by procedures based on steepest ascent and singular value decomposition (SVD), respectively