qrCholesky
public Gram.Cholesky qrCholesky(java.util.ArrayList<java.lang.Integer> dropped_cols,
boolean standardized)
Compute Cholesky decompostion by computing partial QR decomposition (R == LU).
The advantage of this method over the standard solve is that it can deal with Non-SPD matrices.
Gram matrix comes out as Non-SPD if we have collinear columns.
QR decomposition can identify collinear (redundant) columns and remove them from the dataset.
QR computation:
QR is computed using Gram-Schmidt elimination, using Gram matrix instead of the underlying dataset.
Gram-schmidt decomposition can be computed as follows: (from "The Eelements of Statistical Learning")
1. set z0 = x0 = 1 (Intercept)
2. for j = 1:p
for l = 1:j-1
gamma_jl = dot(x_l,x_j)/dot(x_l,x_l)
zj = xj - sum(gamma_j[l]*x_l)
if(zj ~= 0) xj was redundant (collinear)
Zjs are orthogonal projections of xk and form base of the X space. (dot(z_i,z_j) == 0 for i != j)
In the end, gammas contain (Scaled) R from the QR decomp which is == LU from cholesky decomp.
Note that all of these operations can be be computed from the Gram matrix only, as gram matrix contains
dot(x_i,x_j) for i = 1..N, j = 1..N
We can obviously compute gamma_lk directly, instead of replacing xk with zk, we fix the gram matrix.
When doing that, we need to replace dot(xi,xk) with dot(xi,zk) for all i.
There are two cases,
1) dot(xk,xk) -> dot(zk,zk)
dot(xk - sum(gamma_l*x_l,xk - sum(gamma_l*x_l)
= dot(xk,xk) - 2* sum(gamma_l*dot(x_i,x_k) + sum(gamma_l*sum(gamma_k*dot(x_l,x_k)))
(can be simplified using the fact that dot(zi,zj) == 0 for i != j
2) dot(xi,xk) -> dot(xi,zk) for i != k
dot(xi, xj - sum(gamma_l*x_l))
= dot(xi, xj) - dot(xi,sum(gamma_l*x_l))
= dot(xi,xj) - sum(gamma_l*dot(xi,x_l)) (linear combination
The algorithm then goes as follows:
for j = 1:n
for l = 1:j-1
compute gamma_jl
update gram by replacing xk with zk = xk- sum(gamma_jl*s*xl);
- Parameters:
dropped_cols - - empty list which will be filled with collinear columns removed during computation- Returns:
- Cholesky - cholesky decomposition fo the gram