Singular Value Decomposition

​

Lior Pachter

California Institute of Technology

1

Lecture 5

Caltech Bi/BE/CS183

Spring 2023

These slides are distributed under the CC BY 4.0 license

M = UΣV^T

Recall: Singular Value Decomposition (Lecture 1)

2

This is the most important matrix decomposition for computational biology / data science / statistics !

Preliminaries

• In order to simplify matters, we will restrict our discussion to real matrices, i.e. matrices with real-valued entries. SVD is more general: it works for complex matrices, but our simplification will facilitate an exposition of the main ideas as utilized in computational biology.
• We will state results without proof. This will be due to time constraints; the needed linear algebra is elementary and is typically taught in an advanced undergraduate linear algebra class, but a complete presentation with all the requisite proofs is beyond the scope of the class.
• The expository article (Martin and Porter, 2012) provides a useful overview of the SVD and an introduction to its many varied applications.

3

Recall: a matrix is code for a (linear) function

4

How a matrix describes (is code for) a function

5

=

How a matrix describes (is code for) a function

6

=

How a matrix describes (is code for) a function

7

=

M

(

)

x

The code depends on the choice of basis

8

=

M

(

)

x

A basis consists of a set of independent vectors that span a vector space.

The code depends on the choice of basis

9

A basis consists of a set of independent vectors that span a vector space.

Bases of a vector space

• Vector spaces may have many bases, however all bases of a vector space have the same number of elements.
• The number of elements in a basis of a vector space is called the dimension of the vector space.
• The standard basis for Rⁿ consists of the n vectors �(1,0,0…,0), (0,1,0,0,...,0), …, (0,0,...,1).����
• An orthogonal basis consists of vectors that are mutually orthogonal. The standard basis is orthogonal, and additionally orthonormal, i.e. all vectors in the basis have norm 1.

10

A simple matrix (linear transformation)

• The identity matrix

11

Another simple matrix (linear transformation)

• The diagonal matrix = scaling transformation

12

What is singular value decomposition about?

• Linear transformations, and their corresponding matrices (which are rectangular tables filled with numbers), are seemingly complicated and arbitrary.
• The singular value decomposition (SVD) says that every matrix is essentially diagonal, i.e. “nice”, provided the “right” bases are used for the domain and range spaces.
• By finding the “right” bases, the SVD provides fundamental insights into linear transformations and their accompanying matrix representations.

13

Singular value decomposition

• Input: an m x n matrix�
• Output: a set of numbers called singular values and two collections of vectors: a set of right singular vectors and another set of left singular vectors.

14

The meaning of singular values

• As a linear map, an m x n matrix M can be thought of as mapping a vector x from Rⁿ to R^m.
• A unit sphere in Rⁿ is mapped to an ellipsoid in R^m:����
• The non-zero singular values of M are the lengths of the semi-axes of the ellipsoid.

15

Measuring directions of distortion

• The maximal singular value can therefore be understood to be the size of the vector that points in the direction in which the linear transformation corresponding to M has the largest effect.
• Formally, the maximal singular value, which is usually denoted as σ₁ can be understood to be���
• Similarly, the smallest non-zero singular value is the size of the smallest semi-axis of the ellipsoid that is the image of the unit sphere under M.

16

The meaning of singular vectors

• There are two sets of singular vectors, called left and right singular vectors. They correspond, respectively, to the first min(m,n) columns in the matrices U and V in the singular value decomposition of M, ie. in M = UΣV^T.
• The ith singular vectors satisfy the relationship Mv = σ_iu.
• Thus, the left singular vectors describe the directions of the semi-axes corresponding to the image of the unit sphere under the linear transformation corresponding to M.
• The singular vector corresponding to the largest singular value point in the direction in which the linear transformation has the largest effect.
• In the example, the first left singular vector, scaled by σ₁, is the dark red vector. The light red vector is the corresponding right singular vector.

17

Example from Holbrook, 2019

Higher dimensions

• Examples illustrating the geometry of SVD are usually in two dimensions, but the geometric intuition is valid in higher dimensions. The following shows an example in three dimensions based on the 3 x 3 matrix:

18

Example from Holbrook, 2019

A source of confusion: eigenvectors (or selfie vectors)

• An eigenvector is a vector associated to a linear transformation, or equivalently to a matrix that represents the linear transformation.
• Eigenvectors of linear transformations describe directions for which the transformations only shrink or stretch the vectors.
• In the example, the light blue and red vectors, which are mapped to the dark blue and dark red vectors by M, are the eigenvectors. Their direction remains the same after transformation (up to sign); only the lengths change.

19

Example from Holbrook, 2019

Another example of selfie vectors and selfie values

• In the example, the light blue and red vectors, which are mapped to the dark blue and dark red vectors by M. The directions of the red and blue vectors remain the same after transformation (up to sign); only the lengths change.
• One selfie value is -2: the light blue selfie vector (-1,1) is multiplied by -2 to scale to (2,-2). The other selfie value is 2: the light red selfie vector (1,1) is multiplied by 2 to scale to (2,2).

20

Example from Holbrook, 2019

