# Completions to discrete probability distributions in log–linear models

May Cai  M. Cai
School of Mathematics
Georgia Institute of Technology
Atlanta
Georgia 30332
USA<EMAIL_ADDRESS>,  Cecilie Olesen Recke  C.O. Recke
Department of Mathematics
University of Copenhagen
Copenhagen
Denmark<EMAIL_ADDRESS>and  Thomas Yahl  T. Yahl
Department of Mathematics
University of Wisconsin–Madison
Madison
Wisconsin 53706
USA<EMAIL_ADDRESS>https://tjyahl.github.io/

###### Abstract.

Completion problems, of recovering points from a set of observed coordinates,
are abundant in applications to image reconstruction, phylogenetics, and data
science. We consider a completion problem coming from algebraic statistics, of
determining those observed probabilities which can be finitely completed to a
probability distribution in a given log–linear model. These observed
probabilities either have a unique completion or two completions to the
log–linear model depending on the set of observed coordinates.

##  1\. Introduction

An imperfect data sampling method may prevent one from observing certain
outcomes and thus, it may be that probabilities are only known for certain
outcomes. With a priori knowledge of the statistical model, the known
probabilities may be used to compute the probability for each outcome—the
original probability distribution may be recovered, or completed.

A problem of this form is known as a probability completion problem.
Precisely, consider a statistical model $\mathcal{M}\subseteq\mathbb{R}^{n}$
consisting of probability distributions with outcome states
$[n]=\\{1,\dotsc,n\\}$. Fix a subset of these states $E\subseteq[n]$ called
observed states which correspond to those probabilities which are known or
able to be obtained. This subset of states determines a coordinate projection
$\pi_{E}:\mathcal{M}\to\mathbb{R}^{E}$ whose image consists of points which
may be completed to a probability distribution in $\mathcal{M}$. A point
$p_{E}\in\mathbb{R}^{E}$ is called a partial observation, and one looks to
describe the fiber $\pi_{E}^{-1}(p_{E})$—the set of probability distributions
$p\in\mathcal{M}$ whose coordinate projection $\pi_{E}(p)$ is equal to
$p_{E}$. We say a probability distribution $p\in\pi_{E}^{-1}(p_{E})$ is a
completion of $p_{E}$ to the model $\mathcal{M}$. In addition to enumerating
the completions of a partial observation, one may look for an explicit
description of the image $\pi_{E}(\mathcal{M})$—the set of partial
observations which may be completed to $\mathcal{M}$.

Probability completion problems were first considered in [KKKR17, KR17], where
they study completions to the independence model of two or more random
variables. As the independence model is the intersection of the space of rank
one tensors and the probability simplex, this may be regarded as a type of low
rank tensor completion problem as in [SC10, KTTU12, KTT15, BBS20]. More
generally, probability completion problems may be understood as problems in
compressed sensing as described in [BGMV23].

We are concerned with probability completion problems where the statistical
model $\mathcal{M}$ is a log–linear model, the restriction of a toric variety
to the probability simplex. The class of log–linear models encompasses many
well–studied discrete models such as discrete graphical models, hierarchical
models, and staged–tree models [HS02, HS07, GMN22]. Log–linear models are also
important as their Markov bases are understood and may be used in sampling
algorithms as described in [DS98, Sul18].

We use the well–understood geometry of toric varieties to infer properties of
the log–linear model and the completion problem. For example, the algebraic
moment map relates the topology of a given log–linear model $\mathcal{M}$ with
the topology of a specific polytope. Many results concerning a log–linear
model can then be deduced by studying this polytope, in particular, its facial
structure.

Our main contributions are twofold. We enumerate the number of completions of
a partial observation to a log–linear model under mild conditions and we
determine an effective algorithm of describing the completable region—which
consists of partial observations that are completable to the log–linear model.
These results are summarized in Theorem 4.10, Theorem 4.12, and Theorem 4.15.
We illustrate these results with several examples, some of which are relevant
for applications.

We begin by giving background on toric varieties and log–linear models in
Section 2. In Section 3, we describe the completion problem to a given toric
variety and include necessary results for future sections. In Section 4 we
have our completion results to a given log–linear model. We also give explicit
computations of when completions are possible to examples of log–linear models
and hierarchical models. In Section 5, we give a procedure for describing the
algebraic boundary of the completable region, as well as explicit
semialgebraic descriptions for certain models.

### Acknowledgements

The authors would like to thank Kaie Kubjas for her mentorship and advice
throughout the research process. We are also grateful for Serkan Hoşten, Kaie,
and Bernd Sturmfels for organizing the Varieties from Statistics
Apprenticeship Week at the Institute for Mathematical and Statistical
Innovation (IMSI). Furthermore we would like to thank all the other
participants of the Algebraic Statistics and Our Changing World program for
their feedback on early drafts of the paper. Part of this research was
performed while the authors were visiting the Institute for Mathematical and
Statistical Innovation (IMSI), which is supported by the National Science
Foundation (Grant No. DMS–1929348). This research was partially supported by
NSF Grant No. DMS–1855726. Cecilie Olesen Recke was supported by Novo Nordisk
Foundation Grant NNF20OC0062897.

##  2\. Toric Varieties

We discuss the necessary background on toric varieties for the completion
problem. Given a vector of non–negative integers
$v=(v_{1},\dotsc,v_{k})\in\mathbb{Z}_{\geq 0}^{k}$ and variables
$\theta=(\theta_{1},\dotsc,\theta_{k})$, a monomial is an expression of the
form $\theta^{v}=\theta_{1}^{v_{1}}\dotsb\theta_{k}^{v_{k}}$. The vector $v$
is the exponent vector of the monomial $\theta^{v}$. For an integer matrix
$A\in\mathbb{Z}_{\geq 0}^{k\times n}$ with columns
$a_{1},\dotsc,a_{n}\in\mathbb{Z}_{\geq 0}^{k}$, we define a map
$\varphi^{A}:\mathbb{C}^{k}\to\mathbb{C}^{n}$ by

$\displaystyle\varphi^{A}(\theta)=(\theta^{a_{1}},\dotsc,\theta^{a_{n}}).$

That is, the coordinate functions of $\varphi^{A}$ are monomials, and the
exponent vector of each monomial is a column of $A$.

The closure of the image $X_{A}=\overline{\operatorname{im}\varphi^{A}}$ is
the toric variety associated to the integer matrix $A\in\mathbb{Z}_{\geq
0}^{k\times n}$, which is an irreducible variety of dimension $\dim
X_{A}=\operatorname{rank}A$. In the language of [CLS11], the image
$\varphi^{A}((\mathbb{C}^{\times})^{k})$ is a dense torus which acts on the
points of $X_{A}$ by coordinate–wise multiplication. We note that this fact
remains true over the real numbers. If $p\in X_{A}$ lies in the toric variety
and $\theta\in(\mathbb{R}^{\times})^{k}$, then the coordinate–wise product
$p\varphi^{A}(\theta)\in X_{A}$ also lies in the toric variety.

The defining ideal of the toric variety $X_{A}$,

$\displaystyle
I_{A}=I(X_{A})=\\{f\in\mathbb{C}[x_{1},\dotsc,x_{n}]:f(x)=0\leavevmode\nobreak\
\text{ for all }\leavevmode\nobreak\ x\in X_{A}\\},$

is called a toric ideal. The toric ideal $I_{A}$ is a prime ideal generated by
pure binomials and generators for this ideal may be computed explicitly from
the matrix $A$, as described in [Sul18].

######  Proposition 2.1.

If $A\in\mathbb{Z}_{\geq 0}^{k\times n}$ is an integer matrix, then

$\displaystyle I_{A}=\langle p^{u}-p^{v}\;|\;u,v\in\mathbb{N}^{n}\text{ and
}Au=Av\rangle.$

Further, if $(1,\dotsc,1)\in\operatorname{im}A^{T}$, then $I_{A}$ is
homogeneous.

Software such as 4ti2 [tt] and Macaulay2 [GS] contain methods used to
effectively compute Gröbner bases for toric ideals. This allows one to make
several computations with toric ideals, such as determining containment of
points and computing elimination ideals.

Given an integer matrix $A\in\mathbb{Z}_{\geq 0}^{k\times n}$, the image
$\operatorname{im}\varphi^{A}$ can be determined precisely. The following
definition taken from [GMS06] provides a necessary condition for a point to
lie in the image $\operatorname{im}\varphi^{A}$. For a point
$p\in\mathbb{C}^{n}$, the support of $p$ is the set

$\displaystyle\operatorname{supp}(p)=\\{i\in[n]:p_{i}\neq 0\\}$

consisting of the coordinates of $p$ which are non–zero.

######  Definition 2.2 ([GMS06]).

Let $A\in\mathbb{Z}_{\geq 0}^{k\times n}$ be a matrix with column vectors
$a_{1},\dotsc,a_{n}\in\mathbb{Z}^{k}$. A point $p\in\mathbb{C}^{n}$ is
$A$–feasible if, for every $j\in[n]\setminus\operatorname{supp}(p)$, the
support $\operatorname{supp}(a_{j})$ is not contained in the union
$\bigcup_{l\in\operatorname{supp}(p)}\operatorname{supp}(a_{l})$.

We note that $A$–feasibility is equivalent to the notion of zero–consistency
from [KKKR17]. $A$–feasibility is a necessary condition for a point
$p\in\mathbb{C}^{n}$ to lie in the image $\operatorname{im}\varphi^{A}$. For
those points lying in the toric variety $p\in X_{A}$, this condition is also
sufficient. This was proved in [GMS06] for the non–negative toric variety—we
extend their result to the complex toric variety.

######  Proposition 2.3.

If $A\in\mathbb{Z}_{\geq 0}^{k\times n}$ is an integer matrix, then the image
of the map $\varphi^{A}$ is given by the set

$\displaystyle\operatorname{im}\varphi^{A}=\\{p\in X_{A}:p\leavevmode\nobreak\
\text{is $A$--feasible}\\}.$

###### Proof.

Write $a_{1},\dotsc,a_{n}$ for the columns of $A$ and $a_{ij}$ for the
$(i,j)$-entry of $A$. If $p\in\operatorname{im}\varphi^{A}$, then
$p\in\overline{\operatorname{im}\varphi^{A}}=X_{A}$. Similarly, if
$p=\varphi^{A}(\theta)$ then for $j\in[n]\setminus\operatorname{supp}(p)$,
there is an $i\in[k]$ such that $a_{ij}>0$ and $\theta_{i}=0$ so that
$i\in\operatorname{supp}(a_{j})$. However,
$i\not\in\operatorname{supp}(a_{l})$ for each $l\in\operatorname{supp}(p)$
since otherwise $p_{l}=0$. Therefore, $p$ is $A$–feasible. Thus, the inclusion
$\operatorname{im}\varphi^{A}\subseteq\\{p\in X_{A}:p\leavevmode\nobreak\
\text{is $A$--feasible}\\}$ holds.

For the reverse inclusion, let $p\in X_{A}$ be $A$–feasible. Without loss of
generality we may assume that $p$ only has non–zero entries. Indeed, since $p$
is $A$–feasible, we may restrict $\varphi^{A}$ to the coordinate subspace of
$\mathbb{C}^{k}$ such that $\theta_{i}=0$ for
$i\in[n]\setminus\bigcup_{l\in\operatorname{supp}(p)}\operatorname{supp}(a_{l})$.
We compute a preimage of this restriction by discarding all zero entries of
$p$, and reinserting them in the appropriate places afterwards.

Let $p\in X_{A}$ have non–zero coordinates. From 2.1, for any
$u\in\mathbb{Z}^{n}$ such that $Au=0$, we must have that $p^{u}=1$. By taking
the logarithm and writing $\log(p)$ for the coordinate–wise logarithm of $p$,
one finds that $u^{T}\log(p)=0$. Thus, $\log(p)$ annihilates the kernel of $A$
and hence, lies in the image of $A^{T}$. Writing $\log(p)=A^{T}v$ and applying
coordinate–wise exponentiation, one finds that
$p=\varphi^{A}(e^{v})\in\operatorname{im}\varphi^{A}$. ∎

We assume now that our matrix $A\in\mathbb{Z}_{\geq 0}^{k\times n}$ is such
that each column sum is equal to a fixed number $N$. Thus $(1,\dotsc,1)$ is an
eigenvector for $A^{T}$ so that $(1,\dotsc,1)\in\operatorname{im}A^{T}$. Let
$\operatorname{conv}S$ denote the convex hull of the points in a set $S$ and
recall that a polytope is the convex hull of a finite point set. We write
$P_{A}=\operatorname{conv}\\{a_{1},\dotsc,a_{n}\\}$ for the polytope defined
by the columns of $A$. This polytope is contained in the hyperplane determined
by the equation $\sum_{i}x_{i}=N$ and has dimension $\operatorname{rank}A-1$.

A facial set of $A$ is a set $F\subseteq[n]$ such that there is a vector
$v\in\mathbb{R}^{k}$ satisfying $v^{T}a_{i}=0$ for $i\in F$ and $v^{T}a_{i}>0$
for $i\in[n]\setminus F$. We call the vector $v$ an inner normal vector for
the face $F$. A facet is a proper face which is not contained in any strictly
larger proper face.

Geometrically, a facial set indexes the columns of $A$ that lie in a face of
the polytope $P_{A}$ and an inner normal vector $v$ of a face $F$ is an inner
normal vector of the cone over the polytope $P_{A}$ with the cone point at the
origin. More on the relationship between cones, polytopes, and their faces can
be found in [Ewa96].

######  Remark 2.4.

The assumption that the column sums of $A$ are equal is a stronger condition
than necessary. However, many problems that arise naturally in applications
satisfy this property. The weaker assumption that the affine span of the
columns has dimension $\operatorname{rank}A-1$ is sufficient for the results
to hold.

The following result from [GMS06] describes the set of possible supports of a
point in $X_{A}$ via the facial sets of $A$.

######  Lemma 2.5 ([GMS06]).

Let $A\in\mathbb{Z}_{\geq 0}^{k\times n}$ be a matrix whose columns are the
vectors $a_{1},\dotsc,a_{n}\in\mathbb{R}^{k}$. If $p\in X_{A}$, then
$\operatorname{supp}(p)$ is a facial set of $A$.

If $F\subseteq[n]$ is a facial set of $A\in\mathbb{Z}_{\geq 0}^{k\times n}$,
we define the characteristic vector $\chi_{F}$ by $(\chi_{F})_{i}=1$ if $i\in
F$ and $(\chi_{F})_{i}=0$ if $i\in[n]\setminus F$. By [GMS06, A.2],
$\chi_{F}\in X_{A}$. Thus, for every facial set $F$ of $A$, there is a point
of $X_{A}$ with support $F$.

###  2.1. Non–negative Toric Varieties and Log–Linear Models

Given a matrix $A\in\mathbb{Z}_{\geq 0}^{k\times n}$, we define the
non–negative toric variety $X_{A}^{\geq 0}=X_{A}\,\cap\,\mathbb{R}_{\geq
0}^{n}$. We will also write $X_{A}^{>0}$ for the points of $X_{A}^{\geq 0}$
with positive coordinates. For a positive integer $n>0$, we write
$\Delta_{n-1}\subseteq\mathbb{R}^{n}$ for the set of probability distributions
in $\mathbb{R}^{n}$—precisely, $\Delta_{n-1}$ is the set of points
$p\in\mathbb{R}^{n}$ whose coordinates are non–negative and sum to one. The
intersection $X_{A}\cap\Delta_{n-1}$ may be considered as a set of probability
distributions which are limits of certain discrete exponential probability
distributions as described in [GMS06].

######  Definition 2.6.

The log–linear model defined by an integer matrix $A\in\mathbb{Z}_{\geq
0}^{k\times n}$ is the set

$\displaystyle\mathcal{M}_{A}=X_{A}^{\geq 0}\cap\Delta_{n-1}.$

We will write $\mathcal{M}_{A}^{>0}=X_{A}^{>0}\cap\Delta_{n-1}$ for the points
of the log–linear model $\mathcal{M}_{A}$ with positive coordinates. Note that
our definition of log–linear model varies from that found in [Sul18]. In
particular, we allow for probability distributions that lie in the boundary of
the probability simplex. The origin of the name “log–linear model” is
described in Chapter 6 of [Sul18]. Namely, for those points
$p\in\mathcal{M}_{A}^{>0}$ with non–zero coordinates, the coordinate–wise
logarithm $\log(p)$ lies in the image $\operatorname{im}A^{T}$. Many familiar
discrete probability models are in fact log–linear models, such as the
independence model, undirected graphical models, and hierarchical models.

If $A\in\mathbb{Z}_{\geq 0}^{k\times n}$ is such that
$(1,\dotsc,1)\in\operatorname{im}A^{T}$, then the log–linear model
$\mathcal{M}_{A}$ may be considered the projectivization of the non–negative
toric variety $X_{A}^{\geq 0}$ in the real projective space
$\mathbb{RP}^{n-1}$. Indeed, since $I_{A}$ is homogeneous, $X_{A}^{\geq 0}$ is
a cone and we may scale each point so that the sum of the coordinates is equal
to one. The algebraic moment map provides a way to understand the topology of
the projectivization of the non–negative toric variety and hence, of our model
$\mathcal{M}_{A}$.

The algebraic moment map is defined on the projectivization of a non–negative
toric variety in [Ful93, Sot03]. With the identification of the
projectivization of the non–negative toric variety with the log–linear model
$\mathcal{M}_{A}$, we may define the algebraic moment map as follows.

######  Definition 2.7.

The algebraic moment map $\mu:\mathcal{M}_{A}\to\mathbb{R}^{n}$ is defined by
$\mu(p)=Ap$.

For $p\in\mathcal{M}_{A}$, the image $\mu(p)$ is a convex combination of the
columns of $A$. Hence, the image of the algebraic moment map is contained in
the polytope $P_{A}$. In fact, the algebraic moment map is a homeomorphism of
$\mathcal{M}_{A}$ with $P_{A}$ [Sot03]. Further, this map restricts to a
homeomorphism of $\mathcal{M}_{A}^{>0}$ with the interior
$\operatorname{int}(P_{A})$ as described in [Ful93].

######  Theorem 2.8 ([Ful93, Sot03]).

If $A\in\mathbb{Z}_{\geq 0}^{k\times n}$ is such that
$(1,\dotsc,1)\in\operatorname{im}A^{T}$, then the algebraic moment map
$\mu:\mathcal{M}_{A}\to P_{A}$ is a homeomorphism. Further, the restriction
$\mu:\mathcal{M}_{A}^{>0}\to\operatorname{int}(P_{A})$ is a homeomorphism.

This provides useful topological information about our model. For example,
this implies that both $\mathcal{M}_{A}$ and $\mathcal{M}_{A}^{>0}$ are
contractible spaces and in particular, they are connected. Further, the set
$\mathcal{M}_{A}^{>0}$, consisting of points of the log–linear model with
non–zero coordinates, is the interior of the log–linear model
$\mathcal{M}_{A}$ and is dense. Thus, the boundary $\partial\mathcal{M}_{A}$
of the log–linear model consists of points with some coordinate equal to zero.

##  3\. Completing to the Toric Variety

We write $[n]=\\{1,\dotsc,n\\}$ for the set indexing the coordinates of
$\mathbb{C}^{n}$. Any subset $E\subseteq[n]$ determines a projection
$\pi_{E}:\mathbb{C}^{n}\to\mathbb{C}^{E}$ to the coordinates indexed by $E$
and we say a partial observation is a point $p_{E}\in\mathbb{C}^{E}$. Given an
integer matrix $A\in\mathbb{Z}_{\geq 0}^{k\times n}$, our goal in this section
is to describe the image $\pi_{E}(X_{A})$—the set of partial observations
$p_{E}\in\mathbb{C}^{E}$ which are completable to a point in the toric variety
$p\in X_{A}$. We do so by first explicitly determining when a partial
observation is completable to the image $\operatorname{im}\varphi^{A}$.

As $E\subseteq[n]$, we will write
$\operatorname{supp}(\pi_{E}(p))=\operatorname{supp}(p)\cap E$ for a point
$p\in\mathbb{C}^{n}$. If $A_{E}$ denotes the submatrix of $A$ whose columns
are indexed by $E$, then there is an equality
$\varphi^{A_{E}}=\pi_{E}\circ\varphi^{A}$. Thus, we may write equality of the
images
$\pi_{E}(\operatorname{im}\varphi^{A})=\operatorname{im}\varphi^{A_{E}}$ and
the defining ideal of the image $\pi_{E}(\operatorname{im}\varphi^{A})$ is the
toric ideal given by

$\displaystyle
I(\pi_{E}(\operatorname{im}\varphi^{A}))=I(X_{A_{E}})=I_{A_{E}}.$

This ideal may be computed via Proposition 2.1, or as an elimination ideal of
$I_{A}$. Indeed, $I_{A_{E}}$ is obtained from $I_{A}$ by eliminating the
variables $x_{i}$ for $i\in[n]\setminus E$. We obtain the following corollary
of Proposition 2.3 describing the completions to
$\operatorname{im}\varphi^{A}$.

######  Corollary 3.1.

A partial observation $p_{E}\in\mathbb{C}^{E}$ is completable to a point of
the image $\operatorname{im}\varphi^{A}$ if and only if $p_{E}\in X_{A_{E}}$
and $p_{E}$ is $A_{E}$–feasible.

###### Proof.

This follows from the equality
$\operatorname{im}\varphi^{A_{E}}=\pi_{E}(\operatorname{im}\varphi^{A})$. A
partial observation $p_{E}\in\mathbb{C}^{E}$ is completable to the image
$\operatorname{im}\varphi^{A}$ if and only if it lies in the image
$\operatorname{im}\varphi^{A_{E}}$. By Proposition 2.3, this is exactly when
$p_{E}\in X_{A,E}$ and $p_{E}$ is $A_{E}$–feasible. ∎

######  Remark 3.2.

We note that Lemma 1 in [GMS06] is analogous to Proposition 2.3 for the
non–negative real numbers—that a point $p\in\mathbb{R}_{\geq 0}^{n}$ lies in
the image $\varphi^{A}(\mathbb{R}_{\geq 0}^{k})$ exactly when $p\in X_{A}$ and
$p$ is $A$–feasible. Thus, Corollary 3.1 extends to the non–negative real
setting—a partial observation $p_{E}\in\mathbb{R}_{\geq 0}^{E}$ is completable
to a point of the image $\varphi^{A}(\mathbb{R}_{\geq 0}^{k})$ if and only if
$p_{E}\in X_{A,E}$ and $p_{E}$ is $A_{E}$–feasible.

