Likelihood Geometry of the Squared Grassmannian
Hannah Friedman

: Assessing Contextual Integrity Norms in Language Models
    
Yan Shvartzshnaider

York University


Vasisht Duddu

University of Waterloo


John Lacalamita

York University



    
=======================================================================================================================



§ ABSTRACT 
  We study projection determinantal point processes and their connection to the squared Grassmannian.
  We prove that the log-likelihood function of this statistical model has (n - 1)!/2 critical points, all of which are real and positive, thereby settling a conjecture of Devriendt, Friedman, Reinke, and Sturmfels.






§ INTRODUCTION

Determinantal point processes (DPPs) on a finite ground set are a family of statistical models whose state space is the power set of the ground set.
The key feature of DPPs is negative correlation, meaning that DPPs select for diverse subsets of the ground set, for some notion of diversity.  
DPPs elegantly model negative correlation and consequently have many applications in physics, random matrix theory, and machine learning <cit.>.

DPPs were previously studied from an algebraic statistics perspective in <cit.>.
We continue in this vein, motivated by the connection between the Grassmannian and a special class of DPPs called projection DPPs which is studied by Devriendt, Friedman, Reinke, and Sturmfels in <cit.>.
We go beyond the work in <cit.>, giving a complete picture of the likelihood geometry of projection DPPs.
Our main result is the resolution of <cit.>.


A DPP is a random variable Z on the power set 2^[n] of the finite set [n] such that
[I ⊆ Z] = (K_I), 
where K is an n × n symmetric matrix with eigenvalues in [0,1] and K_I is the principal submatrix of K whose rows and columns are indexed by I.
The matrix K is the kernel of the DPP and encodes the similarity of the elements of the ground set [n].


We study maximum likelihood estimation for determinantal point processes.
Given some data (u_I)_I ∈ 2^[n], we seek the maximizer of the log-likelihood function

    L_u(q) = ∑_I ∈ 2^[n] u_I log(q_I) -   ( ∑_I ∈ 2^[n] u_I  ) log ( ∑_I ∈ 2^[n] q_I )

where the vector q = (q_I)_I ∈ 2^[n] is a probability distribution coming from a DPP, up to scaling.
The maximizer of L_u, called the maximum likelihood estimate (MLE), is the point on the DPP model that best explains the data u. 
The number of complex critical points of (<ref>) for generic data u is the maximum likelihood degree (ML degree) of the model.

The ML degree gives an algebraic bound on the complexity of maximum likelihood estimation.


To count the critical points of (<ref>), we need a precise description of the constraints on (q_I)_I ∈ 2^[n].
In particular, we need to know the probability q_I of observing a set I, rather than [I ⊆ Z].
We discuss two scenarios in which there are nice formulae for q_I.


When the eigenvalues of K lie in (0, 1), there exists a positive definite matrix Θ such that q_I = (Θ_I)/(Θ + Id_n); see <cit.> for details.
The maximum likelihood estimation problem can then be solved by maximizing (<ref>) subject to the constraint that q satisfies the hyperdeterminantal relations; see <cit.>. 
Practitioners use the unconstrained, parameteric log-likelihood function

    L_u(Θ) = ∑_I ∈ 2^[n] u_I log((Θ_I)) -   ( ∑_I ∈ 2^[n] u_I  ) log((Θ + Id_n)).

In <cit.>, the authors express the number of critical points of the parametric log-likelihood function in terms of the ML degree of the hyperdeterminantal variety.

In this paper, we take the approach of <cit.> and restrict the eigenvalues of K to be in {0, 1}.
If K has rank d, then K is the unique orthogonal projection matrix onto a d-dimensional subspace and we denote K by P.
DPPs whose kernels are projection matrices are called projection DPPs <cit.>.
By <cit.>, a projection DPP with kernel P has state space [n]d and the probability of observing a d-subset I is q_I = (P_I).
The column space of P is a d-dimensional subspace of ^n and can be represented by its vector of Plücker coordinates (p_I)_I ∈[n]d; see <cit.>.
There is a particularly nice relationship between the principal minors of P and the Plücker coordinates of its column span. 

  The principal minors of an orthogonal projection matrix P are proportional to the corresponding squared Plücker coordinates:
  
    q_I = (P_I) = p^2_I/∑_J ∈[n]d p_J^2.



