Python例程从秩缺陷矩阵中提取线性独立行

Question

我正在努力解决以下问题:我有一些非常大的矩阵(比如,至少,2000x2000,可能在将来它们甚至会达到10000x10000),排名非常小(2或3,称之为N),我需要找到一个有效的Python例程来从中提取线性独立行(或列,矩阵是对称的!).我试图采用QR分解的Q矩阵的前N列,但它似乎不能正常工作(这可能是错的吗？).你有更好的主意吗？

非常感谢你!

编辑 这是我用来实现Ami Tavory建议的方法的Python代码:

from numpy import absolute
from numpy.linalg import qr

q = qr(R)[1] #R is my matrix
q = absolute(q)
sums = sum(q,axis=1)

i = 0
while( i < dim ): #dim is the matrix dimension
    if(sums[i] > 1.e-10):
       print "%d is a good index!" % i
    i += 1

这应该告诉我行是否为非零,因此如果R的第i列是线性独立的.

Answer 1

在革兰氏施密特过程发现使用线性组合的基础(等同最大的独立子集),并且QR分解有效模仿此.

因此,执行所需操作的一种方法是应用于numpy.linalg.qr转置,并检查R矩阵的非零分量.相应的列(在转置矩阵中,即原始矩阵中的行)是独立的.

编辑经过一番搜索,我相信伯克利的这个讲座解释了它,但这里有一些例子

import numpy as np

# 2nd column is redundant
a = np.array([[1, 0, 0], [0, 0, 0], [1, 0, 1]])
>> np.linalg.qr(a)[1] # 2nd row empty
array([[ 1.41421356,  0.        ,  0.70710678],
   [ 0.        ,  0.        ,  0.        ],
   [ 0.        ,  0.        ,  0.70710678]])

# 3rd column is redundant
a = np.array([[1, 0, 0], [1, 0, 1], [0, 0, 0], ])
>> np.linalg.qr(a)[1] # 3rd row empty
array([[ 1.41421356,  0.        ,  0.70710678],
   [ 0.        ,  0.        , -0.70710678],
   [ 0.        ,  0.        ,  0.        ]])

# No column redundant
a = np.array([[1, 0, 0], [1, 0, 1], [2, 3, 4], ])
>> np.linalg.qr(a)[1] # No row empty
array([[ 2.44948974,  2.44948974,  3.67423461],
   [ 0.        ,  1.73205081,  1.73205081],
   [ 0.        ,  0.        ,  0.70710678]])