Univariate total variation denoising

Denoises a sequence of observations by solving the univariate total variation denoising optimization problem at a given regularization level.

Usage

tvdenoising(y, lambda, weights = NULL)

Arguments

y

Vector of observations to be denoised.

lambda

Regularization parameter value. Must be >= 0.

weights

Vector of observation weights. The default is NULL, which corresponds to unity weights. If specified, this vector must have the same length as y, and must have positive entries.

Value

Vector of denoised values.

Details

This function minimizes the univariate total variation denoising (also called fused lasso) criterion squares criterion $$ \frac{1}{2} \sum_{i=1}^n (y_i - \theta_i)^2 + \lambda \sum_{i=1}^{n-1} |\theta_{i+1} - \theta_i|, $$ over \(\theta\). This is a special structured convex optimization problem which can be solved in linear time (\(O(n)\) operations) using algorithms based on dynamic programming (Viterbi) or taut string methods. The current function implements a highly-efficient dynamic programming method developed by Johnson (2013).

References

Johnson (2013), "A dynamic programming algorithm for the fused lasso and L0-segmentation."

Examples

y <- c(rep(0, 50), rep(3, 50)) + rnorm(100)
yhat <- tvdenoising(y, 5)
plot(y, pch = 16, col = "gray60")
lines(yhat, col = "firebrick", lwd = 2)