矩阵分解

矩阵分解是一种将矩阵简化为其组成部分的方法。这种方法可以简化更复杂的矩阵运算,这些运算可以在分解的矩阵上执行,而不是在原始矩阵本身上执行。它的衍生Non-negative matrix factorization也被用于降维等操作上。

来源:矩阵分解
简介

矩阵分解是一种将矩阵简化为其组成部分的方法。这种方法可以简化更复杂的矩阵运算,这些运算可以在分解的矩阵上执行,而不是在原始矩阵本身上执行。它的衍生Non-negative matrix factorization也被用于降维等操作上。

矩阵分解的一个常见类比是数字因子分解,例如将10因子分解为2×5。 与分解实数值一样,有许多方法可以分解矩阵,因此存在一系列不同的矩阵分解技术。

image.png 举例:近似非负矩阵分解的展示。 矩阵V由两个较小的矩阵W和H表示,当它们相乘时,近似地重构V。

两种简单且广泛使用的矩阵分解方法是LU矩阵分解和QR矩阵分解。

LU Matrix Decomposition

一个(n×n)-矩阵A(在一个场上),使得主子式不为零,

det(\begin{matrix}
a_{11} & ... & a_{1i}\\ 
 \vdots &  &  \vdots\\ 
a_{i1} & ... & a_{ii} 
\end{matrix}) \neq 0, i=1,...,n.

image.png

可以写成A = LU,L为低三角矩阵,U为上三角矩阵。这也称为三角分解。如果指定L(分别为U)的对角元素(例如,全部等于1),则该因子分解是唯一的;参见,例如,《A survey of numerical mathematics》, p.821。相反,如果A是可逆的且A = LU,那么所有主要的主子式都是非零的。

通常,需要对行(或列)进行排列以获得三角分解。对于任何(m×n)矩阵,存在置换矩阵P,具有单位对角线的下三角矩阵L和(m×n)梯形矩阵U,使得PA = LU。这里,梯形矩阵可以描述如下:

i)非零行首先出现(行中的第一个非零条目有时称为枢轴);

ii)每个枢轴下方是一列零;

iii)每个枢轴位于上排的枢轴的右侧。例如,

\begin{pmatrix}
0 &\bullet & * & * & * & * & * & * & * &* \\
0 & 0 & \bullet & * & * & * & * &* &* &* \\
0 & 0 & 0 & 0 & 0 & \bullet & * & * & * & * \\
0 & 0 &0 & 0 & 0 &0 & 0 & 0 & 0 &\bullet \\
0& 0& 0 & 0 & 0 & 0 &0 & 0 & 0 & 0
\end{pmatrix}

image.png

其中枢轴用点∙表示。 LU分解与高斯消元紧密相关,见高斯方法和《Linear algebra and its applications》。

QR Matrix Decomposition

设A是(m×n)- 矩阵,且m≥n,在\mathbb{C}上。然后矩阵(m×m)Q和右 - 三角m×n 矩阵R,使得A = QR。 这里,形式为右三角形(m×n)矩阵为如下,且m≥n

\begin{pmatrix}
r_{11} & r_{12} & ... &r_{1n} \\ 
0 &  r_{22} & ... &r_{2n} \\ 
\vdots  &  & \ddots & \vdots\\ 
0 & 0 & ... & r_{nn}\\ 
0 & 0 & ... & 0\\ 
 \vdots &  & \ddots  &  \vdots\\ 
0 & 0 & ... & 0
\end{pmatrix}

image.png

实数(分别是复数)非奇异矩阵A具有分解QR,其中Q正交,R所有元素为正。 这种因式分解是独特的,并且由Gram-Schmidt正交化过程给出(参见正交化方法)。 经常使用的特征值问题的QR算法(参见迭代方法)基于重复的QR分解。

Singular value factorization.

设A是秩k的\mathbb{C}上的(m×n)矩阵。 然后它可以写成矩阵A =U\sumV,V是(n×n) 单位矩阵和Σ形式为:

image.png

\sum = \begin{pmatrix}
D &0 \\
0 & 0
\end{pmatrix}


