Sharp lower and upper bounds for the Gaussian rank of a graph

doi:10.1016/j.jmva.2015.03.004

Journal of Multivariate Analysis

Volume 139, July 2015, Pages 207-218

https://doi.org/10.1016/j.jmva.2015.03.004 Get rights and content

Under an Elsevier user license

open archive

Abstract

An open problem in graphical Gaussian models is to determine the smallest number of observations needed to guarantee the existence of the maximum likelihood estimator of the covariance matrix with probability one. In this paper we formulate a closely related problem in which the existence of the maximum likelihood estimator is guaranteed for all generic observations. We call the number determined by this problem the Gaussian rank of the graph representing the model. We prove that the Gaussian rank is strictly between the subgraph connectivity number and the graph degeneracy number. These bounds are sharper than the bounds known in the literature and furthermore computable in polynomial time.

AMS subject classification

62H12

97K30

Keywords

Gaussian graphical models

Maximum likelihood estimation

Tree-width

Connectivity number

Degeneracy number

Random graphs

Symmetric graphs

1. Introduction

An open problem in graphical Gaussian models is to determine the smallest number of observations needed to guarantee the existence of the maximum likelihood estimator (MLE) of the covariance matrix. This problem first arose in Dempster’s paper [3] and has been frequently brought to attention by Steffen Lauritzen, as evident in [1] and Lauritzen’s lectures in “Durham Symposium on Mathematical Aspects of Graphical Models 2008”. Hence we refer to this problem as the D&L problem using the initials of Dempster and Lauritzen. Note that the D&L problem as stated above is not well-posed, because the existence of the MLE cannot be guaranteed for all observations, no matter how large the number of observations is. To make this well-posed, a necessary condition is to ignore a set of observations of probability zero and thus require the existence of the MLE only for observations in a set of probability one. It is now clear that the D&L problem in its most general form can be expressed as follows.

D&L problem (I) For a given graphical Gaussian model with respect to a graph $G$ , determine the smallest number of observations needed to guarantee the existence of the MLE with probability one.

A slightly different well-posed formulation of the D&L problem is to require the existence of the MLE (of the covariance matrix, henceforth) for all generic observations in the following sense. Let $n \leq p$ . Then the observations¹ $x_{1}, \dots, x_{n} \in R^{p}$ are said to be generic if each $n \times n$ principal submatrix of the sample covariance matrix $S = 1 / n \sum_{i = 1}^{n} x_{i} x_{i}^{⊤}$ is non-singular. Note that with probability one every $n$ observations are generic (thus the set of non-generic observations is of probability zero). This formulation can now be expressed as follows.

D&L problem (II) For a given graphical Gaussian model with respect to a graph $G$ , determine the smallest number of observations needed to guarantee the existence of the MLE for all generic observations.

The number determined by the D&L problem (II) is said to be the Gaussian rank of $G$ , denoted by $r (G)$ . The primary goal of this paper is to obtain sharp lower and upper bounds on $r (G)$ . In parallel to the D&L problem (II), the number determined by the D&L problem (I) is said to be the weak Gaussian rank of $G$ , denoted by $r_{w} (G)$ . Note again that being in general position is a generic property of any $n$ observations, that is, with probability one for every $n$ observations each $n \times n$ principal submatrix of the sample covariance matrix is non-singular. Thus obviously $r (G) \geq r_{w} (G)$ , for every graph $G$ .

As we mentioned earlier, the D&L problem first arose in [3], a celebrated work of Dempster in which, under the principle of parsimony in fitting parametric models, Dempster introduced graphical Gaussian models and gave a partial analytic expression for the MLE of the covariance matrix, assuming that the MLE exists. In practice, the MLE has to be computed by an iterative numerical procedure, such as the iterative proportional scaling procedure (IPS) [16]. However, if the number of observations is not sufficiently large there is no guarantee that the output matrix will indeed correspond to the MLE, as it might not be positive definite. It is clear that the number determined by the D&L problem under either formulations depends on the level of sparsity in graph, but the exact nature of this dependency is far from clear. Mainly because sparse graphs are not well understood, in particular it is not known what graph parameters best measure the graph sparsity. Hence the D&L problems (I) and (II) are important problems not only in relation to maximum likelihood estimation but also for gaining deeper insight into sparse graphs. In practice, the D&L problem (II) is equivalent to the D&L problem (I), because in general the data can be expected to be generic and therefore $n \geq r (G)$ is a condition that minimally guarantees the existence of the MLE.

In a graphical Gaussian model the sparsity is given by a pattern of zeros in the inverse covariance matrix. The pattern of zeros is determined by the missing edges of a graph and each zero entry of a generic inverse covariance matrix indicates that the corresponding pair of variables are conditionally independent given the remaining variables. An attractive feature of graphical Gaussian models, or graphical models in general, is that if the graph representing the model is sparse, then the MLE of the covariance matrix can exist even if the number of observations is much smaller than the dimension of the multivariate Gaussian distribution. Intuitively, we expect that the Gaussian rank of the graph, the number determined by the D&L problem, to decrease as the graph becomes sparser. However, it is not clear what best measures the sparsity of a graph or how the Gaussian rank varies accordingly. The main theorem of this paper suggests two such measures of sparsity.

Despite some efforts since 90’s not much progress has been made to resolve the D&L problem. The existing results are limited to a handful of publications as follows.

(R1)
[5] For a decomposable graph $G$ , a graph that has no induced cycle of length larger than or equal to four, the Gaussian rank is equal to $ω (G)$ , the size of the largest complete subgraph of $G$ .
(R2)
[5] For every graph $G, ω (G) \leq r_{w} (G) \leq r (G) \leq tw (G) + 1$ , where $tw (G)$ denotes the treewidth of $G$ (See [7] for the definition).
(R3)
[1] For $C_{p}$ , a cycle of length $p \geq 3, 2 = ω (C_{p}) < r_{w} (C_{p}) = r (C_{p}) = 3 = tw (C_{p}) + 1$ .
(R4)
[17] For $G_{3, 3}$ , the 3×3 grid, $2 = ω (G_{3, 3}) < r_{w} (G_{3, 3}) = r (G_{3, 3}) = 3 < tw (G_{3, 3}) + 1 = 4$ .

In the literature the bounds given by (R2) are currently the best known bounds for the Gaussian rank. Restricted to the class of decomposable graphs these bounds are tight, since

tw (G) + 1 = ω (G)

for a decomposable graph

G

, but we may note that (R4) in [17] shows that for non-decomposable graphs the bounds in (R2) are not necessarily tight. Intuitively, it is apparent that

ω (G)

overestimates and

tw (G)

underestimates the sparsity of

G

and therefore sharper bounds may exist. In this paper we give sharper bounds on the Gaussian rank. The lower and upper bounds we give are the subgraph connectivity number, denoted by

κ^{*} (G)

, and the graph degeneracy number, denoted by

δ^{*} (G)

. Both

κ^{*} (G)

and

δ^{*} (G)

will be defined later in Section 2.2. Formally we prove the following theorem.

Theorem 1.1

Let $G = (V, E)$ be a graph. Then(1.1) $κ^{*} (G) + 1 \leq r (G) \leq δ^{*} (G) + 1$

The proof of this theorem is given in Section 4. The upper bound is proved by mathematical induction using two key observations: suppose a graph

H

is obtained from

G

by removing a vertex

v

and its adjacent edges. Then (1)

r (H) \geq r (G) - 1

and (2) if

r (G)

is larger than the number of the vertices adjacent to

v

, then

r (H) = r (G)

. The proof of the lower bound relies on Lovász–Saks–Schrijver’s Theorem in [11].

