使用 SVD 求解欠定 scipy.sparse 矩阵
Solving an underdetermined scipy.sparse matrix using svd
问题
我有一组方程式，变量用小写变量表示，常量用大写变量表示
A = a + b
B = c + d
C = a + b + c + d + e
我在具有两列的 pandas DataFrame 中提供了有关这些方程结构的信息：Constants 和 Variables
例如
df = pd.DataFrame([['A','a'],['A','b'],['B','c'],['B','d'],['C','a'],['C','b'],
['C','c'],['C','d'],['C','e']],columns=['Constants','Variables'])
然后我使用 NetworkX
将其转换为稀疏 CSC 矩阵
table = nx.bipartite.biadjacency_matrix(nx.from_pandas_dataframe(df,'Constants','Variables')
,df.Constants.unique(),df.Variables.unique(),format='csc')
当转换为稠密矩阵时，table看起来像下面这样
矩阵([[1, 1, 0, 0, 0],[0, 0, 1, 1, 0],[1, 1, 1, 1, 1]], dtype=int64)
我想从这里找到哪些变量是可解的（在这个例子中，只有 e 是可解的）并且对于每个可解变量，它的值依赖于哪些常量（在这种情况下，因为 e = C-B-A，它依赖于A，B，和C)
尝试解决方案
我首先尝试使用 rref 来求解可解变量。我使用了符号库 sympy 和函数 sympy.Matrix.rref，这正是我想要的，因为任何可解变量都会有自己的行，几乎全是零，只有 1 行，我可以逐行检查。
然而，这个解决方案不是stable。首先，它非常慢，并且没有利用我的数据集可能非常稀疏的事实。此外， rref 对浮点数的处理不太好。所以我决定转向另一种受 Removing unsolvable equations from an underdetermined system 启发的方法，它建议使用 svd
方便的是，scipy.sparse库中有一个svd函数，即scipy.sparse.linalg.svds。然而，由于我缺乏线性代数背景，我不明白 运行 这个函数在我的 table 上输出的结果，或者如何使用这些结果来得到我想要的。
问题的更多细节
- 我的问题中每个变量的系数都是1。这就是数据在前面显示的两列pandas DataFrame
中的表达方式
- 我的实际例子中的绝大多数变量都将无法求解。目标是找到少数可解的
- 如果适合这个问题的限制，我非常愿意尝试替代方法。
这是我第一次发布问题，所以如果这不完全符合指南，我深表歉意。请留下建设性的批评，但要温和！
您正在求解的系统的形式为
[ 1 1 0 0 0 ] [a] [A]
[ 0 0 1 1 0 ] [b] = [B]
[ 1 1 1 1 1 ] [c] [C]
[d]
[e]
即五个变量的三个方程a, b, c, d, e。正如您问题中提到的答案所提到的，可以使用 pseudoinverse, which Numpy directly provides in terms of the pinv 函数来解决这种不确定的系统。
由于 M 具有线性独立的行，伪逆在这种情况下具有 属性 即 M.pinv(M) = I，其中 I 表示单位矩阵（在这种情况下为 3x3） .因此正式地，我们可以将解决方案写为：
v = pinv(M) . b
其中 v 是 5 分量解向量，b 表示右侧的 3 分量向量 [A, B, C]。然而，这个解决方案并不是唯一的，因为可以从所谓的内核或矩阵 M 的 null space 添加一个向量（即，向量 w 其中 M.w=0) 它仍然是一个解决方案：
M.(v + w) = M.v + M.w = b + 0 = b
因此，唯一存在唯一解的变量是那些来自 M 的空值 space 的所有可能向量的对应分量为零的变量。也就是说，如果你assemble把空space的基变成一个矩阵（每列一个基向量），那么"solvable variables"就会对应这个矩阵的零行（对应列的任何线性组合的分量也将为零）。
让我们将其应用到您的特定示例中：
import numpy as np
from numpy.linalg import pinv
M = [
[1, 1, 0, 0, 0],
[0, 0, 1, 1, 0],
[1, 1, 1, 1, 1]
]
print(pinv(M))
[[ 5.00000000e-01 -2.01966890e-16 1.54302378e-16]
[ 5.00000000e-01 1.48779676e-16 -2.10806254e-16]
[-8.76351626e-17 5.00000000e-01 8.66819360e-17]
[-2.60659800e-17 5.00000000e-01 3.43000417e-17]
[-1.00000000e+00 -1.00000000e+00 1.00000000e+00]]
从这个伪逆，我们看到变量 e（最后一行）确实可以表示为 - A - B + C。但是，它也"predicts" 即a=A/2 和b=A/2。为了消除这些非唯一解（例如 a=A 和 b=0 也同样有效），让我们计算 null space 借用 SciPy [=48= 的函数]:
print(nullspace(M))
[[ 5.00000000e-01 -5.00000000e-01]
[-5.00000000e-01 5.00000000e-01]
[-5.00000000e-01 -5.00000000e-01]
[ 5.00000000e-01 5.00000000e-01]
[-1.77302319e-16 2.22044605e-16]]
这个函数 returns 已经将空 space assembled 的基础转化为矩阵（每列一个向量），我们看到，在合理的精度内，唯一零行确实只是变量e.
对应的最后一行
编辑：
对于方程组
A = a + b, B = b + c, C = a + c
对应的矩阵M为
[ 1 1 0 ]
[ 0 1 1 ]
[ 1 0 1 ]
这里我们看到矩阵实际上是方阵，并且是可逆的（行列式是2）。因此伪逆与 "normal" 逆重合：
[[ 0.5 -0.5 0.5]
[ 0.5 0.5 -0.5]
[-0.5 0.5 0.5]]
对应解a = (A - B + C)/2, ...。由于 M 是可逆的，它的内核/空 space 是空的，这就是为什么食谱函数 returns 只有 []。为了看到这一点，让我们使用内核的定义——它由所有非零向量 x 组成，使得 M.x = 0。但是，由于 M^{-1} 存在，因此 x 被给出为 x = M^{-1} . 0 = 0，这是一个矛盾。形式上，这意味着找到的解决方案是唯一的（或者所有变量都是 "solvable"）。
以 ewcz 的答案为基础，可以使用 numpy.linalg.svd 计算零空间和伪逆。请参阅以下链接：
问题
我有一组方程式，变量用小写变量表示，常量用大写变量表示
A = a + b
B = c + d
C = a + b + c + d + e
我在具有两列的 pandas DataFrame 中提供了有关这些方程结构的信息：Constants 和 Variables
例如
df = pd.DataFrame([['A','a'],['A','b'],['B','c'],['B','d'],['C','a'],['C','b'],
['C','c'],['C','d'],['C','e']],columns=['Constants','Variables'])
然后我使用 NetworkX
将其转换为稀疏 CSC 矩阵table = nx.bipartite.biadjacency_matrix(nx.from_pandas_dataframe(df,'Constants','Variables')
,df.Constants.unique(),df.Variables.unique(),format='csc')
当转换为稠密矩阵时，table看起来像下面这样
矩阵([[1, 1, 0, 0, 0],[0, 0, 1, 1, 0],[1, 1, 1, 1, 1]], dtype=int64)
我想从这里找到哪些变量是可解的（在这个例子中，只有 e 是可解的）并且对于每个可解变量，它的值依赖于哪些常量（在这种情况下，因为 e = C-B-A，它依赖于A，B，和C)
尝试解决方案
我首先尝试使用 rref 来求解可解变量。我使用了符号库 sympy 和函数 sympy.Matrix.rref，这正是我想要的，因为任何可解变量都会有自己的行，几乎全是零，只有 1 行，我可以逐行检查。
然而，这个解决方案不是stable。首先，它非常慢，并且没有利用我的数据集可能非常稀疏的事实。此外， rref 对浮点数的处理不太好。所以我决定转向另一种受 Removing unsolvable equations from an underdetermined system 启发的方法，它建议使用 svd
方便的是，scipy.sparse库中有一个svd函数，即scipy.sparse.linalg.svds。然而，由于我缺乏线性代数背景，我不明白 运行 这个函数在我的 table 上输出的结果，或者如何使用这些结果来得到我想要的。
问题的更多细节
- 我的问题中每个变量的系数都是1。这就是数据在前面显示的两列pandas DataFrame 中的表达方式
- 我的实际例子中的绝大多数变量都将无法求解。目标是找到少数可解的
- 如果适合这个问题的限制，我非常愿意尝试替代方法。
这是我第一次发布问题，所以如果这不完全符合指南，我深表歉意。请留下建设性的批评，但要温和！
您正在求解的系统的形式为
[ 1 1 0 0 0 ] [a] [A]
[ 0 0 1 1 0 ] [b] = [B]
[ 1 1 1 1 1 ] [c] [C]
[d]
[e]
即五个变量的三个方程a, b, c, d, e。正如您问题中提到的答案所提到的，可以使用 pseudoinverse, which Numpy directly provides in terms of the pinv 函数来解决这种不确定的系统。
由于 M 具有线性独立的行，伪逆在这种情况下具有 属性 即 M.pinv(M) = I，其中 I 表示单位矩阵（在这种情况下为 3x3） .因此正式地，我们可以将解决方案写为：
v = pinv(M) . b
其中 v 是 5 分量解向量，b 表示右侧的 3 分量向量 [A, B, C]。然而，这个解决方案并不是唯一的，因为可以从所谓的内核或矩阵 M 的 null space 添加一个向量（即，向量 w 其中 M.w=0) 它仍然是一个解决方案：
M.(v + w) = M.v + M.w = b + 0 = b
因此，唯一存在唯一解的变量是那些来自 M 的空值 space 的所有可能向量的对应分量为零的变量。也就是说，如果你assemble把空space的基变成一个矩阵（每列一个基向量），那么"solvable variables"就会对应这个矩阵的零行（对应列的任何线性组合的分量也将为零）。
让我们将其应用到您的特定示例中：
import numpy as np
from numpy.linalg import pinv
M = [
[1, 1, 0, 0, 0],
[0, 0, 1, 1, 0],
[1, 1, 1, 1, 1]
]
print(pinv(M))
[[ 5.00000000e-01 -2.01966890e-16 1.54302378e-16]
[ 5.00000000e-01 1.48779676e-16 -2.10806254e-16]
[-8.76351626e-17 5.00000000e-01 8.66819360e-17]
[-2.60659800e-17 5.00000000e-01 3.43000417e-17]
[-1.00000000e+00 -1.00000000e+00 1.00000000e+00]]
从这个伪逆，我们看到变量 e（最后一行）确实可以表示为 - A - B + C。但是，它也"predicts" 即a=A/2 和b=A/2。为了消除这些非唯一解（例如 a=A 和 b=0 也同样有效），让我们计算 null space 借用 SciPy [=48= 的函数]:
print(nullspace(M))
[[ 5.00000000e-01 -5.00000000e-01]
[-5.00000000e-01 5.00000000e-01]
[-5.00000000e-01 -5.00000000e-01]
[ 5.00000000e-01 5.00000000e-01]
[-1.77302319e-16 2.22044605e-16]]
这个函数 returns 已经将空 space assembled 的基础转化为矩阵（每列一个向量），我们看到，在合理的精度内，唯一零行确实只是变量e.
编辑：
对于方程组
A = a + b, B = b + c, C = a + c
对应的矩阵M为
[ 1 1 0 ]
[ 0 1 1 ]
[ 1 0 1 ]
这里我们看到矩阵实际上是方阵，并且是可逆的（行列式是2）。因此伪逆与 "normal" 逆重合：
[[ 0.5 -0.5 0.5]
[ 0.5 0.5 -0.5]
[-0.5 0.5 0.5]]
对应解a = (A - B + C)/2, ...。由于 M 是可逆的，它的内核/空 space 是空的，这就是为什么食谱函数 returns 只有 []。为了看到这一点，让我们使用内核的定义——它由所有非零向量 x 组成，使得 M.x = 0。但是，由于 M^{-1} 存在，因此 x 被给出为 x = M^{-1} . 0 = 0，这是一个矛盾。形式上，这意味着找到的解决方案是唯一的（或者所有变量都是 "solvable"）。
以 ewcz 的答案为基础，可以使用 numpy.linalg.svd 计算零空间和伪逆。请参阅以下链接：