Technical Perspective: Reconstructing the Unknown, Balancing Structure and Uncertainty

We have all been there. Late at night, half-sleeping on the couch in front of the TV, opening our eyes every few minutes, catching occasional glimpses of the old movie playing. Waking up, we try to reconstruct and make sense of the plot, reconciling the partial, fragmented pieces of information we have gathered (she stole the money, showers are dangerous, Mother is upstairs) against our preconceived notions (it is a psychological thriller, the blonde actress is the star, twist ending expected). Clearly, there is a tension and synergy between the "partial information" that we have acquired, and the "structured object" that is a traditional movie plot.

Another familiar example of this situation is given by constraint satisfaction puzzles such as Sudoku. Here, the partial information is given by the numbers that are initially revealed, and the structured object is the unknown, final completed pattern satisfying all the constraints. Solving Sudoku, or understanding what the movie was about, is the process of reconciling what we have seen against our priors.

As in these examples, the problem of estimating or reconstructing an unknown structured object from incomplete, partial, noisy measurements is a fundamental one in scientific and technological applications. Many aspects of signal processing, imaging, system identification, and statistical inference can be fruitfully understood from this perspective. For instance, consider understanding a speech signal, reconstructing a real-world image, or identifying a dynamical model of a robotic arm. In all these cases, we have good priors about what the objects should be, but also have empirical information about the concrete instance we are interested in.

The beautiful and foundational work of Candés and Recht on matrix completion addresses an interesting and important situation of this kind, where the unknown object is a low-rank matrix, and the "measurements" correspond to a random subset of its entries. Besides the mathematical simplicity and elegance of the model, what makes this problem formulation remarkable is that it appears quite naturally in a number of important applications, including many tasks related to machine learning and collaborative filtering such as the celebrated Netflix problem.

What often makes these problems challenging is the subtle interaction between a priori information and data. In the existing literature, many different situations have been studied, which can be roughly classified as either probabilistic or set-based assumptions. In particular, the popular "compressed sensing" techniques correspond to sparsity assumptions on the unknown object, and have received much research attention in recent years. The low-rank models studied in this paper naturally generalize many of these ideas to the matrix setting. In combination with sparsity techniques, they have proven to be remarkably flexible and powerful for modeling complex statistical and dynamical phenomena.

There are a number of important technical innovations in this beautiful paper that have created much research excitement and set the stage for numerous follow-up works.

The approach to matrix completion followed in this paper uses convex optimization in an essential way. The nuclear norm of a matrix (the sum of its singular values) is a convex function that is intimately related to its low-rank properties. Replacing a difficult, non-convex rank minimization problem with a better-behaved convex surrogate enables the use of the well-developed machinery of numerical convex optimization to produce candidate solutions. However, the main question remains: how well does this work, if it indeed does? How many entries of the matrix do we need to observe, if we hope to exactly reconstruct the matrix? As the authors show, a surprisingly small number of entries are required to completely recover the unknown matrix with high probability.

There are a number of important technical innovations in this beautiful paper that have created much research excitement and set the stage for numerous follow-up works. In particular, the notion of "incoherence" of the row and column spaces of the matrix has proved fundamental to ensure the observed random samples are "representative enough," and nicely generalizes earlier concepts from the compressed sensing literature. The probabilistic analysis techniques, relying on subtle duality arguments and concentration inequalities, have provided a template for a number of similar recovery results.

Like many great papers, this one not only answers an interesting question but also raises several new ones: What are the most general "structured objects" that we can efficiently recover? What are the fundamental limitations of convex optimization techniques? Is it possible to relax the convexity requirements, while keeping tractability? To what extent can these results be generalized to richer and more powerful models of structure and uncertainty? Whatever the answers to these questions may be, it is clear the path to their solution has been illuminated by this insightful piece of work.