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

Kyle Gilman; Samuel Burer; Laura Balzano

doi:10.1137/23M1545136

Back

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

Journal article

Peer reviewed

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

Kyle Gilman, Samuel Burer and Laura Balzano

SIAM journal on matrix analysis and applications, Vol.46(2), pp.1091-1116

06/30/2025

DOI: 10.1137/23M1545136

View Online

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.

semidefinite programming

heteroscedastic probabilistic principal component analy-sis

Stiefel manifold optimization

Details

Title: Subtitle: A Semidefinite Relaxation for Sums of Heterogeneous Quadratic Forms on the Stiefel Manifold
Creators: Kyle Gilman
Samuel Burer
Laura Balzano
Resource Type: Journal article
Publication Details: SIAM journal on matrix analysis and applications, Vol.46(2), pp.1091-1116
Publisher: SIAM PUBLICATIONS
DOI: 10.1137/23M1545136
ISSN: 0895-4798
eISSN: 1095-7162
Grant note: NSF CAREER award: CCF1845076 ARO YIP award: W911NF1910027 AFOSR YIP: FA9550-19-1-0026 NSF BIG-DATA award: IIS-1838179 NSF: CCF-2331590
The first and third authors were supported in part by NSF CAREER award CCF1845076, ARO YIP award W911NF1910027, AFOSR YIP award FA9550-19-1-0026, and NSF BIG-DATA award IIS-1838179. The third author was also supported by NSF award CCF-2331590.
Language: English
Date published: 06/30/2025
Academic Unit: Business Analytics
Record Identifier: 9984813149102771

Metrics

1 Record Views