Linear Algebra II: Matrix Operations¶

This topic, Linear Algebra II: Matrix Operations, builds on the basics of linear algebra. It is essential because these intermediate-level manipulations of tensors lie at the heart of most machine learning approaches and are especially predominant in deep learning.

Through the measured exposition of theory paired with interactive examples, you’ll develop an understanding of how linear algebra is used to solve for unknown values in high-dimensional spaces as well as to reduce the dimensionality of complex spaces. The content covered in this topic is itself foundational for several other topics in the Machine Learning Foundations series, especially Probability & Information Theory and Optimization.

Over the course of studying this topic, you'll:

• Develop a geometric intuition of what’s going on beneath the hood of machine learning algorithms, including those used for deep learning.
• Be able to more intimately grasp the details of machine learning papers as well as all of the other subjects that underlie ML, including calculus, statistics, and optimization algorithms.
• Reduce the dimensionalty of complex spaces down to their most informative elements with techniques such as eigendecomposition, singular value decomposition, and principal component analysis.

Note that this Jupyter notebook is not intended to stand alone. It is the companion code to a lecture or to videos from Jon Krohn's Machine Learning Foundations series, which offer detail on the following:

Review of Introductory Linear Algebra

• Modern Linear Algebra Applications
• Tensors, Vectors, and Norms
• Matrix Multiplication
• Matrix Inversion
• Identity, Diagonal and Orthogonal Matrices

Segment 2: Eigendecomposition

• Affine Transformation via Matrix Application
• Eigenvectors and Eigenvalues
• Matrix Determinants
• Matrix Decomposition
• Applications of Eigendecomposition

Segment 3: Matrix Operations for Machine Learning

• Singular Value Decomposition (SVD)
• The Moore-Penrose Pseudoinverse
• The Trace Operator
• Principal Component Analysis (PCA): A Simple Machine Learning Algorithm
• Resources for Further Study of Linear Algebra

Segment 1: Review of Introductory Linear Algebra¶

Vector Transposition¶

Return to slides here.

$L^2$ Norm¶

So, if units in this 3-dimensional vector space are meters, then the vector $x$ has a length of 25.6m

Return to slides here.

Matrices¶

Matrix Transposition¶

Return to slides here.

Matrix Multiplication¶

Scalars are applied to each element of matrix:

Using the multiplication operator on two tensors of the same size in PyTorch (or Numpy or TensorFlow) applies element-wise operations. This is the Hadamard product (denoted by the $\odot$ operator, e.g., $A \odot B$) not matrix multiplication:

Matrix multiplication with a vector:

Matrix multiplication with two matrices:

Matrix Inversion¶

Show that $y = Xw$:

Return to slides here.

Segment 2: Eigendecomposition¶

Affine Transformation via Matrix Application¶

Let's say we have a vector $v$:

Let's plot $v$ using my plot_vectors() function (which is based on Hadrien Jean's plotVectors() function from this notebook, under MIT license).

"Applying" a matrix to a vector (i.e., performing matrix-vector multiplication) can linearly transform the vector, e.g, rotate it or rescale it.

The identity matrix, introduced earlier, is the exception that proves the rule: Applying an identity matrix does not transform the vector:

