Fast Non-Negative Orthogonal Matching Pursuit
Fast Non-Negative Orthogonal Matching Pursuit
复制标题
DOI：
10.1109/lsp.2015.2393637
复制
发表时间：
2015-01
影响因子：
3.9
通讯作者：
Mehrdad Yaghoobi;Di Wu;M. Davies
中科院分区：
文献类型：
--
作者：
Mehrdad Yaghoobi;Di Wu;M. Davies
非负信号是一类重要的稀疏信号。已经提出了许多算法来恢复这种非负表示，其中贪婪和凸松弛算法是最流行的方法之一。贪婪技术已被修改，以纳入表示的非负性。一个这样的修改已经提出了正交匹配追踪（OMP），它首先选择正系数，并使用非负优化技术作为替代的正交投影到选定的支持。除了优化程序的额外计算成本之外，它并没有受益于OMP的快速实现技术。这些快速实现是基于矩阵分解。在这里，我们首先调查的问题，积极的代表性，使用追求算法。然后，我们将描述一个新的实现，它可以完全结合的系数的正性约束，在整个选择阶段的算法。因此，我们提出了一种新的快速实现的非负OMP，这是基于QR分解和迭代系数更新。我们将经验表明，这样的修改可以很容易地加快实施的一个因素，在一个合理的大小问题。
One of the important classes of sparse signals is the non-negative signals. Many algorithms have already been proposed to recover such non-negative representations, where greedy and convex relaxed algorithms are among the most popular methods. The greedy techniques have been modified to incorporate the non-negativity of the representations. One such modification has been proposed for Orthogonal Matching Pursuit (OMP), which first chooses positive coefficients and uses a non-negative optimisation technique as a replacement for the orthogonal projection onto the selected support. Beside the extra computational costs of the optimisation program, it does not benefit from the fast implementation techniques of OMP. These fast implementations are based on the matrix factorisations. We here first investigate the problem of positive representation, using pursuit algorithms. We will then describe a new implementation, which can fully incorporate the positivity constraint of the coefficients, throughout the selection stage of the algorithm. As a result, we present a novel fast implementation of the Non-Negative OMP, which is based on the QR decomposition and an iterative coefficients update. We will empirically show that such a modification can easily accelerate the implementation by a factor of ten in a reasonable size problem.