基追踪问题的近点算法及其应用研究

J4 ›› 2016, Vol. 38 ›› Issue (01): 120-124.

基追踪问题的近点算法及其应用研究

张小亚，张慧，王红霞

（国防科学技术大学理学院,湖南长沙 410073）

收稿日期:2014-09-10 修回日期:2015-04-28 出版日期:2016-01-25 发布日期:2016-01-25
基金资助:
国家自然科学基金（61072118,61201327）

A proximal point algorithm of
basis pursuit and its applications

ZHANG Xiaoya，ZHANG Hui，WANG Hongxia

（College of Science,National University of Defense Technology,Changsha 410073,China）

Received:2014-09-10 Revised:2015-04-28 Online:2016-01-25 Published:2016-01-25

摘要/Abstract

摘要：

基追踪问题具有广泛的应用背景，近年来得到了大量的关注和研究。近点算法是解决该问题的一种有效算法,其关键是子问题的求解,利用线性Bregman迭代的求解思想进行Lagrange对偶分析求解子问题，设计了一个新的迭代算法BPPPA。与线性Bregman算法相比，BPPPA可避免参数选取对模型的依赖，并用于非压缩感知的稀疏恢复问题求解。同时,为了提高新算法的收敛速度，进一步对新算法进行了Nestrove加速，得到了加速的BPPPA算法。数值实验中，分别针对压缩感知中的稀疏信号恢复和非压缩感知模型，测试了参数选取对算法效率的影响，实验结果验证了新算法的有效性。

关键词: 基追踪问题, 近点算法, 线性Bregman迭代, 稀疏恢复, 对偶分析

Abstract:

Basis pursuit has promising applications and becomes a hotspot research topic in recent years. The proximal point algorithm is an effective way for solving basis pursuit problems. We propose a new algorithm, which combines the proximal point algorithm and the idea of linearized Bregman algorithm to solve this problem under the Lagrange dual analysis. Compared with the original linearized Bregman algorithm, the proposed algorithm can avoid the dependency of parameter selection on the model, so its application is beyond the compressed sensing problems. In order to accelerate the convergence speed of the new algorithm, every subproblem is speeded up by Nestrove acceleration scheme. In the simulations on sparse recovery problems of both compressed sensing and noncompressed sensing, we test the influence of parameter selections on the algorithm’s convergence, and the results demonstrate the advantage of this new algorithm.

Key words: basis pursuit;proximal point algorithm;linearized Bregman iteration;sparse recovery;dual analysis

张小亚，张慧，王红霞. 基追踪问题的近点算法及其应用研究[J]. J4, 2016, 38(01): 120-124.

ZHANG Xiaoya，ZHANG Hui，WANG Hongxia. A proximal point algorithm of
basis pursuit and its applications [J]. J4, 2016, 38(01): 120-124.

参考文献［9］

［1］	Figueiredo M,Nowak R,Wright S. Gradient projection for sparse reconstruction:Application to compressed sensing and other inverse problems［J］. Journal of Selected Topics in Signal Processing,2007,1(4):586598.
［2］	Yin W, Osher S, Goldfarb D, et al. Bregman iterative algorithms for l1minimization with applications to compressed sensing［J］. SIAM Journal on Imaging Sciences,2008,1(1):143168.
［3］	Chen S,Dohono D,Saunders M A. Atomic decomposition by basis pursuit ［J］. SIAM Journal on Scientific Computing,2001,58(1):3361.
［4］	Parikh N,Boyd S. Proximal algorithms［J］. Foundations and Trends in Optimization,2014,1(3):123231.
［5］	Lai M,Yin W. Augmented and nuclearnorm models with a globally linearly convergent algorithm［J］. SIAM Journal on Imaging Sciences,2013,6(2):10591091.
［6］	Zhang H,Yin W. Gradient methods for convex minimization:Better rates under weaker conditions:CAM Report［R］. UCLA,2013:1317.
［7］	Nesterov. Y. Gradient methods for minimizing composite objective function［J］.Mathematical Programming,2007,140(3):768785.
［8］	Rockafellar R. Monotone operators and the proximal point algorithm［J］. SIAM Journal on Control and Optimization,1976,14(5):877898.
［9］	Guler O. New proximal point algorithms for convex minimization［J］. Society for Industy and Applied Mathematics,1992,2(4):649664.