The little Grothendieck problem (a special case of Boolean quadratic optimization) consists of maximizing P ij Cijxixj over binary variables xi 2 f 1g, where C is a positive semidenite matrix. In this paper we focus on a natural generalization of this problem, the little Grothendieck problem over the orthogonal group. Given C 2 R dn dn a positive semidenite matrix, the objective is to maximize P ij tr C T ijOiO T restricting Oi to take values in the group of orthogonal matrices O(d), where Cij denotes the (ij)-th d d block of C. We propose an approximation algorithm, to which we refer 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 semidenite programming where the relaxation is inspired by the work of Goemans and Williamson in the context of the MaxCut problem. For a given d 1, we show a constant approximation ratio of 2, where d is the expected average singular value of a d d matrix with random GaussianN 0; 1 i.i.d. entries. For d = 1 we recover the known 2 = 2= approximation guarantee for the classical little Grothendieck problem. 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 1 2 p 2 . The little Grothendieck problem falls under the larger class of problems approximated by an algorithm recently proposed in the context of the non-commutative Grothendieck inequality. Nonetheless, our approach is simpler and gives a better approximation ratio.
The little Grothendieck problem (a special case of Boolean quadratic optimization) consists of maximizing P ij Cijxixj over binary variables xi 2 f 1g, where C is a positive semidenite matrix. In this paper we focus on a natural generalization of this problem, the little Grothendieck problem over the orthogonal group. Given C 2 R dn dn a positive semidenite matrix, the objective is to maximize P ij tr C T ijOiO T restricting Oi to take values in the group of orthogonal matrices O(d), where Cij denotes the (ij)-th d d block of C. We propose an approximation algorithm, to which we refer 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 semidenite programming where the relaxation is inspired by the work of Goemans and Williamson in the context of the MaxCut problem. For a given d 1, we show a constant approximation ratio of 2, where d is the expected average singular value of a d d matrix with random GaussianN 0; 1 i.i.d. entries. For d = 1 we recover the known 2 = 2= approximation guarantee for the classical little Grothendieck problem. 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 1 2 p 2 . The little Grothendieck problem falls under the larger class of problems approximated by an algorithm recently proposed in the context of the non-commutative Grothendieck inequality. Nonetheless, our approach is simpler and gives a better approximation ratio.
The Grothendieck constant KG is the smallest constant such that for every d ∈ N and every matrix A = (aij), sup u i,v j ∈B (d) X aij〈ui, vj 〉 � KG · ij sup x i,y j ∈[−1,1] X ij aijxiyj, where B (d) is the unit ball in R d. Despite several efforts [15, 23], the value of the constant KG remains unknown. The Grothendieck constant KG is precisely the integrality gap of a natural SDP relaxation for the KM,N-Quadratic Programming problem. The input to this problem is a matrix A = (aij) and the objective is to maximize the quadratic form P ij aijxiyj over xi, yj ∈ [−1, 1]. In this work, we apply techniques from [22] to the KM,N-Quadratic Programming problem. Using some standard but non-trivial modifications, the reduction in [22] yields the following hardness result: Assuming the Unique Games Conjecture [9], it is NP-hard to approximate the KM,N-Quadratic Programming problem to any factor better than the Grothendieck constant KG. By adapting a “bootstrapping ” argument used in a proof of Grothendieck inequality [5], we are able to perform a tighter analysis than [22]. Through this careful analysis, we obtain the following new results: ◦ An approximation algorithm for KM,N-Quadratic Programming that is guaranteed to achieve an approximation ratio arbitrarily close to the Grothendieck constant KG (optimal approximation ratio assuming the Unique Games Conjecture). ◦ We show that the Grothendieck constant KG can be computed within an error η, in time depending only on η. Specifically, for each η, we formulate an explicit finite linear program, whose optimum is η-close to the Grothendieck constant. We also exhibit a simple family of operators on the Gaussian Hilbert space that is guaranteed to contain tight examples for the Grothendieck inequality.
This paper considers the following type of quadratic programming problem. Given an arbitrary matrix A, whose diagonal elements are zero, find x /spl isin/ {-1, 1}/sup n/ such that x/sup T/Ax is maximized. Our approximation algorithm for this problem uses the canonical semidefinite relaxation and returns a solution whose ratio to the optimum is in /spl Omega/(1/ logn). This quadratic programming problem can be seen as an extension to that of maximizing x/sup T/Ay (where y's components are also /spl plusmn/1). Grothendieck's inequality states that the ratio of the optimum value of the latter problem to the optimum of its canonical semidefinite relaxation is bounded below by a constant. The study of this type of quadratic program arose from a desire to approximate the maximum correlation in correlation clustering. Nothing substantive was known about this problem; we present an /spl Omega/ (1/logn) approximation, based on our quadratic programming algorithm. We can also guarantee that our quadratic programming algorithm returns a solution to the MAXCUT problem that has a significant advantage over a random assignment.
The Grothendieck constant KG is the smallest constant such that for every d ∊ ℕ and every matrix A = (aij), where B(d) is the unit ball in ℝd. Despite several efforts [15, 23], the value of the constant KG remains unknown. The Grothendieck constant KG is precisely the integrality gap of a natural SDP relaxation for the KM,N-Quadratic Programming problem. The input to this problem is a matrix A = (αij) and the objective is to maximize the quadratic form Σij aijxiyj over xi, yj ∊ [–1, 1]. In this work, we apply techniques from [22] to the KM,N-Quadratic Programming problem. Using some standard but non-trivial modifications, the reduction in [22] yields the following hardness result: Assuming the Unique Games Conjecture [9], it is NP-hard to approximate the KM,N-Quadratic Programming problem to any factor better than the Grothendieck constant KG. By adapting a “bootstrapping” argument used in a proof of Grothendieck inequality [5], we are able to perform a tighter analysis than [22]. Through this careful analysis, we obtain the following new results: An approximation algorithm for KM,N-Quadratic Programming that is guaranteed to achieve an approximation ratio arbitrarily close to the Grothendieck constant KG (optimal approximation ratio assuming the Unique Games Conjecture). We show that the Grothendieck constant KG can be computed within an error η, in time depending only on η. Specifically, for each η, we formulate an explicit finite linear program, whose optimum is η-close to the Grothendieck constant. We also exhibit a simple family of operators on the Gaussian Hilbert space that is guaranteed to contain tight examples for the Grothendieck inequality.
Quadratic programming over orthogonal matrices encompasses a broad class of hard optimization problems that do not have an efficient quantum representation. Such problems are instances of the little noncommutative Grothendieck problem (LNCG), a generalization of binary quadratic programs to continuous, noncommutative variables. In this work, we establish a natural embedding for this class of LNCG problems onto a fermionic Hamiltonian, thereby enabling the study of this classical problem with the tools of quantum information. This embedding is accomplished by a new representation of orthogonal matrices as fermionic quantum states, which we achieve through the well-known double covering of the orthogonal group. Correspondingly, the embedded LNCG Hamiltonian is a two-body fermion model. Determining extremal states of this Hamiltonian provides an outer approximation to the original problem, a quantum analogue to classical semidefinite relaxations. In particular, when optimizing over the special orthogonal group our quantum relaxation obeys additional, powerful constraints based on the convex hull of rotation matrices. The classical size of this convex-hull representation is exponential in matrix dimension, whereas our quantum representation requires only a linear number of qubits. Finally, to project the relaxed solution back into the feasible space, we propose rounding procedures which return orthogonal matrices from appropriate measurements of the quantum state. Through numerical experiments we provide evidence that this rounded quantum relaxation can produce high-quality approximations.
Semidefinite relaxations are a powerful tool for approximately solving combinatorial optimization problems such as MAX-CUT and the Grothendieck problem. By exploiting a bounded rank property of extreme points in the semidefinite cone, we make a sub-constant improvement in the approximation ratio of one such problem. Precisely, we describe a polynomial-time algorithm for the positive semidefinite Grothendieck problem -- based on rounding from the standard relaxation -- that achieves a ratio of 2/π+Θ(1/n), whereas the previous best is 2/π+Θ(1/n). We further show a corresponding integrality gap of 2/π+O~(1/n1/3).
In this paper we study the approximation algorithms for a class of discrete quadratic optimization problems in the Hermitian complex form. A special case of the problem that we study corresponds to the max-3-cut model used in a recent paper of Goemans and Williamson J. Comput. System Sci., 68 (2004), pp. 442-470]. We first develop a closed-formformula to compute the probability of a complex-valued normally distributed bivariate random vector to be in a given angular region. This formula allows us to compute the expected value of a randomized (with a specific rounding rule) solution based on the optimal solution of the complex semidefinite programming relaxation problem. In particular, we present an [m2(1−cosm2π)/8π]-approximation algorithm, and then study the limit of that model, in which the problem remains NP-hard. We show that if the objective is to maximize a positive semidefinite Hermitian form, then the randomization-rounding procedure guarantees a worst-case performance ratio of π/4≈0.7854, which is better than the ratio of 2/π≈0.6366 for its counterpart in the real case due to Nesterov. Furthermore, if the objective matrix is real-valued positive semidefinite with nonpositive off-diagonal elements, then the performance ratio improves to 0.9349.