An immediate consequence of Lemma <ref> is that every probability distribution arising from a projection DPP can be written as the entry-wise square of a vector of Plücker coordinates.
This observation motivates the definition of the squared Grassmannian, denoted sGr(d,n), as the Zariski closure of the  model for projection DPPs.
The squared Grassmannian is the image of the squaring map from the Grassmannian Gr(d, n) ⊂ℙ^nd - 1 in its Plücker embedding given by (p_I)_I ∈[n]d↦ (p_I^2)_I ∈[n]d; see <cit.>.
Thus the MLE of a projection DPP is found by maximizing the implicit log-likelihood function (<ref>) over  sGr(d, n).

We focus on the case where d = 2, so our model has state space [n]2.
We determine the number of critical points of the implicit log-likelihood function:


  The ML degree of sGr(2,n) is (n - 1)!/2 for n ≥ 3.

In Section <ref>, we prove that all of these critical points are relevant from a statistical perspective.
This is reminiscent of Varchenko's Theorem <cit.>. 

  For u ∈^n2, each critical point of the log-likelihood function (<ref>) over sGr(2,n) is real, positive, and a local maximum when restricted to real points of sGr(2,n).


Another consequence of Lemma <ref>, is that the model of projection DPPs is parameterized by d × n matrices M_d,n:

    q_I = (M_d,n)_I^2/∑_J ∈[n]d (M_d,n)_J^2

where (M_d,n)_I is the maximal minor of M_d,n whose columns are indexed by I.
We then have the parametric log-likelihood function for projection DPPs:

    L_u(M_d,n) = ∑_I ∈[n]d u_I log(((M_d,n)_I)^2) - 
       ( ∑_I ∈[n]d u_I  ) log ( ∑_I ∈[n]d((M_d,n)_I)^2 ).

If we restrict to the matrices M_d,n whose first d × d square is the identity, we get a 2^n-1-degree parameterization; see <cit.>.
Therefore the number of critical points of (<ref>) is 2^n-1 times the ML degree of the squared Grassmannian.
[d = 2, n = 3]
  The implicit log-likelihood function is
  
    L_u(q) = u_12log(q_12) + u_13log(q_13) + u_23log(q_23) - (u_12 + u_13 + u_23) log(q_12 + q_13 + q_23).

  Because sGr(2,3) = ^2, the MLE is u and the ML degree is one.
  We can find the same answer parametrically: if M_2,3 = [   1   0 x_3;   0   1 y_3 ], then 
  
    L_u(M_2,3) = u_12log(1) + u_13log(y_3^2) + u_23log(x_3^2) - (u_12 + u_13 + u_23) log(1 + x_3^2 + y_3^2)

  whose partial derivatives are
  
    ∂ L_u/∂ x_3 = 2u_23/x_3 - 2(u_12 + u_13 + u_23)x_3/1 + x_3^2 + y_3^2 = 0,       ∂ L_u/∂ y_3 = 2u_13/y_3 - 2(u_12 + u_13 + u_23)y_3/1 + x_3^2 + y_3^2 = 0.

  We can solve these equations by hand to find x_3 = ±√(u_23/u_12) and y_3 = ±√(u_13/u_12) for a total of four solutions.
  Our parameterization sends the parametric solution to the implicit one:
  
    [                 1                 0  ±√(u_23)/√(u_12);                 0                 1 ±√(u_13)/√(u_12). ]↦ (1: u_13/u_12 : u_23/u_12).



Likelihood inference on the Grassmannian has been studied in other contexts as well; see <cit.> for an overview and comparison of three different models.
Of particular interest is the configuration space of X(d, n) which is modeled by the Grassmannian modulo a torus action.
When d = 2, X(2, n) is the moduli space ℳ_0,n of n marked points in ^1.
Similar to our situation, the number of critical points of the likelihood function on ℳ_0,n grows exponentially and all (n - 3)! critical points are real <cit.>.


