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

[suntzu86]

RELATED TO: GH-191 (deleting rows from cholesky)

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

This would make computing covariance matrices (and cholesky factors) from adding 1 point at a time go from O(N_{sampled}^4) to O(N_{sampled}^3) (particularly useful if we save state btwn MOE calls). This also speeds up heuristic EI solvers by a similar amount (since the heuristics modify the covariance matrix after each step). Plus, it's cool.

Davis_2005_Row_Modification_of_Sparse_Cholesky_Factorization http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.9.6702&rep=rep1&type=pdf Rephrases row addition & deletion from cholesky factor as rank-1 updates. I'm not entirely sure if these methods are numerically stable, but I think so.

Their method is general, allowing insertion anywhere. If we only insert as the last row, things simplify a lot (matlab-ish notation):

start: L_{1:n, 1:n} * L_{1:n,1:n}^T = A_{1:n, 1:n}
z = A_{1:n+1, n+1} % size n+1
u = zeros(n+1)
u_{1:n} = L_{:, :} \ z_{:}
u_{n+1} = sqrt(z_{n+1} - u_{1:n}^T * u_{1:n})
Lnew_{1:n,1:n} = L_{:, :}
Lnew_{1:n, n+1} = 0
Lnew_{n+1, 1:n+1} = u_{:}

Note: if n = 0, return the sqrt of u_{1} Note: if u_{n+1} is negative or 0, the new matrix is indefinite or semidefinite, respectively.

Note: it wouldn't be a huge leap to implement the fully general version. It requires the same machinery as GH-191 so let's do this simpler version first.

This is also implemented as cholinsert in octave (also in the cholmod package, both opensource).