MIT | 数据分析、信号处理和机器学习中的矩阵方法 笔记系列 Lecture 5 Positive Definite and Semidefinite Matrices

本系列为MIT Gilbert Strang教授的"数据分析、信号处理和机器学习中的矩阵方法"的学习笔记。

• Gilbert Strang & Sarah Hansen | Sprint 2018
• 18.065: Matrix Methods in Data Analysis, Signal Processing, and Machine Learning
• 视频网址: https://ocw.mit.edu/courses/18-065-matrix-methods-in-data-analysis-signal-processing-and-machine-learning-spring-2018/
• 关注下面的公众号，回复“ 矩阵方法 ”，即可获取 本系列完整的pdf笔记文件~

内容在CSDN、知乎和微信公众号同步更新

• CSDN博客
• 知乎
• 微信公众号

• Markdown源文件暂未开源，如有需要可联系邮箱
• 笔记难免存在问题，欢迎联系邮箱指正

Lecture 0: Course Introduction

Lecture 1 The Column Space of $A$ Contains All Vectors $Ax$

Lecture 2 Multiplying and Factoring Matrices

Lecture 3 Orthonormal Columns in $Q$ Give $Q^{\prime }Q=I$

Lecture 4 Eigenvalues and Eigenvectors

Lecture 5 Positive Definite and Semidefinite Matrices

Lecture 6 Singular Value Decomposition (SVD)

Lecture 7 Eckart-Young: The Closest Rank $k$ Matrix to $A$

Lecture 8 Norms of Vectors and Matrices

Lecture 9 Four Ways to Solve Least Squares Problems

Lecture 10 Survey of Difficulties with $Ax=b$

Lecture 11 Minimizing ||x|| Subject to $Ax=b$

Lecture 12 Computing Eigenvalues and Singular Values

Lecture 13 Randomized Matrix Multiplication

Lecture 14 Low Rank Changes in $A$ and Its Inverse

Lecture 15 Matrices $A(t)$ Depending on $t$, Derivative = $dA/dt$

Lecture 16 Derivatives of Inverse and Singular Values

Lecture 17 Rapidly Decreasing Singular Values

Lecture 18 Counting Parameters in SVD, LU, QR, Saddle Points

Lecture 19 Saddle Points Continued, Maxmin Principle

Lecture 20 Definitions and Inequalities

Lecture 21 Minimizing a Function Step by Step

Lecture 22 Gradient Descent: Downhill to a Minimum

Lecture 23 Accelerating Gradient Descent (Use Momentum)

Lecture 24 Linear Programming and Two-Person Games

Lecture 25 Stochastic Gradient Descent

Lecture 26 Structure of Neural Nets for Deep Learning

Lecture 27 Backpropagation: Find Partial Derivatives

Lecture 28 Computing in Class [No video available]

Lecture 29 Computing in Class (cont.) [No video available]

Lecture 30 Completing a Rank-One Matrix, Circulants!

Lecture 31 Eigenvectors of Circulant Matrices: Fourier Matrix

Lecture 32 ImageNet is a Convolutional Neural Network (CNN), The Convolution Rule

Lecture 33 Neural Nets and the Learning Function

Lecture 34 Distance Matrices, Procrustes Problem

Lecture 35 Finding Clusters in Graphs

Lecture 36 Alan Edelman and Julia Language

Lecture 5 Positive Definite and Semidefinite Matrices

5.1 Positive Definite Matrix

正定矩阵的性质

Topics in this lecture:

• For Symmetric Positive Definite Matrix $S$ (实矩阵： 正定矩阵 (一定是对称阵) $\Rightarrow$ 且特征值>0)

  1. All ${\lambda }_i$ > 0
  2. Energy $x^{T}Sx>0$ (all $x\ne 0$)
  3. $S=A^{T}A$ (independent cols in A)
  4. All leading determinants $>0$
  5. All points in elimination $>0$

• An Example:

  • $S=\left[\begin{array}{cc}3& 4\\ 4& 5\end{array}\right]$

    ▪ $S$ is symmetric

• Is $S$ Positive Definite?

  • $Det(S)=15-16=-1$

  • 意味着${\lambda }_1{\lambda }_2=-1$, 特征值不可能都是正的

• 如何make S be positive?

  ▪ add stuff to the main diagonal $\Rightarrow$ make $S$ more positive

  ▪ 将S的右下角替换为6

  ▪ $S=\left[\begin{array}{cc}3& 4\\ 4& 6\end{array}\right]$

• 需要 All leading determinants $>0$ pivot

  • $S=\left[\begin{array}{cc}-3& 4\\ 4& -6\end{array}\right]$ 非正定

• 再看 All points in elimination $>0$

  ▪ 1st pivot = 3;

  ▪ $S$ $\to$ $\left[\begin{array}{cc}3& 4\\ 0& 2/3\end{array}\right]$ $\Rightarrow$ 2nd pivot = $2/3>0$

正定矩阵的energy function及其在优化理论中的应用

