从秩不足矩阵中提取线性无关行的例行程序

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列是否线性独立。

- Simone Bolognini

Answer 1

Gram Schmidt过程使用线性组合找到基（等价于最大独立子集），而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]])

- Ami Tavory

---

谢谢！“相应的组件”是指起始矩阵的列/行或R矩阵的列/行？抱歉，我以前从未使用过这种方法... - Simone Bolognini

稍等，如果您对这种方法不熟悉，我会尝试为您找到一个链接。 - Ami Tavory

非常友善！因为我仍然不清楚在R中应该寻找什么以及如何转置起始矩阵中的结果。 - Simone Bolognini

@SimoneBolognini 看看这些例子是否有帮助。 - Ami Tavory

如果我理解正确的话，您的方法建议查找R矩阵的非空行，其索引应对应于起始矩阵的线性独立列的索引。我尝试了一下，似乎不起作用：我知道我的矩阵的秩为2，但仍然找到了6个非空行，其中只有一个对应于两个真正独立向量中的一个。另一个（我知道在矩阵底部找到）从未被考虑过。有线索吗？ - Simone Bolognini

Answer 2

这是我找到解决问题的链接！这里提出的柯西-施瓦茨方法非常有效！！

- Simone Bolognini

Answer 3

这是一个最简示例，演示了Ami建议使用QR分解并采用非空行R的方法无法按照描述的那样工作：

# 2 dependent rows
>> A = array([[ 1.,  1.,  0.,  0.],
              [-1., -1.,  0.,  0.]])
# looks like it works for this case
>> numpy.linalg.qr(A.T)[1]
array([[-1.41421356,  1.41421356], 
       [ 0.        ,  0.        ]])

# counter example
>> A2 = numpy.array([[1,1,0,0.],[-1,-1,0,0.],[1,2,3,4]])
>> numpy.linalg.qr(A2.T)[1] 
array([[-1.41421356,  1.41421356, -2.12132034],
       [ 0.        ,  0.        ,  0.70710678], # 2nd row is not null
       [ 0.        ,  0.        , -5.        ]]) 

第二个枢轴丢失了，可能这里有一些可以利用的结构，但不是行。

- suntzuisafterU