Approximating the little Grothendieck problem over the orthogonal and unitary groups

DOI10.1007/S10107-016-0993-7zbMATH Open1356.90101arXiv1308.5207OpenAlexW2100685794WikidataQ42746594 ScholiaQ42746594MaRDI QIDQ344957FDOQ344957

Authors: Afonso S. Bandeira, A. Singer, Christopher A. Kennedy 

Publication date: 25 November 2016

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Abstract: The little Grothendieck problem consists of maximizing $su{m}_{ij}{C}_{ij}{x}_i{x}_j$ over binary variables $x_{i}inpm1$, where C is a positive semidefinite matrix. In this paper we focus on a natural generalization of this problem, the little Grothendieck problem over the orthogonal group. Given C a dn x dn positive semidefinite matrix, the objective is to maximize $su{m}_{ij}Tr(C_{ij}^T{O}_i{O}_j^T)$ restricting $O_i$ to take values in the group of orthogonal matrices, where $C_{ij}$ denotes the (ij)-th d x d block of C. We propose an approximation algorithm, which we refer to as Orthogonal-Cut, to solve this problem and show a constant approximation ratio. Our method is based on semidefinite programming. For a given $dgeq1$, we show a constant approximation ratio of $alph{a}_R(d{)}^2$, where $alph{a}_R(d)$ is the expected average singular value of a d x d matrix with random Gaussian $N(0,1/d)$ i.i.d. entries. For d=1 we recover the known $alph{a}_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 problem over the Unitary Group. 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~$frac12sqrt2$. The little Grothendieck problem falls under the class of problems approximated by a recent algorithm proposed in the context of the non-commutative Grothendieck inequality. Nonetheless, our approach is simpler and it provides a more efficient algorithm with better approximation ratios and 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.

Full work available at URL: https://arxiv.org/abs/1308.5207

Recommendations

• The positive semidefinite Grothendieck problem with rank constraint
• Towards computing the Grothendieck constant
• Efficient rounding for the noncommutative Grothendieck inequality
• Efficient Rounding for the Noncommutative Grothendieck Inequality
• The Grothendieck constant is strictly smaller than Krivine's bound

zbMATH Keywords

semidefinite programmingGrothendieck problem

Mathematics Subject Classification ID

Semidefinite programming (90C22)

Cites Work

• Title not available (Why is that?)
• Introductory lectures on convex optimization. A basic course.
• Title not available (Why is that?)
• Sums of random symmetric matrices and quadratic optimization under orthogonality constraints
• A generalized solution of the orthogonal Procrustes problem
• Semidefinite Programming
• Some Metric Inequalities in the Space of Matrices
• Primal-Dual Interior-Point Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical Results
• Semidefinite relaxation and nonconvex quadratic optimization
• Grothendieck’s Theorem, past and present
• Computing the Polar Decomposition—with Applications
• Trace inequalities and quantum entropy: an introductory course
• Title not available (Why is that?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Random matrix methods for wireless communications.
• Random Matrix Theory and Wireless Communications
• Three-dimensional structure determination from common lines in cryo-EM by eigenvectors and semidefinite programming
• A Cheeger Inequality for the Graph Connection Laplacian
• On the singular values of Gaussian random matrices
• Rate of convergence in probability to the Marchenko-Pastur law
• On maximization of quadratic form over intersection of ellipsoids with common center
• Résumé de la théorie métrique des produits tensoriels topologiques
• On tractable approximations of uncertain linear matrix inequalities affected by interval uncertainty
• Block coordinate descent methods for semidefinite programming
• Approximating the cut-norm via Grothendieck's inequality
• The positive semidefinite Grothendieck problem with rank constraint
• Closest Unitary, Orthogonal and Hermitian Operators to a Given Operator
• Tight hardness of the non-commutative Grothendieck problem
• Global registration of multiple point clouds using semidefinite programming
• Moments of Wishart-Laguerre and Jacobi ensembles of random matrices: application to the quantum transport problem in chaotic cavities
• Efficient rounding for the noncommutative Grothendieck inequality
• Quadratic forms on graphs (extended abstract)
• Angular synchronization by eigenvectors and semidefinite programming
• A generalized Grothendieck inequality and nonlocal correlations that require high entanglement
• Moment inequalities for sums of random matrices and their applications in optimization
• On approximating complex quadratic optimization problems via semidefinite programming relaxations

Cited In (13)

• Cohomology of cryo-electron microscopy
• The geometry of synchronization problems and learning group actions
• Orthogonal Trace-Sum Maximization: Tightness of the Semidefinite Relaxation and Guarantee of Locally Optimal Solutions
• Estimating \(L^\infty\) norms by \(L^{2k}\) norms for functions on orbits.
• Near-optimal bounds for generalized orthogonal Procrustes problem via generalized power method
• A brief introduction to manifold optimization
• Nonconvex phase synchronization
• Orthogonal trace-sum maximization: applications, local algorithms, and global optimality
• The positive semidefinite Grothendieck problem with rank constraint
• Global registration of multiple point clouds using semidefinite programming
• Non-unique games over compact groups and orientation estimation in cryo-EM
• Disentangling orthogonal matrices
• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization

This page was built for publication: Approximating the little Grothendieck problem over the orthogonal and unitary groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q344957)