  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 (Steidl et
al., 2006; Kim et al., 2009; Tibshirani, 2014), 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 $\ell_1$-penalized basis regression problem where the basis
functions are tensor products of falling factorial functions, a piecewise
polynomial (discrete spline) basis that underlies univariate trend filtering.
  This paper is a unification and extension of the results in Sadhanala et al.
(2016, 2017). We develop a complete set of theoretical results that describe
the behavior of $k^{\mathrm{th}}$ order Kronecker trend filtering in $d$
dimensions, for every $k \geq 0$ and $d \geq 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$).
