Minimizing Nonconvex Functions for Sparse Vector Reconstruction
Minimizing Nonconvex Functions for Sparse Vector Reconstruction
复制标题
DOI：
10.1109/tsp.2010.2046900
复制
发表时间：
2010-07-01
影响因子：
5.4
通讯作者：
Reilly, James P.
中科院分区：
文献类型：
--
作者：
Mourad, Nasser;Reilly, James P.
在本文中，我们开发了一种新的方法来最小化一类非凸（凹的非负正交）的功能，用于解决欠定线性方程组的解向量是已知的先验稀疏。所提出的技术是基于用易于最小化的二次凸函数局部替换原始目标函数。所得到的算法是迭代的，并且绝对收敛到原目标函数的不动点。对于一定的凸目标函数的选择，一类算法称为迭代加权最小二乘（IRLS）是所提出的方法的一个特例。因此，本文提出的算法是对已有方法的推广和统一。此外，我们还提出了一类新的算法，具有更好的收敛性能相比，定期IRLS算法，因此，可以被认为是这些算法的增强。由于原始目标函数是非凸的，所提出的算法是容易收敛到局部最小值。为了减轻这个困难，我们提出了一个随机扰动技术，提高了所提出的算法的性能。数值结果表明，所提出的算法优于一些众所周知的算法，通常用于解决同样的问题。
In this paper, we develop a novel methodology for minimizing a class of nonconvex (concave on the non-negative orthant) functions for solving an underdetermined linear system of equations when the solution vector is known a priori to be sparse. The proposed technique is based on locally replacing the original objective function by a quadratic convex function which is easily minimized. The resulting algorithm is iterative and is absolutely converging to a fixed point of the original objective function. For a certain selection of convex objective functions, the class of algorithms called iterative reweighted least squares (IRLS) is shown to be a special case of the proposed methodology. Thus, the proposed algorithms are a generalization and unification of the previous methods. In addition, we also propose a new class of algorithms with better convergence properties compared to the regular IRLS algorithms and, hence, can be considered as enhancements to these algorithms. Since the original objective functions are nonconvex, the proposed algorithm is susceptible to convergence to a local minimum. To alleviate this difficulty, we propose a random perturbation technique that enhances the performance of the proposed algorithm. The numerical results show that the proposed algorithms outperform some of the well-known algorithms that are usually utilized for solving the same problem.