1
$\begingroup$

I'm trying to develop an estimator for the concentration matrix of a Gaussian Graphical Model. I've become stuck in trying to find conditions for the estimator to exist. I have a sufficient condition and I think it is also necessary, but I can't prove it. I'd greatly appreciate any suggestions on how to proceed.

Problem statement

Let $V$ be an arbitrary $k$-dimensional vector subspace of $\mathbb R^n$. Let $X\in\mathbb R^{n\times n}$ be a symmetric matrix whose column space is contained in $V$. Now I add constraints to X: given some pairs $(i,j)$ such that $1\leq i < j\leq n$, I need $X_{ij}=0$. How many of these zero constraints can I satisfy before the only solution is $X=0$?

I've found a sufficient condition for a non-zero solution to exist: the number of constraints $q$ must satisfy $q< \frac{k(k+1)}{2}$. I think its also a necessary condition, but I could use a hand in showing that.

Proof of sufficient condition

Let $M_V$ be the space of symmetric $n\times n$ matrices whose column space is contained in $V$. An orthonormal basis for $M_V$ is $\{\frac{1}{2}Q(e_ie_j^T+e_je_i^T)Q^T : 1\leq i \leq j \leq n\}$ where the columns of $Q\in\mathbb R^{n\times k}$ form an orthonormal basis for $V$ and $e_i$ are the standard basis vectors for $\mathbb R^k$, so $\dim(M_V)=\frac{k(k+1)}{2}$.

Let $M_X$ be the space of symmetric $n\times n$ matrices that satisfy the $q$ zero constraints. Now suppose no non-zero $X$ satisfying the constraints exist: this implies $M_V\cap M_X=\{0\}$. Hence $\dim(M_V+M_X) = \dim(M_V)+\dim(M_X) = \frac{k(k+1)}{2}+\left(\frac{n(n+1)}{2}-q\right)$. Since $M_V+M_X$ is contained within the space of symmetric $n\times n$ matrices, its dimension is bounded by $\frac{n(n+1)}{2}$. Thus "no non-zero $X$" implies $q\geq\frac{k(k+1)}{2}$.

Improve this question
$\endgroup$
1
  • $\begingroup$ I should add that $V$ is a random subspace whose distribution is uniform over all possible $k$-dimensional subspaces of $\mathbb R^n$, while the zero constraints are independent of $V$. There are pathological choices of $V$ where $q<\frac{k(k+1)}{2}$ is not a necessary condition (e.g, we could have $M_V\subseteq M_X$). However, I think these pathological choices have probability zero. $\endgroup$
    – Peter
    Commented Mar 10, 2012 at 16:59

1 Answer 1

Reset to default
1
$\begingroup$

Just to clarify: are the $q$ entries $(i,j)$ fixed, or are they also chosen uniformly at random over all possible sets of q entries of an $n \times n$ matrix? (This is not so important though).

Assuming that these $q$'s are fixed, here's a proof of sufficiency: suppose $q = k(k+1)/2$, $k < n$. Fix $q$ entries $(i,j)$, and consider the set $M$ of all $n \times n$ matrices with these entries being $0$. Then for any $X \in M$, I claim that the column space of $X$ has codimension at most k-1, and this occurs precisely when up to a permutation, $X$ is a block matrix with a $k \times k$ zero-block that contains the diagonal.

It then follows that the column space of any such $X$ intersects non-trivially with a subspace of codimension $n-k$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you for your answer. The $q$ entries are indeed fixed. The original question proves that $q<k(k+1)/2$ is sufficient for $M_V\cap M_X$ to have a non-trivial intersection. Your answer seems to extend the result to $q\leq k(k+1)/2$. This is indeed helpful, but what I really need is a necessary condition for $M_V\cap M_X$ to have a non-trivial intersection. Also, I am having some difficulty following your proof. You write "I claim that the column space of X has codimension at most k-1", but this assertion isn't obvious to me. Could you please explain why it is true? Thank you. $\endgroup$
    – Peter
    Commented Apr 13, 2012 at 8:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .