Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question

closed as too localized by Igor Rivin, Deane Yang, Dmitri Pavlov, S. Carnahan Mar 29 '11 at 4:28

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

    
I don't think MO is the right place for this question, maybe Stack Overflow stackoverflow.com is better. –  Zander Mar 29 '11 at 2:29
2  
I agree that this is completely inappropriate, voting to close –  Igor Rivin Mar 29 '11 at 2:45

2 Answers 2

up vote 1 down vote accepted

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}$.

share|improve this answer
    
Thanks! This is what I wanted. –  Peter Mar 29 '11 at 4:40

Matlab has a sparse matrix type.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.