SPARSE APPROXIMATION VIA PENALTY DECOMPOSITION METHODS
SPARSE APPROXIMATION VIA PENALTY DECOMPOSITION METHODS
复制标题
DOI：
10.1137/100808071
复制
发表时间：
2013-01-01
影响因子：
3.1
通讯作者：
Zhang, Yong
中科院分区：
文献类型：
--
作者：
Lu, Zhaosong;Zhang, Yong
在本文中，我们考虑稀疏逼近问题，即一般的l（0）最小化问题的l（0）-“范数”的一部分，约束或目标函数的一个向量。特别是，我们首先研究这些问题的一阶最优性条件。然后，我们提出了惩罚分解（PD）的方法来解决这些问题，其中一系列的惩罚子问题解决了块坐标下降（BCD）的方法。在一些适当的假设下，我们建立了PD方法产生的序列的任何聚点满足问题的一阶最优性条件。此外，对于其中l（0）部分是唯一非凸部分的问题，我们证明了这样的聚点是问题的局部极小。此外，我们证明了BCD方法生成的序列的任何聚点是罚子问题的块坐标极小元。此外，对于l（0）部分是唯一非凸部分的问题，我们建立了这样的聚点是罚子问题的局部极小。最后，我们测试我们的PD方法的性能，将它们应用到稀疏逻辑回归，稀疏逆协方差选择，和压缩感知问题。计算结果表明，当寻求相同基数的解时，我们的方法应用于基于l（0）的模型通常具有更好的解质量和/或速度比现有的方法应用于相应的基于l（1）的模型。
In this paper we consider sparse approximation problems, that is, general l(0) minimization problems with the l(0)-"norm" of a vector being a part of constraints or objective function. In particular, we first study the first-order optimality conditions for these problems. We then propose penalty decomposition (PD) methods for solving them in which a sequence of penalty subproblems are solved by a block coordinate descent (BCD) method. Under some suitable assumptions, we establish that any accumulation point of the sequence generated by the PD methods satisfies the first-order optimality conditions of the problems. Furthermore, for the problems in which the l(0) part is the only nonconvex part, we show that such an accumulation point is a local minimizer of the problems. In addition, we show that any accumulation point of the sequence generated by the BCD method is a block coordinate minimizer of the penalty subproblem. Moreover, for the problems in which the l(0) part is the only nonconvex part, we establish that such an accumulation point is a local minimizer of the penalty subproblem. Finally, we test the performance of our PD methods by applying them to sparse logistic regression, sparse inverse covariance selection, and compressed sensing problems. The computational results demonstrate that when solutions of same cardinality are sought, our approach applied to the l(0)-based models generally has better solution quality and/or speed than the existing approaches that are applied to the corresponding l(1)-based models.