Learning Graph Structures, Graphical Lasso and Its Applications - Part 2: Formulation

As a first step, now we must figure out how to formulate our problem as a mathematical one so that we know where its solution will likely fall.

As when working with any other mathematical model, we have to make some simplifying assumptions, which is a necessary evil, but do recall the saying “all models are wrong, but some are useful”.

So here we will assume each of our N observations will be a p-dimensional Gaussian. Cast into one of our examples in the previous section, this means, e.g., that we record the closing prices of p different tickers for N days, which basically results in an N*p data matrix for us to work with.

For those curious minds, here are some justifications why normality is assumed, not only here and all over the place:

1. It leads to mathematical simplicity – in the parlance of plebeians like you and me, this means trying to skirt complex/messy math. Yes, it does conduce to easier geometric interpretation and easier parameter estimation.

2. Remember Central Limit Theorem? Sum of lots of independent statistical distributions converge to normal distribution eventually. We rarely encounter monads these days and the features (prices, etc) that we work with are of course no exception.

3. Remember the Second Law of Thermodynamics? The total entropy of an isolated system never decreases and always increases in non-ideal condition (read, in almost all real-world conditions). Normal distribution turns out to be the one distribution with maximum entropy among all real-valued distributions with specified mean and covariance.

Note there seems some interesting link between 2 and 3 above.

Now that we have formulated our data matrix and the distribution of the data, how do we go from here to the construction of the undirected graph we want?

The key lies in the fact that there is a mapping from the inverse covariance matrix of our data to the undirected graph that we want. Let us show this in the next section.