In this paper we consider the problem of locating a nonzero entry in a
high-dimensional vector from possibly adaptive linear measurements. We consider
a recursive bisection method which we dub the compressive binary search and
show that it improves on what any nonadaptive method can achieve. We establish
a non-asymptotic bound that applies to all methods, regardless of their
computational complexity. Combined, these results show that the compressive
binary search is within a double logarithmic factor of the optimal performance.

We consider the task of detecting a salient cluster in a sensor network,
i.e., an undirected graph with a random variable attached to each node.
Motivated by recent research in environmental statistics and the drive to
compete with the reigning scan statistic, we explore alternatives based on the
percolative properties of the network. The first method is based on the size of
the largest connected component after removing the nodes in the network whose
value is lower than a given threshold. The second one is the upper level set
scan test introduced by Patil and Taillie (2003).

Let M be a bounded domain of a Euclidian space with smooth boundary. We
relate the Cheeger constant of M and the conductance of a neighborhood graph
defined on a random sample from M. By restricting the minimization defining the
latter over a particular class of subsets, we obtain consistency (after
normalization) as the sample size increases, and show that any minimizing
sequence of subsets has a subsequence converging to a Cheeger set of M.

In the context of clustering, we assume a generative model where each cluster
is the result of sampling points in the neighborhood of an embedded smooth
surface, possibly contaminated with outliers. We consider a prototype for a
higher-order spectral clustering method based on the residual from a local
linear approximation.