Approximating the little Grothendieck problem over the orthogonal and unitary groups
- 25 March 2016
- journal article
- research article
- Published by Springer Nature in Mathematical Programming
- Vol. 160 (1-2) , 433-475
Abstract
The little Grothendieck problem consists of maximizing \(\sum _{ij}C_{ij}x_ix_j\) for a positive semidefinite matrix C, over binary variables \(x_i\in \{\pm 1\}\). In this paper we focus on a natural generalization of this problem, the little Grothendieck problem over the orthogonal group. Given \(C\in \mathbb {R}^{dn\times dn}\) a positive semidefinite matrix, the objective is to maximize \(\sum _{ij}{\text {tr}}\left( C^T_{ij}O_iO_j^T\right) \) restricting \(O_i\) to take values in the group of orthogonal matrices \(\mathcal {O}_d\), where \(C_{ij}\) denotes the (ij)-th \(d\times d\) block of C. We propose an approximation algorithm, which we refer to as Orthogonal-Cut, to solve the little Grothendieck problem over the group of orthogonal matrices \(\mathcal {O}_d\) and show a constant approximation ratio. Our method is based on semidefinite programming. For a given \(d\ge 1\), we show a constant approximation ratio of \(\alpha _{\mathbb {R}}(d)^2\), where \(\alpha _{\mathbb {R}}(d)\) is the expected average singular value of a \(d\times d\) matrix with random Gaussian \(\mathcal {N}\left( 0,\frac{1}{d}\right) \) i.i.d. entries. For \(d=1\) we recover the known \(\alpha _{\mathbb {R}}(1)^2=2/\pi \) approximation guarantee for the classical little Grothendieck problem. Our algorithm and analysis naturally extends to the complex valued case also providing a constant approximation ratio for the analogous little Grothendieck problem over the Unitary Group \(\mathcal {U}_d\). Orthogonal-Cut also serves as an approximation algorithm for several applications, including the Procrustes problem where it improves over the best previously known approximation ratio of \(\frac{1}{2\sqrt{2}}\). The little Grothendieck problem falls under the larger class of problems approximated by a recent algorithm proposed in the context of the non-commutative Grothendieck inequality. Nonetheless, our approach is simpler and provides better approximation with matching integrality gaps. Finally, we also provide an improved approximation algorithm for the more general little Grothendieck problem over the orthogonal (or unitary) group with rank constraints, recovering, when \(d=1\), the sharp, known ratios.
Keywords
All Related Versions
Funding Information
- Air Force Office of Scientific Research (FA9550-12-1-0317)
- Air Force Office of Scientific Research (FA9550-13-1-0076)
- National Institute of General Medical Sciences (R01GM090200)
- Simons Foundation (LTR DTD 06-05-2012)
This publication has 30 references indexed in Scilit:
- Three-Dimensional Structure Determination from Common Lines in Cryo-EM by Eigenvectors and Semidefinite ProgrammingSIAM Journal on Imaging Sciences, 2011
- Angular synchronization by eigenvectors and semidefinite programmingApplied and Computational Harmonic Analysis, 2011
- Moment inequalities for sums of random matrices and their applications in optimizationMathematical Programming, 2009
- On approximating complex quadratic optimization problems via semidefinite programming relaxationsMathematical Programming, 2006
- Sums of random symmetric matrices and quadratic optimization under orthogonality constraintsMathematical Programming, 2006
- On maximization of quadratic form over intersection of ellipsoids with common centerMathematical Programming, 1999
- Semidefinite relaxation and nonconvex quadratic optimizationOptimization Methods and Software, 1998
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programmingJournal of the ACM, 1995
- Closest Unitary, Orthogonal and Hermitian Operators to a Given OperatorMathematics Magazine, 1975
- Some metric inequalities in the space of matricesProceedings of the American Mathematical Society, 1955