The paper incorrectly states that the cost of solving the set of
linear equation is O(N^2).  The complexity is actually 1/3*O(N^3) in this
case, assuming that a Cholesky decomposition is used to solve the
system of equations, as is typically done for the type of matrices
used in these papers.  As lead author on these papers, I apologize for
this mistake.

The computation is actually O(N^3) because the Choleksy decomposition
is itself 1/3*O(N^3).  This factorization is then followed by an
O(N^2) set of substitution steps.

It should be noted that this is still much more efficient than
inverting the precision matrix, which will have the rough complexity
of O(N^3), as the series of substitution steps must be repeated n
times. The amount of memory required for storing the covariance matrix
of whole images will also be prohibitive.  It may be possible to avoid
inverting the precision matrix by performing repeated O(N^3)
factorizations of modified versions of the precision matrix, however,
this will still be much slower than the discriminative training
approach.


-- Marshall Tappen 
December 14, 2009