All the results stated in (R1) through (R4) now immediately follow from Theorem 1.1, since by some simple calculations we can show that

(a)
for a decomposable graph $G, ω (G) = κ^{*} (G) + 1 = δ^{*} (G) + 1 = tw (G) + 1$ ;
(b)
for any (arbitrary) graph $G, ω (G) \leq κ^{*} (G) + 1 \leq r (G) \leq δ^{*} (G) + 1 \leq tw (G) + 1$ ;
(c)
for a cycle (of any length) $G, κ^{*} (G) = δ^{*} (G) = 2$ ;
(d)
for a $k \times m$ grid (with $k$ and $m \geq 2$ ), $κ^{*} (G) = δ^{*} (G) = 2$ .

Note that by Part (d) the Gaussian rank of every grid is 3 which is substantially less than the upper bound given by (R2) for grids of large dimensions. The reason is that the treewidth of a

k \times m

grid is

min {k, m}

which tends to

+ \infty

k

and

m \to + \infty

[14]. Here we mention that by relating

r_{w} (G)

to the rigidity of the graph

G

, Gross and Sullivant in a recent manuscript [6] also obtain the upper bound in Theorem 1.1 for

r_{w} (G)

This paper is structured as follows. In Section 2 we first introduce required preliminaries and notation in graph theory, matrix algebra and Gaussian graphical models, and then explain the MLE problem for Gaussian graphical models. In Section 3 we give an alternative description of the Gaussian rank and derive some of its properties. In Section 4 we prove Theorem 1.1. In Section 5 we apply Theorem 1.1 to some special graphs to exactly determine their Gaussian ranks. These graphs include symmetric graphs and random graphs. We also obtain a tight numerical upper bound for the Gaussian ranks of planar graphs.

2. Preliminaries

In this section, we establish some necessary notation, terminology and definitions in graphical models, matrix algebra and geometric graph theory. We also carefully explain how the maximum likelihood problem for graphical Gaussian models leads to the D&L problem.

2.1. Graph theoretical notion, definitions

Our notation presented here closely follows the notation established in [15], [10]. Let $G = (V, E)$ be an undirected graph, where $V = V (G)$ is the vertex set and $E = E (G)$ is the edge set of $G$ . Each edge $e \in E$ is an unordered pair $i j = {i, j}$ , where $i, j \in V$ . For ease of notation we assume that $E$ contains all the self-loops, that is, $(i, i)$ for every $i \in V$ . Unless otherwise stated, we always assume that $V (G) = {1, \dots, p} = [p]$ .

