2
$\begingroup$

I have a 400x132 rectangular matrix with only 0 and 1. I am looking for the linear combinations of the columns of the matrix that sum to 0. For example C1 + C2 - C3 = 0.

I want to find the linear combinations with as few columns as possible. So for example, I don't want to find the 2 combinations: C1 + C2 - C4 = 0 and C1 + C2 -C4 - C5 + C6 = 0, but I want to find C1 + C2 - C4 = 0 and - C5 + C6 = 0.

I can calculate easily all linear combination (I use SVD to find a base of the kernel of the matrix). However, the results do not satisfy my constraints of having as many 0 as possible.

Does any one know a method to do this?

Thanks!

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
2
$\begingroup$

It sounds like you're describing an instance of the "sparse null basis problem" – this was the title of what (I believe is) the seminal work on this problem, by Coleman and Pothen. You can find their 1984 tech report at http://ecommons.library.cornell.edu/handle/1813/6438, and it may be helpful to search for work that cites theirs. See also the paper of Brualdi, Friedland and Pothen found at https://cs.uwaterloo.ca/research/tr/1993/40/CS-93-40.pdf. (That's the one I remember reading years ago, which is about how long it's been since I looked at anything related to this stuff.) I seem to recall that there is some nice matroid theory involved. In any case, it seems there has been some work on the more applied side of things as well. For example, I found this recent paper from the journal Numerical Algorithms which is entitled "An efficient algorithm for sparse null space basis problem using ABS methods".

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .