figure 2. Recovery of full matrices from their entries. for each (n, m, r) triple, we repeated the following procedure 50 times. A matrix M
of rank r and a subset of m entries were selected at random. Then, we solved the nuclear norm minimization for X subject to Xij = Mij on the
selected entries. We declared M to be recovered if Xopt − M F/ M F < 10− 3. The results are shown for (a) general 50 × 50 matrices (b) 50 × 50
positive definite matrices. The color of each cell reflects the empirical recovery rate (scaled between 0 and 1). White denotes perfect recovery
in all experiments, and black denotes failure for all experiments.
1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1
0.1 0.2 0.3
0.4 0.5 0.6 0.7 0.8 0.9 1
0.1 0.2 0.3
0.4 0.5 0.6 0.7 0.8 0.9 1
dimension of the rank r matrices, dr = r (2n − r), and the number of measurements m.
Note that the axes range from 0 to 1 as a value > 1 on
the x-axis corresponds to an overdetermined linear system where the semidefinite program always succeeds, and
a value > 1 on the y-axis corresponds to when there are an
infinite number of rank r matrices with the provided entries.
The color of each cell in the figures reflects the empirical recovery rate of the 50 runs (scaled between 0 and 1).
Interestingly, the experiments reveal very similar plots for
different n, suggesting that our theoretical upper bounds on
recovery may be rather conservative.
For a second experiment, we generated random
positive semidefinite matrices and tried to recover them from
their entries using the nuclear norm heuristic. As above,
we repeated the same procedure 50 times for each (n,
m, r) triple. We generated M, an n × n positive semidefinite matrix of rank r, by sampling an n × r factor MF
with i.i.d. Gaussian entries and setting M = MFMFT. We
sampled a subset W of m entries uniformly at random.
Then, we solved the nuclear norm minimization problem with an additional constraint that the decision variable be positive definite. Figure 2(b) shows the results
of these experiments for n = 50. The x-axis again corresponds to the fraction of the entries of the matrix that
are revealed to the solver, but, in this case, the number of
measurements is divided by Dn = n(n + 1)/2, the number
of unique entries in a positive-semidefinite matrix, and
the dimension of the rank r matrices is dr = nr − r (r − 1)/2.
The color of each cell is chosen in the same fashion as
in the experiment with full matrices. Interestingly, the
recovery region is much larger for positive semidefinite
matrices, and future work is needed to investigate if the
theoretical scaling is also more favorable in this scenario
of low-rank matrix completion.
These phase transition diagrams reveal a considerably
smaller region of parameter space than the Gaussian models
studied in Recht et al.
30 In the experiments in Recht et al.,
M was generated in the same fashion as above, but, in the
place of sampling entries, we generated m random Gaussian
projections of the data (see the discussion in Section 2. 4).
In these experiments, the recovery regime is far larger than
that in the case of sampling entries, but this is not particu-
larly surprising as each Gaussian observation measures a
contribution from every entry in the matrix M.
2. 3. More general bases
Our main result (Theorem 2. 3) extends to a variety of other
low-rank matrix completion problems beyond the sampling
of entries. Indeed, suppose we have two orthonormal bases
f1, …, fn and g1, …, gn of Rn, and that we are interested in solv-
ing the rank minimization problem
( 2. 7)
The machine learning community’s interest in specialized
algorithms for multiclass and multitask learning provides
a motivating example (see, e.g., Amit et al.
1 and Argyriou
2). In multiclass learning, the goal is to build multiple classifiers with the same training data to distinguish
between more than two categories. For example, in face
recognition, one might want to classify whether an image
patch corresponds to an eye, nose, or mouth. In multitask
learning, we have a large set of data and a variety of different classification tasks, but, for each task, only partial
subsets of the data are relevant. For instance, in activity
recognition, we may have acquired sets of observations of
multiple subjects and want to determine if each observed
person is walking or running. However, a different classifier is desired for each individual, and it is not clear how
having access to the full collection of observations can
improve classification performance. Multitask learning
aims to take advantage of access to the full database to
improve performance on individual tasks. A description
of how to apply our results to the multiclass setting can be