Linear Algebra

An overview of the chapter “Linear Algebra” from the famous book “Deep Learning” written by Ian Goodfellow, Yoshua Bengio and Aaron Courville. The authors create a brief introduction of the important concepts of linear algebra that help guide machine learning. All images and tables in this post are from their book.

Scalars, Vectors, Matrices and Tensors

The study of linear algebra involves several types of mathematical objects:

Scalars: A single number. For example,

$n = 10$

Vectors: An array of numbers. For example,

$x = \begin{bmatrix} x_0 \\ x_1 \\ . \\ . \\ . \\ x_n \end{bmatrix}$

To access elements 1 and 3 in array, we set $S = \begin{Bmatrix} 1,3 \end{Bmatrix}$ and use $x_S$ . To get all elemets other than 1 and 3, we use $x_{-S}$

Matrices: 2-D array of numbers. For example,

$A = \begin{bmatrix} x_{1,1} & x_{1,2}\\ x_{2,1} & x_{2,2} \end{bmatrix}$

Tensors: more than 2-D array. For example, $A_{i,j,k}$

One important operation on matrices is the transpose. The transpose of a matrix is the mirror image of the matrix across a diagonal line, called the main diagonal, running down and to the right, starting from its upper left corner. $(A^T)_{i,j} = A_{j,i}$

In Machine Learning, we allow addition of matrces and vectors where, $C_{i,j} = A_{i,j} + b{j}$ The implicit copying of b across each row is called broadcasting.

Multiplying Matrices and Vectors

Matrix Multiplication:

$C_{m*p} = A_{m*n}B_{n*p}$

where, $C_{i,j} = \sum _{k} A_{i,k}B_{k,j}$ .

Element wise product or Hadard product:

$C = A\odot B$

where, $C_{i,j} = A_{i,j}*B_{i,j}$ .

Dot product: Product of two vectors of same dimensionality.

$x\cdot y = x^Ty$

Matrix multiplication is associative ( $A(BC) = (AB)C$ ), distributive ( $A(B+C) = AB + AC$ ) but not commutative ( $AB \neq BA$ ). However, the commutative property holds for vector product ( $x^Ty = y^Tx$ ).

Also, note that $(AB)^T = B^TA^T$ .

Identity & Inverse Matrices

Linear algebra offers a powerful tool called matrix inversion, that allows us to analytically solve equation $Ax = b$ for many values of $A$ . We denote the identity matrix that preserves n-dimensional vectors as $I_{n}\in \mathbb{R}^{n*n}$ , and

$AA^{-1}= I$

where $A^{-1}$ is inverse of A. Also note that, $I_{n}x = x$ .

$Ax = b$
$A^{-1}Ax = A^{-1}b$
$I_{n}x = A^{-1}b$
$x = A^{-1}b$

Note that $x = A^{-1}b$ might or might not exist depending on the existence of inverse of $A$ .

Linear Dependence and Span

Suppose $Ax = b$ has 2 solutions $x,y$ , then $z = \alpha x + (1-\alpha)y$ is also a solution.

Formally, a linear combination of some set of vectors $\begin{Bmatrix} v^{(1)} ,... , v^{(n)} \end{Bmatrix}$ is given by multiplying each vector $v^{(i)}$ by a corresponding scalar coefficient and adding the results:

$\sum _{i}c_{i}v^{(i)}$

The span of a set of vectors is the set of all points obtainable by linear combination of the original vectors. Determining whether $Ax = b$ has a solution amounts to testing whether $b$ is in the span of columns of $A$ , aka column space or range of $A$ In order for the system $Ax = b$ to have a solution for all values of $b \in \mathbb{R}^{m}$ , we therefore require that the column space of A be all of $\mathbb{R}^{m}$ . If any point in $\mathbb{R}^{m}$ is excluded from th column space, that point is a potential value of $b$ that has no solution. The requirement that the column space of A be all of $\mathbb{R}^{m}$ implies immediately that $A$ must have at least $m$ columns, i.e., $n\geq m$ . Having $n\geq m$ is only a necessary condition for every point to have a solution, It is not however sufficient condition since, it is possible for some of the columns to be redundant.

A set of vectors is linearly independent if no vector in the set is a linear combination of other vectors. This means that for the column space of the matrix to encompass all of $\mathbb{R}^{m}$ , the matrix must contain at least one set of $m$ linearly independent columns. This condition is both necessary and sufficient for $Ax = b$ to have a solution for every value of $b$ . Note that the requirement is for a set to have exactly $m$ linear independent columns, not at least $m$ . In order for the matrix to have an inverse, we additionally need to ensure that $Ax = b$ has at most one solution for each value of $b$ . To do so, we need to ensure that matrix has at most m columns. Otherwise, there is more than one way of parametrizing each solution. Together, this means that the matrix must be a square, that is, we require that $m = n$ and that all of the columns must be linearly independent. A square matrix with linearly independent columns is known as singular. If $A$ is not square or is square, but singular, it can still be possible to solve the equation. However, we cannot use the method of matrix inversion to find the solution.

Norms

