Reconstructing the unknown,
by Pablo A. Parrilo
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” corre-
spond 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, in-
cluding many tasks related to machine
learning and collaborative filtering
such as the celebrated Netflix problem.
There are a number
of important technical
innovations in this
beautiful paper that
have created much
and set the stage
statistical and dynamical phenomena.
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 inequali-ties, 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 tractabil-ity? 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.
Pablo A. Parrilo ( firstname.lastname@example.org) is a professor of
electrical engineering and computer science at the
Massachusetts Institute of technology, Cambridge, Ma.
© 2012 aCM 0001-0782/12/06 $10.00