论文标题
voronoigram：从分散数据中估算有界变化函数的最小值估计
The Voronoigram: Minimax Estimation of Bounded Variation Functions From Scattered Data
论文作者
论文摘要
我们考虑了估计多元函数$ f_0 $ formed变化（BV）的问题，从嘈杂的观察值$ y_i = f_i = f_0（x_i） + z_i $在随机设计点上制作的$ x_i \ in \ in \ mathbb {r}^d $，$ i = 1，$ i = 1，\ ldots，ndots，n $。我们研究了一个构成设计点的Voronoi图的估计器，然后解决一个优化问题，该问题根据一定的总变化（电视）的某些离散概念（电视）正规化：参数的加权绝对差异$θ_i，θ_j$（估计函数值$ f_0（x_i），f_0（x_i），f_0（x_j x_j）$ y $ i y y $ i n y $ i n of y y $ i n of y y y y $ i n相邻$ i相邻。一旦我们将域限制为在voronoi图上分段恒定的函数，这被认为等于一个根据通常的连续性（测量理论）概念正规化的变分优化问题。 因此，所考虑的回归估计量在自适应形成的Voronoi细胞工会上进行（缩水）局部平均，我们将其称为Voronoigram，遵循Koenker（2005）中的思想，并从Tukey的回归图中汲取灵感（Tukey，1961年）。我们在本文中的贡献涵盖了概念和理论前沿：我们讨论了Voronoigram的一些独特属性，与使用其他基于图的离散化的电视调查估计器相比。我们得出了Voronoi电视功能的渐近极限；并且我们证明，对于估计本质上有限的BV函数，Voronoigram是最小速率最佳速率（最高对数因素）。
We consider the problem of estimating a multivariate function $f_0$ of bounded variation (BV), from noisy observations $y_i = f_0(x_i) + z_i$ made at random design points $x_i \in \mathbb{R}^d$, $i=1,\ldots,n$. We study an estimator that forms the Voronoi diagram of the design points, and then solves an optimization problem that regularizes according to a certain discrete notion of total variation (TV): the sum of weighted absolute differences of parameters $θ_i,θ_j$ (which estimate the function values $f_0(x_i),f_0(x_j)$) at all neighboring cells $i,j$ in the Voronoi diagram. This is seen to be equivalent to a variational optimization problem that regularizes according to the usual continuum (measure-theoretic) notion of TV, once we restrict the domain to functions that are piecewise constant over the Voronoi diagram. The regression estimator under consideration hence performs (shrunken) local averaging over adaptively formed unions of Voronoi cells, and we refer to it as the Voronoigram, following the ideas in Koenker (2005), and drawing inspiration from Tukey's regressogram (Tukey, 1961). Our contributions in this paper span both the conceptual and theoretical frontiers: we discuss some of the unique properties of the Voronoigram in comparison to TV-regularized estimators that use other graph-based discretizations; we derive the asymptotic limit of the Voronoi TV functional; and we prove that the Voronoigram is minimax rate optimal (up to log factors) for estimating BV functions that are essentially bounded.
