Higher-Order Total Variation Classes on Grids: Minimax Theory and Trend Filtering Methods
Higher-Order Total Variation Classes on Grids: Minimax Theory and Trend Filtering Methods
复制标题
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Veeranjaneyulu Sadhanala;Yu-Xiang Wang;J. Sharpnack;R. Tibshirani
中科院分区：
文献类型：
--
作者：
Veeranjaneyulu Sadhanala;Yu-Xiang Wang;J. Sharpnack;R. Tibshirani
本文研究了由噪声观测值估计d维网格图（边长相等n^{1/d}）上n个结点上的函数值的问题。假设函数是平滑的，但允许在网格中的不同区域表现出不同的平滑度。这种异质性避开了来自非参数统计的平滑性的经典度量，例如保持器平滑性。同时，全变差（TV）平滑类允许异质性，但在另一种意义上是限制性的：只有常数函数才算完全平滑（实现零TV）。为了超越这一点，我们定义了两个新的高阶TV类，基于两种方法编译跨节点的参数的离散导数。我们将这两个新类的保持器类，并推导出其极小极大误差的下界。我们还分析了两个自然相关的趋势过滤方法，当$d=2$，每个被认为是率最优的适当的类。
We consider the problem of estimating the values of a function over $n$ nodes of a $d$-dimensional grid graph (having equal side lengths $n^{1/d}$) from noisy observations. The function is assumed to be smooth, but is allowed to exhibit different amounts of smoothness at different regions in the grid. Such heterogeneity eludes classical measures of smoothness from nonparametric statistics, such as Holder smoothness. Meanwhile, total variation (TV) smoothness classes allow for heterogeneity, but are restrictive in another sense: only constant functions count as perfectly smooth (achieve zero TV). To move past this, we define two new higher-order TV classes, based on two ways of compiling the discrete derivatives of a parameter across the nodes. We relate these two new classes to Holder classes, and derive lower bounds on their minimax errors. We also analyze two naturally associated trend filtering methods; when $d=2$, each is seen to be rate optimal over the appropriate class.