Eigenvalues, Eigenvectors and SVD

Eigenvector and Eigenvalues

Theorem. Given a symmetric matrix $A \in \mathbb{R}^{n \times n}$ that is positive semi-definitive, there exists an orthogonal matrix $V \in \mathbb{R}^{n \times n}$, and a diagonal matrix $\Sigma \in \mathbb{R}^{n \times n}$ with all entries non-negative, such that

$$A = V \Sigma V^T.$$

We need the following fact for the proof.

Fact. If a function $f: S \rightarrow \mathbb{R}$ is continuous on a closed set $S$, then it achieves maximum value at some point of $S$.

Proof. Consider the maximization problem:

Question to ponder: Explain the geometric meaning of the term $x^T A x$.

The corresponding Lagrange function is given by

Taking derivative with respect to $x$ gives

Existence of maximum solution: Note that $\{ x : x^T x = 1 \}$ is defined the boundary of the unit cycle, which is a closed set. Combined with the fact that $f \doteq (1 / 2) \cdot x^T A x$ is a continuous function (with respect to $x$), it takes its maximum value at some point in $\{ x : x^T x = 1 \}$. Denote this point $v_1 \in \{ x : x^T x = 1 \}$.

Gradient at the maximum point: At this point, it holds that

which implies that $v_1$ is an eigenvector of $A$. Denote its corresponding eigenvalue $\lambda_1$.

Question to ponder: Prove that $\lambda_1$ is the largest eigenvalue.

After finding $v_1$, consider a new optimization problem:

That is, we want to find a new unit vector that is orthogonal to $v_1$ while maximizing $\frac{1}{2} x^T A x$.

Existence of maximum solution. By the lemma and the facts:

1. $\{x : x^T x = 1\} \cap \{ x : v_1^T x = 0 \}$ is closed.
2. $\frac{1}{2} x^T A x$ is continuous.

Denote this maximum point $v_2$. Now consider the new Lagrange function for the optimization

Gradient at the maximum point: At this point, it holds that

Left multiplying $v_1^T$ gives

where $v_1^T A = (A v_1)^T$ follows from the symmetry of $A$, i.e., $A = A^T$.

Therefore,

It follows that $v_2$ is an eigenvector of $A$. Denote its associated eigenvalue $\lambda_2$.

In a similar manner, we can define

There exists an optimal point $v_3$. The derivative of Lagrange function at this point is

for some parameters $\lambda, \beta_1, \beta_2$. Left multiplying $v_1^T$ or $v_2^T$ gives $\beta_1 = 0$ and $\beta_2 = 0$ so that $v_3$ is an eigenvector of $A$.

Following the procedure, we can find $n$ eigenvectors $v_1, v_2, \ldots, v_n$ of $A$. Define

Then

Hence,

$\square$

Singular Vector Decomposition

In general, a matrix $A \in \mathbb{R}^{m \times n}$ is considered a linear mapping from $\mathbb{R}^n$ to $\mathbb{R}^m$. It takes a vector $x \in \mathbb{R}^n$ to a new one $Ax \in \mathbb{R}^m$. We are interested in the following question.

Is there a vector $x$, whose length ratio,

$$\max_{x \in \mathbb{R}^n } \frac{ \Vert Ax \Vert }{ \Vert x \Vert },$$

is maximized by the mapping?

As $\Vert x \Vert$ is a number,

Hence, it suffices to consider unit vectors, and the following optimization problem:

In this case, the objective function is $0.5 \cdot \Vert Ax \Vert^2 = 0.5 \cdot (Ax)^T (Ax) = 0.5 \cdot x^T A^T A x$.

Following similar process of previous section, we can find a set of eigenvectors $v_1, v_2, \ldots, v_n$ of $A^T A$. Define $U \in \mathbb{R}^{m \times n}$

Then $U { \sqrt \Sigma } V^T = A$, which is called the singular vector decomposition of $A$.

Finally, we can verify that the columns of $U$ are perpendicular: $\forall i \neq j, i, j \in [n]$,

as $v_i$ and $v_j$ are orthogonal eigenvectors of $A^T A$.