Applications of eigenvectors

很多时候需要把已有问题转化为特征值问题。

1. 有一个对称矩阵（有时候是对称半正定矩阵），我们想要找一个方便的基。
2. 具体的优化问题。

Setup

Given: Collection of data points \(x_i\)

• Age
• Weight
• Blood pressure
• Heart rate

Find: Correlations between different dimensions

Simplest Model

One-dimensional subspace:

\[ \mathbf{x_i} \approx c_i \mathbf{v}, \quad \mathbf{v} \text{ unknown} \]

Equivalently:

\[ \mathbf{x_i} \approx c_i \hat{\mathbf{v}}, \quad \hat{\mathbf{v}} \text{ unknown with } ||\hat{\mathbf{v}}||_2 = 1 \]

Variational Idea

\[ \text{minimize } \sum_{i=1}^n ||\mathbf{x_i} - \text{proj}_{\hat{\mathbf{v}}} \mathbf{x_i}||_2^2\\ \text{subject to } ||\hat{\mathbf{v}}||_2 = 1 \]

What does the constraint do?

• Does not affect optimal \(\hat{\mathbf{v}}\).
• Removes scaling ambiguity.

Geometric Interpretation

Review from Last Lecture

\[ \begin{aligned} &\min_{c_i} \sum_i ||\mathbf{x_i} - c_i \hat{\mathbf{v}}||_2^2 \\&\xRightarrow {c_i = \mathbf{x_i}\cdot \hat{\mathbf{v}}} \sum_i ||\mathbf{x_i} - (\mathbf{x_i}\cdot \hat{\mathbf{v}}) \hat{\mathbf{v}}||_2^2\\ &= \sum_i ||\mathbf{x_i}||_2^2 - 2 \sum_i (\mathbf{x_i}\cdot \hat{\mathbf{v}})^2 + \sum_i (\mathbf{x_i}\cdot \hat{\mathbf{v}})^2\\ &= \sum_i ||\mathbf{x_i}||_2^2 - \sum_i (\mathbf{x_i}\cdot \hat{\mathbf{v}})^2\\ &= \text{const.} - \sum_i (\mathbf{x_i}\cdot \hat{\mathbf{v}})^2\\ &= \text{const.} - ||X^T \hat{\mathbf{v}}||_2^2 \\ &= \text{const.} - \hat{\mathbf{v}}^T X X^T \hat{\mathbf{v}}, \end{aligned} \]

\[ X=\begin{bmatrix} | & | & & | \\ \mathbf{x_1} & \mathbf{x_2} & \cdots & \mathbf{x_n} \\ | & | & & | \end{bmatrix}\\ \]

\[ X^T \hat{\mathbf{v}} = \begin{bmatrix} \mathbf{x_1}\cdot \hat{\mathbf{v}} \\ \mathbf{x_2}\cdot \hat{\mathbf{v}} \\ \vdots \\ \mathbf{x_n}\cdot \hat{\mathbf{v}} \end{bmatrix} \]

Equivalent Optimization

\[ \textrm{maximize } ||X^T \hat{\mathbf{v}}||_2^2\\ \textrm{subject to } ||\hat{\mathbf{v}}||_2 = 1 \]

homogeneous quadratic function with quadratic constraint，有二次约束（尤其是norm为1）的齐次二次优化问题，可以转化为特征值问题。

\[ \Lambda(\hat{\mathbf{v}};\lambda) = \frac{1}{2} \hat{\mathbf{v}}^T X X^T \hat{\mathbf{v}} + \lambda (\frac{1}{2} - \frac{1}{2} ||\hat{\mathbf{v}}||_2^2)\\ \mathbf{0} = \nabla_{\hat{\mathbf{v}}} \Lambda(\hat{\mathbf{v}};\lambda) = X X^T \hat{\mathbf{v}} - \lambda \hat{\mathbf{v}}\\ \Rightarrow X X^T \hat{\mathbf{v}} = \lambda \hat{\mathbf{v}}\\ \]

