Sparse signal reconstruction via concave continuous piecewise linear programming

作者：Liu, Kuangyu^*; Xu, Zhiming; Xi, Xiangming; Wang, Shuning

来源：Digital Signal Processing, 2016, 54: 12-26.

DOI：10.1016/j.dsp.2016.03.010

• Compressed sensing
• Continuous piecewise linear programming
• Global optimization
• gamma valid cut

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 l(0) norm minimization. In this paper, CS has been considered from a new perspective. We equivalently transform the l(0) 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 gamma 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.

• 出版日期2016-7
• 单位中国人民解放军空军工程大学; 清华大学