论文标题
一维数据的最稀少分段线性回归
Sparsest Piecewise-Linear Regression of One-Dimensional Data
论文作者
论文摘要
我们研究了第二个导数的总变化（TV）正则化（TV）正则化（TV）正则化（TV）的一维回归的问题，该衍生物已知这是促进几乎没有打结的分段线性溶液的问题。尽管有有效的算法来确定这种适应性花纹，但电视正则化的困难是该解决方案通常不是唯一的，这在实践中通常被忽略。在本文中，我们提出了一个系统分析，该分析完整地描述了解决方案设置，在解决方案是唯一的情况下，这些案例与唯一的情况之间有明确的区别，而这些解决方案设置更为频繁，却没有。对于后一种情况，我们确定最稀少的解决方案，即具有最小结数的解决方案，并得出一个公式以计算仅基于数据点的最小结数。为了实现这一目标，我们首先考虑确切的插值问题，这会导致更容易的理论分析。接下来，我们放宽了回归设置的确切插值要求，并考虑严格凸出数据验证成本函数的惩罚优化问题。我们表明，潜在的惩罚问题可以作为一个受约束的问题进行重新纠正，因此我们以前的所有结果仍然适用。基于我们的理论分析，我们提出了一种简单而快速的两步算法，即不可知论到独特性，以达到这一惩罚问题的最稀少解决方案。
We study the problem of one-dimensional regression of data points with total-variation (TV) regularization (in the sense of measures) on the second derivative, which is known to promote piecewise-linear solutions with few knots. While there are efficient algorithms for determining such adaptive splines, the difficulty with TV regularization is that the solution is generally non-unique, an aspect that is often ignored in practice. In this paper, we present a systematic analysis that results in a complete description of the solution set with a clear distinction between the cases where the solution is unique and those, much more frequent, where it is not. For the latter scenario, we identify the sparsest solutions, i.e., those with the minimum number of knots, and we derive a formula to compute the minimum number of knots based solely on the data points. To achieve this, we first consider the problem of exact interpolation which leads to an easier theoretical analysis. Next, we relax the exact interpolation requirement to a regression setting, and we consider a penalized optimization problem with a strictly convex data-fidelity cost function. We show that the underlying penalized problem can be reformulated as a constrained problem, and thus that all our previous results still apply. Based on our theoretical analysis, we propose a simple and fast two-step algorithm, agnostic to uniqueness, to reach a sparsest solution of this penalized problem.
