Dainis Zeps
email: dainize@mii.lu.lv

Combinatorial map as multiplication of combinatorial knots

published or not. The documents may come

Introduction

We proceed with building combinatorial map theory that from different points of view and formulations is considered in from [START_REF] Bonnington | Fundamentals of topological graph theory[END_REF] to [START_REF] Zeps | Combinatorial Maps. Tutorial[END_REF].

We multiply permutations from left to right. Geometrical combinatorial map is pair of permutations, vertex and face rotations, (P, Q) acting on set of elements C if P • Q -1 = ρ edge rotation or inner edge rotation π = Q -1 P is involution without fixed elements. We consider set of maps with fixed π calling them normalized maps. Mostly we use one particular choice of π equal to [START_REF] Lando | Graphs on Surphaces and Their Applications[END_REF] ... (2k -1 2k), k > 1. If so, map may be characterized with one permutation, say vertex rotation P .

In [START_REF] Zeps | Graphs as rotations[END_REF] we saw that particular choice of ρ by fixed π induces partitioning of the set C into to subsets

C
2 : C 1 → C 1 .
In [START_REF] Zeps | Graphs with rotations:partial maps[END_REF] was shown that by fixing µ map P may be expressed as multiplication γ 1 • γ 2 • π 2 , where γ 1 acts within C 1 and γ 2 acts within C 2 .

In [START_REF] Zeps | Graphs as rotations[END_REF] was shown that normalized map always may be expressed as P = µ • α, where α is called knotting and it is selfconjugate map in sense that α π = α. In [START_REF] Zeps | The use of the combinatorial map theory in graph-topological computations[END_REF] we got formulas for µ and α, i.e.,

µ = γ 2 πγ -1 1 and α = γ 1 γ π 1 .
From [START_REF] Zeps | Graphs as rotations[END_REF] we know that α's form a group K π with respect to multiplication of maps. Moreover, classes of maps with fixed ρ's, denoted as K ρ , are cosets (left and right) of K π .

Main part

We are going to regain main formulae from introduction.

Let us prove some theorems that leads us to the main result. Theorem 4. Map P can be expressed as

Theorem 1. ρ • π [or π • ρ] is equal
P π 1 = γ 1 γ 2 π = γ 2 γ 1 π with µ(P ) = γ 2 πγ -1 1 [= γ 1 ργ -1 2 ]
and π 1 as inner cut edge rotation and π 2 inner cycle edge rotation.

Proof. Let knot µ = µ(P ) be fixed. Then set of corners is partitioned into two sets C 1 and C 2 . From form of µ(= γ 2 • π • γ -1 1 ) we directly judge that γ 1 belongs to, say, C 1 and γ 2 to C 2 . Thus, γ 1 and γ 2 commute by multiplying. Let us choose vertex rotation with this fixed knot and π 1 = id, i.e., with all edges being cycle edges. Then vertex rotation is alternation of corners from C 1 and C 2 respectively, and face rotation's cycles are correspondingly of one color. Then form of

µ = γ 2 • π • γ -1 1 shows directly that P • π 1 must be equal to γ 1 • γ 2 (= γ 2 • γ 1 ). Finally, in general we get µ = C 1 : π C 2 : ρ = C 2 : γ 2 πγ -1 1 C 1 : γ 1 ργ -1 2 .
Theorem 5. Map P • π 1 can be expressed as

C 1 : β 1 C 2 : β 2
, where involutions β 1 and β 2 are equal to

β 1 = π -γ1 and β 2 = π -γ2 . Moreover, β 1 = γ 1 γ -1 2 µ and β 2 = γ 2 γ -1 1 µ. Moreover, β 1 β 2 is squared knot µ(..., β 1 ) with one color cycles reversed. See theorem 1. δ = π γ 1 . P = γ 1 γ 2 π 2 .
Proof.

P π 1 = C 1 : β 1 C 2 : β 2 = C 1 : γ 1 πγ -1 1 C 2 : γ 2 πγ -1 2 = ( C 1 : γ 1 C 2 : γ 2 ) • π = γ 1 γ 2 π.
Corollary 6. Map P π 1 is a knot for inner edge rotation β 1 and edge rotation β 2 .

Theorem 7. Let for some fixed knot the map P be equal to µα. Then α is equal to

γ 1 πγ 1 π 2 or γ 1 γ π 1 π 1 . Proof. α = µ -1 P π 1 = γ 1 πγ -1 2 γ 2 γ 1 π = γ 1 πγ 1 π = γ 1 γ π 1 . This α is knotting for P π 1 . For map P knotting is γ 1 πγ 1 π 2 or γ 1 γ π 1 π 1 . Corollary 8. α π = α. Selfconjugate α's comprise group. Proof. α π = (γ 1 γ π 1 π 1 ) π = γ π 1 γ ππ π π 1 = γ 2 γ 1 π 1 = α. Theorem 9. γ 1 γ π
1 is some knot's square. Proof. Let us denote this knot by ν. Direct observation shows that theorem is correct. Then fixed knot µ induces α and it determines fixed ν such that ν 2 = γ 1 γ π 1 . Theorem 10. Every combinatorial P can be expressed as multiplication of knots in the form

P = µ • ν 2 • π 1 .
Proof. It directly follows from previous theorems. Really,

P = µα = γ 2 πγ -1 1 γ 1 γ π 1 π 1 = γ 2 γ 1 π 2 = µ(γ 1 π) 2 π 1 = µν 2 π 1 .
It must be noted that π 1 is some knot too. We call this knot trivial knot. Let us call knot ν map's inner knot.

Corollary 11. Map is multiplication of its knot with its inner knot's square and with its trivial knot.

Theorem 12. For P π 1 µ commutes with α, i.e.,

P π 1 = µ • α = α • µ. In general, P = µα = αµ π 1 . Proof. For P π 1 , µ α = (γ 2 πγ -1 1 ) γ1πγ1π . Further, γ γ1πγ1π 2 = γ π•π 2 = γ 2
, because corners of γ 1 and γ 2 do not intersect. The same is true for the member γ -1 1 . Further, π γ 1 πγ 1 π = π α = π. Thus, we get µ α = µ.

Theorem 13. For partial map [P, µ] its inner edge rotation is α.

Proof. Direct observation.

Conclusions

There are four types of permutations that are used to build "all" in combinatorial map theory, i.e., knot-type, knot-square-type, knot-square-with-reversed-cycles-type, two-color-involutions. Comprehensive algebra of all these types should be ground for combinatorial map theory.

  Moreover, ρ with choice of particular µ partitions π into π 1 • π 2 , where we call π 1 cut edges and π 2 cycle edges, so that P • π 1 : C 1 → C 2 and P • π

1 and C 2 [in general in several ways] so that the knot µ = C 1 : π C 2 : ρ is defined. Here, knot µ as permutation has 2 k choices if k is number of cycles in it. Rightly, changing direction of some cycle of µ we get another possible value for knot µ.

  Two joined cycles of square of knot may be combined in the cycle of knot in two ways, and thus, k independent operations give 2 k results. For vertex rotation µ • π corresponding face rotation and knot are equal to µ, and knotting equal to π. γ 1 = id, γ 2 = µ • π, and π 1 = π, because all edges of this map are cut edges. Corresponding graph to this map is set of star graphs as many as cycles in µ. Direct calculation gives what is stated by theorem.

	Proof. 1) µ expressing as	C 1 : π C 2 : ρ	, and multiplying by π, we get	C 1 : π • π C 2 : ρ • π	and using theorem
	1 what was to be proved.
	2)

to some combinatorial knot µ squared and one or other color cycles induced from this knot reversed. Proof. Let us write knot µ in the form C 1 : π C 2 : ρ . Then square of µ we would get applying π • ρ for one color corners and ρ • π for other color corners. Theorem 2. By fixing the square of the knot it has 2 k knots in correspondence [in general for different maps] where k is the number of cycles in the knot. Proof. Theorem 3. [µ • π is knot's half-square] 1) µ • π contains squared knot's cycles of only one color. 2)


Andries Steenkamp
email: andries.steenkamp@cwi.nl

Matrix factorization ranks via polynomial optimization

In light of recent data science trends, new interest has fallen in alternative matrix factorizations. By this, we mean various ways of factorizing particular data matrices so that the factors have special properties and reveal insights into the original data. We are interested in the specialized ranks associated with these factorizations, but they are usually difficult to compute. In particular, we consider the nonnegative-, completely positive-, and separable ranks. We focus on a general tool for approximating factorization ranks, the moment hierarchy, a classical technique from polynomial optimization, further augmented by exploiting ideal-sparsity. Contrary to other examples of sparsity, the resulting sparse hierarchy yields equally strong, if not superior, bounds while potentially delivering a speed-up in computation.

Introduction and motivation for matrix factorization ranks

We live in a digital world. Data drives decisions as a never-ending stream of information engulfs our lives. An essential tool for navigating the flood of information is the ability to distill large bodies of information into actionable knowledge. A practical example is nonnegative (NN) factorization, applied to data represented as a matrix. A NN factorization of an entry-wise nonnegative matrix 𝑀 ∈ R 𝑚×𝑛 + is a pair of nonnegative matrices 𝐴 ∈ R 𝑚×𝑟 + and 𝐵 ∈ R 𝑟 ×𝑛 + for some integer 𝑟 ∈ N such that:

𝑀 = 𝐴𝐵. (1)
Andries Steenkamp CWI Amsterdam, e-mail: jajs@cwi.nl

The primary object of interest is the inner dimension 𝑟 of the factorization. One can always take 𝐴 = 𝑀 and 𝐵 = 𝐼, where 𝐼 is the identity matrix, hence getting 𝑟 = 𝑛. However, the interesting case is when 𝑟 < 𝑚𝑛 𝑚+𝑛 . In this case, one has managed to express the 𝑚 × 𝑛 values of 𝑀 in terms of the (𝑚 × 𝑟) + (𝑟 × 𝑛) values of 𝐴 and 𝐵, and as a result, using less storage. The smallest integer 𝑟 for which this is possible is called the nonnegative matrix factorization rank, or just the nonnegative rank for short, and is mathematically defined as follows, rank + (𝑀) := min{𝑟 ∈ N : 𝑀 = 𝐴𝐵 for some 𝐴 ∈ R 𝑚×𝑟 + and 𝐵 ∈ R 𝑟 ×𝑛 + }. [START_REF] Berman | Completely Positive Matrices[END_REF] It is not hard to see that the NN-rank is sandwiched between the classical rank and the size of the matrix, i.e., rank(𝑀) ≤ rank + (𝑀) ≤ min{𝑛, 𝑚}.

However, storage space efficiency is only part of the value of NN factorization. The true power of NN factorization comes from the fact that it is an easy-to-interpret linear dimensionality reduction technique.

To understand what we mean by this, we first re-examine the relationship between the three matrices 𝑀, 𝐴, and 𝐵 in eq. ( 1).

Observe how the 𝑗 th column of 𝑀 is given as a conic combination of the columns of 𝐴 with weights given by the 𝑗 th column of 𝐵, i.e., 𝑀 :, 𝑗 = 𝑟 ∑ 𝑖=1 𝐵 𝑖, 𝑗 𝐴 :,𝑖 .