In contrast, consider this matrix (let's call it $E$) that flips vectors over the $x$-axis:

Or, this matrix, $F$, which flips vectors over the $y$-axis:

Applying a flipping matrix is an example of an affine transformation: a change in geometry that may adjust distances or angles between vectors, but preserves parallelism between them.

In addition to flipping a matrix over an axis (a.k.a., reflection), other common affine transformations include:

• Scaling (changing the length of vectors)
• Shearing (example of this on the Mona Lisa coming up shortly)
• Rotation

(See here for an outstanding blog post on affine transformations in Python, including how to apply them to images as well as vectors.)

A single matrix can apply multiple affine transforms simultaneously (e.g., flip over an axis and rotate 45 degrees). As an example, let's see what happens when we apply this matrix $A$ to the vector $v$:

We can concatenate several vectors together into a matrix (say, $V$), where each column is a separate vector. Then, whatever linear transformations we apply to $V$ will be independently applied to each column (vector):

Now that we can appreciate the linear transformation of vectors by matrices, let's move on to working with eigenvectors and eigenvalues...

Return to slides here.

Eigenvectors and Eigenvalues¶

An eigenvector (eigen is German for "typical"; we could translate eigenvector to "characteristic vector") is a special vector $v$ such that when it is transformed by some matrix (let's say $A$), the product $Av$ has the exact same direction as $v$.

An eigenvalue is a scalar (traditionally represented as $\lambda$) that simply scales the eigenvector $v$ such that the following equation is satisfied:

$Av = \lambda v$

Easiest way to understand this is to work through an example:

Eigenvectors and eigenvalues can be derived algebraically (e.g., with the QR algorithm, which was independently developed in the 1950s by both Vera Kublanovskaya and John Francis), however this is outside scope of the ML Foundations series. We'll cheat with NumPy eig() method, which returns a tuple of:

• a vector of eigenvalues
• a matrix of eigenvectors

The matrix contains as many eigenvectors as there are columns of A:

With a corresponding eigenvalue for each eigenvector:

Let's confirm that $Av = \lambda v$ for the first eigenvector:

And again for the second eigenvector of A:

Using the PyTorch eig() method, we can do exactly the same:

Eigenvectors in >2 Dimensions¶

While plotting gets trickier in higher-dimensional spaces, we can nevertheless find and use eigenvectors with more than two dimensions. Here's a 3D example (there are three dimensions handled over three rows):

Confirm $Xv = \lambda v$ for an example eigenvector:

Exercises:

1. Use PyTorch to confirm $Xv = \lambda v$ for the first eigenvector of $X$.
2. Confirm $Xv = \lambda v$ for the remaining eigenvectors of $X$ (you can use NumPy or PyTorch, whichever you prefer).

Return to slides here.

2x2 Matrix Determinants¶

Return to slides here.

Return to slides here.

Generalizing Determinants¶

Return to slides here.

Determinants & Eigenvalues¶

Return to slides here.

Here's $|\text{det}(X)|$ in NumPy:

Let's use a matrix $B$, which is composed of basis vectors, to explore the impact of applying matrices with varying $|\text{det}(X)|$ values:

Let's start by applying the matrix $N$ to $B$, recalling from earlier that $N$ is singular:

Aha! If any one of a matrix's eigenvalues is zero, then the product of the eigenvalues must be zero and the determinant must also be zero.

Now let's try applying $I_2$ to $B$:

All right, so applying an identity matrix isn't the most exciting operation in the world. Let's now apply this matrix $J$ which is more interesting:

Finally, let's apply the matrix $D$, which scales vectors by doubling along both the $x$ and $y$ axes:

Return to slides here.

Eigendecomposition¶

The eigendecomposition of some matrix $A$ is

$A = V \Lambda V^{-1}$

Where:

• As in examples above, $V$ is the concatenation of all the eigenvectors of $A$
• $\Lambda$ (upper-case $\lambda$) is the diagonal matrix diag($\lambda$). Note that the convention is to arrange the lambda values in descending order; as a result, the first eigenvalue (and its associated eigenvector) may be a primary characteristic of the matrix $A$.

Confirm that $A = V \Lambda V^{-1}$:

Eigendecomposition is not possible with all matrices. And in some cases where it is possible, the eigendecomposition involves complex numbers instead of straightforward real numbers.

In machine learning, however, we are typically working with real symmetric matrices, which can be conveniently and efficiently decomposed into real-only eigenvectors and real-only eigenvalues. If $A$ is a real symmetric matrix then...

$A = Q \Lambda Q^T$

...where $Q$ is analogous to $V$ from the previous equation except that it's special because it's an orthogonal matrix.

Let's confirm $A = Q \Lambda Q^T$:

(As a quick aside, we can demostrate that $Q$ is an orthogonal matrix because $Q^TQ = QQ^T = I$.)

Exercises:

1. Use PyTorch to decompose the matrix $P$ (below) into its components $V$, $\Lambda$, and $V^{-1}$. Confirm that $P = V \Lambda V^{-1}$.
2. Use PyTorch to decompose the symmetric matrix $S$ (below) into its components $Q$, $\Lambda$, and $Q^T$. Confirm that $S = Q \Lambda Q^T$.

Return to slides here.

Segment 3: Matrix Operations for ML¶

Singular Value Decomposition (SVD)¶

As on slides, SVD of matrix $A$ is:

$A = UDV^T$

Where:

• $U$ is an orthogonal $m \times m$ matrix; its columns are the left-singular vectors of $A$.
• $V$ is an orthogonal $n \times n$ matrix; its columns are the right-singular vectors of $A$.
• $D$ is a diagonal $m \times n$ matrix; elements along its diagonal are the singular values of $A$.

$D$ must have the same dimensions as $A$ for $UDV^T$ matrix multiplication to be possible:

SVD and eigendecomposition are closely related to each other:

• Left-singular vectors of $A$ = eigenvectors of $AA^T$.
• Right-singular vectors of $A$ = eigenvectors of $A^TA$.
• Non-zero singular values of $A$ = square roots of eigenvalues of $AA^T$ = square roots of eigenvalues of $A^TA$

Exercise: Using the matrix P from the preceding PyTorch exercises, demonstrate that these three SVD-eigendecomposition equations are true.

Image Compression via SVD¶

The section features code adapted from Frank Cleary's.

Fetch photo of Oboe, a terrier, with the book Deep Learning Illustrated:

Convert image to grayscale so that we don't have to deal with the complexity of multiple color channels:

Convert data into numpy matrix, which doesn't impact image data:

Calculate SVD of the image:

As eigenvalues are arranged in descending order in diag($\lambda$) so too are singular values, by convention, arranged in descending order in $D$ (or, in this code, diag($\sigma$)). Thus, the first left-singular vector of $U$ and first right-singular vector of $V$ may represent the most prominent feature of the image:

Additional singular vectors improve the image quality:

With 64 singular vectors, the image is reconstructed quite well, however the data footprint is much smaller than the original image:

Specifically, the image represented as 64 singular vectors is 3.7% of the size of the original!

Alongside images, we can use singular vectors for dramatic, lossy compression of other types of media files.

Return to slides here.

The Moore-Penrose Pseudoinverse¶

Let's calculate the pseudoinverse $A^+$ of some matrix $A$ using the formula from the slides:

$A^+ = VD^+U^T$

As shown earlier, the NumPy SVD method returns $U$, $d$, and $V^T$:

To create $D^+$, we first invert the non-zero values of $d$:

...and then we would take the tranpose of the resulting matrix.

Because $D$ is a diagonal matrix, this can, however, be done in a single step by inverting $D$:

$D^+$ must have the same dimensions as $A^T$ in order for $VD^+U^T$ matrix multiplication to be possible:

(Recall $D$ must have the same dimensions as $A$ for SVD's $UDV^T$, but for MPP $U$ and $V$ have swapped sides around the diagonal matrix.)

Now we have everything we need to calculate $A^+$ with $VD^+U^T$:

Working out this derivation is helpful for understanding how Moore-Penrose pseudoinverses work, but unsurprisingly NumPy is loaded with an existing method pinv():

Exercise

Use the torch.svd() method to calculate the pseudoinverse of A_p, confirming that your result matches the output of torch.pinverse(A_p):

Return to slides here.

For regression problems, we typically have many more cases ($n$, or rows of $X$) than features to predict (columns of $X$). Let's solve a miniature example of such an overdetermined situation.

We have eight data points ($n$ = 8):

Although it appears there is only one predictor ($x_1$), our model requires a second one (let's call it $x_0$) in order to allow for a $y$-intercept. Without this second variable, the line we fit to the plot would need to pass through the origin (0, 0). The $y$-intercept is constant across all the points so we can set it equal to 1 across the board:

Concatenate $x_0$ and $x_1$ into a matrix $X$:

From the slides, we know that we can calculate the weights $w$ using the equation $w = X^+y$:

The first weight corresponds to the $y$-intercept of the line, which is typically denoted as $b$:

While the second weight corresponds to the slope of the line, which is typically denoted as $m$:

With the weights we can plot the line to confirm it fits the points:

DO NOT return to slides here. Onward!

The Trace Operator¶

Denoted as Tr($A$). Simply the sum of the diagonal elements of a matrix: $$\sum_i A_{i,i}$$

The trace operator has a number of useful properties that come in handy while rearranging linear algebra equations, e.g.:

• Tr($A$) = Tr($A^T$)
• Assuming the matrix shapes line up: Tr($ABC$) = Tr($CAB$) = Tr($BCA$)

In particular, the trace operator can provide a convenient way to calculate a matrix's Frobenius norm: $$||A||_F = \sqrt{\mathrm{Tr}(AA^\mathrm{T})}$$

Exercises

With the matrix A_p provided below:

1. Use the PyTorch trace method to calculate the trace of A_p.
2. Use the PyTorch Frobenius norm method and the trace method to demonstrate that $||A||_F = \sqrt{\mathrm{Tr}(AA^\mathrm{T})}$

Return to slides here.

Principal Component Analysis¶

This PCA example code is adapted from here.

Return to slides here.