Python package for making a rank-deficient sparse matrix full rank

Question

I am running a regression with a sparse rank-deficient matrix where many columns are correlated with others. At the moment, I remove all columns with a correlation over 0.8. The matrix has 12k columns and 35k observations, and I drop about 2k columns.

For example, my text may mention cities and I have three highly correlated n-grams: "New York", "York City", and "New York City". At the moment, I am dropping all three of them and I lose one dimension in the rank of the matrix. I am looking for a package that keeps makes the matrix invertible and keeps its rank as high as possible; and whose transformation on that matrix can be applied to a single row, because I want to predict the values when a single new observation arrives.

I found the PyPi package collinearity. Converting the sparse matrix to a dense matrix is fast, but the collinearity package on it is prohibitively slow (several hours). This is probably because, from reading the description, it adds features one at a time and recomputes all correlations.

This thread links to a paper with a QR-Column Pivoting algorithm to select the most linearly independent columns. Since Singular Value Decompositions and matrix operations are optimized for sparse matrices, does a package exist that already does this conversion of a rank-deficient sparse matrix to a full-rank, invertible matrix?

Answer 1

A fast svd implementation suits your needs. SVD is the "gold-standard" of rank-revealing matrix factorizations (Golub & van Loan, Matrix Computations).

The first place to start is to try scipy.sparse.linalg.svds. If it's not fast enough for your needs, then you'll need to explore other packages & SVD algorithms.

Some alternative SVD algorithms are mentioned here What fast algorithms exist for computing truncated SVD? but you might have to do some digging to turn up a python implementation that suits your needs. I've read that implicitly restarted lanczos bidiagonalization methods can compute SVD for much, much larger matrices than the one you have, such as the Netflix prize dataset, but I haven't found a widely used python implementation.

Alternatively, you could simply use your rank-deficient matrix as-is and estimate a penalized regression instead. Options include ridge-regression, lasso and elastic-net.

Answer 2

Do you only want to remove highly correlated variables? If so, the following solution uses less than 6GB of RAM, assuming everything is float32, and runs in a few seconds. I used torch because it often seems to parallelize work better than numpy does.

The basic idea is to calculate a correlation matrix, make it upper triangular, and remove any column whose (absolute) max correlation is greater than the threshold.

import torch

COR_LIMIT = 0.8

data = torch.rand(35000, 12000)
cor = torch.corrcoef(data.T)
cor = torch.triu(cor, 1)
keep_mask = torch.abs(cor.max(dim=0).values) < COR_LIMIT
data = data[:, keep_mask]