  While nonparametric density estimators often perform well on low dimensional
data, their performance can suffer when applied to higher dimensional data,
owing presumably to the curse of dimensionality. One technique for avoiding
this is to assume no dependence between features and that the data are sampled
from a separable density. This allows one to estimate each marginal
distribution independently thereby avoiding the slow rates associated with
estimating the full joint density. This is a strategy employed in naive Bayes
models and is analogous to estimating a rank-one tensor. In this paper we
investigate whether these improvements can be extended to other simplified
dependence assumptions which we model via nonnegative tensor decompositions. In
our central theoretical results we prove that restricting estimation to
low-rank nonnegative PARAFAC or Tucker decompositions removes the
dimensionality exponent on bin width rates for multidimensional histograms.
These results are validated experimentally with high statistical significance
via direct application of existing nonnegative tensor factorization to
histogram estimators.
