a logo for the course

Matrix Computations

David Gleich

Purdue University

Fall 2017

Course number CS-51500

Tuesday and Thursday, 10:30-11:45am

Location Forney B124


Homework

Homework 3

Please answer the following questions in complete sentences in a typed, clearly prepared manuscript and submit the solution by the due date on Blackboard (Monday, September 18th, 2017, about 4am)

Problem 0: Homework checklist

Problem 1: Compute it!

Produce the analytic SVDs of the following matrices. (That is, no numerical approximations, but feel free to let Matlab give you a good guess!). It's important to think about these questions because I may give similar questions on a midterm or final and you'll be expected to remember these. It's also handy to think about how to construct these, even though we haven't seen any algorithms yet. You should be able to work them all out directly from the definition.

Problem 2: Fun with the SVD.

The following quesitons are some warm up questions about the theory of the SVD. Each of these is designed to teach you something about the SVD. So there is usually a nice fact that I want you to know.

  1. Find a matrix with two different SVD factorizations.
    What is the same in both cases?

  2. What is the SVD of for arbitrary vectors , ?

  3. Show that .

  4. If is an orthogonal matrix, what is it's SVD? In particular, what are the singular values?

Problem 3: The celebrated Eckart-Young theorem

One of the early communities to use the SVD for data analyais were the psychometricians. They were trying to understand how to analyze matrices of test scores!

If individuals are each subjected to tests, it is a fundamental postulate of factor theory that the resulting score matrix a can be adequately approximated by another matrix whose rank is less than the smaller of or .
Closely associated to this postulate is the purely mathematical problem of finding that matrix of rank which most closely approximates a given matrix of higher rank . It will be shown that if the least-squares criterion of approximation be adopted, this problem has a general solution which is relatively simple in a theoretical sense, though the amount of numerical work involved in applications may be prohibitive. Certain conclusions can be drawn from the theoretical solution which may be of importance in practical work. -- Eckart and Young

In this question, we will work through a proof of the Eckart-Young theorem. You are welcome to go look at the paper for the original proof. However, I think the more modern steps below will be easier to follow. Note that you can also find this same proof in many references. Again, you are free to look at these and even copy them. However, I will ask that you explain everything! If you find yourself reading these and thinking, "hmm... why is that true...?" Those are exactly the steps we are expecting you to explain.

The Eckart-Young theorem states:

Let , without loss of generality, assume . Let be the SVD. Let , , and . Define Then: for any matrix of rank .

It's helpful to translate this into real language. Suppose I give you a matrix , and ask for the closest matrix to but with rank instead of rank instead. Eckart-Young tells us that we can construct such as matrix from the SVD.

In this problem, we'll use the matrix 2-norm.

  1. Explain why we don't lose any generality with the assumption .

  2. Warmup Suppose that is a diagonal matrix with non-negative entries. What is the best diagonal rank approximation to ? (Yes, you have to prove it. No, you cannot assume the Eckart-Young theorem is true!)

  3. Warmup Show that .

  4. Warmup Show that where is the rank of . Why does this mean we can assume that without losing any further generality?

  5. Show that .

  6. We'll proceed by contradiction now. Suppose that a rank matrix exists with . Briefly justify why:

  7. Using the last result, we can choose to be anything we want. Note that is rank . This means it must have a null-space of dimension . Show that, for any vector in the null-space of that:

  8. Now we have a subspace of such that is bounded above. We'll now show that there's another subspace where it's bounded below! Let . Show that . (Hint, note that is an orthogonal basis for that span.)

  9. What's the dimension of the space where is bounded above? What's the dimension of the space where is bounded below? Why does this lead to a contradiction?

  10. Give yourself a pat on the back!

Problem 4: Eigendigits

Download the matrix 'usps_all.mat' from http://www.cs.nyu.edu/~roweis/data/usps_all.mat Recall, you can use

matread(download(
      "http://www.cs.nyu.edu/~roweis/data/usps_all.mat"))

as we did in the Cosine similarity file

  1. Describe how the data is stored. Use the heatmap or colorview function in Julia to draw a picture of each individual digit. (Or something else in another language to draw a sample picture of each digit.

    (If you are having trouble with this one, post on Piazza and we will try and be helpful. We just want you to be able to work with the data and we will guide you through what's done here...)

  2. Describe a scheme to center the vector associated with each digit picture. That is, if is the vector associated with a digit, then explain how to add a scalar to such that and the sum of is zero.

  3. Describe and implement a matrix operation to center a matrix of all digits. (Hint, you will likely have to reshape the data-cube that the data comes in...)

  4. Compute the singular value decomposition of the matrix of centered images as a "pixels centered digits" matrix.
    What is the largest singular value?

  5. Plot the leading singular vector as a pixel image. What do you see?

  6. Repeat the same analysis for just for the pictures associated with each digit. That is, you should compute the dominant eigenvalue for 10 matrices, one associated with each digit, as well as producing the picture of the leading singular vector for those 10 matrices. Report any key differences from the picture in number 5.

  7. If you're curious about this, this website has more info http://en.wikipedia.org/wiki/Eigenface. (Except we are doing eigendigits!) You should also look at the subdominant eigenvectors as well.