基于似零范数和混合优化的压缩感知信号快速重构算法

伍飞云; 周跃海; 童峰

doi:10.3724/SP.J.1004.2014.02145

基于似零范数和混合优化的压缩感知信号快速重构算法

doi: 10.3724/SP.J.1004.2014.02145

1.
厦门大学水声通信与海洋信息技术教育部重点实验室厦门 361005

基金项目:

国家自然科学基金(11274259), 教育部高等学校博士点专项基金(20120121110030) 资助

详细信息

作者简介:
伍飞云厦门大学海洋与地球学院博士研究生. 主要研究方向为信号处理, 水声通信. E-mail: wfyfly@126.com

计量
- 文章访问数: 1728
- HTML全文浏览量: 116
- PDF下载量: 1103
- 被引次数: 0
出版历程
- 收稿日期: 2013-04-10
- 修回日期: 2014-05-21
- 刊出日期: 2014-10-20

A Fast Sparse Signal Recovery Algorithm Based on Approximate l₀ Norm and Hybrid Optimization

1.
Key Laboratory of Underwater Acoustic Communication and Marine Information Technique of the Ministry of Education, Xiamen University, Xiamen 361005

Funds:

Supported by National Natural Science Foundation of China (11274259), and the Specialized Research Fund for the Doctoral Program of Higher Education of China (20120121110030)

摘要

摘要: 欠定系统(又称超完备系统)的稀疏信号恢复在压缩感知、源信号分离和信号采集等领域中被广泛研究. 目前这类问题主要采用l1范数约束结合线性规划优化或贪婪算法进行求解, 但这些方法存在收敛速度慢、恢复精度不高等缺陷. 提出一种快速恢复稀疏信号的算法, 该算法采用一种新的近似l0范数代替l1范数构造代价函数, 并融合牛顿法和最陡梯度法推导出寻优迭代式,以获得似零范数代价函数的最优解. 仿真实验和真实数据实验结果表明, 与经典算法相比, 该算法在能提供相同精度、甚至更好精度的条件下, 收敛速度更快.
- 范数约束 /
- 稀疏信号恢复 /
- 似零范数 /
- 稀疏水声信通 /
- 压缩感知
Abstract: Obtaining sparse solutions of under-determined, or over-complete, linear systems of equations has found extensive applications in signal processing of compressive sensing, source separation and signal acquisition. However, the previous approaches to this problem, which generally minimize the l1 norm using linear programming (LP) techniques or greedy methods, are subject to drawbacks such as low accuracy and slow convergence. This paper proposes to replace the l1 norm with a newly defined approximate l0 norm (AL0), the optimization of which leads to the derivation of a hybrid approach by incorporating the steepest descent method with the Newton iteration. Numerical simulations and real data experiment show that the proposed algorithm is about two to three orders of magnitude faster than the state-of-the-art interior-point LP solvers, while providing the same (or better) accuracy.
- Norm constraint /
- sparse signal reconstruction /
- approximate l0 norm /
- sparse underwater acoustic channel /
- compressed sensing

HTML全文

参考文献(20)

[1]	Takigawa T, Kudo M, Toyama T. Performance analysis of minimum l1-norm solutions for underdetermined source separation. IEEE Transaction on Signal Processing, 2004, 52(3): 582-591
[2]	[2] Kim S J, Koh K, Lustig M, Boyd S, Gorinevsky D. An interior-point method for large-scale l1-regularized least squares. IEEE Journal of Selected Topics in Signal Processing, 2007, 1(4): 606-617
[3]	[3] Figueiredo M, Nowak R, Wright S. Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems. IEEE Journal of Selected Topics in Signal Processing, 2007, 1(4): 586-597
[4]	[4] Tropp J A. Greed is good: algorithmic results for sparse approximation. IEEE Transaction on Information Theory, 2004, 50(10): 2231-2242
[5]	[5] Tropp J A, Gilbert A C. Signal recovery from random measurements via orthogonal matching pursuit. IEEE Transactions on Information Theory, 2007, 53(12): 4655-4666
[6]	[6] Blumensath T, Davies M E. Iterative hard thresholding for compressed sensing. Applied and Computational Harmonic Analysis, 2009, 27(3): 265-274
[7]	[7] Hosein M, Massoud B Z, Christian J. A fast approach for overcomplete sparse decomposition based on smoothed l0 norm. IEEE Transaction on Signal Processing, 2009, 57(1): 289-301
[8]	[8] Blumensath T, Davies M E. Normalized iterative hard thresholding: guaranteed stability and performance. IEEE Journal of Selected Topics in Signal Processing, 2010, 4(2): 298-309
[9]	Wang Jun-Hua, Huang Zhi-Tao, Zhou Yi-Yu, Wang Feng-Hua. Robust sparse recovery based on approximate l0 norm. Chinese Journal of Electronics, 2012, 40(5): 1185-1189(王军华, 黄知涛, 周一宇, 王丰华. 基于近似l0范数的稳健稀疏重构算法. 电子学报, 2012, 40(5): 1185-1189)
[10]	Wu F Y, Tong F. Gradient optimization p-norm-like constraint LMS algorithm for sparse system estimation. Signal Processing, 2013, 93(4): 967-971
[11]	Wu F Y, Tong F. Non-uniform norm constraint LMS algorithm for sparse system identification. IEEE Communication Letters, 2013, 17(2): 385-388
[12]	Jin J, Gu Y, Mei S. A stochastic gradient approach on compressive sensing signal reconstruction based on adaptive filtering framework. IEEE Journal of Selected Topics in Signal Processing, 2010, 4(2): 409-420
[13]	Shi K, Shi P. Adaptive sparse Volterra system identification with l0-norm penalty. Signal Processing, 2011, 91(10): 2432-2436
[14]	Palais R S. A simple proof of the Banach contraction principle. Journal of Fixed Point Theory and Applications, 2007, 2(2): 221-223
[15]	Garg R, Khandekar R. Gradient descent with sparsification: an iterative algorithm for sparse recovery with restricted isometry property. In: Proceedings of the 26th Annual International Conference on Machine Learning. New York: ACM, 2009. 337-344
[16]	Stojanovic M. Retrofocusing techniques for high rate acoustic communications. The Journal of the Acoustical Society of America, 2005, 117(3): 1173-1185
[17]	Zhang Cheng, Yang Hai-Rong, Wei Sui. Compressive sensing based on deterministic sparse Toeplitz measurement matrices with random pitch. Acta Automatica Sinica, 2012, 38(8): 1362-1369(张成, 杨海蓉, 韦穗. 基于随机间距稀疏Teoplitz测量矩阵的压缩传感. 自动化学报, 2012, 38(8): 1362-1369)
[18]	Li Shu-Tao, Wei Dan. A survey on compressive sensing. Acta Automatica Sinica, 2009, 35(11): 1369-1377(李树涛, 魏丹. 压缩传感综述. 自动化学报, 2009, 35(11): 1369-1377)
[19]	Liu Fang, Wu Jiao, Yang Shu-Yuan, Jiao Li-Cheng. Research advances on structured compressive sensing. Acta Automatica Sinica, 2013, 39(12): 1980-1995 (刘芳, 武娇, 杨淑媛, 焦李成. 结构化压缩感知研究进展. 自动化学报, 2013, 39(12): 1980-1995)
[20]	Li W C, Preisig J C. Estimation of rapidly time-varying sparse channels. IEEE Journal of Oceanic Engineering, 2007, 32(4): 927-939