Divided Differences, Falling Factorials, and Discrete Splines: Another Look at Trend Filtering and Related Problems

Abstract

This paper serves as a postscript of sorts to Tibshirani (2014); Wang et al. (2014), who developed continuous-time formulations and properties of trend filtering, a discrete-time smoothing tool proposed (independently) by Steidl et al. (2006); Kim et al. (2009). The central object of study is the falling factorial basis, as it was called by Tibshirani (2014); Wang et al. (2014). Its span turns out to be a space of piecewise polynomials that has a classical place in spline theory, called discrete splines (Mangasarian and Schumaker, 1971, 1973; Schumaker, 2007). At the Tibshirani (2014); Wang et al. (2014), we were not fully aware of these connections. The current paper attempts to rectify this by making these connections explicit, reviewing (and making use of) some of the important existing work on discrete splines, and contributing several new perspectives and new results on discrete splines along the way.