其中D是对角线,具有A的奇异值s_1,...,s_k,即A的特征值的正平方根AA*(也就是,A*A)。

【出处:https://www.encyclopediaofmath.org/index.php/Matrix_factorization   】

2. 发展历史

描述

矩阵分解已经有了悠久的历史。

在数值分析和线性代数中,lower–upper (LU) decomposition分解或因子分解将矩阵作为下三角矩阵和上三角矩阵的乘积。有时也包括置换矩阵。 LU分解可以被视为高斯消元的矩阵形式。 计算机通常使用LU分解来求解线性方程的平方系统,并且当反转矩阵或计算矩阵的行列式时,它也是关键步骤。 LU分解由数学家Tadeusz Banachiewicz于1938年引入。

Cholesky分解或Cholesky分解是将Hermitian正定矩阵分解为下三角矩阵及其共轭转置的乘积,这对于有效的数值解,例如, 蒙特卡罗模拟。 André-Louis Cholesky发现它是真实的矩阵。 当它适用时,Cholesky分解的效率大约是用于求解线性方程组的LU分解的两倍。

Jordan-Chevalley分解,以Camille Jordan和Claude Chevalley的名字命名,表示线性算子是其通勤半单部分及其幂零部分的总和。 乘法分解表示一个可逆算子作为其通勤半单元和单极部分的乘积。 分解在代数群的研究中很重要。

【来源:https://en.wikipedia.org/wiki/Matrix_decomposition  】

在化学计量学中,非负矩阵分解在“自建模曲线分辨率, self modeling curve resolution”的名称下有着悠久的历史。1971年,《Self modeling curve resolution》 在该框架中,右矩阵中的向量是连续曲线而不是离散向量。 20世纪90年代中期,芬兰的一组研究人员以正矩阵分解的名义进行了非负矩阵因子分解的早期研究,如1994年的《Positive matrix factorization: A non-negative factor model with optimal utilization of error estimates of data values》,1995年的《Source identification of bulk wet deposition in Finland by positive matrix factorization》。

在Lee和Seung研究算法的性质之后,它被广泛地称为非负矩阵分解,并且为两种类型的因子分解发布了一些简单而有用的算法。1999年《Learning the parts of objects by non-negative matrix factorization》,2000年的《 Algorithms for Non-negative Matrix Factorization》。

在通过非负矩阵分解来学习对象的部分时,Lee和Seung提出NMF主要用于基于部分的图像分解。它将NMF(non-negative matrix factorization)与矢量量化和主成分分析进行了比较,并表明虽然这三种技术可以写成因子分解,但它们实现了不同的约束,因此产生了不同的结果。

NMF作为概率图形模型:可见单位(V)通过权重W连接到隐藏单位(H),因此V由具有均值{\ displaystyle \ sum _ {a} W_ {ia} h_ {的概率分布生成a}} \ sum _ {a} W_ {ia} h_ {a}。[12]:5

后来证明,某些类型的NMF是更普遍的概率模型的实例,称为“多项PCA”《 Variational Extensions to EM and Multinomial PCA》。当通过最小化Kullback-Leibler散度获得NMF时,它实际上等同于通过最大似然估计训练的多项PCA的另一个实例,概率潜在语义分析《Relation between PLSA and NMF and Implications》。该方法通常用于分析和聚类文本数据,并且还与潜在类模型有关。

具有最小二乘目标的NMF相当于宽松形式的K均值聚类:矩阵因子W包含聚类质心,H包含聚类成员指标。《A Unifying Approach to Hard and Probabilistic Clustering》为使用NMF进行数据聚类提供了理论基础。然而,k-means并没有对其质心强加非负性,所以最接近的类比实际上是“半NMF”。

NMF可以看作是一个双层有向图模型,具有一层观察到的随机变量和一层隐藏的随机变量。NMF超越矩阵延伸到任意秩序的张量。该扩展可以被视为例如PARAFAC模型的非负对应物。NMF的其他扩展包括几个数据矩阵和张量的联合因子分解,其中一些因素是共享的。这些模型对于传感器融合和关系学习很有用。

