矩阵分解：理论与机器学习应用概述

需积分: 18 155 浏览量更新于2024-07-06 2 收藏 3.12MB PDF 举报

矩阵分解作为现代信息技术领域的重要基石，在统计学、优化、机器学习，特别是深度学习中发挥着至关重要的作用。1954年，Alston S. Householder发表的《数值分析原理》标志着矩阵分解研究的早期进展，其中重点关注了矩阵的块LU分解，即将矩阵分解为下三角矩阵和上三角矩阵的乘积。这一分解方式为后续算法设计奠定了基础，特别是在神经网络训练中的反向传播算法的发展极大地推动了其在深度学习中的应用。本文档的焦点在于提供一个全面的介绍，涵盖了数值线性代数和矩阵分析中的核心概念与数学工具，目标是使读者能够轻松理解和掌握矩阵分解技术。然而，由于篇幅限制，文章并未详尽探讨所有关于矩阵分解的深入话题，如欧几里得空间、赫米特空间和希尔伯特空间的独立分析，以及复数域中的相关理论。对于这些领域的深入学习，读者被鼓励参考一系列经典教材，例如Householder（2006）、Trefethen和Bau III（1997）、Strang（2009）等作者的作品，他们提供了对这些高级主题的详尽讲解。同时，Gill et al. (2021)、Goodfellow et al. (2016)、Boyd和Vandenberghe (2018)等人的研究则聚焦于矩阵分解在具体机器学习场景下的应用实例和最新进展。矩阵分解技术不仅限于理论，它涉及的技巧广泛应用于诸如特征值分解、奇异值分解（SVD）、QR分解等，这些方法对于数据降维、异常检测、推荐系统，以及深度学习中的参数初始化和模型简化等方面都至关重要。通过理解这些基础概念，读者将能够更好地理解并应用矩阵分解技术解决实际问题，提升算法性能和效率。矩阵分解是信息技术领域的一座桥梁，连接着基础理论与实际应用。虽然本文无法穷尽所有细节，但为读者提供了一个坚实的基础，以便进一步探索这个富有挑战性和创新性的研究领域。

Jun Lu

Part I

Gaussian Elimination

1. LU Decomposition

Perhaps the best known and the ﬁrst matrix decomposition we should know about is the

LU decomposition. We now illustrate the results in the following theorem and the proof of

the existence of which will be delayed in the next sections.

Theorem 1.1: (LU Decomposition with Permutation)

Every nonsingular n × n square matrix A can be factored as

A = P LU,

where P is a permutation matrix, L is a unit lower triangular matrix (i.e., lower triangular

matrix with all 1’s on the diagonal), and U is a nonsingular upper triangular matrix.

Note that, in the remainder of this text, we will put the decomposition-related results

in the blue box. And other claims will be in a gray box. This rule will be applied for the

rest of the survey without special mention.

Remark 1.2: (Decomposition Notation)

The above decomposition applies to any nonsingular matrix A. We will see that this de-

composition arises from the elimination steps in which case row operations of subtraction

and exchange of two rows are allowed where the subtractions are recorded in matrix L

and the row exchanges are recorded in matrix P . To make this row exchange explicit, the

common form for the above decomposition is QA = LU where Q = P

that records the

exact row exchanges of the rows of A. Otherwise, the P would record the row exchanges

of LU . In our case, we will make the decomposition to be clear for matrix A rather than

for QA. For this reason, we will put the permutation matrix on the right-hand side of

the equation for the remainder of the text without special mention.

Speciﬁcally, in some cases, we will not need the permutation matrix. This decomposition

relies on the leading principal minors. We provide the deﬁnition which is important for the

illustration.

Deﬁnition 1.3: (Leading Principal Minors)

Let A be an n ×n square matrix. A k ×k submatrix of A obtained by deleting the last

n −k columns and the last n −k rows from A is called a k-th order leading principal

submatrix of A, that is, the k × k submatrix taken from the top left corner of A.

The determinant of the k × k leading principal submatrix is called a k-th order leading

principal minor of A.

Under mild conditions on the leading principal minors of matrix A, the LU decomposi-

tion will not involve the permutation matrix.

Matrix Decomposition and Applications

Theorem 1.4: (LU Decomposition without Permutation)

For any n × n square matrix A, if all the leading principal minors are nonzero, i.e.,

det(A

1:k,1:k

) 6= 0, for all k ∈ {1, 2, . . . , n}, then A can be factored as

A = LU ,

where L is a unit lower triangular matrix (i.e., lower triangular matrix with all 1’s on the

diagonal), and U is a nonsingular upper triangular matrix.

Speciﬁcally, this decomposition is unique. See Corollary 1.8.

