elimination the linear dependent columns of a non-square matrix in python
Asked Answered
F

2

6

I have a matrix A = np.array([[1,1,1],[1,2,3],[4,4,4]]) and I want only the linearly independent rows in my new matrix. The answer might be A_new = np.array([1,1,1],[1,2,3]]) or A_new = np.array([1,2,3],[4,4,4])

Since I have a very large matrix so I need to decompose the matrix into smaller linearly independent full rank matrix. Can someone please help?

Forbid answered 7/12, 2018 at 9:59 Comment(1)
import numpy as np A = np.array([ [1,1,1],[1,2,3],[4,4,4]])Forbid
S
5

There are many ways to do this, and which way is best will depend on your needs. And, as you noted in your statement, there isn't even a unique output.

One way to do this would be to use Gram-Schmidt to find an orthogonal basis, where the first $k$ vectors in this basis have the same span as the first $k$ independent rows. If at any step you find a linear dependence, drop that row from your matrix and continue the procedure.

A simple way do do this with numpy would be,

q,r = np.linalg.qr(A.T)

and then drop any columns where R_{i,i} is zero.

For instance, you could do

A[np.abs(np.diag(R))>=1e-10]

While this will work perfectly in exact arithmetic, it may not work as well in finite precision. Almost any matrix will be numerically independent, so you will need some kind of thresholding to determine if there is a linear dependence. If you use the built in QR method, you will have to make sure that there is no dependence on columns which you previously dropped.

If you need even more stability, you could iteratively solve the least squares problem

A.T[:,dependent_cols] x = A.T[:,col_to_check]    

using a stable direct method. If you can solve this exactly, then A.T[:,k] is dependent on the previous vectors, with the combination given by x.

Which solver to use may also be dictated by your data type.

Seasonseasonable answered 25/12, 2018 at 3:29 Comment(1)
this approach fails for me when A is not squareDumdum
D
0

The questioner asked how to do this when the array is not square.

I have a partial solution

Complete the square. Then use the solution above or this approach How to find linearly independent rows from a matrix

A.shape

(222,324)

data2= np.zeros((324,324))
data2[:222,:] = A
lambdas, V =  np.linalg.qr(data2)
linearly_independent_indices = np.abs(np.diag(V))>=1e-10

This correctly flagged linear dependencies among the first 222 columns. However, it did not provide useful feedback for the final 102 columns.

Shifting the column order and repeating may help, but a better solution awaits

Dumdum answered 29/5, 2024 at 18:9 Comment(0)

© 2022 - 2025 — McMap. All rights reserved.