(

Because all terms involved are nonnegative, zero entries in 𝑀 force the corresponding entries of the factors to be zero. Formally, for any 𝑘 ∈ {1, 2, .., 𝑚} and 𝑗 ∈ {1, 2, .., 𝑛}, 𝑀 𝑘, 𝑗 = 0 if and only if 𝐵 𝑖, 𝑗 𝐴 𝑘,𝑖 = 0 for all 𝑖 ∈ {1, 2, .., 𝑟 }. Having no cancellation among factors will be useful for interpreting applications of nonnegative factorization. We will explain this further in section 1.1 with examples. Furthermore, observe that the nonnegative factorization needs not be unique. In fact, for any non-singular, nonnegative matrix 𝑃 ∈ R 𝑟 ×𝑟 + with nonnegative inverse 𝑃 -1 one can produce another factorization 𝑀 = ( 𝐴𝑃 -1 ) (𝑃𝐵).

An example of such a matrix 𝑃 would be a permutation matrix.

Example of a nonnegative factorization

Consider the following example of a 4 × 4 nonnegative matrix and its nonnegative factorization from which we can deduce that rank + (𝑀) = 2, because rank(𝑀) = 2:

𝑀 =         35

Applications of nonnegative factorization

Having introduced the nonnegative rank, we now justify its importance with three applications. What we present here is but a small fraction of the whole body of literature on nonnegative factorization. The interested reader is highly encouraged to read a recent monograph of Gillis [START_REF] Gillis | Nonnegative Matrix Factorization[END_REF] for an in-depth study of the nonnegative rank with many applications and further references. Alternatively, we invite the reader to try and conceive a few applications of their own.

Image processing

When analyzing large amounts of images, it is natural to ask if the vast bulk of images are not just combinations of a few "basic images". This raises two questions.

First, how does one find or construct a set of basic images? Second, given this, hopefully small, set of basic images, how does one reproduce the original images? Lee and Seung answered both questions in [START_REF] Lee | Learning the parts of objects by non-negative matrix factorization[END_REF], where they factorized a set of images of human faces into a set of typical facial features and nonnegative weights.

Combining the weights and features, one approximately recovers the original faces.

In this setting, the matrix 𝑀 has as columns the vectorized gray-scale images of human faces, hence 𝑀 𝑖, 𝑗 is the 𝑖 th pixel of the 𝑗 th face, with a value between 0 and 1, with 0 corresponding to black and 1 to white.

Recalling the interpretation of (3), we can think of the columns of the matrix 𝐴 as (vectorized) images of human facial features, like a mouth or pair of eyes. Hence, the 𝑗 th image 𝑀 :, 𝑗 is a weighted sum of feature-images 𝐴 :,𝑖 (𝑖 ∈ [𝑟]), where the (nonnegative) weight of feature 𝐴 :,𝑖 is given by entry 𝐵 𝑖, 𝑗 of the matrix 𝐵.

In contradistinction to other techniques like principle component analysis (PCA), which possibly gives factors with negative entries, NN factorization saves us from the task of interpreting notions like "negative pixels" or "image cancellations." By "negative pixels," we mean negative factor values, i.e., 𝐵 𝑖, 𝑗 𝐴 𝑘,𝑖 < 0. This means that factor 𝐵 𝑖, 𝑗 𝐴 :,𝑖 does not just add features but also possibly erases the features added by other factors 𝐵 ℓ, 𝑗 𝐴 :,ℓ , where ℓ ≠ 𝑖. A fun by-product of these image factorizations is that one can generate new images by multiplying the matrix 𝐴 with new weights different from 𝐵. However, the resulting images are not guaranteed to look like faces for a poor choice of weights.

Topic recovery and document classification

In text analysis, the matrix 𝑀 is called the word occurrence matrix, and its entries 𝑀 𝑖, 𝑗 are the number of times the 𝑖 th word occurs in the 𝑗 th document. This way of looking at a corpus of text is often called a "bag of words model," the sequence is ignored, and only the quantity is considered. Since word count is always nonnegative, 𝑀 is nonnegative and has some NN factors 𝐴 and 𝐵. The columns of matrix 𝐴 take the meaning of "topics", and 𝐵 gives the correct weights to recover 𝑀. Since there are no cancellations, we observe in the columns of 𝐴 that certain sets of words tend to occur together, at least within the original set of documents. Moreover, we see how the documents (the columns of 𝑀) are composed from these base topics (the columns of 𝐴), with the importance of each topic given by the entries of 𝐵. One can hence use these learned topics to group or classify documents.

Linear extension complexity

This third application is different from the above two. First, we define the linear extension complexity, then we show how it relates to the nonnegative rank, and finally, we motivate its importance. The linear extension complexity of a polytope 𝑃 is the smallest integer 𝑟 for which 𝑃 can be expressed as the linear image of an affine section of R 𝑟 + . Alternatively, the linear extension complexity can be defined as the smallest number of facets a higher dimensional polytope 𝑄 can have while still having 𝑃 as a projection. In 1991 Yannakakis [START_REF] Yannakakis | Expressing combinatorial optimization problems by linear programs[END_REF] proved that the linear extension complexity of 𝑃 is equal to the nonnegative rank of the slack matrix associated with 𝑃. For a polytope 𝑃 the slack matrix is (𝑑 𝑖 -𝑐 𝑇 𝑖 𝑣) 𝑣 ∈V,𝑖 ∈I , where 𝑐 𝑖 ∈ R 𝑚 , 𝑑 𝑖 ∈ R come from the hyperplane representation of 𝑃 = {𝑥 ∈ R 𝑚 : 𝑐 𝑇 𝑖 𝑥 ≤ 𝑑 𝑖 (𝑖 ∈ I)}, and the vectors 𝑣 ∈ R 𝑚 come from the extremal point representation of 𝑃 = conv(𝑉). This link between nonnegative rank and linear extension complexity was instrumental in showing why many combinatorial problems, like the traveling salesman problem, could not be efficiently solved simply by lifting the associated problem polytope to higher dimensions in some clever way, see [START_REF] Fiorini | Exponential lower bounds for polytopes in combinatorial optimization[END_REF]. On the topic of lifting convex sets we refer the reader to the survey [START_REF] Fawzi | Lifting for simplicity: Concise descriptions of convex sets[END_REF].

Commonly used notation

We group here some notation used throughout the chapter. For any positive integer 𝑚 ∈ N we denote by [𝑚] := {1, 2, ..., 𝑚} the set consisting of the first 𝑚 positive integers. For vectors 𝑢, 𝑣 ∈ R 𝑚 we denote by 𝑢, 𝑣 := 𝑖 ∈ [𝑚] 𝑢 𝑖 𝑣 𝑖 the vector innerproduct of 𝑢 and 𝑣. Similarly, for matrices 𝐴, 𝐵 ∈ R 𝑚×𝑛 we use the same notation to denote the Frobenius inner product 𝐴, 𝐵 := 𝑖 ∈ [𝑚], 𝑗 ∈ [𝑛] 𝐴 𝑖, 𝑗 𝐵 𝑖, 𝑗 of 𝐴 and 𝐵. We say that a square matrix 𝐴 ∈ R 𝑚×𝑚 is positive semi-definite (PSD), denoted by 𝐴 0, if and only if 𝑣 𝑇 𝐴𝑣 ≥ 0 for any choice of 𝑣 ∈ R 𝑚 . The set of all PSD matrices of size 𝑟 ∈ N is denoted by S 𝑟 + := { 𝐴 ∈ R 𝑟 ×𝑟 : 𝐴 0}. Analogous to real matrices that are PSD, there are complex square matrices that are Hermitian PSD. A complex matrix 𝐴 ∈ C 𝑚×𝑚 is Hermitian PSD if and only if 𝑣 * 𝐴𝑣 ≥ 0 for all 𝑣 ∈ C 𝑚 , where 𝑣 * is the complex conjugate of 𝑣. For positive integer 𝑚, we denote by H 𝑚 the set of all 𝑚 × 𝑚 Hermitian matrices. By

Σ[𝑥] := { ∑ 𝑖 ∈ [𝑘 ] 𝜎 𝑖 : 𝑘 ∈ N, 𝜎 𝑖 = 𝑝 2 𝑖 for some polynomial 𝑝 𝑖 ∈ R[𝑥]}
we denote the set of all sums of squares of polynomials. If the variables 𝑥 = (𝑥 1 , 𝑥 2 , ..., 𝑥 𝑚 ) are clear from the context we simply write Σ.

On computing the nonnegative rank

Given the utility of computing nonnegative factorizations, it is natural to ask the following. Is it difficult to compute the nonnegative rank for a given data matrix 𝑀 ≥ 0? This was answered in the affirmative in 2009 by Vavasis [START_REF] Vavasis | On the complexity of nonnegative matrix factorization[END_REF]. Despite being NPhard to solve, good approximations are sometimes quite accessible. In section 2, we show a general technique for approximating the matrix factorization rank from below using tools from polynomial optimization. An alternative geometrically motivated approach is to look for a minimal rectangle cover for the support of 𝑀, see [START_REF] Gillis | On the geometric interpretation of the nonnegative rank[END_REF].Given a matrix 𝑀 ∈ R 𝑛×𝑚 , one seeks the smallest set of rectangles, sets of the form

𝑅 := {{𝑖, 𝑗 } : 𝑖 ∈ 𝐼 ⊂ [𝑛], 𝑗 ∈ 𝐽 ⊂ [𝑛]
}, such that for each nonzero entry 𝑀 𝑖, 𝑗 ≠ 0, {𝑖, 𝑗 } belongs to at least one of these rectangle. Finding the factorization rank does not necessarily give a factorization. The method we propose in section 2 does not generally give a factorization, except in a particular case, which we consider in section 2.3, where it is possible to recover the factors. For NN factorization, several algorithms exist that iteratively compute 𝐴 and 𝐵 given a guessed value 𝑟. However, these algorithms only give approximate factorizations, that is, 𝑀 ≈ 𝐴𝐵, with respect to some norm. A sufficiently good approximate NN factorization also implies an upper bound on the NN rank.

For practical problems, an approximation is often sufficient. For a detailed account of NN factorization, we refer the reader again to the book of Gillis [START_REF] Gillis | Nonnegative Matrix Factorization[END_REF].

Other factorization ranks

Above, we looked at NN factorization and some of its applications in data analysis and optimization theory. However, there are many more matrix factorization ranks, each having its intricacies, applications, and interpretations. We list a few more examples of factorization ranks to link them to NN factorization and later state some results on some of them.

Completely positive factorization

This factorization is very similar to nonnegative factorization apart from the modification that 𝐵 = 𝐴 𝑇 . Formally, an entry-wise nonnegative matrix 𝑀 ∈ S 𝑚 is completely positive (CP) if there exists a nonnegative matrix 𝐴 ∈ R 𝑚×𝑟 + , for some integer 𝑟 ∈ N, such that:

𝑀 = 𝐴𝐴 𝑇 . (5)
Clearly, CP-matrices are doubly nonnegative, i.e., entry-wise nonnegative and positive semi-definite (PSD). However, these are not sufficient criteria for 𝑀 to be CP, unless 𝑚 ≤ 4, see [START_REF] Berman | Completely Positive Matrices[END_REF]. Consider the following (Example 2.9 from [START_REF] Berman | Completely Positive Matrices[END_REF]) to see that this does not hold for 𝑚 ≥ 5.

Example of a doubly nonnegative matrix that is not CP [2]

𝑀 =           1 1 0 0 1 1 2 1 0 0 0 1 2 1 0 0 0 1 2 1 1 0 0 1 6           .
The nonnegativity is clear, the PSDness is checked via computing all the minors (or using a computer to check the eigenvalues). To see why the matrix is not CP, we refer to the explanation given in Berman and Shaked-Monderer's monograph [START_REF] Berman | Completely Positive Matrices[END_REF].

Just deciding if a given matrix is CP is already an NP-hard problem; see [START_REF] Dickinson | On the computational complexity of membership problems for the completely positive cone and its dual[END_REF]. Because the completely positive factors 𝐴 and 𝐴 𝑇 are the same, up to transposition, the CP factorization is often called a symmetric factorization. We will see another example shortly at the end of this section. Similar to nonnegative rank, there is a completely positive rank mathematically defined as the smallest inner dimension 𝑟 ∈ N for which a CP factorization of 𝑀 exists, i.e. rank cp (𝑀) := min{𝑟 ∈ N : 𝑀 = 𝐴𝐴 𝑇 for some

𝐴 ∈ R 𝑚×𝑟 + }. (6)
Clearly a matrix 𝑀 is CP if and only if rank cp (𝑀) < ∞. Hence computing the CP-rank can't be any easier than deciding if 𝑀 is CP. That being said, the complexity status of computing rank cp (𝑀) for a CP matrix 𝑀 is unknown to the best of our knowledge. Some upper bounds are known for the CP-rank: first, rank cp (𝑀) ≤ 𝑚, when 𝑚 ≤ 4, and second, rank cp (𝑀) ≤ 𝑚+1 2 -4 if 𝑚 ≥ 5, see [START_REF] Shaked-Monderer | On the cp-rank and minimal cp factorizations of a completely positive matrix[END_REF]. In 1994 it was conjectured by Drew, Johnson, and Loewy [START_REF] Drew | Completely positive matrices associated with M-matrices[END_REF] that rank cp (𝑀) ≤ 𝑚 2 4 , the bound being only attained for CP matrices 𝑀 that have complete bipartite support graphs. This conjecture was disproved by Bomze et al. [START_REF] Bomze | From seven to eleven: Completely positive matrices with high cp-rank[END_REF][START_REF] Bomze | New lower bounds and asymptotics for the cp-rank[END_REF] two decades later, using several specially constructed counter-examples. We show in eq. ( 7) an example, namely 𝑀 7 from [START_REF] Bomze | From seven to eleven: Completely positive matrices with high cp-rank[END_REF], of size 𝑚 = 7, with rank cp ( 𝑀 7 ) = 14 > 49 4 = 12:

𝑀 7 =               163
              . ( 7
)
On the more applied side, CP matrices occur in the theory of block designs. We omit many details here, but essentially, block designs deal with arranging distinct objects into blocks in such a way that the objects occur with certain regularity within and among the blocks. There is a direct application of block design in designing experiments where researchers wish to prevent the differences between test subjects from obfuscating the differences in outcome due to treatment, see [START_REF] Hall | Combinatorial Theory[END_REF] for block designs in depth and see [START_REF] Shaked-Monderer | Copositive and Completely Positive Matrices[END_REF] for the link between block designs and CP matrices.

From another perspective of applications, completely positive matrices are of great interest in optimization.

In 2009, Burer [START_REF] Burer | On the copositive representation of binary and continuous nonconvex quadratic programs[END_REF] showed that any nonconvex quadratic program with binary and continuous variables could be reformulated as a linear program over the cone of completely positive matrices. This effectively meant that many NP-hard problems could now be viewed as linear programs with CP-membership constraints. This reformulation does not make the problems any easier to solve as the difficulty is now pushed into characterizing complete positivity. However, it does allow us to attack a large class of problems by understanding a unifying thread.

For a thorough account of completely positive and copositive matrices, we refer the inquisitive reader to the monograph by Berman and Shaked-Monderer [START_REF] Shaked-Monderer | Copositive and Completely Positive Matrices[END_REF].

Separable rank

In the setting of quantum information theory, the state of some physical system is often characterized by a Hermitian PSD matrix 𝑀 ∈ H 𝑚 ⊗ H 𝑚 . These states are said to be separable if there exist vectors 𝑎 1 , ..., 𝑎 𝑟 , 𝑏 1 , ..., 𝑏 𝑟 ∈ C 𝑚 for which

𝑀 = 𝑟 ∑ ℓ=1 𝑎 ℓ 𝑎 * ℓ ⊗ 𝑏 ℓ 𝑏 * ℓ , (8)
where 𝑎 * denotes the complex conjugate of 𝑎, and ⊗ denotes the tensor product. We will not go into the details, but it suffices to think of separable states as fully explained by classical physics, in contradistinction, non-separable states, a.k.a. entangled states have special properties of interest in quantum physics. For rank-one states, i.e., if rank(𝑀) = 1, also called pure states, one can obtain a separable factorization by using singular value decomposition (SVD). Non-rank-one states are called mixed states, and deciding whether a mixed state 𝑀 is separable is, in general, NP-hard, see [START_REF] Gurvits | Classical deterministic complexity of Edmonds' problem and quantum entanglement[END_REF][START_REF] Gharibian | Strong NP-hardness of the quantum separability problem[END_REF].

Example of an entangled state [8]

Consider the following mixed state of size 9 × 9, hence 𝑚 = 3. We have omitted showing zeros for readability, and we draw grid lines in order to highlight the block structure.

𝑀 =                   1 1 1 2 1 1 2 1 1 1 2 1 1 1 2 1 1 2 1 1 2 1 1 1                  
.

In [START_REF] Choi | Positive linear maps. Operator Algebras and Applications[END_REF] it is shown that 𝑀 is entangled.

Analogously to other matrix ranks we considered thus far, there is also a notion of separable rank, see [START_REF] De Las Cuevas | Separability for mixed states with operator Schmidt rank two[END_REF], sometimes called optimal ensemble cardinality [START_REF] Divincenzo | Optimal decompositions of barely separable states[END_REF], which we define for a separable matrix 𝑀 as

rank sep (𝑀) = min{𝑟 ∈ N : 𝑀 = 𝑟 ∑ ℓ=1 𝑎 ℓ 𝑎 * ℓ ⊗ 𝑏 ℓ 𝑏 * ℓ for some 𝑎 ℓ and 𝑏 ℓ in C 𝑚 }. (9)
A possible interpretation of the separable rank is that it gives a sense of how complex a classical system is, with the convention being that an entangled state has infinite separable rank. To our knowledge, the complexity of computing the separable rank is still unknown. There are some crude bounds on the separable rank though rank(𝑀) ≤ rank sep (𝑀) ≤ rank(𝑀) 2 .

The left most inequality can be strict (see [START_REF] Divincenzo | Optimal decompositions of barely separable states[END_REF]) and the right most inequality follows from Caratheodory's theorem [START_REF] Uhlmann | Entropy and Optimal Decompositions of States Relative to a Maximal Commutative Subalgebra[END_REF].

In addition to the above definition, there are several other variations on this notion of separability. One variation is to look for factorizations of the form 𝑀 = 𝑟 ℓ=1 𝐴 ℓ ⊗ 𝐵 ℓ , where 𝐴 ℓ , 𝐵 ℓ ∈ H 𝑚 are Hermitian PSD matrices. From this it is easy to define the associated mixed separable rank as the smallest 𝑟 for which such a factorization is possible. When 𝑀 is diagonal its mixed separable rank equals the nonnegative rank of an associated 𝑚 × 𝑚 matrix consisting of the diagonal entries of 𝑀, see [START_REF] De Las Cuevas | Mixed states in one spatial dimension: Decompositions and correspondence with nonnegative matrices[END_REF]. This shows that mixed separable rank is hard to compute.

Nonnegative tensor factorization ranks

Tensors, also called multi-way arrays, are natural generalizations of matrices commonly encountered in applied fields such as statistics, computer vision, and data science. Strictly speaking, tensor factorization ranks falls beyond the scope of this chapter, but given the similarities, we would be remiss not to include some remarks and references on the matter.

Consider, for example, a three-way array 𝑇 ∈ R 𝑛×𝑚× 𝑝 . Then, its tensor rank is the smallest number 𝑟 ∈ N of rank-one tensors (tensors of the form 𝑎 ⊗ 𝑏 ⊗ 𝑐 for some 𝑎 ∈ R 𝑛 , 𝑏 ∈ R 𝑚 , and 𝑐 ∈ R 𝑝 ) necessary to describe 𝑇, i.e.

rank tensor (𝑇) = min{𝑟 ∈ N : 𝑇 = 𝑟 ∑ ℓ=1 𝑎 ℓ ⊗ 𝑏 ℓ ⊗ 𝑐 ℓ , 𝑎 ℓ ∈ R 𝑛 , 𝑏 ℓ ∈ R 𝑚 , 𝑐 ℓ ∈ R 𝑝 }.
Similarly, one can define the nonnegative tensor rank by requiring the factors 𝑎 ℓ , 𝑏 ℓ , and 𝑐 ℓ to be nonnegative. Moreover, one can define the symmetric tensor rank by requiring 𝑛 = 𝑚 = 𝑝 and the factors to be equal, i.e., 𝑎 ℓ = 𝑏 ℓ = 𝑐 ℓ for all ℓ ∈ [𝑟]. An interesting effect of going to tensors is that some decompositions become unique [START_REF] Sidiropoulos | On the uniqueness of multilinear decomposition of N-way arrays[END_REF]. See [START_REF] Cichocki | Nonnegative Matrix and Tensor Factorizations: Applications to Exploratory Multi-Way Data Analysis and Blind Source Separation[END_REF] for an applications-centric monograph on tensor factorization. For a mathematical survey, see Kolda and Bader [START_REF] Kolda | Tensor decompositions and applications[END_REF].

Non-commutative matrix factorization ranks

We conclude this section with two more factorizations, often called non-commutative analogs of nonnegative-and CP factorizations. First is the positive semi-definite (PSD) factorization, where given a matrix 𝑀 ∈ R 𝑚×𝑛 + we look for PSD matrices 𝐴 1 , ..., 𝐴 𝑚 , 𝐵 1 , ..., 𝐵 𝑛 ∈ S 𝑟 + , for some 𝑟 ∈ N, such that the matrix 𝑀 is described entry-wise as follows: 𝑀 𝑖, 𝑗 = 𝐴 𝑖 , 𝐵 𝑗 ∈ R for 𝑖 ∈ [𝑚] and 𝑗 ∈ [𝑛]. If the matrices 𝐴 𝑖 and 𝐵 𝑗 are diagonal for 𝑖 ∈ [𝑚] and 𝑗 ∈ [𝑛], then we recover a nonnegative factorization. Similar to nonnegative factorization, there is a substantial research interest in PSD-factorization, largely due to its many appealing geometric interpretations, including semi-definite representations of polyhedra. We refer the reader to the survey by Fawzi et al. [START_REF] Fawzi | Positive semidefinite rank[END_REF] for further study of PSD-factorizations.

Second, we have the symmetric analog of PSD-factorization, called a completely positive semi-definite (CPSD) factorization, which simply adds the requirement that 𝑛 = 𝑚 and

𝐵 𝑖 = 𝐴 𝑖 for all 𝑖 ∈ [𝑚].
The associated definition of rank accompanying these two factorizations should be clear. We stop introducing matrix factorization ranks now and shift gears towards proving bounds.

Bounding matrix factorization ranks

There are two modes of approximating factorization ranks. The first is from above, using heuristics to construct factorizations. The second is from below, via computing parameters, often combinatorial in nature, exploiting the support graph of the matrix 𝑀. The approach we follow falls in this latter category. We will explain the method applied to the CP-rank, though it should be clear what substitutions are needed to generalize it to the other factorization ranks we described in section 1.

In this section, we give the focal point of this chapter, the moment hierarchy. This is the core technique for approximating factorization ranks. In order to define the hierarchy, we start in section 2.1 with polynomial optimization problems, which we feel is more natural than jumping straight into generalized moment problems considered in section 2.2. Finally, we apply the tools built in section 2.2 to the setting of CP-rank in section 2.3.

The significant results concerning the properties of the hierarchy, like convergence, flatness, and exactness, will be mentioned and explained as we proceed. See the works [START_REF] Gribling | Lower bounds on matrix factorization ranks via noncommutative polynomial optimization[END_REF][START_REF] Gribling | Bounding the separable rank via polynomial optimization[END_REF] for a more fleshed-out exposition of the process we follow here.

A brief introduction to polynomial optimization

We will be drawing heavily from the rich field of polynomial optimization, so it is only natural that we introduce some tools and notations in this regard. This small subsection is not an overview of the field. For that, we recommend the excellent works [START_REF] Laurent | Sums of squares, moment matrices and optimization over polynomials[END_REF][START_REF] Lasserre | Moments, Positive Polynomials and Their Applications[END_REF]. We attempt to cover only the necessities needed to motivate the title and ease the reader into the more advanced machinery. Depending on the book's other chapters and the reader's background, some topics may be familiar, in which case, perusing this subsection will at least clarify the notation we use.

Consider the following optimization problem:

𝑓 min := inf 𝑥 ∈𝐾 𝑓 (𝑥), (10)
where

𝐾 := {𝑥 ∈ R 𝑚 : 𝑔 𝑖 (𝑥) ≥ 0 (𝑖 ∈ [ 𝑝]) , ℎ 𝑗 (𝑥) = 0 ( 𝑗 ∈ [𝑞])}, (11)
and 𝑓 , 𝑔 1 , ..., 𝑔 𝑝 , ℎ 1 , ..., ℎ 𝑞 ∈ R[𝑥] are polynomials in 𝑚 variables 𝑥 1 , ..., 𝑥 𝑚 . The domain of optimization, 𝐾, is a basic closed semi-algebraic set. Problem ( 10) is called a polynomial optimization problem or a POP for short. POPs are versatile tools for modeling various problems. Clearly, linear and quadratic programs are instances of POPs. Furthermore, one can encode binary variables with polynomial constraints of the form 𝑥 𝑖 (𝑥 𝑖 -1) = 0. Hence, many NP-hard problems can be reformulated as a POP, and, as such, POPs are generally hard to solve, see [START_REF] Lasserre | Moments, Positive Polynomials and Their Applications[END_REF].

The moment approach to attacking a POP of the form (10) is as follows. We optimize the integral of the objective over probability measures that have support on 𝐾, i.e., we consider the following problem val POP := inf

𝜇 ∈ℳ (𝐾 ) ∫ 𝑓 (𝑥)𝑑𝜇, s.t. ∫ 1𝑑𝜇 = 1, (12)
where ℳ(𝐾) is the set of all Borel measures supported on the set 𝐾. Problems ( 10) and ( 12) are equivalent in the sense that they have the same optimal values, i.e., 𝑓 min = val POP . To see that 𝑓 min ≥ val POP holds consider the Dirac delta measure 𝛿 𝑥 min supported at a minimizer 𝑥 min of problem [START_REF] Curto | Solution of the truncated complex moment problem for flat data[END_REF]. Then we have

val POP ≤ ∫ 𝑓 (𝑥)𝑑𝛿 𝑥 min = 𝑓 (𝑥 min ) = 𝑓 min .
For the other inequality, val POP ≥ 𝑓 min , simply observe

∫ 𝑓 (𝑥)𝑑𝜇 ≥ 𝑓 min ∫ 1𝑑𝜇 = 𝑓 min .
The last equality comes from the fact that 𝜇 is a probability measure. With the equivalence between POPs and this new problem ( 12) established, we can focus on solving the latter.

Generalized moment problems

Problem ( 12) is a special instance of what is called a generalized moment problem (GMP), which is an even more versatile type of problem than a POP. Reformulating our optimization problem over measures does not give a clear advantage, as measures are difficult to handle. However, we will soon see in [START_REF] Divincenzo | Optimal decompositions of barely separable states[END_REF] how one can truncate the problem to create a hierarchy of semi-definite programs (SDP). Consider the following general form of GMP:

val := inf 𝜇 ∈ℳ (𝐾 ) ∫ 𝑓 0 (𝑥)𝑑𝜇 : ∫ 𝑓 𝑖 𝑑𝜇 = 𝑎 𝑖 (𝑖 ∈ [𝑁]) , (13)
where 𝑓 0 , 𝑓 1 , ..., 𝑓 𝑁 are polynomials. From the discussion in section 2.1, we saw that POPs are a special class of GMPs with 𝑁 = 1 and 𝑓 1 = 𝑎 1 = 1. In section 2.3, we will show that the CP-rank can be reformulated as a GMP. Before we can start attacking the above GMP with the so-called moment method, we must first set some notation and basic definitions. Let N 𝑚 𝑡 be the set of all multi-indices 𝛼 = (𝛼

𝐿( 𝑓 ) = 𝐿 ( ∑ 𝛼 𝑐 𝛼 𝑥 𝛼 ) = ∑ 𝛼 𝑐 𝛼 𝐿(𝑥 𝛼 ) = ∑ 𝛼 𝑐 𝛼 ∫ 𝑥 𝛼 𝑑𝜇 = ∫ 𝑓 𝑑𝜇.
Denote the space of truncated linear functionals acting on the space of polynomials of degree at most 𝑡, i.e., on R[𝑥] 𝑡 , by R[𝑥] * 𝑡 . Going in the opposite direction, i.e., from a linear functional 𝐿 ∈ R[𝑥] * to a measure 𝜇, is not always possible. When there does exists a measure 𝜇 ∈ ℳ(𝐾) such that 𝐿 (𝑥 𝛼 ) = ∫ 𝑥 𝛼 𝑑𝜇 for all 𝛼 ∈ N 𝑚 , 𝐿 is said to have a representing measure. We introduce some more concepts and notation to characterize the necessary conditions for measure representable functionals.

Recall the definition of our semi-algebraic set 𝐾 in eq. ( 11):

𝐾 := {𝑥 ∈ R 𝑚 : 𝑔 𝑖 (𝑥) ≥ 0 (𝑖 ∈ [ 𝑝]) , ℎ 𝑗 (𝑥) = 0 ( 𝑗 ∈ [𝑞])}.
For 𝑡 ∈ N ∪ {∞} define the truncated quadratic module generated by g := (𝑔 0 , 𝑔 1 , 𝑔 2 , ..., 𝑔 𝑝 ), with 𝑔 0 = 1, as

M (g) 2𝑡 := 𝑝 ∑ 𝑗=0 𝜎 𝑗 𝑔 𝑗 : 𝜎 𝑗 ∈ Σ, deg(𝜎 𝑗 𝑔 𝑗 ) ≤ 2𝑡 . (14)
Here Σ denotes the set of sums of squares of polynomials. In a similar vein we define the truncated ideal generated by h := (ℎ 1 , ℎ 2 , ..., ℎ 𝑞 ) as

I (h) 2𝑡 := 𝑞 ∑ 𝑗=1 𝛾 𝑗 ℎ 𝑗 : 𝛾 𝑗 ∈ R[𝑥], deg(𝛾 𝑗 ℎ 𝑗 ) ≤ 2𝑡 . (15)
When 𝑡 = ∞ we also just drop the subscript and write: M (g) and I (h).

A crucial observation (see [START_REF] Lasserre | Moments, Positive Polynomials and Their Applications[END_REF]) is that if 𝐿 ∈ R[𝑥] * has a representing measure 𝜇 ∈ ℳ(𝐾) then 𝐿 ≥ 0 on M (g) and 𝐿 = 0 on I (h). Using this, we can define, for any 𝑡 ∈ N ∩ {∞}, the following sequence of parameters,

𝜉 𝑡 := min{𝐿( 𝑓 0 ) :𝐿 ∈ R[𝑥] * 2𝑡 , 𝐿 ( 𝑓 𝑖 ) = 𝑎 𝑖 (𝑖 ∈ [𝑁]), 𝐿 ≥ 0 on M (g) 2𝑡 , 𝐿 = 0 on I (h) 2𝑡 }. ( 16
)
We call 𝜉 1 , 𝜉 2 , ..., 𝜉 ∞ a hierarchy as we clearly have for any 𝑡 ∈ N that,

𝜉 𝑡 ≤ 𝜉 𝑡+1 ≤ 𝜉 ∞ ≤ val.

Exercise 1

Given a solution 𝐿 to the problem associated with 𝜉 𝑡+1 construct a solution to the problem associated with 𝜉 𝑡 .

Under mild assumptions, the bounds 𝜉 𝑡 converge asymptotically to the optimum value val as 𝑡 goes to infinity. We state the well-known and widely used result here and refer to [START_REF] Lasserre | Moments, Positive Polynomials and Their Applications[END_REF][START_REF] De Klerk | A survey of semidefinite programming approaches to the generalized problem of moments and their error analysis[END_REF] for a full exposition.

Theorem 1 Assume problem (13) is feasible and the following Slater-type condition holds:

there exist scalars 𝑧 0 , 𝑧 1 , . . . , 𝑧 𝑁 ∈ R such that 𝑁 ∑ 𝑖=0 𝑧 𝑖 𝑓 𝑖 (𝑥) > 0 for all 𝑥 ∈ 𝐾.

Then [START_REF] De Las Cuevas | Separability for mixed states with operator Schmidt rank two[END_REF] has an optimal solution 𝜇, which can be chosen to be finite atomic, i.e., 𝜇 = 𝑗 ∈𝐽 𝑐 𝑗 𝛿 𝑥 ( 𝑗) for some finite index set 𝐽, scalars 𝑐 𝑗 ≥ 0, and points 𝑥 ( 𝑗) ∈ 𝐾. If, in addition, M (g) is Archimedean, i.e., 𝑅 -𝑚 𝑖=1 𝑥 2 𝑖 ∈ M (g) for some scalar 𝑅 > 0, then we have lim 𝑡→∞ 𝜉 𝑡 = 𝜉 ∞ = val.

Hence, the link between the GMP (13) and the hierarchy ( 16) is established.

Earlier, we said that, for each 𝑡, problem ( 16) is an SDP. This fact may become apparent after the following characterizations. Firstly, observe that a polynomial

𝜎 ∈ R[𝑥] 2𝑡 is
𝐿 (𝑔 𝑗 [𝑥] 𝑡-𝑑 𝑔 𝑗 [𝑥] 𝑇 𝑡-𝑑 𝑔 𝑗 ) 0, (17)
for 𝑗 = 0, 1, ..., 𝑝, where 𝑑 𝑔 𝑗 := deg(𝑔 𝑗 )/2 . Secondly, the ideal constraints 𝐿 = 0 on I (h) 2𝑡 can be encoded as follows:

𝐿 (ℎ 𝑗 [𝑥] 2𝑡-deg(ℎ 𝑗 ) ) = 0, (18)
for each 𝑗 ∈ [𝑞], where the vector equality should be understood entry-wise.

Exercise 2

Prove the above two claimed equivalences.

Using eq. ( 17) and eq. ( 18) we can reformulate problem [START_REF] Divincenzo | Optimal decompositions of barely separable states[END_REF] as

𝜉 𝑡 = min{𝐿( 𝑓 ) :𝐿 ∈ R[𝑥] * 2𝑡 , 𝐿( 𝑓 𝑖 ) = 𝑎 𝑖 (𝑖 ∈ [𝑁]), 𝐿(𝑔 𝑗 [𝑥] 𝑡-𝑑 𝑔 𝑗 [𝑥] 𝑇 𝑡-𝑑 𝑔 𝑗 ) 0 ( 𝑗 = 0, 1, ..., 𝑝), 𝐿(ℎ 𝑗 [𝑥] 2𝑡-deg(ℎ 𝑗 ) ) = 0 ( 𝑗 ∈ [𝑞])}. (19)
For fixed level 𝑡, the program ( 19) is an SDP of size polynomial in 𝑚. It is known that SDPs are efficiently solvable under some technical conditions, see [START_REF] Nesterov | Interior-Point Polynomial Algorithms in Convex Programming[END_REF]. However, computing val remains inefficient because the matrices describing (

Finite convergence and recovering optimal solutions

Thus far in this section, we have seen how to get successive approximations of val. We saw in the preceding section 2.1 how GMPs relate to POPs, and soon in section 2.3 we will see how GMPs relate to the CP-rank of a matrix. However, what was not shown is whether we can also recover an optimizer 𝑥 min . On another note, we said that the hierarchy quickly exceeds hardware capacity as the level increase, so it would be helpful if we had finite convergence, i.e., 𝜉 𝑡 = 𝜉 ∞ for some 𝑡 < ∞. It turns out that there is a condition under which we solve both of these shortcomings mentioned above: finite convergence and the possibility of recovering an optimizer. Simply put, if a solution 𝐿 to the hierarchy 𝜉 𝑡 at level 𝑡 satisfies the flatness condition [START_REF] Fawzi | Lifting for simplicity: Concise descriptions of convex sets[END_REF], then the bound at that level is exact, i.e., 𝜉 𝑡 = 𝜉 ∞ , and there is a way to extract a finite atomic solution to the GMP in eq. ( 13). We formally state the classical theorem due to Curto and Fialkow [START_REF] Curto | Solution of the truncated complex moment problem for flat data[END_REF][START_REF] Curto | The truncated complex 𝐾 -moment problem[END_REF], upon which we base these claims. Note that the original formulation by Curto and Fialkow was not in the context of GMPs. We refer the reader again to [START_REF] Lasserre | Moments, Positive Polynomials and Their Applications[END_REF][START_REF] De Klerk | A survey of semidefinite programming approaches to the generalized problem of moments and their error analysis[END_REF] for a more cohesive view.

Theorem 2 (Flatness theorem) [START_REF] Curto | Solution of the truncated complex moment problem for flat data[END_REF][START_REF] Curto | The truncated complex 𝐾 -moment problem[END_REF] Consider the set 𝐾 from [START_REF] Curto | The truncated complex 𝐾 -moment problem[END_REF] and define

𝑑 𝐾 := max{1, deg(𝑔 𝑗 )/2 : 𝑗 ∈ [ 𝑝]}. Let 𝑡 ∈ N such that 2𝑡 ≥ max{deg( 𝑓 𝑖 ) : 0 ≤ 𝑖 ≤ 𝑁 } and 𝑡 ≥ 𝑑 𝐾 . Assume 𝐿 ∈ R[𝑥] *
2𝑡 is an optimal solution to the program ( 19) defining the parameter 𝜉 𝑡 and it satisfies the following flatness condition:

rank 𝐿 ( [𝑥] 𝑠 [𝑥] 𝑇 𝑠 ) = rank 𝐿( [𝑥] 𝑠-𝑑 𝐾 [𝑥] 𝑇 𝑠-𝑑 𝐾 ) for some integer 𝑠 such that 𝑑 𝐾 ≤ 𝑠 ≤ 𝑡. ( 20
)
Then equality 𝜉 𝑡 = val holds and problem ( 13) has an optimal solution 𝜇 which is finite atomic and supported on 𝑟 := rank 𝐿( [𝑥] 𝑠-𝑑 𝐾 [𝑥] 𝑇 𝑠-𝑑 𝐾 ) points in 𝐾. For the details on how to extract the atoms of the optimal measure when the flatness condition of Theorem 2 holds, we refer to [START_REF] Henrion | Detecting global optimality and extracting solutions in Glop-tiPoly[END_REF][START_REF] Laurent | Sums of squares, moment matrices and optimization over polynomials[END_REF].

In the context of factorization, we will soon see that the convergence described in Theorems 1 and 2 is not towards the rank but instead another closely related convex parameter. Furthermore, for the cases of nonnegative-and CP factorization, the atoms we recover are exactly the columns of the factorization matrices. We now proceed to apply the above techniques to the task of approximating the completely positive rank.

Constructing a hierarchy of lower bounds for CP-rank

With the moment hierarchy machinery in place, we return our attention to factorization ranks. In particular, we will construct a hierarchy of lower bounds for the CP-rank. It should be clear to the reader how to extend the contents of this section to the nonnegative and separable ranks. As for the other ranks discussed in section 1, some technicalities will be required, which we omit for brevity and simply provide references where appropriate.

Begin by recalling the definition of the CP-rank from eq. ( 6), and note that we can equivalently express it as follows:

rank cp (𝑀) = min{𝑟 ∈ N : 𝑀 = 𝑟 ∑ ℓ=1 𝑎 ℓ 𝑎 𝑇 ℓ for some 𝑎 1 , 𝑎 2 , ..., 𝑎 𝑟 ∈ R 𝑚 + }. ( 21
)
The above is sometimes called an atomic formulation because the factors 𝑎 ℓ (the columns of 𝐴 in the eq. ( 6) formulation) can be thought of as the atoms of the factorization. Assuming we know that 𝑀 is CP, we believe solving the optimization problem ( 21) is still hard, though, to the best of our knowledge, there is no proof of this claim. It is natural to ask if relaxing some constraints yields an easier problem.

In this vein, Fawzi and Parrilo [START_REF] Fawzi | Self-scaled bounds for atomic cone ranks: Applications to nonnegative rank and cp-rank[END_REF] introduced a natural "convexification" of the CP-rank:

𝜏 cp (𝑀) := inf 𝜆 : 1 𝜆 𝑀 ∈ conv{𝑥𝑥 𝑇 : 𝑥 ∈ R 𝑚 + , 𝑀 -𝑥𝑥 𝑇 0, 𝑀 ≥ 𝑥𝑥 𝑇 } . ( 22
)
A similar parameter can be defined for the NN-rank [START_REF] Fawzi | Self-scaled bounds for atomic cone ranks: Applications to nonnegative rank and cp-rank[END_REF] and the separable rank [START_REF] Gribling | Bounding the separable rank via polynomial optimization[END_REF].

Exercise 3

Prove that 𝜏 cp (𝑀) is a lower bound for rank cp (𝑀).

Because 𝜏 cp is a convex relaxation of the combinatorial parameter rank cp , it is possibly strictly worse, i.e., 𝜏 cp (𝑀) < rank cp (𝑀) for some 𝑀. Furthermore, 𝜏 cp (𝑀) does not appear any easier to compute than rank cp (𝑀), in part because we do not have an efficient characterization of the convex hull described in eq. ( 22). However, not all is lost, as 𝜏 cp (𝑀) can be reformulated as a GMP,

𝜏 cp (𝑀) = inf 𝜇 ∈M (𝐾 𝑀 ) ∫ 𝐾 𝑀 1𝑑𝜇 : ∫ 𝐾 𝑀 𝑥 𝑖 𝑥 𝑗 𝑑𝜇 = 𝑀 𝑖 𝑗 (𝑖, 𝑗 ∈ [𝑚]), , (23)
where

𝐾 𝑀 := {𝑥 ∈ R 𝑚 : √ 𝑀 𝑖𝑖 𝑥 𝑖 -𝑥 2 𝑖 ≥ 0 (𝑖 ∈ [𝑚]), 𝑀 𝑖 𝑗 -𝑥 𝑖 𝑥 𝑗 ≥ 0 (𝑖 ≠ 𝑗 ∈ [𝑚]), 𝑀 -𝑥𝑥 𝑇 0}. ( 24
)
For a small proof using Theorem 1 see Lemma 2 of [START_REF] Korda | Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks[END_REF]. The idea of using a GMP to model CP matrices was already explored in the work of Nie [START_REF] Nie | The A-truncated 𝐾 -moment problem[END_REF].

The reader may wonder why the constraints 𝑀 𝑖 𝑗 -𝑥 𝑖 𝑥 𝑗 ≥ 0 and √ 𝑀 𝑖𝑖 𝑥 𝑖 -𝑥 2 𝑖 ≥ 0 are preferred here over the equivalent and more intuitive constraints: 𝑥 𝑖 ≥ 0 and 𝑀 𝑖 𝑗 -𝑥 𝑖 𝑥 𝑗 ≥ 0 (for all 𝑖, 𝑗 ∈ [𝑚]). This is because the former gives, for finite 𝑡, a larger truncated quadratic module, which in turn gives better bounds for the finite levels of the hierarchy. Both options are, of course, equivalent in the limit as 𝑡 goes to infinity, see [START_REF] Gribling | Lower bounds on matrix factorization ranks via noncommutative polynomial optimization[END_REF].

Note that the last constraint, 𝑀 -𝑥𝑥 𝑇 0, is a polynomial matrix constraint. The idea behind this constraint is to encode that any CP factor 𝑎𝑎 𝑇 of 𝑀 is PSD less than 𝑀, i.e., 𝑀 -𝑎𝑎 𝑇 0. We could equivalently have asked that 𝑓 𝑣 (𝑥) := 𝑣 𝑇 (𝑀 -𝑥𝑥 𝑇 )𝑣 ≥ 0 for all 𝑣 ∈ R 𝑛 , or that the minors of 𝑀 -𝑥𝑥 𝑇 be nonnegative. However the matrix formulation is computationally easier to implement as we will see below. Several characterizations and supplementary references are considered for this constraint in [START_REF] Gribling | Bounding the separable rank via polynomial optimization[END_REF]. Now we simply apply the techniques of section 2.1 to construct a hierarchy of lower bounds for the above GMP [START_REF] Gharibian | Strong NP-hardness of the quantum separability problem[END_REF] to obtain the following parameter for any 𝑡 ∈ N ∪ {∞}:

𝜉 cp 𝑡 (𝑀) := min{𝐿(1) :𝐿 ∈ R[𝑥] * 2𝑡 , 𝐿(𝑥𝑥 𝑇 ) = 𝑀, 𝐿( [𝑥] 𝑡 [𝑥] 𝑇 𝑡 ) 0, 𝐿(( √ 𝑀 𝑖𝑖 𝑥 𝑖 -𝑥 2 𝑖 ) [𝑥] 𝑡-1 [𝑥] 𝑇 𝑡-1 ) 0 (𝑖 ∈ [𝑚]), 𝐿((𝑀 𝑖 𝑗 -𝑥 𝑖 𝑥 𝑗 ) [𝑥] 𝑡-1 [𝑥] 𝑇 𝑡-1 ) 0 (𝑖 ≠ 𝑗 ∈ [𝑚]), 𝐿((𝑀 -𝑥𝑥 𝑇 ) ⊗ [𝑥] 𝑡-1 [𝑥] 𝑇 𝑡-1 ) 0}. (25)
The basic idea for the construction of this hierarchy comes initially from [START_REF] Gribling | Lower bounds on matrix factorization ranks via noncommutative polynomial optimization[END_REF]. The last constraint was added later in [START_REF] Gribling | Bounding the separable rank via polynomial optimization[END_REF].

Using Theorem 1 we have the following chain of inequalities:

𝜉 cp 1 (𝑀) ≤ 𝜉 cp 2 (𝑀) ≤ ... ≤ 𝜉 cp ∞ (𝑀) = 𝜏 cp (𝑀) ≤ rank cp (𝑀).
Let us get some intuition for why this hierarchy works. Consider a CP factorization 𝑎 1 , ..., 𝑎 𝑟 ∈ R 𝑚 + of 𝑀 with 𝑟 := rank cp (𝑀). Define for each 𝑖 ∈ [𝑟] the following evaluation linear functional 𝐿 𝑎 𝑖 that maps a polynomial 𝑓 (𝑥) to its evaluation at the point 𝑎 𝑖 , i.e.,

𝐿 𝑎 𝑖 : R[𝑥] 𝑓 (𝑥) ↦ → 𝑓 (𝑎 𝑖 ) ∈ R (𝑖 ∈ [𝑟]).
Then L := 𝑖 ∈ [𝑟 ] 𝐿 𝑎 𝑖 is feasible for the problem [START_REF] Gillis | On the geometric interpretation of the nonnegative rank[END_REF]. Moreover, L(1) = 𝑟 = rank cp (𝑀).

Exercise 4

Show that L satisfies each of the constraints of problem [START_REF] Gillis | On the geometric interpretation of the nonnegative rank[END_REF].

One can think of the constraints in [START_REF] Gillis | On the geometric interpretation of the nonnegative rank[END_REF] as filters excluding solutions that are dissimilar to L. Of course, L is only feasible and not necessarily optimal. Hence 𝜉 𝑡 (𝑀) ≤ rank cp (𝑀) for every 𝑡, and in practice, the inequality is often strict. The finite atomic measure μ := 𝑟 𝑖=1 𝛿 𝑎 𝑖 supported on the atoms 𝑎 1 , ..., 𝑎 𝑟 is a representing measure of L.

With a hierarchy constructed, we can now compute some examples.

A note on computing hierarchies of SDPs

We said before that, for a fixed 𝑡 ∈ N, problem ( 25) is an SDP, and we claimed that it could be computed efficiently. We now give some tips in implementing these problems using freely available software. Theory is often a poor substitute for handson experience when it comes to implementing code. Therefore, this small subsection is simply a snapshot of the quickly changing available tools. The reader is encouraged to play around with these tools should he/she seek a deeper understanding. At the end, we list a table of results so that the reader can get a feel for the power of these approximation hierarchies.

Disclaimer, the procedure we describe here is based on the author's experience and preferences and should not be seen as the only way to compute hierarchies.

The core idea is to work inside the programming language Julia [START_REF] Bezanson | Julia: A fresh approach to numerical computing[END_REF], within which there is a package called JuMP [START_REF] Dunning | JuMP: A modeling language for mathematical optimization[END_REF] specially designed as a high-level interface between several commonly used solvers and Julia. In particular, JuMP can interface with MOSEK [START_REF] Andersen | The MOSEK interior point optimizer for linear programming: An implementation of the homogeneous algorithm[END_REF], a powerful commercial interior-point solver. Though MOSEK requires a license to run, academic licenses are available free of charge at the time of writing this. To summarize, one installs Julia, imports JuMP, uses the JuMP syntax to formulate the desired SDP as a JuMP-model, and then one passes off the JuMPmodel to MOSEK to be solved. In broad strokes, this was the procedure followed in [START_REF] Gribling | Lower bounds on matrix factorization ranks via noncommutative polynomial optimization[END_REF][START_REF] Gribling | Bounding the separable rank via polynomial optimization[END_REF][START_REF] Korda | Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks[END_REF] to compute bounds for the NN-, CP-, and separable ranks. Some code is available as a package .

See the code repository: https://github.com/JAndriesJ/ju-cp-rank

Some numerical results for CP-rank

In [START_REF] Gribling | Bounding the separable rank via polynomial optimization[END_REF], the hierarchy (25) was tested on several matrices with high CP-rank. See [START_REF] Bomze | From seven to eleven: Completely positive matrices with high cp-rank[END_REF] for the construction and definitions of these matrices. We already saw 𝑀 7 above in eq. [START_REF] Burer | On the copositive representation of binary and continuous nonconvex quadratic programs[END_REF]. We now list the bound at level 𝑡 = 3 of the hierarchy [START_REF] Gillis | On the geometric interpretation of the nonnegative rank[END_REF] for some of the other matrices in [START_REF] Bomze | From seven to eleven: Completely positive matrices with high cp-rank[END_REF]. Level 𝑡 = 3 was the highest that could be computed on the available hardware.

Exploiting sparsity

In this penultimate section, we explore sparsity, by which we mean the exploitation of zeros in the matrix 𝑀 to obtain better bounds or faster computations. In particular, we will explore a special kind of sparsity called ideal sparsity, as defined in [START_REF] Korda | Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks[END_REF]. Recall in problem ( 16) that the ideal constraint in the SDP forces the measure to vanish on certain polynomials. In this section, we show how the zero entries in a matrix lead the measure vanish on particular monomials. Using this, we can replace the original measure by multiple measures, each with a smaller support than the original one. The motivation behind this divide-and-conquer tactic is that the measures with smaller support lead to SDPs with smaller matrices and hence are easier to compute. Surprisingly, the sparse hierarchy, which we will define in [START_REF] Lasserre | Moments, Positive Polynomials and Their Applications[END_REF], is also stronger than its dense analog [START_REF] Divincenzo | Optimal decompositions of barely separable states[END_REF], in contradistinction to other sparsity techniques where one often sacrifices the quality of the bounds in favor of computational benefits. We first begin with a general introduction to ideal sparsity for the GMP setting in section 3.1. With the basic idea established, we apply ideal sparsity to CP-rank in section 3.2 and construct a sparse analog to the hierarchy [START_REF] Gillis | On the geometric interpretation of the nonnegative rank[END_REF]. Finally, we conclude this section with some results in section 3.3 demonstrating the benefits of this sparse hierarchy over its dense analog.

An abbreviated introduction to ideal sparsity

Let 𝑉 := [𝑚], 𝐸 ⊆ {{𝑖, 𝑗 } ∈ 𝑉 × 𝑉 : 𝑖 ≠ 𝑗 }, and let 𝐸 := {{𝑖, 𝑗 } ∈ 𝑉 × 𝑉 : {𝑖, 𝑗 } ∉ 𝐸, 𝑖 ≠ 𝑗 } be its complement. Suppose now that the semi-algebraic set from eq. ( 11) is defined as follows

𝐾 𝐸 := {𝑥 ∈ R 𝑚 : 𝑔 𝑖 (𝑥) ≥ 0 (𝑖 ∈ [ 𝑝]) , 𝑥 𝑖 𝑥 𝑗 = 0 ({𝑖, 𝑗 } ∈ 𝐸)}.
By definition, the ideal in eq. ( 15) becomes

I 𝐸 ,2𝑡 := ∑ {𝑖, 𝑗 } ∈𝐸 𝛾 𝑖 𝑗 𝑥 𝑖 𝑥 𝑗 : 𝛾 𝑖 𝑗 ∈ R[𝑥] 2𝑡-2 ⊆ R[𝑥] 2𝑡 . (26)
Observe that we have 𝐾 𝐸 ⊆ I 𝐸 . We plan to partition 𝐾 𝐸 in a particular way to eliminate the need for ideal constraints in the subsequent levels of the hierarchy. Consider the undirected graph 𝐺 = (𝑉, 𝐸) and denote its maximal cliques by 𝑉 1 , . . . , 𝑉 𝑠 . For each 𝑘 ∈ [𝑠] define the following subset of 𝐾 𝐸 :

𝐾 𝑘 := {𝑥 ∈ 𝐾 : supp(𝑥) ⊆ 𝑉 𝑘 } ⊆ 𝐾 ⊆ R 𝑚 . (27)
Here, supp(𝑥) = {𝑖 ∈ [𝑚] : 𝑥 𝑖 ≠ 0} denotes the support of 𝑥 ∈ R 𝑚 . Observe that the sets 𝐾 1 , . . . , 𝐾 𝑠 cover the set 𝐾 𝐸 :

𝐾 𝐸 = 𝐾 1 ∪ . . . ∪ 𝐾 𝑠 . (28)
It is an easy exercise to see that if 𝑥 ∈ 𝐾 𝐸 , then its support supp(𝑥) is a clique of the graph 𝐺, and thus it is contained in a maximal clique 𝑉 𝑘 , so that 𝑥 ∈ 𝐾 𝑘 , for some 𝑘 ∈ [𝑠]. Now define 𝐾 𝑘 ⊆ R |𝑉 𝑘 | to be the projection of 𝐾 𝑘 onto the subspace indexed by 𝑉 𝑘 :

𝐾 𝑘 := {𝑦 ∈ R |𝑉 𝑘 | : (𝑦, 0 𝑉 \𝑉 𝑘 ) ∈ 𝐾 𝑘 } ⊆ R |𝑉 𝑘 | . ( 29
)
We use the notation (𝑦, 0 𝑉 \𝑉 𝑘 ) to denote the vector of R 𝑛 obtained from 𝑦 ∈ R We may now define the following sparse analog of (13):

val sp := inf 𝜇 𝑘 ∈ℳ (𝐾 𝑘 ),𝑘 ∈ [𝑠] 𝑠 ∑ 𝑘=1 ∫ 𝑓 0 |𝑉 𝑘 𝑑𝜇 𝑘 : 𝑠 ∑ 𝑘=1 ∫ 𝑓 𝑖 |𝑉 𝑘 𝑑𝜇 𝑘 = 𝑎 𝑖 (𝑖 ∈ [𝑁]) . (30)
Proposition 1 [START_REF] Korda | Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks[END_REF] Problems (13) (using 𝐾 𝐸 ) and [START_REF] Henrion | Detecting global optimality and extracting solutions in Glop-tiPoly[END_REF] are equivalent, i.e., their optimum values are equal: val = val sp .

Based on the reformulation [START_REF] Henrion | Detecting global optimality and extracting solutions in Glop-tiPoly[END_REF] we can define the following ideal-sparse moment relaxation for problem [START_REF] De Las Cuevas | Separability for mixed states with operator Schmidt rank two[END_REF]: for any integer 𝑡 ∈ N ∪ {∞}

𝜉 isp 𝑡 := inf 𝑠 𝑘=1 𝐿 𝑘 ( 𝑓 0 |𝑉 𝑘 ) : 𝐿 𝑘 ∈ R[𝑥(𝑉 𝑘 )] * 2𝑡 (𝑘 ∈ [𝑠]), 𝑠 𝑘=1 𝐿 𝑘 ( 𝑓 𝑖 |𝑉 𝑘 ) = 𝑎 𝑖 (𝑖 ∈ [𝑁]), 𝐿 𝑘 ≥ 0 on M (g |𝑉 𝑘 ) 2𝑡 (𝑘 ∈ [𝑠]) , (31)
where g |𝑉 𝑘 := (𝑔 0 |𝑉 𝑘 , 𝑔 1|𝑉 𝑘 , 𝑔 2 |𝑉 𝑘 , ..., 𝑔 𝑝 |𝑉 𝑘 ). Note that the ideal constraint are entirely captured by the fact that none of the measures 𝜇 𝑘 support any elements of the ideal.

With two hierarchies converging to the same value, the obvious question is whether one converges faster. Surprisingly, the bounds for the sparse hierarchy [START_REF] Kolda | Tensor decompositions and applications[END_REF] are at least as good as for the dense hierarchy [START_REF] Divincenzo | Optimal decompositions of barely separable states[END_REF].

Theorem 3 [START_REF] Korda | Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks[END_REF] For any integer 𝑡 ∈ N∪ {∞}, we have 𝜉 𝑡 ≤ 𝜉 isp 𝑡 ≤ val. If, in addition M (g) is Archimedian and the condition in Theorem 1 holds, then lim 𝑡→∞ 𝜉 isp 𝑡 = val. The advantage of ( 31) over ( 16) is twofold. Firstly, the sparse bounds are at least as good as the dense bounds. Secondly, there is potential for computation speed-up since each set 𝑉 𝑘 can be much smaller than the whole set 𝑉. This holds despite there now being more variables and constraints overall. However, speed-up fails in cases where there are exponentially many (in 𝑛) maximal cliques, like when 𝐺 is a complete graph with a perfect matching deleted.

Observe that chordality need not be assumed on the cliques. However, we are required to find all maximal cliques. For an arbitrary graph, this could be difficult, but in the setting of factorization ranks, the graphs are often small, with around 5 to 15 vertices. Hence, one can compute the maximal cliques using algorithms like the one described in [START_REF] Bron | Algorithm 457: Finding all cliques of an undirected graph[END_REF].

Ideal sparsity in approximating CP-rank

Return now to the completely positive rank. The rather abstractly defined ideal constraint in section 3.1 will emerge naturally from the zeros in a matrix. Consider a CP matrix 𝑀 ∈ S 𝑚 + , assume 𝑀 𝑖𝑖 > 0 for all 𝑖 ∈ [𝑚]. If 𝑀 is a CP matrix with 𝑀 𝑖𝑖 = 0, then its 𝑖 th row and column are identically zero, and thus it can be removed without changing the CP-rank. Define the support graph 𝐺 𝑀 := (𝑉, 𝐸 𝑀 ) of 𝑀, with edge-set and non-edge-set respectively defined by:

𝐸 𝑀 := {{𝑖, 𝑗 } : 𝑀 𝑖 𝑗 ≠ 0, 𝑖, 𝑗 ∈ 𝑉, 𝑖 ≠ 𝑗 }, 𝐸 𝑀 := {{𝑖, 𝑗 } : 𝑀 𝑖 𝑗 = 0, 𝑖, 𝑗 ∈ 𝑉, 𝑖 ≠ 𝑗 }.
If 𝐺 𝑀 is not connected, then 𝑀 can be block-diagonalized using row and column permutations. It is immediately apparent that the CP-rank of a block diagonal matrix is the sum of the CP-ranks of its blocks. So we may assume that 𝐺 𝑀 is connected. Now we can modify the semi-algebraic set from eq. ( 24) to read as follows

𝐾 isp 𝑀 := {𝑥 ∈ R 𝑚 : √ 𝑀 𝑖𝑖 𝑥 𝑖 -𝑥 2 𝑖 ≥ 0 (𝑖 ∈ [𝑚]), 𝑀 𝑖 𝑗 -𝑥 𝑖 𝑥 𝑗 ≥ 0 ({𝑖, 𝑗 } ∈ 𝐸 𝑀 ), 𝑥 𝑖 𝑥 𝑗 = 0 ({𝑖, 𝑗 } ∈ 𝐸 𝑀 ), 𝑀 -𝑥𝑥 𝑇 0}. (32)
We have not introduced any new information. We have just explicitly encoded the fact that 𝑀 𝑖 𝑗 = 0 and 𝑀 𝑖 𝑗 -𝑥 𝑖 𝑥 𝑗 ≥ 0 imply 𝑥 𝑖 𝑥 𝑗 = 0 (because 𝑥 ≥ 0). In this form we can apply the results from sections 2.2, 2.3 and 3.1 to define the following new hierarchy,

𝜉 cp,isp 𝑡 (𝑀) = min 𝑠 ∑ 𝑘=1 𝐿 𝑘 (1) : 𝐿 𝑘 ∈ R[𝑥(𝑉 𝑘 )] * 2𝑡 (𝑘 ∈ [𝑠]), ∑ 𝑘 ∈ [𝑠]:𝑖, 𝑗 ∈𝑉 𝑘 𝐿 𝑘 (𝑥 𝑖 𝑥 𝑗 ) = 𝑀 𝑖 𝑗 (𝑖, 𝑗 ∈ 𝑉), 𝐿 𝑘 ( [𝑥(𝑉 𝑘 )] 𝑡 [𝑥(𝑉 𝑘 )] 𝑇 𝑡 ) 0 (𝑘 ∈ [𝑠]), 𝐿 𝑘 (( √ 𝑀 𝑖𝑖 𝑥 𝑖 -𝑥 2 𝑖 ) [𝑥(𝑉 𝑘 )] 𝑡-1 [𝑥(𝑉 𝑘 )] 𝑇 𝑡-1 ) 0 (𝑖 ∈ 𝑉 𝑘 , 𝑘 ∈ [𝑠]), 𝐿 𝑘 ((𝑀 𝑖 𝑗 -𝑥 𝑖 𝑥 𝑗 ) [𝑥(𝑉 𝑘 )] 𝑡-1 [𝑥(𝑉 𝑘 )] 𝑇 𝑡-1 ) 0 (𝑖 ≠ 𝑗 ∈ 𝑉 𝑘 , 𝑘 ∈ [𝑠]), 𝐿 𝑘 ((𝑀 -𝑥𝑥 𝑇 ) ⊗ [𝑥(𝑉 𝑘 )] 𝑡-1 [𝑥(𝑉 𝑘 )] 𝑇 𝑡-1 ) 0, (𝑘 ∈ [𝑠]). (33)
As a direct consequence of Theorem 3 we have the following relation:

𝜉 cp 𝑡 (𝑀) ≤ 𝜉 cp,isp 𝑡 (𝑀) ≤ 𝜏 cp (𝑀).
Problem (33) looks cumbersome. However, it is ultimately just problem [START_REF] Gillis | On the geometric interpretation of the nonnegative rank[END_REF] with the single functional replaced by multiple functionals, each with support tailored to exclude polynomials in the ideal I 𝐸 𝑀 .

Observe that, if, in problem [START_REF] Lasserre | Moments, Positive Polynomials and Their Applications[END_REF], we replace the matrix 𝑀 -𝑥𝑥 𝑇 by its principal submatrix indexed by 𝑉 𝑘 , then one also gets a lower bound on 𝜏 cp (𝑀), at most 𝜉 cp,isp 𝑡 (𝑀), but potentially cheaper to compute. We let 𝜉 cp,wisp 𝑡 (𝑀) denote the parameter obtained in this way, by replacing in the definition of 𝜉 cp,isp 𝑡 (𝑀) the last constraint by

𝐿 𝑘 ((𝑀 [𝑉 𝑘 ] -𝑥(𝑉 𝑘 )𝑥(𝑉 𝑘 ) 𝑇 ) ⊗ [𝑥(𝑉 𝑘 )] 𝑡-1 [𝑥(𝑉 𝑘 )] 𝑇 𝑡-1 ) 0 for 𝑘 ∈ [𝑠], (34)
so that we have 𝜉

An example of maximal cliques in the support graph of a matrix

To get some intuition into what the maximal cliques look like in the CP factorization setting, consider the following matrix and its associated support graph in fig. 1.

Advantages of the sparse hierarchy

In this subsection, we compare the dense and sparse hierarchies for approximating the CP-rank. The comparison is first made in terms of bounds and then in terms of computational speed-up.

Better bounds

We now demonstrate some advantages of the sparse hierarchy (33) above its dense counterpart in [START_REF] Gillis | On the geometric interpretation of the nonnegative rank[END_REF]. To this end consider one of the matrices from [START_REF] Bomze | New lower bounds and asymptotics for the cp-rank[END_REF], namely,

𝑀 =                       
91 0 0 0 19 24 24 24 19 24 24 24 0 42 0 0 24 6 6 6 24 6 6 6 0 0 42 0 24 6 6 6 24 6 6 6 0 0 0 42 24 6 6 6 24 6 6 6 19 24 24 24 91 0 0 0 19 24 24 24 24 6 6 6 0 42 0 0 24 6 6 6 24 6 6 6 0 0 42 0 24 6 6 6 24 6 6 6 0 0 0 42 24 6 6 6 19 24 24 24 19 24 24 24 91 0 0 0 24 6 6 6 24 6 6 6 0 42 0 0 24 6 6 6 24 6 6 6 0 0 42 0 24 6 6 6 24 6 6 6 0 0 0 42

                      
.

For this matrix we know that rank cp ( 𝑀) = 37. At the first level 𝑡 = 1, we have 𝜉 cp,isp 1

( 𝑀) = 29.66 while the dense hierarchy gives 𝜉 cp 1 ( 𝑀) = 4.85. Going to higher levels does improve the dense bound to 𝜉 cp 2 ( 𝑀) = 29.66, but the sparse bound does not seem to change.

In [START_REF] Korda | Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks[END_REF], it was shown that the separation between 𝜉 cp,isp 1

(𝑀) and 𝜉 and increasing 𝑚. Here 𝐼 𝑚 is the identity matrix, and 𝐽 𝑚 is the all-ones matrix. This gap is motivated by the sparse hierarchy incorporating certain structural information that the dense hierarchy ignores. To understand what we mean, consider first the edge clique-cover number 𝑐(𝐺) of the graph 𝐺 defined to be the minimal number of cliques needed to cover all edges of 𝐺. In Lemma 13 of [START_REF] Korda | Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks[END_REF] it is shown that 𝜉

Speed-up in computation

We said before that the sparse hierarchy involves smaller SDPs than the dense version and, as a result, can be computed faster.

To demonstrate this, the hierarchies are tested on a family of randomly generated CP-matrices ordered ascending in size and ascending in nonzero density. The nonzero density of a matrix 𝑀 is the fraction of entries above the diagonal that are nonzero, hence for the identity matrix, it would be zero, and for a dense matrix with no zeros, it would be one. This parameter is crude in that it is oblivious to the structure of the support graph. Nonetheless, it suffices to show how the speed-up is related to the sparsity in the matrix. Consider the following fig. 2 taken from [START_REF] Korda | Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks[END_REF]. , and 𝜉 cp,wisp 𝑡 described already. The exact definition is avoided here because there are several technicalities to consider that will only detract from the core message, which is that the sparse hierarchy is potentially much faster when there are many zeros in the matrix.

Summary

Finally, we summarise this chapter. In section 1, we introduced the reader to several factorization ranks and motivated their importance with applications and links to other branches of science. After building the general tools needed, we focused on approximating the CP-rank in section 2. We then improved our approximation in section 3 by including structural information about the matrix support graph before demonstrating the improvement with theoretical and numerical results. We hope to have convinced the reader of the generality and utility of polynomial optimization techniques in dealing with the difficult and pertinent problem of matrix factorization.

Fig. 1

 1 Fig. 1 Example of a matrix and its support graph. This example has non-edges: 𝐸 𝑀 := { {1, 4}, {1, 6}, {2, 6}, {3, 4}, {3, 6}, {4, 5} }, and maximal cliques: 𝑉 1 := {1, 2, 3, 5, 7}, 𝑉 2 := {2, 4, 7}, 𝑉 3 := {5, 6, 7}, 𝑉 4 := {4, 6, 7}. Hence, if 𝑀 is CP, then its factors can only be supported by one of these four cliques.

cp 1 (

 1 𝑀) could be made arbitrarily big by taking matrices 𝑀 of the form:𝑀 = (𝑚 + 1)𝐼 𝑚 𝐽 𝑚 𝐽 𝑚 (𝑚 + 1)𝐼 𝑚 ∈ S 2𝑚

cp,wisp 1 ( 5 2 ( 2 (

 1522 𝑀) ≥ 𝑐 frac (𝐺 𝑀 ),where 𝑐 frac (𝐺) is the fractional edge clique-cover number, the natural linear relaxation of 𝑐(𝐺):𝑐 frac (𝐺) := min 𝑠 ∑ 𝑘=1 𝑥 𝑘 : ∑ 𝑘:{𝑖, 𝑗 } ⊆𝑉 𝑘 𝑥 𝑘 ≥ 1 for {𝑖, 𝑗 } ∈ 𝐸 .ExerciseCompute the fractional and usual (integer) clique-cover number of 𝐺 𝑀 .Hence we have the following relations:𝑐 frac (𝐺 𝑀 ) ≤ 𝜉 𝑀) ≤ ... ≤ 𝜉 cp,isp ∞ (𝑀) = 𝜏 cp (𝑀) ≤ rank cp (𝑀) 𝑀) ≤ ... ≤ 𝜉 cp ∞ (𝑀).The weak sparse hierarchy 𝜉 cp,wisp 𝑡 and the dense hierarchies 𝜉 cp 𝑡 are incomparable, as there are examples where one outperforms the other and vice versa.

2 Fig. 2

 22 Fig. 2 Scatter plot of the computation times (in seconds) for the three hierarchies 𝜉 cp 2, † (indicated by a red square), 𝜉 cp,isp 2, † (indicated by a yellow lozenge), 𝜉 cp,wisp 2, † (indicated by a green circle) against matrix size and nonzero density for 850 random matrices. The matrices are arranged in ascending size (𝑛 = 5, 6, 7, 8, 9) and then ascending nonzero density, ranging from the minimal density needed to have a connected support graph to a fully dense matrix. For each size and nonzero density ten examples were computed to account for different support graphs.

  1 , 𝛼 2 , ..., 𝛼 𝑚 ) such that |𝛼| := 𝑚 𝑖=1 𝛼 𝑖 ≤ 𝑡. If 𝑡 = ∞ we just write N 𝑚 . For 𝑥 = (𝑥 1 , 𝑥 2 , ..., 𝑥 𝑚 ) ∈ R 𝑚 denote the truncated sequence of monomials by [𝑥] 𝑡 := 𝑥 𝛼 𝛼∈N 𝑚 𝑡 , where 𝑥 𝛼:= 𝑥 𝛼 1 1 𝑥 𝛼 2 2 • • • 𝑥 𝛼 𝑚 𝑚 .For a measure 𝜇 define its moments to be the sequence of values, obtained when integrating the monomials w.r.t. the measure, i.e, ∫ 𝑥 𝛼 𝑑𝜇 (𝛼 ∈ N 𝑚 ).Using moments, we can think of measures as linear functionals acting on the ring of polynomials. That is, for a measure 𝜇, we can define a linear map 𝐿 : R[𝑥] → R by defining what it does to monomials: 𝐿(𝑥 𝛼 ) = ∫ 𝑥 𝛼 𝑑𝜇 for every 𝛼 ∈ N 𝑛 . Hence, for any polynomial 𝑓 = 𝛼 𝑐 𝛼 𝑥 𝛼 , we have

  a sum of squares, i.e. 𝜎 ∈ Σ, if and only if there exists some matrix 𝑀 𝜎 0 such that 𝜎(𝑥) = [𝑥] 𝑇 𝑡 𝑀 𝜎 [𝑥] 𝑡 . Having this in mind, we see that 𝐿 ≥ 0 on Σ 2𝑡 is equivalent to saying 𝐿([𝑥] 𝑡 [𝑥] 𝑇 2𝑡 and 𝑗 ∈ [ 𝑝] we have 𝐿(𝑔 𝑗 𝜎) = 𝐿(𝑔 𝑗 (𝑥) [𝑥] 𝑡 [𝑥] 𝑇 𝑡 ), 𝑀 𝜎 . Thus 𝐿 ≥ 0 on M (g) 2𝑡 can be equivalently characterized by the PSD constraints:

𝑡 ) 0, because 𝐿 (𝜎) = 𝐿( [𝑥] 𝑇 𝑡 𝑀 𝜎 [𝑥] 𝑡 ) = 𝐿( [𝑥] 𝑡 [𝑥] 𝑇

𝑡 ), 𝑀 𝜎 , and using the fact that the PSD cone is self-dual. Similarly, for any 𝜎 ∈ Σ

  [START_REF] Fawzi | Positive semidefinite rank[END_REF]) could be of size max 𝑗 ∈ [ 𝑝] {

	𝑚+𝑡-𝑑 𝑔 𝑗 𝑡-𝑑 𝑔 𝑗	}, and hence soon grow beyond what most
	currently available hardware can store in memory. In our experience the level 𝑡 of
	the hierarchy is often quite small (1 to 5) for practical examples.

Table 1

 1 Bounds for completely positive rank at level 𝑡 = 3.

	𝑀 rank( 𝑀 ) 𝑚 𝑚 2 4	𝜉 3 ( 𝑀 ) rank cp ( 𝑀 ) cp
	𝑀 7	7	7 12	11.4	14
	𝑀 7	7	7 12	10.5	14
	𝑀 8	8	8 16	14.5	18
	𝑀 9	9	9 20	18.4	26

  |𝑉 𝑘 | by padding it with zeros at all entries indexed by 𝑉 \ 𝑉 𝑘 . For an 𝑛-variate function 𝑓 : R |𝑉 | → R and a subset 𝑈 ⊆ 𝑉, we let 𝑓 |𝑈 : R |𝑈 | → R denote the function in the variables 𝑥(𝑈) = {𝑥 𝑖 : 𝑖 ∈ 𝑈}, which is obtained from 𝑓 by setting to zero all the variables 𝑥 𝑖 indexed by 𝑖 ∈ 𝑉 \ 𝑈. That is, 𝑓 |𝑉 𝑘 (𝑦) = 𝑓 (𝑦, 0 𝑉 \𝑉 𝑘 ) for 𝑦 ∈ R |𝑉 𝑘 | .

Acknowledgements

We want to thank Prof. Dr. Monique Laurent for proofreading several drafts of this chapter and providing key insights when the author's knowledge was lacking. We also thank the editors for the opportunity to consolidate and share our expertise on this fascinating topic.

This work is supported by the European Union's Framework Programme for Research and Innovation Horizon 2020 under the Marie Skłodowska-Curie Actions Grant Agreement No. 813211 (POEMA).


Alain Provost

DES TEMPLIERS. NOTE SUR LE CAS DE L'EVEQUE GUICHARD DE

TROYES

C'est bien souvent sur le mode généalogique, en interrogeant une histoire inaugurée un siècle et demi plus tôt, entre la Champagne et la Terre sainte, que l'on cherche à rendre compte du procès des Templiers. On aimerait ici contribuer à déplacer la perspective, par l'étude d'une affaire contemporaine, moins célèbre, et néanmoins bien documentée : le procès de Guichard, évêque de Troyes, en Champagne, dont on tentera de définir les relations avec l'affaire du Temple 1 . Le procès de Guichard de Troyes 2 s'inscrit, comme on le sait, dans un contexte marqué par la convergence d'une série d'affaires où s'interpénètrent les catégories du politique et du religieux 3 . À première vue, le cas pourrait sembler relever de la catégorie du fait divers, tant il offre les traits presque anecdotiques d'une sorte d'intrigue de cour. On postulera pourtant qu'il importe de prendre l'affaire au sérieux : inscrite au coeur du « tournant démoniaque » des années 1280-1330 identifié par Alain Boureau 4 , elle pourrait bien constituer un accès à ce qu'étaient

les « mystères de l'État » (Ernst H. Kantorowicz) dans la France de Philippe le Bel5 .

Le procès de l'évêque Guichard est une affaire complexe, qui comporte plusieurs strates, et dont on peut suivre les développements à partir de l'été 13086 . C'est en effet par un acte daté du 9 août 1308 que le pape Clément V donne commission à l'archevêque de Sens de procéder à une enquête sur le cas de l'évêque de Troyes, en Champagne. Guichard était soupçonné de « crimes énormes et sacrilèges » (enormia et nephanda) 7 : en premier lieu d'avoir fait mourir par envoûtement quelques années plus tôt, en 1305, la reine de France Jeanne de Navarre, et aussi d'avoir tenté d'empoisonner le frère et le fils aîné du roi, Charles de Valois et Louis de Navarre -le futur Louis X. À ces crimes, qui lésaient la majesté divine et la majesté royale, venait s'ajouter l'accusation d'avoir causé naguère, également par le moyen du poison, la mort de la mère de la reine Jeanne, Blanche d'Artois. À la suite du mandement pontifical d'août 1308 se déroule une enquête lors de laquelle près de 300 témoins sont interrogés, à Paris, mais aussi à Troyes et à Provins, entre octobre 1308 et décembre 1309. Cette enquête est menée par les commissaires ecclésiastiques que le pape avait désignés, l'archevêque de Sens, c'est à dire le métropolitain de l'évêque de Troyes -Étienne Bécart dans la phase initiale -et deux autres des suffragants de celui-ci, l'évêque d'Orléans et l'évêque d'Auxerre. Cependant, cette procédure s'interrompt. L'affaire n'a sans doute jamais été jugée, et son aboutissement ressemble à un compromis. En effet, on retrouve ensuite Guichard à Avignon auprès du pape. Il n'a été ni déposé, ni dégradé ; il a été transféré sur un siège épiscopal périphérique, celui de l'Église de Bosnie8 , qu'il n'a sans doute pas occupé : c'est sans doute en Champagne, en janvier 1317, qu'est mort l'ancien évêque de Troyes9 .

Avant d'accéder aux fonctions épiscopales en 1298, Guichard avait été moine de l'abbaye de Montier-la-Celle, près de Troyes, prieur de Saint-Ayoul de Provins -un important prieuré dépendant de Montier-la-Celle -, puis abbé de cette même abbaye. Les grandes étapes de sa carrière illustrent donc une trajectoire caractérisée par sa dimension locale. Cette carrière a pu être comprise comme le produit du soutien des deux reines, Blanche d'Artois et sa fille Jeanne, héritière de la Champagne et de la Navarre, mariée à l'héritier du trône de France -Philippe IV le Bel -en août 1284. Accédant au trône en 1285, Philippe le Bel exerçait donc un contrôle sur l'administration du comté de Champagne, qui touchait à la frontière orientale du royaume, et pouvait avoir besoin de relais locaux10 . D'autre part, les accusations formulées contre Guichard nous apprennent que celui-ci, disgracié, aurait été « chassé du conseil du roi » (ex causa de consilio regio ejectus fuerat et expulsus) 11 . Sa carrière l'avait donc conduit tout près du coeur du pouvoir. À propos de cette trajectoire, on peut formuler l'hypothèse d'une ascension manquée : celle d'un clerc qui aurait pu être un précieux serviteur de la monarchie, dans le contexte du processus d'intégration de l'espace champenois à l'État capétien. Tout ceci vient en outre se combiner au jeu des rivalités et des clientèles dans le champ de luttes qu'a pu constituer l'entourage de Jeanne de Navarre, où les noms de Simon Festu, archidiacre de Vendôme puis évêque de Meaux, et de Noffo Dei, homme d'affaires florentin actif aux foires de Champagne, et pendu en 1313 pour un crime inconnu, passent pour être ceux des principaux adversaires de Guichard, si l'on s'en tient à cette vision agonistique de l'affaire.

Enfin, la carrière de Guichard s'est déroulée entre Provins et Troyes : on ne peut pas négliger la proximité des foires de Champagne, qui conservent alors une importante activité financière. Certaines dépositions insistent sur les relations que Guichard aurait entretenues avec un certain nombre de manieurs d'argent italiens qui fréquentaient les foires 12 . S'il n'est pas possible de considérer la dimension financière comme la clef de l'affaire, on ne saurait pour autant la négliger, notamment parce que c'est la fuite d'un chanoine fraudeur nommé Jean de Calais (vers 1300), dont l'évêque est tenu pour responsable, qui est donnée pour l'élément déclencheur de la disgrâce de celui-ci 13 . À l'origine de la procédure d'enquête engagée contre l'évêque de Troyes, il y aurait eu la parole d'un ermite, qui aurait assisté, dans son ermitage, aux agissements de Guichard, accomplissant des maléfices. Cet ermite, fuyant l'évêque, se serait réfugié à Sens, afin de se confesser. Puis il aurait répété la teneur de sa confession au bailli de Sens, Guillaume de Hangest. Le bailli se serait saisi de la cause, pour en référer au roi. D'où, ensuite, le mandement d'enquête de Clément V. Telle est en tout cas la séquence que la lecture des pièces du procès suggère de reconstituer. On y voit agir un petit groupe de témoins cruciaux, protagonistes, voire complices, des agissements clandestins de Guichard : l'ermite déjà mentionné, ainsi que, parmi d'autres, une « devineresse », une accoucheuse, ou bien encore le chambellan de l'évêque. Les dépositions de ces premiers témoins prennent la forme de récits structurés, précis, développés. Ce sont celles qui mettent le plus gravement en cause les agissements de Guichard, évoquant notamment les pratiques d'envoûtement et la fabrication du poison, et avec cellesci, donc, la manipulation de la surnature. Ces dépositions étaient déterminantes pour la poursuite de la procédure : elles avaient permis d'établir la diffamatio de Guichard. Après, l'enquête pouvait suivre son cours, suivant la logique procédurale 14 . C'est ainsi que d'autres charges furent énoncées, sous la forme de nouvelles listes d'articuli. Nombre d'entre elles sont assez banales. Pratique de l'usure et de la simonie, entretien d'une concubine : ces accusations, sans doute assez faciles à produire, sont conformes à celles qui sont formulées dans les affaires comparables. Au total, elles dressent le portrait d'un mauvais pasteur, scandaleux et corrompu, orgueilleux et avide, colérique et violent -en quelque sorte, terme à terme, le contre-modèle du saint évêque 15 . Plus encore, certains articuli, sous une forme stéréotypée mais efficace, tendent à disposer rétrospectivement tout au long de l'existence de Guichard les signes supposés de son caractère démoniaque, et ce en remontant jusqu'au temps de sa naissance -puisque, clef du système d'accusation, Guichard aurait été fils d'incube.

Manifestations diaboliques, envoûtement et poison, trahison autour de la famille royale, compétition dans le champ du pouvoir, enjeux financiers : cette combinaison peut inciter au soupçon. Chroniques et oeuvres littéraires livrent un écho de l'affaire. Dans l'ensemble, ces textes sont plutôt favorables à l'évêque, et pecunia, deliberaverat Johannem de Calesio, qui quamplura bona maliciose subtraxerat dicte domine Navarre regine viroque suo quondam, quod totum ad ipsam dominam reginam Navarre pertinere debebat post mortem mariti sui predicti, et quem Johannem dictus episcopus in custodia receperat ad instanciam ipsius domine regine Navarre et ad securitatem debiti supradicti. 14 Dépositions de l'ermite Regnaud de Langres, de la devineresse Margueronne de Bellevillette, de l'accoucheuse Perrote de Pouy, du chambellan de l'évêque Lorin de la Chambre et de quatre autres témoins : Paris, A.N., J 438, n° 6, fol. 1 à 7. 15 Pour l'idéal du saint évêque, tel qu'il se dessine notamment dans les procès de canonisation, voir André Vauchez, La sainteté en Occident aux derniers siècles du Moyen Âge d'après les procès de canonisation et les documents hagiographiques (Rome, 1988).

accréditent le schéma d'une erreur judiciaire, voire d'une machination échafaudée contre un innocent, revanche des envieux sur un « parvenu » qui voulait en imposer aux puissants. Les pièces du procès permettent quant à elles de faire porter la réflexion sur les conditions de production des dépositions. Parmi les dizaines de témoins interrogés, on trouve d'abord des membres du clergé du diocèse de Troyes, notamment des membres du chapitre cathédral et des moines de l'abbaye de Montier-la-Celle, dont les relations avec Guichard, abbé puis évêque, pouvaient avoir été conflictuelles16 . À la lecture des dépositions, l'hypothèse d'un truquage d'ensemble paraît cependant difficile à défendre. Ceci n'exclut pas, en revanche, que certains témoignages -et non la totalité -aient été très orientés, notamment dans la phase initiale de la procédure : il est question, dans la chronique de Jean de Saint-Victor, d'un certain « faux ermite » ; d'autres chroniqueurs parlent également de faux témoins [START_REF]Sur l'écho du procès dans les chroniques et les oeuvres littéraires : Grandes Chroniques de France[END_REF] . Ce sont les fondements mêmes de l'édifice procédural qui posent problème ; à l'ouverture de l'enquête, il y avait sans doute eu forçage. On peut donc retenir l'idée d'une instrumentalisation de l'affaire par le pouvoir royal, l'inscrivant dans des stratégies préexistantes. En témoigne aussi, par exemple, la production d'un faux destiné à compromettre l'évêque, et s'achevant sur ces mots : « Metez ceste lettre ou feu quant vous l'auroiz leue 18 ».

Ceci posé, je souhaiterais dire pourquoi l'on peut parler, au-delà d'un effet d'analogie, de réelles convergences, voire de connexions et d'interactions, entre le procès de l'évêque de Troyes et deux autres affaires de bien plus grande ampleur : le procès à la mémoire du pape Boniface VIII et, naturellement, le procès des Templiers. Il faudrait y ajouter le procès de Bernard Saisset, évêque de Pamiers, accusé par le roi de haute trahison en 1302, qui n'a pas été gracié avant 1308. De manière très partielle, je voudrais d'abord analyser la convergence de certaines caractéristiques de ces affaires, puis m'attacher à leur insertion dans le contexte général des relations entre le roi de France et le pape Clément V.

Les rapprochements entre ces différentes affaires ont été opérés depuis longtemps déjà. Michelet, en une page célèbre, l'avait affirmé : « Les premières années du XIV e siècle ne sont qu'un long procès [START_REF] Michelet | Histoire de France[END_REF] ». Mais il faut aussi noter que, bien avant Michelet, ces procès avaient été souvent copiés et rassemblés, notamment dans les collections des érudits du XVII e siècle 20 . Et sans doute faut-il aussi prendre en considération la portée du classement archivistique initial des pièces de ces procès, dans les layettes du Trésor des chartes des rois de France, classement dont les effets affectent aussi nos propres travaux, en ce qu'ils préconstituent en quelque sorte nos objets d'étude. Cette proximité entre les différentes affaires se traduit par l'intervention des mêmes hommes, par la mise en oeuvre de schémas d'accusation comparables, et par des modes d'actions identiques.

Il existe autour du pouvoir des réseaux, un espace où circulent les hommes, les idées, les techniques et les méthodes. La commission chargée d'enquêter sur le cas de l'évêque de Troyes est initialement composée de l'archevêque de Sens Étienne Bécart, de l'évêque d'Orléans Raoul Grosparmi, et de l'évêque d'Auxerre Pierre de Grès. On sait que Raoul était le cousin d'Alips de Mons, deuxième épouse d'Enguerran de Marigny, et que Pierre était le frère du maréchal de France Jean de Grès ; lui aussi était un parent de Marigny 21 . On sait également qu'Étienne Bécart était présent au Louvre lorsque Guillaume de Nogaret en mars 1303 et Guillaume de Plaisians au mois de juin de la même année procédèrent à la lecture des accusations formulées contre Boniface VIII [START_REF] Bécart | été l'un des cinq archevêques français destinataires, avec le chancelier de l'université de Paris[END_REF] . Bien que ces faits ne soient pas nécessairement déterminants, ils traduisent ce qu'étaient les structures du champ bureaucratique et les trajectoires des hommes de gouvernement. Il est plus significatif de noter que le successeur d'Étienne Bécart au siège archiépiscopal de Sens en avril 1309 est Philippe de Marigny, dont on connaît le rôle dans le procès des Templiers23 . Son nom n'est pas explicitement mentionné dans l'affaire Guichard, mais sa désignation signifiait que celle-ci se déroulait bien dans la sphère de contrôle du pouvoir royal. Surtout, on ne peut ignorer l'intervention de Guillaume de Nogaret, garde du sceau à partir de novembre 1307. L'une des pièces du procès de l'évêque de Troyes lui est adressée (un brouillon d'articles d'accusation) ; une autre est très certainement de sa main (les articles d'accusation proposés contre Guichard par le bailli de Sens) 24 . Les idées et les méthodes de Nogaret étaient donc là aussi à l'oeuvre, ce que suggère aussi l'examen des accusations formulées lors de ces affaires ; A. Rigault n'avait sans doute pas tort d'y voir la patte du garde du sceau.

