Carnegie Mellon University
ahu2_phd_sta_2023.pdf (21.32 MB)

Estimation of BVk functions from scattered data

Download (21.32 MB)
posted on 2023-12-20, 19:54 authored by Addison J. Hu
 The study of bounded variation (BV) functions, and its higher-order generalizations (BVk functions), is rooted in many ?elds: statistics, signal processing, functional analysis, approximation theory, among others. From these diverse perspectives has emerged a comprehensive theory of BVk functions and their estimation from noisy data in dimension d = 1. In dimension d > 1, the statistical picture is much less clear. Existing statistical theory for BVk functions can broadly broken down into two categories: replacing the continuous-time BVk function class with a discrete analogue; or retaining the continuous-time function class and using continuous-time loss (e.g., the white noise model). A gap in the literature lies in the estimation of functions from the continuous-time function class under a sampling model. This thesis is motivated by that gap. 
The second and third chapters address the problem of estimating BVk functions, for index values k = 0 and k = 1, using scattered data. These cases correspond to functions of bounded variation and functions whose gradient are bounded variation, respectively. For the k = 0 case, we study an estimator, the Voronoigram, which fits piecewise constant functions using the Voronoi tessellation of the sample locations. Using the Voronoigram, we establish that the minimax rate (up to log terms) over bounded variation classes is n −1/d. For the k = 1 case, we study an estimator, the Delaunaygram, which fits continuous piecewise linear functions using the Delaunay tessellation of the sample locations. We ?nd that the Delaunaygram has a n −4/(4+d) rate of convergence when d < 4 and n −2/d rate when d ≥ 4 over discrete gradient variation classes, and ob?tain matching minimax lower bounds over continuous gradient variation classes. We address the discrete-to-continuous gap, which we expect to be resolved in following work. Along the way, we explore methodological, computational, and practical properties of the two estimators. 
The final chapter addresses the broader goal of estimating of BVk functions, k ≥ 2. Special attention is called to the following topics: bounded variation classes for k ≥ 2; anticipated rates of convergence for BVk classes; challenges specific to dimension d > 1; and the desired properties of higher-order generalizations of the estimators studied in this thesis. 




Degree Type

  • Dissertation


  • Statistics and Data Science

Degree Name

  • Doctor of Philosophy (PhD)


Ryan Tibshirani