Efficient rounding for the noncommutative Grothendieck inequality

Assaf Naor^{∗}  Oded Regev^{†}  Thomas Vidick^{‡}

Abstract

The classical Grothendieck inequality has applications to the design of approximation algorithms for NP-hard optimization problems. We show that an algorithmic interpretation may also be given for a noncommutative generalization of the Grothendieck inequality due to Pisier and Haagerup. Our main result, an efficient rounding procedure for this inequality, leads to a constant-factor polynomial time approximation algorithm for an optimization problem which generalizes the Cut Norm problem of Frieze and Kannan, and is shown here to have additional applications to robust principle component analysis and the orthogonal Procrustes problem.

Contents

1 Introduction  2
1.1 Applications of Theorem 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.1 The Grothendieck problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.2 Robust PCA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.3 The orthogonal Procrustes problem . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.4 A Frieze-Kannan decomposition for 4-tensors . . . . . . . . . . . . . . . . . . 5
1.1.5 Quantum XOR games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 The noncommutative Grothendieck inequality . . . . . . . . . . . . . . . . . . . . . . 7
1.2.1 The complex case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.2 The rounding algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.3 An intuitive description of the rounding procedure in the commutative case . 10
2 Proof of Theorem 4  11
2.1 Analysis of the rounding procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2 Derandomized rounding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3 The rounding procedure in the case of (18) . . . . . . . . . . . . . . . . . . . . . . . . 16

∗Courant Institute, New York University, 251 Mercer Street, New York NY 10012, USA. Supported by NSF grant CCF-0832795, BSF grant 2010021, the Packard Foundation and the Simons Foundation. Part of this work was completed while A. N. was visiting Université de Paris Est Marne-la-Vallée.

†Courant Institute, New York University. Supported by a European Research Council (ERC) Starting Grant. Part of the work done while the author was with the CNRS, DI, ENS, Paris.

‡Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology. Supported by the National Science Foundation under Grant No. 0844626.

3 The real and Hermitian cases  17
3.1 Two-dimensional rounding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2 Rounding in the Hermitian case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.3 Proof of Theorem 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4 Direct rounding in the real case  23
5 Some applications  27
5.1 Constant-factor algorithm for robust PCA problems . . . . . . . . . . . . . . . . . . . 29
5.2 A constant-factor algorithm for the orthogonal Procrustes problem . . . . . . . . . . 30
5.3 An algorithmic noncommutative dense regularity lemma . . . . . . . . . . . . . . . . 31
References  32

1 Introduction

In what follows, the standard scalar product on ^{n} is denoted ⟨·, ·⟩, i.e, ⟨x, y⟩ = ∑ _{i=1}^{n} x_{i}\overline{y_{i}} for all x, y ∈ ^{n}. We always think of ^{n} as canonically embedded in ^{n}; in particular the restriction of ⟨·, ·⟩ to ^{n} is the standard scalar product on ^{n}. Given a set S, the space M_{n}(S) stands for all the matrices M = (M_{ij})_{i,j=1}^{n} with M_{ij} ∈ S for all i, j ∈ {1, …, n}. Thus, M_{n}(M_{n}( )) is naturally identified with the n^{4}-dimensional space of all 4-tensors M = (M_{ijkl})_{i,j,k,l=1}^{n} with M_{ijkl} ∈ for all i, j, k, l ∈ {1, …, n}. The set of all n × n orthogonal matrices is denoted O_{n} ⊆ M_{n}( ), and the set of all n × n unitary matrices is denoted U_{n} ⊆ M_{n}( ).

Given M = (M_{ijkl}) ∈ M_{n}(M_{n}( )) denote

Opt_{}(M) =^{def} sup_{U,V ∈O_{n}} ∑_{i,j,k,l=1}^{n} M_{ijkl}U_{ij}V_{kl}.

and similarly, for M = (M_{ijkl}) ∈ M_{n}(M_{n}( )) denote

Opt_{}(M) =^{def} sup_{U,V ∈U_{n}} | ∑_{i,j,k,l=1}^{n} M_{ijkl}U_{ij}\overline{V_{kl}}|.

Theorem 1. There exists a polynomial time algorithm that takes as input M ∈ M_{n}(M_{n}( )) and outputs U, V ∈ O_{n} such that

Opt_{}(M) ⩽ O(1) ∑_{i,j,k,l=1}^{n} M_{ijkl}U_{ij}V_{kl}.

Respectively, there exists a polynomial time algorithm that takes as input M ∈ M_{n}(M_{n}( )) and outputs U, V ∈ U_{n} such that

Opt_{}(M) ⩽ O(1)| ∑_{i,j,k,l=1}^{n} M_{ijkl}U_{ij}\overline{V_{kl}}|.

We will explain the ideas that go into the proof of Theorem 1 later, and it suffices to say at this juncture that our algorithm is based on a rounding procedure for semidefinite programs that is markedly different from rounding algorithms that have been previously used in the optimization literature, and as such it indicates the availability of techniques that have thus far remained untapped for the purpose of algorithm design. Prior to explaining the proof of Theorem 1 we list below some of its applications as an indication of its usefulness.

Remark 2. The implied constants in the O(1) terms of Theorem 1 can be taken to be any number greater than 2\sqrt{2} in the real case, and any number greater than 2 in the complex case. There is no reason to believe that the factor 2\sqrt{2} in the real case is optimal, but the factor 2 in the complex case is sharp in a certain natural sense that will become clear later. The main content of Theorem 1 is the availability of a constant factor algorithm rather than the value of the constant itself. In particular, the novelty of the applications to combinatorial optimization that are described below is the mere existence of a constant-factor approximation algorithm.

1.1 Applications of Theorem 1

We now describe some examples demonstrating the usefulness of Theorem 1. The first example does not lead to a new result, and is meant to put Theorem 1 in context. All the other examples lead to new algorithmic results. Many of the applications below follow from a more versatile reformulation of Theorem 1 that is presented in Section 5 (see Proposition 20).

1.1.1 The Grothendieck problem

The Grothendieck optimization problem takes as input a matrix A ∈ M_{n}( ) and aims to efficiently compute (or estimate) the quantity

max_{ε,δ∈{−1,1}^{n}} ∑_{i,j=1}^{n} A_{ij}ε_{i}δ_{j}.  (1)

This problem falls into the framework of Theorem 1 by considering the 4-tensor M ∈ M_{n}(M_{n}( )) given by M_{iijj} = A_{ij} and M_{ijkl} = 0 if either i ≠ j or k ≠ l. Indeed,

Opt_{}(M) = max_{U,V ∈O_{n}} ∑_{i,j=1}^{n} A_{ij}U_{ii}V_{jj} = max_{x,y∈[−1,1]^{n}} ∑_{i,j=1}^{n} A_{ij}x_{i}y_{j} = max_{ε,δ∈{−1,1}^{n}} ∑_{i,j=1}^{n} A_{ij}ε_{i}δ_{j}.

A constant-factor polynomial time approximation algorithm for the Grothendieck problem was designed in [AN04], where it was also shown that it is NP-hard to approximate this problem within a factor less that 1 + ε_{0} for some ε_{0} ∈ (0, 1). A simple transformation [AN04] relates the Grothendieck problem to the Frieze-Kannan Cut Norm problem [FK99] (this transformation can be made to have no loss in the approximation guarantee [KN12, Sec. 2.1]), and as such the constant-factor approximation algorithm for the Grothendieck problem has found a variety of applications in combinatorial optimization; see the survey [KN12] for much more on this topic. In another direction, based on important work of Tsirelson [Tsi87], the Grothendieck problem has found applications to quantum information theory [CHTW04]. Since the problem of computing Opt_{}(·) contains the Grothendieck problem as a special case, Theorem 1 encompasses all of these applications, albeit with the approximation factor being a larger constant.

1.1.2 Robust PCA

The input to the classical principal component analysis (PCA) problem is K, n ∈ a set of points a_{1}, …, a_{N} ∈ ^{n}. The goal is to find a K-dimensional subspace maximizing the sum of the squared ℓ_{2} norms of the projections of the a_{i} on the subspace. Equivalently, the problem is to find the maximizing vectors in

max_{\begin{matrix}y_{1},...,y_{K}∈ ^{n} \\ ⟨y_{i},y_{j}⟩=δ_{ij} \end{matrix}} ∑_{i=1}^{N} ∑_{j=1}^{K} |⟨a_{i}, y_{j}⟩|^{2},  (2)

where here, and in what follows, δ_{ij} is the Kronecker delta. This question has a closed-form solution in terms of the singular values of the N × n matrix whose i-th row contains the coefficients of the point a_{i}.

The fact that the quantity appearing in (2)is the maximum of the sum of the squared norms of the projected points makes it somewhat non-robust to outliers, in the sense that a single long vector can have a large effect on the maximum. Several more robust versions of PCA were suggested in the literature. One variant, known as “R1-PCA,” is due to Ding, Zhou, He, and Zha [DZHZ06 ], and aims to maximize the sum of the Euclidean norms of the projected points, namely,

max_{\begin{matrix}y_{1},...,y_{K}∈ ^{n} \\ ⟨y_{i},y_{j}⟩=δ_{ij} \end{matrix}} ∑_{i=1}^{N} ( ∑_{j=1}^{K} |⟨a_{i}, y_{j}⟩|^{2})^{1/2}.  (3)

We are not aware of any prior efficient algorithm for this problem that achieves a guaranteed approximation factor. Another robust variant of PCA, known as “L1-PCA”, was suggested by Kwak [Kwa08], and further studied by McCoy and Tropp [MT12] (see Section 2.7 in [MT12] in particular). Here the goal is to maximize the sum of the ℓ_{1} norms of the projected points, namely,

max_{\begin{matrix}y_{1},...,y_{K}∈ ^{n} \\ ⟨y_{i},y_{j}⟩=δ_{ij} \end{matrix}} ∑_{i=1}^{N} ∑_{j=1}^{K} |⟨a_{i}, y_{j}⟩|.  (4)

In [MT12] a constant factor approximation algorithm for the above problem is obtained for K = 1 based on [AN04], and for general K an approximation algorithm with an approximation guarantee of O(log n) is obtained based on prior work by So [So11].

In Section 5.1 we show that both of the above robust versions of PCA can be cast as special cases of Theorem 1, thus yielding constant-factor approximation algorithms for both problems and all K ∈ {1, …, n}.

1.1.3 The orthogonal Procrustes problem

Let n, d ⩾ 1 and K ⩾ 2 be integers. Suppose that S_{1}, …, S_{K} ⊆ ^{d} are n-point subsets of ^{d}. The goal of the generalized orthogonal Procrustes problem is to rotate each of the S_{k} separately so as to best align them. Formally, write S_{k} = {x_{1}^{k}, x_{2}^{k}, …, x_{n}^{k}}. The goal is to find K orthogonal matrices U_{1}, …, U_{K} ∈ O_{d} that maximize the quantity

∑_{i=1}^{n} ∥ ∑_{k=1}^{K} U_{k}x_{i}^{k}∥_{2}^{2}.  (5)

If one focuses on a single summand appearing in (5), say ∑ _{k=1}^{K} U_{k}x_{1}^{k}, then it is clear that in order to maximize its length one would want to rotate each of the x_{1}^{k} so that they would all point in the same direction, i.e., they would all be positive multiples of the same vector. The above problem aims to achieve the best possible such alignment (in aggregate) for multiple summands of this type. We note that by expanding the squares one sees that U_{1}, …, U_{K} ∈ O_{d} maximize the quantity appearing in (5)if and only if they minimize the quantity ∑ _{i=1}^{n} ∑ _{k,l=1}^{K} ∥U_{k}x_{i}^{k} − U_{l}x_{i}^{l}∥_{2}^{2}.

The term “generalized” was used above because the orthogonal Procrustes problem refers to the case K = 2, which has a closed-form solution. The name “Procustes” is a (macabre) reference to