Lemma 2.5 and Corollary 3.1 allow us to determine when a partial observation
$p_{E}\in X_{A_{E}}$ is completable to the toric variety $X_{A}$.

######  Theorem 3.3.

A partial observation $p_{E}\in\mathbb{C}^{E}$ is completable to a point $p\in
X_{A}$ if and only if $p_{E}\in X_{A_{E}}$ and there is a facial set $F$ of
$A$ such that $\operatorname{supp}(p_{E})=F\cap E$.

###### Proof.

If $p_{E}=\pi_{E}(p)\in\pi_{E}(X_{A})$ for some $p\in X_{A}$, then by Lemma
2.5 $\operatorname{supp}(p)$ is a facial set of $A$ and
$\operatorname{supp}(p_{E})=\operatorname{supp}(p)\cap E$.

Conversely, if $p_{E}\in X_{A_{E}}$ and $F$ is a facial set of $A$ such that
$\operatorname{supp}(p_{E})=E\cap F$, then $p_{E}$ is $A_{E\cap F}$–feasible
since $p_{E}$ has non–zero coordinates $(p_{E})_{i}$ for every $i\in E\cap
F=\operatorname{supp}(p_{E})$. By Corollary 3.1, this implies there exists
$\theta\in\mathbb{C}^{k}$ such that the $i$–th coordinates
$(\varphi^{A}(\theta))_{i}=(p_{E})_{i}$ are equal for every $i\in E\cap F$.
Consider the point $\varphi^{A}(\theta)\chi_{F}\in X_{A}$. If $i\in E\cap F$,
then the $i$–th coordinates $(\varphi^{A}(\theta)\chi_{F})_{i}=(p_{E})_{i}$
are equal. Similarly, if $i\in E\setminus F$, then
$(\varphi^{A}(\theta)\chi_{F})_{i}=(p_{E})_{i}=0$. Thus,
$\varphi^{A}(\theta)\chi_{F}\in X_{A}$ is a completion of $p_{E}$. ∎

######  Remark 3.4.

As with the previous results, this extends to the non–negative toric variety—a
partial observation $p_{E}\in\mathbb{R}_{\geq 0}^{E}$ is completable to a
point $p\in X_{A}^{\geq 0}$ if and only if $\operatorname{supp}(p_{E})$ is the
intersection of a facial set of $A$ with $E$. This can be seen by reiterating
the proof above over $\mathbb{R}_{\geq 0}$ or by taking the coordinate–wise
absolute value of any complex completion of $p_{E}\in\mathbb{R}_{\geq 0}^{E}$.

Given a partial observation $p_{E}\in\mathbb{C}^{E}$, Lemma 2.5 and Theorem
3.3 allow us to quickly determine properties of completions to $X_{A}$ by
studying the facial sets of $A$. If $F_{1}$ and $F_{2}$ are facial sets, then
their intersection $F_{1}\cap F_{2}$ is a facial set. In particular, for any
set $E\subseteq[n]$, there is a minimal facial set $F$ containing $E$, which
is the intersection of all facial sets containing $E$.

######  Corollary 3.5.

Let $A\in\mathbb{Z}_{\geq 0}^{k\times n}$ be an integer matrix,
$E\subseteq[n]$ be a subset of the coordinates, $p_{E}\in\mathbb{C}^{E}$ be a
partial observation, and $p\in X_{A}$ be a completion of $p_{E}$. If
$F\subseteq[n]$ is the smallest facial set containing
$\operatorname{supp}(p_{E})$, then $F\subseteq\operatorname{supp}(p)$.

$1$$\bullet$$2$$\bullet$$3$$\bullet$$\bullet$$4$ Figure 1. An example polytope
$P_{A}$. The point corresponding to the 4-th column of $A$ lies in the
relative interior of the polytope.

######  Example 3.6.

Consider an integer matrix $A\in\mathbb{Z}_{>0}^{k\times 4}$ such that the
polytope $P_{A}$ is as in Figure 1. If $E=\\{4\\}$ then the smallest facial
set containing $E$ is $F=\\{1,2,3,4\\}$ so that by Corollary 3.5, any
completion $p\in X_{A}$ has all non–zero coordinates. If
$p_{E}\in\mathbb{C}^{E}$ is non–zero, then $\operatorname{supp}(p_{E})=E\cap
F$ so that there are completions to $X_{A}$ and each has all non–zero
coordinates. If $p_{E}=0$, then any completion has support given by one of the
facial sets $\emptyset$, $\\{1,2\\}$, $\\{1,3\\}$, or $\\{2,3\\}$.

##  4\. Completion to the Log–Linear Model

Let $E\subseteq[n]$ be a subset indexing coordinates of $\mathbb{R}_{\geq
0}^{n}$ and $\pi_{E}:\mathbb{R}_{\geq 0}^{n}\to\mathbb{R}_{\geq 0}^{E}$ be the
corresponding coordinate projection. Given an integer matrix
$A\in\mathbb{Z}_{\geq 0}^{k\times n}$, we consider the completions of a
partial observation $p_{E}\in\mathbb{R}^{E}$ to the log–linear model
$\mathcal{M}_{A}$. Our analysis of the problem relies on our ability to
understand completions to the non–negative toric variety $X_{A}^{\geq 0}$ as
described in the previous section.

We provide a description of the interior and the boundary of the completable
region $\pi_{E}(\mathcal{M}_{A})$, which consists of partial observations
which can be completed to a point in $\mathcal{M}_{A}$: see Theorem 4.10. This
is accomplished by analyzing the branch locus of the projection
$\pi_{E}:\mathcal{M}_{A}^{>0}\to\mathbb{R}^{E}$, which is the locus of points
where the differential $(d\pi_{E})_{p}$ drops rank. For a point
$p\in\mathcal{M}_{A}^{>0}$ that does not lie in the branch locus, the image
$\pi_{E}(p)$ lies in the interior of the completable region
$\pi_{E}(\mathcal{M}_{A})$. Thus, the problem of determining the interior and
the boundary of the completable region rests on understanding the image of the
branch locus and the image of the boundary of the log–linear model
$\partial\mathcal{M}_{A}$.

In addition, we enumerate the completions for a partial observation with
non–zero coordinates lying in the completable region. It will be shown that a
partial observation can have either one or two completions to the log–linear
model $\mathcal{M}_{A}$ depending on the subset $E\subseteq[n]$ chosen and
whether the partial observation lies in the interior or the boundary of the
completable region—see Theorem 4.12 and Theorem 4.15. Our results determine
the number of completions of a partial observation to $\mathcal{M}_{A}$, but
produce no general algorithm for computing these completions.

We work under the mild assumption that our subset $E\subseteq[n]$ satisfies
$|E|=\operatorname{rank}A_{E}=\operatorname{rank}A-1$. The assumption that
$|E|=\operatorname{rank}A_{E}\leq\operatorname{rank}A-1$ guarantees that the
image $\pi_{E}:\mathcal{M}_{A}\to\mathbb{R}^{E}$ is full–dimensional—see
Corollary 4.6. Further, we assume that $|E|=\operatorname{rank}A-1$ so that
one expects finitely–many completions to the log–linear model
$\mathcal{M}_{A}$ for a general partial observation. If
$|E|<\operatorname{rank}A-1$, then any partial observation lying in the
completable region has infinitely many completions to $\mathcal{M}_{A}$.

###  4.1. The Branch Locus of a Coordinate Projection

We study the coordinate projection
$\pi_{E}:\mathcal{M}^{>0}_{A}\to\mathbb{R}^{E}$ and its branch locus as a
means to determine the interior and the boundary of the completable region
$\pi(\mathcal{M}_{A})$. To accomplish this, we compute the tangent spaces of
$X_{A}^{>0}$ and $\mathcal{M}_{A}^{>0}$.

Let $A\in\mathbb{Z}_{\geq 0}^{k\times n}$ have entries $a_{ij}$ for $1\leq
i\leq k$ and $1\leq j\leq n$. By differentiating the monomial map
$\varphi^{A}:\mathbb{R}^{k}_{>0}\to\mathbb{R}^{n}_{>0}$ at
$\theta\in\mathbb{R}^{k}_{>0}$, we obtain a map
$d\varphi_{\theta}^{A}:\mathbb{R}^{k}\to\mathbb{R}^{n}$ defined by

$\displaystyle(d\varphi_{\theta}^{A})_{ij}=a_{ji}\frac{1}{\theta_{j}}\varphi^{A}_{i}(\theta).$

By writing $p=\varphi^{A}(\theta)$, the image of the differential may be
written as

$\displaystyle\operatorname{im}d\varphi^{A}_{\theta}=\\{(p_{1}v_{1},\dotsc,p_{n}v_{n})\in\mathbb{R}^{n}:v\in\operatorname{im}A^{T}\\}.$

Since this image has dimension $\operatorname{rank}A=\dim X_{A}^{>0}$, it
follows that the image $\operatorname{im}d\varphi_{\theta}^{A}$ coincides with
the tangent space of the image $X_{A}^{>0}$. Thus, $X_{A}^{>0}$ is smooth at
each point and the tangent space is given by

$\displaystyle
T_{p}X_{A}^{>0}=\operatorname{im}d\varphi^{A}_{\theta}=\\{(p_{1}v_{1},\dotsc,p_{n}v_{n})\in\mathbb{R}^{n}:v\in\operatorname{im}A^{T}\\}.$

Write $H\subseteq\mathbb{R}^{n}$ for the hyperplane defined by the equation
$\sum_{i}x_{i}=1$ so that $T_{p}H=\\{x\in\mathbb{R}^{n}:\sum_{i}x_{i}=0\\}$.
Since $(1,\dotsc,1)\in\operatorname{im}A^{T}$, it follows that
$(p_{1},\dotsc,p_{n})\in T_{p}X_{A}^{>0}$ so that
$T_{p}X_{A}^{>0}+T_{p}H=\mathbb{R}^{n}$—that is, $X_{A}^{>0}$ intersects $H$
transversally at each point. Thus, we may regard
$\mathcal{M}_{A}=X_{A}^{>0}\cap H$ as a smooth manifold of dimension
$\dim\mathcal{M}_{A}^{>0}=\dim X_{A}^{>0}-1=\operatorname{rank}A-1$. Further,
we write its tangent space as

$\displaystyle
T_{p}\mathcal{M}_{A}^{>0}=\\{(p_{1}v_{1},\dotsc,p_{n}v_{n})\in\mathbb{R}^{n}:v\in\operatorname{im}A^{T},\leavevmode\nobreak\
v^{T}p=0\\}.$

Let $E\subseteq[n]$ index a subset of the coordinates such that
$|E|=\operatorname{rank}A_{E}=\operatorname{rank}A-1$ and let
$\pi_{E}:\mathbb{R}^{n}\to\mathbb{R}^{E}$ denote the corresponding coordinate
projection. As a linear map, we identify the differential $(d\pi_{E})_{p}$ at
any point $p$ with the projection $\pi_{E}$ itself. The following proposition
aids in identifying those points where the differential
$(d\pi_{E}|_{\mathcal{M}_{A}^{>0}})_{p}$ is not an isomorphism.

######  Proposition 4.1.

