IEEE Signal Processing - July 2018 - 29

Concluding remarks
Low-rank matrices represent an important class of signals
with low-dimensional intrinsic structures. In this article, we
have presented some recent developments on low-rank matrix
estimation, focusing on the setting with incomplete measurements and additional structural constraints. We have particularly emphasized the remarkable modeling power of low-rank
matrices, which are useful in a range of problems much wider
than the name may suggest, including those where the presence of low-rank structures are not obvious at all. In terms of
algorithms and theory, attention is paid to the integration of
statistical and computational considerations: fast algorithms
have been developed that are applicable to large-scale problems and, at the same time, enjoy provable performance guarantees under mild assumptions. As we have seen, such recent
progress is made possible by combining techniques from
diverse fields; in particular, convex and nonconvex optimization, as well as probabilistic analysis, play a key role.
We conclude by mentioning a few topics and future directions that are not covered in this article. We have focused on the
matrix sensing and completion problems with linear measurements. There are many other low-rank estimation problems that
are amenable to convex and nonconvex optimization-based algorithms and enjoy similar geometric properties and performance
guarantees. A partial list of such problems includes phase retrieval [57], blind deconvolution [56], robust PCA [70], dictionary
learning [73], lifting for mixture problems [92], low-rank phase

0.3
0.25
NMAE

Burer-Monteiro factorization formulation as described in the
section "Provable and Fast Low-Rank Matrix Estimation via
Nonconvex Factorization." We set the maximum number of
iterations to 4,000 and the convergence tolerance to 5 # 10 -6 .
Similarly as before, BFGD typically terminates early in our
experiment. For the step size, we use the default setting of the
original implementation. The NMAEs of BFGD for the training
data and test data are shown in Figure 7. The minimum NMAE
for test data is 0.1895, achieved by setting the rank to two.
We make several observations from the aforementioned
experiment results. First, we see that, consistently across the
three algorithms, the training error generally goes down as the
rank becomes larger, whereas the test error exhibits a U-shape
behavior, decreasing first and then increasing later. This
phenomenon is in accordance with the bias-variance tradeoff
principle described in the section "The Ubiquity of Low-Rank
Models" and, in particular, shows that using a low-rank model
is helpful in reducing the variance and prevents overfitting.
Second, all three algorithms achieve a minimum test NMAE
around 0.19, using a rank no more than five. The small optimal
values for the rank are likely due to the highly noisy nature of
the MovieLens data set, for which suppressing variance is crucial to good performance on the test set. Finally, while the estimation/prediction performance of these algorithms is similar,
their computational costs, such as running times and memory
usage, vary. These costs depend heavily on the specific implementations and termination criteria used, so we do not provide
a detailed comparison here.

0.2

NMAE for Training Data
NMAE for Test Data

0.15
0.1
0.05

Rank

Figure 7. The performance of BFGD [91] on MovieLens 100 K data set. The
NMAE for training data and test data via BFGD with respect to the rank are given.

retrieval [93], community detection [89], and synchronization
problems [69]. More broadly, applications of low-rank matrix
recovery go well beyond the setting of linear measurements
and least-squares objectives. Prime examples include low-rank
matrix recovery with quantized, categorical, and non-Gaussian
data [94], [95], and ranking from comparison-based observations [96]. These problems involve more general objective functions (such as the log-likelihood) and constraints that depend on
the specific observation schemes and noise structures. Another
promising line of research aims at exploiting hidden low-rank
structures in settings where the problem on the surface has
nothing to do with low-rank matrices, yet such structures reveal
themselves under suitable transformation and approximation.
Problems of this type include latent variable models with certain
smoothness/monotonicity properties [23].
Another topic of much interest is how to select the model
rank automatically and robustly and how to quantify the effect
of model mismatch. These are important issues even in standard matrix sensing and completion; we have not discussed
these issues in detail in this survey article. Finally, we have
omitted many other low-rank recovery algorithms that are not
directly based on (continuous) optimization, including various
spectral methods, kernel and nearest-neighbor type methods,
and algorithms with a more combinatorial flavor. Some of
these algorithms are particularly useful in problems involving
complicated discrete and time-evolving structures and active/
adaptive sampling procedures. All of these topics are the subject of active research with tremendous potential.

Acknowledgments
We thank Yuanxin Li for preparing the numerical experiments in this article. The work of Yudong Chen is supported
in part by the National Science Foundation (NSF) under CRII
award 1657420 and grant CCF-1704828. The work of Yuejie
Chi is supported in part by the Air Force Office of Scientific
Research under grant FA9550-15-1-0205, by the Office of
Naval Research under grant N00014-18-1-2142, and by NSF
under grants CAREER ECCS-1818571 and CCF-1806154.

IEEE Signal Processing Magazine

July 2018

Table of Contents for the Digital Edition of IEEE Signal Processing - July 2018