Multiplies a given vector by D, the discrete derivative matrix of a given order, with respect to given design points.
d_mat_mult(v, k, xd, tf_weighting = FALSE, transpose = FALSE)Vector to be multiplied by D, the discrete derivative matrix.
Order for the discrete derivative matrix. Must be >= 0.
Design points. Must be sorted in increasing order, and have length
at least k+1.
Should "trend filtering weighting" be used? This is a
weighting of the discrete derivatives that is implicit in trend filtering;
see details for more information. The default is FALSE.
Multiply by the transpose of D? The default is FALSE.
Product of the discrete derivative matrix D and the input vector v.
The discrete derivative matrix of order \(k\), with respect to
design points \(x_1 < \ldots < x_n\), is denoted \(D^k_n\). It has
dimension \((n-k) \times n\). Acting on a vector \(v\) of function
evaluations at the design points, denoted \(v = f(x_{1:n})\), it gives
the discrete derivatives of \(f\) at the points \(x_{(k+1):n}\):
$$
D^k_n v = (\Delta^k_n f) (x_{(k+1):n}).
$$
The matrix \(D^k_n\) can be constructed recursively as the product of a
diagonally-weighted first difference matrix and \(D^{k-1}_n\); see the
help file for d_mat(), or Section 6.1 of Tibshirani (2020). Therefore,
multiplication by \(D^k_n\) or by its transpose can be performed in
\(O(nk)\) operations based on iterated weighted differences. See Appendix
D of Tibshirani (2020) for details.
The option tf_weighting = TRUE performs multiplication by \(W^k_n D^k_n\)
where \(W^k_n\) is a \((n-k) \times (n-k)\) diagonal matrix with
entries \((x_{i+k} - x_i) / k\), \(i = 1,\ldots,n-k\). This weighting
is implicit in trend filtering, as the penalty in the \(k\)th order trend
filtering optimization problem (with optimization parameter \(\theta\))
is \(\|W^{k+1}_n D^{k+1}_n \theta\|_1\). Moreover, this is precisely the
\(k\)th order total variation of the \(k\)th degree discrete spline
interpolant \(f\) to \(\theta\), with knots in \(x_{(k+1):(n-1)}\);
that is, such an interpolant satisfies:
$$
\mathrm{TV}(D^k f) = \|W^{k+1}_n D^{k+1}_n \theta\|_1,
$$
where \(D^k f\) is the \(k\)th derivative of \(f\). See Section
9.1. of Tibshirani (2020) for more details.
Tibshirani (2020), "Divided differences, falling factorials, and discrete splines: Another look at trend filtering and related problems", Section 6.1.
discrete_deriv() for discrete differentiation at arbitrary query
points, b_mat_mult() for multiplying by the extended discrete derivative
matrix, and d_mat() for constructing the discrete derivative matrix.