矩阵分解

$A$ is diagonalizable if and only if it has linearly independent eigenvectors, or equivalently, if the geometric multiplicity and the algebraic multiplicity of all the eigenvalues agree. A special case of this is if $A$ has $n$ distinct eigenvalues. Suppose we have eigenvalues $\lambda_1, \dots, \lambda_n$ and corresponding eigenvectors $v_1, \dots, v_n$. Then

Intuitively, this says that we can find a basis consisting of the eigenvectors of $A$. Useful for computing large powers of $A$, as $A^n = XD^n X^{-1}$. An important example is $A$ being real and symmetric implies $A$ is diagonalizable.

SVD is powerful in low-rank approximations of matrices. Unlike eigenvalue decomposition, SVD uses two unique bases (left/right singular vectors). For orthogonal matrices $U (m \times m), V (n \times n)$ and diagonal matrix $\Sigma (m \times n)$ with nonnegative diagonal entries in nonincreasing order, we can write any $m \times n$ matrix $A$ as:

Intuitively, this says that we can express $A$ as a diagonal matrix with suitable choices of (orthogonal) bases.

For nonsingular $A$, we can write $A = QR$, where $Q$ is orthogonal and $R$ is an upper triangular matrix with positive diagonal elements. QR decomposition assists in increasing the efficiency of solving $Ax = b$ for nonsingular $A$:

QR decomposition is very useful in efficiently solving large numerical systems and inversion of matrices. Furthermore, it is also used in least-squares when our data is not full rank.

For nonsingular $A$, we can write $A = LU$, where $L$ is a lower and $U$ is an upper triangular matrix. This decomposition assists in solving $Ax = b$ as well as computing the determinant:

If $A$ is symmetric positive definite, then $A$ can be expressed as $A = R^\intercal R$ via Cholesky decomposition, where $R$ is an upper triangular matrix with positive diagonal entries. Cholesky decomposition is essentially LU decomposition with $L = U^\intercal$. These decompositions are both useful for solving large linear systems.

Fix a vector $v \in \mathbb{R}^n$. The projection of $x \in \mathbb{R}^n$ onto $v$ is given by

More generally, if $S = \text{Span}\{v_1, \dots, v_k\} \subseteq \mathbb{R}^n$ has orthogonal basis $\{v_1, \dots, v_k\}$, then the projection of $x \in \mathbb{R}^n$ onto $S$ is given by

The main property is that $\text{proj}_S(x) \in S$ and $x - \text{proj}_S(x)$ is orthogonal to any $s \in S$. Linear Regression can be viewed as a projection of our observed data onto the subspace formed by the span of the collected data.