If $E\subseteq[n]$ is such that
$|E|=\operatorname{rank}A_{E}=\operatorname{rank}A-1$, then
$\dim(\operatorname{im}A^{T}\cap\ker\pi_{E})=1$. That is, every vector in
$\operatorname{im}A^{T}\cap\ker\pi_{E}$ is a scalar multiple of any non–zero
vector $\nu\in\operatorname{im}A^{T}\cap\ker\pi_{E}$.

###### Proof.

The map
$\pi_{E}:(\operatorname{im}A^{T}+\ker\pi_{E})\to\operatorname{im}A_{E}^{T}$
gives an isomorphism of the space
$(\operatorname{im}A^{T}+\ker\pi_{E})/\ker\pi_{E}$ with
$\operatorname{im}A_{E}^{T}$ so that

$\displaystyle\dim(\operatorname{im}A^{T}+\ker\pi_{E})$
$\displaystyle=\dim\operatorname{im}A_{E}^{T}+\dim\ker\pi_{E}$
$\displaystyle=\operatorname{rank}A_{E}+n-|E|$ $\displaystyle=n.$

Thus, we may compute
$\dim(\operatorname{im}A^{T}\cap\ker\pi_{E})=\dim\operatorname{im}A^{T}+\dim\ker\pi_{E}-n=1$.
∎

######  Corollary 4.2.

Let $E\subseteq[n]$ be such that
$|E|=\operatorname{rank}A_{E}=\operatorname{rank}A-1$ and
$\nu\in\operatorname{im}A^{T}\cap\ker\pi_{E}$ be a non–zero vector. For
$p\in\mathcal{M}_{A}^{>0}$, the differential
$(d\pi_{E}|_{\mathcal{M}_{A}^{>0}})_{p}:T_{p}\mathcal{M}_{A}^{>0}\to\mathbb{R}^{E}$
is an isomorphism if and only if $\nu^{T}p\neq 0$.

###### Proof.

Since $\dim T_{p}\mathcal{M}_{A}^{>0}$ and $|E|$ are equal to
$\operatorname{rank}A-1$, the differential is an isomorphism if and only if it
is injective. Recall that

$\displaystyle
T_{p}\mathcal{M}_{A}^{>0}=\\{(p_{1}v_{1},\dotsc,p_{n}v_{n})\in\mathbb{R}^{n}:v\in\operatorname{im}A^{T},\leavevmode\nobreak\
v^{T}p=0\\}.$

As $p\in\mathcal{M}_{A}^{>0}$, a non–zero tangent vector
$(p_{1}v_{1},\dotsc,p_{n}v_{n})\in T_{p}\mathcal{M}_{A}^{>0}$ lies in
$\ker(d\pi_{E}|_{\mathcal{M}_{A}^{>0}})_{p}$ if and only if
$v\in\operatorname{im}A^{T}\cap\ker\pi_{E}$ and $v^{T}p=0$. Equivalently, the
kernel $\ker(d\pi_{E}|_{\mathcal{M}_{A}^{>0}})_{p}$ is non–trivial if and only
if $\nu^{T}p=0$. ∎

We demonstrate that the locus of points $p\in\mathcal{M}_{A}^{>0}$ such that
$\nu^{T}p=0$ is a proper subset of $\mathcal{M}_{A}^{>0}$. Recall that the
algebraic moment map $\mu:\mathcal{M}_{A}\to P_{A}$ is a homeomorphism as
described in Theorem 2.8.

######  Proposition 4.3.

Let $E\subseteq[n]$ be such that
$|E|=\operatorname{rank}A_{E}=\operatorname{rank}A-1$ and let
$\nu\in\operatorname{im}A^{T}\cap\ker\pi_{E}$ be a non–zero vector. A point
$p\in\mathcal{M}_{A}$ satisfies $\nu^{T}p=0$ if and only if
$\mu(p)\in\operatorname{im}A_{E}\cap P_{A}$.

###### Proof.

Note that $q\in\operatorname{im}A_{E}$ if and only if $v^{T}q=0$ for all
$v\in\ker A_{E}^{T}$—that is, $q$ lies in the span of the columns of $A$
indexed by $E$ exactly when every hyperplane equation which vanishes on the
columns of $A$ indexed by $E$ also vanish on $q$. Thus, for
$p\in\mathcal{M}_{A}$, one has $\mu(p)\in\operatorname{im}A_{E}\cap P_{A}$ if
and only if $v^{T}\mu(p)=(A^{T}v)^{T}p=0$ for all $v\in\ker A_{E}^{T}$.
However, the equality $A^{T}(\ker
A_{E}^{T})=\operatorname{im}A^{T}\cap\ker\pi_{E}$ holds so that the result
follows. ∎

The intersection $\operatorname{im}A_{E}\cap P_{A}$ is the set of points in
$P_{A}$ spanned by the columns of $A$ indexed by $E$. Since
$\operatorname{rank}A_{E}=\operatorname{rank}A-1$, this is a proper subset of
$P_{A}$ and the locus of points $p\in\mathcal{M}_{A}$ such that $\nu^{T}p=0$
is a proper subset of $\mathcal{M}_{A}$. Thus, the generic rank of the
projection $\pi_{E}|_{\mathcal{M}_{A}^{>0}}$ is
$\dim\mathcal{M}_{A}^{>0}=|E|=\operatorname{rank}A-1$ and this rank drops
exactly on the of points $\mathcal{M}_{A}$ lying on the hyperplane defined by
$\nu^{T}p=0$. This allows us to give the following definition of the branch
locus.

######  Definition 4.4.

If $|E|=\operatorname{rank}A_{E}=\operatorname{rank}A-1$ and
$\nu\in\operatorname{im}A^{T}\cap\ker\pi_{E}$ is any non–zero vector, then the
branch locus of the projection $\pi_{E}|_{\mathcal{M}_{A}}$ is the set of
points

$\displaystyle B_{A,E}=\\{p\in\mathcal{M}_{A}^{>0}:\nu^{T}p=0\\}.$

We note that with this terminology, Proposition 4.3 states that the image of
the algebraic moment map applied to the branch locus $B_{A,E}$ is given by
$\mu(B_{A,E})=\operatorname{im}A_{E}\cap P_{A}$. That is, $\mu(B_{A,E})$ is
the points of $P_{A}$ that are spanned by the columns of $A$ indexed by $E$.
In addition, the equality $\operatorname{im}A^{T}\cap\ker\pi_{E}=A^{T}(\ker
A_{E}^{T})$ gives an effective method of computing a vector $\nu$. This is
illustrated in Example 4.5.

######  Example 4.5.

Let

$\displaystyle A=\begin{pmatrix}4&0&0&2&1\\\ 0&4&0&1&2\\\
0&0&4&1&1\end{pmatrix}\in\mathbb{Z}_{\geq 0}^{3\times 5}$

and $E=\\{4,5\\}$. The polytope $P_{A}$ and the image $\mu(B_{A,E})$ are
illustrated in Figure 2. Since
$|E|=\operatorname{rank}A_{E}=\operatorname{rank}A-1=2$, the result of
Proposition 4.3 applies. The kernel $\ker A_{E}^{T}$ is generated by the
vector $\omega=(1,1,-3)$, so we may let
$\nu=\frac{1}{4}A^{T}\omega=(1,1,-3,0,0)\in A^{T}(\ker A_{E}^{T})$. Thus, the
branch locus of the projection $\pi_{E}:\mathcal{M}_{A}^{>0}\to\mathbb{R}^{E}$
is given by the hyperplane section

$\displaystyle B_{A,E}=\\{p\in\mathcal{M}_{A}^{>0}:p_{1}+p_{2}-3p_{3}=0\\}.$

$\mu(B_{A,E})$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$1$$2$$3$$4$$5$
Figure 2. The polytope $P_{A}$ and the image $\mu(B_{A,E})$ for Example 4.5.

We end by showing that a point $p\in\mathcal{M}_{A}^{>0}\setminus B_{A,E}$ not
in the branch locus maps to the interior of the completable region.

######  Corollary 4.6.

If $|E|=\operatorname{rank}A_{E}=\operatorname{rank}A-1$ and
$p\in\mathcal{M}_{A}^{>0}\setminus B_{A,E}$, then there is an open subset
$U\subseteq\mathbb{R}^{E}$ such that $\pi_{E}(p)\in U$ and
$U\subseteq\pi_{E}(\mathcal{M}_{A})$. In particular, the completable image is
full–dimensional and
$\pi_{E}(p)\in\operatorname{int}(\pi_{E}(\mathcal{M}_{A}))$ lies in the
interior of the completable region.

###### Proof.

For any point $p\in\mathcal{M}_{A}^{>0}\setminus B_{A,E}$, the differential
$(d\pi_{E}|_{\mathcal{M}_{A}^{>0}})_{p}:T_{p}\mathcal{M}_{A}^{>0}\to\mathbb{R}^{E}$
is an isomorphism. By the implicit function theorem, $\pi_{E}$ restricts to a
diffeomorphism of an open neighborhood of $p\in\mathcal{M}_{A}^{>0}$ to an
open neighborhood of $\pi_{E}(p)$. ∎

###  4.2. The Interior and Boundary of the Completable Region

Corollary 4.6 shows that for $p\in\mathcal{M}_{A}^{>0}\setminus B_{A,E}$, the
image $\pi_{E}(p)$ lies in the interior of the completable region
$\pi_{E}(\mathcal{M}_{A})$. We will show that the boundary of the completable
region consists of the image of the boundary of the model
$\pi_{E}(\partial\mathcal{M}_{A})$ and the image of the branch locus
$\pi_{E}(B_{A,E})$, which completely classifies the interior and the boundary
of the completable region. We accomplish this by better understanding the
completions of a partial observation to the non–negative toric variety
$X_{A}^{\geq 0}$.

######  Proposition 4.7.

Let $E\subseteq[n]$ be such that
$|E|=\operatorname{rank}A_{E}=\operatorname{rank}A-1$ and let
$\nu\in\operatorname{im}A^{T}\cap\ker\pi_{E}$ be a non–zero vector. If
$p_{E}\in\mathbb{R}_{>0}^{E}$ is a partial observation with non–zero
coordinates, then for any completions $p,q\in X_{A}^{\geq 0}$ of $p_{E}$,
there exists $\alpha\in\mathbb{R}$ such that

$\displaystyle p_{i}=q_{i}e^{\alpha\nu_{i}}\leavevmode\nobreak\
\leavevmode\nobreak\ \text{ for all }\leavevmode\nobreak\
i\in\operatorname{supp}(p)\cap\operatorname{supp}(q).$

###### Proof.

We note that for any point $p\in X_{A}$, by projecting the coordinates indexed
by $\operatorname{supp}(p)$, there is a completion to
$\varphi^{A}(\mathbb{R}_{>0}^{k})$ which agrees with $p$ on its support. Thus,
we may write $p=\chi_{\operatorname{supp}(p)}\varphi^{A}(\theta)$ for some
$\theta\in\mathbb{R}_{>0}^{k}$. Thus, we write
$p=\chi_{F_{1}}\varphi^{A}(\theta_{1})$ and
$q=\chi_{F_{2}}\varphi^{A}(\theta_{2})$ where $F_{1}=\operatorname{supp}(p)$
and $F_{2}=\operatorname{supp}(q)$ are facial sets that contain $E$, and
$\theta_{1},\theta_{2}\in\mathbb{R}_{>0}^{k}$. Then by taking the
coordinate–wise logarithm, we have

