  Modeling the distribution of high dimensional data by a latent tree graphical
model is a common approach in multiple scientific domains. A common task is to
infer the underlying tree structure given only observations of the terminal
nodes. Many algorithms for tree recovery are computationally intensive, which
limits their applicability to trees of moderate size. For large trees, a common
approach, termed divide-and-conquer, is to recover the tree structure in two
steps. First, recover the structure separately for multiple randomly selected
subsets of the terminal nodes. Second, merge the resulting subtrees to form a
full tree. Here, we develop Spectral Top-Down Recovery (STDR), a
divide-and-conquer approach for inference of large latent tree models. Unlike
previous methods, STDR's partitioning step is non-random. Instead, it is based
on the Fiedler vector of a suitable Laplacian matrix related to the observed
nodes. We prove that under certain conditions this partitioning is consistent
with the tree structure. This, in turn leads to a significantly simpler merging
procedure of the small subtrees. We prove that STDR is statistically
consistent, and bound the number of samples required to accurately recover the
tree with high probability. Using simulated data from several common tree
models in phylogenetics, we demonstrate that STDR has a significant advantage
in terms of runtime, with improved or similar accuracy.