Norms are used to measure the size of a vector. Formally, the $L^{p}$ norm is given by:

$\left \| x \right \|_{p} = \left ( \sum _i\left | x_i \right |^{p} \right )^{\frac{1}{p}}$

for $p \in \mathbb{R}$ , $p \geq 1$ . Norm must follow 3 conditions:

$f(x)=0\Rightarrow x=0$
$f(x+y) \leq f(x) + f(y)$
$\forall \alpha \in \mathbb{R}, f(\alpha x) = \left | \alpha \right |f(x)$

The $L^2$ norm, with $p=2$ , is known as the Eucledian Norm and is equal to $(x^Tx)^{\frac{1}{2}}$ . The squared $L^2$ norm is more convenient to work with mathematically and computationally than the $L^2$ norm itself. If data is close to the origin is of high importance, we use $L^1$ norm. The $L^1$ norm may be simplified as $\left \| x \right \|_1 = \sum _i \left |x_i \right |$ . We sometimes measure the size of the vector by counting its number of nonzero elements. Some authors refer to this function as the “ $L^0$ norm”, but this is incorrect terminology. The number of non-zero entries in a vector is not a norm, because scaling the vector by $\alpha$ does not change the number of nonzero entries. The $L^1$ norm is often used as a substitute for the number of nonzero entries. One other norm is the max norm or $L^\infty$ which can be simplifies to the absolute value of the element with the largest magnitude in the vector, $\left \| x \right \|_{\infty} = \max_{i} \left | x_i \right |$ . Sometimes, we also wish to measure the size of a matrix. In the context of deep learning, the most common way to do this is with the otherwise obscure Frobenius norm:

$\left \| A \right \|_F = \sqrt{\sum _{i,j}A_{i,j}^2}$

which is similar to $L^2$ norm of vectors, but for matrices.

Furthermore, the dot product of two vectors can be rewritten in terms of norms. Specifically,

$x^Ty = \left \| x \right \|_2\left \| y \right \|_2\cos\theta$

Special Kinds of matrices and Vectors

Diagonal Matrix:

