Sparse signal reconstruction via concave continuous piecewise linear programming

详细信息    查看全文

• 作者：Kuangyu Liu^a ; ^{liu-ky12@mails.tsinghua.edu.cn" class="auth_mail" title="E-mail the corresponding author}Author Vitae ; Zhiming Xu^a ; ^b ; ^{xzm13@mails.tsinghua.edu.cn" class="auth_mail" title="E-mail the corresponding author}Author Vitae ; Xiangming Xi^a ; ^{xxm10@mails.tsinghua.edu.cn" class="auth_mail" title="E-mail the corresponding author}Author Vitae ; Shuning Wang^a ; ^{swang@mail.tsinghua.edu.cn" class="auth_mail" title="E-mail the corresponding author}Author Vitae
• 关键词：Compressed sensing ; Continuous piecewise linear programming ; Global optimization ; γ valid cut
• 刊名：Digital Signal Processing
• 出版年：2016
• 出版时间：July 2016
• 年：2016
• 卷：54
• 期：Complete
• 页码：12-26
• 全文大小：957 K

文摘

Compressed sensing (CS) is a new paradigm for acquiring sparse and compressible signals which can be approximated using much less information than their nominal dimension would suggest. In order to recover a signal from its compressive measurements, the conventional CS theory seeks the sparsest signal that agrees with the measurements via a great many algorithms, which usually solve merely an approximation of the pan id="mmlsi1" class="mathmlsrc">pan class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1051200416300045&_mathId=si1.gif&_user=111111111&_pii=S1051200416300045&_rdoc=1&_issn=10512004&md5=772f6491887d4f8835616aaaed937409" title="Click to view the MathML source">l₀pan>pan class="mathContainer hidden">pan class="mathCode">$l_0$pan>pan>pan> norm minimization. In this paper, CS has been considered from a new perspective. We equivalently transform the pan id="mmlsi1" class="mathmlsrc">pan class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1051200416300045&_mathId=si1.gif&_user=111111111&_pii=S1051200416300045&_rdoc=1&_issn=10512004&md5=772f6491887d4f8835616aaaed937409" title="Click to view the MathML source">l₀pan>pan class="mathContainer hidden">pan class="mathCode">$l_0$pan>pan>pan> norm minimization into a concave continuous piecewise linear programming based on the prior knowledge of sparsity, and propose a novel global optimization algorithm for it based on a sophisticated detour strategy and the γ valid cut theory. Numerical experiments demonstrate that our algorithm improves the best known number of measurements in the literature, relaxes the restrictions of the sensing matrix to some extent, and performs robustly in the noisy scenarios.