Python中求解含半正定矩阵B的广义特征值系统问题

我尝试使用Normalized Cut算法（Shi and Malik, 2000）将一个矩阵分割为两个矩阵，为此需要求解广义特征值系统**(Ax = λBx)**的第二小特征向量。我的输入中，B是半正定矩阵，但scipy.linalg.eigh要求B为正定矩阵，运行时触发错误。我想了解该输入是否存在解决方案，以及如何实现。

尝试的代码 #

from scipy.linalg import eigh
eigvals, eigvecs = eigh(A, B, eigvals_only=False, subset_by_index=[0, 1])

错误信息 #

numpy.linalg.LinAlgError: The leading minor of order 2 of B is not positive definite. The factorization of B could not be completed and no eigenvalues or eigenvectors were computed.

解决方案 #

当B为半正定矩阵时，说明B存在零特征值（对应Normalized Cut中无连接的孤立节点），可通过以下方法解决：

方法1：正则化B矩阵 #

给B添加极小的单位矩阵扰动，将其转化为正定矩阵，这种方法简单高效，实际场景中对分割结果影响极小：

import numpy as np
from scipy.linalg import eigh

# 定义极小扰动值
epsilon = 1e-8
# 构造正定的正则化B矩阵
B_reg = B + epsilon * np.eye(B.shape[0])
# 求解广义特征值，获取前两个特征向量
eigvals, eigvecs = eigh(A, B_reg, subset_by_index=[0, 1])
# 提取第二小特征向量
second_eigvec = eigvecs[:, 1]

方法2：投影到B的非零特征子空间 #

分离B的零空间，将问题投影到非零特征子空间后求解，避免扰动带来的误差：

import numpy as np
from scipy.linalg import eigh

# 对B做特征分解
B_eigvals, B_eigvecs = np.linalg.eigh(B)
# 过滤掉接近零的特征值（阈值可根据实际情况调整）
threshold = 1e-10
nonzero_mask = B_eigvals > threshold
# 获取非零特征值对应的特征向量矩阵
V = B_eigvecs[:, nonzero_mask]

# 将A和B投影到非零子空间
A_proj = V.T @ A @ V
B_proj = V.T @ B @ V  # 此时B_proj为对角正定矩阵

# 在子空间中求解广义特征值问题
proj_eigvals, proj_eigvecs = eigh(A_proj, B_proj, subset_by_index=[0, 1])
# 将子空间中的特征向量投影回原空间
eigvecs = V @ proj_eigvecs
# 提取第二小特征向量
second_eigvec = eigvecs[:, 1]

方法3：使用稀疏矩阵求解器（若A/B为稀疏矩阵） #

如果A和B是稀疏矩阵，scipy.sparse.linalg.eigsh对B的半正定情况兼容性更好：

from scipy.sparse.linalg import eigsh

# 求解前两个最小特征值对应的特征向量
eigvals, eigvecs = eigsh(A, k=2, M=B, which='SM')
# 第二小特征向量为eigvecs[:, 1]
second_eigvec = eigvecs[:, 1]

内容的提问来源于stack exchange，提问作者Soheil Keshavarz