Generalized Methods and Solvers for Noise Removal from Piecewise Constant Signals

Abstract

Removing noise from piecewise constant (PWC) signals, is a challenging signal processing problem arising in many practical contexts. For example, in exploration geosciences, noisy drill hole records need separating into stratigraphic zones, and in biophysics, jumps between molecular dwell states need extracting from noisy fluorescence microscopy signals. Many PWC denoising methods exist, including total variation regularization, mean shift clustering, stepwise jump placement, running medians, convex clustering shrinkage and bilateral filtering; conventional linear signal processing methods are fundamentally unsuited however. This paper shows that most of these methods are associated with a special case of a generalized functional, minimized to achieve PWC denoising. The minimizer can be obtained by diverse solver algorithms, including stepwise jump placement, convex programming, finite differences, iterated running medians, least angle regression, regularization path following, and coordinate descent. We introduce novel PWC denoising methods, which, for example, combine global mean shift clustering with local total variation smoothing. Head-to-head comparisons between these methods are performed on synthetic data, revealing that our new methods have a useful role to play. Finally, overlaps between the methods of this paper and others such as wavelet shrinkage, hidden Markov models, and piecewise smooth filtering are touched on.

32 pages, 5 figures

References in corpus (3)

• Pathwise coordinate optimization
• Piecewise linear regularized solution paths
• A path algorithm for the Fused Lasso Signal Approximator

Cited by in corpus (9)

• Compressed Sensing with 1D Total Variation: Breaking Sample Complexity Barriers via Non-Uniform Recovery
• On change point detection using the fused lasso method
• Topological Data Analysis for True Step Detection in Piecewise Constant Signals
• Bayesian selection for the l2-Potts model regularization parameter: 1D piecewise constant signal denoising
• Smoothing for signals with discontinuities using higher order Mumford-Shah models
• Smoothing splines for discontinuous signals
• A fast Primal-Dual-Active-Jump method for minimization in $\mathrm{BV}((0,T);{\mathbb{R}}^d)$
• Degrees-of-freedom penalized piecewise regression
• How to monitor and mitigate stair-casing in l1 trend filtering