Dans le cas de l'évêque Guichard, comme dans celui des Templiers ou celui du pape Boniface VIII, on peut retenir que, contrairement à ce qui a été affirmé parfois, les accusations présentent une logique et une cohérence. Elles répondent à des impératifs stratégiques et tactiques ; l'existence d'ébauches et de brouillons démontre que leur accumulation s'inscrit dans un processus dynamique, qui interdit de considérer les séries qu'elles constituent comme une accumulation informe. Tout se passe comme si l'on puisait dans un répertoire d'accusations, ordonnées notamment autour des thèmes de la fréquentation du démon et du scandale sexuel, et visant à discréditer et à diaboliser l'adversaire. On peut ici se contenter d'un exemple, lié à la question des sacrements, et particulièrement à l'eucharistie. Dans les accusations avancées contre les Templiers figure celle de l'absence de formule de consécration lors de la messeprivée, par conséquent, d'efficacité sacramentelle, puisque l'hostie non consacrée n'est pas le corps du Christ. Or parmi les accusations ébauchées mais non retenues contre l'évêque de Troyes figure une forme de profanation eucharistique : Guichard était soupçonné de conserver l'hostie dans sa bouche avant de la recracher [START_REF]jour et de nuit aux affaires pendantes, et remarque « que des procès contre magnas personas ont généralement des résultats tristes et dangereux, comme des exemples récents l'ont montré 34 » -Jean Coste voyait ici une allusion aux procès contre Bernard Saisset et Guichard de Troyes 35 . Surtout, on ne peut manquer de remarquer que le rythme du procès de l'évêque de Troyes est quasiment superposable à celui du procès de l'ancien pape[END_REF] . Outre l'indice relatif au travail d'élaboration et de remaniements du système d'accusation, il y a là un énoncé qu'il importerait de situer avec précision dans son contexte, entre les développements de la théologie sacramentelle et les accusations du même ordre alors formulées contre les juifs.