This paper is organized as follows.
In Section <ref>, we outline the approach for the proof of Theorem <ref> and study the topology of the parametric model arising from (<ref>).
In Section <ref>, we study the stratification of the parametric model by a deletion map and prove Theorem <ref>.
In Section <ref>, we turn to real critical points and prove Theorem <ref>.
We finish by computing the MLE for random data for 4≤ n≤ 9 and we record the runtimes. 





§ PARAMETRIC MODEL

Our approach to computing the ML degree of sGr(2,n) is topological. 
If X ⊆^n is a projective variety, then ℋ = {(x_0 : ⋯ : x_n) ∈ X | (∑^n_i=0x_i) ·∏_i=0^n x_i = 0} is the set of points of X where the log-likelihood function is undefined.
The set X \ℋ⊆ (^*)^n+1 is a very affine variety, meaning that it is a closed subvariety of the torus (^*)^n+1.
We use the following theorem, which first appeared as <cit.> under stronger hypotheses. 

  If the very affine variety X \ℋ is smooth of dimension d, then the ML degree of X equals the signed Euler characteristic (-1)^dχ(X \ℋ).

The Euler characteristic is a topological invariant that can be defined as the alternating sum of the Betti numbers of the space.
We will often make use of the excision property of the Euler characteristic: if Z = X ⊔ Y, then χ(Z) = χ(X) + χ(Y).
We also rely on the fibration property of the Euler characteristic; if f: X → Y is a fibration, then χ(X) = χ(Y) χ(F), where F is the fiber of a point in Y.
For the maps we consider, proving that the fibers of a map are homeomorphic suffices to show that the map is a fibration.



We apply Theorem <ref> to the squared Grassmannian.
The open squared Grassmannian is the very affine variety


    sGr(d,n)^∘ = {(q_I)_I ∈[n]d∈ sGr(d, n) | ( ∑_I ∈[n]d q_I  ) ·∏_I ∈[n]d q_I≠ 0 }⊆ (^*)^nd.

The variety sGr(d,n)^∘ is smooth because Gr(d,n) is smooth and the Jacobian of the squaring map has full rank on points in the preimage of sGr(d,n)^∘. 
Because ( sGr(d,n)) = d(n-d), by Theorem <ref>, the ML degree of sGr(d,n) is (-1)^d(n-d)χ( sGr(d,n)^∘). 


We now turn to the case d = 2 and parameterize the open squared Grassmannian by 

    X_n → sGr(2,n)^∘,   
      M_n = 
      [   1   0 x_3 x_4   ⋯ x_n;   0   1 y_3 y_4   ⋯ y_n ]↦
      (p_ij^2)_1 ≤ i < j ≤ n

where p_ij is the 2-minor formed from columns i and j of M_n and X_n is the subset of ^2(n-2) such that the image of the parameterization is sGr(2,n)^∘.
To be specific, we define

    Q_n = ∑_1 ≤ i < j ≤ n p_ij^2       and       
      X_n = {
      M_n
      ∈ℂ^2(n-2) Q_n · ( ∏_1 ≤ i< j ≤ n p_ij ) ≠ 0 
      }.

We can explicitly write the parametric log-likelihood function in the d = 2 case as
  
    L_u(M_n) = ∑_i = 3^n   (u_1ilog(y_i^2) + u_2ilog(x_i^2) ) + ∑_3 ≤ i < j ≤ nu_ijlog((x_iy_j - y_ix_j)^2)  - ∑_1 ≤ i < j ≤ n u_ijlog(Q_n).

  The map in (<ref>) has degree 2^n-1 with no ramification points because we can flip the signs of any row and column of the matrix M_n independently; see <cit.>.
  By multiplicativity of the Euler characteristic, the implicit and parametric models are related by:



    χ(X_n) = 2^n-1χ( sGr(2, n)^∘) = 2^n-1 ML Deg( sGr(2,n))  = #{critical points of (<ref>)}.






