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

Gram Schmidt process使用线性组合找到一个基础(等效最大独立子集)，QR Decomposition有效地模仿了这一点。

因此，一种方法就是申请 numpy.linalg.qr到转置，并检查 R 矩阵的非零分量。相应的列(在转置矩阵中，即原始矩阵中的行)是独立的。

---

编辑 经过一番搜索，我相信this Berkeley lecture解释它，但这里有例子

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]])