Concernant enfin les méthodes et les modes d'actions, quelques mots relatifs à la publicisation des affaires suffiront. D'après Jean de Saint-Victor, le dimanche 6 octobre 1308, une réunion de gens du peuple et de clercs se tint au jardin du roi, et, à propos de cette assemblée, le chroniqueur établit un lien avec l'emprisonnement de l'évêque de Troyes. Il est donc vraisemblable que, pour Guichard comme pour les Templiers ou Boniface, à travers ce type de réunion, un même mode d'action ait été mis en oeuvre pour diffuser l'information, révélant une certaine aptitude à travailler l'opinion26 . Reste que c'est sans doute l'examen de la chronologie qui révèle le mieux les connexions entre les différentes affaires27 .

Dans sa phase décisive -et documentée -le procès de Guichard de Troyes se déroule entre 1308 et 131428 . Le fait que le déclenchement du procès de Guichard intervienne en 1308 n'est pas insignifiant. Philippe le Bel a fait pression sur le pape Clément V dès les débuts du pontificat de celui-ci, à l'automne 1305. Mais il semble bien que cette pression se soit accentuée dans les premiers mois de l'année 1308 (avec notamment les questions adressées aux théologiens de l'Université de Paris -la réponse de ceux-ci est datée du 25 mars 1308 -et la réunion des états du royaume, à Tours, du 5 au 15 mai 1308), pour atteindre ses sommets lors de la confrontation du roi de France et du pape à Poitiers au printemps et à l'été 1308.

