Sparsest Error Detection via Sparsity Invariant Transformation based $ell_1$ Minimization

This paper presents a new method, referred to here as the sparsity invariant transformation based $ell_1$ minimization, to solve the $ell_0$ minimization problem for an over-determined linear system corrupted by additive sparse errors with arbitrary intensity. Many previous works have shown that $ell_1$ minimization can be applied to realize sparse error detection in many over-determined linear systems. However, performance of this approach is strongly dependent on the structure of the measurement matrix, which limits application possibility in practical problems. Here, we present a new approach based on transforming the $ell_0$ minimization problem by a linear transformation that keeps sparsest solutions invariant. We call such a property a sparsity invariant property (SIP), and a linear transformation with SIP is referred to as a sparsity invariant transformation (SIT). We propose the SIT-based $ell_1$ minimization method by using an SIT in conjunction with $ell_1$ relaxation on the $ell_0$ minimization problem. We prove that for any over-determined linear system, there always exists a specific class of SITs that guarantees a solution to the SIT-based $ell_1$ minimization is a sparsest-errors solution. Besides, a randomized algorithm based on Monte Carlo simulation is proposed to search for a feasible SIT.

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.