We consider the problem of consistently matching multiple sets of elements to each other, which is a common task in fields such as computer vision. To solve the underlying NP-hard objective, existing methods often relax or approximate it, but end up with unsatisfying empirical performance due to their inexact objectives. We propose a coordinate update algorithm that directly solves the exact objective. By using the pairwise alignment information to build an undirected graph and initializing the permutation matrices along the edges of its Maximum Spanning Tree, our algorithm successfully avoids bad local optima. Theoretically, with high probability our algorithm guarantees we can solve this problem optimally on data with reasonable noise. Empirically, our algorithm consistently and significantly outperforms existing methods on several benchmark tasks on real datasets.