Philippe le Bel est arrivé à Poitiers le 26 mai 1308, avec son entourage et son armée. Il a quitté les lieux vers le 25 juillet, laissant sur place ses conseillers -Aycelin, Nogaret, Plaisians -pour poursuivre les négociations. Dans ce cadre, les termes des deux discours prononcés en consistoire le 29 mai puis le 14 juin 1308 par Guillaume de Plaisians expriment avec une grande netteté l'offensive subie par Clément V. Le pape est fermement invité à régler l'affaire du Temple (« Agissez donc, agissez. Autrement, il nous faudrait vous parler un autre langage ») 29 , à moins que le pouvoir séculier ne s'en charge (« Si donc la main droite, c'est-à-dire le bras ecclésiastique, manque à la défense de ce corps sacré [nous sommes « un seul corps avec le Christ » vient d'affirmer Plaisians], le bras gauche, c'est-à-dire la justice temporelle, ne se lèvera pas pour sa défense ? »)30 . Or les termes contenus dans les articles d'accusation proposés au même moment (entre les mois d'août et d'octobre 1308) par le bailli de Sens contre Guichard de Troyes (dont l'exemplaire que nous connaissons est très vraisemblablement, rappelons-le, de la main de Nogaret) se situent sur un registre très proche : ayant pris conseil, le roi a constaté les crimes commis par l'évêque contre la majesté divine et la majesté royale, et contre la foi catholique ; il a affirmé que l'exemple serait périlleux si ces crimes devaient rester impunis, et a déclaré que, si nécessaire, il saurait rendre la justice lui-même, pour préserver l'honneur de l'Église et écarter un tel danger et une telle abomination 31 .

