CS168: The Modern Algorithmic Toolbox Lecture #9: The ...

1 CS168: The Modern Algorithmic ToolboxLecture #9: The Singular Value Decomposition (SVD)and Low-Rank matrix ApproximationsTim Roughgarden & Gregory Valiant April 24, 20221 What Are The Missing Entries?Here s a quiz for you: consider the following 5 3 matrix , with 7 entries shown and 8 entriesmissing: 7???8??12 6??221 6? .What are the missing entries?Thismatrix completionproblem seems a bit unfair, no? After all, each of the unknownentries could be anything, and there s no way to know what they are. But what if I told youthe additional hint that the complete matrix has nice structure? This could mean manythings, but for the example let s use an extreme assumption: thatall rows are multiples ofeach , it is possible to recover all of the missing entries! For example, if the third row is amultiple of the second one, then each entry in the latter must be32times the correspondingentry in the former (because of the 12 and 8 in the middle column).

2 Thus we canconclude that the third entry of the second row must be a 4. Similarly, the middle entryof the fourth row is a 4, the last entry of the final row is a 3, and so on. Here s the c 2016 2022, Tim Roughgarden and Gregory Valiant. Not to be sold, published, or distributed withoutthe authors matrix : 72 128 8 442 12 614 4 221 6 3 .(1)The point of the example is that when you know something about the structure of apartially known matrix , then sometimes it s possible to recover all of the lost assumption that all rows are multiples of each other is pretty extreme what would matrix structure mean more generally? One natural and useful definition, explained inthe next section, is that of having low matrix RankYou have probably seen the notion of matrix rank in previous courses, but let s take amoment to page back in the relevant is only one rank-zero matrix of a given size, namely the rank-one matrix is precisely a non-zero matrix of the type assumedin the example above all rows are (not necessarily integral) multiples of each other.

3 Inthe example in (1), all columns are also multiples of each other; this is not an equivalent definition of a rank-1m nmatrix is as theouter productuv>of anm-vectoruand ann-vectorv:1A=uv>= u1v>u2v>..umv> = v1uv2u vnu .Note that each row is a multiple ofv>, and each column is multiple rank-two matrix is just a superposition ( , sum) of two rank-1matrices:A=uv>+wz>= u1v>+w1z>u2v>+w2z>..umv>+wmz> = u w [v>z>].(2)1 Contrast this with theinner( ) productu>v= ni=1uivi, which is only defined for two vectorsof the same dimension and results in a A Y ZT = n m k k n Figure 1: Any matrixAof rankkcan be decomposed into a long and skinny matrix timesa short and long s worth spending some time checking and internalizing the equalities in (2).OK not quite: a rank-2 matrix is one that can be written as the sum of two rank-1matrices and is not itself a rank-0 or rank-1 general definition of matrix rank should now be clear: a matrixAhas rankkif it can be written as the sum ofkrank-one matrices, and cannot be writtenas the sum ofk 1 or fewer rank-one in terms of matrix multiplication , an equivalent definition is thatAcan writtenas, or factored into, the product of a long and skinny (m k) matrixYand a short andlong (k n) matrixZ>(Figure 1).

4 (And thatAcannot be likewise factored into the productofm (k 1) and (k 1) nmatrices.)There are many equivalent definitions of the rank of a matrixA. The following twoconditions are equivalent to each other and to the definition above (any one of the threeconditions implies the other two):1. The largest linearly independent subset of columns ofAhas sizek. That is, allncolumns ofAarise as linear combinations of onlykof The largest linearly independent subset of rows ofAhas sizek. That is, allmrows ofAarise as linear combinations of onlykof is clear that the first condition implies the second and third: ifA=YZ>, then all ofA s columns are linear combinations of thekcolumns ofY, and all ofA s rows are linearcombinations of thekrows ofZ>. See your linear algebra course for proofs of the otherimplications (they are not difficult).