Remark 1.5: (Other Forms of the LU Decomposition without Permutation)

The leading principal minors are nonzero, in another word, means the leading principal

submatrices are nonsingular.

Singular A In the above theorem, we assume A is nonsingular as well. The LU de-

composition also exists for singular matrix A. However, the matrix U will be singular as

well in this case. This can be shown in the following section that, if matrix A is singular,

some pivots will be zero, and the corresponding diagonal values of U will be zero.

Singular leading principal submatrices Even if we assume matrix A is nonsingular,

the leading principal submatrices might be singular. Suppose further that some of the

leading principal minors are zero, the LU decomposition also exists, but if so, it is again

not unique.

We will discuss where this decomposition comes from in the next section. There are

also generalizations of LU decomposition to non-square or singular matrices, such as rank-

revealing LU decomposition. Please refer to (Pan, 2000; Miranian and Gu, 2003; Dopico

et al., 2006) or we will have a short discussion in Section 1.10.

1.1 Relation to Gaussian Elimination

Solving linear system equation Ax = b is the basic problem in linear algebra. Gaussian

elimination transforms a linear system into an upper triangular one by applying simple

elementary row transformations on the left of the linear system in n − 1 stages if A ∈

n×n

. As a result, it is much easier to solve by a backward substitution. The elementary

transformation is deﬁned rigorously as follows.

Deﬁnition 1.6: (Elementary Transformation)

For square matrix A, the following three transformations are referred as elementary

row/column transformations:

1. Interchanging two rows (or columns) of A;

2. Multiplying all elements of a row (or a column) of A by some nonzero number;

Jun Lu

3. Adding any row (or column) of A multiplied by a nonzero number to any other row

(or column);

Speciﬁcally, the elementary row transformations of A are unit lower triangular to multiply

A on the left, and the elementary column transformations of A are unit upper triangular

to multiply A on the right.

The Gaussian elimination is described by the third type - elementary row transformation

above. Suppose the upper triangular matrix obtained by Gaussian elimination is given by

U = E

n−1

n−2

. . . E

A, and in the k-th stage, the k-th column of E

k−1

k−2

. . . E

A is

x ∈ R

. Gaussian elimination will introduce zeros below the diagonal of x by

= I − z

where e

∈ R

is the k-th unit basis vector, and z

∈ R

is given by

= [0, . . . , 0, z

k+1

, . . . , z

]

, z

, ∀i ∈ {k + 1, . . . , n}.

We realize that E

is a unit lower triangular matrix (with 1’s on the diagonal) with only

the k-th column of the lower submatrix being nonzero,







1 . . . 0 0 . . . 0

0 . . . 1 0 . . . 0

0 . . . −z

k+1

1 . . . 0

0 . . . −z

0 . . . 1







and multiplying on the left by E

will introduce zeros below the diagonal:

x =







1 . . . 0 0 . . . 0

0 . . . 1 0 . . . 0

0 . . . −z

k+1

1 . . . 0

0 . . . −z

0 . . . 1













k+1



















For example, we write out the Gaussian elimination steps for a 4 ×4 matrix. For simplicity,

we assume there are no row permutations. And in the following matrix,  represents a

value that is not necessarily zero, and boldface indicates the value has just been changed.

A Trivial Gaussian Elimination For a 4 × 4 Matrix:







   







−→







   

0 



 



 



0 



 



 



0 



 



 









−→







   

0   

0 0 



 



0 0 



 









−→







   

0   

0 0  

0 0 0 









, (1.1)

Matrix Decomposition and Applications

where E

, E

are lower triangular matrices. Speciﬁcally, as discussed above, Gaus-

sian transformation matrices E

’s are unit lower triangular matrices with 1’s on the diag-

onal. This can be explained that for the k-th transformation E

, working on the matrix

k−1

. . . E

A, the transformation subtracts multiples of the k-th row from rows {k + 1, k +

2, . . . , n} to get zeros below the diagonal in the k-th column of the matrix. And never use

rows {1, 2, . . . , k − 1}.

For the transformation example above, at step 1, we multiply on the left by E

so that

multiples of the 1-st row are subtracted from rows 2, 3, 4 and the ﬁrst entries of rows 2, 3, 4

are set to zero. Similar situations for step 2 and step 3. By setting L = E

−1

and letting the matrix after elimination be U,

we get A = LU. Thus we obtain an LU

decomposition for this 4 × 4 matrix A.

Deﬁnition 1.7: (Pivot)

First nonzero entry in the row after each elimination step is called a pivot. For example,

the blue crosses in Equation (1.1) are pivots.

But sometimes, it can happen that the value of A

is zero. No E

can make the next