Les décisions prises par Clément V au terme de l'affrontement, au mois d'août 1308, permettent elles aussi de mettre en perspective de manière significative le déclenchement de la procédure engagée contre l'évêque de Troyes. Ces décisions sont au nombre de trois. En premier lieu, par la bulle Faciens misericordiam, datée du 12 août 130832 , se trouve instituée, dans l'affaire du Temple, la double procédure, contre l'ordre et contre les personnes. Ensuite, datée du 12 août également, la bulle Regnans in coelis convoque un concile général pour le 1 er octobre 1310. Enfin, c'est au même moment que Clément V déclare accepter l'ouverture d'une enquête sur le cas de son prédécesseur Boniface, au vu des accusations formulées contre celui-ci : le pape annonce qu'il s'occupera de cette affaire après son installation à Avignon, où il arrive en mars 1309 ; après une convocation lancée le 13 septembre de cette même année, le procès à la mémoire de Boniface VIII s'ouvre le 16 mars 1310.

Le mandement d'enquête de Clément V concernant l'évêque de Troyes est daté du 9 août 1308 : il paraît difficile de considérer qu'il n'y ait là qu'une coïncidence. En bref, le mois d'août 1308 est un moment décisif pour les deux affaires, celle du Temple et celle de Boniface VIII, auxquelles vient s'ajouter, comme un élément de pression supplémentaire de la part du roi et de ses agents, le cas de Guichard de Troyes. Tout se passe comme si, dans le jeu serré qui s'était déroulé à Poitiers au printemps et à l'été 1308, Clément V avait finit par admettre une forme de compromis avec Philippe le Bel : cédant sur certains points, il s'efforçait de conserver une certaine capacité d'action, afin de préserver la jours d'avril de la même année -que les notaires procédèrent à la rédaction des pièces du procès du prélat 36 .

