Smoothed Analysis of Discrete Tensor Decomposition and Assemblies of
We analyze linear independence of rank one tensors produced by tensor powers of
randomly perturbed vectors. This enables efficient decomposition of sums of
high-order tensors. Our analysis builds upon Bhaskara et al.  but allows
for a wider range of perturbation models, including discrete ones. We give an
application to recovering assemblies of neurons. Assemblies are large sets of
neurons representing specific memories or concepts. The size of the
intersection of two assemblies has been shown in experiments to represent the
extent to which these memories co-occur or these concepts are related; the
phenomenon is called association of assemblies. This suggests that an
animal's memory is a complex web of associations, and poses the problem of
recovering this representation from cognitive data. Motivated by this
problem, we study the following more general question: Can we reconstruct
the Venn diagram of a family of sets, given the sizes of their l-wise
intersections? We show that as long as the family of sets is randomly
perturbed, it is enough for the number of measurements to be polynomially
larger than the number of nonempty regions of the Venn diagram to fully
reconstruct the diagram.
Reference: N. Ananri, C. Daskalakis, W. Maass, C. H. Papadimitriou,
A. Saberi, and S. Vempala.
Smoothed analysis of discrete tensor decomposition and assemblies of neurons.
32nd Conference on Neural Information Processing Systems (NIPS 2018),
Montreal, Canada, 2018.