a logo for the course

Matrix Computations

David Gleich

Purdue University

Fall 2018

Course number CS-51500

Tuesday and Thursday, 3:00-4:15pm

Location Forney G124


Homework 7

Homework 7

Please answer the following questions in complete sentences in a clearly prepared manuscript and submit the solution by the due date on Blackboard (around Sunday, October 28th, 2018.)

Remember that this is a graduate class. There may be elements of the problem statements that require you to fill in appropriate assumptions. You are also responsible for determining what evidence to include. An answer alone is rarely sufficient, but neither is an overly verbose description required. Use your judgement to focus your discussion on the most interesting pieces. The answer to "should I include 'something' in my solution?" will almost always be: Yes, if you think it helps support your answer.

Problem 0: Homework checklist

Problem 1: Condition numbers

Consider the following computations. Discuss if they are well-conditioned or ill-conditioned. If the answer depends on the types of input, please provide some rough guidance. (e.g. for subtraction, it's ill-conditioned if the numbers are close by)

  1. The mean of a dataset .

  2. The sample variance .

  3. A matrix vector product .

  4. Evaluating a neural network layer where the elements are and the soft-plus function .

Problem 2: Experience with the SVD

Produce the analytic SVDs of the following matrices. (That is, no numerical approximations, but feel free to let Julia 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 3: Eigenfaces

For this problem, we'll be using the same face data from Yale that we used on Homework 6. This is on our website:

* <http://www.cs.purdue.edu/homes/dgleich/cs515-2018/homeworks/Yale_64.csv>
* <http://www.cs.purdue.edu/homes/dgleich/cs515-2018/homeworks/Yale_64_ids.csv>

And this can be read into Julia via

    A = readdlm("Yale_64.csv",',')
    labels = readdlm("Yale_64_ids.csv")

More about the data is here: http://www.cad.zju.edu.cn/home/dengcai/Data/FaceData.html This was converted from the Matlab file into the CSV files.

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

  2. Describe and implement a matrix operation to center a matrix of all faces.

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

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

  5. 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.

Problem 4: Matrix Analysis

Suppose that is a symmetric positive definite matrix with on the diagonal. Address -- through whatever means you want, but make sure you document anything you look at or work through -- the following question. Does the convergence rate of Gauss-Seidel change with the condition number? If so, how?