We study the Compressed Sensing (CS) problem, which is the problem of finding
the most sparse vector that satisfies a set of linear measurements up to some
numerical tolerance. CS is a central problem in Statistics, Operations Research
and Machine Learning which arises in applications such as signal processing,
data compression and image reconstruction. We introduce an $\ell_2$ regularized
formulation of CS which we reformulate as a mixed integer second order cone
program. We derive a second order cone relaxation of this problem and show that
under mild conditions on the regularization parameter, the resulting relaxation
is equivalent to the well studied basis pursuit denoising problem. We present a
semidefinite relaxation that strengthens the second order cone relaxation and
develop a custom branch-and-bound algorithm that leverages our second order
cone relaxation to solve instances of CS to certifiable optimality. Our
numerical results show that our approach produces solutions that are on average
$6.22\%$ more sparse than solutions returned by state of the art benchmark
methods on synthetic data in minutes. On real world ECG data, for a given
$\ell_2$ reconstruction error our approach produces solutions that are on
average $9.95\%$ more sparse than benchmark methods, while for a given sparsity
level our approach produces solutions that have on average $10.77\%$ lower
reconstruction error than benchmark methods in minutes.

本文研究了压缩感知问题，提出了一种基于二阶锥的优化方法，该方法在证明一定正则参数条件下与基础凸优化问题等价的前提下，求解具有优良效果的稀疏向量，该方法相较于当前最优方法具有更高的稀疏性和更低的重构误差