MULTIVARIATE TREND FILTERING FOR LATTICE DATA

• 成果类型: Article
• 署名作者: Sadhanala, Veeranjaneyulu; Wang, Yu-xiang; Hu, Addison j.; Tibshirani, Ryan j.
• 署名单位: Alphabet Inc.; Google Incorporated; University of California System; University of California San Diego; Carnegie Mellon University; University of California System; University of California Davis
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/24-AOS2440
• 发表日期: 2024
• 页码: 2400-2430
• 关键词: total variation minimization; Minimax Adaptive Estimation; Nonlinear estimation; DENSITY-ESTIMATION; selection rule; risk bounds; adaptation; restoration; regression; FAMILY

摘要

We study a multivariate version of trend filtering, called Kronecker trend filtering or KTF, for the case in which the design points form a lattice in d dimensions. KTF is a natural extension of univariate trend filtering ( Int. J. Comput. Vis. 70 (2006) 214-255; SIAM Rev. 51 (2009) 339-360; Ann. Statist. 42 (2014) 285-323), and is defined by minimizing a penalized least squares problem whose penalty term sums the absolute (higher-order) differences of the parameter to be estimated along each of the coordinate directions. The corresponding penalty operator can be written in terms of Kronecker products of univariate trend filtering penalty operators, hence the name Kronecker trend filtering. Equivalently, one can view KTF in terms of an I 1-penalized basis regression problem where the basis functions are tensor products of falling factorial functions, which is a piecewise polynomial (discrete spline) basis that underlies univariate trend filtering. This paper is a unification and extension of the results in (In Advances in Neural Information Processing Systems (2016); in Advances in Neural Information Processing Systems (2017)). We develop a complete set of theoretical results that describe the behavior of k th-order Kronecker trend filtering in d dimensions, for every k >= 0 and d >= 1. This reveals a number of interesting phenomena, including the dominance of KTF over linear smoothers in estimating heterogeneously smooth functions, and a phase transition at d = 2(k + 1), a boundary past which (on the high dimension-to-smoothness side) linear smoothers fail to be consistent entirely. We also leverage recent results on discrete splines from (Tibshirani (2020)), in particular, discrete spline interpolation results that enable us to extend the KTF estimate to any off-lattice location in constant-time (independent of the size of the lattice n ).