$\displaystyle
0=\log(p_{E})-\log(q_{E})=A_{E}^{T}(\log(\theta_{1})-\log(\theta_{2})).$

Therefore $\log(\theta_{1})-\log(\theta_{2})\in\ker A_{E}^{T}$ so that
$\log(p)-\log(q)=\alpha\nu\in A^{T}(\ker A_{E}^{T})$ for some
$\alpha\in\mathbb{R}$. Exponentiating, we have that for
$\varphi^{A}(\theta_{1})=\varphi^{A}(\theta_{2})e^{\alpha\nu}$. Then for $i\in
F_{1}\cap F_{2}$, we have that $p_{i}=q_{i}e^{\alpha\nu_{i}}$. ∎

We now leverage this proposition to show that the boundary of the completable
region $\partial\pi_{E}(\mathcal{M}_{A})$ is given by the image of the
boundary of the model $\pi_{E}(\partial\mathcal{M}_{A})$ and the image of the
branch locus $\pi_{E}(B_{A,E})$. Equivalently, we show no point of the
boundary $\partial\mathcal{M}_{A}$ or the branch locus $B_{A,E}$ map into the
interior $\operatorname{int}(\pi_{E}(\mathcal{M}_{A}))$. We start by showing a
point $p\in\partial\mathcal{M}_{A}$ is such that $\pi_{E}(p)$ has some
coordinate equal to zero or the coordinates of $\pi_{E}(p)$ cannot be
increased by any amount and remain completable to the log–linear model
$\mathcal{M}_{A}$.

######  Lemma 4.8.

If $E\subseteq[n]$ is such that
$|E|=\operatorname{rank}A_{E}=\operatorname{rank}A-1$, then the boundary of
the model $\partial\mathcal{M}_{A}$ maps by $\pi_{E}$ into the boundary of the
completable region $\partial\pi_{E}(\mathcal{M}_{A})$. That is, there is an
inclusion
$\pi_{E}(\partial\mathcal{M}_{A})\subseteq\partial\pi_{E}(\mathcal{M}_{A})$.

###### Proof.

Let $p\in\mathcal{M}_{A}$ and $p_{E}=\pi_{E}(p)$. If
$p\in\partial\mathcal{M}_{A}$, then some coordinate of $p$ is equal to zero
and $\operatorname{supp}(p)\subseteq[n]$ is a proper facial set. There are two
cases to consider. If $E$ is not contained in $\operatorname{supp}(p)$, then
$p_{E}\in\mathbb{R}^{E}$ contains some zero coordinate and any open ball
around $p_{E}$ contains points with negative coordinates. Those points with
negative coordinates have not completion to $\mathcal{M}_{A}$ so that
$p_{E}\in\partial\pi_{E}(\mathcal{M}_{A})$.

Assume that $E\subseteq\operatorname{supp}(p)$. Since
$\operatorname{rank}A_{E}=\operatorname{rank}A-1$ and $\operatorname{supp}(p)$
is a proper facial set, it follows that $\operatorname{supp}(p)$ is a facet
and $\operatorname{supp}(p)$ is the smallest facial set containing $E$.
Without loss of generality, we may let $\omega\in\ker A_{E}^{T}$ be an inner
normal vector of the facet $\operatorname{supp}(p)$ so that $\nu=A^{T}\omega$
satisfies $\nu_{i}=0$ for all $i\in\operatorname{supp}(p)$ and $\nu_{i}>0$ for
$i\in[n]\setminus\operatorname{supp}(p)$.

Let $\epsilon>0$ and $q_{E}=(1+\epsilon)p_{E}\in\mathbb{R}^{E}$. Then
$(1+\epsilon)p\in X_{A}^{\geq 0}$ is a completion of $q_{E}$ and by
Proposition 4.7, any other completion $q\in X_{A}^{\geq 0}$ of $q_{E}$
satisfies

$\displaystyle q_{i}=(1+\epsilon)p_{i}e^{\alpha\nu_{i}}$

for all $i\in\operatorname{supp}(p)\cap\operatorname{supp}(q)$. Since
$E\subseteq\operatorname{supp}(q)$ and $\operatorname{supp}(p)$ is the
smallest facial set containing $E$, we have that
$\operatorname{supp}(p)\subseteq\operatorname{supp}(q)$. Further, since
$\nu_{i}=0$ for all $i\in\operatorname{supp}(p)$ and $q_{i}=(1+\epsilon)p_{i}$
for $i\in\operatorname{supp}(p)$. We compute

$\displaystyle\sum_{i}q_{i}\geq\sum_{i\in\operatorname{supp}(p)}q_{i}=(1+\epsilon)\sum_{i\in\operatorname{supp}(p)}p_{i}=1+\epsilon>1.$

Any open set around $p_{E}$ then contains points which are not completable to
$\mathcal{M}_{A}$ so that $p_{E}\in\partial\pi_{E}(\mathcal{M}_{A})$. ∎

Lemma 4.8 extends to the branch locus $B_{A,E}$ as well. We show that if $p\in
B_{A,E}$, then the coordinates of $\pi_{E}(p)$ cannot be increased while
remaining completable to the log–linear model $\mathcal{M}_{A}$. Thus, the
image $\pi_{E}(B_{A,E})$ is contained in the boundary of the completable
region as well.

######  Lemma 4.9.

If $E\subseteq[n]$ is such that
$|E|=\operatorname{rank}A_{E}=\operatorname{rank}A-1$, then the branch locus
$B_{A,E}$ maps by $\pi_{E}$ into the boundary of the completable region
$\partial\pi_{E}(\mathcal{M}_{A})$. That is, there is an inclusion
$\pi_{E}(B_{A,E})\subseteq\partial\pi_{E}(\mathcal{M}_{A})$.

###### Proof.

We may assume $E$ is not contained in a proper facial set, since otherwise
$B_{A,E}$ is empty as can be seen by Proposition 4.3. Thus, by Corollary 3.5,
if $p_{E}\in\mathbb{R}^{E}$ has non–zero coordinates, any completion $p\in
X_{A}^{\geq 0}$ has non–zero coordinates. Let $p\in B_{A,E}$ and
$p_{E}=\pi_{E}(p)$. If $\epsilon>0$ and $q_{E}=(1+\epsilon)p_{E}$ as above,
then $(1+\epsilon)p\in X_{A}^{\geq 0}$ is a completion. For any other
completion $q\in X_{A}^{\geq 0}$, there exists $\alpha\in\mathbb{R}$ such that
$q_{i}=(1+\epsilon)p_{i}e^{\alpha\nu_{i}}$ for all $i\in[n]$ since $p$ and $q$
have all non–zero coordinates. Since $\nu^{T}p=0$, one computes

$\displaystyle\sum_{i}q_{i}=(1+\epsilon)\sum_{i}p_{i}e^{\alpha\nu_{i}}\geq(1+\epsilon)\sum_{i}p_{i}(1+\alpha\nu_{i})=1+\epsilon>1.$

Again one finds that any open set around $p_{E}$ contains points which are not
completable to $\mathcal{M}_{A}$ so that
$p_{E}\in\partial\pi_{E}(\mathcal{M}_{A})$. ∎

We combine Lemma 4.8 and Lemma 4.9 to describe the boundary and the interior
of the completable region.

######  Theorem 4.10.

If $E\subseteq[n]$ is such that
$|E|=\operatorname{rank}A_{E}=\operatorname{rank}A-1$, then the boundary of
the completable region is equal to the image by $\pi_{E}$ of the union of the
boundary of the model $\partial\mathcal{M}_{A}$ and the branch locus
$B_{A,E}$. Precisely,

$\displaystyle\partial\pi_{E}(\mathcal{M}_{A})=\pi_{E}(\partial\mathcal{M}_{A})\cup\pi_{E}(B_{A,E}).$

Equivalently, the interior of the completable region is equal to the image

$\displaystyle\operatorname{int}(\pi_{E}(\mathcal{M}_{A}))=\pi_{E}(\mathcal{M}_{A}^{>0}\setminus
B_{A,E}).$

###### Proof.

For $p\in\mathcal{M}_{A}^{>0}\setminus B_{A,E}$, the differential
$(d\pi_{E})_{p}$ is an isomorphism so that
$\pi(p)\in\operatorname{int}(\pi(\mathcal{M}_{A}))$. By taking the relative
complement with $\pi_{E}(\mathcal{M}_{A})$, the inclusion
$\partial\pi_{E}(\mathcal{M}_{A})\subseteq\pi_{E}(\partial\mathcal{M}_{A})\cup\pi_{E}(B_{A,E})$
follows. The reverse inclusion is an immediate consequence of Lemma 4.8 and
Lemma 4.9. ∎

We illustrate Theorem 4.10 in Example 4.11.

######  Example 4.11.

Let

$\displaystyle A=\begin{pmatrix}2&1&1&0\\\ 0&1&0&1\\\
0&0&1&1\end{pmatrix}\in\mathbb{Z}_{\geq 0}^{3\times 4}$

and $E=\\{1,4\\}$. The polytope $P_{A}$, the image $\mu(B_{A,E})$, and the
completable region $\pi_{E}(\mathcal{M}_{A})$ are illustrated in Figure 3.
Using coordinates $x,y,z,w$ for $\mathbb{R}^{4}$, the log–linear model is
given by

$\displaystyle\mathcal{M}_{A}=\\{(x,y,z,w)\in\mathbb{R}_{\geq 0}^{4}:xw-
yz=x+y+z+w-1=0\\}.$

As $(0,1,-1)\in\ker A_{E}^{T}$, we may take $\nu=(0,1,-1,0)$ so that

$\displaystyle B_{A,E}=\\{(x,y,z,w)\in\mathcal{M}_{A}^{>0}:y-z=0\\}.$

As the subset $E$ is not contained in a proper facial set, the boundary
$\partial\mathcal{M}_{A}$, of points where some coordinate is equal to zero,
maps to the coordinate axes of $\mathbb{R}_{\geq 0}^{E}$. Contrary to this,
the branch locus $B_{A,E}$ maps to the curved boundary of Figure 3. The
defining equation for this this curve can be obtained via elimination. Indeed,
the defining ideal of the branch locus is the prime ideal

$\displaystyle I(B_{A,E})=\langle xw-yz,x+y+z+w-1,y-z\rangle.$

Using Macaulay2 [GS] to eliminate the variables $y$ and $z$, we find that the
eliminant of $I(B_{A,E})$ is generated by the single polynomial

$\displaystyle f(x,w)=x^{2}-2xw-w^{2}-2x-2w+1.$

Thus, $f(x,w)=0$ is the defining equation of the projection
$\pi_{E}(B_{A,E})$.

We note that the image $\pi_{E}(B_{A,E})$ is a semialgebraic set and the zero
set $\\{(x,w)\in\mathbb{R}^{2}:f(x,w)=0\\}$ is its Zariski closure. In
general, it is difficult to obtain a semialgebraic description of the image
$\pi_{E}(B_{A,E})$ or of the completable region $\pi_{E}(\mathcal{M}_{A})$.

$\mu(B_{A,E})$$\bullet$$\bullet$$\bullet$$\bullet$$1$$2$$3$$4$

