Homework 7
Assigned Mon Apr 4, due Thu Apr 14


Matrix Completion, the Nuclear Norm and Semidefinite Programming
  1. The singular value decomposition of a p by q matrix A can be defined in several ways which can lead to confusion. Let's assume that p ≥ q, and, for the moment, that the columns are linearly independent, so the rank is q. Then the definition in the text on p.648 is consistent with the "economy-sized" SVD in Matlab, [U,S,V]=svd(A,0). When the matrix has rank r < q, the definition in the book defines only nonzero singular values, but in the more standard definition, there are q-r zero singular values (and additional columns in U and V). Then, the singular values of A are the square roots of the eigenvalues of the symmetric positive semidefinite q by q matrix ATA. (This is shown on p.648; see also p.646.) Assuming to avoid confusion that the rank is q, define a p+q by p+q symmetric indefinite matrix B with zero diagonal blocks and with A and AT in the off-diagonal block positions. Show that B has 2q nonzero eigenvalues which are plus and minus the singular values of A, and p-q eigenvalues which are zero.

  2. Low rank matrix completion problem is a problem where a p by q matrix, which is assumed to have low rank, needs to be completed from knowledge of a relatively small number of its entries. The most famous example is the Netflix Prize. It is now well known that just as convex L1 optimization problems such as LASSO typically result in sparse solutions, Nuclear Norm convex optimization problems typically result in low rank matrix solutions. The formulation is: minimize the nuclear norm of the matrix (the sum of all q of its singular values) subject to the constraint that the matrix has the correct known entries. As shown in class (see the notes), the nuclear norm can be characterized as the optimal value of a semidefinite program (end of p.4 of the notes). Making use of Question 1 above, given any X, write down a special feasible (W1,W2) satisfying the semidefinite constraint, namely by setting both to the same multiple of the identity matrix: how small can you make this? Also, give an example of a very special X for which this feasible (W1,W2) actually is the optimal solution.

  3. As explained on p.5 of the notes, we can address the matrix completion problem by minimizing the nuclear norm, using the SDP characterization on p.4 with additional constraints imposing values for known entries in X. Using the examples in Xdata.mat, use CVX to minimize the nuclear norm specifying only a relatively small number of the entries, where you generate the row and column indexes for these specified entries randomly. Run successive SDPs with increasing numbers of entries specified until you successfully recover the matrix. For each of the 3 matrices in the data file, approximately how many of the entries do you need to specify to be able to recover the matrix exactly? Average your results over repeated runs with different row and column index pairs. (Use ceil(k*rand)) to generate a random integer between 1 and k.)

  4. For randomly generated square matrices X of order q and fixed rank = 3 do a more systematic investigation of how the number of required specified entries (to recover the matrix) and the time required by CVX (use cputime) varies with q. Plot the results. How big can you make q and still solve one of these SDPs in less than 1 minute?
As a possible final project instead of the final exam, find a paper on the web on a subject relevant to the topics of this course that interests you and that suggests an algorithm suitable for large sparse problems, summarize the paper in your report, implement the algorithm proposed by the paper, test it on an interesting new set of problems, and summarize your experience. Possible topics include Discuss your choice of paper with me before April 19.