为什么对称正定 (SPD) 矩阵如此重要?

机器算法验证 数理统计 优化 协方差矩阵 直觉 线性代数
2022-02-05 22:33:14

我知道对称正定(SPD)矩阵的定义,但想了解更多。

为什么它们如此重要,凭直觉?

这是我所知道的。还有什么?

  • 对于给定的数据,协方差矩阵是 SPD。协方差矩阵是一个重要的指标,请参阅这篇出色的文章以获得直观的解释。

  • 二次形式12xAxbx+c是凸的,如果A是 SPD。凸性对于可以确保局部解是全局解的函数来说是一个很好的属性。对于凸问题,有很多好的算法可以解决,但对于非凸问题则不然。

  • 什么时候A是 SPD,二次形式的优化解

    minimize   12xAxbx+c
    和线性系统的解决方案
    Ax=b
    是相同的。所以我们可以在两个经典问题之间进行转换。这很重要,因为它使我们能够使用在另一个领域中发现的技巧。例如,我们可以使用共轭梯度法来求解线性系统。

  • 有许多好的算法(快速、数值稳定)更适合 SPD 矩阵,例如 Cholesky 分解。

编辑:我不是在尝试询问 SPD 矩阵的身份,而是询问属性背后的直觉来显示重要性。例如,正如@Matthew Drury 所提到的,如果矩阵是 SPD,则特征值都是正实数,但为什么所有正数都很重要。@Matthew Drury 对 flow 有一个很好的答案,这就是我想要的。

4个回答

(实)对称矩阵具有一组完整的正交特征向量,其对应的特征值都是实数。对于非对称矩阵,这可能会失败。例如,二维空间中的旋转在实数中没有特征向量或特征值,您必须通过复数传递到向量空间才能找到它们。

如果矩阵是另外正定的,那么这些特征值都是正实数。这个事实比第一个要容易得多,因为如果v是具有单位长度的特征向量,并且λ对应的特征值,那么

λ=λvtv=vtAv>0

其中最后一个等式使用正定性的定义。

这里对直觉的重要性在于线性变换的特征向量和特征值描述了最容易理解变换的坐标系。在像标准坐标系这样的“自然”基础上,线性变换可能很难理解,但每个变换都带有一个“首选”特征向量基础,其中变换充当所有方向的缩放。这使得转换的几何形状更容易理解。

例如,函数局部极值的二阶导数检验R2R通常作为一系列神秘条件给出,涉及二阶导数矩阵中的一个条目和一些行列式。事实上,这些条件简单地编码了以下几何观察:

  • 如果二阶导数矩阵是正定的,则​​您处于局部最小值。
  • 如果二阶导数矩阵是负定的,则您处于局部最大值。
  • 否则,你都不是,一个鞍点。

您可以通过上面的本征基几何推理来理解这一点。临界点的一阶导数消失,因此这里函数的变化率由二阶导数控制。现在我们可以进行几何推理

  • 在第一种情况下,有两个特征方向,如果你沿着其中一个方向移动,函数就会增加。
  • 在第二个中,两个特征方向,如果你在其中一个方向上移动,函数就会减小。
  • 最后,有两个特征方向,但其中一个函数增加,另一个函数减少。

由于特征向量跨越整个空间,任何其他方向都是特征方向的线性组合,因此这些方向的变化率是特征方向变化率的线性组合。所以事实上,这在所有方向上都成立(这或多或少意味着在更高维空间上定义的函数是可微的)。现在,如果您在脑海中画出一张小图,那么对于初学者微积分课本中相当神秘的东西来说,这很有意义。

这直接适用于您的要点之一

二次形式12xAxbx+c 是凸的,如果A是 SPD。凸是一个很好的属性,可以确保本地解决方案是全局解决方案

二阶导数的矩阵是A处处,是对称正定的。从几何上讲,这意味着如果我们在任何本征方向上移开(因此是任何方向,因为任何其他方向都是本征方向的线性组合),函数本身将在其切平面上方弯曲。这意味着整个表面都是凸的。

关于优化(因为你用优化标签标记了你的问题),SPD 矩阵非常重要,原因很简单——SPD Hessian 保证搜索方向是下降方向。考虑牛顿法无约束优化的推导。首先,我们形成泰勒展开式f(x+Δx)

f(x+Δx)f(x)+ΔxTf(x)+12ΔxT2f(x)Δx

接下来,我们取关于的导数Δx

f(x+Δx)f(x)+2f(x)Δx

最后,将导数设为 0 并求解Δx

Δx=2f(x)1f(x)

假设2f(x)是 SPD,很容易看出Δx是下降方向,因为:

f(x)TΔx=f(x)T2f(x)1f(x)<0

使用牛顿法时,非 SPD Hessian 矩阵通常被“轻推”为 SPD。有一种称为修改 Cholesky 的简洁算法将检测非 SPD Hessian,在正确的方向上适当地“轻推”它并分解结果,所有这些(基本上)与 Cholesky 分解的成本相同。Quasi-Newton 方法通过强制近似 Hessian 为 SPD 来避免这个问题。

顺便说一句,对称不定系统近来受到了很多关注。它们出现在用于约束优化的内点方法的背景下。

您会在许多基本方法中找到一些直觉,以显示实对称矩阵的特征值都是实数:https ://mathoverflow.net/questions/118626/real-symmetric-matrix-has-real-eigenvalues-elementary-证明/118640#118640

特别是二次型xTAx自然地出现在瑞利商中,对称矩阵提供了可以说是展示特征值是实数的大型矩阵家族的最自然方式。参见 Courant 极小极大定理,例如:https ://en.wikipedia.org/wiki/Courant_minimax_principle

同样对称的、严格正定矩阵是唯一可以定义非平凡内积以及诱导范数的矩阵集:d(x,y)=x,Ay=xTAy. 这是因为根据实向量的定义x,y d(x,y)=d(y,x)对全部x,yx2=xTAx>0为了x0. 通过这种方式,对称正定矩阵可以被视为坐标变换的理想候选者。

后一个属性在支持向量机领域绝对是关键,特别是内核方法和内核技巧,其中内核必须是对称正的,才能产生正确的内积。事实上,默瑟定理将对称矩阵的直观性质推广到了函数空间。

在几何上,正定矩阵定义了一个度量,例如黎曼度量,因此我们可以立即使用几何概念。

如果xy是向量和A一个正定矩阵,那么

d(x,y)=(xy)TA(xy)
是一个度量(也称为距离函数)。

此外,正定矩阵与内积有关:Rn,我们可以定义一个内积

x,y=xTAy
在哪里A如上是肯定的。更多,所有内部产品Rn以这种方式产生。