[C++] [Python] derive, implement, and test removing/deleting rows from a cholesky factor

[suntzu86]

RELATED TO: (GH-192) inserting rows into Cholesky

It's probably easiest to prototype this in Python and then implement in C++.

Note that this is trivial if you're removing the last row/column--just delete them, 0 work. For all other rows/cols it's more complex.

This is incredibly useful for speeding up LeaveOneOut log likelihood. That method scales very poorly right now and this would speed it up by O(N_{sampled}). It could also imaginably have uses in heuristic EI solvers.

The SCHEX method in LINPACK takes a cholesky factor, swaps 2 rows, and then applies Givens rotations to make it triangular again. http://www.math.utah.edu/software/linpack/linpack/schex.html

So the simplest idea:

L*L^T = A
permute the rows/cols of L: Lnew = P * L * P^T
remove the last row/column of Lnew (see note above)
now Lnew is *not * triangular; use orthogonal transforms (e.g., linpack SCHEX) to restore the shape and return

Givens (and householder, orthogonal matrix ops) rotations are extremely well-conditioned so this method should work well.

See (GH-192) for Davis 2005, which rephrase deletion into a rank-1 update (performable directly via cholesky-like derivation, householder, or givens). I THINK this is boils down to the same thing that I just suggested. Then this paper: Gill_1974_Methods_for_Modifying_Matrix_Factorizations http://www.stanford.edu/group/SOL/papers/ggms74.pdf goes over methods for performing rank-1 updates on a cholesky factor. I think the Givens method (C3) is the same as: http://en.wikipedia.org/wiki/Cholesky_decomposition#Updating_the_decomposition

This link indicates you can do the same with Househoulder matrices (also in Gill 1974) and it's more efficient: http://stats.stackexchange.com/questions/85661/cholesky-update-for-removing-row I'm guessing this is analogous to the QR process (in which case householder is better conditioned too).

Implemented as choldelete in octave (also part of "cholmod" package, both open source). Both should be similar to the (more general) qrdelete (matlab).