Greek mythology (see http://en.wikipedia.org/wiki/Procrustes).

The generalized orthogonal Procrustes problem has been extensively studied since the 1970s, initially in the psychometric literature (see, e.g., [CC71, Gow75, TB77]), and more recent applications of it are to areas such as image and shape analysis, market research and biometric identification; see the books [GD04, DM98], the lecture notes [SG02], and [MP07] for much more information on this topic.

The generalized orthogonal Procrustes problem is known to be intractable, and it has been investigated algorithmically in, e.g., [TB77, Bou82, SB88]. A rigorous analysis of a polynomial-time approximation algorithm for this problem appears in the work of Nemirovski [Nem07], where the generalized orthogonal Procrustes problem is treated as an important special case of a more general family of problems called “quadratic optimization under orthogonality constraints”, for which he obtains a O(\sqrt[3]{n + d} + log K) approximation algorithm. This was subsequently improved by So [So11] to O(log(n + d + K)). In Section 5.2 we use Theorem 1 to improve the approximation guarantee for the generalized orthogonal Procrustes problem as defined above to a constant approximation factor. See also Section 5.2 for a more complete discussion of variants of this problem considered in [Nem07, So11] and how they compare to our work.

1.1.4 A Frieze-Kannan decomposition for 4-tensors

In [FK99] Frieze and Kannan designed an algorithm which decomposes every (appropriately defined) “dense” matrix into a sum of a few “cut matrices” plus an error matrix that has small cut-norm. We refer to [FK99] and also Section 2.1.2 in the survey [KN12] for a precise formulation of this statement, as well as its extension, due to [AN04], to an algorithm that allows sub-constant errors. In Section 5.3 we apply Theorem 1 to prove the following result, which can be viewed as a noncommutative variant of the Frieze-Kannan decomposition. For the purpose of the statement below it is convenient to identify the space M_{n}(M_{n}( )) of all 4-tensors with M_{n}( ) ⊗ M_{n}( ). Also, for M ∈ M_{n}( ) ⊗ M_{n}( ) we denote from now on its Frobenius (Hilbert-Schmidt) norm by

∥M∥_{2} =^{def} \sqrt{∑_{i,j,k,l=1}^{n} |M_{ijkl}|^{2}}.

Theorem 3. There exists a universal constant c ∈ (0, ∞) with the following property. Suppose that M ∈ M_{n}( ) ⊗ M_{n}( ) and 0 < ε ⩽ 1/2, and let

T =^{def} ⌈ \frac{cn^{2}∥M∥_{2}^{2}}{ε^{2}Opt_{}(M)^{2}} ⌉ .  (6)

One can compute in time poly(n, 1/ε) a decomposition

M = ∑_{t=1}^{T} α_{t}(A_{t} ⊗ B_{t}) + E,  (7)

such that A_{t}, B_{t} ∈ U_{n}, the coefficients α_{t} ∈ satisfy |α_{t}| = O(∥M∥_{2}/n), and Opt_{}(E) ⩽ εOpt_{}(M). Moreover, if M ∈ M_{n}( ) ⊗ M_{n}( ) then one can replace Opt_{}(M) in (6)by Opt_{}(M), take the coefficients α_{t} to be real, A_{t}, B_{t} ∈ O_{n} and E such that Opt_{}(E) ⩽ εOpt_{}(M).

Theorem 3 contains as a special case its commutative counterpart, as studied in [FK99, AN04]. Here we are given A ∈ M_{n}( ) with |a_{ij}| ⩽ 1 for all i, j ∈ {1, …, n}, and we aim for an error εn^{2}. Define M_{iijj} = a_{ij} and M_{ijkl} = 0 if i ≠ j or k ≠ l. Then ∥M∥_{2} ⩽ n. An application of Theorem 3 (in the real case) with ε replaced by εn^{2}/Opt_{}(M) yields a decomposition A = ∑ _{t=1}^{T} α_{t}(a_{t}b_{t}^{∗}) + E with a_{t}, b_{t} ∈ [−1, 1]^{n} and E ∈ M_{n}( ) satisfying sup_{ε,δ∈{−1,1}} ∑ _{ij=1}^{n} E_{ij}ε_{i}δ_{j} ⩽ εn^{2}. Moreover, the number of terms is T = O(1/ε^{2}).

Theorem 3 is proved in Section 5.3 via an iterative application of Theorem 1, following the “energy decrement” strategy as formulated by Lovász and Szegedy [LS07] in the context of general weak regularity lemmas. Other than being a structural statement of interest in its own right, we show in Section 5.3 that Theorem 3 can be used to enhance the constant factor approximation of Theorem 1 to a PTAS for computing Opt_{}(M) when Opt_{}(M) = Ω(n∥M∥_{2}). Specifically, if Opt_{}(M) ⩾ κn∥M∥_{2} then one can compute a (1 + ε)-factor approximation to Opt_{}(M) in time 2^{poly(1/(κε))} poly(n). This is reminiscent of the Frieze-Kannan algorithmic framework [FK99] for dense graph and matrix problems.

1.1.5 Quantum XOR games

As we already noted, the Grothendieck problem (recall Section 1.1.1) also has consequences in quantum information theory [CHTW04], and more specifically to bounding the power of entanglement in so-called “XOR games”, which are two-player one-round games in which the players each answer with a bit and the referee bases her decision on the XOR of the two bits. As will be explained in detail in Section 1.2 below, the literature on the Grothendieck problem relies on a classical inequality of Grothendieck [Gro53], while our work relies on a more recent yet by now classical noncommutative Grothendieck inequality of Pisier [Pis78] (and its sharp form due to Haagerup [Haa85]). Even more recently, the Grothendieck inequality has been generalized to another setting, that of completely bounded linear maps defined on operator spaces [PS02, HM08]. While we do not discuss the operator space Grothendieck inequality here, we remark that in [RV12a] the operator space Grothendieck inequality is proved by reducing it to the Pisier-Haagerup noncommutative Grothendieck inequality. Without going into details, we note that this reduction is also algorithmic. Combined with our results, it leads to an algorithmic proof of the operator space Grothendieck inequality, together with an accompanying rounding procedure.

In the preprint [RV12b] written by the last two named authors, the noncommutative and operator space Grothendieck inequalities are shown to have consequences in a setting that generalizes that of classical XOR games, called “quantum XOR games”: in such games, the questions to the players may be quantum states (and the answers are still a single classical bit). The results in [RV12b] derive an efficient factor-2 approximation algorithm for the maximum success probability of players in such a game, in three settings: players sharing an arbitrary quantum state, players sharing a maximally entangled state, and players not sharing any entanglement. Theorem 1 implies that in all three cases a good strategy for the players, achieving a success that is a factor 2 from optimal, may be found in polynomial time. These matters are taken up in [RV12b] and will not be discussed further here.

1.2 The noncommutative Grothendieck inequality

The natural semidefinite relaxation of (1)is

sup_{d∈} sup_{x,y∈(S^{d−1} )^{n}} ∑_{i,j=1}^{n} A_{ij}⟨x_{i}, y_{j}⟩,  (8)

where S^{d−1} is the unit sphere of ^{d}. Since, being a semidefinite program (SDP), the quantity appearing in (8)can be computed in polynomial time with arbitrarily good precision (see [GLS93]), the fact that the Grothendieck optimization problem admits a constant-factor polynomial time approximation algorithm follows from the following inequality, which is a classical inequality of Grothendieck of major importance to several mathematical disciplines (see Pisier’s survey [Pis12] and the references therein for much more on this topic; the formulation of the inequality as below is due to Lindenstrauss and Pe�czyński [LP68]).

sup_{d∈} sup_{x,y∈(S^{d−1} )^{n}} ∑_{i,j=1}^{n} A_{ij}⟨x_{i}, y_{j}⟩ ⩽ K_{G} sup_{ε,δ∈{−1,1}^{n}} ∑_{i,j=1}^{n} A_{ij}ε_{i}δ_{j}.  (9)

Here K_{G} ∈ (0, ∞), which is understood to be the infimum over those constants for which (9)holds true for all n ∈ and all A ∈ M_{n}( ), is a universal constant known as the (real) Grothendieck constant. Its exact value remains unknown, the best available bounds [Ree91, BMMN11] being 1.676 < K_{G} < 1.783. In order to actually find an assignment ε, δ to (1) that is within a constant factor of the optimum one needs to argue that a proof of (9)can be turned into an efficient rounding algorithm; this is done in [AN04].

If one wishes to mimic the above algorithmic success of the Grothendieck inequality in the context of efficient computation of Opt_{}(·), the following natural strategy presents itself: one should replace real entries of matrices by vectors in ℓ_{2}, i.e., consider elements of M_{n}(ℓ_{2}), and replace the orthogonality constraints underlying the inclusion U ∈ O_{n}, namely,

∀ i, j ∈ {1, …, n}, ∑_{k=1}^{n} U_{ik}U_{jk} = ∑_{k=1}^{n} U_{ki}U_{kj} = δ_{ij},

by the corresponding constraints using scalar product. Specifically, given an n × n vector-valued matrix X ∈ M_{n}(ℓ_{2}) define two real matrices XX^{∗}, X^{∗}X ∈ M_{n}( ) by

∀ i, j ∈ {1, …, n}, (XX^{∗})_{ij} =^{def} ∑_{k=1}^{n} ⟨X_{ik}, X_{jk}⟩, and (X^{∗}X)_{ij} =^{def} ∑_{k=1}^{n} ⟨X_{ki}, X_{kj}⟩,  (10)

and let the set of d-dimensional vector-valued orthogonal matrices be given by

O_{n}( ^{d}) =^{def} {X ∈ M_{n}( ^{d}) : XX^{∗} = X^{∗}X = I} .  (11)

One then considers the following quantity associated to every M ∈ M_{n}(M_{n}( )),

SDP_{}(M) =^{def} sup_{d∈} sup_{X,Y∈O_{n}( ^{d})} ∑_{i,j,k,l=1}^{n} M_{ijkl} ⟨X_{ij}, Y_{kl}⟩.  (12)

Since the constraints that underlie the inclusion X, Y ∈ O_{n}( ^{d}) are linear equalities in the pairwise scalar products of the entries of X and Y, the quantity SDP_{}(M) is a semidefinite program and can therefore be computed in polynomial time with arbitrarily good precision. One would therefore aim to prove the following noncommutative variant of the Grothendieck inequality (9),

∀ n ∈ , ∀ M ∈ M_{n}(M_{n}( )), SDP_{}(M) ⩽ O(1) · Opt_{}(M).  (13)

The term “noncommutative” refers here to the fact that Opt_{}(M) is an optimization problem over the noncommutative group O_{n}, while the classical Grothendieck inequality addresses an optimization problem over the commutative group {−1, 1}^{n}. In the same vein, noncommutativity is manifested by the fact that the classical Grothendieck inequality corresponds to the special case of “diagonal” 4-tensors M ∈ M_{n}(M_{n}( )), i.e., those that satisfy M_{ijkl} = 0 whenever i ≠ j or k ≠ l.

Grothendieck conjectured [Gro53] the validity of (13)in 1953, a conjecture that remained open until its 1978 affirmative solution by Pisier [Pis78]. A simpler, yet still highly nontrivial proof of the noncommutative Grothendieck inequality (13)was obtained by Kaijser [Kai83]. In Section 4 we design a rounding algorithm corresponding to (13)based on Kaijser’s approach. This settles the case of real 4-tensors of Theorem 1, albeit with worse approximation guarantee than the one claimed in Remark 2. The algorithm modeled on Kaijser’s proof is interesting in its own right, and seems to be versatile and applicable to other problems, such as possible non-bipartite extensions of the noncommutative Grothendieck inequality in the spirit of [AMMN06]; we shall not pursue this direction here.

A better approximation guarantee, and arguably an even more striking rounding algorithm, arises from the work of Haagerup [Haa85] on the complex version of (13). In Section 3 we show how the real case of Theorem 1 follows formally from our results on its complex counterpart, so from now on we focus our attention on the complex case.

1.2.1 The complex case

In what follows we let S_{}^{d−1} denote the unit sphere of ^{d} (thus S_{}^{0} can be identified with the unit circle S^{1} ⊆ ^{2}). The classical complex Grothendieck inequality [Gro53, LP68] asserts that there exists K ∈ (0, ∞) such that

∀ n ∈ , ∀ A ∈ M_{n}( ), sup_{x,y∈(S_{}^{2n−1} )^{n}} | ∑_{i,j=1}^{n} A_{ij}⟨x_{i}, y_{j}⟩| ⩽ O(1) sup_{α,β∈(S_{}^{0} )^{n}} | ∑_{i,j=1}^{n} A_{ij}α_{i}\overline{β_{j}} |.  (14)

Let K_{G}^{}denote the infimum over those K ∈ (0, ∞) for which (14)holds true. The exact value of K_{G}^{} remains unknown, the best available bounds being 1.338 < K_{G}^{}< 1.4049 (the left inequality is due to unpublished work of Davie, and the right one is due to Haagerup [Haa87]).

For M ∈ M_{n}(M_{n}( )) we define

SDP_{}(M) =^{def} sup_{d∈} sup_{X,Y∈U_{n}( ^{d})} | ∑_{i,j,k,l=1}^{n} M_{ijkl} ⟨X_{ij}, Y_{kl}⟩|,  (15)

where analogously to (11)we set

U_{n}( ^{d}) =^{def} {X ∈ M_{n}( ^{d}) : XX^{∗} = X^{∗}X = I} .

Here for X ∈ M_{n}( ^{d}) the complex matrices XX^{∗}, X^{∗}X ∈ M_{n}( ) are defined exactly as in (10), with the scalar product being the complex scalar product. Haagerup proved [Haa85] that

∀ n ∈ , ∀ M ∈ M_{n}(M_{n}( )), SDP_{}(M) ⩽ 2 · Opt_{}(M).  (16)

Our main algorithm is an efficient rounding scheme corresponding to inequality (16). The constant 2 in (16)is sharp, as shown in [HI95] (see also [Pis12, Sec. 12]).

We note that the noncommutative Grothendieck inequality, as it usually appears in the literature, involves a slightly more relaxed semidefinite program. In order to describe it, we first remark that instead of maximizing over X, Y ∈ U_{n}( ^{d}) in (15) we could equivalently maximize over X, Y ∈ M_{n}( ^{d}) satisfying XX^{∗}, X^{∗}X, YY^{∗}, Y^{∗}Y ⩽ I, which is the same as the requirement ∥XX^{∗}∥, ∥X^{∗}X∥, ∥YY^{∗}∥, ∥Y^{∗}Y∥ ⩽ 1, where here and in what follows ∥ · ∥ denotes the operator norm of matrices. This fact is made formal in Lemma 6 below. By relaxing the constraints to ∥XX^{∗}∥ + ∥X^{∗}X∥ ⩽ 2 and ∥YY^{∗}∥ + ∥Y^{∗}Y∥ ⩽ 2, we obtain the following quantity, which can be shown to still be a semidefinite program.

∥M∥_{nc} =^{def} sup_{d∈} sup_{\begin{matrix}X,Y∈M_{n}( ^{d}) \\ ∥XX^{∗}∥+∥X^{∗}X∥⩽2 \\ ∥YY^{∗}∥+∥Y^{∗}Y∥⩽2 \end{matrix}} | ∑_{i,j,k,l=1}^{n} M_{ijkl} ⟨X_{ij}, Y_{kl}⟩|.  (17)

Clearly ∥M∥_{nc} ⩾ SDP_{}(M) for all M ∈ M_{n}(M_{n}( )). Haagerup proved [Haa85] that the following stronger inequality holds true for all n ∈ and M ∈ M_{n}(M_{n}( )).

∥M∥_{nc} ⩽ 2 · Opt_{}(M).  (18)

As our main focus is algorithmic, in the following discussion we will establish a rounding algorithm for the tightest relaxation (16). In Section 2.3 we show that the same rounding procedure can be used to obtain an algorithmic analogue of (18)as well.

1.2.2 The rounding algorithm

Our main algorithm is an efficient rounding scheme corresponding to (16). In order to describe it, we first introduce the following notation. Let φ : → ^{+} be given by

φ(t) =^{def} \frac{1}{2}sech( \frac{π}{2} t) = \frac{1}{e^{πt/2} + e^{−πt/2}} .  (19)

One computes that ∫_{}φ(t)dt = 1, so φ is a density of a probability measure μ on , known as the hyperbolic secant distribution. By [JKB95, Sec. 23.11] we have

∀ a ∈ (0, ∞), ∫_{}a^{it}φ(t)dt = \frac{2a}{1 + a^{2}} .  (20)

It is possible to efficiently sample from μ using standard techniques; see, e.g., [Dev86, Ch. IX.7].

In what follows, given X ∈ M_{n}( ^{d}) and z ∈ ^{d} we denote by ⟨X, z⟩ ∈ M_{n}( ) the matrix whose entries are ⟨X, z⟩_{jk} = ⟨X_{jk}, z⟩.

Rounding procedure

1. Let X, Y ∈ M_{n}( ^{d}) be given as input. Choose z ∈ {1, −1, i, −i}^{d} uniformly at random, and sample t ∈ according to the hyperbolic secant distribution μ.

2. Set X_{z} =^{def} \frac{1}{\sqrt{2}}⟨X, z⟩ ∈ M_{n}( ) and Y_{z} =^{def} \frac{1}{\sqrt{2}} ⟨Y, z⟩∈ M_{n}( ).

3. Output the pair of matrices (A, B) = (A(z, t), B(z, t)) =^{def} (U_{z}|X_{z}|^{it}, V_{z}|Y_{z}|^{−it} ) ∈ U_{n} × U_{n} where X_{z} = U_{z}|X_{z}| and Y_{z} = V_{z}|Y_{z}| are the polar decompositions of X_{z} and Y_{z}, respectively.

Figure 1: The rounding algorithm takes as input a pair of vector-valued matrices X, Y ∈ M_{n}( ^{d}). It outputs two matrices A, B ∈ U_{n}( ).

Theorem 4. Fix n, d ∈ and ε ∈ (0, 1). Suppose that M ∈ M_{n}(M_{n}( )) and that X, Y ∈ U_{n}( ^{d}) are such that

| ∑_{i,j,k,l=1}^{n} M_{ijkl}⟨X_{ij}, Y_{kl}⟩| ⩾ (1 − ε)SDP_{}(M),  (21)

where SDP_{}(M) is given in (15). Then the rounding procedure described in Figure 1 outputs a pair of matrices A, B ∈ U_{n} such that

[ | ∑_{i,j,k,l=1}^{n} M_{ijkl} A_{ij}\overline{B_{kl}}| ] ⩾ ( \frac{1}{2} − ε) SDP_{}(M).  (22)

Moreover, rounding can be performed in time polynomial in n and log(1/ε), and can be derandomized in time poly(n, 1/ε).

While the rounding procedure of Figure 1 and the proof of Theorem 4 (contained in Section 2 below) appear to be different from Haagerup’s original proof of (18)in [Haa85], we derived them using Haagerup’s ideas. One source of difference arises from changes that we introduced in order to work with the quantity SDP_{}(M), while Haagerup’s argument treats the quantity ∥M∥_{nc}. A second source of difference is that Haagerup’s proof of (18)is rather indirect and nonconstructive, while it is crucial to the algorithmic applications that were already mentioned in Section 1.1 for us to formulate a polynomial-time rounding procedure. Specifically, Haagerup establishes the dual formulation of (18), through a repeated use of duality, and he uses a bootstrapping argument that relies on nonconstructive tools from complex analysis. The third step in Figure 1 originates from Haagerup’s complex-analytic considerations. Readers who are accustomed to semidefinite rounding techniques will immediately notice that this step is unusual; we give intuition for it in Section 1.2.3 below, focusing for simplicity on applying the rounding procedure to vectors rather than matrices (i.e., the more familiar setting of the classical Grothendieck inequality).

1.2.3 An intuitive description of the rounding procedure in the commutative case

Consider the effect of the rounding procedure in the commutative case, i.e., when X, Y ∈ M_{n}( ^{d}) are diagonal matrices. Let the diagonals of X, Y be x, y ∈ ( ^{d})^{n}, respectively. The first step consists in performing a random projection: for j ∈ \{1, …, n\} let α_{j} = ⟨x_{j}, z⟩/\sqrt{2} ∈ and β_{j} = ⟨y_{j}, z⟩/\sqrt{2} ∈ , where z is chosen uniformly at random from \{1, −1, i, −i\}^{n} (alternatively, with minor modifications to the proof one may choose i.i.d. z_{j} uniformly from the unit circle, as was done by Haagerup [Haa85], or use standard complex Gaussians). This step results in sequences of complex numbers whose pairwise products α_{k}\overline{β_{j}}, in expectation, exactly reproduce the pairwise scalar products ⟨x_{k}, y_{j}⟩. However, in general the resulting complex numbers α_{k} and β_{j} may have modulus larger than 1. Extending the “sign” rounding performed in, say, the Goemans-Williamson algorithm for MAXCUT [GW95] to the complex domain, one could then round each α_{k} and β_{j} independently by simply replacing them by their respective complex phase.

The procedure that we consider differs from this standard practice by taking into account potential information contained in the modulus of the random complex numbers α_{k}, β_{j}. Writing in polar coordinates α_{k} = r_{k}e^{iθ_{k}} and β_{j} = s_{j}e^{iϕ_{j}} we sample a real t according to a specific distribution (the hyperbolic secant distribution μ), and round each α_{k} and each β_{j} to

a_{k} =^{def} e^{i(θ_{k}+t log r_{k})} ∈ S_{}^{0} , and b_{j} =^{def} e^{i(ϕ_{j}−t log s_{j})} ∈ S_{}^{0} ,

respectively. Observe that this step performs a correlated rounding: the parameter t is the same for all j, k ∈ {1, …, n}.

The proof presented in [Haa85] uses the maximum modulus principle to show the existence of a real t for which a_{k}, b_{j} as defined above provide a good assignment. Intuition for the existence of such a good t can be given as follows. Varying t along the real line corresponds to rotating the phases of the complex numbers α_{j}, β_{k} at a speed proportional to the logarithm of their modulus: elements with very small modulus vary very fast, those with modulus 1 are left unchanged, and elements with relatively large modulus are again varied at (logarithmically) increasing speeds. This means that the rounding procedure takes into account the fact that an element with modulus away from 1 is a “miss”: that particular element’s phase is probably irrelevant, and should be changed. However, elements with modulus close to 1 are “good”: their phase can be kept essentially unchanged.

We identify a specific distribution μ such that a random t distributed according to μ is good, in expectation. This results in a variation on the usual “sign” rounding technique: instead of directly keeping the phases obtained in the initial step of random projection, they are synchronously rotated for a random time t, at speeds depending on the associated moduli, resulting in a provably good pair of sequences a_{k}, b_{j} of complex numbers with modulus 1.

Roadmap: In Section 2 we prove Theorem 4 both as stated in Section 1.2.2 and in a form based on (18). The real case as well as a closely related Hermitian case are treated next, first in Section 3 as a corollary of Theorem 4, and then using an alternative direct rounding procedure in Section 4. Section 5 presents the applications that were outlined in Section 1.1.

2 Proof of Theorem 4

In this section we prove Theorem 4. The rounding procedure described in Figure 1 is analyzed in Section 2.1, while the derandomized version is presented in Section 2.2. The efficiency of the procedure is clear; we refer to Section 2.2 for a discussion on how to discretize the choice of t. In Section 2.3 we show how the analysis can be modified to the case of ∥M∥_{nc} and (18).

In what follows, it will be convenient to use the following notation. Given M ∈ M_{n}(M_{n}( )) and X, Y ∈ M_{n}( ^{d}), define

M(X, Y) =^{def} ∑_{i,j,k,l=1}^{n} M_{ijkl} ⟨X_{ij}, Y_{kl}⟩∈ .  (23)

Thus M(·, ·) is a sesquilinear form on M_{n}( ^{d}) × M_{n}( ^{d}), i.e., M(αX, βY) = α\overline{β}M(X, Y) for all X, Y ∈ M_{n}( ^{d}) and α, β ∈ . Observe that if A, B ∈ M_{n}( ) then

M(A, B) = ∑_{i,j,k,l=1}^{n} M_{ijkl}A_{ij}\overline{B_{kl}} = ∑_{i,j,k,l=1}^{n} M_{ijkl} (A ⊗ \overline{B}) _{(ij),(kl)} .  (24)

2.1 Analysis of the rounding procedure

Proof of (22).Let X, Y ∈ U_{n}( ^{d}) be vector-valued matrices satisfying (21). Let z ∈ {1, −1, i, −i}^{d} be chosen uniformly at random, and

X_{z} =^{def} \frac{1}{\sqrt{2}} ⟨X, z⟩  and  Y_{z} =^{def} \frac{1}{\sqrt{2}} ⟨Y, z⟩

be random variables taking values in M_{n}( ) defined as in the second step of the rounding procedure (see Figure 1). Then,

z[ M(X_{z}, Y_{z}) ] = \frac{1}{2} _{z}[ ∑_{r,s=1}^{d} \overline{z_{r}}z_{s} ∑_{i,j,k,l=1}^{n} M_{ijkl}(X_{ij})_{r}\overline{(Y_{kl})_{s}}] = \frac{1}{2}M(X, Y),  (25)

where we used the fact that [\overline{z_{r}}z_{s}] = δ_{rs} for every r, s ∈ \{1, …, d\}.

Observe that (20)implies that

∀ a ∈ (0, ∞), _{t}[a^{it}] = 2a − _{t}[a^{2+it} ].

Applying this identity to the nonzero singular values of X_{z} ⊗ \overline{Y_{z}}, we deduce the matrix equality

t(A ⊗ \overline{B}) = _{t}[ ( U_{z}|X_{z}|^{it}) ⊗ ( \overline{V_{z}}|Y_{z}|^{it}) ]
= 2X_{z} ⊗ \overline{Y_{z}}− _{t}[ ( U_{z}|X_{z}|^{2+it} ) ⊗ ( \overline{V_{z}}|Y_{z}|^{2+it} ) ]
= 2X_{z} ⊗ \overline{Y_{z}}− _{t}[ ( U_{z}|X_{z}|^{2+it} ) ⊗ ( \overline{V_{z}|Y_{z}|^{2−it}}) ] ,  (26)

where U_{z}, V_{z} ∈ U_{n} are such that X_{z} = U_{z}|X_{z}| and Y_{z} = V_{z}|Y_{z}| are the polar decompositions of X_{z} and Y_{z}, respectively (and therefore the polar decomposition of \overline{Y_{z}} is \overline{Y_{z}} = \overline{V_{z}}|Y_{z}|), and we recall that the output of our rounding scheme as described in Figure 1 is A = U_{z}|X_{z}|^{it} and B = V_{z}|Y_{z}|^{−it} .

It follows from (23), (24), (25)and (26)that

z,t[ M(A, B) ] = M(X, Y) − _{z,t}[ M(U_{z}|X_{z}|^{2+it} , V_{z}|Y_{z}|^{2−it} ) ].  (27)

Our goal from now on is to bound the second, “error” term on the right-hand side of (27). Specifically, the rest of the proof is devoted to showing that for any fixed t ∈ we have

| _{z}[ M(U_{z}|X_{z}|^{2+it} , V_{z}|Y_{z}|^{2−it} ) ]| ⩽ \frac{1}{2}SDP_{}(M).  (28)

Once established, the estimate (28)completes the proof of the desired expectation bound (22)since

z,t[ |M(A, B)| ] ⩾^{(27)∧(28)} M(X, Y) − \frac{1}{2}SDP_{}(M) ⩾^{(21)} ( \frac{1}{2} − ε) SDP_{}(M).

So, for the rest of the proof, fix some t ∈ . As a first step towards (28)we state the following claim.

Claim 5. Let W ∈ M_{n}( ^{d}) be a vector-valued matrix, and for every r ∈ {1, …, d} define W_{r} ∈ M_{n}( ) by (W_{r})_{ij} = (W_{ij})_{r}. Let z ∈ {1, −1, i, −i}^{d} be chosen uniformly at random. Writing W_{z} = ⟨W, z⟩ ∈ M_{n}( ), we have

z [(W_{z}W_{z}^{∗})^{2}] = (WW^{∗})^{2} + ∑_{r=1}^{d} W_{r}(W^{∗}W − W_{r}^{∗}W_{r})W_{r}^{∗},  (29)

z [(W_{z}^{∗}W_{z})^{2}] = (W^{∗}W)^{2} + ∑_{r=1}^{d} W_{r}^{∗}(WW^{∗} − W_{r}W_{r}^{∗})W_{r}.  (30)

Proof. By definition W_{z} = ∑ _{r=1}^{d} \overline{z_{r}}W_{r}, and recalling (10)we have WW^{∗} = ∑ _{r=1}^{d} W_{r}W_{r}^{∗} and W^{∗}W = ∑ _{r=1}^{d} W_{r}^{∗}W_{r}. Consequently,

z [(W_{z}W_{z}^{∗})^{2}] = _{z}[ ∑_{p,q,r,s=1}^{d} \overline{z_{p}}z_{q}\overline{z_{r}}z_{s}W_{p}W_{q}^{∗}W_{r}W_{s}^{∗} ]

= ∑_{p=1}^{d} W_{p}W_{p}^{∗}W_{p}W_{p}^{∗} + ∑_{\begin{matrix}p,q∈\{1,...,d\} \\ p≠q \end{matrix}} ( W_{p}W_{p}^{∗}W_{q}W_{q}^{∗} + W_{p}W_{q}^{∗}W_{q}W_{p}^{∗})

= ∑_{p,q=1}^{d} W_{p}W_{p}^{∗}W_{q}W_{q}^{∗} + ∑_{p,q=1}^{d} W_{p}W_{q}^{∗}W_{q}W_{p}^{∗} − ∑_{p=1}^{d} W_{p}W_{p}^{∗}W_{p}W_{p}^{∗}

= ( ∑_{p=1}^{d} W_{p}W_{p}^{∗})^{2} + ∑_{p=1}^{d} W_{p}( ∑_{q=1}^{d} W_{q}^{∗}W_{q}) W_{p}^{∗} − ∑_{p=1}^{d} W_{p}W_{p}^{∗}W_{p}W_{p}^{∗},

proving (29). A similar calculation yields (30).

Now, for every t ∈ define two vector-valued matrices

F(t), G(t) ∈ M_{n} ( ^{{1,−1,i,−i}^{d}} )

by setting for every j, k ∈ {1, …, n} and z ∈ {1, −1, i, −i}^{d},

(F(t)_{jk})_{z} =^{def} \frac{1}{2^{d}} ( U_{z}|X_{z}|^{2+it} ) _{jk}  and  (G(t)_{jk})_{z} =^{def} \frac{1}{2^{d}} ( V_{z}|Y_{z}|^{2−it} )_{jk}.  (31)

Thus,

M(F(t), G(t)) = \frac{1}{4^{d}} ∑_{z∈\{1,−1,i,−i\}^{d}} M(U_{z}|X_{z}|^{2+it} , V_{z}|Y_{z}|^{2−it} ) = _{z}[ M(U_{z}|X_{z}|^{2+it} , V_{z}|Y_{z}|^{2−it} ) ]. (32)

Moreover, recalling that X_{z} = U_{z}|X_{z}| is the polar decomposition of X_{z}, we have

F(t)F(t)^{∗} = \frac{1}{4^{d}} ∑_{z∈\{1,−1,i,−i\}^{d}} U_{z}|X_{z}|^{4}U_{z}^{∗} = _{z} [U_{z}|X_{z}|^{4}U_{z}^{∗}] = _{z} [(X_{z}X_{z}^{∗})^{2}] .  (33)

Similarly F(t)^{∗}F(t) = _{z} [(X_{z}^{∗}X_{z})^{2}], so that an application of Claim 5 with W = \frac{1}{\sqrt{2}}X yields, using

XX^{∗} = X^{∗}X = I since X ∈ U_{n}( ^{d}),

F(t)F(t)^{∗} + \frac{1}{4} ∑_{r=1}^{d} X_{r}X_{r}^{∗}X_{r}X_{r}^{∗} = F(t)^{∗}F(t) + \frac{1}{4} ∑_{r=1}^{d} X_{r}^{∗}X_{r}X_{r}^{∗}X_{r} = \frac{1}{2}I.  (34)

Analogously,

G(t)G(t)^{∗} + \frac{1}{4} ∑_{r=1}^{d} Y_{r}Y_{r}^{∗}Y_{r}Y_{r}^{∗} = G(t)^{∗}G(t) + \frac{1}{4} ∑_{r=1}^{d} Y_{r}^{∗}Y_{r}Y_{r}^{∗}Y_{r} = \frac{1}{2}I.  (35)

The two equations above imply that F(t), G(t) satisfy the norm bounds

max \{∥F(t)F(t)^{∗}∥, ∥F(t)^{∗}F(t)∥, ∥G(t)G(t)^{∗}∥, ∥G(t)^{∗}G(t)∥\} ⩽ \frac{1}{2}.  (36)

As shown in Lemma 6 below, (36)implies that there exists a pair of vector-valued matrices

R(t), S(t) ∈ U_{n}( ^{d+2n^{2}} )

such that

M(R(t), S(t)) = M(\sqrt{2}F(t), \sqrt{2}G(t)).  (37)

(This fact can also be derived directly using (34)and (35).) Recalling the definition of SDP_{}(M) in (15), it follows that for every t ∈ ,

| _{z}[ M(U_{z}|X_{z}|^{2+it} , V_{z}|Y_{z}|^{2−it} ) ]| =^{(32)}|M(F(t), G(t))| =^{(37)} \frac{1}{2}|M(R(t), S(t))| ⩽ \frac{1}{2}SDP_{}(M), (38)

completing the proof of (28).

Lemma 6. Let X, Y ∈ M_{n}( ^{d}) be such that max(∥X^{∗}X∥, ∥XX^{∗}∥, ∥Y^{∗}Y∥, ∥YY^{∗}∥) ⩽ 1. Then there exist R, S ∈ U_{n}( ^{d+2n^{2}} ) such that for every M ∈ M_{n}(M_{n}( )) we have M(R, S) = M(X, Y). Moreover, R and S can be computed from X and Y in time poly(n, d).

Proof. Let A = I − XX^{∗} and B = I − X^{∗}X, and note that A, B ⩾ 0 and Tr(A) = Tr(B). Write the spectral decompositions of A and B as A = ∑ _{i=1}^{n} λ_{i}(u_{i}u_{i}^{∗}) and B = ∑ _{j=1}^{n} μ_{j}(v_{j}v_{j}^{∗}) respectively. Set σ = ∑ _{i=1}^{n} λ_{i} = ∑ _{j=1}^{n} μ_{j}, and define

R =^{def} X ⊕ ( ⨁_{i,j=1}^{n} \sqrt{\frac{λ_{i}μ_{j}}{σ}} (u_{i}v_{j}^{∗})) ⊕ ( 0_{M_{n}( ^{n^{2}})} ) ∈ M_{n}( ^{d} ⊕ ^{n^{2}} ⊕ ^{n^{2}}).

With this definition we have RR^{∗} = XX^{∗} + A = I and R^{∗}R = X^{∗}X + B = I, so R ∈ U_{n}( ^{d+2n^{2}} ). Let S ∈ U_{n}( ^{d+2n^{2}} ) be defined analogously from Y, with the last two blocks of n^{2} coordinates permuted. One checks that M(R, S) = M(X, Y), as required.

Finally, A, B, their spectral decomposition, and the resulting R, S can all be computed in time poly(n, d) from X, Y.

2.2 Derandomized rounding

Note that we can always assume that X, Y ∈ U_{n}( ^{d}), where d ⩽ 2n^{2}. We start by slightly changing the projection step. Define X′_{z} to be the projection X_{z} = \frac{1}{\sqrt{2}}⟨X, z⟩, after we replace all singular values of X_{z} that are smaller than ε with ε. Then, writing

2X′_{z}⊗ \overline{Y_{z}}′= 2X_{z} ⊗ \overline{Y_{z}}+ 2(X′_{z}− X_{z}) ⊗ \overline{Y_{z}}+ 2X′_{z}⊗ (\overline{Y′_{z}}− \overline{Y_{z}}),

we see that in the analogue of (27) the first term is at least M(X, Y) − 4εdSDP_{}(M). Here we use that ∥X_{z}∥, ∥Y_{z}∥ ⩽ d which follows by the triangle inequality and X, Y ∈ U_{n}( ^{d}). For the second term in (27), the previous analysis remains unchanged, provided we prove an analogue of (36). Using (33) and the analogous equations for F(t)^{∗}F(t), G(t)G(t)^{∗} and G(t)^{∗}G(t), it will suffice to bound four expressions such as ∥ _{z}[ (X′_{z}(X′_{z})^{∗})^{2} ]∥. One checks that the modification to the rounding we did can only increase this by ε^{4} (even for each z), hence following the previous analysis we get the bound in (38)with SDP_{}(M)/2 replaced by (1 + ε^{4})SDP_{}(M)/2.

Next, we observe that the coordinates of z need not be independent, and it suffices if they are chosen from a four-wise independent distribution. As a result, there are only poly(n) possible values of z and they can be enumerated efficiently. Therefore, we can assume that we have a value z ∈ {1, −1, i, −i}^{d} for which

| _{t}[ M(U_{z}|X′_{z}|^{it}, V_{z}|Y′_{z}|^{−it} ) ]| ⩾ ( \frac{1}{2} − ε) SDP_{}(M).  (39)

Notice that for some universal constant c > 0, with probability at least 1 − ε, a sample from the hyperbolic secant distribution is at most c log(1/ε) in absolute value. Therefore, denoting the restriction of the hyperbolic secant distribution to the interval [−c log(1/ε), c log(1/ε)] by μ′, and using the fact that the expression inside the expectation in (39)is never larger than SDP_{}(M), for t′distributed according to μ′we have

| _{t′}[ M(U_{z}|X′_{z}|^{it′}, V_{z}|Y′_{z}|^{−it′} ) ]| ⩾ ( \frac{1}{2} − 2ε) SDP_{}(M).

Moreover, for any t, t′∈ ,

|M(U_{z}|X′_{z}|^{it}, V_{z}|Y′_{z}|^{−it} ) − M(U_{z}|X′_{z}|^{it′}, V_{z}|Y′_{z}|^{−it′} )|
= |M(U_{z}(|X′_{z}|^{it} − |X′_{z}|^{it′}), V_{z}|Y′_{z}|^{−it} ) + M(U_{z}|X′_{z}|^{it′}, V_{z}(|Y′_{z}|^{−it} − |Y′_{z}|^{−it′}))|
⩽ |M(U_{z}(|X′_{z}|^{it} − |X′_{z}|^{it′}), V_{z}|Y′_{z}|^{−it} )| + |M(U_{z}|X′_{z}|^{it′}, V_{z}(|Y′_{z}|^{−it} − |Y′_{z}|^{−it′}))|.  (40)

The first absolute value in (40)is at most

SDP_{}(M) · ∥U_{z}(|X′_{z}|^{it} − |X′_{z}|^{it′})∥ · ∥V_{z}|Y′_{z}|^{−it} ∥ = SDP_{}(M) · ∥|X′_{z}|^{it} − |X′_{z}|^{it′}∥
⩽ SDP_{}(M) · log(max{∥X′_{z}∥, ∥(X′_{z})^{−1} ∥}) · |t − t′|.

We have ∥X′_{z}∥ ⩽ d as explained above, and ∥(X′_{z})^{−1} ∥ ⩽ 1/ε by the way our modified rounding procedure was defined. Similar bounds hold for Y′_{z}. It therefore suffices to pick t from a grid of size O(log(1/ε) max(1/ε^{2}, d/ε)).

2.3 The rounding procedure in the case of (18)

Theorem 4 addressed the performance of the rounding procedure described in Figure 1 with respect to inequality (16). Here we prove that this rounding procedure has the same performance with respect to the noncommutative Grothendieck inequality (18)as well. This is the content of the following theorem.

Theorem 7. Fix n, d ∈ and ε ∈ (0, 1). Suppose that M ∈ M_{n}(M_{n}( )) and that X, Y ∈ M_{n}( ^{d}) satisfy

max {∥XX^{∗}∥ + ∥X^{∗}X∥, ∥YY^{∗}∥ + ∥Y^{∗}Y∥} ⩽ 2,  (41)

and

| ∑_{i,j,k,l=1}^{n} M_{ijkl}⟨X_{ij}, Y_{kl}⟩| ⩾ (1 − ε)∥M∥_{nc},  (42)

where ∥M∥_{nc} was defined in (18). Then the rounding procedure described in Figure 1 outputs a pair of matrices A, B ∈ U_{n} such that

[ | ∑_{i,j,k,l=1}^{n} M_{ijkl} A_{ij}\overline{B_{kl}}| ] ⩾ ( \frac{1}{2} − ε) ∥M∥_{nc}.  (43)

Proof. We shall explain how to modify the argument presented in Section 2.1, relying on the notation that was introduced there. All we need to do is to replace (38)by the assertion

∀ t ∈ ,  |M(F(t), G(t))| ⩽ \frac{1}{2}∥M∥_{nc}.  (44)

To this end we use the following corollary of Claim 5, which is a slight variant of [Haa85, Lem. 4.1].

Corollary 8. Let W ∈ M_{n}( ^{d}) be a vector-valued matrix and z ∈ {1, −1, i, −i}^{d} chosen uniformly at random. Writing W_{z} = ⟨W, z⟩ ∈ M_{n}( ), we have

∥ _{z} [(W_{z}W_{z}^{∗})^{2}]∥ + ∥ _{z} [(W_{z}^{∗}W_{z})^{2}]∥ ⩽ ( ∥WW^{∗}∥+ ∥W^{∗}W∥)^{2}.  (45)

Proof. Starting from (29)and noting that

∥ ∑_{r=1}^{d} W_{r}(W^{∗}W − W_{r}^{∗}W_{r})W_{r}^{∗}∥ ⩽ ∥W^{∗}W∥ · ∥ ∑_{r=1}^{d} W_{r}W_{r}^{∗}∥ = ∥W^{∗}W∥· ∥WW^{∗}∥,

we obtain the inequality

∥ _{z} [(W_{z}W_{z}^{∗})^{2}]∥ ⩽ ∥WW^{∗}∥^{2} + ∥W^{∗}W∥· ∥WW^{∗}∥.  (46)

Similarly, from (30)we get

∥ _{z} [(W_{z}^{∗}W_{z})^{2}]∥ ⩽ ∥W^{∗}W∥^{2} + ∥WW^{∗}∥· ∥W^{∗}W∥.  (47)

By summing (46)and (47)one deduces (45).

Combining (33)with (45)for W = X/\sqrt{2}, we have

∥F(t)F(t)^{∗}∥ + ∥F(t)^{∗}F(t)∥ ⩽ \frac{1}{4}(∥XX^{∗}∥ + ∥X^{∗}X∥)^{2} ⩽^{(41)} 1.  (48)

Analogously,

∥G(t)G(t)^{∗}∥ + ∥G(t)^{∗}G(t)∥ ⩽ \frac{1}{4}(∥YY^{∗}∥ + ∥Y^{∗}Y∥)^{2} ⩽ 1.  (49)

Recalling the definition of ∥M∥_{nc}, it follows from (48)and (49)that for every t ∈ ,

| _{z}[ M(U_{z}|X_{z}|^{2+it} , V_{z}|Y_{z}|^{2−it} ) ]| =^{(32)}|M(F(t), G(t))| ⩽ \frac{1}{2}∥M∥_{nc}.  (50)

Hence,

z,t[ |M(A, B)| ] ⩾^{(27)∧(50)} M(X, Y) − \frac{1}{2}∥M∥_{nc} ⩾^{(42)} ( \frac{1}{2} − ε) ∥M∥_{nc},

completing the proof of the desired expectation bound (43).

Remark 9. The following example, due to Haagerup [Haa85], shows that the factor 2 approximation guarantee obtained in Theorem 7 is optimal: the best constant in (18) equals 2. Let M ∈ M_{n}(M_{n}( )) be given by M_{1jk1} = δ_{jk}, and M_{ijkl} = 0 if (i, l) ≠ (1, 1). A direct computation shows that Opt_{}(M) = 1. Define X, Y ∈ M_{n}( ^{n}) by X_{1j} = Y_{j1} = \sqrt{2/(n + 1)} e_{j} ∈ ^{n} for j ∈ {1, …, n} and all other entries of X and Y vanish (here e_{1}, …, e_{n} is the standard basis of n). Using these two vector-valued matrices one shows that ∥M∥_{nc} ⩾ 2n/(n + 1). Recall that in the Introduction we mentioned that it was shown in [HI95] that the best constant in the weaker inequality (16)is also 2, but the example exhibiting this stronger fact is more involved.

3 The real and Hermitian cases

The n × n Hermitian matrices are denoted H_{n}. A 4-tensor M ∈ M_{n}(M_{n}( )) ≅ M_{n}( ) ⊗ M_{n}( ) is said to be Hermitian if M_{ijkl} = \overline{M_{jilk}} for all i, j, k, l ∈ \{1, …, n\}. Investigating the noncommutative Grothendieck inequality in the setting of Hermitian M is most natural in applications to quantum information, while problems in real optimization as described in the Introduction lead to real M ∈ M_{n}(M_{n}( )). These special cases are treated in this section.

Consider the following Hermitian analogue of the quantity Opt_{}(M).

Opt_{}^{∗} (M) =^{def} sup_{\begin{matrix}A,B∈H_{n} \\ ∥A∥,∥B∥⩽1 \end{matrix}} | ∑_{i,j,k,l=1}^{n} M_{ijkl}A_{ij}\overline{B_{kl}}|.

Note that the convex hull of U_{n} consists of all the matrices A ∈ M_{n}( ) with ∥A∥ ⩽ 1, so by convexity for every M ∈ M_{n}(M_{n}( )) we have

Opt_{}(M) = sup_{\begin{matrix}A,B∈M_{n}( ) \\ ∥A∥,∥B∥⩽1 \end{matrix}} | ∑_{i,j,k,l=1}^{n} M_{ijkl}A_{ij}\overline{B_{kl}}|.  (51)

This explains why Opt_{}^{∗} (M) should indeed be viewed as a Hermitian analogue of Opt_{}(M). The real analogue of (51)is that, due to the fact that the convex hull of O_{n} consists of all the matrices A ∈ M_{n}( ) with ∥A∥ ⩽ 1, for every M ∈ M_{n}(M_{n}( )) we have

Opt_{}(M) = sup_{\begin{matrix}A,B∈M_{n}( ) \\ ∥A∥,∥B∥⩽1 \end{matrix}} | ∑_{i,j,k,l=1}^{n} M_{ijkl}A_{ij}B_{kl}|.  (52)

The following theorem establishes an algorithmic equivalence between the problems of approximating either of these two quantities.

Theorem 10. For every K ∈ [1, ∞) the following two assertions are equivalent.

1. There exists a polynomial time algorithm Alg^{∗} that takes as input a Hermitian M ∈ M_{n}(M_{n}( )) and outputs A, B ∈ H_{n} with max{∥A∥, ∥B∥} ⩽ 1 and Opt_{}^{∗} (M) ⩽ K|M(A, B)|.

2. There exists a polynomial time algorithm Alg that takes as input M ∈ M_{n}(M_{n}( )) and outputs U, V ∈ O_{n} such that Opt_{}(M) ⩽ KM(U, V).

In Section 3.2 we show that for every K > 2\sqrt{2} there exists an algorithm Alg^{∗} as in part 1) of Theorem 10. Consequently, we obtain the algorithm for computing Opt_{}(M) whose existence was claimed in Theorem 1. The implication 1) ⟹ 2) of Theorem 10 is the only part of Theorem 10 that will be used in this article; the reverse direction 2) ⟹ 1) is included here for completeness. Both directions of Theorem 10 are proved in Section 3.3.