• 关于 Energy $x^{T}Sx>0$ (all $x\ne 0$)

  • 记 $f(x)=x^{T}Sx=\left[\begin{array}{cc}{x}_1& x_2\end{array}\right]\left[\begin{array}{cc}3& 4\\ 4& 6\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]=\left[\begin{array}{cc}{x}_1& x_2\end{array}\right]\left[\begin{array}{c}3x_1+4x_2\\ 4x_1+6x_2\end{array}\right]$ = $3x_1^2+6x_2^2+8x_1{x}_2$

  • $f(x)$ = $3x_1^2+6x_2^2+8x_1{x}_2$

    ▪ f(x) 关于$x_1$和$x_2$的函数如下图所示 (图中使用(x,y)表示$x$的坐标)

    ▪ 此即$f(x)$能量函数 (Energy function), and a convex function

    ▪ 该能量函数始终大于0 (all $x\ne 0$) --> 正定矩阵

    ▪ deep learning 中的 loss function 也是此类 energy function $\Rightarrow$ minimize the function

  • Therefore, $f(x)>0$ (for all $x\ne 0$)

    🚩 对于 quadratic , convex means positive definite / positive semidefinite

    🚩 使用gradient descent 进行求解, the big algorithm of deep learning、 neural nets and machine learning

    🚩 特征值决定了the energy function的形状： If you have a very small eigenvalue and a very large eigenvalue, the shape of the “bowl” will be thin and deep $\Rightarrow$ difficult for the gradient descent algorithms !!

    🚩 这也是正定矩阵非常重要的一个原因：能够确定根据损失函数解优化问题的性质，并根据特征值估计难度

正定矩阵的判定

• Question 1: If $S$ and $T$ are positive definite matrices, Is $S=S_1+S_2$ a positive definite matrix?

  • S,T are pos. def.

  • What about S+T?

  • 思路：使用最开始的5个test:

    ▪ 1 All ${\lambda }_i$ > 0

    ▪ 2 Energy $x^{T}Sx>0$ (all $x\ne 0$)

    ▪ 3 $S=A^{T}A$ (independent cols in A)

    ▪ 4 All leading determinants $>0$

    ▪ 5 All points in elimination $>0$

  • Test 1: Eigenvalues – Eigenvalue of (S+T) is not clear from S and T

  • Test 2: Energy $x^T(S+T)x>0?$ for all x $\ne 0$

    ✅ Yes! $x^T(S+T)x=x^{T}Sx+x^{T}Tx>0$

    ✅ So the answer is yes: (S+T) is pos. def.

• Question 2: If $S$ is a positive definite matrix, Is $S^{-1}$ a positive definite matrix?

  • Test 1: Good!
  • $S^{-}1$ has eigenvalues $1/\lambda$
  • So, Yes – $S^{-1}$ is a positive definite matrix

• Question 3: If $S$ is a positive definite matrix, Is $SM$ a positive definite matrix? (M is another matrix)

  • ans: the question was not any good

  • $SM$ is probably not symmetric 只有对称矩阵，才能确保特征值都是实数，才有之前的5个test

  • How about $Q^{T}SQ$ (Q is a orthogonal matrix)

    ▪ $Q^{T}SQ$ is a symmetric matrix

    ▪ Yes!

    ▪ Test 1: $Q^{T}SQ$ = $Q^{-1}SQ$ 与 matrix $S$ similar $\Rightarrow$ the consequence of being similar: same eigenvalues Pos. def.

    ▪ Test 2: $x^T{Q}^{T}SQx=(Qx{)}^{T}S(Qx)>0$ $\Rightarrow$ Pos. def.

5.2 Positive Semi-Definite (PSD) Matrix

半正定矩阵的性质

• For Semi-Positive Definite Matrix $S$ (实矩阵： 正定矩阵 (一定是对称阵) $\Rightarrow$ 且特征值>0)

  1. All ${\lambda }_i$ $\ge$ 0
  2. Energy $x^{T}Sx\ge 0$ (all $x\ne 0$)
  3. $S=A^{T}A$ (dependent columns allowed)
  4. All leading determinants $\ge 0$
  5. All points in elimination $\ge 0$

• Semi-Positive Definite is the borderline

  • Example: $S=\left[\begin{array}{cc}3& 4\\ 4& 16/3\end{array}\right]$

  • (Test 1)关于eigenvalues:

    ▪ 根据 determinant $\Rightarrow$ ${\lambda }_2=0$

    ▪ 根据 trace $\Rightarrow$ ${\lambda }_1=3+16/3$

半正定矩阵举例

• An example: $S=\left[\begin{array}{ccc}1& 1& 1\\ 1& 1& 1\\ 1& 1& 1\end{array}\right]$

  • Semidef

  • Test 1: Its eigenvalues: {3,0,0}

  • 如何看出来它的特征值？$\downarrow$

    🚩 Because the rank is 1 $\Rightarrow$ only one non-zero eigenvalues;

    🚩 and the trace is $3$ $\Rightarrow$ the eigenvalues are {3,0,0}

  • Test 3: write it as $S=A^{T}A$

    🚩 becaues it is symmetric, it can be write as：

    🚩 $S=Q\Lambda Q^T$ = ${\lambda }_1{q}_1{q}_1^T+{\lambda }_2{q}_2{q}_2^T+{\lambda }_3{q}_3{q}_3^T$, 其中 ${\lambda }_2$ and ${\lambda }_3$ = 0 $\Rightarrow$ $S={\lambda }_1{q}_1{q}_1^T=3([1,1,1{]}^T/(\sqrt{3}))\times [1,1,1]/(\sqrt{3})=q_1^T{q}_1$

Next week:

• singular value decomposition