Tensor denoising with trend filtering

Abstract

We extend the notion of trend filtering to tensors by considering the kth-order Vitali variation – a discretized version of the integral of the absolute value of the kth-order total derivative. We prove adaptive ℓ0-rates and not-so-slow ℓ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 ℓ0-rate n−1, up to logarithmic terms, if the underlying tensor is a product of (k−1)th-order polynomials on a constant number of hyperrectangles. For general k we prove the ℓ1-rate of estimation n−H(d)+2k−12H(d)+2k−1, up to logarithmic terms, where H(d) is the dth 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 ℓ0-rates, mesh grids for ℓ1-rates and, in the background, the projection arguments by Dalalyan, Hebiri, and Lederer (2017).