3.1 Two-dimensional rounding

In this section we give an algorithmic version of Krivine’s proof [Kri79] that the 2-dimensional real Grothendieck constant satisfies K_{G}(2) ⩽ \sqrt{2}. The following theorem is implicit in the proof of [Kri79, Thm. 1].

Theorem 11 (Krivine). Let g : → be defined by g(x) = sign(cos(x)), and let f : [0, π/2) → be given by

f(t) =^{def} \{ \begin{matrix}1 & if 0 ⩽ t ⩽ \frac{π}{4}, \\ \frac{6}{π}( \frac{π}{2} − t) − \frac{1}{2}( \frac{4}{π})^{3}( \frac{π}{2} − t)^{3} & if \frac{π}{4} ⩽ t < \frac{π}{2}. \end{matrix}

Extend f to a function defined on all of by requiring that it is even and f(x + π) = −f(x) for all x ∈ . There exists a sequence {b_{2ℓ+1} }_{ℓ=0}^{∞} ∈ ^{}such that for every L ∈ the numbers {b_{0}, …, b_{2L+1} } can be computed in poly(L) time, ∑ _{ℓ=L+1}^{∞} |b_{2ℓ+1} | ⩽ C/L for some universal constant C, ∑ _{ℓ=0}^{∞} |b_{2ℓ+1} | = 1, and

∀x, y ∈ , cos(x − y) = \sqrt{2} ∑_{ℓ=0}^{∞} b_{2ℓ+1} \frac{1}{2π} ∫_{−π}^{π} f((2ℓ + 1)x − t)g(t − (2ℓ + 1)y)dt.

An explicit formula for the sequence {b_{2ℓ+1} }_{ℓ=0}^{∞} can be extracted as follows from the proof of [Kri79, Thm. 1]. For any ℓ ⩾ 0, define a_{2ℓ} = 0,

a_{2ℓ+1} = (−1)^{ℓ}cos ( \frac{(2ℓ + 1)π}{4} ) \frac{16}{π^{2}(2ℓ + 1)^{4}} ( \frac{1}{2ℓ + 1} − (−1)^{ℓ} \frac{π}{4} ),

b_{1} = \sqrt{2}(π/4)^{3}/(3a_{1}), and for ℓ > 0,

b_{2ℓ+1} = −\frac{1}{a_{1}} ∑_{\begin{matrix}d|(2ℓ+1) \\ d≠1 \end{matrix}} a_{d}b_{\frac{2ℓ+1}{d}} .

Then |a_{2ℓ+1} | = O(1/ℓ^{4}), from which one deduces the crude bound |b_{2ℓ+1} | = O(1/ℓ^{2}).

Two-dimensional rounding procedure

1. Let ε > 0 and, for j, k ∈ {1, …, n} let x_{j}, y_{k} ∈ with |x_{j}| = |y_{k}| = 1, be given as input. Let f, g, C and {b_{2ℓ+1} }_{ℓ=0}^{∞} be as in Theorem 11.

2. For every j, k let θ_{j} ∈ [0, 2π) (resp. ϕ_{k} ∈ [0, 2π)) be the angle that x_{j} (resp. y_{k}) makes with the x-axis.

3. Select t ∈ [−π, π] uniformly at random. Let L = ⌈C/ε⌉ and p = 1 − ∑ _{ℓ=L+1}^{∞} |b_{2ℓ+1} |. Select ℓ ∈ {−1, 0, …, L} with probability Pr(−1) = 1 − p and Pr(ℓ) = |b_{2ℓ+1} | for ℓ ∈ {0, …, L}.

4. For every j, k, if ℓ ⩾ 0 then set λ_{j} =^{def} sign(b_{2ℓ+1} )f((2ℓ + 1)θ_{j} − t) and μ_{k} =^{def} g(t − (2ℓ + 1)ϕ_{k}). Otherwise, set λ_{j} = 0, μ_{k} = 0.

5. Return (λ_{j})_{j∈{1,...,n}} and (μ_{k})_{k∈{1,...,n}}.

Figure 2: The two-dimensional rounding algorithm takes as input real 2-dimensional unit vectors. It returns real numbers of absolute value at most 1.

Figure 2 describes a two-dimensional rounding scheme derived from Theorem 11. The following claim states its correctness in a way that will be useful for us later.

Claim 12. Let ε > 0 and for every j, k ∈ {1, …, n} let x_{j}, y_{k} ∈ satisfy |x_{j}| = |y_{k}| = 1. Then the rounding procedure described in Figure 2 runs in time poly(n, 1/ε) and returns λ_{j}, μ_{k} ∈ with |λ_{j}|, |μ_{k}| ⩽ 1 for every j, k ∈ {1, …, n}, and

[ λ_{j} μ_{k}] = \frac{1}{\sqrt{2}} ℜ (x_{j}\overline{y_{k}}) + ε⟨x′_{j}, y′_{k}⟩,  (53)

where x′_{j}, y′_{k} ∈ L_{2}( ) are such that ∥x′_{j}∥_{2}, ∥y′_{k}∥_{2} ⩽ 1.

Proof. Fix j, k ∈ {1, …, n} and let θ_{j}, ϕ_{k} and λ_{j}, μ_{k} be as defined in Steps 2 and 4 of the rounding procedure, respectively. Applying Theorem 11,

[ λ_{j} μ_{k}] = ∑_{ℓ=0}^{L} b_{2ℓ+1} \frac{1}{2π} ∫_{−π}^{π} f((2ℓ + 1)θ_{j} − t)g(t − (2ℓ + 1)ϕ_{k})dt = \frac{1}{\sqrt{2}} cos(θ_{j} − ϕ_{k}) + η_{jk},

where

η_{jk} =^{def} − ∑_{ℓ=L+1}^{∞} b_{2ℓ+1} \frac{1}{2π} ∫_{−π}^{π} f((2ℓ + 1)θ_{j} − t)g(t − (2ℓ + 1)ϕ_{k})dt.

By definition, cos(θ_{j} − ϕ_{k}) = ℜ (x_{j}\overline{y_{k}}). Using 1 − ε ⩽ p ⩽ 1, which follows from the bound stated in Theorem 11, η_{jk} equals 1 − p ⩽ ε times a weighted average of the product of certain values taken by f and g, the former only depending on θ_{j} and the latter on ϕ_{k}. Equivalently, this weighted average can be written as the inner product of two vectors x′_{j}and y′_{k} of norm at most 1. Finally, all steps of the rounding procedure can be performed in time polynomial in n and 1/ε.

3.2 Rounding in the Hermitian case

Let M ∈ M_{n}(M_{n}( )) be Hermitian, and X, Y ∈ U_{n}( ^{d}). For every r ∈ {1, …, d} define as usual X_{r}, Y_{r} ∈ M_{n}( ) by (X_{r})_{jk} = (X_{jk})_{r} and (Y_{r})_{jk} = (Y_{jk})_{r}. Define X′, Y′∈ M_{n}( ^{2d}) by

X′_{jk} =^{def} ∑_{p=1}^{d} ( ( \frac{X_{p} + X_{p}^{∗}}{2} ) _{jk}e_{2p−1} + i ( \frac{X_{p} − X_{p}^{∗}}{2} ) _{jk}e_{2p}) ∈ ^{2d},

and

Y′_{jk} =^{def} ∑_{p=1}^{d} ( ( \frac{Y_{p} + Y_{p}^{∗}}{2}) _{jk}e_{2p−1} + i ( \frac{Y_{p} − Y_{p}^{∗}}{2}) _{jk}e_{2p}) ∈ ^{2d}.

Then (X′)(X′)^{∗} = (X′)^{∗}(X′) = (XX^{∗} + X^{∗}X)/2 = I, so X′∈ U_{n}( ^{2d}) and similarly Y′∈ U_{n}( ^{2d}). Moreover, since M is Hermitian, |M(X, Y)| = |M(X′, Y′)|. This shows that for the purpose of proving the noncommutative Grothendieck inequality for Hermitian M we may assume without loss of generality that the “component matrices” of X, Y are Hermitian themselves. Nevertheless, even in this case the rounding algorithm described in Figure 1 returns unitary matrices A, B that are not necessarily Hermitian. The following simple argument shows how Krivine’s twodimensional rounding scheme can be applied on the eigenvalues of A, B to obtain Hermitian matrices of norm 1, at the loss of a factor \sqrt{2} in the approximation. A similar argument, albeit not explicitly algorithmic, also appears in [RV12b, Claim 4.7].

Theorem 13. Let n be an integer, M ∈ M_{n}(M_{n}( )) Hermitian, ε ∈ (0, 1) and X, Y ∈ U_{n}( ^{d}) such that

| M(X, Y) | ⩾ (1 − ε)SDP_{}(M).

Then the rounding procedure described in Figure 3 runs in time polynomial in n and 1/ε and outputs a pair of Hermitian matrices A′, B′∈ M_{n}( ) with norm at most 1 such that

[ | M(A′, B′) | ] ⩾ ( \frac{1}{2\sqrt{2}} − ( 1 + \frac{1}{\sqrt{2}}) ε) SDP_{}(M).

Proof. Let A, B ∈ M_{n}( ) be as defined as in Step 2 of Figure 3, and assume as in Figure 3 that M(A, B) is real. By Theorem 4 we have [|M(A, B)|] ⩾ ( \frac{1}{2} − ε) SDP_{}(M). Hence to conclude it will suffice to show that for any fixed pair of matrices A, B ∈ M_{n}( ),

[ |M(A′, B′)| ] ⩾ \frac{1}{\sqrt{2}}|M(A, B)| − εSDP_{}(M),  (54)

Hermitian rounding procedure

1. Let X, Y ∈ M_{n}( ^{d}) and ε > 0 be given as input.

2. Let A, B ∈ M_{n}( ) be the unitary matrices returned by the complex rounding procedure described in Figure 1. If necessary, multiply A by a complex phase to ensure that M(A, B) is real. Write the spectral decompositions of A, B as

A = ∑_{j=1}^{n} e^{iθ_{j}}u_{j}u_{j}^{∗}  and  B = ∑_{k=1}^{n} e^{iϕ_{k}}v_{k}v_{k}^{∗},

where θ_{j}, ϕ_{k} ∈ and u_{j}, v_{k} ∈ ^{n}.

3. Apply the two-dimensional rounding algorithm from Figure 2 to the vectors x_{j} =^{def} e^{iθ_{j}} and

y_{k} =^{def} e^{iϕ_{k}}. Let λ_{j}, μ_{k} be the results.

4. Output

A′ =^{def} ∑_{j=1}^{n} λ_{j}u_{j}u_{j}^{∗}  and  B′ =^{def} ∑_{k=1}^{n} μ_{k}v_{k}v_{k}^{∗}.

Figure 3: The Hermitian rounding algorithm takes as input a pair of vector-valued matrices X, Y ∈ M_{n}( ^{d}). It outputs two Hermitian matrices A′, B′∈ M_{n}( ) of norm at most 1.

where A′, B′ are as returned by the rounding procedure and the expectation is over the random choices made in the two-dimensional rounding step, i.e., Step 3 of Figure 3. Applying Claim 12,

[ |M(A′, B′)|] ⩾ | ∑_{j,k=1}^{n} M(u_{j}u_{j}^{∗}, v_{k}v_{k}^{∗}) [λ_{j}μ_{k}]|

⩾^{(53)} | \frac{1}{\sqrt{2}} ∑_{j,k=1}^{n} M(u_{j}u_{j}^{∗}, v_{k}v_{k}^{∗})ℜ(e^{i(θ_{j}−ϕ_{k})} ) ]| − ε| ∑_{j,k=1}^{n}⟨x′_{j}, y′_{k}⟩ M(u_{j}u_{j}^{∗}, v_{k}v_{k}^{∗})|

