# Multivariate Trend Filtering for Lattice Data

arXiv: https://arxiv.org/abs/2112.14758 · HTML: https://mlsanity.com/paper/2112.14758/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 107 references that are in the map.
- First posted on arXiv 29 Dec 2021.

## Builds on (most cited first, 21 of 21)

- [Adaptive piecewise polynomial estimation via trend filtering](https://mlsanity.com/paper/1304.2986/) (2013)
- [Trend Filtering on Graphs](https://mlsanity.com/paper/1410.7690/) (2014)
- [Total Variation Classes Beyond 1d: Minimax Rates, and the Limitations of Linear Smoothers](https://mlsanity.com/paper/1605.08400/) (2016)
- [On the Prediction Performance of the Lasso](https://mlsanity.com/paper/1402.1700/) (2014)
- [Dykstra's Algorithm, ADMM, and Coordinate Descent: Connections, Insights, and Extensions](https://mlsanity.com/paper/1705.04768/) (2017)
- [Multivariate extensions of isotonic regression and total variation denoising via entire monotonicity and Hardy-Krause variation](https://mlsanity.com/paper/1903.01395/) (2019)
- [Generalized Sparse Additive Models](https://mlsanity.com/paper/1903.04641/) (2019)
- [Fast and Flexible ADMM Algorithms for Trend Filtering](https://mlsanity.com/paper/1406.2082/) (2014)
- [Modular proximal optimization for multidimensional total-variation regularization](https://mlsanity.com/paper/1411.0589/) (2014)
- [Adaptive Estimation of Multivariate Piecewise Polynomials and Bounded Variation Functions by Optimal Decision Trees](https://mlsanity.com/paper/1911.11562/) (2019)
- [The Falling Factorial Basis and Its Statistical Applications](https://mlsanity.com/paper/1405.0558/) (2014)
- [Prediction bounds for higher order total variation regularized least squares](https://mlsanity.com/paper/1904.10871/) (2019)
- [New Risk Bounds for 2D Total Variation Denoising](https://mlsanity.com/paper/1902.01215/) (2019)
- [Divided Differences, Falling Factorials, and Discrete Splines: Another Look at Trend Filtering and Related Problems](https://mlsanity.com/paper/2003.03886/) (2020)
- [Construction of Tight Frames on Graphs and Application to Denoising](https://mlsanity.com/paper/1408.4012/) (2014)
- [MARS via LASSO](https://mlsanity.com/paper/2111.11694/) (2021)
- [Non-parametric Quantile Regression via the K-NN Fused Lasso](https://mlsanity.com/paper/2012.01758/) (2020)
- [A Fast and Flexible Algorithm for the Graph-Fused Lasso](https://mlsanity.com/paper/1505.06475/) (2015)
- [Adaptive Non-Parametric Regression With the K-NN Fused Lasso](https://mlsanity.com/paper/1807.11641/) (2018)
- [Nonparametric density estimation by histogram trend filtering](https://mlsanity.com/paper/1509.04348/) (2015)
- [Fused Density Estimation: Theory and Methods](https://mlsanity.com/paper/1805.03288/) (2018)

## Built on by (most cited first, 4 of 4)

- [Deep Learning meets Nonparametric Regression: Are Weight-Decayed DNNs Locally Adaptive?](https://mlsanity.com/paper/2204.09664/) (2022)
- [The Voronoigram: Minimax Estimation of Bounded Variation Functions From Scattered Data](https://mlsanity.com/paper/2212.14514/) (2022)
- [Variance estimation in graphs with the fused lasso](https://mlsanity.com/paper/2207.12638/) (2022)
- [Graph-dependent shrinkage priors for Bayesian trend filtering](https://mlsanity.com/paper/2608.23802/) (2026)

## Abstract (arXiv)

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 ℓ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 kth 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).