an unknown sparse signal (a vector
of length n) from a small number m
of linear measurements of it. Equivalently, given an m x n measurement
matrix A with m << n and the measurement results b = Az, the problem is to figure out the signal z.
This problem has several important
applications, for example in medical imaging. If z can be arbitrary, then
the problem is hopeless: since m < n,
the linear system Ax = b is underde-termined and has an infinite number
of solutions (of which z is only one).
But many real-world signals are (
approximately) k-sparse in a suitable
basis for small k, meaning that (
almost) all of the mass is concentrated
on k coordinates.l The main results in
compressive sensing show that, under appropriate assumptions on A,
the problem can be solved efficiently
even when m is only modestly bigger
than k (and much smaller than n).
15, 20
One way to prove these results is to
formulate a linear programming relaxation of the (NP-hard) problem of
computing the sparsest solution to
Ax = b, and then show this relaxation
is exact.
Planted and Semi-Random Models
Our next genre of models is also inspired by the idea that interesting
instances of a problem should have
“clearly optimal” solutions, but differs from the stability conditions in assuming a generative model—a specific
distribution over inputs. The goal is
to design an algorithm that, with high
probability over the assumed input distribution, computes an optimal solution in polynomial time.
The planted clique problem. In the
maximum clique problem, the input
is an undirected graph G = (V, E), and
the goal is to identify the largest subset
of vertices that are mutually adjacent.
This problem is NP-hard, even to approximate by any reasonable factor.
Is it easy when there is a particularly
prominent clique to be found?
Jerrum27 suggested the following
generative model: There is a fixed set V
of n vertices. First, each possible edge
(u, v) is included independently with
l For example, audio signals are typically approximately sparse in the Fourier basis, images in the wavelet basis.
50% probability. This is also known
as an Erdös-Renyi random graph with
edge density ½. Second, for a parameterk ∈ { 1, 2, . . . , n}, a subset Q ⊆ V
of k vertices is chosen uniformly at
random, and all remaining edges with
both endpoints in Q are added to the
graph (thus making Q a k-clique).
How big does k need to be before
Q becomes visible to a polynomial-time algorithm? The state of the art
is a spectral algorithm of Alon et al.,
3
which recovers the planted clique Q
with high probability provided k is at
least a constant times √n. Recent work
suggests that efficient algorithms cannot recover Q for significantly smaller
values of k.
11
An unsatisfying algorithm. The algorithm of Alon et al.
3 is theoretically
interesting and plausibly useful. But if
we take k to be just a bit bigger, at least
a constant times √n log n , then there is
an uninteresting and useless algorithm that recovers the planted clique
with high probability: return the k vertices with the largest degrees. To see
why this algorithm works, think first
about the sampled Erdös-Renyi random graph, before the clique Q is
planted. The expected degree of each
vertex is ≈ n/2, with standard deviation
≈√n/2. Textbook large deviation in-equalities show that, with high probability, the degree of every vertex is within ≈√lnn standard deviations of its
expectation (Figure 4). Planting a
clique Q of size a√n log n, for a sufficiently large constant a, then boosts
the degrees of all of the clique vertices
enough that they catapult past the degrees of all of the non-clique vertices.
What went wrong? The same thing
that often goes wrong with pure av-
erage-case analysis—the solution is
brittle and overly tailored to a specific
distributional assumption. How can
we change the input model to encour-
age the design of algorithms with more
robust guarantees? Can we find a sweet
spot between average-case and worst-
case analysis?
Semi-random models. Blum and
Spencer13 proposed studying
semi-random models, where nature and
an adversary collaborate to produce
an input. In many such models, nature first samples an input from a
specific distribution (like the probabilistic planted clique model noted
here), which is then modified by the
adversary before being presented as
an input to an algorithm. It is important to restrict the adversary’s power,
so that it cannot simply throw out
nature’s starting point and replace it
with a worst-case instance. Feige and
Killian24 suggested studying monotone
adversaries, which can only modify
the input by making the optimal solution “more obviously optimal.” For
example, in the semi-random version of the planted clique problem, a
monotone adversary is only allowed
to remove edges that are not in the
planted clique Q—it cannot remove
edges from Q or add edges outside Q.
Semi-random models with a monotone adversary may initially seem no
harder than the planted models that
they generalize. But let’s return to the
planted clique model with k = Ω(√n log n
), where the “top-k degrees” algorithm
succeeds with high probability when
there is no adversary. A monotone adversary can easily foil this algorithm in
the semi-random planted clique model, by removing edges between clique
Figure 4. Degree distribution of an Erdo″s–Rényi graph with edge density ½, before planting
the k-clique Q. If k = Ω (√ (n lg n ), then the planted clique will consist of the k vertices with
the highest degrees.
degrees