  This paper studies the problem of recovering a signal vector and the
corrupted noise vector from a collection of corrupted linear measurements
through the solution of a l1 minimization, where the sensing matrix is a
partial Fourier matrix whose rows are selected randomly and uniformly from rows
of a full Fourier matrix. After choosing the parameter in the l1 minimization
appropriately, we show that the recovery can be successful even when a constant
fraction of the measurements are arbitrarily corrupted, moreover, the
proportion of corrupted measurement can grows arbitrarily close to 1, provided
that the signal vector is sparse enough. The upper-bound on the sparsity of the
signal vector required in this paper is asymptotically optimal and is better
than those achieved by recent literatures [1, 2] by a ln(n) factor.
Furthermore, the assumptions we impose on the signal vector and the corrupted
noise vector are loosest comparing to the existing literatures [1-3], which
lenders our recovery guarantees are more applicable. Extensive numerical
experiments based on synthesis as well as real world data are presented to
verify the conclusion of the proposed theorem and to demonstrate the potential
of the l1 minimization framework.
