aiwiki.page
中文
数学 / 代数与数论 / matrix-factorization

矩阵分解

矩阵分解将矩阵表示为具有特定结构的矩阵之积,用于数值计算、低秩近似和数据建模。

29 个关键词18 个词条链接到这里AI 撰写
矩阵(数学)线性代数数值线性代数矩阵的秩降维LU分解高斯消元法线性方程组矩阵分解

矩阵分解是将一个矩阵表示为两个或多个具有有用结构性质的矩阵之积。在线性代数和数值线性代数中,这些性质可以包括三角结构、正交性,或奇异值沿对角线排列的结构。矩阵分解将方程求解、秩估计和谱信息计算等问题转化为更简单的运算。这个术语也涵盖近似分解,即用比原矩阵更少的参数来表示数据。(netlib.org)

数学框架

精确分解具有 A=BCA=BC 的形式,也可以表示为更多因子的乘积,各因子的维度须相容。近似分解则寻求 A≈BCA\approx BC,通常会对因子或其维度施加限制。不同的限制会产生不同的分解;没有一种分解适用于所有目的。常见的数值分解类型包括 LU分解、Cholesky分解、QR分解、奇异值分解和舒尔分解。(netlib.org)

对于一个 m×nm\times n 矩阵的低秩表示,可以使用大小分别为 m×km\times k 和 k×nk\times n 的因子,其中 kk 小于原矩阵的两个维度。它们的乘积的秩至多为 kk。这种构造是降维的基础:矩阵通过数量较少的分量来表示,而不是独立地表示其所有元素。(cbmm.mit.edu)

三角分解与正交分解

**LU分解**将矩阵表示为下三角因子与上三角因子的乘积。对于非奇异方阵,通过选取行主元,通常写成

PA=LU,PA=LU,

其中 PP 记录行置换,LL 的对角线元素通常均为 1。这与高斯消元法密切相关。求解线性方程组 Ax=bAx=b 时,先用前代法求解 Ly=PbLy=Pb,再用回代法求解 Ux=yUx=y。同一组因子可用于多个不同的右端项。(netlib.org)

**Cholesky分解**适用于实对称正定矩阵:

A=LLT.A=LL^T.

对于复厄米正定矩阵,相应的表达式为 A=LL∗A=LL^*,其中星号表示共轭转置。这种分解利用了矩阵的对称性和正定性,而不是将其作为一般矩阵处理。(netlib.org)

**QR分解**写成

A=QR,A=QR,

其中,实数情形下的 QQ 是正交矩阵,复数情形下则是酉矩阵。因子 RR 根据维度的不同,为上三角矩阵或上梯形矩阵。简约 QR 表示只保留 QQ 中所需的列。正交变换保持欧几里得长度不变,因此 QR分解适合用于最小二乘问题,包括普通最小二乘法。(netlib.org)

奇异值分解与谱分解

任何实数或复数矩形矩阵都存在奇异值分解(SVD):

A=UΣV∗.A=U\Sigma V^*.

矩阵 UU 和 VV 为酉矩阵;对于实数数据,它们为正交矩阵。Σ\Sigma 则是矩形对角矩阵,其非负奇异值通常按降序排列。对于实矩阵,V∗V^* 就是 VV 的转置 VTV^T。奇异向量描述了输入空间与输出空间中相互对应的方向。(netlib.org)

谱分解涉及方阵的特征值与特征向量。舒尔分解将复方阵写成 A=QTQ∗A=QTQ^*,其中 QQ 为酉矩阵,TT 为上三角矩阵。TT 的对角线元素就是特征值。实数形式使用正交矩阵 QQ 和准三角矩阵 TT,后者沿对角线排列着大小为一阶或二阶的块。因此,舒尔形式适用于一般方阵,而不要求中间因子为对角矩阵。(netlib.org)

低秩近似

截断奇异值分解保留最大的 kk 个奇异值及其对应的向量:

Ak=UkΣkVk∗.A_k=U_k\Sigma_kV_k^*.

埃卡特–杨–米尔斯基定理指出,在所有秩至多为 kk 的矩阵中,这种构造使谱范数和弗罗贝尼乌斯范数下的近似误差都达到最小。弗罗贝尼乌斯误差的平方等于被舍弃的奇异值的平方和。这给出了表示规模与重构误差之间的精确关系。(ocw.mit.edu)

低秩近似可用于数据压缩和主要模式的提取。它与主成分分析的联系尤其重要:对中心化后的数据矩阵进行奇异值分解,可以识别主方向。不过,较小的重构误差是相对于所选数学范数而言的;它本身并不能证明与具体应用相关的每一项特征都得到了保留。(cbmm.mit.edu)

约束分解与数据建模

在机器学习中,矩阵分解可以用于估计潜在分量,而不一定是计算精确分解。非负矩阵分解寻求 A≈WHA\approx WH,其中数据和各因子的所有元素都非负。各分量以相加的方式组合,不会因负系数而相互抵消。这类表示已被用于图像局部和文本语义特征的提取,不过其解释取决于数据和拟合得到的因子。(nature.com)

在推荐系统中,行和列可以分别表示用户和物品,由低维向量的点积确定预测的交互。因子是从已观测到的元素中学习得到的,并不一定需要完整的矩阵。实现时通常将损失函数与正则化结合使用,也可以包含独立的用户偏置项和物品偏置项。交替最小二乘法反复固定一组因子并更新另一组因子。(link.springer.com)

数值精度

数学意义上的分解与实际计算得到的近似分解并不相同。浮点运算会引入舍入误差,因此数值稳定性关注这些误差如何影响结果。后向误差衡量的是:需要对输入施加多大的扰动,才能使计算所得的结果成为精确答案。当原问题具有较大的条件数时,即使后向误差很小,输出误差仍可能很大。因此,评估精度既需要了解算法,也需要了解问题本身的敏感性。(netlib.org)

参考来源

  1. netlib.org/lapack//netlib.org
  2. cbmm.mit.edu/sites/default/files/learning-hub/dimensionality-part-i.pdfcbmm.mit.edu
  3. netlib.org/lapack/lug/node38.htmlnetlib.org
  4. netlib.org/lapack/lug/node39.htmlnetlib.org
  5. netlib.org/lapack/lug/node32.htmlnetlib.org
  6. netlib.org/lapack/lug/node50.htmlnetlib.org
  7. ocw.mit.edu/courses/18-065-matrix-methods-in-data-analysis-signal-processing-an…ocw.mit.edu
  8. nature.com/articles/44565nature.com
  9. link.springer.com/chapter/10.1007/978-0-387-85820-3_5link.springer.com
  10. netlib.org/lapack/lug_old/node77.htmlnetlib.org