Figure 3. (Left) The polytope $P_{A}$ and image $\mu(B_{A,E})$ for Example
4.11
(Right) The completable region $\pi_{E}(\mathcal{M}_{A})$ for Example 4.11

###  4.3. Enumerating Completions to the Log–Linear Model

Given a matrix $A\in\mathbb{Z}_{\geq 0}^{k\times n}$ and a subset
$E\subseteq[n]$ such that
$|E|=\operatorname{rank}A_{E}=\operatorname{rank}A-1$, we discuss the possible
number of completions of a partial observation with non–zero coordinates in
the completable region $p_{E}\in\pi_{E}(\mathcal{M}_{A})$ to the log–linear
model $\mathcal{M}_{A}$. By elementary methods, we conclude that such a
partial observation has either 0, 1, or 2 completions to $\mathcal{M}_{A}$
depending on whether the subset $E\subseteq[n]$ lies in a proper facial set
and whether $p_{E}$ lies in the boundary or the interior of the completable
region.

We first consider the case that a partial observation with non–zero
coordinates lies in the boundary of the completable region
$p_{E}\in\partial\pi_{E}(\mathcal{M}_{A})$.

######  Theorem 4.12.

Let $E\subseteq[n]$ be such that
$|E|=\operatorname{rank}A_{E}=\operatorname{rank}A-1$. If
$p_{E}\in\partial\pi_{E}(\mathcal{M}_{A})$ is a partial observation with
non–zero coordinates lying in the boundary of the completable region, then
$p_{E}$ has a unique completion to the log–linear model $\mathcal{M}_{A}$.

  1. 1.

If $E$ is contained in a proper facial set, then this completion lies in the
boundary of the completable region $\partial\mathcal{M}_{A}$.

  2. 2.

If $E$ is not contained in a proper facial set, then this completion lies in
the branch locus $B_{A,E}$.

###### Proof.

Let $p_{E}\in\partial\pi_{E}(\mathcal{M}_{A})$ be a partial observation with
non–zero coordinates in the boundary of the completable region. By Theorem
4.10, we may express the boundary of the completable region as

$\displaystyle\partial\pi_{E}(\mathcal{M}_{A})=\pi_{E}(\partial\mathcal{M}_{A})\cup\pi_{E}(B_{A,E}).$

If $E$ is contained in a proper facial set, then $B_{A,E}$ is empty by
Proposition 4.3 so that $p_{E}$ has a completion
$p\in\partial\mathcal{M}_{A}$. Similarly, if $E$ is not contained in a proper
facial set, then any completion of $p_{E}$ has all non–zero coordinates so
that $p_{E}$ necessarily has a completion $p\in B_{A,E}$. We separate the
proof into these cases.

If $E$ is contained in a proper facial set, then $p_{E}$ has a completion
$p\in\partial\mathcal{M}_{A}$. Similar to Lemma 4.8, since
$\operatorname{rank}A_{E}=\operatorname{rank}A-1$ and $\operatorname{supp}(p)$
is a proper facial set, it follows that $\operatorname{supp}(p)$ is a facet
and the smallest face containing $E$. We may let $\omega\in\ker A_{E}^{T}$ be
an inner normal vector of the facial set $\operatorname{supp}(p)$ so that
$\nu=A^{T}\omega$ satisfies $\nu_{i}=0$ for $i\in\operatorname{supp}(p)$ and
$\nu_{i}>0$ for $i\in[n]\setminus\operatorname{supp}(p)$.

If $q\in\mathcal{M}_{A}$ is any other completion of $p_{E}$, then by
Proposition 4.7 there exists $\alpha\in\mathbb{R}$ such that

$\displaystyle q_{i}=p_{i}e^{\alpha\nu_{i}}$

for $i\in\operatorname{supp}(p)\cap\operatorname{supp}(q)$. Since
$E\subseteq\operatorname{supp}(q)$ and $\operatorname{supp}(p)$ is the
smallest facial set containing $E$, we have
$\operatorname{supp}(p)\subseteq\operatorname{supp}(q)$. Further, since
$\nu_{i}=0$ for $i\in\operatorname{supp}(p)$, we have that $q_{i}=p_{i}$ for
$i\in\operatorname{supp}(p)$. Since $p,q\in\mathcal{M}_{A}$, we see

$\displaystyle
0=\sum_{i\in[n]}(q_{i}-p_{i})=\sum_{i\in[n]\setminus\operatorname{supp}(p)}q_{i}.$

Since $q_{i}\geq 0$ for each $i$, this implies that $q_{i}=0$ for
$i\in[n]\setminus\operatorname{supp}(p)$ so that $q=p$.

If $E$ is not contained in a proper facial set, then $p_{E}$ has a completion
$p\in B_{A,E}$. If $q\in\mathcal{M}_{A}$ is any other completion, then $q$
also has non–zero coordinates. Let
$\nu\in\operatorname{im}A^{T}\cap\ker\pi_{E}$ be a non–zero vector. By
Proposition 4.7, there exists $\alpha\in\mathbb{R}$ such that

$\displaystyle q_{i}=p_{i}e^{\alpha\nu_{i}}$

for all $i\in[n]$. Observe that

$\displaystyle\sum_{i}p_{i}(e^{\alpha\nu_{i}}-\alpha\nu_{i}-1)=\sum_{i}(q_{i}-p_{i})-\alpha\nu^{T}p=0.$

As each term of this summand is non–negative, this implies each summand is
equal to zero. Since $p$ has non–zero coordinates and $\nu$ is a non–zero
vector, there is some index $i$ such that $p_{i}\neq 0$ and $\nu_{i}\neq 0$,
but $p_{i}(e^{\alpha\nu_{i}}-\alpha\nu_{i}-1)=0$. Therefore it must be that
$\alpha=0$ and $q=p$. ∎

We turn our attention now to partial observations lying in the interior of the
completable region $p_{E}\in\operatorname{int}(\pi_{E}(\mathcal{M}_{A}))$.
Completions in this case may not be unique, however it can be seen that there
are at most two.

######  Proposition 4.13.

Let $E\subseteq[n]$ be such that
$|E|=\operatorname{rank}A_{E}=\operatorname{rank}A-1$ and let
$\nu\in\operatorname{im}A^{T}\cap\ker\pi_{E}$ be a non–zero vector. If
$p_{E}\in\operatorname{int}(\pi_{E}(\mathcal{M}_{A}))$ is a partial
observation in the interior of the completable region, then any two distinct
completions $p,q\in\mathcal{M}_{A}$ are such that $\nu^{T}p$ and $\nu^{T}q$
are non–zero and have opposite signs.

###### Proof.

By Theorem 4.10, $p_{E}$ has a completion $p\in\mathcal{M}_{A}^{>0}\setminus
B_{A,E}$ and any other completion also lies in $\mathcal{M}_{A}^{>0}\setminus
B_{A,E}$. By Proposition 4.7, if $p,q\in\mathcal{M}_{A}^{>0}\setminus B_{A,E}$
are any two completions, there exists $\alpha\in\mathbb{R}$ such that

$\displaystyle q_{i}=p_{i}e^{\alpha\nu_{i}}$

for all $i\in[n]$. Without loss of generality by interchanging $p$ and $q$, we
may assume that $\alpha>0$. Observe

$\displaystyle
0=\sum_{i}(q_{i}-p_{i})=\sum_{i}p_{i}(e^{\alpha\nu_{i}}-1)\geq\alpha\sum_{i}\nu_{i}p_{i}=\alpha\nu^{T}p.$

Since $\alpha>0$ and $\nu^{T}p\neq 0$, this implies that $\nu^{T}p<0$. By the
same process reversing the roles of $p$ and $q$ and by replacing $\alpha$ by
$-\alpha$, one finds that $\nu^{T}q>0$. ∎

######  Corollary 4.14.

If $E\subseteq[n]$ is such that
$|E|=\operatorname{rank}A_{E}=\operatorname{rank}A-1$ and
$p_{E}\in\operatorname{int}(\pi_{E}(\mathcal{M}_{A}))$ is a partial
observation in the interior of the completable region, then $p_{E}$ has at
most two completions to $\mathcal{M}_{A}$.

Contrasting the case that a partial observation $p_{E}$ lies in the boundary
of the completable region, the number of completions to $\mathcal{M}_{A}$ for
a partial observation in the interior of the completable region may vary.
Indeed, the number of completions is depends on whether the set
$E\subseteq[n]$ is contained in a proper facial set.

######  Theorem 4.15.

Let $E\subseteq[n]$ be such that
$|E|=\operatorname{rank}A_{E}=\operatorname{rank}A-1$ and let
$p_{E}\in\operatorname{int}(\pi_{E}(\mathcal{M}_{A}))$ be a partial
observation lying in the interior of the completable region.

  1. 1.

If $E$ is contained in a proper facial set, then $p_{E}$ has a unique
completion to $\mathcal{M}_{A}$.

  2. 2.

If $E$ is not contained in a proper facial set, then $p_{E}$ has two
completions to $\mathcal{M}_{A}$.

###### Proof.

1. If $E\subseteq[n]$ is contained in a proper facial set $F$, we may let $\omega\in\ker A_{E}^{T}$ be an inner normal vector for $F$. Then $\nu=A^{T}\omega$ is such that $\nu_{i}=0$ for $i\in F$ and $\nu_{i}>0$ for $i\in[n]\setminus F$. Thus, $\nu^{T}p\geq 0$ for all $p\in\mathcal{M}_{A}$. From Proposition 4.13, it follows that $p_{E}$ must have a unique completion to $\mathcal{M}_{A}$.

2. Assume $E\subseteq[n]$ is not contained in a proper facial set. If $p_{E}\in\operatorname{int}(\pi_{E}(\mathcal{M}_{A}))$ is a partial observation with non–zero coordinates in the interior of the completable region, then by Theorem 4.10, $p_{E}$ has a completion $p\in\mathcal{M}_{A}^{>0}\setminus B_{A,E}$. By Corollary 3.5 and Proposition 4.7, any completion $q\in X_{A}^{\geq 0}$ must have all non–zero coordinates and there must exist $\alpha\in\mathbb{R}$ satisfying

$\displaystyle q_{i}=p_{i}e^{\alpha\nu_{i}}$

for all $i\in[n]$. Setting $x=e^{\alpha}$, the completion $q\in X_{A}^{\geq
0}$ lies in the log–linear model $\mathcal{M}_{A}$ exactly when $x$ is a root
of the (Laurent) polynomial

$\displaystyle f(x)=\sum_{i}p_{i}x^{\nu_{i}}-1.$

Conversely, any positive root of this polynomial yields a completion of
$p_{E}$ lying in the log–linear model $\mathcal{M}_{A}$. From Corollary 4.14,
the polynomial $f$ has at most two positive roots. We use continuity arguments
to show that $f$ always has two positive roots.

Note that since $E$ is not contained in a proper facial set, the vector $\nu$
must have positive and negative coordinates corresponding to terms of $f$ with
positive and negative exponents. As these terms of $f$ have positive
coefficients, $f(x)$ can then be made arbitrarily large for $x>1$ sufficiently
large and for $0<x<1$ sufficiently small. Note that $x=1$ is a root of $f$ and
$f^{\prime}(1)=\nu^{T}p$. Thus, if $\nu^{T}p>0$, then for $0<x<1$ sufficiently
close to $x=1$, $f(x)$ is negative. Thus $f(x)$ has a root in the open
interval $(0,1)$. Similarly, if $\nu^{T}p<0$, then for $x>1$ sufficiently
close to $x=1$, $f(x)$ is negative and $f(x)$ has a root in the open interval
$(1,\infty)$. Thus, $f$ always has two positive roots yielding two completions
of $p_{E}$. ∎

