We measure the degree of oscillation of a sampled function f by the number of its local extrema. The greater this number, the more oscillatory and complex f becomes. In signal denoising, we want a restored function g that is simple and fits the data f well. We propose to model this by a global optimization, coined oscillation regularization, that reduces both the data fitting error and the number of local extrema of g. To the best of our knowledge, the number of local extrema of g is a topological prior that is rarely exploited in the literature of regularization. We show that for sampled functions with values out of a discrete alphabet with V symbols defined on a chain of L nodes, the optimal solution can be found in O(VL) time using dynamic programming. For functions with continuous ranges we derive a polynomial time algorithm that depends only on L using linear programming. Despite its simplicity in concept and algorithms, experiments show that oscillation regularization often yields state-of-art result. The availability of efficient algorithms also makes our method highly useful in other applications.
Oscillation regularization uses the number of local extrema of a function to form the prior. In signal denoising, it is useful for recovering the noise-free signal while preserving the possible sharp transitions in the input. Here are the MATLAB/C++ [code] and the [paper].
