Optimization on the biorthogonal manifold

Klaus Glashoff, Michael M. BronsteinarXiv 2016 · DOI · arXiv

Abstract

In this paper, we consider optimization problems w.r.t. to pairs of orthogonal matrices $XY = I$. Problems of this form arise in several applications such as finding shape correspondence in computer graphics. We show that the space of such matrices is a Riemannian manifold, which we call the biorthogonal manifold. To our knowledge, this manifold has not been studied before. We give expressions of tangent space projection, exponential map, and retraction operators of the biorthogonal manifold, and discuss their numerical implementation.

Introduction

In many areas of engineering and computer graphics, finding pairs of matrices that are inverses of each other is a fundamental task. For instance, when mapping the surface of one 3D shape to another, a "round-trip" guarantee is often required: mapping a point from Shape A to Shape B and then back to Shape A should return the point to its original position. Mathematically, this constraint is expressed as $XY = I$.

Traditionally, these problems are solved using penalty methods, which add a term to the objective function to punish deviations from the identity. However, this approach requires a delicate balancing act; low penalties fail to satisfy the constraint, while high penalties lead to numerical instability and slow convergence. This paper proposes a manifold optimization approach, treating the constraint $XY = I$ as a smooth surface—the biorthogonal manifold—and ensuring the algorithm stays strictly on this surface throughout the optimization process.

The Biorthogonal Manifold

The authors formally define the biorthogonal manifold $BO(n)$ as a submanifold of the space of real $n \times n$ matrices. By recognizing that the set of pairs $(X, X^{-1})$ forms a Lie group, the authors leverage clean algebraic structures to derive the necessary geometric tools for optimization.

Geometric Tools

To optimize on this manifold, three key operators are required:

  1. Tangent Space Projection: Standard Euclidean gradients must be projected onto the manifold's tangent plane. This ensures that the search direction respects the local geometry of the constraint.
  2. Retraction and Exponential Map: After taking a step along the tangent plane, the resulting point typically drifts off the manifold. A retraction operator "snaps" the point back onto the manifold surface. The authors utilize matrix exponentials ($\exp(X), \exp(-X)$) for this purpose.
Illustration of Riemannian optimization steps: projection of the gradient onto the tangent space and retraction of the updated point back to the manifold surface.

Numerical Implementation

A significant challenge in manifold optimization is the computational cost of the projection step. The authors show that projecting onto the tangent space of $BO(n)$ involves solving a Generalized Sylvester Equation. By employing Singular Value Decomposition (SVD), they decouple this complex system into $n^2$ independent scalar problems, making the overhead computationally negligible for matrices up to $1000 \times 1000$.

The SVD-based algorithm used to efficiently compute the minimum-norm solution for the tangent space projection.

Experimental Results

The method was evaluated using synthetic random matrices and the FAUST dataset, a benchmark for 3D human shape correspondence.

  • Efficiency: In controlled tests with $100 \times 100$ matrices, the biorthogonal manifold method converged in just 12 iterations, whereas standard penalty methods required 60 iterations.
  • Accuracy: On the FAUST dataset, the manifold approach achieved lower geodesic error than existing state-of-the-art methods, providing more accurate shape correspondences.
  • Feasibility: Unlike penalty methods, which only approximate the constraint, the manifold approach maintains $XY=I$ to within machine precision at every step.

Conclusion

By treating the $XY=I$ constraint as a Riemannian manifold, this work provides a robust and efficient framework for bi-directional mapping problems. While the current use of matrix exponentials for retraction is efficient for moderate dimensions, future work may explore approximate retractions to scale the method to even higher-dimensional data in machine learning applications, such as invertible neural networks.

Summary updated

Abstract

In this paper, we consider optimization problems w.r.t. to pairs of orthogonal matrices $XY = I$. Problems of this form arise in several applications such as finding shape correspondence in computer graphics. We show that the space of such matrices is a Riemannian manifold, which we call the biorthogonal manifold. To our knowledge, this manifold has not been studied before. We give expressions of tangent space projection, exponential map, and retraction operators of the biorthogonal manifold, and discuss their numerical implementation.
BibTeX
@misc{glashoff2016optimization,
  author = {Klaus Glashoff and Michael M. Bronstein},
  title = {{Optimization on the biorthogonal manifold}},
  year = {2016},
  eprint = {1609.04161},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1609.04161},
}

Loading related content...

Figure