= \frac{1}{\sqrt{2}}|M(A, B)| − ε|M(W, Z)|,  (55)

where in the last inequality, for the first term we used that M(u_{j}u_{j}^{∗}, v_{k}v_{k}^{∗}) is real since M is Hermitian, and for the second term we defined the vector-valued matrices

W =^{def} ∑_{j=1}^{n} x′_{j}u_{j}u_{j}^{∗} ∈ M_{n}(L_{2}( ))  and  Z =^{def} ∑_{k=1}^{n} y′_{k}v_{k}v_{k}^{∗} ∈ M_{n}(L_{2}( )).

One checks that WW^{∗} = ∑ _{j=1}^{n} ∥x′_{j}∥_{2}^{2}u_{j}u_{j}^{∗}. Since ∥x′_{j}∥_{2} ⩽ 1 for all j ∈ {1, …, n}, it follows that ∥WW^{∗}∥ ⩽ 1. Similarly max{∥W^{∗}W∥, ∥ZZ^{∗}∥, ∥Z^{∗}Z∥} ⩽ 1. Applying Lemma 6 we obtain R, S ∈ U_{n}(ℓ_{2}( )) such that M(W, Z) = M(R, S), hence |M(W, Z)| ⩽ SDP_{}(M). Eq. (55)then implies the desired estimate (54).

