Open access
Date
2022Type
- Journal Article
ETH Bibliography
yes
Altmetrics
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). Show more
Permanent link
https://doi.org/10.3929/ethz-b-000525559Publication status
publishedExternal links
Journal / series
Mathematical Statistics and LearningVolume
Pages / Article No.
Publisher
European Mathematical SocietySubject
Tenor denoising; total variation; Vitali variation; trend filtering; oracle inequalitiesOrganisational unit
03717 - van de Geer, Sara (emeritus) / van de Geer, Sara (emeritus)
Funding
169011 - Topics in High-Dimensional Statistics (SNF)
More
Show all metadata
ETH Bibliography
yes
Altmetrics