Don’t confuse (left and right) singular vectors with eigenvectors

21

right singular vector

scaled left singular vector

eigenvector

The SVD theorem

22

The singular vectors are mutually orthogonal

• From the theorem statement we learn that the left singular vectors are orthonormal, which means that they are mutually orthogonal, and also have norm 1. The same is true for the right singular vectors.
• This is evident in the example, where the light (red and blue) vectors, corresponding to the right singular vectors, are perpendicular and touching the unit circle.

23

Example from Holbrook, 2019

Relevance of orthonormality of U and V

• Recall that two vectors x,y are orthogonal if their dot product x·y = 0. The norm of a vector is the square of its dot product with itself.
• If U is an orthonormal matrix, then it follows that U^TU = I. This is because a row of U^T multiplied by a column of U is zero (if the row and column numbers are different, because the vectors in U are orthogonal), or one (if they are the same, because the vectors in U have norm 1).
• In other words, U^T is the inverse of U, and similarly V^T is the inverse of V.

24

Relevance of orthonormality of U and V

• If the SVD of M is given by M = UΣV^T then note that M^T = VΣU^T, and therefore it follows that��M^TM = (VΣU^T)(UΣV^T)� = VΣ(U^TU)ΣV^T� = VΣ·ΣV^T� = VΣ²V^T.
• Recall that V^T is the inverse of V, therefore we have established a decomposition of M^TM as M^TM = VΣ²V^-1.

25

Eigendecomposition

• An n x n matrix A is said to be diagonalizable if A can be written as�A = PDP^-1 for some diagonal matrix D. When a matrix is diagonalizable, in this form, multiplying both sides on the right by P^-1 we get that �AP = PD.
• If the entries of D are λ₁,λ₂,..λ_n, and matrix P has columns p₁,p₂,...p_n, then AP = PD translates to the statement that Ap_i = λ_i p_i , i.e., the entries of D are eigenvalues of A, and the columns of P are the corresponding eigenvectors. For this reason the decomposition of a diagonalizable matrix into A = PDP^-1 is called eigendecomposition.

26

From SVD to eigendecomposition

• Recall that the SVD of M given by M = UΣV^T yields a decomposition of M^TM as M^TM = VΣ²V^-1. In other words, VΣ²V^-1 is the eigendecomposition of M^TM.
• Therefore, the singular values of M are the square root of the eigenvalues of M^TM. This can be taken as the definition of singular values.
• Furthemore, this provides an approach, albeit not necessarily the best, to computing the SVD of a matrix M: first compute M^TM and then compute the eigenvalues to find the singular values. Find the eigenvectors of M^TM to get V. Find the eigenvectors of MM^T to get U.

27

From eigendecomposition to SVD

• Singular value decomposition can be viewed as a generalization of eigendecomposition in the following sense:
• A square matrix M is called normal if M^TM = MM^T.
• The (sorted) singular values of the matrix M are equal to the absolute value of the (sorted) eigenvalues of M.
• In other words, for normal matrices, singular value decomposition is essentially eigendecomposition.
• While eigendecomposition only works for (certain kinds) of square matrices, singular value decomposition provides a decomposition for matrices that are rectangular.

28

Recap: the (linear algebra) magic of SVD

• With all the formulas and linear algebra associated with SVD, it’s easy to lose sight of the magic of the decomposition…
• Among all the orthonormal bases in the domain space, the SVD finds one (light blue and red) that maps into another orthonormal basis, this time in the domain space (directions of dark red and blue arrows).
• That this can be done for any linear transformation is a sort of… magic.

29

Example from Holbrook, 2019

Summary

Singular vectors: the right singular vectors are orthonormal vectors whose image under the linear transformation corresponding to a matrix yields the directions (orthonormal left singular vectors) of the semi-axes of the ellipsoid formed as the image of the unit sphere.

Singular values: The sizes of the semi-axes of the ellipsoid which is the image nuder the linear transformation corresponding to a matrix.

SVD by eigendecomposition: the SVD of a matrix M can be computed by eigendecomposition of the matrix M^TM. This observation is the first step towards the proof that the SVD exists.

SVD as a generalization of eigendecomposition: In some sense, SVD generalizes eigendecomposition. It can be thought of as saying that “every matrix is diagonal, provided one uses the proper bases for the domain and range spaces”- (Trefethen & Bau III, 1997).

30

^T

^T

Using SVD on matrices derived from measurements

• An important feature of SVD is that singular values are robust to perturbations. Formally, if à is a perturbation of a matrix A such that �à = A + Δ, where the singular values of A are �and the singular values of A are , then
• (Weyl, 1912): , for all i = 1,2,..., n.�
• (Mirsky, 1960): �
• These results show that singular values are stable under perturbation. Singular vectors are sensitive to perturbation, but there are stability results for the subspaces they span. This makes SVD suitable for application to noisy data.

31

Algorithms for singular value decomposition