3.3 Proof of Theorem 10

In this section we prove Theorem 10. We first record for future use the following simple lemma, which is an algorithmic version of (52).

Lemma 14. There exists a polynomial time algorithm that takes as input a 4-tensor M ∈ M_{n}(M_{n}( )) and two matrices A, B ∈ M_{n}( ) with max{∥A∥, ∥B∥} ⩽ 1 and outputs two orthogonal matrices U, V ∈ O_{n} such that

∑_{i,j,k,l=1}^{n} M_{ijkl}A_{ij}B_{kl} ⩽ ∑_{i,j,k,l=1}^{n} M_{ijkl}U_{ij}V_{kl}.

Proof. Write the singular value decompositions of A, B as A = ∑ _{i=1}^{n} σ_{i}e_{i}f_{i}^{∗} and B = ∑ _{i=1}^{n} τ_{i}g_{i}h_{i}^{∗}, where each of the sequences (e_{i})_{i=1}^{n} , (f_{i})_{i=1}^{n} , (g_{i})_{i=1}^{n} , (h_{i})_{i=1}^{n} ⊆ ^{n} is orthonormal, and σ, τ ∈ [0, 1]^{n} (since max{∥A∥, ∥B∥} ⩽ 1). Now, M(A, B) is given by

∑_{i,j=1}^{n} σ_{i}τ_{j}M(e_{i}f_{i}^{∗}, g_{j}h_{j}^{∗}).  (56)

Fixing all σ_{i}, τ_{j} but, say, σ_{1}, (56)is a linear function of σ_{1}, and thus we can shift σ_{1} to either −1 or 1, without decreasing (56). Proceeding in this way with the other variables σ_{2}, …, σ_{n}, τ_{1}, …, τ_{n}, each one in its turn, we obtain ε, δ ∈ {−1, 1}^{n} such that if we define U, V ∈ O_{n} by U = ∑ _{i=1}^{n} ε_{i}(e_{i}f_{i}^{∗}) and V = ∑ _{i=1}^{n} δ_{i}(g_{i}h_{i}^{∗}) then M(A, B) ⩽ M(U, V), as required.

Proof of Theorem 10.We first prove the implication 1) ⟹ 2). For any A ∈ M_{2n}( ) define A_{1}, A_{2}, A_{3}, A_{4} ∈ M_{n}( ) through the block decomposition A = ( \begin{matrix}A_{1} & A_{2} \\ A_{3} & A_{4} \end{matrix} ). Given M ∈ M_{n}(M_{n}( )) let M′∈ M_{2n}(M_{2n}( )) be such that M′(A, B) = M(ℜA_{2}, ℜB_{2}) for every A, B ∈ H_{2n}. Formally, for every i, j, k, l ∈ {1, …, 2n} we have

M′_{ijkl} = \frac{1}{4} \{ \begin{matrix}M_{i,j−n,k,l−n} & if (i, k) ∈ \{1, …, n\}^{2} and (j, l) ∈ \{n + 1, …, 2n\}^{2}, \\ M_{j,i−n,l,k−n} & if (j, l) ∈ \{1, …, n\}^{2} and (i, k) ∈ \{n + 1, …, 2n\}^{2}, \\ M_{i,j−n,l,k−n} & if (i, l) ∈ \{1, …, n\}^{2} and (j, k) ∈ \{n + 1, …, 2n\}^{2}, \\ M_{j,i−n,k,l−n} & if (j, k) ∈ \{1, …, n\}^{2} and (i, l) ∈ \{n + 1, …, 2n\}^{2}, \\ 0 & otherwise. \end{matrix}

Then M′ is Hermitian. Apply the algorithm Alg^{∗} (whose existence is the premise of part 1) of Theorem 10) to M′to get A, B ∈ H_{2n} such that Opt_{}^{∗} (M) ⩽ K|M(A, B)|. Since A, B ∈ H_{2n} we have A_{3} = A_{2}^{∗} and B_{3} = B_{2}^{∗}. Because max{∥A∥, ∥B∥} ⩽ 1 also max{∥ℜA∥, ∥ℜB∥} ⩽ 1. By Lemma 14 we can therefore efficiently find U, V ∈ O_{n} such that

KM(U, V) ⩾ K|M(ℜA, ℜB)| = K|M′(A, B)| ⩾ Opt_{}^{∗} (M′)

= sup_{\begin{matrix}C,D∈H_{2n} \\ ∥C∥,∥D∥⩽1 \end{matrix}} |M′(C, D)| ⩾ sup_{S,T∈O_{n}} |M′(( \begin{matrix}0 & S \\ S^{∗} & 0 \end{matrix}) , ( \begin{matrix}0 & T \\ T^{∗} & 0 \end{matrix}))| = sup_{S,T∈O_{n}} M(S, T) = Opt_{}(M).

To prove the reverse implication 2) ⟹ 1), define ψ : M_{2n}( ) → H_{n} by

ψ ( ( \begin{matrix}A_{1} & A_{2} \\ A_{3} & A_{4} \end{matrix} ) ) =^{def} \frac{1}{4} (A_{1} + A_{1}^{∗} + A_{4} + A_{4}^{∗}) + \frac{i}{4} (A_{2} − A_{2}^{∗} + A_{3}^{∗} − A_{3}) ∈ H_{n}.  (57)

