  We extend the notion of trend filtering to tensors by considering the $k^{\rm
th}$-order Vitali variation, a discretized version of the integral of the
absolute value of the $k^{\rm th}$-order total derivative. We prove adaptive
$\ell^0$-rates and not-so-slow $\ell^1$-rates for tensor denoising with trend
filtering.
  For $k=\{1,2,3,4\}$ we prove that the $d$-dimensional margin of a
$d$-dimensional tensor can be estimated at the $\ell^0$-rate $n^{-1}$, up to
logarithmic terms, if the underlying tensor is a product of $(k-1)^{\rm
th}$-order polynomials on a constant number of hyperrectangles. For general $k$
we prove the $\ell^1$-rate of estimation $n^{- \frac{H(d)+2k-1}{2H(d)+2k-1}}$,
up to logarithmic terms, where $H(d)$ is the $d^{\rm th}$ harmonic number.
  Thanks to an ANOVA-type of decomposition we can apply these results to the
lower dimensional margins of the tensor to prove bounds for denoising the whole
tensor. Our tools are interpolating tensors to bound the effective sparsity for
$\ell^0$-rates, mesh grids for $\ell^1$-rates and, in the background, the
projection arguments by Dalalyan et al.
