An Interior-Point Method for Large-Scale l1-Regularized Least Squares
An Interior-Point Method for Large-Scale l1-Regularized Least Squares
复制标题
DOI：
10.1109/jstsp.2007.910971
复制
发表时间：
2007-12-01
影响因子：
7.5
通讯作者：
Gorinevsky, Dimitry
中科院分区：
文献类型：
--
作者：
Kim, Seung-Jean;Koh, K.;Gorinevsky, Dimitry
最近，已经对用于稀疏信号重构的基于l（1）正则化的方法（例如，基追踪去噪和压缩传感）和特征选择（例如，Lasso算法）在信号处理、统计学和相关领域中的应用。这些问题可以转化为l（1）-正则化最小二乘规划（LSPs），其可以重新表示为凸二次规划，然后通过几种标准方法如邻域点法求解，至少对于小型和中型问题。在本文中，我们描述了一个专门的邻域点方法来解决大规模，l（1）-正则化的LSP，使用预处理共轭梯度算法来计算搜索方向。邻点法可以解决大型稀疏问题，有一百万个变量和观察，在PC上几十分钟。它可以有效地解决大型密集的问题，出现在稀疏信号恢复与正交变换，利用这些变换的快速算法。该方法在磁共振成像数据集上示出。
Recently, a lot of attention has been paid to l(1) regularization based methods for sparse signal reconstruction (e.g., basis pursuit denoising and compressed sensing) and feature selection (e.g., the Lasso algorithm) in signal processing, statistics, and related fields. These problems can be cast as l(1)-regularized least-squares programs (LSPs), which can be reformulated as convex quadratic programs, and then solved by several standard methods such as interior-point methods, at least for small and medium size problems. In this paper, we describe a specialized interior-point method for solving large-scale, l(1)-regularized LSPs that uses the preconditioned conjugate gradients algorithm to compute the search direction. The interior-point method can solve large sparse problems, with a million variables and observations, in a few tens of minutes on a PC. It can efficiently solve large dense problems, that arise in sparse signal recovery with orthogonal transforms, by exploiting fast algorithms for these transforms. The method is illustrated on a magnetic resonance imaging data set.