## Abstract

The little Grothendieck problem consists of maximizing ∑ _{i} _{j}C_{i} _{j}x_{i}x_{j} for a positive semidefinite matrix C, over binary variables x_{i}∈ { ± 1 }. In this paper we focus on a natural generalization of this problem, the little Grothendieck problem over the orthogonal group. Given C∈ R^{d} ^{n} ^{×} ^{d} ^{n} a positive semidefinite matrix, the objective is to maximize ∑ijtr(CijTOiOjT) restricting O_{i} to take values in the group of orthogonal matrices O_{d}, where C_{i} _{j} denotes the (ij)-th d× 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 O_{d} and show a constant approximation ratio. Our method is based on semidefinite programming. For a given d≥ 1 , we show a constant approximation ratio of α_{R}(d) ^{2}, where α_{R}(d) is the expected average singular value of a d× d matrix with random Gaussian N(0,1d) i.i.d. entries. For d= 1 we recover the known α_{R}(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 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 122. 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.

Original language | English (US) |
---|---|

Pages (from-to) | 433-475 |

Number of pages | 43 |

Journal | Mathematical Programming |

Volume | 160 |

Issue number | 1-2 |

DOIs | |

State | Published - Nov 1 2016 |

## All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)

## Keywords

- Approximation algorithms
- Procrustes problem
- Semidefinite programming