Risquons quelques mots de conclusion. Au-delà des analogies formelles entre ces différentes affaires, on peut donc avancer l'hypothèse d'une convergence structurelle entre elles. La somme des charges produites contre l'évêque de Troyes dessine de lui un portrait démoniaque dont le caractère plus ou moins vraisemblable importe assez peu. Surtout, dans cette affaire comme dans d'autres, les accusations délimitent des frontières, des catégories, des normes. Elles désignent des ennemis. Elles traduisent une vision du monde dans laquelle l'ordre et l'unité du corps de la chrétienté et du corps du royaume sont menacés par la subversion. Mais tout ceci ne se situe pas seulement sur un plan idéologique. Ces dispositifs et ces discours sont appuyés sur des formes procédurales. L'enquête justifie que le roi agisse, notamment lorsqu'il est question de pratiques magiques, que l'on tend à considérer comme diaboliques. La qualification du crime est une clef qui rend possible l'intervention royale. Les « grands procès » du temps de Philippe le Bel, parce qu'ils disent les menaces qui travaillent contre la majesté royale et contre la majesté divine, donnent accès aux dispositifs très concrets par lesquels s'établissent ou se renforcent l'obéissance et la souveraineté : rien non plus d'un lien exclusivement vertical et abstrait, mais, à travers la procédure du témoignage, une articulation des différents registres relevant du contrôle social et de la discipline des discours et des comportements, caractéristique d'une étape de la construction toujours provisoire de ce que l'on pourrait être tenté de nommer l'État hégémonique 37 .