(1)
For a vertex $v \in V$ , the set and the number of vertices adjacent to $v$ are denoted by $ne (v)$ and ${deg}_{G} (v)$ .
(2)
A graph $H$ is a subgraph of $G$ , denoted by $H \subseteq G$ , if $V (H) \subseteq V (G)$ and $E (H) \subseteq E (G)$ .
(3)
For a set $V^{'} \subseteq V$ , the graph defined by $G [V^{'}] = (V^{'}, E \cap V^{'} \times V^{'})$ is said to be the subgraph of $G$ induced by $V^{'}$ .
(4)
For a vertex $v \in V$ , the induced subgraph $G [V ∖ {v}]$ is denoted by $G - v$ . Note that $G - v$ is simply obtained by removing $v$ and its incident edges from $G$ .
(5)
For an edge $e \in E, G - e$ denotes the subgraph obtained by removing $e$ from $G$ , that is, $G - e = (V, E ∖ {e})$ .

2.2. Graph parameters

Let $G$ denote the set of all graphs. A graph parameter is a function $(μ : G \to R) : G \mapsto μ (G)$ . In words, a graph parameter is a function that assigns a number to each graph. In graph theory two common graph parameters are:

(a)
$δ (G) = min {{deg}_{G} (v) : v \in V}$ , said to be the minimum degree of $G$ ;
(b)
$κ (G) = min {| S | : S \subseteq V such that G [V ∖ S] is disconnected}$ , said to be the vertex connectivity number of $G$ . In words, $κ (G)$ is the smallest number $k$ of vertices whose deletion separates the graph or makes it trivial.

Now for every graph parameter

μ

we can define a new graph parameter as

μ^{*} (G) = max {μ (H) : H \subseteq G} .

Two such defined graph parameters are

δ^{*} (G)

and

κ^{*} (G)

, known as the graph degeneracy number and the subgraph connectivity number of

G

, respectively [15]. Note that

κ^{*} (G)

is the smallest number of vertex deletions sufficient to disconnect each subgraph of

G

. Since

κ (G) \leq δ (G)

we have (2.1)

κ^{*} (G) \leq δ^{*} (G) (see Part (a) inRemark 2.1) .

Example 2.1

Consider the graphs given by Fig. 1(a)–(c).

(a)
The graph denoted by $G_{4, 5}$ in Fig. 1(a) is a 4×5 grid. It is easy to see that $κ^{*} (G_{4, 5}) = δ^{*} (G_{4, 5}) = 2$ . In fact for every $k \times m$ grid (with $k$ and $m \geq 2$ ), $κ^{*} (G_{k, m}) = δ^{*} (G_{k, m}) = 2$ .
(b)
The graph denoted by $C_{8}$ in Fig. 1(b) is a cycle of length 8 with $κ^{*} (C_{8}) = δ^{*} (C_{8}) = 2$ . This is obviously true for any arbitrary cycle $C_{p}$ (with length $p \geq 3$ ).
(c)
The graph denoted by $K_{4, 3}$ in Fig. 1(c) is a complete (4,3)-bipartite graph. In general, a complete $(k, m)$ -bipartite graph is a graph so that its vertex set can be partitioned into two sets with $k$ and $m$ elements such that two vertices are adjacent if and only if they are in different partitions of $V$ . One can check that $κ^{*} (K_{k, m}) = δ^{*} (K_{k, m}) = min {k, m}$ [15].

Remark 2.1

These simple facts can be found in [15].

(a)
If two graph parameters are such that $μ_{1} (H) \leq μ_{2} (H)$ for every subgraph $H \subseteq G$ , then $μ_{1}^{*} (G) \leq μ_{2}^{*} (G)$ .
(b)
If a graph parameter is non-decreasing, that is, $H \subseteq G ⟹ μ (H) \leq μ (G)$ , then $μ^{*} (G) = μ (G)$ . For example, for this reason $ω^{*} (G) = ω (G)$ and ${tw}^{*} (G) = tw (G)$ .
(c)
For every graph $G$ we have $ω (G) \leq κ (G) + 1 \leq δ (G) + 1 \leq tw (G) + 1$ . In light of (a) and (b), this implies that $ω (G) \leq κ^{*} (G) + 1 \leq δ^{*} (G) + 1 \leq tw (G) + 1$ .
(d)
There are algorithms (specifically given in [15]) that compute $κ^{*} (G)$ and $δ^{*} (G)$ , respectively, in no more than $O ({| V |}^{3 / 2} {| E |}^{2})$ and $O (| E |)$ steps (in contrast, clique number and treewidth cannot be computed in polynomial time).

2.3. Matrix algebra notation, definitions

The notation presented here closely follows the notation established in [19], [15]. For a vector $u = (u_{i} : i \in V) \in R^{V}$ and $α \subseteq V$ , let $u [α]$ denote the subvector $(u_{i} : i \in α) \in R^{α}$ . For a matrix $A = (A_{i, j}) \in R^{V \times V}$ and $α$ and $β \subseteq V$ , let $A [α, β]$ denote the submatrix $(a_{i, j} : i \in α, j \in β) \in R^{α \times β}$ . A principal submatrix $A [α, α]$ is simply denoted by $A [α]$ . Some other notations used throughout the paper are as follows.

(1)
The set of $p \times p$ symmetric matrices is denotes by $S (p)$ .
(2)
The set of (symmetric) positive semi-definite matrices is denoted by $S_{+} (p)$ .
(3)
The set of (symmetric) positive definite matrices is denoted by $S_{+ +} (p)$ .
(4)
The set of matrices $A \in S_{+} (p)$ of a fixed rank $d$ is denoted by $S_{+} (p, d)$ .
(5)
$A ⪰ 0$ (or $A ≻ 0$ ) denotes $A$ is a positive semidefinite (or positive definite) matrix without specifying its dimension.
(6)
The Moore–Penrose generalized inverse of $A$ is denoted by $A^{†}$ . Note that $A^{†} A A^{†} = A^{†}$ and $A A^{†} A = A$ . It is clear that $A^{†} = A^{- 1}$ when $A$ is non-singular.
(7)
Let $A$ be partitioned as $A = (\begin{matrix} A [α] & A [α, β] \\ A [β, α] & A [β] \end{matrix})$ , where $β = V ∖ α$ . Then the Schur complement of $A [α]$ , denoted by $A [β | α]$ , is defined by $A [β | α] = A [β] - A [β, α] A {[α]}^{†} A [α, β] .$

Convention: For convenience in subsequent sections, unless otherwise stated, we always assume that given matrices are non-zero.

2.4. General-position vectors and matrices

Let $v_{1}, \dots, v_{p}$ be $p$ vectors in $R^{d}$ . These vectors are said to be in general position in $R^{d}$ if any $d$ vectors among them are linearly independent. Also a square matrix $A$ of rank $d$ is said to be in general position if every $d \times d$ principal submatrix of $A$ is non-singular.

Next we proceed with two lemmas and a corollary due to Eaton and Perlman [4] and Malley [13]. For completeness and because the notation under consideration is slightly different in the Appendix we prove these results.

Lemma 2.1

[4], [13]

If $p \geq d$ vectors are randomly selected in $R^{d}$ (with a probability distribution dominated by Lebesgue measure), then with probability one they are in general position.

Lemma 2.1 therefore implies that being in general position is a generic property of any

p \geq d

vectors in

R^{d}

. The next lemma shows that there is a relationship between general-position vectors and matrices.

Lemma 2.2

Let $A \in S_{+} (p, d)$ . Then $A$ is in general position if and only if there are general-position vectors $v_{1}, \dots, v_{p} \in R^{d}$ such that(2.2) $A = (\begin{matrix} v_{1}^{⊤} \\ ⋮ \\ v_{p}^{⊤} \end{matrix}) (\begin{matrix} v_{1} & \dots & v_{p} \end{matrix}) = {(v_{i}^{⊤} v_{j})}_{1 \leq i, j \leq p} .$

Corollary 2.1

[4], [13]

Suppose $x_{1}, \dots, x_{n}$ are $n$ observations from a $p$ -variate distribution. Then with probability one the sample covariance matrix $S$ and the sample correlation matrix $R$ are in general positions.

A useful property of a general-position matrix $A \in S_{+} (p, d)$ is that in some sense it can be extended to another general-position matrix in $S_{+} (p + 1, r)$ or $S_{+} (p + 1, r + 1)$ . The next lemma formalizes this fact.

Lemma 2.3

Let $A \in S_{+} (p, d)$ be in general position.

(a)
There exist non-zero vectors $w$ and $v \in R^{p}$ such that $A - w w^{⊤}$ and $(\begin{matrix} 1 & v^{T} \\ v & A \end{matrix})$ are general-position matrices, respectively, in $\in S_{+} (p, d)$ and $S_{+} (p + 1, d)$ .
(b)
If $d \leq p - 1$ , then there exists a vector $u \in R^{p}$ such that $A + u u^{⊤} \in S_{+} (p, d + 1)$ is in general position. This in return implies that the matrix $(\begin{matrix} 1 & u^{⊤} \\ u & A + u u^{⊤} \end{matrix}) \in S_{+} (p + 1, d + 1) is in general position.$

Proof

(a) Let $τ = [d]$ and choose a non-zero vector $x_{τ} \in R^{d}$ such that $x_{τ}^{⊤} A [τ] x_{τ} < 1$ . We set $x = (\begin{matrix} x_{τ} \\ 0 \end{matrix}) \in R^{p} and w = A x = (\begin{matrix} A [τ] x_{τ} \\ A [γ, τ] x_{τ} \end{matrix}),$ where $γ = V ∖ τ$ . Note that $A ⪰ 0$ and $x^{⊤} A x = x_{τ}^{⊤} A [τ] x_{τ} < 1$ . Thus we have $1 - w^{⊤} A^{†} w = 1 - x^{⊤} A x > 0,$ and therefore $B = A - w w^{⊤} \in S_{+} (p)$ , by Theorem 1.20 in [19]. Now we claim that $B$ has rank $d$ and is in general position. It suffices to show that $B [α] = A [α] - w [α] w {[α]}^{⊤} ≻ 0$ for every set $α = {i_{1}, \dots, i_{d}} \subseteq V$ . Let $β = V ∖ α$ . Then $w [α] = (A x) [α] = (\begin{matrix} A [α] & A [α, β] \end{matrix}) (\begin{matrix} x [α] \\ x [β] \end{matrix}) = A [α] x [α] + A [α, β] x [β] .$ Thus, if we set $y_{α} = x [α] + A {[α]}^{- 1} A [α, β] x [β]$ , then $A [α] y_{α} = w [α]$ . Our claim is established if we can show that $(\begin{matrix} 1 & w {[α]}^{⊤} \\ w & A [α] \end{matrix}) ≻ 0, or equivalently 1 - w^{⊤} [α] A {[α]}^{- 1} w [α] = 1 - y_{α}^{⊤} A [α] y_{α} > 0 .$ We verify that the right-hand side inequality holds by writing $y_{α}^{⊤} A [α] y_{α} = {(x [α] + A {[α]}^{- 1} A [α, β] x [β])}^{⊤} A [α] (x [α] + A {[α]}^{- 1} A [α, β] x [β]) = x {[α]}^{⊤} A [α] x [α] + 2 x {[α]}^{⊤} A [α, β] x [β] + x {[β]}^{⊤} A [β, α] A {[α]}^{- 1} A [α, β] x [β] = x {[α]}^{⊤} A [α] x [α] + 2 x {[α]}^{⊤} A [α, β] x [β] + x {[α]}^{⊤} A [α, β] x [β] - x {[β]}^{⊤} A [β | α] x [β] = {(\begin{matrix} x [α] \\ x [β] \end{matrix})}^{⊤} (\begin{matrix} A [α] & A [α, β] \\ A [β, α] & A [β] \end{matrix}) (\begin{matrix} x [α] \\ x [β] \end{matrix}) - x {[β]}^{⊤} A [β | α] x [β] = x^{⊤} A x - x {[β]}^{⊤} A [β | α] x [β] \leq x^{⊤} A x (since A ⪰ 0 and therefore A [β | α] ⪰ 0) < 1 .$ Therefore, $B [α] ≻ 0$ and $rank (B [α]) = | α | = d$ . This shows that $B = A - w w^{⊤} \in S_{+} (p, d)$ is in general position. To prove the second half of Part (a) we proceed similarly. First we choose a vector $y_{τ} \in R^{d}$ such that $y_{τ}^{⊤} A [τ] y_{τ} = 1$ . Now we set $y = (\begin{matrix} y_{τ} \\ 0 \end{matrix}) \in R^{p} and v = A y = (\begin{matrix} A [τ] y_{τ} \\ A [γ, τ] y_{τ} \end{matrix}) .$ Then we have $1 - v^{⊤} A^{†} v = 1 - y^{⊤} A y = 0$ . Consequently, $B = A - v v^{⊤} \in S_{+} (p, d - 1)$ is in general position. This in return implies that $(\begin{matrix} 1 & v^{⊤} \\ v & A \end{matrix}) \in S_{+} (p + 1, d) is in general position.$ (b) First note that for a vector $u \in R^{p}$ , $rank (A + u u^{⊤}) = rank (A)$ if and only if $u \in Range (A)$ , otherwise $rank (A + u u^{⊤}) = rank (A) + 1$ [9]. Now it suffices to find a vector $u \in R^{p} ∖ Range (A)$ such that $p_{α} (u) = det (A [α] + u [α] u {[α]}^{⊤}) \neq 0$ for each $α = {i_{1}, \dots, i_{d + 1}} \subseteq V$ . For this, we note that $Range (A)$ and the zeros of the polynomials $p_{α} (x)$ are all algebraic sets $⊊ R^{p}$ and therefore have zero measures. Thus we can choose a vector $u$ in the nonempty set $R^{p} ∖ (Range (A) ⋃_{α} {x : p_{α} (x) = 0})$ . For this vector the matrix $A + u u^{⊤} \in S_{+} (p, d + 1)$ is in general position. The rest of the proof is similar to that of Part (a). □

Remark 2.2

As the proof shows, Part (a) of Lemma 2.3 holds in particular for $w = A x$ , where $x = (\begin{matrix} x_{τ} \\ 0 \end{matrix})$ and $x_{τ} \in R^{d}$ satisfies $x_{τ}^{⊤} A [τ] x_{τ} < 1$ .

2.5. Graphical Gaussian models

Let $G = (V, E)$ be a graph with $p$ vertices. A Gaussian distribution $N_{p} (0, Σ)$ is said to be Markov with respect to $G$ if ${(Σ^{- 1})}_{i, j} = 0 whenever i j \notin E .$ The graphical Gaussian model over $G$ , denoted by $N (G)$ , is the family of $N_{p} (0, Σ)$ Markov with respect to $G$ . Let $Z_{G} = {A \in S (p) : A_{i, j} = 0 for each i j \notin E} and P_{G} = Z_{G} \cap S_{+ +} (p) .$ Then $Z_{G}$ is an $| E |$ -dimensional linear space and $P_{G}$ is an open convex cone in $Z_{G}$ . Note that $P_{G}$ is in fact the set of inverse covariance matrices for the graphical Gaussian model $N (G)$ .

2.6. The maximum likelihood problem

Suppose $x_{1}, \dots, x_{n}$ are $n$ observations taken from $N_{p} (0, Σ) \in N (G)$ . Then the MLE of $Σ$ is the solution to the following optimization problem [8]: $\underset{Ω}{argmax} (- \frac{n}{2} log det Σ - \frac{n}{2} tr (Σ^{- 1} S))$ $subject to {(Σ^{- 1})}_{i, j} = 0, \forall i j \notin E$ $Σ ≻ 0 .$ Recall that $S = 1 / n \sum_{i = 1}^{n} x_{i} x_{i}^{⊤}$ is the sample covariance matrix. In terms of the inverse covariance matrix $Ω = Σ^{- 1}$ , this optimization problem can be recast as the convex optimization problem: (2.3) $\underset{Ω}{argmin} (- \frac{n}{2} log det Ω + \frac{n}{2} tr (Ω S))$ $subject to Ω \in P_{G} .$ A standard optimization procedure such as in [8] or [2] shows that the dual problem of (2.3) solves the following concave optimization problem. $\underset{Ω}{argmax} (log det Σ)$ (2.4) $subject to {\begin{cases} Σ_{i, j} = S_{i, j}, & \forall i j \in E \\ Σ ≻ 0, \end{cases}$ which has a unique solution if and only if the feasible set determined by Eq. (2.4) is non-empty. Note that the existence of a matrix $Σ$ that satisfies the condition given by Equation (2.4) is essentially a positive definite completion problem. For the future reference we record the conclusion as follows.

Proposition 2.1

Suppose $x_{1}, \dots, x_{n}$ are $n$ observations taken from $N_{p} (0, Σ) \in N (G)$ . Then the MLE of $Σ$ exists if and only if there is a matrix $P \in S_{+ +} (p)$ such that $P_{i, j} = S_{i, j}$ for every $i j \in E$ .

3. The Gaussian rank of a graph

In this section we give another description for the Gaussian rank of a graph using its unique property with respect to the positive definite completion problem given by Eq. (2.4). An advantage of this alternative description is that more easily can be verified and thus used to derive the properties of the Gaussian rank as a graph parameter.

3.1. An alternative description of the Gaussian rank

Let $G = (V, E)$ be a graph. Two matrices $A, B \in R^{p \times p}$ are said to match on $G$ , denoted by $A \overset{G}{=} B$ , if $A_{i, j} = B_{i, j}$ for each $i j \in E$ . In other words, two matrices match on $G$ if their Euclidean projection onto $Z_{G}$ are identical. The matching relation $\overset{G}{=}$ is additive, and invariant under scaling [1]. More precisely, (3.1) $A \overset{G}{=} B and U \overset{G}{=} V ⟹ A + U \overset{G}{=} B + V$ (3.2) $A \overset{G}{=} B ⟹ D A D \overset{G}{=} D B D, for every diagonal matrix D .$

Let us recall that by definition $r (G)$ is the smallest number $r$ with the property that for every observations $x_{1}, \dots, x_{r}$ if the sample covariance matrix $S$ is of rank $r$ and in general position, then the MLE exists. In light of Proposition 2.1 an alternative description of $r (G)$ can be given as follows.

Proposition 3.1

Let $G$ be a graph. Then $r (G)$ is the smallest number $r$ with the following property:

$(⋆)$
$\forall A \in S_{+} (p, r)$ , if $A$ is in general position $⟹ \exists P \in S_{+ +} (p)$ such that $P \overset{G}{=} A$ .

Remark 3.1

Similarly, $r_{w} (G)$ is the smallest number $r$ with the following property:

Almost surely $\forall A \in S_{+} (p, r)$ , if $A$ is in general position $⟹ \exists P \in S_{+ +} (p)$ such that $P \overset{G}{=} A$ .

3.2. Some basic properties of the Gaussian rank

In this subsection we list some basic properties of the Gaussian rank as a graph parameter. Let us keep in mind that $r (G) \leq r$ , for some positive integer $r$ if the condition $(⋆)$ in Proposition 3.1 is satisfied. Also, because of the scale invariant property of matching relation given by Eq. (3.2), whenever convenient we can assume that $A \in S_{+} (p, r)$ is a correlation matrix, that is, the diagonals of $A$ are all 1.

Proposition 3.2

Let $r > r (G)$ . Then for every general-position matrix $A \in S_{+} (p, r)$ there is a matrix $P \in S_{+ +} (p)$ such that $P \overset{G}{=} A$ .

Proof

Let $A = \sum_{i = 1}^{r} w_{i} w_{i}^{⊤}$ be a decomposition of $A$ as in Eq. (A.1). Let us set $B = \sum_{i = 1}^{r (G)} w_{i} w_{i}^{⊤}$ and $C = \sum_{i = r (G) + 1}^{r} w_{i} w_{i}^{⊤}$ . Since $A$ is in general position the matrix $B \in S_{+} (p, r (G))$ is also in general position. Thus there is a matrix $Q \in S_{+ +} (p)$ such that $Q \overset{G}{=} B$ . Eq. (3.1) now shows $A = B + C \overset{G}{=} Q + C \in S_{+ +} (p)$ as desired. □

In relation to the D&L problem (II) Proposition 3.2 is an important property that intuitively seems obvious. The reason is that if the MLE exists for every generic

r (G)

observations, then we expect this to be true for every generic

r \geq r (G)

observations as well.

Proposition 3.3

Let $v \in V$ be a vertex of $G$ . Then the following holds.

(a)
$r (G - v) \leq r (G) \leq r (G - v) + 1$ .
(b)
$r (G) = r (G - v) + 1$ if $v$ is adjacent to all other vertices.

Proof

First, without loss of generality we assume that $p \geq 2$ and $v = 1$ .

(a)
Let us set $r = r (G)$ . The claim is that $r (G - v) \leq r$ . Since $r (G - v) \leq p - 1$ it suffices to consider the case $r \leq p - 1$ . Let $A \in S_{+} (p - 1, r)$ be in general position. By Part (a) in Lemma 2.3 there is a vector $w \in R^{p - 1}$ such that $B = (\begin{matrix} 1 & w^{⊤} \\ w & A \end{matrix}) \in S_{+} (p, r) is in general position.$ Let $P \in S_{+ +} (p)$ such that $P \overset{G}{=} B$ . If we set $α = V (G - v)$ , then it is clear that $A \overset{G - v}{=} P [α] \in S_{+ +} (p - 1)$ .
Now we show that $r (G) \leq r (G - v) + 1$ . Let us set $r_{0} = r (G - v)$ and let $A \in S_{+} (p, r_{0} + 1)$ be in general position. We assume without loss of generality that $A$ is a correlation matrix. If we partition $A$ as $A = (\begin{matrix} 1 & u^{⊤} \\ u & B \end{matrix}), then C = B - u u^{⊤} ⪰ 0 .$ By using the Guttman rank additivity formula in [19] and the fact that $C [α] = B [α] - u [α] u {[α]}^{⊤}$ , for each $α \subseteq V$ , we conclude that $C \in S_{+} (p - 1, r_{0})$ is in general position. Therefore, there is a matrix $Q \in S_{+ +} (p - 1)$ such that $Q \overset{G - v}{=} C$ . Let us set $P = (\begin{matrix} 1 & u^{⊤} \\ u & Q + u u^{⊤} \end{matrix}) \in S_{+ +} (p) .$ The additive property of the matching relation given by Eq. (3.1) now shows that $Q + u u^{⊤} \overset{G - v}{=} B$ and therefore $P \overset{G}{=} A$ .
(b)
Suppose $v = 1$ is adjacent to $2, \dots, p$ . As before, let us set $r = r (G)$ . By Part (a) above $r (G - v) \geq r - 1$ . Thus, it suffices to show that $r (G - v) \leq r - 1$ . For this, let $A \in S_{+} (p - 1, r - 1)$ . Clearly, it suffices to consider the case $r \leq p - 1$ . By Part (b) of Lemma 2.3 there is a vector $u \in R^{p - 1}$ such that the matrix $(\begin{matrix} 1 & u^{⊤} \\ u & A + u u^{⊤} \end{matrix}) \in S_{+} (p, r) is in general position.$ Therefore, there is a matrix $P \in S_{+ +} (p)$ such that $P = (\begin{matrix} 1 & u^{⊤} \\ u & Q \end{matrix}) \overset{G}{=} (\begin{matrix} 1 & u^{⊤} \\ u & A + u u^{⊤} \end{matrix}), for some matrix Q \in S_{+ +} (p - 1) .$ Thus, $A + u u^{⊤} \overset{G - v}{=} Q$ and consequently $A \overset{G - v}{=} Q - u u^{⊤} \in S_{+ +} (p - 1)$ . □

Corollary 3.1

Let $H$ be a subgraph of $G$ . Then $r (H) \leq r (G)$ .

Proof

Every subgraph of $G$ is obtained by removing successively a finite number of vertices and edges from $G$ . Therefore, it suffices to show that $r (G - v) \leq r (G)$ , for each vertex $v \in V$ , and $r (G - e) \leq r (G)$ , for each edge $e \in E$ . The latter is obvious using the condition $(⋆)$ in Proposition 3.1. □

A graph $G$ is said to be the clique sum of two subgraphs $G_{1} = (V_{1}, E_{1})$ and $G_{2} = (V_{2}, E_{2})$ if $V = V_{1} \cup V_{2}, E = E_{1} \cup E_{2}$ and $G [V_{1} \cap V_{2}]$ is a complete graph (including the empty graph). We write this as $G = G_{1} \oplus_{V_{1} \cap V_{2}} G_{2}$ . The following proposition is now immediate using a standard completion process given by [5] or [10].

Proposition 3.4

Suppose $G = G_{1} \oplus_{V_{1} \cap V_{2}} G_{2}$ . Then $r (G) = max {r (G_{1}), r (G_{2})}$ . In particular, if $G_{1}, \dots, G_{k}$ are all the connected components of $G$ , then $r (G) = max {r (G_{i}) : i = 1, \dots, k} .$

Remark 3.2

In relation to the D&L problem (I) we can show (by slightly modifying our proofs and using the alternative description of $r_{w} (G)$ given by Remark 3.1) that the properties of the Gaussian rank discussed in this subsection are also valid properties of the weak Gaussian rank. This fact however will not be used in the paper.

4. The proof of Theorem 1.1

In this section we prove Theorem 1.1, that is, the bounds given by Eq. (1.1). The lower and the upper bounds for $r (G)$ are proved in separate subsections.

4.1. The upper bound: $r (G) \leq δ^{*} (G) + 1$

First we state and prove the following key lemma.

Lemma 4.1

Let $v \in V$ be a vertex of $G$ . If $r (G - v) \geq {deg}_{G} (v) + 1$ , then $r (G) = r (G - v)$ .

Proof

If ${deg}_{G} = 0$ , then by Proposition 3.4 $r (G) = max {1, r (G - v)} = r (G - v)$ . Thus we assume that ${deg}_{G} (v) \geq 1$ . For convenience, let us assume that $v = 1$ and $ne (v) = {2, \dots, {deg}_{G} (v) + 1}$ . Note that $V (G - v) = {2, \dots, p}$ . Now we set $r_{0} = r (G - v), τ = {2, \dots, r_{0}} and γ = V (G - v) ∖ τ .$ Note that $ne (v) \subseteq τ$ since $r_{0} \geq {deg}_{G} (v) + 1$ . Let $A \in S_{+} (p, r_{0})$ . We need to show that there is a matrix $P \in S_{+ +} (p)$ such that $P \overset{G}{=} A$ . For this, we assume that $A$ is a correlation matrix and therefore can be partitioned as $A = (\begin{matrix} 1 & u^{⊤} \\ u & B \end{matrix}) = (\begin{matrix} 1 & u {[τ]}^{⊤} & u {[γ]}^{⊤} \\ u [τ] & A [τ] & A [τ, γ] \\ u [γ] & A [γ, τ] & A [γ] \end{matrix}), where B = (\begin{matrix} A [τ] & A [τ, γ] \\ A [γ, τ] & A [γ] \end{matrix}) .$ Note also that $u \in R^{p - 1}$ and $B \in S_{+} (p - 1, r_{0})$ is in general position. Let us set $x_{τ} = A {[τ]}^{- 1} u [τ]$ . Now we have $(\begin{matrix} 1 & u {[τ]}^{⊤} \\ u [τ] & A [τ] \end{matrix}) ≻ 0 and therefore 1 - u {[τ]}^{⊤} A {[τ]}^{- 1} u [τ] > 0 .$ This implies that $x_{τ}^{⊤} A [τ] x_{τ} = x_{τ}^{⊤} B [τ] x_{τ} < 1$ . By Part (a) of Lemma 2.3 and Remark 2.2, if we set $w = B x$ , then $B - w w^{⊤} \in S_{+} (p - 1, r_{0})$ is in general position. Therefore, there is a matrix $Q \in S_{+ +} (p - 1)$ such that $Q \overset{G - v}{=} B - w w^{⊤}$ . Let us set $P = (\begin{matrix} 1 & w^{⊤} \\ w & Q + w w^{⊤} \end{matrix}) \in S_{+ +} (p) .$ By Eq. (3.1) it is clear that $Q + w w^{⊤} \overset{G - v}{=} B$ . Also, since $w [τ] = A [τ] x_{τ} = u [τ]$ and $ne (v) \subseteq τ$ we have $P_{1 j} = A_{1 j}$ whenever $j \in ne (v)$ . Therefore, $P \overset{G}{=} A$ . □

We now prove that the upper bound

r (G) \leq δ^{*} (G) + 1

holds.

Proof

By mathematical induction let us assume that for any graph $H$ with fewer than $p$ vertices $r (H) \leq δ^{*} (H) + 1$ . Now let $G$ be a graph with $p$ vertices. We assume without loss of generality that $p \geq 2$ . Let $v \in V$ such that ${deg}_{G} (v) = δ (G)$ . On the contrary, let us assume that $r (G) \geq δ^{*} (G) + 2$ , then by Part (a) of Proposition 3.3 we obtain $r (G - v) \geq r (G) - 1 \geq δ^{*} (G) + 1 \geq {deg}_{G} (v) + 1 .$ Lemma 4.1 now implies that $r (G) = r (G - v)$ . The induction hypothesis then implies that $r (G) = r (G - v) \leq δ^{*} (G - v) + 1$ . The fact that $δ^{*} (G) = max {δ (G), δ^{*} (G - v)}$ [15] implies that $r (G) \leq δ^{*} (G) + 1$ . □

Remark 4.1

Note that Lemma 4.1 also holds for the weak Gaussian rank, that is, for any graph $G$ if $r_{w} (G - v) \geq {deg}_{G} + 1$ , then $r_{w} (G) = r_{w} (G - v)$ . Consequently, this implies $r_{w} (G) \leq δ^{*} (G) + 1$ . But the latter more easily follows from the fact that $r_{w} (G) \leq r (G) \leq δ^{*} (G) + 1$ .

4.2. The lower bound: $κ^{*} (G) + 1 \leq r (G)$

To prove that this lower bound holds we mainly rely on Lovász–Saks–Schrijver’s Theorem in [11]. This theorem associates the connectivity of a graph with its certain geometric representations. More details are as follows. Let $G = (V, E)$ be graph. An orthonormal representation of $G$ in $R^{d}$ is a function $ϕ : V \to R^{d}$ assigning a unit vector $u_{i}$ to each vertex $i \in V$ such that $u_{i}^{⊤} u_{j} = 0$ whenever $i j \notin E$ . In words, $ϕ$ assigns to each vertex a unit vector in $R^{d}$ such that the vectors assigned to nonadjacent vertices are orthogonal. Now a general-position orthonormal representation of $G$ in $R^{d}$ is an orthonormal representation $ϕ$ in $R^{d}$ such that the $p$ assigned vectors $ϕ (1) = u_{1}, \dots, ϕ (p) = u_{p}$ are in general position in $R^{d}$ . The next theorem is crucial for proving the lower bound in Theorem 1.1.

Theorem 4.1

Lovász–Saks–Schrijver [11], [12]

If $G = (V, E)$ is a graph with $p$ vertices, then the following are equivalent:

(i)
$G$ is $(p - d)$ -connected;
(ii)
$G$ has a general-position orthonormal representation in $R^{d}$ .

Remark 4.2

We note that in the proof of $(i) ⟹ (2)$ in [11] it is shown that the set of general-position orthonormal representations in $R^{d}$ is a subvariety of $R^{p d}$ and, consequently, of probability zero.

We now proceed to prove that the lower bound

κ^{*} (G) + 1 \leq r (G)

holds.

Proof

Since $r (H) \leq r (G)$ for every subgraph $H$ of $G$ , in light of Part (a) and Part (b) in Remark 2.1, it suffices to show that for every graph $G$ we have $r (G) \geq κ (G) + 1$ . First we set $k = κ (G)$ and $d = p - k$ . By Theorem 4.1 there are general-position unit vectors $u_{1}, \dots, u_{p} \in R^{d}$ such that $u_{i}^{⊤} u_{j} = 0$ for each $i j \notin E$ . Let $Ω = {(u_{i}^{⊤} u_{j})}_{1 \leq i, j \leq p}$ . By Lemma 2.2 we have $Ω \in S_{+} (p, d)$ is in general position. Let $w_{1}, \dots, w_{k} \in R^{p}$ be a basis of $Null (Ω)$ and set $A = (\begin{matrix} w_{1} & \dots & w_{k} \end{matrix}) (\begin{matrix} w_{1}^{⊤} \\ ⋮ \\ w_{k}^{⊤} \end{matrix}) \in S_{+} (p, k) .$ The proof of Lemma 6.3 in [18] shows that the matrix $A \in S_{+} (p, k)$ is in general position. Let $P \in S (p)$ such that $P \overset{G}{=} A$ . Then $tr (P Ω) = \sum_{i j \in E} P_{i, j} Ω_{i, j} = \sum_{i j \in E} A_{i, j} Ω_{i, j} = tr (A Ω) = 0 (note that A Ω = 0) .$ This shows that $P \notin S_{+ +} (p)$ , since $S_{+ +} (p)$ is a self dual cone, that is, $S_{+ +} (p) = {Q \in S (p) : tr (Q B) > 0 for every B \in S_{+} (p) ∖ {0}},$ and $Ω \in S_{+} (p) ∖ {0}$ . Thus there is no matrix $P \in S_{+ +} (p)$ such that $P \overset{G}{=} A$ . This shows that $r (G) \geq κ (G) + 1$ . □

Remark 4.3

Note that the proof of lower bound above does not imply that $κ^{*} (G) + 1 \leq r_{w} (G)$ . This is because by using Lovász–Saks–Schrijver’s Theorem, in light of Remark 4.2, the set of all general position matrices $A \in S_{+} (p, κ (G))$ in our proof is of probability zero, and this is not sufficient to conclude $κ^{*} (G) > r_{w} (G)$ .

5. Some applications of Theorem 1.1

A useful application of the bounds given by Theorem 1.1 is that when the lower and upper bounds are equal the Gaussian rank is exactly determined. In this section we briefly discuss for which graphs $κ^{*} (G) = δ^{*} (G)$ . We also use Theorem 1.1 to obtain a sharp numerical upper bound for the Gaussian ranks of the so-called planar graphs.

5.1. Gaussian ranks of symmetric graphs

Let $G = (V, E)$ be a graph. A permutation $σ : V \to V$ is said to be an automorphism of $G$ if $i j \in E ⟹ σ (i) σ (j) \in E$ . The graph $G$ is said to be symmetric if for any two edges $i j$ and $i^{'} j^{'} \in E$ there is an automorphism $σ$ of $G$ such that $σ (i) = i^{'}$ and $σ (j) = j^{'}$ (please see Chapter 27 in [7] for a detailed discussion of symmetric graphs). For example, one can check that the graphs given by Fig. 2(a) and (b) are symmetric. The symmetric property in particular implies that $G$ is regular, that is, there is a positive integer $k$ such that ${deg}_{G} (v) = k$ for every vertex $v \in V$ . An interesting feature of a symmetric graph $G$ is that $κ (G) = δ (G)$ . This consequently implies that $κ^{*} (G) = δ^{*} (G)$ . Theorem 1.1 therefore implies that for a symmetric graph the Gaussian rank is exactly determined as (5.1) $r (G) = κ^{*} (G) = δ^{*} (G) .$ Note that Eq. (5.1) can hold for many non-symmetric graphs as well, such as the regular graph given by Fig. 2(c) or even non-regular graphs such as grids. To the best of our knowledge the class of all graphs $G$ satisfying $κ^{*} (G) = δ^{*} (G)$ , or even $κ (G) = δ (G)$ , is not fully characterized.

5.2. Gaussian ranks of random graphs

A random graph $G (ϵ)$ in the Erdös–Rényi model is a graph in which the edges are selected by a sequence of (independent) Bernoulli trials with probability $0 < ϵ < 1$ [7].

Theorem 5.1 Bollobás et al.

Almost surely for every random graph $G (ϵ)$ we have $κ (G (ϵ)) = δ (G (ϵ))$ .

The next result now follows from Theorem 5.1 above and Theorem 1.1.

Corollary 5.1

Almost surely for every random graph $G (ϵ)$ we have $r (G (ϵ)) = κ^{*} (G (ϵ)) = δ^{*} (G (ϵ)) .$ This in particular implies that almost surely for every random graph $G (ϵ)$ we have $r_{w} (G (ϵ)) \leq κ^{*} (G) + 1 .$

5.3. On the Gaussian ranks of planar graphs

A planar graph is a graph that can be drawn in a plane without the edges crossing each other. In graph theory it is well-known that planar graphs are at most 5-degenerate, that is, $δ^{*} (G) \leq 5$ if $G$ is planar. Theorem 1.1 therefore implies that when $G$ is a planar graph $r (G) \leq 6$ . Note that the upper bound 6 is tight. For this, consider the planar graph $G$ in Fig. 3. Since $κ^{*} (G) = δ^{*} (G) = 5$ by Eq. (5.1) we have $r (G) = 6$ .

Remark 5.1

We note that Gross and Sullivant in [6] prove that for every planar graph $G, r_{w} (G) \leq 4$ . Comparing this with the tight upper bound $r (G) \leq 6$ shows that for some graphs the week Gaussian rank can be strictly less than the Gaussian rank. For example for the graph $G$ given by Fig. 3 we have $r_{w} (G) = 4 < r (G) = 6$ .

Acknowledgments

Special thanks to Steen Andersson, Gérard Letac, Hélène Massam and Bala Rajaratnam for helpful discussions and feedback. I am also grateful to the referees for their detailed, helpful comments.

Appendix.

Proof of Lemma 2.1

First we note that randomly selecting $p$ vectors in $R^{d}$ is equivalent to randomly selecting a matrix $W \in R^{d \times p}$ . Let $X = (x_{i, j})$ denote a $d \times p$ matrix of variables. For each $α = {i_{1}, \dots, i_{d}} \subseteq [p]$ we define the polynomial $p_{α} (X) = det (\begin{matrix} x_{1, i_{1}} & \dots & x_{1, i_{d}} \\ ⋮ & ⋱ & ⋮ \\ x_{d, i_{1}} & \dots & x_{d, i_{d}} \end{matrix}) and V_{α} = {W \in R^{d \times p} : p_{α} (W) = 0} .$ Each $V_{α} ⊊ R^{d \times p}$ is an algebraic set and its (Lebesgue) measure is therefore zero. Thus, $\Pr (W \in R^{d \times p} ∖ ⋃_{α} V_{α}) = 1$ . This completes the proof, since each $d$ columns of a matrix $W \in R^{d \times p} ∖ ⋃_{α} V_{α}$ are linearly independent. □

Proof of Lemma 2.2

$(⟹)$
Suppose $A \in S_{+} (p, d)$ . Let each pair of $(λ_{1}, u_{1}), \dots, (λ_{d}, u_{d})$ denote a positive eigenvalue and its corresponding eigenvector of $A$ . Let us set $w_{i} = \sqrt{λ_{i}} u_{i}$ , for $i = 1, \dots, d$ . Then we have (A.1) $A = \sum_{i = 1}^{d} w_{i} w_{i}^{⊤} = W^{⊤} W, where W = (\begin{matrix} w_{1}^{⊤} \\ ⋮ \\ w_{d}^{⊤} \end{matrix}) = (\begin{matrix} v_{1} & \dots & v_{p} \end{matrix}) \in R^{d \times p} .$ Note that $v_{1}, \dots, v_{p} \in R^{d}$ are the columns of $W$ . Suppose for $α = {i_{1}, \dots, i_{d}} \subseteq [p]$ the vectors $v_{i_{1}}, \dots, v_{i_{d}}$ are linearly dependent. Thus, there is a non-zero vector $x_{α} = {(x_{i_{1}}, \dots, x_{i_{d}})}^{⊤} \in R^{d}$ such that $\sum_{i \in α} x_{i} v_{i} = W (\begin{matrix} x_{α} \\ 0 \end{matrix}) = 0 ⟹ W^{⊤} W (\begin{matrix} x_{α} \\ 0 \end{matrix}) = A (\begin{matrix} x_{α} \\ 0 \end{matrix}) = 0 .$ Thus $A [α] x_{α} = 0$ and consequently $A [α]$ is singular.
$(⟸)$
Suppose $v_{1}, \dots, v_{p} \in R^{d}$ are in general position. Let $A$ be defined as in Eq. (2.2). Then for each $α = {i_{1}, \dots, i_{d}} \subseteq [p]$ the submatrix $A [α] = (\begin{matrix} v_{i_{1}}^{⊤} \\ ⋮ \\ v_{i_{d}}^{⊤} \end{matrix}) (\begin{matrix} v_{i_{1}} & \dots & v_{i_{d}} \end{matrix}) is obviously non-singular.$ □

Proof of Corollary 2.1

Let $X = (\begin{matrix} x_{1}^{⊤} \\ ⋮ \\ x_{n}^{⊤} \end{matrix}) = (\begin{matrix} y_{1} & \dots & y_{p} \end{matrix}) \in R^{n \times p}$ be the data matrix. Then by Lemma 2.1 with probability one $y_{1}, \dots, y_{p}$ , the columns of $X$ , are in general position in $R^{n}$ . The result now follows from Lemma 2.2, since whenever the columns of $X$ are in general position $S = 1 / n (X^{⊤} X)$ is also in general position. □

References

[1]
Søren L. Buhl
On the existence of maximum likelihood estimators for graphical Gaussian models
Scand. J. Stat., 20 (3) (1993), pp. 263-270
Google Scholar
[2]
Joachim Dahl, Lieven Vandenberghe, Vwani Roychowdhury
Covariance selection for nonchordal graphs via chordal embedding
Optim. Methods Softw., 23 (4) (2008), pp. 501-520
CrossRef View in Scopus Google Scholar
[3]
Arthur P. Dempster
Covariance selection
Biometrics (1972), pp. 157-175
CrossRef Google Scholar
[4]
Morris L. Eaton, Michael D. Perlman
The non-singularity of generalized sample covariance matrices
Ann. Statist., 1 (1973), pp. 710-717
Google Scholar
[5]
Robert Grone, Charles R. Johnson, Eduardo M. de Sá, Henry Wolkowicz
Positive definite completions of partial Hermitian matrices
Linear Algebra Appl., 58 (1984), pp. 109-124
View PDF View article View in Scopus Google Scholar
[6]
Elizabeth Gross, Seth Sullivant, The maximum likelihood threshold of a graph. 2014. ArXiv:1404.6989.
Google Scholar
[7]
Jonathan L. Gross, Jay Yellen (Eds.), Handbook of Graph Theory, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL (2004)
[8]
Trevor Hastie, Robert Tibshirani, Jerome Friedman
The Elements of Statistical Learning (second ed.), Springer Series in Statistics, Springer, New York (2009)
Data mining, inference, and prediction
Google Scholar
[9]
Alston S. Householder
The Theory of Matrices in Numerical Analysis
Dover Publications, Inc., New York (1975)
Reprint of 1964 edition
Google Scholar
[10]
Steffen L. Lauritzen
Graphical Models, Oxford Statistical Science Series, vol. 17, The Clarendon Press, Oxford University Press, New York (1996)
Oxford Science Publications
Google Scholar
[11]
L. Lovász, M. Saks, A. Schrijver
Orthogonal representations and connectivity of graphs
Linear Algebra Appl., 114/115 (1989), pp. 439-454
View PDF View article View in Scopus Google Scholar
[12]
L. Lovász, M. Saks, A. Schrijver
A correction: orthogonal representations and connectivity of graphs
[Linear Algebra Appl. 114/115 (1989), 439–454; MR0986889 (90k:05095)]
Linear Algebra Appl., 313 (1-3) (2000), pp. 101-105
View PDF View article View in Scopus Google Scholar
[13]
James D. Malley
Statistical and algebraic independence
Ann. Statist., 11 (1) (1983), pp. 341-345
Google Scholar
[14]
Bernard Mans, Luke Mathieson
On the treewidth of dynamic graphs
Theoret. Comput. Sci., 554 (2014), pp. 217-228
View PDF View article View in Scopus Google Scholar
[15]
David W. Matula
Subgraph connectivity numbers of a graph
Theory and Applications of Graphs (Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976), Lecture Notes in Math., vol. 642, Springer, Berlin (1978), pp. 371-383
Google Scholar
[16]
T.P. Speed, H.T. Kiiveri
Gaussian Markov distributions over finite graphs
Ann. Statist., 14 (1) (1986), pp. 138-150
Google Scholar
[17]
Caroline Uhler
Geometry of maximum likelihood estimation in Gaussian graphical models
Ann. Statist., 40 (1) (2012), pp. 238-261
CrossRef View in Scopus Google Scholar
[18]
Hein van der Holst
Graphs with magnetic Schrödinger operators of low corank
J. Combin. Theory Ser. B, 84 (2) (2002), pp. 311-339
View PDF View article View in Scopus Google Scholar
[19]
Fuzhen Zhang
The Schur Complement and its Applications, Numerical Methods and Algorithms, vol. 4, Springer-Verlag, New York (2005)
Google Scholar

Cited by (6)

Maximum likelihood thresholds of generic linear concentration models
2023, arXiv
Maximum likelihood thresholds via graph rigidity
2021, arXiv
Maximum Likelihood Threshold and Generic Completion Rank of Graphs
2019, Discrete and Computational Geometry
The maximum likelihood threshold of a graph
2018, Bernoulli
Gaussian Graphical Models: An Algebraic and Geometric Perspective
2017, arXiv
Maximum likelihood threshold and generic completion rank of graphs
2017, arXiv

¹: Throughout the paper, we always assume that the observations are independent and identically distributed.

[1] [1]
Søren L. Buhl
On the existence of maximum likelihood estimators for graphical Gaussian models
Scand. J. Stat., 20 (3) (1993), pp. 263-270
Google Scholar

[2] [2]
Joachim Dahl, Lieven Vandenberghe, Vwani Roychowdhury
Covariance selection for nonchordal graphs via chordal embedding
Optim. Methods Softw., 23 (4) (2008), pp. 501-520
CrossRef View in Scopus Google Scholar

[3] [3]
Arthur P. Dempster
Covariance selection
Biometrics (1972), pp. 157-175
CrossRef Google Scholar

[4] [4]
Morris L. Eaton, Michael D. Perlman
The non-singularity of generalized sample covariance matrices
Ann. Statist., 1 (1973), pp. 710-717
Google Scholar

[5] [5]
Robert Grone, Charles R. Johnson, Eduardo M. de Sá, Henry Wolkowicz
Positive definite completions of partial Hermitian matrices
Linear Algebra Appl., 58 (1984), pp. 109-124
View PDF View article View in Scopus Google Scholar

[6] [6]
Elizabeth Gross, Seth Sullivant, The maximum likelihood threshold of a graph. 2014. ArXiv:1404.6989.
Google Scholar

[7] [7]
Jonathan L. Gross, Jay Yellen (Eds.), Handbook of Graph Theory, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL (2004)

[8] [8]
Trevor Hastie, Robert Tibshirani, Jerome Friedman
The Elements of Statistical Learning (second ed.), Springer Series in Statistics, Springer, New York (2009)
Data mining, inference, and prediction
Google Scholar

[9] [9]
Alston S. Householder
The Theory of Matrices in Numerical Analysis
Dover Publications, Inc., New York (1975)
Reprint of 1964 edition
Google Scholar

[10] [10]
Steffen L. Lauritzen
Graphical Models, Oxford Statistical Science Series, vol. 17, The Clarendon Press, Oxford University Press, New York (1996)
Oxford Science Publications
Google Scholar

[11] [11]
L. Lovász, M. Saks, A. Schrijver
Orthogonal representations and connectivity of graphs
Linear Algebra Appl., 114/115 (1989), pp. 439-454
View PDF View article View in Scopus Google Scholar

[12] [12]
L. Lovász, M. Saks, A. Schrijver
A correction: orthogonal representations and connectivity of graphs
[Linear Algebra Appl. 114/115 (1989), 439–454; MR0986889 (90k:05095)]
Linear Algebra Appl., 313 (1-3) (2000), pp. 101-105
View PDF View article View in Scopus Google Scholar

[13] [13]
James D. Malley
Statistical and algebraic independence
Ann. Statist., 11 (1) (1983), pp. 341-345
Google Scholar

[14] [14]
Bernard Mans, Luke Mathieson
On the treewidth of dynamic graphs
Theoret. Comput. Sci., 554 (2014), pp. 217-228
View PDF View article View in Scopus Google Scholar

[15] [15]
David W. Matula
Subgraph connectivity numbers of a graph
Theory and Applications of Graphs (Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976), Lecture Notes in Math., vol. 642, Springer, Berlin (1978), pp. 371-383
Google Scholar

[16] [16]
T.P. Speed, H.T. Kiiveri
Gaussian Markov distributions over finite graphs
Ann. Statist., 14 (1) (1986), pp. 138-150
Google Scholar

[17] [17]
Caroline Uhler
Geometry of maximum likelihood estimation in Gaussian graphical models
Ann. Statist., 40 (1) (2012), pp. 238-261
CrossRef View in Scopus Google Scholar

[18] [18]
Hein van der Holst
Graphs with magnetic Schrödinger operators of low corank
J. Combin. Theory Ser. B, 84 (2) (2002), pp. 311-339
View PDF View article View in Scopus Google Scholar

[19] [19]
Fuzhen Zhang
The Schur Complement and its Applications, Numerical Methods and Algorithms, vol. 4, Springer-Verlag, New York (2005)
Google Scholar

Outline

Cited by (6)

Figures (3)

Journal of Multivariate Analysis

Abstract

AMS subject classification

Keywords

1. Introduction

2. Preliminaries