By (<ref>), we can compute the number of critical points of both the implicit and parametric log-likelihood functions from χ(X_n).
We compute χ(X_n) in Section <ref> by an argument similar to that in <cit.>.
In particular, we wish to define a map X_n + 1→ X_n which deletes the last column and use the fact that this map is a stratified fibration to compute the Euler characteristic inductively. 
However, this deletion map is not well defined, because Q_n vanishes on points in X_n+1, so we define this map only on the open subset of X_n + 1 where Q_n does not vanish, denoted X_n + 1^∘  = {  M_n+1∈ X_n + 1 Q_n ≠ 0  }.
We define the projection

    π_n + 1: X_n + 1^∘→ X_n,       [     1     0   x_3   x_4     ⋯   x_n x_n+1;     0     1   y_3   y_4     ⋯   y_n y_n+1 ]↦[   1   0 x_3 x_4   ⋯ x_n;   0   1 y_3 y_4   ⋯ y_n ]

and argue that the change from X_n + 1 to X_n + 1^∘ does not affect the Euler characteristic.
To do so, we observe that the fiber of a point M_n ∈ X_n under π_n + 1 is the complement in (^*)^2 of the lines p_i(n + 1) and conic Q_n + 1. 
The lines p_i(n+1) all pass through the origin, so the key to understanding the geometry of the fibers is to understand the conic Q_n+1.
We can write

    Q_n + 1 = [     1 x_n+1 y_n+1 ][                 Q_n                   0                   0;                   0 1 + ∑_i = 3^n y_i^2  - ∑_i = 3^n x_iy_i;                   0  - ∑_i = 3^n x_iy_i 1 +	∑_i = 3^n x_i^2 ][     1; x_n+1; y_n+1 ].

Taking the determinant of the matrix, we find that the discriminant of Q_n + 1 as a conic in x_n + 1 and y_n + 1 is Q_n^2.
We  prove that restricting to X_n + 1^∘ does not change the Euler characteristic.

  For n ≥ 3, we have χ(X_n+1) = χ(X_n + 1^∘). 


  By the excision property, χ(X_n+1) = χ(X_n + 1^∘) +χ(X_n+1\ X_n + 1^∘).
  We shall prove that χ(X_n+1\ X_n + 1^∘) = 0 by showing that the map below is a fibration on its image:
  
    X_n + 1\ X_n + 1^∘→ (^*)^2(n-2),       [     1     0   x_3   x_4     ⋯   x_n x_n+1;     0     1   y_3   y_4     ⋯   y_n y_n+1 ]↦[   1   0 x_3 x_4   ⋯ x_n;   0   1 y_3 y_4   ⋯ y_n ].

  It suffices to show that the fibers  are homeomorphic. 
  Every nonempty fiber F is the complement in (^*)^2 of n - 1 lines through the origin: each minor p_i(n + 1) for i ≥ 3 contributes one line and  Q_n + 1 degenerates into a double line since Q_n = 0.

  The Euler characteristic of finitely many lines through the origin in (^*)^2 is zero because each line is a ^1 with two points removed and the lines do not intersect. 
  Because χ((^*)^2) = 0, the Euler characteristic of the complement of n -1 lines through the origin in (^*)^2 is zero, too.
  By the fibration property of the Euler characteristic and because χ(F) = 0, we conclude that χ(X_n + 1\ X_n + 1^∘) = 0.




























§ STRATIFICATION OF THE PARAMETRIC MODEL

We now prove that the map π_n + 1 is a stratified fibration and compute χ(X_n).
A map f: X → Y between complex algebraic varieties with a stratification {S_α}_α=1^m of Y by closed sets is a
stratified fibration if the restriction of f to each open stratum S^∘_α = S_α\⋃_S_β⊊ S_α S_β is a fibration with fiber denoted F_S_α.
We use Möbius inversion with the fibration property of the Euler characteristic, to compute Euler characteristics along stratified fibrations.


  Let f: X → Y be a stratified fibration.
  Let 𝒮 be the poset of closed strata S_α of f, let F_S_α be the fiber of a generic point in S_α, and let μ be the Möbius function of 𝒮.
  Then
  
    χ(X) 
           = χ(Y) ·χ(F_Y) + ∑_S_α∈𝒮χ(S_α) ·∑_S_β∈𝒮, S_β⊇ S_αμ(S_α, S_β) · (χ(F_S_β) - χ(F_Y)).


