# Improved Approximation Algorithms for Orthogonally Constrained Problems Using Semidefinite Optimization

arXiv: https://arxiv.org/abs/2501.02942 · HTML: https://mlsanity.com/paper/2501.02942/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 48 references that are in the map.
- First posted on arXiv 6 Jan 2025.

## Builds on (most cited first, 9 of 9)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Regularization vs. Relaxation: A conic optimization perspective of statistical variable selection](https://mlsanity.com/paper/1510.06083/) (2015)
- [Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints](https://mlsanity.com/paper/2009.10395/) (2020)
- [Certifiably Optimal Low Rank Factor Analysis](https://mlsanity.com/paper/1604.06837/) (2016)
- [Approximating the Little Grothendieck Problem over the Orthogonal and Unitary Groups](https://mlsanity.com/paper/1308.5207/) (2013)
- [Faster exact solution of sparse MaxCut and QUBO problems](https://mlsanity.com/paper/2202.02305/) (2022)
- [A Semidefinite Relaxation for Sums of Heterogeneous Quadratic Forms on the Stiefel Manifold](https://mlsanity.com/paper/2205.13653/) (2022)
- [A Strengthened SDP Relaxation for Quadratic Optimization Over the Stiefel Manifold](https://mlsanity.com/paper/2208.03125/) (2022)

## Abstract (arXiv)

Building on the blueprint from Goemans and Williamson (1995) for the Max-Cut problem, we construct a polynomial-time approximation algorithm for orthogonally constrained quadratic optimization problems. First, we derive a semidefinite relaxation and propose a randomized rounding algorithm to generate feasible solutions from the relaxation. Second, we derive constant-factor approximation guarantees for our algorithm. When optimizing for m orthonormal vectors in dimension n, we leverage strong duality and semidefinite complementary slackness to show that our algorithm achieves a 1/3-approximation ratio. For any m of the form 2q for some integer q, we also construct an instance where the performance of our algorithm is exactly (m+2)/(3m), which can be made arbitrarily close to 1/3 by taking m rightarrow + ∞, hence showing that our analysis is tight.