NMF是非负二次规划(NQP)的一个实例,就像支持向量机(SVM)一样。然而,SVM和NMF在一个比NQP更密切的水平上相关,这允许直接应用为两种方法中的任何一种开发的解决方案算法来解决两个领域的问题。

在天文学中,NMF是一种有前途的降维方法,因为天体物理信号是非负的。 NMF已应用于光谱观测和直接成像观测作为研究天文物体的共同特性和后处理天文观测的方法。 Blanton&Roweis(2007)对光谱观测的研究进展考虑了天文观测的不确定性,ZHU(2016)后来对其进行了改进,其中还考虑了缺失数据并启用了并行计算。 然后Ren等人采用了他们的方法 (2018)直接成像领域作为检测系外行星的方法之一,特别是对于星周盘的直接成像。

NMF可用于文本挖掘应用程序。 在该过程中,使用来自一组文档的各种术语(通常是加权的词频信息)的权重来构造文档项矩阵。 该矩阵被分解为术语特征和特征文档矩阵。 特征源自文档的内容,特征文档矩阵描述相关文档的数据集群。

Arora,Ge,Halpern,Mimno,Moitra,Sontag,Wu和Zhu(2013)给出了使用NMF学习主题模型的多项式时间算法。 该算法假定主题矩阵满足通常在这些设置中保持的可分离条件.

【来源:https://en.wikipedia.org/wiki/Non-negative_matrix_factorization

主要事件

年份事件相关论文
1999Lee, D. D., & Seung, H. S.非负矩阵分解的学习Lee, D. D., & Seung, H. S. (1999). Learning the parts of objects by non-negative matrix factorization. Nature, 401(6755), 788.
2001Lee, D. D., & Seung, H. S.陈述对非负矩阵分解的算法Lee, D. D., & Seung, H. S. (2001). Algorithms for non-negative matrix factorization. In Advances in neural information processing systems (pp. 556-562).
2008Mnih, A., & Salakhutdinov, R. R.提出概率矩阵分解Mnih, A., & Salakhutdinov, R. R. (2008). Probabilistic matrix factorization. In Advances in neural information processing systems (pp. 1257-1264).
2009Koren, Y., Bell, R., & Volinsky, C.提出在推荐系统下的矩阵分解方法Koren, Y., Bell, R., & Volinsky, C. (2009). Matrix factorization techniques for recommender systems. Computer, (8), 30-37.
2010Mairal, J., Bach, F., Ponce, J., & Sapiro, G.提出矩阵分解和稀疏编码的在线学习Mairal, J., Bach, F., Ponce, J., & Sapiro, G. (2010). Online learning for matrix factorization and sparse coding. Journal of Machine Learning Research, 11(Jan), 19-60.

3. 发展分析

瓶颈

非负矩阵分解(nonnegative matrix factorization)的当前研究(自2010年起)包括但不限于

1.算法:搜索因子的全局最小值和因子初始化。

2.可扩展性:如何对百万到亿万的矩阵进行分解,这在Web级数据挖掘中很常见,例如,参见分布式非负矩阵分解(Distributed Nonnegative Matrix Factorization,DNMF)和可扩展非负矩阵分解(ScalableNMF)

3.在线:如何在不重新计算新数据时更新分解。

4.集体(联合)因子分解:为多视图学习分解多个相互关联的矩阵

5. Cohen和Rothblum 1993问题:理性矩阵是否总是具有最小内维数的NMF,其因子也是合理的。最近,这个问题得到了消极的回答。

未来发展方向

  1. 在线计算:希望在解决因子分解的问题中可以在线计算,减少重复计算。
  2. 可拓展性:对大量的矩阵进行分解时,采取怎样的计算模式。
  3. 因子初始化方法的如何选择。

Contributor: Ruiying Cai

相关人物
Chris Volinsky
Chris Volinsky
H Sebastian Seung
H Sebastian Seung
Daniel Dongyuel Lee
Daniel Dongyuel Lee
Yehuda Koren
Yehuda Koren
简介
相关人物