36 Paris,A.N.,J 438,n° 7,fol. 8v. 37 En empruntant librement aux travaux de Mario Sbriccoli relatifs à l'émergence du « pénal hégémonique ». Voir Mario Sbriccoli, « Justice négociée, justice hégémonique : l'émergence du pénal public dans les villes italiennes des XIII e et XIV e siècles », Pratiques sociales et politiques judiciaires dans les villes de l'Occident à la fin du Moyen Âge, éd. Jacques Chiffoleau, Claude Gauvard et Andrea Zorzi (Rome, 2007), p. 389-421.

Je remercie Helen Nicholson, Paul Crawford et Jochen Burgtorf pour leur invitation aux sessions consacrées aux Templiers lors de l'International Medieval Congress de Leeds en juillet

2007, et pour leur aide dans la rédaction de cet article. Ma participation à ces sessions a été grandement facilitée par une bourse du Malta Study Center, Hill Museum & Manuscript Library, Collegeville, Minnesota, et je suis également reconnaissant à Theresa Vann pour son soutien. 2 L'étude fondamentale reste la thèse d'École des chartes d'Abel Rigault, Le procès de Guichard, évêque de Troyes, 1308-1313 (Paris, 1896). Voir aussi Alain Provost, « Déposer, c'est faire croire ? À propos du discours des témoins dans le procès de Guichard, évêque de Troyes (1308-1314) », La preuve en justice de l'Antiquité à nos jours, éd. Bruno Lemesle (Rennes, 2003), p. 95-118 ; Id., « La procédure, la norme et l'institution. Le cas de Guichard, évêque de Troyes (1308-1314) », Les procès politiques (XIV e -XVII e siècle), éd. Yves-Marie Bercé (Rome, 2007), p. 83-103. Voir aussi désormais Alain Provost, Domus Diaboli. Un évêque en procès au temps de Philippe le Bel (Paris, 2010).3 De récentes recherches ont montré qu'il fallait aussi tenir compte, au-delà des cas les plus connus, de très nombreux procès d'évêques, qui s'inscrivent depuis le début du XIII e siècle parmi les instruments de gouvernement de l'Église. Voir, par exemple, Julien Théry, « Faide nobiliaire et justice inquisitoire de la papauté à Sienne au temps des Neuf : les recollectiones d'une enquête de Benoît XII contre l'évêque Donosdeo de'Malavolti (ASV, Collectoriae 61A et 404A) », Als die Welt in die Akten kam. Prozessschriftgut im europäischen Mittelalter, éd. Susanne Lepsius et Thomas Wetzstein(Frankfurt, 2008), p. 275-345. 4 Alain Boureau, Satan hérétique. Naissance de la démonologie dans l'Occident médiéval (1280'Occident médiéval ( -1330) ) (Paris, 2004).

Sur le règne de Philippe le Bel, voir Jean Favier, Philippe le Bel(Paris, 1978) ; Joseph R. Strayer, The Reign of of Philip the Fair (Princeton, 1980), P. 300-313 (pour le procès de l'évêque de Troyes). Voir aussi désormais Élisabeth Lalou, Itinéraire de Philippe IV leBel (1285Bel ( -1314) ) (Paris, 2007).

Le dossier est essentiellement constitué d'une douzaine de pièces conservées à Paris, aux Archives Nationales, dans les layettes du Trésor des chartes des rois de France, sous la cote J 438 A et J 438 B (la numérotation est continue de J 438, n° 1, à J 438, n° 12).

Poitiers, 9 août 1308 : Paris, A.N., J 438, n° 3 bis ; Rigault, Le procès de Guichard, p. 269-270 (pièces justificatives, n° 12 : mandement d'enquête de Clément V contre Guichard).

Djakovo, aujourd'hui en Croatie. Pour le transfert, voir Reg. Clem. V, n os 10192, 10302 ; Rigault, Le procès deGuichard,

Voir Rigault, Le procès de Guichard,

Voir Olivier Guyotjeannin, « L'intégration des grandes acquisitions territoriales de la royauté capétienne (XIII e -début XIV e siècle) », Fragen der politischen Integration im mittelalterlichen Europa, éd. Werner Maleczek (Ostfildern, 2005), p. 211-239.

Paris, A.N., J 438, n° 6 (cf. n os 3 et 7), art. 2 ; Rigault, Le procès de Guichard, p. 275-278 (pièces justificatives, n° 14 : premiers articles contre l'évêque de Troyes relatifs aux accusations d'envoûtement et d'empoisonnement, séance du 8 octobre 1308).

Voir, par exemple, la déposition de Nicolaus de Castro Forti : dicens quod a tempore quo dictus nunc episcopus erat prior dicti prioratus Sancti Aygulphi, ipse qui loquitur vidit pluries et frequenter plures lombardos mercatores et feneratores in dictis nundinis conversantes cum dicto tunc priore, et extunc communiter dicebatur quod ipsi tenebant pecuniam a dicto tunc priore, quam pro dicto priore in dictis nundinis ad usuras mutuabant ;Paris, A.N., J 438, n° 6, fol. 31.

Paris, A.N., J 438, n° 8, art. 1; Rigault, Le procès de Guichard, n° 13 : articles contre l'évêque de Troyes proposés par le bailli de Sens aux commissaires apostoliques, août-octobre 1308) : Primo quod dictus episcopus causam odii contraxit contra recordationis inclite dominam Johannam, reginam Francie, domini nostri regis conjugem et consortem, tempore quo dicta domina regina vivebat, ex eo quod ipsa domina regina, exequtrix testamenti domine regine Navarre, matris sue, exegit juste ab ipso episcopo ea quibus episcopus tenebatur dicte domine regine Navarre, eo quod falso ac proditiose, corruptusque

En particulier, plusieurs membres du chapitre cathédral dont le doyen, Henri de la Noue ; trois moines de Montier-la-Celle et l'abbé Hulric ; huit prieurs de prieurés dépendants de Montier-la-

Étienne Bécart mourut en mars 1309 ; il s'était retiré le mois précédent de l'enquête relative à l'évêque de Troyes. Sur le rôle de Philippe de Marigny dans le procès des Templiers, voir Malcolm Barber, The Trial of the Templars (Cambridge, 1978 ; 2 e éd., Cambridge, 2006), chap. 6 (The End of Resistance), passim, et Alain Demurger, Les Templiers. Une chevalerie chrétienne au Moyen Âge (Paris, 2005), p. 463 et 481.

Paris, A.N., J 438, n° 9 (le brouillon) et n° 8 (les articles du bailli de Sens). Je dois cette dernière information à S. Nadiras, que je remercie très vivement, et dont on consultera, sur les méthodes de travail de Nogaret, les positions de thèse de l'École nationale des Chartes : « Guillaume de Nogaret et

Jean de Saint-Victor, RHGF, t. XXI, p. 652. Sur les assemblées et leur typologie, voir Élisabeth Lalou, « Les assemblées générales sous Philippe le Bel », Recherches sur les états généraux et les états provinciaux de la France médiévale, Actes du 110 e Congrès national des sociétés savantes, Montpellier, 1985(Paris, 1986), p. 7-29.

Voir Barber, Trial ; Demurger, Les Templiers ; et Le dossier de l'affaire des Templiers, éd. Georges Lizerand Paris, 1964 (Les classiques de l'histoire de France au Moyen Âge, 1 re éd., 1923). Voir aussi la relecture du procès proposée par Julien Théry, dans son article du Dictionnaire des ordres militaires au Moyen Age, éd. Nicole Bériou et Philippe Josserand(Paris, 2009), p. 743-751.

Le successeur de Guichard sur le siège de Troyes, Jean d'Auxois, est désigné le 14 mars 1314 ; on se souvient que Jacques de Molay est exécuté le 11 ou le 18 mars 1314.

Discours du 29 mai 1308, dans la relation de Jean Bourgogne, procureur de Jacques II d'Aragon à la cour pontificale ; M. Barber, Trial, 2 e éd., p. 107, d'après PUT, II, p. 141-147. Traduction française dans Charles-Victor Langlois, « L'affaire des Templiers », Journal des savants (1908), p. 417-435, ici p. 429.

Discours du 14 juin 1308 : Si igitur dextera, brachium scilicet ecclesiasticum, deficiat in deffensione corporis hujus sacri, nonne brachium sinistrum, scilicet justicia temporalis, ad deffensionem assurget ? Cf. Le dossier, éd.Lizerand,

Paris, A.N., J 438, n° 8, art. XXVII : Nec etiam ipse dominus rex honeste posset obmitere quominus in ecclesie defectum, quod absit, debitum suum exsolveret in predictis ad servandum honorem ecclesie et ad vitanda hec pericula ac scandala. Cf. Rigault, Le procès de Guichard, p. 274-275 (pièces justificatives, n° XIII).

Mais peut-être antidatée. En effet, de nombreuses bulles ont été datées en bloc du 12 août, date antérieure au jour où Clément V quitta définitivement Poitiers, soit le 19 août 1308. Voir Les registres de Clément V. Tables, éd. Yvonne Lanhers, Cyrille Vogel, Robert Fawtier, Guillaume Mollat(Paris, 1948(Paris, -1957)).