Computes the discrete derivative of a function (or vector of function evaluations) of a given order, with respect to given design points, and evaluated at a given query point.
discrete_deriv(f, k, xd, x)Function, or vector of function evaluations at c(xd, x), the
design points xd adjoined with the query point(s) x.
Order for the discrete derivative calculation. Must be >= 0.
Design points. Must be sorted in increasing order, and have length
at least k+1.
Query point(s).
Discrete derivative of f of order k, with respect to design
points xd, evaluated at the query point(s) x.
The discrete derivative operator of order \(k\), with respect design points \(x_1 < \ldots < x_n\), is denoted \(\Delta^k_n\). Acting on a function \(f\), and evaluated at a query point \(x\), it yields: $$ (\Delta^k_n f) (x) = \begin{cases} k! \cdot f[x_{i-k+1},\ldots,x_i,x] & \text{if $x \in (x_i,x_{i+1}]$, $i \geq k$} \\ i! \cdot f[x_1,\ldots,x_i,x] & \text{if $x \in (x_i,x_{i+1}]$, $i < k$} \\ f(x) & \text{if $x \leq x_1$}, \end{cases} $$ where we take \(x_{n+1} = \infty\) for convenience. In other words, for "most" points \(x > x_k\), we define \((\Delta^k_n f)(x)\) in terms of a (scaled) divided difference of \(f\) of order \(k\), where the centers are the \(k\) points immediately to the left of \(x\), and \(x\) itself. Meanwhile, for "boundary" points \(x \leq x_k\), we define \((\Delta^k_n f)(x)\) to be a (scaled) divided difference of \(f\) of the highest possible order, where the centers are the points to the left of \(x\), and \(x\) itself. For more discussion, including alternative representations for the discrete differentiation, see Section 3.1 of Tibshirani (2020).
Note: for calculating discrete derivatives at the design points
themselves, which could be achieved by taking x = xd in the current
function, one should instead use b_mat_mult() or d_mat_mult(), as these
will be more efficient (both will be linear-time, but the latter functions
will be faster).
Tibshirani (2020), "Divided differences, falling factorials, and discrete splines: Another look at trend filtering and related problems", Section 3.1.
b_mat_mult(), d_mat_mult() for multiplication by the extended
and non-extended discrete derivative matrices, giving discrete derivatives
at design points.