• One of the reasons SVD can be useful in applications is that the SVD of matrices can be computed efficiently. A landmark advance in computation of SVDs was (Golub and Reinsch, 1970), which remains in use today. There is a large body of work since then on methods for eigendecomposition and SVD, which is part of the field of numerical linear algebra. A detailed discussion of different algorithms and their pros and cons is beyond the scope of this class.
• Some things to keep in mind:
• There are efficient algorithms for computing singular values without computing singular vectors.
• The fastest SVD algorithms do not rely on eigendecomposition of the product of the matrix and its transpose.

32

Applications of singular value decomposition

• Singular value decomposition has numerous applications in mathematics, science and engineering. These include:
• Determining the rank of a matrix
• Computing the pseudoinverse of a matrix
• Low rank matrix approximation
• Imputation
• Principal component analysis
• Clustering
• Visualization of high-dimensional data in two dimensions
• Removal of noise from data
• …

33

Low-rank approximation

• Note that the rank of a matrix is given by the number of non-zero singular values. In other words, SVD can be used to compute rank.
• Moreover, if M has rank r, the SVD M = UΣV^T can be written as ��M = σ₁u₁v₁^T + σ₂u₂v₂^T+ … + σ_ru_rv_r^T . ��Here u_i, v_i are the ith columns of U and V respectively.�
• This formulation describes M as the sum of rank 1 matrices. The truncated sum, using only the first few terms, provides a good low rank approximation of the matrix M.

34

Example

35

Source: Wikipedia

• The matrix M is rectangular.�
• There are three non-zero singular values.�
• The rank of M is 3; this is clear by inspection.�
• Note that UU^T = I and VV^T = I (easy to check).

The Eckart-Young theorem

• Let M = UΣV^T and set��The matrix M_k is a good low-rank matrix approximation of M. Specifically, ��
• This theorem makes precise the intuition that the top singular values, which measure the sizes of the largest of the semi-axes of the ellipsoid resulting from mapping of a sphere by the linear transformation corresponding to a matrix, capture “most” of the transformation.�
• The theorem was first mentioned in (Eckart and Young, 1936).

36

Low rank approximation for gene expression analysis

• The SVD was first applied to gene expression analysis on data produced with microarrays �(Rachaudhuri, Stuart and Altman, 2000, Alter et al., 2000).

37

Orly Alter

Low rank approximation for imputation

• Low rank approximations of matrices can be used to impute missing values. There are several ways that have been explored for doing this. One approach that has been studied for single-cell RNA-seq in (Linderman et al., 2018) is the following:
• Perform SVD of the gene expression matrix and obtain a low rank approximation. Matrix entries that were initially zero are now non-zero, distributed (approximately) symmetrically around zero. Assume that this represents the distribution, after low rank approximation, of true zeroes.
• For each row (which corresponds to a gene), set to zero all the gene x cell entries with absolute value smaller than than the most negative element in the row.
• Retain the remaining entries in the low-rank approximation.

38

Adaptively-thresholded low-rank approximation (ALRA)

39

(Linderman et al., 2018)

Factorization based imputation of expression in single-cell transcriptomic analysis

40

Mehrabad et al., 2021

SVD pre-processing in a workflow to identify doublets

41

Wolock et al., 2019

see Lecture 2

SVD and decomposition of the covariance matrix.

• Recall (Lecture 4) that the covariance matrix for a data matrix M with n observations (i.e. n cells) is a matrix C given by ��
• If the matrix M is centered, i.e. for each gene the expression averaged over cells is zero, then this reduces to �
• Recall that SVD of M given by M = UΣV^T yields a decomposition of M^TM as M^TM = VΣ²V^-1, i.e., eigendecomposition of the covariance matrix C can be performed by SVD of M.

42

Eigendecomposition of the covariance matrix

• The eigendecomposition of the sample covariance matrix constructed from a data matrix is called principal components analysis (PCA).�Note that PCA does not abbreviate principle component analysis.
• PCA is a method for dimensionality reduction. It has many useful properties that make it a widely used method in single-cell RNA-seq analysis; it is almost ubiquitous and is one of the first steps performed in almost all analyses.
• Will we discuss the properties of PCA, and why eigendecomposition of the covariance matrix is useful in Lecture 6.

43

SVD applications

SVD stability: the singular values of matrices are stable and do not change much if matrix entries are perturbed by small amounts.

​

SVD algorithms: SVDs of matrices can be computed by a variety of numerical linear algebra algorithms. While SVDs of very large matrices remain challenging to compute, SVD is tractable for typical single-cell RNA-seq datasets.

Low-rank approximation: SVD can be used to produce best (Eckart-Young theorem) low-rank approximations of matrices. SVD, by virtue of providing good low-rank approximations of matrices, can also be used for imputation.

Dimension reduction: SVD can be used for PCA to reduce dimension of high-dimensional datasets. This has numerous applications ranging from noise filtering to visualization.

44

Additional References

• An intuitive proof of the SVD theorem.�
• Gilbert Strang’s 18.06 lecture on the SVD.�
• PCA and the code for facial identity in the primate brain.�
• Computing the SVD in Python (Google Colab notebook).�
• Numerical Linear Algebra by Trefethen and Bau, III.�
• Computing the SVD in R (RPubs).

45