PROBING THE PARETO FRONTIER FOR BASIS PURSUIT SOLUTIONS
PROBING THE PARETO FRONTIER FOR BASIS PURSUIT SOLUTIONS
复制标题
DOI：
10.1137/080714488
复制
发表时间：
2008-01-01
影响因子：
3.1
通讯作者：
Friedlander, Michael P.
中科院分区：
文献类型：
--
作者：
van den Berg, Ewout;Friedlander, Michael P.
基追求问题寻求一个待定最小二乘问题的最小一范数解。基追踪降噪（BPDN）只能近似地拟合最小二乘问题，单个参数确定一条曲线，该曲线跟踪最小二乘拟合和解的单范数之间的最优权衡。我们证明了这条曲线是凸的，并且在所有感兴趣的点上连续可微，并且表明它给出了与BPDN密切相关的另外两个优化问题的显式关系。我们描述了一种寻找曲线上任意点的寻根算法；该算法适用于大规模和复杂领域的问题。在每次迭代中，谱梯度投影法近似地最小化了具有显式单范数约束的最小二乘问题。只需要矩阵-向量运算。该问题的原对偶解给出了寻根法所需的函数和导数信息。对一组综合测试问题的数值实验表明，该方法适用于较大的问题。
The basis pursuit problem seeks a minimum one-norm solution of an underdetermined least-squares problem. Basis pursuit denoise (BPDN) fits the least-squares problem only approximately, and a single parameter determines a curve that traces the optimal trade-off between the least-squares fit and the one-norm of the solution. We prove that this curve is convex and continuously differentiable over all points of interest, and show that it gives an explicit relationship to two other optimization problems closely related to BPDN. We describe a root-finding algorithm for finding arbitrary points on this curve; the algorithm is suitable for problems that are large scale and for those that are in the complex domain. At each iteration, a spectral gradient-projection method approximately minimizes a least-squares problem with an explicit one-norm constraint. Only matrix-vector operations are required. The primal-dual solution of this problem gives function and derivative information needed for the root-finding method. Numerical experiments on a comprehensive set of test problems demonstrate that the method scales well to large problems.