elimination step successful. So we need to interchange the ﬁrst row and the second row via

a permutation matrix P

. This is known as the pivoting, or permutation.

Gaussian Elimination With a Permutation In the Beginning:







0   

   







−→









 



 



 



0 



 



 



   







−→







   

0 



 



 



0 



 



 



0 



 



 









−→







   

0   

0 0 



 



0 0 



 









−→







   

0   

0 0  

0 0 0 









By setting L = E

−1

and P = P

−1

, we get A = P LU . Therefore we obtain a full

LU decomposition with permutation for this 4 ×4 matrix A.

In some situations, other permutation matrices P

, P

, . . . will appear in between the

lower triangular E

’s. An example is shown as follows.

Gaussian Elimination With a Permutation In Between:







   







−→







   

0 0 



 



0 



 



 



0 



 



 









−→







   

0 



 



 



0 0 



 



0   







−→







   

0   

0 0  

0 0 0 









2. The inverses of unit lower triangular matrices are also unit lower triangular matrices. And the products

of unit lower triangular matrices are also unit lower triangular matrices.

Jun Lu

In this case, we ﬁnd U = E

A. In Section 1.3 or Section 1.9.1, we will show that the

permutations in-between will result in the same form A = P LU where P takes account of

all the permutations.

The above examples can be easily extended to any n ×n matrix if we assume there are

no row permutations in the process. And we will have n − 1 such lower triangular trans-

formations. The k-th transformation E

introduces zeros below the diagonal in the k-th

column of A by subtracting multiples of the k-th row from rows {k + 1, k + 2, . . . , n}. Fi-

nally, by setting L = E

−1

. . . E

−1

n−1

we obtain the LU decomposition A = LU (without

permutation).

1.2 Existence of the LU Decomposition without Permutation

The Gaussian elimination or Gaussian transformation shows the origin of the LU decompo-

sition. We then prove Theorem 1.4 rigorously, i.e., the existence of the LU decomposition

without permutation by induction.

Proof [of Theorem 1.4: LU Decomposition without Permutation] We will prove

by induction that every n ×n square matrix A with nonzero leading principal minors has a

decomposition A = LU. The 1 × 1 case is trivial by setting L = 1, U = A, thus, A = LU.

Suppose for any k ×k matrix A

with all the leading principal minors being nonzero has

an LU decomposition without permutation. If we prove any (k + 1) ×(k + 1) matrix A

k+1

can also be factored as this LU decomposition without permutation, then we complete the

proof.

For any (k+1)×(k+1) matrix A

k+1

, suppose the k-th order leading principal submatrix

of A

k+1

is A

with the size of k ×k. Then A

can be factored as A

= L

with L

being

a unit lower triangular matrix and U

being a nonsingular upper triangular matrix from

the assumption. Write out A

k+1

as A

k+1





. Then it admits the factorization:

k+1









0 z



= L

k+1

where b = L

y, c

= x

, d = x

y + z, L

k+1





, and U

k+1



0 z



. From

the assumption, L

and U

are nonsingular. Therefore

y = L

−1

b, x

= c

−1

, z = d − x

If further, we could prove z is nonzero such that U

k+1

is nonsingular, we complete the proof.

Since all the leading principal minors of A

k+1

are nonzero, we have det(A

k+1

) =

det(A

)· det(d − c

−1

b) = det(A

) · (d − c

−1

b) 6= 0, where d − c

−1

b is a scalar.

As det(A

) 6= 0 from the assumption, we obtain d − c

−1

b 6= 0. Substitute b = L

and c

= x

into the formula, we have d −x

−1

y = d −x

)

−1

y =

d − x

y 6= 0 which is exactly the form of z 6= 0. Thus we ﬁnd L

k+1

with all the values

3. By the fact that if matrix M has a block formulation: M =



A B

C D



, then det(M ) = det(A) det(D −

−1

B).

剩余183页未读，继续阅读

努力+努力=幸运

粉丝: 3
资源: 136

矩阵分解：理论与机器学习应用概述

Proper orthogonal decomposition and its applications.pdf

论文研究-On Combining Trilinear Decomposition and ICA.pdf

[Meyer]_Matrix_Analysis_And_Applied_Linear_Algebra(b-ok.org)text book.pdf

sparse matrix LU decomposition

important numpy

解释这个bug：numpy.linalg.LinAlgError: Schur decomposition solver error.

实现用Latex写matrix operation programming test plan. describe each part respectively, and write the cases in tables. 1. Introduction 2.multiply 3. arrayFromTxtFile 4. arrayToTxtFile 5. minor 6. determinant 7. inverse 8. inverseLU 9. inverseCD

numpy.linalg.LinAlgError: Singular matrix

最新资源