CODEWITHSUNDEEP
pythonnumpymatrixlinear-algebra
Peter
Peter

Reputation: 13505

Finding linearly interdependent columns of a matrix in numpy

Problem: I have an MxN matrix where M>=N. I want to identify the groups of linearly-interdependent column-vectors within this matrix.

I'm hoping there's a fast and easy way to do this in numpy.

>>> a = np.random.randn(7, 6)
>>> a[:, 3] = 2*a[:, 0]-a[:, 4]
>>> a[:, 5] = 3*a[:, 1]

I'm looking for a function get_column_groups, which will return

>>> get_column_groups(a)
array([0, 1, 2, 0, 0, 1])

I guess bonus points if it also returns the rank of each group, e.g.:

>>> groups, group_ranks = get_column_groups(a)
>>> groups    
array([0, 1, 2, 0, 0, 1])
>>> group_ranks
[2, 1, 1]

Upvotes: 0

Views: 1604

Answers (1)

eickenberg
eickenberg

Reputation: 14377

As far as I understand the question, computing the Spark of the matrix is a subproblem of what you are requesting, hence rendering it NP-Complete in most cases.

There may be some algorithms that do this better than just combinatorial evaluation of columns up to a size of rank(a), but this would be a start.

Upvotes: 1

Related Questions