Example 4.16 demonstrates how the proof of Theorem 4.15 may be used to recover
all completions of a partial observation
$p_{E}\in\operatorname{int}(\pi_{E}(\mathcal{M}_{A}))$ from a single
completion.

######  Example 4.16.

As in Example 4.11, let

$\displaystyle A=\begin{pmatrix}2&1&1&0\\\ 0&1&0&1\\\
0&0&1&1\end{pmatrix}\in\mathbb{Z}_{\geq 0}^{3\times 4}$

and $E=\\{1,4\\}$. Recall that the log–linear model is given by

$\displaystyle\mathcal{M}_{A}=\\{(x,y,z,w)\in\mathbb{R}_{\geq 0}^{4}:xw-
yz=x+y+z+w-1=0\\},$

and the branch locus is the hyperplane section of $\mathcal{M}_{A}^{>0}$
defined by

$\displaystyle B_{A,E}=\\{(x,y,z,w)\in\mathcal{M}_{A}^{>0}:y-z=0\\}.$

Consider the partial observation $(\frac{1}{6},\frac{1}{3})\in\mathbb{R}_{\geq
0}^{E}$ and a completion
$p=(\frac{1}{6},\frac{1}{3},\frac{1}{6},\frac{1}{3})\in\mathcal{M}_{A}^{>0}\setminus
B_{A,E}$. Since $\nu^{T}p=\frac{1}{6}>0$, there is another completion
$q\in\mathbb{M}_{A}^{>0}$ such that $\nu^{T}q<0$. This completion can be
obtained by computing positive roots of the Laurent polynomial

$\displaystyle
f(x)=\sum_{i}p_{i}x^{\nu_{i}}-1=\frac{1}{3}x-\frac{1}{2}+\frac{1}{6}x^{-1}.$

One finds that $x=\frac{1}{2}$ is a root of $f(x)$ so that

$\displaystyle
q=p\left(\frac{1}{2}\right)^{(0,1,-1,0)}=\left(\frac{1}{6},\frac{1}{6},\frac{1}{3},\frac{1}{3}\right)\in\mathcal{M}_{A}^{>0}\setminus
B_{A,E}$

is the other completion. Theorem 4.15 implies that these are the only
completions of the partial observation $p_{E}$ to the log–linear model
$\mathcal{M}_{A}$.

##  5\. Describing the Completable Region

Given a subset $E\subseteq[n]$ and an integer matrix $A\in\mathbb{Z}_{\geq
0}^{k\times n}$, the completable region $\pi_{E}(\mathcal{M}_{A})$ is a
full–dimensional semialgebraic set—it is defined by polynomial inequalities. A
semialgebraic description of the completable region $\pi_{E}(\mathcal{M}_{A})$
is such a description of the completable region by polynomial inequalities.
Obtaining a semialgebraic description of the completable region is difficult
in general. However, in this section we will provide examples where obtaining
the complete semialgebraic description of the completable region is possible
by elementary methods. From Theorem 4.10, the algebraic boundary of the
completable region $\pi_{E}(\mathcal{M}_{A})$ is the union of the Zariski
closure of the image of the boundary $\pi_{E}(\partial\mathcal{M}_{A})$ and
the Zariski closure of the image of the branch locus $\pi_{E}(B_{A,E})$. In
both cases, the defining ideal can be computed explicitly via elimination as
long as the defining ideal of the boundary $\partial\mathcal{M}_{A}$ and the
defining ideal of the branch locus $B_{A,E}$ are known. But first we consider
the simpler problem of computing defining equations for the boundary of the
completable region as in Example 4.11.

######  Definition 5.1.

The algebraic boundary of the completable region $\pi_{E}(\mathcal{M}_{A})$ is
the Zariski closure of the boundary $\partial\pi_{E}(\mathcal{M}_{A})$.

The defining ideal of the boundary $\partial\mathcal{M}_{A}$ is generated by
the product of the coordinates $\prod_{i}x_{i}$, the hyperplane
$\sum_{i}x_{i}-1$, and $I_{A}$. However, the defining ideal of $B_{A,E}$ my be
difficult to obtain. For instance, given
$\nu\in\operatorname{im}A^{T}\cap\ker\pi_{E}$, the hyperplane section defined
by $\nu^{T}p=0$ may intersect the Zariski closure of the log–linear model
$\mathcal{M}_{A}$ in more than one component. However, from Proposition 4.3,
at most one of these components intersects the model $\mathcal{M}_{A}$.
Techniques from real algebraic geometry such as the Positivestellensatz and
its variants produce methods of choosing this component in general. See
[LPR20, GHMM22] for more information on these techniques and their use in
applications.

We provide pseudo–code for computing the defining ideal of the algebraic
boundary. We note the reliance on several methods which we consider as
black–boxes: one for computing the toric ideal $I_{A}$, one for producing the
minimal primes of an ideal, one for determining whether an ideal has a
positive zero, and one for computing elimination ideals.

######  Pseudo–Code (Defining Ideal of the Algebraic Boundary).

Input |  $A$: An integer matrix in $\mathbb{Z}_{\geq 0}^{k\times n}$
---|---
|  $E$: A subset such that
$|E|=\operatorname{rank}A_{E}=\operatorname{rank}A-1$
Output |  $I$: The defining ideal of the algebraic boundary.

  1. 1.

Find a non–zero vector $\nu\in A^{T}(\ker A_{E}^{T})$.

  2. 2.

Compute the minimal primes of the ideal
$J=I_{A}+\langle\sum_{i}x_{i}-1,\nu^{T}x\rangle$.

  3. 3.

Compute $I(B_{A,E})$ as the minimal prime of $J$ whose corresponding variety
intersects the log–linear model $\mathcal{M}_{A}$.

  4. 4.

Set $I_{1}$ as the ideal obtained by eliminating the variables $x_{i}$ for
$i\in[n]\setminus E$ from the defining ideal of the branch locus $I(B_{A,E})$.

  5. 5.

Compute $I(\partial\mathcal{M}_{A})$ as the ideal
$I_{A}+\langle\sum_{i}x_{i}-1,\prod_{i}x_{i}\rangle$.

  6. 6.

Set $I_{2}$ as the ideal obtained by eliminating the variables $x_{i}$ for
$i\in[n]\setminus E$ from the defining ideal of the boundary of the model
$I(\partial\mathcal{M}_{A})$.

  7. 7.

Return $I$ as the radical of the ideal $I_{1}I_{2}$.

We note that in general, inequalities obtained from the defining equations of
the algebraic boundary do not give a semialgebraic description of the
completable region. This is demonstrated in Example 5.2.

######  Example 5.2.

Let

$A=\begin{pmatrix}3&4&0&3&2\\\ 0&1&2&1&1\\\
2&0&3&1&2\end{pmatrix}\in\mathbb{Z}_{\geq 0}^{3\times 5}$

and $E=\\{4,5\\}$. We use coordinates $x$, $y$, $z$, $u$, $v$ for
$\mathbb{R}_{\geq 0}^{5}$. The polytope $P_{A}$ is a triangle containing two
interior points as illustrated in Figure 4 and the defining ideal $I_{A}$ is
generated by three binomials,

$\displaystyle I_{A}=\langle u^{2}-yv,v^{3}-xzu,uv^{2}-xyz\rangle.$

We first consider the portion of the algebraic boundary which is the image of
the branch locus. The kernel $\ker A_{E}^{T}$ is generated by the single
vector $\omega=(1,-4,1)$ so that we may write $\nu=(5,0,-5,0,0)$ and

$\displaystyle B_{A,E}=\\{(x,y,z,u,v)\in\mathcal{M}_{A}^{>0}:x-z=0\\}.$

$1$$\bullet$$2$$\bullet$$3$$\bullet$$\bullet$$4$$\bullet$$5$

Figure 4. (Left) The polytope $P_{A}$ for Example 5.2
(Right) The completable region and curves defined by $f(u,v)=0$ and $g(u,v)=0$

As the ideal

$\displaystyle I(B_{A,E})=\langle
u^{2}-yv,v^{3}-xzu,uv^{2}-xyz,x+y+z+u+v-1,x-z\rangle,$

is prime, it is the defining ideal of the branch locus. Using Macaulay2 to
eliminate the variables $x$, $y$, and $z$ from the ideal $I(B_{A,E})$, the
eliminant is generated by the single polynomial

$\displaystyle
f(u,v)=u^{5}+2u^{4}v+3u^{3}v^{2}+2u^{2}v^{3}+uv^{4}-4v^{5}-2u^{3}v-2u^{2}v^{2}-2uv^{3}+uv^{2}.$

Thus, the algebraic boundary of the completable region
$\pi_{E}(\mathcal{M}_{A})$ is defined by the single polynomial equation
$f(u,v)=0$.

Note if $p\in\partial\mathcal{M}_{A}$, then some coordinate is equal to zero
so that $\operatorname{supp}(p)$ is a proper facial set. Since the only facial
set intersecting $E$ is the set $[5]=\\{1,2,3,4,5\\}$, it follows that
$\operatorname{supp}(p)\cap E=\emptyset$ and $\pi_{E}(p)=(0,0)$. That is,
$\pi_{E}(\partial\mathcal{M}_{A})=\\{(0,0)\\}$. Thus, the algebraic boundary
is defined by the single equation $f(u,v)=0$.

Contrary to this, the completable region is not described by either inequality
$f(u,v)\geq 0$ or $f(u,v)\leq 0$. Indeed, the completable region is
illustrated in Figure 4. The red curve is the algebraic boundary defined by
the equation $f(u,v)=0$, but only the shaded area is the completable region.

To obtain a semialgebraic description of the completable region, consider a
partial observation $(u,v)\in\pi_{E}(\mathcal{M}_{A})$ with non–zero
coordinates and a completion $(x,y,z,u,v)\in\mathcal{M}_{A}$. Multiplying
through the equation $x+y+z+u+v=1$ by $zuv$ and using the generators of the
toric ideal $I_{A}$, one finds that $z$ satisfies the quadratic equation

$\displaystyle uvz^{2}+(u^{3}+u^{2}v+uv^{2}-uv)z+v^{4}=0.$

Conversely, using the generators of $I_{A}$, any solution to this quadratic
yields a completion of $(u,v)$ to the log–linear model $\mathcal{M}_{A}$.
Thus, this quadratic has all non–negative solutions and the sum of these
solutions

$\displaystyle\frac{-1}{uv}\left(u^{3}+u^{2}v+uv^{2}-uv\right)\geq 0$

must also be non–negative. Since $u$ and $v$ are non–zero, this implies that

$\displaystyle g(u,v)=-u^{2}-uv-v^{2}+v\geq 0.$

The blue curve in Figure 4 is defined by the equation $g(u,v)=0$ and together
the inequalities $f(u,v)\geq 0$ and $g(u,v)\geq 0$ provide a semialgebraic
description of the completable region. Precisely,

$\displaystyle\pi_{E}(\mathcal{M}_{A})=\\{(u,v)\in\mathbb{R}_{\geq
0}^{2}:f(u,v)\geq 0,\leavevmode\nobreak\ g(u,v)\geq 0\\}.$

As in Example 5.2, it is often the case that the ideal
$I_{A}+\langle\sum_{i}x_{i}-1,\nu^{T}x\rangle$ is prime, in which case it is
equal to the defining ideal of the branch locus $I(B_{A,E})$. The following
example demonstrates a situation in which the boundary of the log–linear model
$\mathcal{M}_{A}$ maps onto the boundary of the completable region.

######  Example 5.3.

A hierarchical model is a log–linear model determined by the data of a
simplicial complex with positive integer weights given at each of the
vertices. Each vertex corresponds to a random variable with the weight of the
vertex being the number of outcome states of the variable. The faces of the
simplicial structure encode dependencies among these variables. We consider
the hierarchical model associated to the length two segment with each vertex
weight equal to two. This corresponds to three binary random variables
$X_{1}$, $X_{2}$, and $X_{3}$ with the probability of their outcomes related
by certain relations determined by the dependencies.

$X_{1}$$\bullet$$X_{2}$$\bullet$$X_{3}$$\bullet$ Figure 5. The length two line
segment

The model has coordinates $p_{ijk}$ given by the probability that $X_{1}=i$,
$X_{2}=j$, and $X_{3}=k$. As described in [Sul18], a hierarchical model is a
log–linear model and so can be described by an integer matrix
$A\in\mathbb{Z}_{\geq 0}^{k\times n}$. For the hierarchical model associated
to Figure 5 and all weights equal to two, the matrix $A$ is given by

$\displaystyle A=$ $\displaystyle\begin{pmatrix}1&1&0&0&0&0&0&0\\\
0&0&1&1&0&0&0&0\\\ 0&0&0&0&1&1&0&0\\\ 0&0&0&0&0&0&1&1\\\ 1&0&0&0&1&0&0&0\\\
0&1&0&0&0&1&0&0\\\ 0&0&1&0&0&0&1&0\\\ 0&0&0&1&0&0&0&1\end{pmatrix},$

where the columns of $A$ index the coordinates $p_{ijk}$ in lexicographical
order. One finds that $\operatorname{rank}A=6$ and the toric ideal $I_{A}$ is
generated by the following binomials

$\displaystyle I_{A}=\langle
p_{112}p_{211}-p_{111}p_{212},p_{122}p_{211}-p_{121}p_{222}\rangle.$

We demonstrate two subsets $E\subseteq[n]$ for which a semialgebraic
description of the completable region $\pi_{E}(\mathcal{M}_{A})$ can be easily
computed and show how a semialgebraic description can be obtained in general
for this model.

Let $E=\\{1,2,3,4,5\\}\subseteq[8]$ so that
$|E|=\operatorname{rank}A_{E}=\operatorname{rank}A-1=5$. In other words, we
will observe the coordinates $p_{111}$, $p_{112}$, $p_{121}$, $p_{122}$, and
$p_{211}$. Macaulay2 can be used to verify that $E$ is contained in the proper
facial set $\\{1,2,3,4,5,6\\}$. Thus, the branch locus $B_{A,E}$ is empty and
the algebraic boundary can be obtained by eliminating $p_{212}$, $p_{221}$,
and $p_{222}$ from the ideal
$I_{A}+\langle\sum_{i,j,k}p_{ijk}-1,\prod_{i,j,k}p_{ijk}\rangle$. We find that
the algebraic boundary is given by the single polynomial

$\displaystyle f(p_{111},p_{112},p_{121},p_{122},p_{211})$
$\displaystyle=-p_{111}^{2}-p_{111}p_{121}-p_{111}p_{122}-p_{111}p_{211}-p_{112}p_{211}+p_{111}.$

Further, a semialgebraic description of the completable region is given by

$\displaystyle\pi_{E}(\mathcal{M}_{A})=\\{p_{E}\in\mathbb{R}_{\geq
0}^{5}:f(p_{111},p_{112},p_{121},p_{122},p_{211})\geq 0\\}.$

Indeed, given a partial observation $p_{E}\in\pi_{E}(\mathcal{M}_{A})$ with
non–zero coordinates, the remaining coordinates can be computed in rational
functions of the observed coordinates $p_{111}$, $p_{112}$, $p_{121}$,
$p_{122}$, and $p_{211}$ as

$\displaystyle p_{212}$ $\displaystyle=\frac{p_{112}p_{211}}{p_{111}}$
$\displaystyle p_{221}$
$\displaystyle=\frac{p_{121}f(p_{111},p_{112},p_{121},p_{122},p_{211})}{p_{111}(p_{121}+p_{122})}$
$\displaystyle p_{222}$
$\displaystyle=\frac{p_{122}f(p_{111},p_{112},p_{121},p_{122},p_{211})}{p_{111}(p_{121}+p_{122})}.$

As our partial observation has non–zero coordinates, this completion lies in
the log–linear model $\mathcal{M}_{A}$ exactly when
$f(p_{111},p_{112},p_{121},p_{122},p_{211})\geq 0$.

We note that for any subset $E\subseteq[n]$ which is contained in a proper
facial set, the above analysis can be carried out to obtain a semialgebraic
description of the completable region. Indeed, for the hierarchical model
$\mathcal{M}_{A}$, if $E\subseteq[n]$ is contained in a proper facial set,
then the coordinates $p_{i}$ for $i\in[n]\setminus E$ can be explicitly
computed in rational functions in the coordinates $p_{i}$ for $i\in E$ via the
generators of the toric ideal $I_{A}$ and the relation $\sum_{i}p_{i}=1$.

For a subset $E\subseteq[n]$ such that
$|E|=\operatorname{rank}A_{E}=\operatorname{rank}A-1$ that is not contained in
a proper facial set, then by choosing a coordinate $p_{ijk}$ not indexed by
$E$, the remaining coordinates are rational functions in $p_{ijk}$ and the
coordinates indexed by $E$. Indeed, by observing the generators of the toric
ideal $I_{A}$, each of these rational functions has the form $f(p_{E})p_{ijk}$
or $f(p_{E})p_{ijk}^{-1}$ where $f(p_{E})$ is a (Laurent) monomial in the
coordinates indexed by $E$. Subsituting these values into the relation
$\sum_{ijk}p_{ijk}=1$, one finds that $p_{ijk}$ satisfies a quadratic
relation. As in Example 5.2, this quadratic has all non–negative roots for
$p_{E}\in\pi_{E}(\mathcal{M}_{A})$ and one obtains an additional polynomial
inequality that the partial observation $p_{E}$ must satisfy. Since the
remaining coordinates are given as rational functions with positive
coefficients in $p_{ijk}$ and the coordinates indexed by $E$, any solution of
this quadratic corresponds to a completion in $\mathcal{M}_{A}$ of $p_{E}$.
Thus, one obtains a semialgebraic description of the completable region.

In either of the cases above, given a subset $E\subseteq[n]$ satisfying
$|E|=\operatorname{rank}A_{E}=\operatorname{rank}A-1$, one can obtain a
semialgebraic description of the completable region $\pi_{E}(\mathcal{M}_{A})$
for this hierarchical model.

## References

  * [BBS20] Daniel Irving Bernstein, Grigoriy Blekherman, and Rainer Sinn.  Typical and generic ranks in matrix completion.  Linear Algebra and its Applications, 585:71–104, 2020.
  * [BGMV23] Paul Breiding, Fulvio Gesmundo, Mateusz Michałek, and Nick Vannieuwenhoven.  Algebraic compressed sensing.  Applied and Computational Harmonic Analysis, 65:374–406, 2023.
  * [CLS11] David A. Cox, John B. Little, and Henry K. Schenck.  Toric varieties, volume 124 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI, 2011.
  * [DS98] Persi Diaconis and Bernd Sturmfels.  Algebraic algorithms for sampling from conditional distributions.  The Annals of Statistics, 26(1):363–397, 1998.
  * [Ewa96] Günter Ewald.  Combinatorial convexity and algebraic geometry, volume 168 of Graduate Texts in Mathematics.  Springer-Verlag, New York, 1996.
  * [Ful93] William Fulton.  Introduction to toric varieties, volume 131 of Annals of Mathematics Studies.  Princeton University Press, Princeton, NJ, 1993.  The William H. Roever Lectures in Geometry.
  * [GHMM22] Amir Kafshdar Goharshady, S Hitarth, Fatemeh Mohammadi, and Harshit J Motwani.  Template-based program synthesis using stellensätze.  arXiv preprint arXiv:2209.03602, 2022.
  * [GMN22] Christiane Görgen, Aida Maraj, and Lisa Nicklasson.  Staged tree models with toric structure.  Journal of Symbolic Computation, 113:242–268, 2022.
  * [GMS06] Dan Geiger, Christopher Meek, and Bernd Sturmfels.  On the toric algebra of graphical models.  The Annals of Statistics, 34(3):1463 – 1492, 2006.
  * [GS] Daniel R. Grayson and Michael E. Stillman.  Macaulay2, a software system for research in algebraic geometry.  Available at http://www2.macaulay2.com.
  * [HS02] Serkan Hoşten and Seth Sullivant.  Gröbner bases and polyhedral geometry of reducible and cyclic models.  Journal of Combinatorial Theory, Series A, 100(2):277–301, 2002\.
  * [HS07] Serkan Hoşten and Seth Sullivant.  A finiteness theorem for Markov bases of hierarchical models.  Journal of Combinatorial Theory. Series A, 114(2):311–321, 2007\.
  * [KKKR17] Thomas Kahle, Kaie Kubjas, Mario Kummer, and Zvi Rosen.  The geometry of rank-one tensor completion.  SIAM Journal on Applied Algebra and Geometry, 1(1):200–221, 2017\.
  * [KR17] Kaie Kubjas and Zvi Rosen.  Matrix completion for the independence model.  Journal of Algebraic Statistics, 8(1):1–21, 2017.
  * [KTT15] Franz J Király, Louis Theran, and Ryota Tomioka.  The algebraic combinatorial approach for low-rank matrix completion.  Journal of Machine Learning Research, 16(1):1391–1436, 2015.
  * [KTTU12] Franz J Király, Louis Theran, Ryota Tomioka, and Takeaki Uno.  The algebraic combinatorial approach for low-rank matrix completion.  arXiv preprint arXiv:1211.4116, 2012.
  * [LPR20] Henri Lombardi, Daniel Perrucci, and Marie-Françoise Roy.  An elementary recursive bound for effective Positivstellensatz and Hilbert’s 17th problem.  Mem. Amer. Math. Soc., 263(1277):v+125, 2020.
  * [SC10] Amit Singer and Mihai Cucuringu.  Uniqueness of low-rank matrix completion by rigidity theory.  SIAM Journal on Matrix Analysis and Applications, 31(4):1621–1641, 2010.
  * [Sot03] Frank Sottile.  Toric ideals, real toric varieties, and the moment map.  In Topics in algebraic geometry and geometric modeling, volume 334 of Contemporary Mathematics, pages 225–240. American Mathematical Society, Providence, RI, 2003.
  * [Sul18] Seth Sullivant.  Algebraic statistics, volume 194.  American Mathematical Society, Providence, RI, 2018.
  * [tt] 4ti2 team.  4ti2—a software package for algebraic, geometric and combinatorial problems on linear spaces.  Available at https://4ti2.github.io.