In our situation, only the generic fiber contributes: the sums vanish and χ(X) = χ(Y) χ(F_Y). 
We first describe the stratification of X_n and the fibers of π_n + 1.

  The map π_n + 1 is a stratified fibration with stratification
  
    𝒮 = { X_n }∪{S_i | 1 ≤ i ≤ n}∪{S_i ∩ S_j | 1 ≤ i < j ≤ n},

  where S_i = {M_n ∈ X_n |∑_j = 1^n p_ij^2 = 0}.
  The fibers of π_n + 1 are the complements of n lines p_i(n+1) and a conic Q_n + 1 in ^2 where the intersections of the lines with the conic are
  

    
      Q_n + 1∩ p_k(n+1) = two points for all k     in  F_X_n.

      Q_n + 1∩ p_k(n+1) = two points for k ≠ i
∅ for k = i.     in F_S_i.

      Q_n + 1∩ p_k(n+1) = two points for k ≠ i,j
∅ for k ∈{i,j}     in F_S_i ∩ S_j.
    
  



  To prove π_n + 1 is a fibration, it suffices to show that the fibers of π_n + 1 are homeomorphic on each open stratum S^∘.
  
  The fiber in ^2 of a point M_n ∈ X_n is the complement of the lines p_i(n + 1) and the conic Q_n + 1.
  Since all the lines p_i(n + 1) pass through the origin, their intersection is the same for any M_n ∈ X_n.
  The variation in the fibers comes from the intersection with the conic. 
  We claim that every line p_i(n+1) either intersects the conic Q_n + 1 in two distinct points or
  not at all.
  
  In the intersection locus of p_i(n+1) = 0 and Q_n + 1 = 0, 
  
  
  
    Q_n + 1 = Q_n + ∑_j = 1^n p_j (n + 1)^2 = Q_n + x_n+1^2/x_i^2∑_j = 1^n p_ij^2 = 0.

  If ∑_j = 1^n p_ij^2 ≠ 0, then there are two distinct intersection points.
  If ∑_j = 1^n p_ij^2 = 0, then (<ref>) becomes Q_n = 0, which is a contradiction, so the intersection of Q_n + 1 and p_i(n + 1) is empty.
  Thus, in the fiber F_X_n, every line intersects the conic in two points and in the fiber F_S_i, every line intersects the conic in two points, except p_i(n+1) which does not intersect the conic. 


  
  It remains to be shown that there can be at most two lines p_i(n+1) which do not intersect Q_n + 1.
  When p_i(n+1) does not intersect Q_n + 1 in ^2, the line and conic intersect at a double point at infinity.
  In other words, p_i(n+1) is tangent to the projectivization of Q_n + 1 at infinity.
  In projective space, p_i(n + 1) intersects Q_n + 1 tangentially if and only if p_i(n + 1)^∨ lies in the dual conic Q_n + 1^∨, i.e., [    0 -y_i  x_i ] A_n^-1[    0 -y_i  x_i ]^T =∑_j = 1^n p_ij^2 = 0.
  Since at most two lines passing through the origin can be tangent to a conic, only two of the lines p_i(n + 1) can have an empty intersection with the conic Q_n + 1 at once. 
  Thus, in the fiber F_S_i ∩ S_j, every line intersects the conic in two points, except p_i(n + 1) and p_j(n + 1) which do not intersect the conic. 




















































The combinatorics of the stratification 𝒮 is simple, which allows us to evaluate the formula for the Euler characteristic in Lemma <ref>.
To apply the lemma, we need the Möbius function of the poset of each closed stratum; see Figure <ref> for the posets of each of the special strata along with the values of their Möbius functions.
The remaining computations necessary to prove Theorem <ref> are Euler characteristics of the fibers and of the strata.


 
  The Euler characteristics of the fibers are
  
    χ(F_X_n) = 2n       χ(F_S_i) = 2n - 2       χ(F_S_i ∩ S_j) = 2n - 4       for 1 ≤ i < j ≤ n.




  In ^2\{(0,0)}, we have χ(Q_n + 1) = 0, since the conic Q_n + 1 has nonzero constant term Q_n and is therefore topologically equivalent to a ^1 with two points at infinity removed. 
  Similarly, in ^2\{(0,0)}, we have χ(p_i(n + 1)) = 0, since the line p_i(n + 1) is topologically equivalent to a ^1 with the origin and a point at infinity removed.
  Suppose that M_n ∈ X_n.
  Because χ(^2\{(0,0)}) = 0, by the excision property,
  
    χ(π^-1(M_n))    = - χ(Q_n + 1) - ∑_i = 1^n χ(p_i(n + 1)) + ∑_i = 1^n χ(p_i(n + 1)∩ Q_n + 1)
       = ∑_i = 1^n χ(p_i(n + 1)∩ Q_n + 1) =  | ⋃_i = 1^n (p_i(n + 1)∩ Q_n + 1)  |

  where the last equality holds because the intersection of a line with a conic is zero dimensional.

  We computed these intersections in Lemma <ref>.
  In the generic fiber, each of the n lines intersects the conic in two points, for a total of 2n intersection points.
  The intersections for S_i, S_i ∩ S_j are the same, but with n - 1 and n - 2 lines, respectively. 
  
  