5 33 Low-Rank matrix Approximations: MotivationThe primary goal of this Lecture is to identify the best way to approximate a given matrixAwith a rank-kmatrix, for a target rankk. Such a matrix is called alow-rank might you want to do this? low-rank approximation provides a (lossy) compressed version of thematrix. The original matrixAis described bymnnumbers, while describingYandZ>requires onlyk(m+n) numbers. Whenkis small relative tomandn, replacingthe product ofmandnby their sum is a big win. For example, whenArepresentsan image (with entries = pixel intensities),mandnare typically in the 100s. In otherapplications,mandnmight well be in the tens of thousands or more. With images, amodest value ofk(say 100 or 150) is usually enough to achieve approximations thatlook a lot like the original low-rank approximations are a matrix analog to notions of dimensionality reduc-tion for vectors (Lectures #4 and #7).

6 A noisy version of some ground truth signal that is approximatelylow-rank, then passing to a low-rank approximation of the raw dataAmight throw outlots of noise and little signal, resulting in a matrix that is actually more informativethan the approximations offer a first-cut approach to the matrixcompletion problem introduced in Section 1. (We ll see more advanced approachesin Week 9.) Given a matrixAwith missing entries, the first step is to obtain a fullmatrix Aby filling in the missing entries with default values. Exactly what thesedefault values should be requires trial and error, and the success of the method is oftenhighly dependent on this choice. Natural things to try for default values include: 0,the average of the known entries in the same column, the average of the known entriesin the same row, and the average of the known entries of the matrix .

7 The second stepis to compute the best rank-kapproximation to A. This approach works reasonablywell when the unknown matrix is close to a rank-kmatrix and there are not too manymissing high-level plan for computing a rank-kapproximation of a matrixAis: (i) expressAas a list of its ingredients, ordered by importance; (ii) keep only thekmost importantingredients. The non-trivial step (i) is made easy by the singular value decomposition, ageneral matrix operation discussed in the next 2: The singular value decomposition (SVD). Each singular value inShas an associatedleft singular vector inU, and right singular vector The Singular Value Decomposition (SVD) DefinitionsWe ll start with the formal definitions, and then discuss interpretations, applications, andconnections to concepts in previous lectures. Asingular value decomposition (SVD)of anm nmatrixAexpresses the matrix as the product of three simple matrices:A=USV>,(3) anm morthogonal matrix ; ann northogonal matrix ; anm ndiagonal matrix with nonnegative entries, and with the diagonal entriessorted from high to low (as one goes northwest to southeast).

8 3 Note that in contrast to the decomposition discussed in Lecture #8 (A=QDQ>whenAhas the formX>X), the orthogonal matricesUandVarenotthe same sinceAneednot be square,UandVneed not even have the same columns ofUare called theleft singular vectorsofA(these arem-vectors). Thecolumns ofV(that is, the rows ofV>) are theright singular vectorsofA(these aren-vectors). The entries ofSare thesingular valuesofA. Thus with each singular vector (left2 Recall from last Lecture that a matrix isorthogonalif its columns (or equivalently, its rows) are orthonor-mal vectors, meaning they all have norm 1 and the inner product of any distinct pair of them is we say that a (not necessarily square) matrix is diagonal, we mean what you d think: only theentries of the form (i, i) are allowed to be small numerical examples are tedious to do in detail the orthogonality constraint on singularvectors ensures that most of the numbers are messy.)

9 The easiest way to get a feel for what SVDs look likeis to feed a few small matrices into the SVD subroutine supported by your favorite environment (Matlab,python s numpy library, etc.).5or right) there is an associated singular value. The first or top singular vector refers tothe one associated with the largest singular value, and so on. See Figure better see how the SVD expressesAas a list of its ingredients, check that thefactorizationA=USV>is equivalent to the expressionA=min{m,n} i=1si uiv>i,(4)wheresiis theith singular value andui,viare the corresponding left and right singularvectors. That is, the SVD expressesAas a nonnegative linear combination of min{m, n}rank-1 matrices, with the singular values providing the multipliers and the outer productsof the left and right singular vectors providing the rank-1 matrixAhas a SVD.

10 The proof is not deep, but is better covered in a linearalgebra course than here. Geometrically, thinking of anm nmatrix as a mapping fromRntoRm, this fact is kind of amazing: every matrixA, no matter how weird, is onlyperforming a rotation in the domain ( multiplication byV>), followed by scaling plus addingor deleting dimensions ( multiplication byS) as needed, followed by a rotation in the range( multiplication byU). Along the lines of last Lecture s discussion, the SVD is more orless unique. The singular values of a matrix are unique. When a singular value appearsmultiple times, the subspaces spanned by the corresponding left and right singular vectorsare uniquely defined, but arbitrary orthonormal bases can be chosen for are pretty good algorithms for computing the SVD of a matrix ; details are coveredin any numerical analysis course.