A null-space-based weighted ell_1 minimization approach to compressed sensing

摘要

It has become an established fact that the constrained $ell_1$ minimization is capable of recovering thesparse solution from a small number of linear observations and the reweighted version can significantly improve its numerical performance.The recoverability is closely related to the Restricted Isometry Constant (RIC) {of order $s$ ($s$ is an integer), often denoted as $delta_{s}$.A class of sufficient conditions for successful $k$-sparse signal recovery often take the form $delta_{tk} c$, for some $t ge 1$ and $c$ being a constant. When $t 1$, such a bound is often called RIC bound of high order.}There exist a number of such bounds of RICs, high order or not.For example, a high order bound {is recently given by Cai and Zhang cite{CZ14}:} $delta_{tk} sqrt{(t-1)/t}$, and this bound is known sharp for $t ge 4/3$.In this paper, we propose a new weighted $ell_1$ minimization which only requires the following RIC bound that is more relaxed (i.e., bigger) than the above mentioned bound:[delta_{tk} sqrt{rac {t-1}{t -(1-omega^2)}},]where $t 1$ and $0 omega le 1$ is determined {by two optimizations of a similar type}over the null space of the linear observation operator.{In tackling the combinatorial nature of the two optimization problems,we develop a reweighted $ell_1$ minimization that yields a sequence of approximate solutions,which enjoy strong convergence properties. Moreover, the numerical performance of the proposed method}is very satisfactory when compared to some of the state of-the-art methods incompressed sensing.