A unified approach for a 1D generalized total variation problem
A unified approach for a 1D generalized total variation problem
复制标题
DOI：
10.1007/s10107-021-01633-2
复制
发表时间：
2021-03
影响因子：
2.7
通讯作者：
Cheng Lu;D. Hochbaum
中科院分区：
文献类型：
--
作者：
Cheng Lu;D. Hochbaum
研究了一维离散信号去噪问题，该问题包括最小化可分离的凸保真项和凸正则项，凸正则化项惩罚相邻信号值的差异。这个问题推广了全变分正则化问题。本文给出了基于Karush-Kuhn-Tucker最优性条件的一般凸保真度和正则化函数的统一求解方法。对于一般的凸保真度和正则化函数问题，本文给出了一种快速算法，并且如果保真度函数是可微的，并且正则化函数是严格凸的，则该算法也是更快的。对于本文所研究的目标函数类，这两种算法都达到了比现有算法更好的理论最坏情况复杂性。同样在实践中，我们的C++实现方法比流行的C++非线性优化解算器要快得多。
We study a 1-dimensional discrete signal denoising problem that consists of minimizing a sum of separable convex fidelity terms and convex regularization terms, the latter penalize the differences of adjacent signal values. This problem generalizes the total variation regularization problem. We provide here a unified approach to solve the problem for general convex fidelity and regularization functions that is based on the Karush–Kuhn–Tucker optimality conditions. This approach is shown here to lead to a fast algorithm for the problem with general convex fidelity and regularization functions, and a faster algorithm if, in addition, the fidelity functions are differentiable and the regularization functions are strictly convex. Both algorithms achieve the best theoretical worst case complexity over existing algorithms for the classes of objective functions studied here. Also in practice, our C++ implementation of the method is considerably faster than popular C++ nonlinear optimization solvers for the problem.