Non-Negative Orthogonal Greedy Algorithms
Non-Negative Orthogonal Greedy Algorithms
复制标题
DOI：
10.1109/tsp.2019.2943225
复制
发表时间：
2018-05
影响因子：
5.4
通讯作者：
T. T. Nguyen-T.;J. Idier;C. Soussen;E. Djermoune
中科院分区：
文献类型：
--
作者：
T. T. Nguyen-T.;J. Idier;C. Soussen;E. Djermoune
正交贪婪算法是一种常用的稀疏信号重构算法。它们的原理是一个接一个地选择原子。一系列的无约束最小二乘子问题的大小逐渐增加的解决计算的近似系数，这是有效地执行使用快速递归更新计划。在处理非负稀疏信号重构时，需要求解一系列非负最小二乘法子问题。快速实现变得棘手，因为每个子问题不再有封闭形式的解决方案。最近，提出了经典正交匹配追踪和正交最小二乘算法的非负扩展，使用慢（即，非递归）或递归但不精确的实现。在本文中，我们重新审视这些算法在一个统一的方式。定义了一类非负正交贪婪算法，并给出了它们的结构性质。我们提出了一个快速和准确的实现的基础上的有效集分辨率的非负最小二乘和利用热启动初始化。该算法的精度和计算复杂度进行评估的稀疏尖峰反卷积问题。我们还提出了一个应用到近红外光谱分解。
Orthogonal greedy algorithms are popular sparse signal reconstruction algorithms. Their principle is to select atoms one by one. A series of unconstrained least-square subproblems of gradually increasing size is solved to compute the approximation coefficients, which is efficiently performed using a fast recursive update scheme. When dealing with non-negative sparse signal reconstruction, a series of non-negative least-squares subproblems have to be solved. Fast implementation becomes tricky since each subproblem does not have a closed-form solution anymore. Recently, non-negative extensions of the classical orthogonal matching pursuit and orthogonal least squares algorithms were proposed, using slow (i.e., non-recursive) or recursive but inexact implementations. In this paper, we revisit these algorithms in a unified way. We define a class of non-negative orthogonal greedy algorithms and exhibit their structural properties. We propose a fast and exact implementation based on the active-set resolution of non-negative least-squares and exploiting warm start initializations. The algorithms are assessed in terms of accuracy and computational complexity for a sparse spike deconvolution problem. We also present an application to near-infrared spectra decomposition.