Question

The setting is here.

X: 6000x8000 non-sparse matrix

B: 8000x1 sparse vector with only tens of non-zeros

d: positive number

M: is sparsified X'X, i.e. thresholding the elements smaller than d in magnitude to be 0.
Only hundreds of elements are left. So (X' * X - M) have many small elements and is not sparse.

I want to compute the vector y=(X' * X - M)* B and can rewrite as y=X' * (X * B) - M*B. The first part is fast enough, but the second part involves X'*X, and is very very slow.

Could any one help me to accelerate this computation?

Thanks a million!

Answer 1

Don't compute the entries that would be multiplied with the zero entries of $B$. That is, take the submatrix $X_{nz}$ of $X$ consisting of those columns corresponding with the nonzero entries of $B$, and take $B_{nz}$ to be the concatenation of all nonzero entries of $B$. Then compute the sparsification of $X^T \cdot X_{nz}$ and multiply that by $B_{nz}$.

Answer 2

Matlab has a sparse matrix type.