Hierarchical Clustering using Randomly Selected Similarities
  The problem of hierarchical clustering items from pairwise similarities is
found across various scientific disciplines, from biology to networking. Often,
applications of clustering techniques are limited by the cost of obtaining
similarities between pairs of items. While prior work has been developed to
reconstruct clustering using a significantly reduced set of pairwise
similarities via adaptive measurements, these techniques are only applicable
when choice of similarities are available to the user. In this paper, we
examine reconstructing hierarchical clustering under similarity observations
at-random. We derive precise bounds which show that a significant fraction of
the hierarchical clustering can be recovered using fewer than all the pairwise
similarities. We find that the correct hierarchical clustering down to a
constant fraction of the total number of items (i.e., clusters sized O(N)) can
be found using only O(N log N) randomly selected pairwise similarities in
expectation.