$D_{ij} = \left\{\begin{matrix} 1 &, i=j \\ 0 &, otherwise \end{matrix}\right.$

We write $diag(V)$ to denote a square diagonal matrix whose diagonal entries are given by the entries of vector $V$ . To compute $diag(V)x$ , we only need to scale each element $x_i$ by $v_i$ . Not all diagonal matrices need be square. It is possible to construct a rectangular diagonal matrix.

Symmetric Matrix: Matrix $A$ is said to be symmetric if $A^T=A$ , or $A_{i,j} = A_{j,i}$ .
Unit Vector: A vector with unit norm. $\left \| x \right \|_2 = 1$ .
Orthogonal Vectors: A vector $x$ and $y$ are said to be orthogonal if $x^Ty = 0$ . If both the vectors have non-zero norm, this means that they are at a 90 degree angle to each other. In $\mathbb{R}^n$ , at most $n$ vectors may be mutually orthogonal to each other with nonzero norm. If the vectors are not only orthogonal but also have a unit norm, we call them Orthonormal.
Orthogonal Matrix: A square matrix whose rows are mutually orthonormal and whose columns are mutually orthonormal. This would mean that $A^TA = AA^T = I$ . This would also imply that $A^{-1}=A^T$ .

Eigendecomposition

This is a matrix decomposition method in which we decompose a matrix into a set of eigenvectors and eigenvalues.

$A\upsilon = \lambda \upsilon$

Here, $A$ is a square matrix, $\upsilon$ is the eigenvector and $\lambda$ is the eigenvalue. If $\upsilon$ is an eigen vector, so is any rescaled vector $s\upsilon$ where $s \neq 0$ . Hence, we only consider unit vectors. Suppose that a matrix $A$ has $n$ linearly independent eigenvectors, $\begin{Bmatrix} \upsilon ^{(1)}, ..., \upsilon^{(n)} \end{Bmatrix}$ , with corresponding eigenvalues $\begin{Bmatrix} \lambda ^{(1)}, ..., \lambda ^{(n)} \end{Bmatrix}$ . We may concatenate all of the eigenvectors to form a matrix $V$ with one eigenvector per column: $V = \begin{bmatrix} \upsilon ^{(1)}, ..., \upsilon^{(n)} \end{bmatrix}$ . Likewise, we concatenate the eigenvalues to form a vector $\boldsymbol{\lambda}= \begin{bmatrix} \lambda \upsilon ^{(1)}, ..., \lambda \upsilon^{(n)} \end{bmatrix}$ . The eigendecomposition of A is then given by $A = Vdiag(\boldsymbol{\lambda})V^{-1}$ . We have seen that constructing matrices with specific eigenvalues and eigenvectors allows us to stretch space in desired directions. However, we often want to decompose matrices into their eigenvalues and eigenvectors. Not every matrix can be decomposed into eigenvalues and eigenvectors. However, every real symmetric matrix can be decomposed into an expression using only real-valued eigenvectors and eigenvalues:

$A = Q \wedge Q^T$

where $Q$ is an orthogonal matrix composed of eigenvectors of $A$ , and $\wedge$ is a diagonal matrix. While any real symmetric matrix $A$ is guaranteed to have an eigendecomposition, the eigendecomposition may not be unique. If any two or more eigenvectors share the same eigenvalue, then any set of orthogonal vectors lying in their span are also eigenvectors with that eigenvalue. By convention, we usually sort the entries of $\wedge$ in descending order. Under this convention, the eigendecomposition is unique only if all of the eigenvalues are unique.

The eigendecomposition of a matrix tells us many useful facts about the matrix. The matrix is singular if and only if any of the eigenvalues are zero. The eigendecomposition of a real symmetric matrix can also be used to optimize quadratic expressions of the form $f(x) = x^TAx$ subject to $\left \| x \right \|_2 = 1$ . Whenever, $x$ is equal to an eigenvector of $A$ , $f$ taks on the value of corresponding eigenvalue, since:

$A = Q \wedge Q^T \Leftrightarrow \wedge = Q^TAQ$

since $Q$ is orthogonal and $Q^{-1} = Q^T$ . A matrix whose eigenvalues are all positive is called positive definite. A matrix whose eigenvalues are all positive or zero-valued is called positive semidefinite. Likewise, if all eigenvalues are negative, the matrix is negative definite, and if all eigenvalues are negative or zero valued, it is negative semidefinite. Positive semidefinite matrices are interesting for two reasons:

They guarantee that $\forall x, x^TAx \geq 0$
They also guarantee that $x^TAx=0 \Rightarrow x=0$ .

Singular Value Decomposition

This is another method to factorize a matrix, into singular vectors and singular values. This is more generally applicable. Every real matrix has a SVD, but the same is not true for eigen decomposition. Here, we write $A$ in terms of three matrices:

$A=UDV^T$

Here, $A$ is a $m * n$ matrix, $U$ is defined to be a $m*m$ matrix, $D$ to be a $m*n$ matrix, and $V$ to be a $n*n$ matrix. The matrices $U$ and $V$ are both defined to be orthogonal matrices. The matrix $D$ is defined to be a diagonal matrix (not necessarily a square). The elements across the diagonal of $D$ are known as the singular values of the matrix $A$ . The columns of $U$ are known as left-singular vectors. The columns of $V$ are known as the right-singular vectors.

Furthermore, the left-singular vectors of $A$ are the eigenvectors of $AA^T$ , whereas the right-singular vectors of $A$ are the eigenvectors of $A^TA$ .

Moore Penrose Pseudoinverse

Matrix inversion is not defined for matrices that are not square. Suppose $A \in \mathbb{R}^{m*n}$ , if:

$m>n$ , no solutions of $Ax = y$
$n>m$ , multiple solutions of $Ax = y$

The Moore-Penrose pseudoinverse of $A$ is defined as a matrix $A^{+} = VD^{+}U^{T}$ , where $U$ , $D$ , and $V$ are the singular value decomposition of $A$ . $D^{+}$ is obtained by taking the reciprocal of its non-zero elements, then taking the transpose of the resulting matrix. When $A$ has more columns than rows, then solving a linear equation using the pseudoinverse provides one of the many possible solutions. Specifically, it provides the solution $x = A^{+}y$ with minimal Eucledian norm $\left \| x \right \|_2$ among all possible solutions. When $A$ has more rows than columns, it is possible for there to be no solution. In this case, using the pseudoinverse gives us the $x$ for which $Ax$ is as close as possible to $y$ in terms of Eucledian norm $\left \| Ax-y \right \|_2$

The Trace Operator

The trace operator gives the sum of all the diagonal entries of a matrix:

$Tr(A) = \sum _iA_{i,i}$

The trace operator provides an alternative way of writing the Frobenius norm of a matrix: $\left \| A \right \|_F = \sqrt{Tr(AA^T)}$ . Furthermore, the trace operator is invariant to the transpose operator: $Tr(A) = Tr(A^T)$ . Also, the trace operator is invariant to cyclic permutations, even if the output is of a different shape: $Tr(ABC) = Tr(BCA) = Tr(CAB)$ .

The Determinant

The determinant of a square matrix, denoted by $det(A)$ , is a function mapping matrices to real scalars. The determinant is equal to the product of all the eigenvalues of the matrix. The absolute value of the determinant can be thought of as a measure of how much multiplication by the matrix expands or contracts space. If the determinant is 0, the space is contracted completely along at least one dimension, causing it to lose all of its volume. If the determinant is 1, then the transformation preserves volume.

Principal Component Analysis

Principal component analysis, or PCA, is a technique widely used for applications such as dimensionality reduction, lossy data compression, feature extraction and data visualization. PCA can be defined as the orthogonal projection of the data onto a lower dimensional linear space, known as the principal subspace, such that the variance of the projected data is maximized. These lower dimensional linear space is obtained from the eigenvectors derived from eigendecomposition of the data. Equivalently, it can also be defined as the linear projection that minimizer the average projection cost, defined as the mean squared distance between the data points and their projections.

Written on January 10, 2021