Suppose that M ∈ M_{n}(M_{n}( )) is Hermitian and define M′′ ∈ M_{2n}(M_{2n}( )) by requiring that M′′(A, B) = M (ψ(A), ψ(B)) for every A, B ∈ M_{2n}( ). Note that M(ψ(A), ψ(B)) ∈ since M, ψ(A), ψ(B) are all Hermitian. Apply the algorithm Alg of part 2) to M′′, obtaining two orthogonal matrices U, V ∈ O_{2n} satisfying Opt_{}(M′′) ⩽ KM′′(U, V) = KM(ψ(U), ψ(V)). By Lemma 15 below we have max{∥ψ(U)∥, ∥ψ(V)∥} ⩽ 1. Moreover, using Lemma 16 below we have

Opt_{}(M′′) = sup_{\begin{matrix}A,B∈M_{2n}( ) \\ ∥A∥,∥B∥⩽1 \end{matrix}} |M(ψ(A), ψ(B))| ⩾ sup_{\begin{matrix}X,Y∈H_{n} \\ ∥X∥,∥Y∥⩽1 \end{matrix}} |M (ψ (( \begin{matrix}ℜX & ℑX \\ −ℑX & ℜX \end{matrix} )) , ψ (( \begin{matrix}ℜY & ℑY \\ −ℑY & ℑY \end{matrix} ))) | . (58)

Observe that for every X ∈ H_{n} we have ψ (( \begin{matrix}ℜX & ℑX \\ −ℑX & ℜX \end{matrix} )) = X. Consequently the rightmost term in (58) equals Opt_{}^{∗} (M). Therefore Opt_{}^{∗} (M) ⩽ K|M(ψ(U), ψ(V))|, so that the algorithm that outputs ψ(U), ψ(V) has the desired approximation factor.

Lemma 15. Let ψ : M_{2n}( ) → H_{n} be given as in (57). Then ∥ψ(Y)∥ ⩽ ∥Y∥ for all Y ∈ M_{2n}( ).

Proof. For Y ∈ M_{2n}( ) write Z = (Y + Y^{∗})/2. Setting Z = ( \begin{matrix}Z_{1} & Z_{2} \\ Z_{3} & Z_{4} \end{matrix} ), where Z_{1}, Z_{2}, Z_{3}, Z_{4} ∈ M_{n}( ), we then have ψ(Y) = (Z_{1} + Z_{4})/2 + i(Z_{2} − Z_{3})/2. Take z ∈ ^{n} and write z = x + iy, where x, y ∈ ^{n}. Then

ℜ(⟨ψ(Y)z, z⟩)

= \frac{⟨Z_{1}x, x⟩ + ⟨Z_{4}y, y⟩ − ⟨Z_{2}y, x⟩ − ⟨Z_{3}x, y⟩}{2} + \frac{⟨Z_{1}y, y⟩ + ⟨Z_{4}x, x⟩ + ⟨Z_{2}x, y⟩ + ⟨Z_{3}y, x⟩}{2}

= \frac{1}{2} ⟨ Z ( \begin{matrix}x \\ −y \end{matrix} ) , ( \begin{matrix}x \\ −y \end{matrix} ) ⟩ + \frac{1}{2} ⟨ Z ( \begin{matrix}y \\ x \end{matrix}) , ( \begin{matrix}y \\ x \end{matrix}) ⟩ .

Since ψ(Y) is Hermitian, it follows that ∥ψ(Y)∥ ⩽ ∥Z∥ ⩽ ∥Y∥.

Lemma 16. For every X ∈ H_{n} we have ∥( \begin{matrix}ℜX & ℑX \\ −ℑX & ℜX \end{matrix} )∥ = ∥X∥.

Proof. Write Z = ( \begin{matrix}ℜX & ℑX \\ −ℑX & ℜX \end{matrix} ) ∈ M_{2n}( ). Since X is Hermitian, Z is symmetric. For every a, b ∈ ^{n},

⟨ Z ( \begin{matrix}a \\ b \end{matrix}) , ( \begin{matrix}a \\ b \end{matrix}) ⟩ = ⟨(ℜX)a, a⟩ + ⟨(ℑX)b, a⟩ − ⟨(ℑX)a, b⟩ + ⟨(ℜX)b, b⟩
= ℜ (⟨X(a − ib), a − ib⟩) .

Since Z is symmetric and X is Hermitian, it follows that ∥Z∥ = ∥X∥.

4 Direct rounding in the real case

We now describe and analyze a different rounding procedure for the real case of the noncommutative Grothendieck inequality. The argument is based on the proof of the noncommutative Grothendieck inequality due to Kaijser [Kai83], which itself has a structure similar to the proof of the classical Grothendieck inequality due to Krivine [Kri74] (see also [Jam85], the “Notes and Remarks” section of Chapter 1 of [DJT95], and the survey article [JL01]), and uses ideas from [Pis78] to extend that proof to the non-commutative setting.

Real rounding procedure

1. Let X, Y ∈ M_{n}( ^{d}) be given as input, and let ε ∈ {−1, 1}^{d} be chosen uniformly at random.

2. Set Y_{ε} =^{def} ⟨ε, Y⟩. Write the singular value decomposition of Y_{ε} as Y_{ε} = ∑ _{i=1}^{n} t_{i}(ε) u_{i}(ε)v_{i}(ε)^{∗}, where t_{i}(ε) ∈ [0, ∞) and u_{i}(ε), v_{i}(ε) ∈ ^{n}. Define

(Y_{ε})_{τ} =^{def} ∑_{i=1}^{n} min{t_{i}(ε), τ}u_{i}(ε)v_{i}(ε)^{∗},

where τ =^{def} \sqrt{3}/2.

3. Let X(ε) ∈ M_{n}( ) of norm at most 1 be such that

M(X(ε), (Y_{ε})_{τ}) = max_{\begin{matrix}X∈M_{n}( ) \\ ∥X∥⩽1 \end{matrix}} |M(X, (Y_{ε})_{τ})|.

4. Output the pair A = X(ε) and B = \frac{1}{τ}(Y_{ε})_{τ}.

Figure 4: The real rounding algorithm takes as input X, Y ∈ M_{n}( ^{d}). It outputs two real matrices A, B ∈ M_{n}( ) of norm at most 1.

Theorem 17. Given n ∈ , M ∈ M_{n}(M_{n}( )) and η ∈ (0, 1/2), suppose that X, Y ∈ O_{n}( ^{d}) are such that

| M(X, Y) | ⩾ (1 − η)SDP_{}(M),  (59)

where SDP_{}(M) is defined in (12). Then the rounding procedure described in Figure 4 runs in time polynomial in n and outputs a pair of real matrices A, B ∈ M_{n}( ) with norm at most 1 such that

[ | M(A, B) | ] ⩾ \frac{(1 − 2η)^{2}}{3\sqrt{3}} SDP_{}(M).  (60)

Note that by Lemma 14 we can also efficiently convert the matrices A, B to orthogonal matrices U, V ∈ O_{n} without changing the approximation guarantee.

The proof of Theorem 17 relies on two claims that are used to bound the error that results from the truncation step (step 2) in the rounding procedure in Figure 4. The first claim plays the same role as Claim 5 did in the complex case.

Claim 18. Fix X ∈ M_{n}( ^{d}) and let ε ∈ {−1, 1}^{d} be chosen uniformly at random. Set X_{ε} = ⟨ε, X⟩. Then

ε[(X_{ε}X_{ε}^{∗})^{2}] ⩽ (XX^{∗})^{2} + 2∥X^{∗}X∥XX^{∗},
ε[(X_{ε}^{∗}X_{ε})^{2}] ⩽ (X^{∗}X)^{2} + 2∥XX^{∗}∥X^{∗}X.

Proof. Define the symmetric real vector-valued matrix Z by

Z =^{def} ( \begin{matrix}0 & X \\ X^{∗} & 0 \end{matrix}) .

Following the proof of Lemma 1.1 in [Pis78] (which establishes a bound analogous to the one proved in Claim 8 for the case of i.i.d. {±1} random variables) and defining as usual Z_{r} ∈ M_{n}( ) by (Z_{r})_{ij} = (Z_{ij})_{r} for every r ∈ {1, …, d}, we have

ε[⟨ε, Z⟩^{4}] = ∑_{r=1}^{d} Z_{r}^{4} + ∑_{\begin{matrix}r,s∈\{1,...,d\} \\ r≠s \end{matrix}} (Z_{r}^{2}Z_{s}^{2} + Z_{r}Z_{s}Z_{r}Z_{s} + Z_{r}Z_{s}^{2}Z_{r})

= ( ∑_{r=1}^{d} Z_{r}^{2})^{2} + ∑_{\begin{matrix}r,s∈\{1,...,d\} \\ r<s \end{matrix}} (Z_{r}Z_{s} + Z_{s}Z_{r})^{2}.  (61)

Using the inequality (A + B)(A + B)^{∗} ⩽ 2(AA^{∗} + BB^{∗}), which holds for all A, B ∈ M_{n}( ), we can bound the second sum in (61)as follows.

∑_{\begin{matrix}r,s∈\{1,...,d\} \\ r<s \end{matrix}} (Z_{r}Z_{s} + Z_{s}Z_{r})^{2} ⩽ 2 ( ∑_{r=1}^{d} Z_{r}( ∑_{\begin{matrix}s∈\{1,...,d\} \\ s>r \end{matrix}} Z_{s}^{2}) Z_{r} + ∑_{s=1}^{d} Z_{s}( ∑_{\begin{matrix}r∈\{1,...,d\} \\ r<s \end{matrix}} Z_{r}^{2}) Z_{s})

= 2 ∑_{r=1}^{d} Z_{r}( ∑_{\begin{matrix}s∈\{1,...,d\} \\ s≠r \end{matrix}} Z_{s}^{2}) Z_{r}

⩽ 2 ∑_{r=1}^{d} Z_{r}( ∑_{s=1}^{d} Z_{s}^{2}) Z_{r}.

Replacing Z_{r} by its definition and using ABA^{∗} ⩽ ∥B∥AA^{∗}, which holds true for every positive semidefinite B ∈ M_{n}( ), we arrive at the following matrix inequality:

ε[⟨ε, Z⟩^{4}] = ( \begin{matrix}_{ε}[(X_{ε}X_{ε}^{∗})^{2}] & 0 \\ 0 & _{ε}[(X_{ε}^{∗}X_{ε})^{2}] \end{matrix} )
⩽ ( \begin{matrix}(XX^{∗})^{2} & 0 \\ 0 & (X^{∗}X)^{2} \end{matrix}) + 2 ( \begin{matrix}∥X^{∗}X∥ XX^{∗} & 0 \\ 0 & ∥XX^{∗}∥ X^{∗}X \end{matrix}) .

The inequality above implies a separate matrix inequality for both diagonal blocks, proving the claim.

The second claim appears as Lemma 2.3 in [Kai83] (in the complex case). We include a short proof for the sake of completeness.

Claim 19. Let Y ∈ M_{n}( ). For any τ > 0, there exists a decomposition Y = Y_{τ} + Y^{τ} such that ∥Y_{τ}∥_{∞} ⩽ τ and

Y^{τ}(Y^{τ})^{∗} ⩽ \frac{1}{(4τ)^{2}}(YY^{∗})^{2} and (Y^{τ})^{∗}Y^{τ} ⩽ \frac{1}{(4τ)^{2}}(Y^{∗}Y)^{2}.

Proof. Define Y_{τ} by “truncating” the singular values of Y at τ, as is done in step 2 of the rounding procedure described in Figure 4, so that ∥Y_{τ}∥ ⩽ τ. Define Y^{τ} = Y − Y_{τ}. By definition, Y, Y_{τ} and Y^{τ} all have the same singular vectors, and the non-zero singular values of Y^{τ} are of the form μ − τ, where μ ⩾ τ is a singular value of Y. Using the bound |μ − τ| ⩽ μ^{2}/(4τ) valid for any μ ⩾ τ, any nonzero eigenvalue λ = (μ − τ)^{2} of Y^{τ}(Y^{τ})^{∗} (resp. (Y^{τ})^{∗}Y^{τ}) satisfies λ ⩽ μ^{4}/(4τ)^{2}, which proves the claim.

Proof of Theorem 17.We shall continue using the notation introduced in Figure 4, Claim 18 and Claim 19. Let X, Y ∈ O_{n}( ^{d}) satisfying (59). For every ε ∈ {−1, 1}^{d} and any τ > 0 let

Y_{ε} = ⟨ε, Y⟩ = (Y_{ε})_{τ} + Y_{ε}^{τ}

be the decomposition promised by Claim 19. Combining the bound from Claim 18 with the one from Claim 19, we see that

∥ _{ε}[Y_{ε}^{τ}(Y_{ε}^{τ})^{∗}]∥ ⩽ \frac{1}{(4τ)^{2}}(∥YY^{∗}∥^{2} + 2∥Y^{∗}Y∥∥YY^{∗}∥) = \frac{3}{(4τ)^{2}},  (62)

where the final step of (62)follows from Y ∈ O_{n}( ^{d}), and the same bound holds on ∥ _{ε}[(Y_{ε}^{τ})^{∗}Y_{ε}^{τ}]∥. We have

|M(X, Y)| = | _{ε}[M(X_{ε}, Y_{ε})]| ⩽ | _{ε}[M(X_{ε}, (Y_{ε})_{τ})]| + | _{ε}[M(X_{ε}, Y_{ε}^{τ})]|
⩽ | _{ε}[M(X_{ε}, (Y_{ε})_{τ})]| + \frac{\sqrt{3}}{4τ}SDP_{}(M),  (63)

where the last inequality in (63)follows from the definition of SDP_{}(M) and (62).

To bound the first term in (63), let X_{ε} = ∑ _{i=1}^{n} s_{i}(ε)w_{i}(ε)z_{i}(ε)^{∗}, (Y_{ε})_{τ} = ∑ _{i=1}^{n} t′_{i}(ε)u_{i}(ε)v_{i}(ε)^{∗}, where s_{i}(ε), t′_{i}(ε) ⩾ 0 and u_{i}(ε), v_{i}(ε), w_{i}(ε), z_{i}(ε) ∈ ^{n}, be the singular value decompositions of

X_{ε}, (Y_{ε})_{τ}, respectively. Set M_{i,j}(ε) =^{def} M(w_{i}(ε)z_{i}(ε)^{∗}, u_{j}(ε)v_{j}(ε)^{∗}). With these definitions,

| _{ε}[M(X_{ε}, (Y_{ε})_{τ})] | = | _{ε}[ ∑_{i,j=1}^{n} M_{i,j}(ε)s_{i}(ε)t′_{j}(ε)]| ⩽ _{ε}[ ∑_{i=1}^{n} s_{i}(ε) | ∑_{j=1}^{n} M_{i,j}(ε)t′_{j}(ε)|]

⩽ ( _{ε}[ ∑_{i=1}^{n} s_{i}(ε)^{2}| ∑_{j=1}^{n} M_{i,j}(ε)t′_{j}(ε)|])^{1/2}( _{ε}[ ∑_{i=1}^{n} | ∑_{j=1}^{n} M_{i,j}(ε)t′_{j}(ε)|])^{1/2}. (64)

Note that the rightmost term in (64) is at most ( τ _{ε}[M(X(ε), B(ε))])^{1/2}, where B(ε) = \frac{1}{τ}(Y_{ε})_{τ} and X(ε) is as defined in the rounding procedure in Figure 4. To bound the leftmost term in (64), define W_{ε} =^{def} ∑ _{i=1}^{n} (r_{i}(ε)s_{i}(ε)^{2})w_{i}(ε)z_{i}(ε)^{∗}, where r_{i}(ε) is the sign of ∑ _{j=1}^{n} M_{i,j}(ε)t′_{j}(ε), so that

