A Semidefinite Relaxation for Sums of Heterogeneous Quadratic Forms on the Stiefel Manifold

Kyle Gilman, Sam Burer, Laura BalzanoSIAM J. Matrix Anal. Appl 2022

TL;DR

This paper introduces a novel semidefinite programming (SDP) relaxation for a challenging optimization problem involving sums of heterogeneous quadratic forms on the Stiefel manifold. This relaxation not only provides a way to certify global optimality for solutions found by iterative methods but also proves to be tight for important applications like Heteroscedastic Probabilistic Principal Component Analysis (HPPCA).

What Problem Does This Paper Address?

Many modern signal processing and machine learning tasks, such as Heteroscedastic Probabilistic Principal Component Analysis (HPPCA), involve optimizing a sum of heterogeneous quadratic forms over the Stiefel manifold. This is a difficult problem because the Stiefel manifold constraint (requiring orthonormal columns) makes the problem non-convex, and the objective function is a sum of weighted quadratic forms that are not separable. Traditional iterative methods can get stuck in local optima, and guaranteeing global optimality is a significant challenge. Existing theoretical conditions for global optimality are often hard to check in practice.

Methods

The authors propose a new semidefinite programming (SDP) relaxation for the original non-convex problem. This involves "lifting" the problem into a higher-dimensional space of positive semidefinite matrices and relaxing the rank constraints. A key contribution is the development of a "dual certificate" that allows for a computationally efficient check of whether a candidate solution found by an iterative solver is globally optimal. They also analyze the conditions under which their SDP relaxation is "tight," meaning it yields the same optimal solution as the original non-convex problem. This tightness is shown to hold for problems where the underlying matrices are "close-to jointly diagonalizable" (CJD), a property that is demonstrated to hold for the HPPCA problem.

Datasets

Not discussed in the paper. The paper focuses on synthetic data generation for experiments.

Key Insights and Ideas

  • Global Optimality Certificate: The paper provides a practical way to verify if a locally found solution is indeed the global optimum. This is a significant advancement for non-convex optimization problems where guaranteeing global optimality is notoriously difficult.
  • Tightness for "Almost Commuting" Matrices: The authors show that their SDP relaxation is tight not just for perfectly jointly diagonalizable matrices (a known case where tightness holds) but also for matrices that are "close-to" jointly diagonalizable. This broadens the applicability of their method.
  • HPPCA Connection: A crucial insight is that the matrices arising in the HPPCA problem exhibit the "close-to jointly diagonalizable" property, especially as the number of data samples increases or noise levels become more uniform. This provides strong theoretical backing for the effectiveness of their SDP relaxation in this important application.
  • Computational Efficiency: The proposed global optimality certificate is computationally much cheaper than solving the full SDP relaxation, making it practical for high-dimensional problems.

Key Results

  • A novel SDP relaxation for sums of heterogeneous quadratic forms on the Stiefel manifold is derived.
  • A dual certificate is established, enabling a computationally efficient feasibility problem to certify global optimality of candidate solutions.
  • Sufficient conditions for the tightness of the SDP relaxation are provided, particularly for "close-to jointly diagonalizable" (CJD) problems.
  • It is shown that the HPPCA problem possesses the CJD property, implying the SDP relaxation is tight for this application.
  • Numerical experiments validate the global optimality certificate and the conditions for SDP tightness across various problem settings.

Limitations and Future Work

  • Sufficient Conditions: The conditions derived for the SDP tightness and the rank-one property are sufficient, not necessary. This means there might be cases where the SDP is tight even if these conditions are not met.
  • Computational Cost of Certificate: While the certificate is more efficient than solving the full SDP, it still involves solving a feasibility problem with several d x d linear matrix inequalities, which can be computationally intensive for very large dimensions.
  • Exact Stationary Points: The global optimality certificate (Theorem 4.1) relies on the candidate solution being an exact stationary point. In practice, iterative solvers only yield approximate stationary points, so the certificate might be inexact.
  • Future Work: The authors suggest exploring extensions of their theory to more general cases, quantifying the size of the region where the SDP has the rank-one property, and investigating randomized algorithms to further reduce the computational cost for very large-scale problems. They also mention the potential for generalizing their approach to other related problems.

Summary updated

Abstract

We study the maximization of sums of heterogeneous quadratic forms over the Stiefel manifold, a nonconvex problem that arises in several modern signal processing and machine learning applications such as heteroscedastic probabilistic principal component analysis (HPPCA). In this work, we derive a novel semidefinite program (SDP) relaxation of the original problem and study a few of its theoretical properties. We prove a global optimality certificate for the original nonconvex problem via a dual certificate, which leads to a simple feasibility problem to certify global optimality of a candidate solution on the Stiefel manifold. In addition, our relaxation reduces to an assignment linear program for jointly diagonalizable problems and is therefore known to be tight in that case. We generalize this result to show that it is also tight for close-to jointly diagonalizable problems, and we show that the HPPCA problem has this characteristic. Numerical results validate our global optimality certificate and sufficient conditions for when the SDP is tight in various problem settings.
BibTeX
@article{gilman2022semidefinite,
  author = {Kyle Gilman and Sam Burer and Laura Balzano},
  title = {{A Semidefinite Relaxation for Sums of Heterogeneous Quadratic Forms on the Stiefel Manifold}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2022},
}
Figure