Identifying bad measurements in compressive sensing

Abstract

We consider the problem of identifying bad measurements in compressive sensing. These bad measurements can be present due to malicious attacks and system malfunction. Since the system of linear equations in compressive sensing is underconstrained, errors introduced by these bad measurements can result in large changes in decoded solutions. We describe methods for identifying bad measurements so that they can be removed before decoding. In a new separation-based method we separate out top nonzero variables by ranking, eliminate the remaining variables from the system of equations, and then solve the reduced overconstrained problem to identify bad measurements. Comparing to prior methods based on direct or joint l1-minimization, the separation-based method can work under a much smaller number of measurements. In analyzing the method we introduce the notion of inversions which governs the separability of large nonzero variables.