∑_{i=1}^{n} s_{i}(ε)^{2}| ∑_{j=1}^{n} M_{i,j}(ε)t′_{j}(ε)| = M(W_{ε}, (Y_{ε})_{τ}).

Moreover, by definition W_{ε}W_{ε}^{∗} = (X_{ε}X_{ε}^{∗})^{2}, so using Claim 18 we have

∥ _{ε}[W_{ε}^{∗}W_{ε}]∥ = ∥ _{ε}[(X_{ε}^{∗}X_{ε})^{2}] ∥ ⩽ ∥X^{∗}X∥^{2} + 2∥XX^{∗}∥∥X^{∗}X∥ = 3,

and the same bound holds for ∥ _{ε}[W_{ε}W_{ε}^{∗}]∥. By the definition of (Y_{ε})_{τ} we also have

max { ∥ _{ε}[(Y_{ε})_{τ}^{∗}(Y_{ε})_{τ}]∥, ∥ _{ε}[(Y_{ε})_{τ}(Y_{ε})_{τ}^{∗}]∥} ⩽ τ^{2}.

Hence

ε[ ∑_{i=1}^{n} s_{i}(ε)^{2}| ∑_{j=1}^{n} M_{i,j}(ε)t′_{j}(ε)|] = \sqrt{3}τ _{ε}[M( \frac{W_{ε}}{\sqrt{3}}, \frac{(Y_{ε})_{τ}}{τ}) ] ⩽ \sqrt{3}τ SDP_{}(M),

where we used the definition of SDP_{}(M). Finally, combining (63) and (64) with the bounds shown above we obtain

(1 − η)SDP_{}(M) ⩽^{(59)} |M(X, Y)| ⩽ \sqrt[4]{3}τ\sqrt{SDP_{}(M) · _{ε}[M(X(ε), B(ε))]} + \frac{\sqrt{3}}{4τ}SDP_{}(M). (65)

Setting τ = \sqrt{3}/2 in (65)and simplifying leads to the desired bound (60).

All steps in the rounding procedure can be performed efficiently. The calculation of X(ε) in the third step of Figure 4 can be expressed as a semidefinite program and solved in time polynomial in n. Alternatively, one may directly compute X(ε) by writing the polar decomposition

Tr_{2}(M^{∗}(I ⊗ B)) = QP ∈ M_{n}( ),

where the partial trace is taken with respect to the second tensor, Q is an orthogonal matrix and P is positive semidefinite, and taking X(ε) = Q^{∗}.

5 Some applications

Before presenting the details of our applications of Theorem 1, we observe that the problem of computing Opt_{}(M) is a rather versatile optimization problem, perhaps more so than what one might initially guess from its definition. The main observation is that by considering matrices M which only act non-trivially on certain diagonal blocks of the two variables U, V that appear in the definition of Opt_{}(M), these variables can each be thought of as a sequence of multiple matrix variables, possibly of different shapes but all with operator norm at most 1. This allows for some flexibility in adapting the noncommutative Grothendieck optimization problem to concrete settings, and we explain the transformation in detail next.

For every n, m ⩾ 1, let M_{m,n}( ) be the vector space of real m × n matrices. Given integers k, ℓ ⩾ 1 and sequences of integers (m_{i}), (n_{i}) ∈ ^{k}, (p_{j}), (q_{j}) ∈ ^{ℓ}, we define Bil_{}(k, ℓ; (m_{i}), (n_{i}), (p_{j}), (q_{j})), or simply Bil_{}(k, ℓ) when the remaining sequences are clear from context, as the set of all

f : ( ⨁_{i=1}^{k} M_{m_{i},n_{i}}( )) × ( ⨁_{j=1}^{ℓ} M_{p_{j},q_{j}}( )) →

that are linear in both arguments. Concretely, f ∈ Bil_{}(k, ℓ) if and only if there exists real coefficients α_{irs,juv} such that for every (A_{i}) ∈ ⨁ _{i=1}^{k} M_{m_{i},n_{i}}( ) and (B_{j}) ∈ ⨁ _{j=1}^{ℓ} M_{p_{j},q_{j}}( ),

f((A_{i})_{i∈{1,...,k}}, (B_{j})_{j∈{1,...,ℓ}} ) = ∑_{i=1}^{k} ∑_{j=1}^{ℓ} ∑_{r=1}^{m_{i}} ∑_{s=1}^{n_{i}} ∑_{u=1}^{p_{j}} ∑_{v=1}^{q_{j}} α_{irs,juv} (A_{i})_{rs}(B_{j})_{uv}.  (66)

For integers m, n ⩾ 1, let O_{m,n} ⊂ M_{m,n}( ) denote the set of all m × n real matrices U such that UU^{∗} = I if m ⩽ n and U^{∗}U = I if m ⩾ n. If m = n then O_{n,n} = O_{n} is the set of orthogonal matrices; O_{n,1} is the set of all n-dimensional unit vectors; O_{1,1} is simply the set {−1, 1}. Given f ∈ Bil_{}(k, ℓ), consider the quantity

Opt_{}(f) =^{def} sup_{\begin{matrix}(U_{i})∈⨁ _{i=1}^{k} O_{m_{i},n_{i}} \\ (V_{j})∈⨁ _{j=1}^{ℓ} O_{p_{j},q_{j}} \end{matrix}} f((U_{i}), (V_{j})).

Note that this definition coincides with the definition of Opt_{}(f) given in the introduction whenever f ∈ Bil_{}(1, 1; n, n, n, n). The proof of the following proposition shows that the new optimization problem still belongs the framework of the noncommutative Grothendieck problem.

Proposition 20. There exists a polynomial time algorithm that takes as input k, ℓ ∈ , (m_{i}), (n_{i}) ∈ ^{k}, (p_{j}), (q_{j}) ∈ ^{ℓ} and f ∈ Bil_{}(k, ℓ; (m_{i}), (n_{i}), (p_{j}), (q_{j})) and outputs (U_{i}) ∈ ⨁ _{i=1}^{k} O_{m_{i},n_{i}} and (V_{j}) ∈ ⨁ _{j=1}^{ℓ} O_{p_{j},q_{j}} such that

Opt_{}(f) ⩽ O(1) · f((U_{i}), (V_{j})).

Moreover, the implied constant in the O(1) term can be taken to be any number larger than 2\sqrt{2}.

Proof. Let k, ℓ ∈ , (m_{i}), (n_{i}) ∈ ^{k}, (p_{j}), (q_{j}) ∈ ^{ℓ} be given, and define

m =^{def} ∑_{i=1}^{k} m_{i},  n =^{def} ∑_{i=1}^{k} n_{i},  p =^{def} ∑_{j=1}^{ℓ} p_{j},  q =^{def} ∑_{j=1}^{ℓ} q_{j},

and t =^{def} max{m, n, p, q}. We first describe how ⨁ _{i=1}^{k} M_{m_{i},n_{i}}( ) (respectively ⨁ _{j=1}^{ℓ} M_{p_{j},q_{j}}( )) can be identified with a subset of M_{t}( ) consisting of block diagonal matrices. For any i ∈ {1, …, k} and r ∈ {1, …, m_{i}}, s ∈ {1, …, n_{i}}, let F_{r,s}^{i} ∈ M_{t}( ) be the matrix that has all entries equal to 0 except the entry in position (r + ∑ _{j<i} m_{j}, s + ∑ _{j<i} n_{j}), which equals 1. Similarly, for any j ∈ {1, …, ℓ} and u ∈ {1, …, p_{j}}, v ∈ {1, …, q_{j}} we let G_{u,v}^{j} ∈ M_{t}( ) be the matrix that has all entries equal to 0 except the entry in position (u + ∑ _{i<j} p_{i}, v + ∑ _{i<j} q_{i}), which equals 1. Define linear maps Φ : ⨁ _{i=1}^{k} M_{m_{i},n_{i}}( ) → M_{t}( ) and Ψ : ⨁ _{j=1}^{ℓ} M_{p_{j},q_{j}}( ) → M_{t}( ) by

Φ((A_{i})) =^{def} ∑_{i=1}^{k} ∑_{r=1}^{m_{i}} ∑_{s=1}^{n_{i}} (A_{i})_{r,s} F_{r,s}^{i}  and  Ψ((B_{j})) =^{def} ∑_{j=1}^{ℓ} ∑_{u=1}^{p_{j}} ∑_{v=1}^{q_{j}} (B_{j})_{u,v} G_{u,v}^{j}.

From the definition, one verifies that

∥Φ((A_{i}))∥ = max_{i∈{1,...,k}} ∥A_{i}∥  and  ∥Ψ((B_{j}))∥ = max_{j∈{1,...,ℓ}} ∥B_{j}∥.  (67)

Let f ∈ Bil_{}(k, ℓ) and (α_{irs,juv}) real coefficients as in (66). Define M ∈ M_{t}(M_{t}( )) by

M(F_{r,s}^{i}, G_{u,v}^{j}) =^{def} α_{irs,juv},

and M(A, B) =^{def} 0 if A or B are not in the linear span of the F_{r,s}^{i} or G_{u,v}^{j} respectively. (Recall that the notation M(A, B) was introduced at the beginning of Section 2.) With this definition, for any (A_{i}) ∈ ⨁ _{i=1}^{k} M_{m_{i},n_{i}}( ) and (B_{j}) ∈ ⨁ _{j=1}^{ℓ} M_{p_{j},q_{j}}( ) we have

M(Φ((A_{i})), Ψ((B_{j}))) = f((A_{i}), (B_{j})).

We claim that Opt_{}(f) = Opt_{}(M), where Opt_{}(M) is as defined in the Introduction. Indeed, by (67) for any (U_{i}) ∈ ⨁ _{i=1}^{k} O_{m_{i},n_{i}} and (V_{j}) ∈ ⨁ _{j=1}^{ℓ} O_{p_{j},q_{j}} we have ∥Φ((U_{i}))∥, ∥Ψ((V_{j}))∥ ⩽ 1, hence Opt_{}(f) ⩽ Opt_{}(M). Conversely, let U, V ∈ O_{t} be arbitrary, and U′, V′ their orthogonal projections on Im(Φ), Im(Ψ) respectively. Then M(U′, V′) = M(U, V). Moreover, if

(U′_{i}) ∈ ⨁_{i=1}^{k} M_{m_{i},n_{i}}( )  and  (V′_{j}) ∈ ⨁_{j=1}^{ℓ} M_{p_{j},q_{j}}( )

are such that Φ((U′_{i})) = U′and Ψ((V′_{j})) = V′then by (67)max_{i∈{1,...,k}} ∥U′_{i}∥ = ∥U′∥ ⩽ ∥U∥ = 1, and similarly max_{j∈{1,...,ℓ}} ∥V′_{j}∥ ⩽ 1. As in the proof of Lemma 14, we may then argue that there exists U_{i} ∈ O_{m_{i},n_{i}}, V_{j} ∈ O_{p_{j},q_{j}} such that

f((U_{i}), (V_{j})) ⩾ f((U′_{i}), (V′_{j})) = M(U′, V′) = M(U, V),

proving the reverse inequality Opt_{}(f) ⩾ Opt_{}(M).

To conclude the proof of Proposition 20 it remains to note that the algorithm of Theorem 1, when applied to M, produces in polynomial time U, V ∈ O_{t} such that Opt_{}(M) ⩽ O(1) · M(U, V). Arguing as in Lemma 14, (U_{i}) and (V_{j}) can be computed from U, V in polynomial time and constitute the output of the algorithm.

5.1 Constant-factor algorithm for robust PCA problems

We start with the R1-PCA problem, as described in (3). Let a_{1}, …, a_{N} ∈ ^{n} be given, and define f ∈ Bil_{}(1, N; (K), (n), (1, …, 1), (K, …, K)) by

f(Y, (Z_{1}, …, Z_{N})) =^{def} ∑_{i=1}^{N} ∑_{k=1}^{K} (Z_{i})_{1k}( ∑_{j=1}^{n} Y_{kj}(a_{i})_{j}).

The condition Z_{i} ∈ O_{1,K} is equivalent to Z_{i} being a unit vector, while Y ∈ O_{K,n} is equivalent to the K rows of Y being orthonormal. Using that the ℓ_{2} norm of a vector u ∈ ^{K} is equal to max_{v∈S^{K−1}} ⟨u, v⟩, the quantity appearing in (3)is equal to

sup_{\begin{matrix}Y∈O_{K,n} \\ Z_{1},...,Z_{N}∈O_{1,K} \end{matrix}} f(Y, (Z_{1}, …, Z_{N})),

which by definition is equal to Opt_{}(f). An approximation algorithm for the R1-PCA problem then follows immediately from Proposition 20. The algorithm for L1-PCA follows similarly. Letting g ∈ Bil_{}(1, NK; (K), (n), (1, …, 1), (1, …, 1)) be defined as

g(Y, (Z_{1,1}, …, Z_{N,K})) = ∑_{i=1}^{N} ∑_{k=1}^{K} Z_{ik}( ∑_{j=1}^{n} Y_{kj}(a_{i})_{j}),

and using that Z_{ik} ∈ O_{1,1} is equivalent to Z_{ik} ∈ {−1, 1}, the quantity appearing in (4)is equal to

sup_{\begin{matrix}Y∈O_{K,n} \\ Z_{1,1},...,Z_{N,K}∈O_{1,1} \end{matrix}} g(Y, (Z_{1,1}, …, Z_{N,K})) = Opt_{}(g),

which again fits into the framework of Proposition 20.

5.2 A constant-factor algorithm for the orthogonal Procrustes problem

The generalized orthogonal Procustes problem was described in Section (1.1.3). Continuing with the notation introduced there, let A_{1}, …, A_{K} be d × n real matrices such that the i-th row of A_{k} is the vector x_{i}^{k} ∈ ^{d}. Our goal is then to efficiently approximate

P(A_{1}, …A_{K}) =^{def} max_{U_{1},...U_{K}∈O_{d}} ∥ ∑_{k=1}^{K} U_{k}A_{k}∥_{2}^{2} = max_{U_{1},...U_{K}∈O_{d}} ∑_{k,l=1}^{K} ⟨U_{k}A_{k}, U_{l}A_{l}⟩,  (68)

where we set ⟨A, B⟩ =^{def} ∑ _{i=1}^{d} ∑ _{j=1}^{n} A_{ij}B_{ij} for every two d × n real matrices A, B. We first observe that (68)is equal to

max_{U_{1},...U_{K}∈O_{d}} max_{V_{1},...V_{K}∈O_{d}} ⟨ ∑_{k=1}^{K} U_{k}A_{k}, ∑_{l=1}^{K} V_{l}A_{l}⟩.  (69)

It is clear that (69)is at least as large as (68). For the other direction, using Cauchy-Schwarz,

⟨ ∑_{k=1}^{K} U_{k}A_{k}, ∑_{l=1}^{K} V_{l}A_{l}⟩ ⩽ ∥ ∑_{k=1}^{K} U_{k}A_{k}∥_{2} · ∥ ∑_{l=1}^{K} V_{l}A_{l}∥_{2},

so either U_{1}, …, U_{K} or V_{1}, …, V_{K} achieve a value in (68)that is at least as large as (69). The desired algorithm now follows by noting that (69)falls into the framework of Proposition 20: it suffices to define f ∈ Bil_{}(K, K; (d, …, d), (d, …, d), (d, …, d), (d, …, d)) by

