Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation

Florian Bernard, Daniel Cremers, Anders Johan Thunberg

Overview

Researchers have developed a new algorithm that finds globally optimal solutions to quadratic problems on the Stiefel manifold while simultaneously promoting sparsity. By exploiting "orthogonal invariance," the method rotates the solution within its optimal subspace to produce sparse matrices. This significantly improves the accuracy of downstream tasks like matching points across multiple images, a problem known as permutation synchronisation.

The Problem: The Gap Between Continuous and Discrete

Many complex combinatorial problems—like matching graphs, clustering data, or synchronising permutations across a set of images—are "NP-hard," meaning they are computationally nightmarish to solve exactly. To get around this, researchers often use spectral relaxations. They take a discrete problem (like finding a permutation matrix) and "relax" it into a continuous one over the Stiefel manifold (the set of matrices with mutually orthogonal columns of unit length).

Standard solvers use eigenvalue decomposition to find a mathematically "perfect" global optimum for these relaxed problems. However, the resulting matrix is usually dense and "fuzzy." The original discrete problem, on the other hand, requires a sparse, crisp matrix (like a permutation matrix where most entries are zero).

The core challenge is finding a solution that is both globally optimal for the relaxed problem and sparse enough to be easily converted back into a discrete solution. Previous methods usually had to sacrifice one property for the other.

The Solution: Exploiting Orthogonal Invariance

The authors propose a modification to the classic Orthogonal Iteration algorithm, a well-known numerical method used to find the dominant eigenvectors of a matrix.

Their key insight lies in orthogonal invariance. In these quadratic problems, if a matrix $U$ is an optimal solution, then $U$ multiplied by any rotation matrix $Q$ is also an optimal solution. This provides "extra degrees of freedom."

Instead of just looking for any optimal $U$, the researchers use these degrees of freedom to "rotate" the solution toward a sparser representation. They introduce a sparsity-promoting matrix, $Z(U_t)$, into the iterative step:

  1. Standard Step: Multiply the current estimate by the data matrix $W$.
  2. The "Sparse" Twist: Multiply by $Z(U_t)$, which is derived from the gradient of a secondary objective (like an $\ell_p$-norm where $p > 2$). This step "steers" the matrix toward having a few large elements and many near-zero elements.
  3. Orthogonalize: Perform a QR decomposition to keep the matrix on the Stiefel manifold.

Because they are rotating within the optimal subspace, they can guarantee the final result is still a global optimiser of the original problem—essentially getting sparsity "for free."

Application and Datasets

The paper evaluates the algorithm on two main fronts:

  • Real-World Data: The CMU House Sequence, a classic computer vision dataset consisting of 111 frames of a toy house. The goal is to "synchronise" point matchings across all frames simultaneously.
  • Synthetic Data: Random partial permutation matrices generated to test varying parameters like universe size, observation rate (missing data), and error rate (noise).
Qualitative comparison of point matching on the CMU House dataset.

By obtaining a sparse continuous solution, the final step of "rounding" the result to a discrete permutation matrix becomes much more accurate. The "fuzzy" parts of the matrix are already mostly gone before the rounding happens, leading to visibly better matching results.

Key Results

Quantitative results showing fscore, objective, and runtime comparisons.
  • Superior Accuracy: On the CMU House dataset, the proposed method consistently achieved higher fscores (a measure of precision and recall) and higher objective values than existing spectral and non-negative matrix factorisation baselines.
  • Robustness to Noise: In synthetic tests, the method maintained high accuracy even as the error rate increased or the observation rate decreased, outperforming standard approaches.
  • Efficiency: Despite the extra sparsity step, the algorithm's runtime is comparable to the fastest existing spectral methods and significantly faster than alternating minimisation techniques.

Limitations and Future Work

The authors note a few constraints to their approach:

  • Subspace Limits: The amount of sparsity achievable is fundamentally limited by the "sparsest possible basis" for the dominant subspace of the data matrix. If the optimal subspace itself doesn't contain sparse vectors, the algorithm cannot force them to exist.
  • Eigenvalue Assumptions: The theoretical proof of convergence for the sparse rotation relies on the top eigenvalues being equal (or nearly equal). While this is often true in "clean" synchronisation problems, it might not hold in other domains.
  • Universal Sparsity: While the method works well for permutations, different types of "sparsity" might require different choices for the $Z(U_t)$ function, which remains an open area for research.

Summary updated

Abstract

We address the non-convex optimisation problem of finding a sparse matrix on the Stiefel manifold (matrices with mutually orthogonal columns of unit length) that maximises (or minimises) a quadratic objective function. Optimisation problems on the Stiefel manifold occur for example in spectral relaxations of various combinatorial problems, such as graph matching, clustering, or permutation synchronisation. Although sparsity is a desirable property in such settings, it is mostly neglected in spectral formulations since existing solvers, e.g. based on eigenvalue decomposition, are unable to account for sparsity while at the same time maintaining global optimality guarantees. We fill this gap and propose a simple yet effective sparsity-promoting modification of the Orthogonal Iteration algorithm for finding the dominant eigenspace of a matrix. By doing so, we can guarantee that our method finds a Stiefel matrix that is globally optimal with respect to the quadratic objective function, while in addition being sparse. As a motivating application we consider the task of permutation synchronisation, which can be understood as a constrained clustering problem that has particular relevance for matching multiple images or 3D shapes in computer vision, computer graphics, and beyond. We demonstrate that the proposed approach outperforms previous methods in this domain.
BibTeX
@inproceedings{bernard2021sparse,
  author = {Florian Bernard and Daniel Cremers and Anders Johan Thunberg},
  title = {{Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=sl_0rQmHxQk},
}
Figure