Assigned Mon Apr 4, due Thu Apr 14
Matrix Completion, the Nuclear Norm and Semidefinite Programming
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
- 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
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.
- 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.
- 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.)
- 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?
Discuss your choice of paper with me before April 19.
- LASSO, basis pursuit or related algorithms for data approximation using sparse vectors
- low-rank recovery using nuclear norm minimization, possibly involving singular value thresholding
- general self-dual cone programming or general semidefinite programming problems