We now show that the Euler characteristics of the closed, codimension one strata vanish.


  We have χ(S_i) = 0 for all i. 


  It is sufficient to prove the claim for S_n by symmetry.
  We first remark that S_n ⊂ X_n^∘.
  

  We argue that S_n has Euler characteristic zero by showing that π_n|_S_n is a fibration whose fiber is the union of two lines through the origin in (^*)^2. 

  
  Since the fiber has Euler characteristic zero, the result follows from the fibration property.
  
  Because  ∑_j = 1^n-1 p_jn^2 is a homogeneous polynomial in x_n and y_n, the fiber of a point in π_n(S_n) is a degenerate conic in the variables x_n, y_n, so each fiber is the union of two lines through the origin in the complement of the lines p_jn and conic Q_n in (^*)^2.
  Since the p_jn all pass through the origin, they do not intersect the degenerate conic in (^*)^2.
  The conic Q_n also does not intersect ∑_j = 1^n-1 p_jn^2, because  Q_n - ∑_j = 1^n-1 p_jn^2 = Q_n - 1 = 0 on the intersection, contradicting S_n ⊂ X_n^∘.
  Since the conic ∑_j = 1^n-1 p_jn^2 does not intersect the lines p_jn or the conic Q_n, the fiber is the union of two lines through the origin in (^*)^2.


