title: Approximating the Little Grothendieck Problem over the Orthogonal and Unitary Groups.
abstract: The little Grothendieck problem consists of maximizing ΣijCijxixjfor a positive semidef-inite matrixC, over binary variablesxi∈ {±1}. In this paper we focus on a natural generalization of this problem, the little Grothendieck problem over the orthogonal group. GivenC∈ ℝdn×dna positive semidefinite matrix, the objective is to maximize [Formula: see text] restrictingOito take values in the group of orthogonal matrices [Formula: see text], whereCijdenotes the (ij)-thd×dblock ofC.We propose an approximation algorithm, which we refer to asOrthogonal-Cut, to solve the little Grothendieck problem over the group of orthogonal matrices [Formula: see text] and show a constant approximation ratio. Our method is based on semidefinite programming. For a givend≥ 1, we show a constant approximation ratio ofαℝ(d)2, whereαℝ(d) is the expected average singular value of ad×dmatrix with random Gaussian [Formula: see text] i.i.d. entries. Ford= 1 we recover the knownαℝ(1)2= 2/π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 [Formula: see text]. 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 [Formula: see text]. 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, whend= 1, the sharp, known ratios.
authors.affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Masachusetts 02142, USA.
authors.forename: Afonso S
authors.initials: AS
authors.lastname: Bandeira
authors.affiliation: Department of Mathematics, The University of Texas at Austin, Austin, Texas 78712, USA.
authors.forename: Christopher
authors.initials: C
authors.lastname: Kennedy
authors.affiliation: Department of Mathematics and PACM, Princeton University, Princeton, New Jersey 08544, USA.
authors.forename: Amit
authors.initials: A
authors.lastname: Singer
keywords: Approximation algorithms; Procrustes problem; Semidefinite programming