  We study the problem of recovering an $s$-sparse signal
$\mathbf{x}^{\star}\in\mathbb{C}^n$ from corrupted measurements $\mathbf{y} =
\mathbf{A}\mathbf{x}^{\star}+\mathbf{z}^{\star}+\mathbf{w}$, where
$\mathbf{z}^{\star}\in\mathbb{C}^m$ is a $k$-sparse corruption vector whose
nonzero entries may be arbitrarily large and $\mathbf{w}\in\mathbb{C}^m$ is a
dense noise with bounded energy. The aim is to exactly and stably recover the
sparse signal with tractable optimization programs. In this paper, we prove the
uniform recovery guarantee of this problem for two classes of structured
sensing matrices. The first class can be expressed as the product of a
unit-norm tight frame (UTF), a random diagonal matrix and a bounded columnwise
orthonormal matrix (e.g., partial random circulant matrix). When the UTF is
bounded (i.e. $\mu(\mathbf{U})\sim1/\sqrt{m}$), we prove that with high
probability, one can recover an $s$-sparse signal exactly and stably by $l_1$
minimization programs even if the measurements are corrupted by a sparse
vector, provided $m = \mathcal{O}(s \log^2 s \log^2 n)$ and the sparsity level
$k$ of the corruption is a constant fraction of the total number of
measurements. The second class considers randomly sub-sampled orthogonal matrix
(e.g., random Fourier matrix). We prove the uniform recovery guarantee provided
that the corruption is sparse on certain sparsifying domain. Numerous
simulation results are also presented to verify and complement the theoretical
results.