We do not need to compute χ(S_i ∩ S_j), because the inside sum in Lemma <ref> vanishes for S_i ∩ S_j.
In fact, we can count the number of critical points of the parametric log-likelihood function.
Theorem <ref> then follows from Proposition <ref> and (<ref>). 


  The parametric log-likelihood function (<ref>) has 2^n-2 (n-1)! critical points. 



  By (<ref>), the number of critical points is equal to the Euler characteristic χ(X_n), so it suffices to show that χ(X_n) = 2^n-2 (n-1)!.

  We proceed by induction on n. 
  The base case is furnished by Example <ref>.
  By Lemmas <ref>, <ref>, and <ref>, we have
  
    χ(X_n + 1) = χ(X_n + 1^∘) =
        χ(F_X_n) χ(X_n)
        + ∑_i = 1^n χ(S_i) ∑_S' ∈{S_i, X_n}μ(S_i, S') (χ(F_S') - F_X_n )
    
        + ∑_1 ≤ i < j ≤ nχ(S_i∩ S_j) ∑_S' ∈{S_i ∩ S_j, S_i, S_j, X_n}μ(S_i ∩ S_j, S') (χ(F_S') - F_X_n )

  By Lemma <ref>, χ(S_i) = 0, so the first sum is zero.
  By Lemma <ref> 
  and the values of the Möbius function in Figure <ref>, the second sum is zero:
  
    ∑_S' ∈{S_i ∩ S_j, S_i, S_j, X_n}μ(S_i ∩ S_j, S') (χ(F_S') - χ(F_X_n)) =
        (1)(-4) + (-1)(-2) + (-1)(-2) = 0.

  By induction and Lemma <ref>, χ(X_n + 1) = χ(F_X_n) χ(X_n) = 2n(2^n-2(n-1)!) = 2^n-1n!.


A formula for the ML degree of sGr(d, n) for d > 2 has not yet been conjectured.
In our calculation of the ML degree of sGr(2,n), we relied heavily on the nice geometry of conics in the complex projective plane, which we do not have for higher d.
In <cit.>, the ML degrees for d = 3 and n = 5, 6, 7 were found to be 12, 552, and 73440 by numerical methods.
These numbers don't follow an obvious pattern, so it is likely that the combinatorics of the stratification is complicated and that we do not have the nice cancellation we get in the proof of Proposition <ref>.
The ML degrees of the configuration space X(d, n) behave similarly.
The ML degree of X(2, n) = ℳ_0,n is (n - 3)! <cit.>, but when d ≥ 3 the combinatorics of the stratification is more complicated and the Euler characteristics are more difficult to compute.
The ML degrees of X(3,n) are known for n ≤ 9 <cit.>.
The ML degree of X(4, 8) was numerically shown to be 5211816 <cit.>.



§ REAL SOLUTIONS


From a statistical perspective, the only relevant critical points of the implicit log-likelihood function (<ref>) are real, nonnegative ones.
Because q_I is a square, this condition is equivalent to the critical points of the parameteric log-likelihood function (<ref>) being real.
We will prove that when d = 2, all critical points of the parametric log-likelihood function (<ref>) are real and are local maxima.
This is not necessarily true for greater d.

[d=3, n = 6]
  This parametric log-likelihood function has 17664 critical points <cit.>.
  Generically, 11904 of them are real and local maxima.
  These numbers were computed using the  package  <cit.>. 

  



For real solutions we turn from the log-likelihood function to the likelihood function

    ∏_1 ≤ i < j ≤ np_ij^2u_ij/ (∑_1 ≤ i < j ≤ np_ij^2 )^∑_i,ju_ij,

which shares its critical points with the log-likelihood function.

We optimize (<ref>) on the real open set X_n^ = X_n ∩^2(n-2).
Since the quadric Q_n has no real solutions, we are left with the complement of the real algebraic variety ⋃_1 ≤ i < j ≤ nV_(p_ij).
The irreducible hypersurfaces V_(p_ij) all pass through the origin and divide X_n^ into unbounded regions.
It is known that every bounded region  contains at least one critical point, because the function is either positive or negative on the region and must therefore achieve a local minimum or maximum; see <cit.>.
The following result extends this idea to unbounded regions.

  Let f_0, f_1, …, f_n ∈[x_1, …, x_d] such that f_0 = 1 and f_0 + f_1 + ⋯ + f_n is positive on ^d.
  If u_0, u_1, …, u_n ∈_> 0, then 
  
    #{regions of ^d \⋃_i=1^n {f_i = 0}}
    ≤#{critical points of f_0^u_0f_1^u_1⋯ f_n^u_n/(f_0 + ⋯ + f_n)^u_0 + ⋯ + u_n in ^d}
    ≤ML degree of V(f_0, …, f_n)

  Further, L = f_0^u_0f_1^u_1⋯ f_n^u_n/(f_0 + ⋯ + f_n)^u_0 + ⋯ + u_n has a local maximum for every region of ^d \⋃_i=1^n {f_i = 0} where L > 0 and a local minimum for every region where L < 0. 


  Since f_0 + ⋯ + f_n > 0, the function L is smooth on ^d.
  
  Because the denominator of L has larger degree than the numerator, L approaches 0 at infinity and is therefore bounded on all regions.
  Because L is smooth and bounded, it attains a local maximum or minimum on each region, depending on the sign of L.
  This proves the first inequality and second statement.
  The second inequality follows from the definition of ML degree. 


We use this result to show that all critical points of the parameteric likelihood function (<ref>) are real.
Theorem <ref> is an immediate corollary, since squares of real numbers are nonnegative. 
A similar technique was used to show that all critical points of the likelihood function on the moduli space ℳ_0,n are real in <cit.>.


  All critical points of the parametric likelihood function (<ref>) are real and each critical point is a local maximum.


  We will prove that X_n^ has exactly 2^n-2(n-1)! regions.

  By Lemma <ref>, with f_0 = p_12 = 1, L_u(M_n) has at least 2^n-2(n-1)!  real solutions.
  Since the total number of solutions is 2^n-2(n-1)! by Theorem <ref>, all solutions are real.
  Every solution is a local maximum by Lemma <ref>, because (<ref>) is nonnegative on ^2(n-2), so it is positive on every region of X_n^.
  

  We first argue that the number of regions of X_n^ is equal to the number of possible sign vectors of (p_ij)_1 ≤ i< j ≤ n.
  Every region has a fixed sign vector, since it is impossible to change the sign vector without crossing a p_ij. 
  Conversely, given a sign vector (s_ij)_1 ≤ i < j ≤ n, Y_s = {M_n ∈ X_n^ : sgn(p_ij) = s_ij} is contractible: for any M_n ∈ Y_s, G(M_n', t) = tM_n + (1-t)M_n' ∈ Y_s for all t ∈ [0,1] and M_n' ∈ Y_s, so G is a deformation retract onto M_n.

  To count the sign vectors, we fix 2 ≤ k ≤ n  and begin with a matrix
  
    M_n = [       1       0    -x_3       ⋯    -x_k x_k + 1       ⋯     x_n;       1       0     y_3       ⋯     y_k y_k + 1       ⋯     y_n ]

  in X_n such that x_3,…, x_n, y_3, …, y_n > 0.
  We take any permutation of the last n - 2 columns and flip the sign of any of the last n - 2 columns.
  This process yields 2^n - 2 (n - 2)! different matrices.
  
  We argue that given a fixed M_n, each of these matrices has a distinct sign vector.
  Because every matrix in X_n arises in this way, there are 2^n - 2 (n - 2)! possible sign vectors for a fixed k.
  Hence, in total, we have 2^n - 2 (n - 1)! total possible sign vectors. 

  Let p be the Plücker vector of M_n and q be the Plücker vector of a matrix produced from M_n by the permutation and sign changes described above.
  We identify the permutation and columns whose signs were flipped.
  The columns i with q_1i < 0 had their signs flipped. 

  
  Assuming that q_1i > 0 for all i, we uniquely identify the permutation from its inversions: for i, j ≥ 3 the signs of p_ij and q_ij agree if and only if the pair ij is not an inversion.


The practical implication of this result is that likelihood inference for projection DPPs is difficult.
In particular, for any data u, the number of local maximizers of both the implicit and parametric log-likelihood function grows exponentially.
In constrast, the linear model on ℳ_0,n in <cit.>,  has only one positive critical point.





  
  
  
  
  
  




Computational Experiments.
  To compute the true MLE for some data u, one needs to compute all critical points of the parametric log-likelihood function (<ref>), evaluate (<ref>) at the critical points, and select the one which yields the largest value.
  We give runtimes for computing the MLE of our model for data selected uniformly at random from [1000].
  We use the numerical algebraic geometry software  <cit.> to compute the critical points of (<ref>).
  We use the strategy outlined in <cit.> to find solutions to the rational equations ∇ L_u(M_n) = 0. 
  We first use the monodromy method to compute the solutions to  ∇ L_u'(M_n) = 0 for some complex start parameters u'.
  We then use a coefficient parameter homotopy to move the start parameters u' to the target parameters u ∈ [1000]^n2, simultaneously moving each solution of ∇ L_u'(M_n) = 0 to a solution of ∇ L_u(M_n) = 0.
  
    [                                   n = 4               n = 5               n = 6               n = 7               n = 8               n = 9;             Runtime             180  ms             235  ms             962  ms           14.287  s              330  s                2  h; Number of Solutions                  24                 192                1920               23040              322560             5160960;                     ]

  The runtime grows exponentially, as expected.
  The bulk of the time is spent computing the solutions to ∇ L_u'(M_n) = 0 with the monodromy method.
  Because  uses a heuristic stopping criterion, knowing the number of solutions a priori makes the computation significantly faster than if we did not know the number of solutions. 
  The computations were run with 64 threads on a 2 × 8-Core Intel Xeon Gold 6144 at 3.5 GHz.


Acknowledgments


We thank Simon Telen for proving the count of critical points for n = 4, which inspired the proof of Theorem <ref>.
We also thank Claudia Fevola, Bernhard Reinke, and Claudia Yun for helpful conversations. 
We thank the Max Planck Institute for Mathematics in the Sciences for its  stimulating research environment and for its computing resources. 






Hannah Friedman, UC Berkeley
<hannahfriedman@berkeley.edu>

