New Accumulative Score Function Based Bound For Sparsity Level of L1 Minimization

This paper discusses a fundamental problem in compressed sensing: the sparse recoverability of L1 minimization with an arbitrary sensing matrix. We develop an new accumulative score function (ASF) to provide a lower bound for the recoverable sparsity level (SL) of a sensing matrix while preserving a low computational complexity. We first define a score function for each row of a matrix, and then ASF sums up large scores until the total score reaches 0.5. Interestingly, the number of involved rows in the summation is a reliable lower bound of SL. It is further proved that ASF provides a sharper bound for SL than coherence We also investigate the underlying relationship between the new ASF and the classical RIC and achieve a RIC-based bound for SL.