"A Piecewise Linear Programming Algorithm for Sparse Signal Reconstruct" by Kuangyu Liu, Xiangming Xi et al.

Article Title

A Piecewise Linear Programming Algorithm for Sparse Signal Reconstruction

Authors

Kuangyu Liu, Department of Automation, Tsinghua National Laboratory for Information Science and Technology (TNList), Tsinghua University, Beijing 100084, China.
Xiangming Xi, Department of Automation, Tsinghua National Laboratory for Information Science and Technology (TNList), Tsinghua University, Beijing 100084, China.
Zhiming Xu, College of Science, Air Force Engineering University, Xi’an 710051, and Department of Automation, Tsinghua University, Beijing 100084, China.
Shuning Wang, Department of Automation, Tsinghua National Laboratory for Information Science and Technology (TNList), Tsinghua University, Beijing 100084, China.

Keywords

compressed sensing, continuous piecewise linear programming, interior point method

Abstract

In order to recover a signal from its compressive measurements, the compressed sensing theory seeks the sparsest signal that agrees with the measurements, which is actually an l0 norm minimization problem. In this paper, we equivalently transform the l0 norm minimization into a concave continuous piecewise linear programming, and propose an optimization algorithm based on a modified interior point method. Numerical experiments demonstrate that our algorithm improves the sufficient number of measurements, relaxes the restrictions of the sensing matrix to some extent, and performs robustly in the noisy scenarios.

DOI

https://doi.org/10.1109/TST.2017.7830893

Publisher

Tsinghua University Press

Recommended Citation

Kuangyu Liu, Xiangming Xi, Zhiming Xu et al. A Piecewise Linear Programming Algorithm for Sparse Signal Reconstruction. Tsinghua Science and Technology 2017, 22(1): 29-41.

Download

Request a Copy

Included in

Computer Sciences Commons, Electrical and Computer Engineering Commons

COinS