\[ \mathbf{v} X X^T \hat{\mathbf{v}} = \lambda \mathbf{v} \hat{\mathbf{v}} = \lambda\\ \] 因此最优的\(\hat{\mathbf{v}}\)是\(X X^T\)的最大的特征值对应的特征向量。

End Goal

Eigenvector of \(X X^T\) with largest eigenvalue.

"Firs principal component"

More after SVD.

问题转化

\[ \min \frac{1}{2} x^T A x - x^T b \rightarrow Ax = b\\ \min \frac{1}{2} x^T A x \text{ s.t. } ||x||_2^2 = 1 \rightarrow Ax = \lambda x, A \text{ positive semidefinite} \]

Physics

Newton:

\[ \mathbf{F} = m \frac{d^2 \mathbf{x}}{dt^2} \]

Hooke:

\[ \mathbf{F} = -k (\mathbf{x}-\mathbf{y}) \]

\[ \mathbf{F}\in \mathbb{R}^{3n}, \mathbf{X} \in \mathbb{R}^{3n}\\ \mathbf{F}=M\mathbf{X}''=A\mathbf{x}\\ v:=x' \]

\[ \frac{d}{dt} \begin{bmatrix} \mathbf{x} \\ \mathbf{v} \end{bmatrix} = \begin{bmatrix} \mathbf{0} & I_{3n \times 3n}\\ M^{-1}A & \mathbf{0} \end{bmatrix} \begin{bmatrix} \mathbf{x} \\ \mathbf{v} \end{bmatrix} \]

General Linear ODE

\(\mathbf{y}\)是关于时间的向量值函数，\(\mathbf{y}_i\)是\(B\)的特征向量，\(\lambda_i\)是特征值。 \[ \mathbf{y}' = B \mathbf{y} \\ B \mathbf{y}_i = \lambda_i \mathbf{y}_i\\ \]

可以假设： \[ \mathbf{y}(0)= c_1 \mathbf{y}_1 + c_2 \mathbf{y}_2 + \cdots + c_k \mathbf{y}_k\\ \] 此外，假设\(\mathbf{y}_i\) span \(\mathbb{R}^n\)，则： \[ \mathbf{y}(t) = \sum_{i=1}^n c_i(t) \mathbf{y}_i\\ B\mathbf{y} = \sum_{i=1}^n c_i(t) B \mathbf{y}_i = \sum_{i=1}^n c_i(t) \lambda_i \mathbf{y}_i\\ \mathbf{y}'(t) = \sum_{i=1}^n c_i'(t) \mathbf{y}_i\\ \] 因为\(B\mathbf{y} = \mathbf{y}'\): \[ c_i'(t) = \lambda_i c_i(t)\\ \rightarrow c_i(t) = c_i(0) e^{\lambda_i t}\\ \mathbf{y}(t) = c_1 e^{\lambda_1 t} \mathbf{y}_1 + c_2 e^{\lambda_2 t} \mathbf{y}_2 + \cdots + c_k e^{\lambda_k t} \mathbf{y}_k\\ \]

Linear Systems

\[ \mathbf{b} = c_1 \mathbf{x}_1 + c_2 \mathbf{x}_2 + \cdots + c_k \mathbf{x}_k\\ A \mathbf{x} = \mathbf{b}\\ \Rightarrow \mathbf{x} = \frac{c_1}{\lambda_1} \mathbf{x}_1 + \frac{c_2}{\lambda_2} \mathbf{x}_2 + \cdots + \frac{c_k}{\lambda_k} \mathbf{x}_k\\ \]

Verify:

\[ A \mathbf{x} = \sum_{i=1}^k \frac{c_i}{\lambda_i} A \mathbf{x}_i = \sum_{i=1}^k \frac{c_i}{\lambda_i} \lambda_i \mathbf{x}_i = \sum_{i=1}^k c_i \mathbf{x}_i = \mathbf{b} \]

Organizing a Collection

Setup

Have: n items in a dataset

\(w_{ij} \geq 0\) similarity of items \(i\) and \(j\)

\(w_{ij} = w_{ji}\)

Want: \(x_i\) embedding on \(\mathbb{R}\)

我们希望\(w_{ij}\)越大，\(x_i\)和\(x_j\)越接近: \[ \min_{\{x_i\}} E(\mathbf{x}),\\ E(\mathbf{x}) = \sum_{i,j} w_{ij} (x_i - x_j)^2,\\ \text{s.t. } ||\mathbf{x}||_2^2 = 1 \leftrightarrow \sum_i x_i^2 = 1\\ \mathbf{1} \cdot \mathbf{x} = 0 \leftrightarrow \sum_i x_i = 0 \]

Let \(a:=w \cdot \mathbf{1}\),

\[ \begin{aligned} E(\mathbf{x}) &= \sum_{i,j} w_{ij} (x_i^2 - 2x_i x_j + x_j^2) \\ &= \sum_{i,j} w_{ij} x_i^2 - 2 \sum_{i,j} w_{ij} x_i x_j + \sum_{i,j} w_{ij} x_j^2\\ &= 2\sum_{i} a_i x_i^2 - 2 \sum_{i,j} w_{ij} x_i x_j\\ &= 2x^T A x - 2x^T W x\\ &= 2x^T (A - W) x, \end{aligned}\\ A=diag(a)\\ \]

Fact:

\[ (A-W) \mathbf{1} = diag(a) \mathbf{1} - W \mathbf{1} = a - a = 0 \]

Lagrange multiplier:

\[ \Lambda = 2x^T (A-W) x - \lambda (x^T x - 1) - \mu (\mathbf{1}^T x)\\ \Rightarrow \nabla_x \Lambda = 4(A-W)x - 2 \lambda x - \mu \mathbf{1} = 0\\ \]

Premultiply by \(\mathbf{1}^T\) on both sides:

\[ \begin{aligned} &\mathbf{1}^T 4(A-W)x - \mathbf{1}^T 2 \lambda x - \mathbf{1}^T \mu \mathbf{1} \\ &= 4 \mathbf{1}^T (A-W)x - 2 \lambda \mathbf{1}^T x - \mu n \\ &= 0 - 0 - \mu n = 0\\ &\Rightarrow \mu = 0 \end{aligned}\\ \therefore \Lambda = 0 \Rightarrow 2(A-W)x = \lambda x\\ E(\mathbf{x}) = x^T (A-W) x = x^T \lambda x = \lambda x^T x = \lambda \]

\(\mathbf{x}\) is eigenvector of \(A-W\) with smallest \(\lambda\not=0\).

\(\lambda\) 不为0的原因是\(E(\mathbf{x})\)不能为0，否则所有的\(x_i\)相等，与约束条件矛盾。

Definition

Eigenvalue and eigenvector

An eigenvector \(\mathbf{x}\not=0\) of \(A \in \mathbb{R}^{n \times n}\) satisfies \(A \mathbf{x} = \lambda \mathbf{x}\) for some \(\lambda \in \mathbb{R}\); \(\lambda\) is an eigenvalue. Complex eigenvalues and eigenvectors instead have \(\lambda \in \mathbb{C}\) and \(x \in \mathbb{C}^n\).

Scale doesn't matter!

\(\rightarrow\) can constrain \(||\mathbf{x}||_2 = 1\).

Spectrum and spectral radius

The spectrum of \(A\) is the set of all eigenvalues of \(A\). The spectral radius \(\rho(A)\) is the maximum value \(|\lambda|\) over all eigenvalues \(\lambda\) of \(A\).

Eigenproblems in the Wild

• Optimize \(A\mathbf{x}\) subject to \(||\mathbf{x}||_2 = 1\).(important!)
• ODE/PDE problem: Closed solutions and approximations for \(\mathbf{y}' = B \mathbf{y}\).
• Critical points of Rayleigh quotient: \(\frac{\mathbf{x}^T A \mathbf{x}}{||\mathbf{x}||_2^2}\).