f((U_{1}, …, U_{K}), (V_{1}, …, V_{K})) = ⟨ ∑_{k=1}^{K} U_{k}A_{k}, ∑_{l=1}^{K} V_{l}A_{l}⟩.

Finally, from an assignment to (69) we can efficiently extract an assignment to (68) achieving at least as high a value by choosing the one among the (U_{k}) or the (V_{l}) that leads to a higher value.

Comparison with previous work. To compare the approximation guarantee that we obtained with the literature, we first note that P(A_{1}, …, A_{K}) is attained at U_{1}, …, U_{K} ∈ O_{d} if and only if U_{1}, …, U_{K} are maximizers of the following quantity over all V_{1}, …, V_{K} ∈ O_{d}.

∑_{\begin{matrix}k,l∈\{1,...,K\} \\ k≠l \end{matrix}}⟨V_{k}A_{k}, V_{l}A_{l}⟩  (70)

Indeed, the diagonal term ⟨V_{k}A_{k}, V_{k}A_{k}⟩ = ∥V_{k}A_{k}∥_{2}^{2} equals ∥A_{k}∥_{2}^{2}, since V_{k} is orthogonal. Consequently, the quantity appearing in (70)differs from the quantity defining P(A_{1}, …, A_{K}) by an additive term that does not depend on V_{1}, …, V_{K}. In the same vein, as already mentioned in Section (1.1.3), P(A_{1}, …, A_{K}) is attained at U_{1}, …, U_{K} ∈ O_{d} if and only if U_{1}, …, U_{K} are minimizers of the following quantity over all V_{1}, …, V_{K} ∈ O_{d}.

∑_{k,l=1}^{K} ∥V_{k}A_{k} − V_{l}A_{l}∥_{2}^{2}.  (71)

While the optimization problems appearing in (68), (70)and (71)have the same exact solutions, this is no longer the case when it comes to approximation algorithms. To the best of our knowledge the polynomial time approximability of the minimization of the quantity appearing in (71) was not investigated in the literature. Nemirovski [Nem07] and So [So11] studied the polynomial time approximability of the maximization of the quantity appearing in (70): the best known algorithm for this problem [So11] has approximation factor O(log(n + d + K)). This immediately translates to the same approximation factor for computing P(A_{1}, …, A_{K}), which was the previously best known algorithm for this problem. Our constant-factor approximation algorithm for P(A_{1}, …, A_{K}) yields an approximation for the maximization of the quantity appearing in (70)that has a better approximation factor than that of [So11] unless the additive difference ∑ _{k=1}^{K} ∥A_{k}∥_{2}^{2} is too large. Precisely, our algorithm becomes applicable in this context as long as this term is at most a factor (1 − 1/C) smaller than P(A_{1}, …, A_{K}). This will be the case for typical applications in which one may think of each A_{k} as obtained from a common A by applying a small perturbation followed by an arbitrary rotation: in that case it is reasonable to expect the optimal solution to satisfy ⟨U_{k}A_{k}, U_{l}A_{l}⟩ ≈ ∥A∥_{2} for every l, k ∈ {1, …, K}; see, e.g., [Nem07, Sec. 4.3].

5.3 An algorithmic noncommutative dense regularity lemma

Our goal here is to prove Theorem 3, but before doing so we note that it leads to a PTAS for computing Opt_{}(M) whenever Opt_{}(M) ⩾ κn∥M∥_{2} for some constant κ > 0 (we shall use below the notation introduced in the statement of Theorem 3).

The idea for this is exactly as in Section 3 of [FK99]. The main point is that given such an M and ε ∈ (0, 1) the decomposition in Theorem 3 only involves T = O(1/(κε)^{2}) terms, which can be computed in polynomial time. Given such a decomposition, we will exhaustively search over a suitably discretized set of values a_{t}, b_{t} for Tr(A_{t}X) and Tr(B_{t}Y) respectively. For each such choice of values, verifying whether it is achievable using an X and Y of operator norm at most 1 can be cast as a semidefinite program. The final approximation to Opt_{}(M) is given by the maximum value of | ∑ _{t=1}^{T} α_{t}a_{t}b_{t}|, among those sequences (a_{t}), (b_{t}) that were determined to be feasible.

In slightly more detail, first note that for any X, Y of operator norm at most 1 the values of Tr(A_{t}X) and Tr(B_{t}Y) lie in the complex disc with radius n. Given our assumption on Opt_{}(M), the bound on α_{t} stated in Theorem 3 implies |α_{t}| = O(Opt_{}(M)/(κn^{2})). Hence an approximation of each Tr(A_{t}X) and Tr(B_{t}Y) up to additive error εκn/T will translate to an additive approximation error to M(X, Y) of O(εOpt_{}(M)). As a result, to obtain a multiplicative (1 ± ε) approximation to Opt_{}(M) it will suffice to exhaustively enumerate among (O((n · T/(εκn))^{2}))^{2T} possible values for the sequences (a_{t}), (b_{t}).

Finally, to decide whether a given sequence of values can be achieved, it suffices to decide two independent feasibility problems of the following form: given n × n complex matrices (A_{t})_{t=1}^{T} of norm at most 1 and (a_{t})_{t=1}^{T} ∈ ^{T}, does there exist X ∈ M_{n}( ) of norm at most 1 such that

max_{t∈\{1,...,T\}} max\{|Re(Tr(A_{t}X) − a_{t})|, |Im(Tr(A_{t}X) − a_{t})|\} ⩽ \frac{εκn}{T} ?

This problem can be cast as a semidefinite program, and feasibility can be decided in time that is polynomial in n and T.

Proof of Theorem 3.The argument is iterative. Assume that {A_{t}, B_{t}}_{t=1}^{τ−1} ⊆ U_{n} have already been

constructed. Write M_{1} =^{def} M and

M_{τ} =^{def} M − ∑_{t=1}^{τ−1} α_{t}(A_{t} ⊗ B_{t}).

If Opt_{}(M_{τ}) ⩽ εOpt_{}(M) then we may stop the construction. Otherwise, by Theorem 1 and multiplying by an appropriate complex phase if necessary, we can find A_{τ}, B_{τ} ∈ U_{n} such that

M_{τ}(A_{τ}, B_{τ}) ⩾ ( \frac{1}{2} − \frac{ε}{2}) Opt_{}(M_{τ}),  (72)

with the left-hand side of (72)real. Set

α_{τ} =^{def} \frac{M_{τ}(A_{τ}, B_{τ})}{∥A_{τ}∥_{2}^{2} · ∥B_{τ}∥_{2}^{2}},

and define M_{τ+1} =^{def} M_{τ} − α_{τ}(A_{τ} ⊗ B_{τ}). By expanding the square we have

∥M_{τ+1} ∥_{2}^{2} = ∥M_{τ} ∥_{2}^{2} − \frac{M_{τ}(A_{τ}, B_{τ})^{2}}{∥A_{τ}∥_{2}^{2}∥B_{τ}∥_{2}^{2}}

⩽ ∥M_{τ} ∥_{2}^{2} − \frac{(1 − ε)^{2}}{4n^{2}} Opt_{}(M_{τ})^{2}

⩽ ∥M_{τ} ∥_{2}^{2} − \frac{ε^{2}(1 − ε)^{2}}{4n^{2}} Opt_{}(M)^{2}.  (73)

It follows from (73) that as long as this process continues, ∥M_{τ}∥_{2}^{2} decreases by an additive term of at least ε^{2}(1 − ε)^{2}Opt_{}(M)^{2}/(4n^{2}) at each step. This process must therefore terminate after at most T ⩽ 4n^{2}∥M∥_{2}^{2}/(ε(1 − ε)Opt_{}(M))^{2} steps.

The “moreover” part of Theorem 3 follows immediately by using the part of Theorem 1 pertaining to Opt_{}(M) (note that the specific approximation factor does not matter here).

Acknowledgements. We thank Daniel Dadush and Raghu Meka for useful discussions.

References

[AMMN06] N. Alon, K. Makarychev, Y. Makarychev, and A. Naor. Quadratic forms on graphs. Invent. Math., 163(3):499–522, 2006.

[AN04] N. Alon and A. Naor. Approximating the cut-norm via Grothendieck’s inequality. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pages 72–80 (electronic). ACM, New York, 2004. doi:10.1145/1007352.1007371.

[BMMN11] M. Braverman, K. Makarychev, Y. Makarychev, and A. Naor. The Grothendieck constant is strictly smaller than Krivine’s bound. In Proc. 52nd FOCS, pages 453–462. 2011.

[Bou82] P. Bourgeois. Extension de la méthode Procuste à la comparaison de nuages de points situés dans des espaces de dimensions différentes. RAIRO Rech. Opér., 16(1):45–63, 1982.

[CC71] E. R. Caianiello and R. M. Capocelli. On form and language: the Procrustes algorithm for feature extraction. Kybernetik (Berlin), 8(6):223–233, 1971.

[CHTW04] R. Cleve, P. Høyer, B. Toner, and J. Watrous. Consequences and limits of nonlocal strategies. In Proc. 19th IEEE Conf. on Computational Complexity (CCC’04), pages 236– 249. 2004.

[Dev86] L. Devroye. Nonuniform random variate generation. Springer-Verlag, New York, 1986.

[DJT95] J. Diestel, H. Jarchow, and A. Tonge. Absolutely summing operators, volume 43 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1995. ISBN 0-521-43168-9. doi:10.1017/CBO9780511526138.

[DM98] I. L. Dryden and K. V. Mardia. Statistical shape analysis. Wiley, 1998.

[DZHZ06] C. Ding, D. Zhou, X. He, and H. Zha. R1-PCA: rotational invariant L1-norm principal component analysis for robust subspace factorization. In Proceedings of the 23rd international conference on Machine learning, ICML ’06, pages 281–288. ACM, New York, USA, 2006.

[FK99] A. Frieze and R. Kannan. Quick approximation to matrices and applications. Combinatorica, 19:175–220, 1999.

[GD04] J. Gower and G. Dijksterhuis. Procrustes problems, volume 30 of Oxford Statistical Science Series. Oxford University Press, 2004.

[GLS93] M. Grötschel, L. Lovász, and A. Schrijver. Geometric algorithms and combinatorial optimization, volume 2 of Algorithms and Combinatorics. Springer-Verlag, Berlin, second edition, 1993.

[Gow75] J. Gower. Generalized Procrustes analysis. Psychometrika, 40:33–51, 1975.

[Gro53] A. Grothendieck. Résumé de la théorie métrique des produits tensoriels topologiques. Bol. Soc. Mat. São Paulo, 8:1–79, 1953.

[GW95] M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42(6):1115–1145, November 1995.

[Haa85] U. Haagerup. The Grothendieck inequality for bilinear forms on C^{∗}-algebras. Adv. in Math., 56(2):93 – 116, 1985.

[Haa87] U. Haagerup. A new upper bound for the complex Grothendieck constant. Israel J. Math., 60:199–224, 1987.

[HI95] U. Haagerup and T. Itoh. Grothendieck type norms for bilinear forms on C^{∗}-algebras. J. Operator Theory, 34(2):263–283, 1995.

[HM08] U. Haagerup and M. Musat. The Effros-Ruan conjecture for bilinear forms on C^{∗}- algebras. Invent. Math., 174:139–163, 2008.

[Jam85] G. Jameson. The interpolation proof of Grothendieck’s inequality. In Proceedings of the Edinburgh Mathematical Society, volume 28, pages 217–223. 1985.

[JKB95] N. L. Johnson, S. Kotz, and N. Balakrishnan. Continuous Univariate Distributions, volume 2. Wiley, 1995.

[JL01] W. B. Johnson and J. Lindenstrauss. Basic concepts in the geometry of Banach spaces. In Handbook of the geometry of Banach spaces, Vol. I, pages 1–84. North-Holland, Amsterdam, 2001. doi:10.1016/S1874-5849(01)80003-6.

[Kai83] S. Kaijser. A simple-minded proof of the Pisier-Grothendieck inequality. In R. Blei and S. Sidney, editors, Banach Spaces, Harmonic Analysis, and Probability Theory, volume 995 of Lecture Notes in Mathematics, pages 33–55. Springer Berlin / Heidelberg, 1983.

[KN12] S. Khot and A. Naor. Grothendieck-type inequalities in combinatorial optimization. Commun. Pure Appl. Math., 65(7):992–1035, 2012.

[Kri74] J. L. Krivine. Théorèmes de factorisation dans les espaces réticulés. In Séminaire Maurey-Schwartz 1973–1974: Espaces L^{p}, applications radonifiantes et géométrie des espaces de Banach, Exp. Nos. 22 et 23, page 22. Centre de Math., École Polytech., Paris, 1974.

[Kri79] J. L. Krivine. Constantes de Grothendieck et fonctions de type positif sur les sphères. Adv. in Math., 31:16–30, 1979.

[Kwa08] N. Kwak. Principal component analysis based on L1-norm maximization. IEEE Trans. Pattern Anal. Mach. Intell., 30(9):1672–1680, September 2008.

[LP68] J. Lindenstrauss and A. Pe�czyński. Absolutely summing operators in L_{p}-spaces and their applications. Studia Math., 29:275–326, 1968.

[LS07] L. Lovász and B. Szegedy. Szemerédi’s lemma for the analyst. Geom. Funct. Anal., 17(1):252–270, 2007.

[MP07] E. Morand and J. Pagès. Analyse factorielle multiple procustéenne. J. Soc. Fr. Stat. & Rev. Stat. Appl., 148(2):65–97, 2007.

[MT12] M. McCoy and J. A. Tropp. Two proposals for robust PCA using semidefinite programming. Electron. J. Statist., 5:1123–1160, 1012.

[Nem07] A. Nemirovski. Sums of random symmetric matrices and quadratic optimization under orthogonality constraints. Math. Program., 109(2):283–317, January 2007.

[Pis78] G. Pisier. Grothendieck’s theorem for noncommutative C^{∗}-algebras, with an appendix on Grothendieck’s constants. J. Funct. Anal., 29(3):397–415, 1978.

[Pis12] G. Pisier. Grothendieck’s theorem, past and present. Bull. Amer. Math. Soc., 49(2):237– 323, 2012. Also available at arXiv:1101.4195.

[PS02] G. Pisier and D. Shlyakhtenko. Grothendieck’s theorem for operator spaces. Invent. Math., 150:185–217, 2002.

[Ree91] J. A. Reeds. A new lower bound on the real Grothendieck constant, 1991. Unpub-

lished manuscript, available at http://www.dtc.umn.edu/reedsj/bound2.dvi.

[RV12a] O. Regev and T. Vidick. Elementary proofs of Grothendieck theorems for completely bounded norms. Journal of Operator Theory, 2012. To appear.

[RV12b] O. Regev and T. Vidick. Quantum XOR games, 2012. Submitted. Available at arXiv:1207.4939.

[SB88] A. Shapiro and J. D. Botha. Dual algorithms for orthogonal Procrustes rotations. SIAM J. Matrix Anal. Appl., 9(3):378–383, 1988.

[SG02]  M. B. Stegmann and D. D. Gomez.  A brief intro-
duction to statistical shape analysis,  2002.  Available at

http://graphics.stanford.edu/courses/cs164-09-spring/Handouts/paper_shape_spaces_imm403.pdf.

[So11] A. So. Moment inequalities for sums of random matrices and their applications in optimization. Math. Program., 130:125–151, 2011.

[TB77] J. M. F. Ten Berge. Orthogonal Procrustes rotation for two or more matrices. Psychometrika, 42(2):267–276, 1977.

[Tsi87] B. S. Tsirelson. Quantum analogues of the Bell inequalities. The case of two spatially separated domains. J. Soviet Math., 36:557–570, 1987.