On the LASSO and Dantzig selector equivalence
On the LASSO and Dantzig selector equivalence
复制标题
DOI：
10.1109/ciss.2010.5464890
复制
发表时间：
2010-03
期刊：
影响因子：
--
通讯作者：
M. Salman Asif;J. Romberg
中科院分区：
文献类型：
--
作者：
M. Salman Asif;J. Romberg
从噪声观测中恢复稀疏信号是许多信息处理环境中出现的问题。Lasso和Dantzig选择器(DS)是用于从线性观测中恢复高维稀疏信号的两种众所周知的方案。本文给出了套索与DS等价的一些结果。我们讨论了套索解与DS解相同的一组条件。有了这些条件，我们制定了一个收缩过程，套索和DS遵循相同的解决路径。此外，我们证明了在这些收缩条件下，套索和DS的解至多只需S同伦步长即可得到，其中S是最终解中非零元的个数。因此，寻找M×N系统的完全同伦路径的计算代价仅为O(SMN)。
Recovery of sparse signals from noisy observations is a problem that arises in many information processing contexts. LASSO and the Dantzig selector (DS) are two well-known schemes used to recover high-dimensional sparse signals from linear observations. This paper presents some results on the equivalence between LASSO and DS. We discuss a set of conditions under which the solutions of LASSO and DS are same. With these conditions in place, we formulate a shrinkage procedure for which LASSO and DS follow the same solution path. Furthermore, we show that under these shrinkage conditions the solution to LASSO and DS can be attained in at most S homotopy steps, where S is the number of nonzero elements in the final solution. Thus the computational cost for finding complete homotopy path for an M × N system is merely O(SMN).