Year: 2019

Abstract:
We provide recovery guarantees for compressible signals that have been corrupted with noise and extend the framework introduced in Bafna et al. (2018) to defend neural networks against `0, `2, and `∞-norm attacks. In the case of `0-norm noise, we provide recovery guarantees for Iterative Hard Thresholding (IHT) and Basis Pursuit (BP). For `2-norm bounded noise, we provide recovery guarantees for BP, and for the case of `∞-norm bounded noise, we provide recovery guarantees for a modified version of Dantzig Selector (DS). These guarantees theoretically bolster the defense framework introduced in Bafna et al. (2018) for defending neural networks against adversarial inputs. Finally, we experimentally demonstrate the effectiveness of this defense framework against an array of `0, `2 and `∞-norm attacks.

text: COMPRESSIVE RECOVERY DEFENSE: A DEFENSE FRAMEWORK FOR `0, `2, AND `∞ NORM ATTACKS.
Anonymous authors Paper under double-blind review

heading: 1 ABSTRACT
text: We provide recovery guarantees for compressible signals that have been corrupted with noise and extend the framework introduced in Bafna et al. (2018) to defend neural networks against `0, `2, and `∞-norm attacks. In the case of `0-norm noise, we provide recovery guarantees for Iterative Hard Thresholding (IHT) and Basis Pursuit (BP). For `2-norm bounded noise, we provide recovery guarantees for BP, and for the case of `∞-norm bounded noise, we provide recovery guarantees for a modified version of Dantzig Selector (DS). These guarantees theoretically bolster the defense framework introduced in Bafna et al. (2018) for defending neural networks against adversarial inputs. Finally, we experimentally demonstrate the effectiveness of this defense framework against an array of `0, `2 and `∞-norm attacks.

heading: 2 INTRODUCTION
text: Signal measurements are often corrupted by noise. The theory of compressive sensing (Candes et al. (2006)) allows us to retrieve the original signal from a corrupted measurement, under some structural assumptions on the measurement mechanism and the signal. Let us consider the class of machine learning problems where the inputs are compressible (i.e., approximately sparse) in some domain. For instance, images and audio signals are known to be compressible in their frequency domain and machine learning algorithms have been shown to perform exceedingly well on classification tasks that take such signals as input (Krizhevsky et al. (2012); Sutskever et al. (2014)). However, it was found in Szegedy et al. (2013) that neural networks can be easily forced into making incorrect predictions by adding adversarial perturbations to their inputs; see also Szegedy et al. (2014); Goodfellow et al. (2015); Papernot et al. (2016); Carlini & Wagner (2017). Further, the adversarial perturbations that led to incorrect predictions were shown to be very small (in either `0, `2, or `∞-norm) and often imperceptible to human beings. For this class of machine learning tasks, we show how to approximately recover original inputs from adversarial inputs and thus defend the neural network `0-norm, `2-norm and `∞-norm attacks.
In the case of `0-norm attacks on neural networks, the adversary can perturb a bounded number of coordinates in the input vector but has no restriction on how much each coordinate is perturbed in absolute value. In the case of `2-norm attacks, the adversary can perturb as many coordinates of the input vector as they choose as long as the `2-norm of the perturbation vector is bounded. Finally, in `∞-norm attacks, the adversary is only constrained by the amount of noise added to each coordinate of the input vector.
The contribution and structure of this paper is as follows. In Section 3.1, we describe the Compressive Recovery Defense (CRD) framework, a compressive-sensing-based framework for defending neural networks against adversarial inputs. This is essentially the same framework introduced in Bafna et al. (2018), though Bafna et al. (2018) considered only `0 attacks. In Section 3.2, we present the recovery algorithms which are used in the CRD framework to approximately recover original inputs from adversarial inputs. These algorithms include standard Basis Pursuit (BP), (k, t)-sparse Iterative Hard Thresholding (IHT) and Dantzig Selector (DS) with an additional constraint. In Section 3.3, we state recovery guarantees for the recovery algorithms in the presence of noise bounded in either `0, `2, or `∞-norm. The guarantees apply to arbitrary `0, `2, and `∞-norm attacks; they do not require prior knowledge of the adversary’s attack strategy. The recovery guarantees are proved rigorously in Appendix A. In Section 4, we experimentally demonstrate the performance of
the CRD framework in defending neural network classifiers on CIFAR-10, MNIST, and FashionMNIST datasets against state-of-the-art `0, `2 and `∞-norm attacks.
Notation. Let x be a vector in CN . Let S ⊆ {1, . . . , N} and S = {1, . . . , N} \ S. The cardinality of S is |S|. If A ∈ Cm×N is a matrix, then AS ∈ Cm×|S| is the column submatrix of A consisting of the columns indexed by S. We denote by xS either the sub-vector in CS consisting of the entries indexed by S or the vector in CN that is formed by starting with x and setting the entries indexed by S to zero. For example, if x = [4, 5,−9, 1]T and S = {1, 3}, then xS is either [4,−9]T or [4, 0,−9, 0]T . It will always be clear from context which meaning is intended. Note that, under the second meaning, xS = x − xS . The support of x, denoted by supp(x), is the set of indices of the non-zero entries of x, i.e., supp(x) = {i ∈ {1, . . . , N} : xi 6= 0}. The `0-quasinorm of x, denoted ‖x‖0, is defined to be the number of non-zero entries of x, i.e. ‖x‖0 = card(supp(x)). We say that x is k-sparse if ‖x‖0 ≤ k. We use xh(k) to denote a k-sparse vector in CN consisting of the k largest (in absolute value) entries of x with all other entries zero. For example, if x = [4, 5,−9, 1]T then xh(2) = [0, 5,−9, 0]T . Note that xh(k) may not be uniquely defined. In contexts where a unique meaning for xh(k) is needed, we can choose xh(k) out of all possible candidates according to a predefined rule (such as the lexicographic order). We also define xt(k) = x− xh(k). If x = [x1, x2]T ∈ C2n with x1, x2 ∈ Cn, and if x1 is k-sparse and x2 is t-sparse, then x is called (k, t)-sparse. We define xh(k,t) = [(x1)h(k), (x2)h(t)]T , which is a (k, t)-sparse vector in C2n.

heading: 3 THEORY

heading: 3.1 COMPRESSIVE RECOVERY DEFENSE (CRD)
text: Bafna et al. (2018) introduced a framework for defending machine learning classifiers against `0- attacks. We extend the framework to `2 and `∞ attacks. The defense framework is based on the theory of compressive sensing, so we call it Compressive Recovery Defense (CRD).
We explain the idea behind the CRD framework in the context of an image classifier. Suppose x ∈ Cn is a (flattened) image vector we wish to classify. But suppose an adversary perturbs x with a noise vector e ∈ Cn. We observe y = x + e, while x and e are unknown to us. Let F ∈ Cn×n be the Discrete Fourier Transform (DFT) matrix. The Fourier coefficients of x are x̂ = Fx. It is well-known that natural images are approximately sparse in the frequency domain. So we expect that x̂ is approximately sparse, meaning that x̂t(k) is small for some small k. We can write y = F−1x̂+ e (1) If ‖e‖2 ≤ η or ‖e‖∞ ≤ η, with η small (as in a `2 or `∞-attack), then we can use an appropriate sparse recovery algorithm with y and F−1 as input to compute a good approximation x# to x̂. Precise error bounds are given in Section 3.3. Then, since F is unitary, F−1x# will be a good approximation (i.e., reconstruction) of x = F−1x̂. So we can feed F−1x# into the classifier and expect to get the same classification as we would have for x. For an `0-attack where e is t-sparse, the approach is only slightly different. We set A = [F−1, I] and write
y = F−1x̂+ e = F−1x̂h(k) + e+ F −1x̂t(k) = A[x̂h(k), e] T + F−1x̂t(k), (2)
so that [x̂h(k), e]T is (k, t)-sparse. This structure lets us use a sparse recovery algorithm to compute a good approximation to x̂, as before. Note that the same idea can be applied with audio signals or other types of data instead of images. Moreover, the DFT can be replaced by any unitary transformation F for which x̂ = Fx is approximately sparse. For example, F may be the Cosine Transform, Sine Transform, Hadamard Transform, or another wavelet transform.
We now describe the training and testing procedure for CRD. For each training image x, we compute x̂h(k) = (Fx)h(k), and then compute the compressed the image x′ = F−1x̂h(k). We then add both x and x′ to the training set and train the network in the usual way. Given a (potentially adversarial) test image y, we first use a sparse recovery algorithm to compute an approximation x# to x̂, then we compute the reconstructed image y′ = F−1x# and feed it into the network for classification.

heading: 3.2 RECOVERY ALGORITHMS
text: We provide the recovery algorithms used in this section. For `0-attacks, we set A = [F−1, I] as in (2). Against `2 or `∞-attacks, we take A = F−1 as in (1).
Algorithm 1: (k, t)-Sparse Iterative Hard Thresholding (IHT) Procedure: IHT (y,A, k, t, T ) Input: y ∈ Cn, A ∈ Cn×2n, and positive integers k, t, T . x[0] = 0 for i := 0 to T do
x[i+1] = ( x[i] +A∗(y −Ax[i]) ) h(k,t)
return x# = x[T+1]
The IHT algorithm above is used to defend against `0-norm attacks. For such attacks, according to (2), the vector we need to recover is (k, t)-sparse. Thus this IHT is adapted to the structure of our problem as it uses the thresholding operation h(k,t) that produces (k, t)-sparse vectors. This structured IHT was first considered in Baraniuk et al. (2010). It gives better theoretical guarantees and practical performance in our CRD application than the standard IHT, which would instead use the thresholding operation h(k+t) that produces (k + t)-sparse vectors. For `2 or `∞ attacks, the recovery error for IHT would (in general) be larger due to the need to include a term for the `2 norm of the tail of the noise vector e. This, in turn, produces worse expected performance of the recovery defense. Therefore we only use Algorithm 1 for `0-norm attacks. We note that the results of Theorem 1 allow for values of k and t greater than or equal to Theorem 2.2. of Bafna et al. (2018).
Algorithm 2: Basis Pursuit (BP). Procedure: BP (y,A, η). Input: y ∈ Cm, A ∈ Cm×N , and η ≥ 0. x# = argminz∈CN ‖z‖1 subject to‖Az − y‖2 ≤ η return x#
We utilize BP for `0 and `2 norm attacks. In the `0 norm case, BP allows us to provide recovery guarantees for larger values of k and t than IHT. For instance, in the case of MNIST and FashionMNIST, IHT (equation (4) of Theorem 1) allows us to set k = 4 and t = 3, whereas BP (equation (7) of Theorem 2) allows us to set k = 8 and t = 8.
In the case of `2 norm attacks, BP is applied withA = F−1, a unitary matrix. As unitary matrices are isometries in `2 norm, BP provides good recovery guarantees for such matrices, and hence against `2 norm attacks.
Algorithm 3: Modified Dantzig Selector (DS). Procedure: DS(y,A, η). Input: y ∈ Cm, A ∈ Cm×N , and η ≥ 0. x# = argminz∈CN ‖z‖1 subject to ‖A∗(Az − y)‖∞ ≤ √ nη, ‖Az − y‖∞ ≤ η return x#
We utilize DS for `∞ norm attacks. The standard Dantzig Selector algorithm does not have the additional constraint ‖Az − y‖∞ ≤ η. Our modified Dantzig Selector includes this constraint for the following reason. In our application, A = F−1 and we want the reconstruction Ax# = F−1x# to be close to the original image x, so that they are classified identically. Thus, we want to the search space for x# to be restricted to those z ∈ CN such that ‖Az−x‖∞ is small. Note, for any z ∈ CN , ‖Az − x‖∞ ≤ ‖Az − y‖∞ + ‖x − y‖∞. In an `∞-attack, ‖x − y‖∞ = ‖e‖∞ is already small. Thus it suffices to require ‖Az − y‖∞ is small. We experimentally illustrate the improvement in reconstruction due to the additional constraint in Section 4.3 (Figure 4, Table 4).
Remarks on Reverse-Engineered Attacks. As observed in Bafna et al. (2018), x[0] in Algorithm 1, can be initialized randomly to defend against a reverse-engineered attack. In the case of Algorithm 2 and Algorithm 3, the minimization problems can be posed as semi-definite programming problems. If solved with interior point methods, one can use random initialization of the central path parameter and add randomness to the stopping criterion. This makes recovery non-deterministic and consequently non-trivial to create a reverse-engineered attack.

heading: 3.3 RECOVERY GUARANTEES
text: LetF ∈ Cn×n be a unitary matrix and I ∈ Cn×n be the identity matrix. DefineA = [F, I] ∈ Cn×2n and let y = A[x̂, e]T = Fx̂+ e, where x̂, e ∈ Cn. Let 1 ≤ k, t ≤ n be integers.
Theorem 1 (`0-norm IHT). Assume |Fij |2 ≤ cn and e is t-sparse. Let x [T+1] = IHT (y,A, k, t, T ) where x[T+1] = [ x̂[T+1], e[T+1] ]T ∈ C2n with x̂[T+1], e[T+1] ∈ Cn. Define ρ := √ 27 √
ckt n , τ(1− ρ) :=
√ 3 √ 1 + 2 √ ckt n . If 0 < ρ < 1, then:
‖x̂[T+1] − x̂h(k)‖2 ≤ ρ(T+1) √ ‖x̂h(k)‖22 + ‖e‖22 + τ‖x̂t(k)‖2 (3)
Moreover for any 0 < < 1 and any T ≥ ( log(1/ )+log( √ ‖x̂h(k)‖22+‖e‖22)
log(1/ρ)
) , we get:
‖x̂[T+1] − x̂h(k)‖2 ≤ τ‖x̂t(k)‖2 + (4)
Now define ρ := 2 √ 2 √
ckt n , τ(1− ρ) := 2. If 0 < ρ < 1, then:
‖x̂[T+1] − x̂h(k)‖2 ≤ ρ(T+1)‖x̂h(k)‖2 + τ(‖x̂t(k)‖2 + ‖e‖2) (5) Moreover for any 0 < < 1 and any T ≥ (
log(1/ )+log(‖x̂h(k)‖2) log(1/ρ)
) , we get:
‖x̂[T+1] − x̂h(k)‖2 ≤ τ(‖x̂t(k)‖2 + ‖e‖2) + (6)
Let us explain how to interpret the recovery guarantees provided by Theorem 1. The inequalities (3), (4), (5), (6) provide an upper bound on the size of ‖x̂[T+1] − x̂h(k)‖2. Since F is a unitary matrix, ‖x̂[T+1] − x̂h(k)‖2 equals ‖Fx̂[T+1] − Fx̂h(k)‖2, which is the difference between the reconstructed image Fx̂[T+1] and the compressed image Fx̂h(k) (which is a compressed version of the original image x). So the inequalities of Theorem 1 tell us how close the reconstructed image must be to the compressed image, and thus indicates how confident we should be that the classification of the reconstructed image will agree with the classification of the compressed image. In other words, the inequalities tell us how likely it is that the CRD scheme using IHT will be able to recover the correct class of the original image, and thus defend the classifier from the adversarial attack. The presence of the norm of the tail x̂t(k) in the upper bounds indicates that the CRD scheme should be more effective when the original image is closer to being perfectly k-sparse in the transformed basis. The ratio kt/n in the upper bounds (via ρ and τ ) suggests that smaller values of k and t relative to n (i.e., sparser transformed images x̂ and error vectors e) will lead to the CRD being more effective. The experiments in Section 4 will demonstrate these phenomena.
Let us compare Theorem 1 to the similar Theorem 2.2 of Bafna et al. (2018). We observe that (3) and (4) allow larger values of k and t than Theorem 2.2 of Bafna et al. (2018). This is because the authors of Bafna et al. (2018) prove their results using Theorem 4 of Baraniuk et al. (2010), which is more restrictive for the values of k and t. We do not use Theorem 4 of Baraniuk et al. (2010). Instead we use (a modified form of) Theorem 6.18 of Foucart & Rauhut (2017) to get (3) and (4). Both Theorem 4 of Baraniuk et al. (2010) (used by Bafna et al. (2018)) and Theorem 6.18 of Foucart & Rauhut (2017) (used by us here) take as input the Restricted Isometry Property (RIP) stated in Theorem 7. We and Bafna et al. (2018) both essentially prove the same RIP, although the proof methods are different. We use a standard Gershgorin disc theorem argument to bound eigenvalues, while Bafna et al. (2018) perform a direct estimation using the triangle inequality and AM-GM inequality.
We turn now to (5) and (6), which provide recovery guarantees for larger values of k and t than (3) and (4), at the expense of the extra error term ‖e‖2. Our proof of (5) and (6) is novel. It relies on explicitly expanding one iteration of IHT in matrix form and using the structure of the resulting matrix form to bound the approximation error at iteration T in terms of the error at iteration T − 2. We then use an inductive argument as in Theorem 6.18 of Foucart & Rauhut (2017) to get (5) and (6).
Next, we consider the recovery error for `0-norm bounded noise with BP instead of IHT. We note that since Algorithm 2 is not adapted to the (k, t)-sparse structure of vector to be recovered, we do not expect the guarantees to be particularly strong. However, providing bounds for BP is useful as there are cases when BP provides recovery guarantees for when recovering a larger number of coefficients (k) and a larger `0 noise budget (t) than IHT.
Theorem 2 (`0-norm BP). Assume |Fij |2 ≤ cn . Define
δk,t =
√ ckt
n , β =
√ max{k, t}c
n , θ =
√ k + t
(1− δk,t) β, τ =
√ 1 + δk,t
1− δk,t
If 0 < δk,t < 1 and 0 < θ < 1, then for x# = BP(y,A, ‖x̂t(k)‖2), we have the error bound ‖x̂# − x̂h(k)‖2 ≤ ( 2τ √ k + t
1− θ
( 1 +
β
1− δk,t
) + 2τ ) ‖x̂t(k)‖2 (7)
where we write x# = [x̂#, e#]T ∈ C2n with x̂#, e# ∈ Cn.
Note that the recovery error in (7) is O(( √ k + t)‖x̂t(k)‖2), which means that we should not expect recovery to be close when the attacker has a large `0 noise budget or when x̂ is not sparse. Also observe that the recovered vector x̂# is not necessarily k-sparse. The recovery error still captures the difference in the original image Fx̂ and the reconstructed image Fx̂#, where a smaller recovery error should once again indicate that our classifier would make the correct prediction. Our third result covers the case when the noise is bounded in `2-norm. Theorem 3 (`2-norm BP). If ‖e‖2 ≤ η, then for x# = BP(y, F, η), we have the error bound
‖x# − x̂‖1 ≤ 2 ( ‖x̂t(k)‖1 + 2 √ kη )
(8)
‖x# − x̂‖2 ≤ 2√ k ‖x̂t(k)‖1 + 6η (9)
Finally, we provide recovery guarantees when the noise is bounded in `∞-norm. Theorem 4 (`∞-norm DS). If ‖e‖∞ ≤ η, then for x# = DS(y, F, η), we have the error bound
‖x# − x̂‖1 ≤ 2 ( ‖x̂t(k)‖1 + 2k √ nη )
(10)
‖x# − x̂‖2 ≤ 2√ k ‖x̂t(k)‖1 + 6
√ knη (11)
The proofs of Theorem 3 and Theorem 4 are based on standard arguments in compressive sensing that rely on establishing the so-called robust null space property of the matrix. Note that the results of Theorem 3 and Theorem 4 also bound the norm difference of the original image Fx̂ and the reconstructed image Fx̂#, where x̂# has no sparsity guarantees. Next, observe that the results of Theorem 4 incur a factor of √ n in the error bounds due to the constraint ‖A∗(Az − y)‖∞ ≤ √ nη in Algorithm 3 which is required to prove the robust null space property. Finally, we note that the additional constraint added to Algorithm 3 does not affect the proof of Theorem 4.

heading: 3.4 RELATED WORK
text: The authors of Bafna et al. (2018) introduced the CRD framework which inspired this work. In fact, Theorem 2.2 of Bafna et al. (2018) also provides an approximation error bound for recovery via IHT. Note that a hypothesis t = O(n/k) has accidentally been dropped from their Theorem 2.2, though it appears in their Lemma 3.6. By making the implied constants explicit in the argument of Bafna et al. (2018), one sees that their Theorem 2.2 is essentially the same as (3) and (4) in Theorem 1 above. For more details, see the proof of Theorem 1 in Appendix A. Note that our recovery error bounds for IHT in (5) and (6) of Theorem 1 do not have analogs in Bafna et al. (2018). They hold for larger values of k and t at the expense of the additional error term ‖e‖2. Other works that provide guarantees include (Hein & Andriushchenko (2017)) and (Cisse et al. (2017)) where the authors frame the problem as one of regularizing the Lipschitz constant of a network and give a lower bound on the norm of the perturbation required to change the classifier decision. The authors of Sinha et al. (2017) use robust optimization to perturb the training data and provide a training procedure that updates parameters based on worst case perturbations. A similar approach to (Sinha et al. (2017)) is (Wong & Kolter (2017)) in which the authors use robust optimization to provide lower bounds on the norm of adversarial perturbations on the training data.
In Lecuyer et al. (2018), the authors use techniques from Differential Privacy (Dwork et al. (2014))in order to augment the training procedure of the classifier to improve robustness to adversarial inputs. Another approach using randomization is Li et al. (2018) in which the authors add i.i.d. Gaussian noise to the input and provide guarantees of maintaining classifier predictions as long as the `2-norm of the attack vector is bounded by a function that depends on the output of the classifier.
Most defenses against adversarial inputs do not come with theoretical guarantees. Instead, a large body of research has focused on finding practical ways to improve robustness to adversarial inputs by either augmenting the training data (Goodfellow et al. (2015)), using adversarial inputs from various networks (Tramèr et al. (2017)), or by reducing the dimensionality of the input (Xu et al. (2017)). For instance, Madry et al. (2017) use robust optimization to make the network robust to worst case adversarial perturbations on the training data. However, the effectiveness of their approach is determined by the amount and quality of training data available and its similarity to the distribution of the test data. An approach similar to ours but without any theoretical guarantees is (Samangouei et al. (2018)). In this work, the authors use Generative Adversarial Networks (GANs) to estimate the distribution of the training data and during inference, use a GAN to reconstruct a non-adversarial input that is most similar to a given test input. We now provide a brief overview on the field of compressive sensing.
Though some component ideas originated earlier in other fields, the field of compressive sensing was initiated with the work of Candès et al. (2006) and Donoho et al. (2006) in which the authors studied the problem of reconstructing sparse signals using only a small number of measurements with the choice of a random matrix. The reconstruction was performed using `1-minimization (i.e., Basis Pursuit) which was shown to produce sparse solutions even in presence of noise; see also Donoho & Elad (2003; 2006); Donoho & Huo (2001). Some of the earlier work in extending compressive sensing to perform stable recovery with deterministic matrices was done by Candes & Tao (2005) and Candes et al. (2006), where the authors showed that recovery of sparse vectors could be performed as long as the measurement matrix satisfied a restricted isometry hypothesis. Blumensath & Davies (2009) introduced IHT as an algorithm to recover sparse signals which was later modified in Baraniuk et al. (2010) to reduce the search space as long as the sparsity was structured. The standard DS algorithm was introduced in Candes et al. (2007) in order to perform stable recovery in the presence of `∞ noise.

heading: 4 EXPERIMENTS
text: All of our experiments are conducted on CIFAR-10 (Krizhevsky (2009)), MNIST (LeCun), and Fashion-MNIST (Xiao et al. (2017)) datasets with pixel values of each image normalized to lie in [0, 1]. Each experiment is conducted on a set of 1000 points sampled uniformly at random from the test set of the respective dataset. For every experiment, we use the Discrete Cosine Transform (DCT) and the Inverse Discrete Cosine Transform (IDCT) denoted by the matrices F ∈ Rn×n and FT ∈ Rn×n respectively. That is, for an adversarial image y ∈ R √ n× √ n, such that, y = x+e, we let x̂ = Fx, and x = FT x̂, where x, x̂ ∈ Rn and e ∈ Rn is the noise vector. For an adversarial image y ∈ R √ n× √ n×c, that contains c channels, we perform recovery on each channel independently by considering ym = xm + em, where x̂m = Fxm, xm = FT x̂m for m = 1, . . . , c. The value k denotes the number of largest (in absolute value) DCT coefficients used for reconstruction of each channel, and the value t denotes the `0 noise budget for each channel. We implement Algorithm 2 and Algorithm 3 using the open source library CVXPY (Diamond & Boyd (2016)).
We now outline the neural network architectures used for experiments in Section 4.1 and 4.2. For CIFAR-10, we use the network architecture of He et al. (2016) while the network architecture for MNIST and Fashion-MNIST datasets is provided in Table 5 of the Appendix. We train our networks using the Adam optimizer for CIFAR-10 and the AdaDelta optimizer for MNIST and FashionMNIST. In both cases, we use a cross-entropy loss function. We train the each neural network according to the CRD framework stated in Section 3.1. The code to reproduce our experiments is available here: https://github.com/anonymousiclrcompressive/iclr2020.

heading: 77.4% 0.0% 71.8%
text: 4.1 DEFENSE AGAINST `0-NORM ATTACKS
This section is organized as follows: first we examine CRD against the One Pixel Attack (OPA) (Su et al. (2019)) for CIFAR-10. We only test the attack on CIFAR-10 as it is most effective against natural images and does not work well on MNIST or FASHION-MNIST. We note that this attack satisfies the theoretical constraints for t provided in Theorem 1, hence allowing us to test how well CRD works within existing guarantees. Once we establish the effectiveness of CRD against OPA, we then test it against two other `0-norm bounded attacks: Carlini and Wagner (CW) `0-norm attack (Carlini & Wagner (2017)) and the Jacobian based Saliency Map Attack (JSMA) (Papernot et al. (2016)).

heading: 4.1.1 ONE PIXEL ATTACK
text: We first resize all CIFAR-10 images to 125 × 125 × 3 while maintaining aspect ratios to ensure that the data falls under the hypotheses of Theorem 1 even for large values of k. The OPA attack perturbs exactly one pixel of the image, leading to an `0 noise budget of t = 3 per image. The `0 noise budget of t = 3 per image allows us to use k = 275 per channel. Table 1 shows that OPA is very effective against natural images and forces the network to mis-classify all previously correctly classified inputs.
We test the performance of CRD in two ways: a) reconstruction quality b) network performance on reconstructed images. In order to analyse the reconstruction quality of Algorithm 1, we do the following: for each test image, we use OPA to perturb the image and then use Algorithm 1 to approximate its largest (in absolute value) k = 275 DCT co-efficients. We then perform the IDCT on these recovered co-efficients to generate reconstructed images. We illustrate reconstruction on a randomly selected image from the test set in Figure 1.
Noting that Algorithm 1 leads to high quality reconstruction, we now test whether network accuracy improves on these reconstructed images. To do so, we feed these reconstructed images as input to the network and report its accuracy in Table 1. We note that network performance does indeed improve as network accuracy goes from 0.0% to 71.8% using Algorithm 1. Therefore, we conclude that CRD provides a substantial improvement in accuracy in against OPA.
4.1.2 CW-`0 ATTACK AND JSMA
Having established the effectiveness of CRD against OPA, we move onto the CW `0-norm attack and JSMA. We note that even when t is much larger than the hypotheses of Theorem 1 and Theorem 2, we find that Algorithms 1 and 2 are still able to defend the network. We hypothesize that this maybe related to the behavior of the RIP of a matrix for “most” vectors as opposed to the RIP for all vectors, and leave a more rigorous analysis for a follow up work.
We follow the procedure described in Section 4.1.1 to analyze the quality of reconstructions for Algorithm 1 and Algorithm 2 in Fig 2. In each case it can be seen that both algorithms provide high quality reconstructions for values of t that are well outside the hypotheses required by Theorem 1 and Theorem 2. We report these t values and the improvement in network performance on reconstructed adversarial images using CRD in Table 2.
4.2 DEFENSE AGAINST `2-NORM ATTACKS
In the case of `2-norm bounded attacks, we use the CW `2-norm attack (Carlini & Wagner (2017)) and the Deepfool attack (Moosavi-Dezfooli et al. (2016)) as they have been shown to be the most powerful. We note that Theorem 3 does not impose any restrictions on k or t and therefore the guarantees of equations (8) and (9) are applicable for recovery in all experiments of this section.
The reconstruction quality is shown in Figure 3. It can be noted that reconstruction using Algorithm 2 is of high quality for all three datasets. In order to check whether this high quality reconstruction also leads to improved performance in network accuracy, we test each network on reconstructed images using Algorithm 2. We report the results in Table 3 and note that Algorithm 2 provides a substantial improvement in network accuracy for each dataset and each attack method used.

heading: 4.3 DEFENSE AGAINST `∞-NORM ATTACKS
text: For `∞-norm bounded attacks, we use the BIM attack (Kurakin et al. (2016)) as it is has been shown to be very effective and also allows us to control the `∞-norm of the attack vector explicitly. We note that while the CW `∞-norm attack (Carlini & Wagner (2017)) has the ability to create attack vectors with `∞-norm less than or equal to BIM, it is computationally expensive and also does not allow one to pre-specify a value for the `∞-norm of an attack vector. Therefore, we limit our experimental analysis to the BIM attack. Note that for any attack vector e, ‖e‖2 ≤ √ n‖e‖∞ hence allowing `∞- norm attacks to create attack vectors with large `2-norm. Therefore, we could expect reconstruction quality and network accuracy to be lower when compared to `2-norm attacks.
In figure 4, we compare the reconstruction quality of images reconstructed with Algorithm 3 to those reconstructed using DS without the additional constraint. As can be noted from the figure, images reconstructed using DS without the additional constraint may not produce meaningful images. This is also reflected in Table 4, which shows that the accuracy of the network is roughly random on images reconstructed without the additional constraint.
We show examples of original images, adversarial images, and their reconstructions using Algorithm 3 in Figure 5. Finally, we report the network performance on reconstructed inputs using Algorithm 3 in Table 4 and also compare this to the performance on inputs reconstructed using DS without the additional constraint. We note that Algorithm 3 provides an increase in network performance against reconstructed adversarial inputs. However, the improvement in performance is not as substantial as it was against `0 or `2-norm attacks.

heading: 5 CONCLUSION
text: We provided recovery guarantees for corrupted signals in the case of `0-norm, `2-norm, and `∞- norm bounded noise. We were able to utilize these results in CRD and improve the performance of neural networks substantially in the case of `0-norm, `2-norm and `∞-norm bounded noise. While `0-norm attacks don’t always satisfy the constraints required by Theorem 1 and Theorem 2, we showed that CRD is still able to provide a good defense for values of t much larger than allowed in the guarantees. The guarantees of Theorem 3 and Theorem 4 were applicable in all experiments and CRD was shown to improve network performance for all attacks.

heading: A APPENDIX
text: A.1 RESTRICTED ISOMETRY PROPERTY
We first establish the restricted isometry property for certain structured matrices. First, we give some definitions.
Definition 5. Let A be a matrix in Cm×N , let M ⊆ CN , and let δ ≥ 0. We say that A satisfies the M -restricted isometry property (or M-RIP) with constant δ if
(1− δ)‖x‖22 ≤ ‖Ax‖22 ≤ (1 + δ)‖x‖22 for all x ∈M . Definition 6. We define Mk to be the set of all k-sparse vectors in CN and similarly define Mk,t to be the set of (k, t)-sparse vectors in C2n. In other words, Mk,t is the following subset of C2n:
Mk,t = { x = [x1 x2] T ∈ C2n : x1 ∈ Cn, x2 ∈ Cn, ‖x1‖0 ≤ k, ‖x2‖0 ≤ t }
We define Sk,t to be the following collection of subsets of {1, . . . , 2n}:
Sk,t = {S1 ∪ S2 : S1 ⊆ {1, . . . , n} , S2 ⊆ {n+ 1, . . . , 2n} , card(S1) ≤ k, card(S2) ≤ t}
Note that Sk,t is the collection of supports of vectors in Mk,t.
Theorem 7. Let A = [F I] ∈ Cn×2n, where F ∈ Cn×n is a unitary matrix with |Fij |2 ≤ cn and I ∈ Cn×n is the identity matrix. Then(
1− √ ckt
n
) ‖x‖22 ≤ ‖Ax‖22 ≤ ( 1 + √ ckt
n
) ‖x‖22 (12)
for all x ∈Mk,t. In other words, A satisfies the Mk,t-RIP property with constant √ ckt
n .
Proof. In this proof, ifB denotes an matrix in Cn×n, then λ1(B), . . . , λn(B) denote the eigenvalues of B ordered so that |λ1(B)| ≤ · · · ≤ |λn(B)|. It suffices to fix an S = S1 ∪ S2 ∈ Sk,t and prove (12) for all non-zero x ∈ CS . SinceA∗SAS is normal, there is an orthonormal basis of eigenvectors u1, . . . , uk+t forA ∗ SAS , where
ui corresponds to the eigenvalue λi(A∗SAS). For any non-zero x ∈ CS , we have x = ∑k+t i=1 ciui for some ci ∈ C, so
‖Ax‖22 ‖x‖22 = 〈A∗SASx, x〉 〈x, x〉 =
∑k+t i=1 λi(A ∗ SAS)c
2 i∑k+t
i=1 c 2 i
. (13)
Thus it will suffice to prove that |λi(A∗SAS)− 1| ≤ √ ckt n for all i. Moreover,
|λi(A∗SAS)− 1| = |λi(A∗SAS − I)| = √ λi ((A∗SAS − I)∗(A∗SAS − I)) (14)
where the last equality holds because A∗SAS − I is normal. By combining (13) and (14), we see that (12) will hold upon showing that the eigenvalues of (A∗SAS − I)∗(A∗SAS − I) are bounded by ckt/n.
So far we have not used the structure ofA, but now we must. Observe that (A∗SAS−I)∗(A∗SAS−I) is a block diagonal matrix with two diagonal blocks of the formX∗X andXX∗. Therefore the three matrices (A∗SAS−I)∗(A∗SAS−I),X∗X , andXX∗ have the same non-zero eigenvalues. Moreover, X is simply the matrix FS1 with those rows not indexed by S2 deleted. The hypotheses on F imply that the entries of X∗X satisfy |(X∗X)ij | ≤ ctn . So the Gershgorin disc theorem implies that each eigenvalue λ of X∗X and (hence) of (A∗SAS − I)∗(A∗SAS − I) satisfies |λ| ≤ cktn .
A.2 ITERATIVE HARD THRESHOLDING
First we present Theorem 8 and then use it to prove Theorem 1.
Theorem 8. Let A ∈ Cn×2n be a matrix. Let 1 ≤ k, t ≤ n be positive integers and suppose δ3 is a M3k,3t-RIP constant for A and that δ2 is a M2k,2t-RIP constant for A. Let x ∈ C2n, r ∈ Cn, y = Ax + r, and S ∈ Sk,t. Letting x[T+1] = IHT (y,A, k, t, T ), if δ3 < 1/ √ 3, then we have the approximation error bound
‖x[T+1] − xS‖2 ≤ ρ(T+1)‖x[0] − xS‖2 + τ‖AxS + r‖2
where ρ := √ 3δ3 < 1 and (1− ρ)τ = √ 3 √ 1 + δ2 ≤ 2.18. Thus, the first term on the right goes to 0 as T goes to∞.
Theorem 8 is a modification of Theorem 6.18 of Foucart & Rauhut (2017). More specifically, Theorem 6.18 of Foucart & Rauhut (2017) considers M3k, M2k, and Sk in place of M3k,3t and M2k,2t and Sk,t and any dimension N in place of 2n. The proofs are very similar, so we omit the proof of Theorem 8. We will now prove a lemma that will be required for the proof of Theorem 1. For the proof of Lemma 9 and Theorem 1, we use the following convention: let A ∈ Cm×N be a matrix, then, we denote by (A)S , the m×N matrix that is obtained by starting with A and zeroing out the columns indexed by S. Note that (A)S = A− (A)S . Lemma 9. Let F ∈ Cn×n be a unitary matrix with |Fij |2 ≤ cn and let S ⊆ [n] be a index set with |S| = t. Then for any k-sparse vector z ∈ Cn, we have:
‖(F ∗)SFz‖22 ≤ ktc
n ‖z‖22
Proof of Lemma 9. First note that (F ∗)S ∈ Cn×n contains only t non-zero columns since |S| = t Therefore, we have |((F ∗)SF )ij | ≤ tcn since |Fij |
2 ≤ cn . Further, since the non-zero columns of (F ∗)S are orthogonal to each other, we get ((F ∗)S)∗(F ∗)S = (I)S , where I ∈ Cn×n is the identity matrix. Using this, we have for any w ∈ Cn,
‖(F ∗)SFw‖22 = 〈(F ∗)SFw, (F ∗)SFw〉 = 〈((F ∗)SF )∗(F ∗)SFw,w〉 = 〈(F ∗)SFw,w〉 = | 〈(F ∗)SFw,w〉 |
Now let V ⊆ [n] be any index set with cardinality k, that is |V | = k and let z ∈ Cn be any vector supported on V . We then get,
‖(F ∗)SFz‖22 = |〈(F ∗)SFz, z〉| = ∣∣∣∣∣∣ ∑ k∈V z∗k ∑ j∈V ((F ∗)SF )kjzj ∣∣∣∣∣∣ ≤ ∑ k∈V |z∗k| ∑ j∈V |((F ∗)SF )kj ||zj |  ≤ ∑ k∈V |z∗k|  tc n ∑ j∈V |zj |
 = tc
n ‖z‖21 ≤
ktc
n ‖z‖22
where we use the fact that z is k-sparse for the last inequality.
Now we provide the proof for Theorem 1.
Proof of Theorem 1. Theorem 7 implies that the statement of Theorem 8 holds with δ3 = √ c·3k·3t n and δ2 = √ c·2k·2t n . Noting that y = A[x̂h(k) e]
T + Fx̂t(k), where [x̂h(k) e]T ∈ Mk,t, set x[T+1] = IHT (y,A, k, t, T ) and apply Theorem 8 with x = [x̂h(k) e]T , r = Fx̂t(k), and S = supp(x). Letting x[T+1] = [x̂[T+1] e[T+1]]T , use the facts that ‖x̂[T+1]− x̂h(k)‖2 ≤ ‖x[T+1]−
xS‖2 and ‖Fx̂t(k)‖2 = ‖x̂t(k)‖2. That will give (3). Letting T = ( log(1/ )+log( √ ‖x̂h(k)‖22+‖e‖22)
log(1/ρ)
) ,
gives ρT √ ‖x̂h(k)‖22 + ‖e‖22 ≤ , which can be substituted in (3) to get (4). Noting that ||e[T ]−e||2 ≤ τ ||x̂t(k)||2 + , we can use the same reasoning as used in Bafna et al. (2018) to get:
‖x̂[T+1] − x̂h(k)‖∞ ≤ √ 2ct
n
( τ‖x̂t(k)‖2 + ) (15)
‖x̂[T+1] − x̂h(k)‖2 ≤ √ 4ckt
n
( τ‖x̂t(k)‖2 + ) (16)
which are the essentially the same as the results of Theorem 2.2 in Bafna et al. (2018).
Now we prove (5). Write x[T ] = (z[T ])h(k,t), where z[T ] = x[T−1] + A∗(y − Ax[T−1]). Further, write z[T ] = [z[T ]1 z [T ] 2 ] T ∈ C2n, where z[T ]1 , z [T ] 2 ∈ Cn. Note that x̂[T ] = (z [T ] 1 )h(k). Therefore, we have z[T ]1 = F ∗(y − e[T−1]), where e[T−1] = (y − Fx̂[T−2])h(t). Now let S be the set of indices selected by the hard thresholding operation h(t) to get e[T−1]. Then observe that z[T ]1 = F ∗(y− (y−Fx̂[T−2])S). Next, note that ‖z[T ]1 − x̂[T ]‖22 ≤ ‖z [T ] 1 − x̂h(k)‖22 as x̂[T ] is a best k-sparse approximation to z[T ]1 . We can thus write,
‖(z[T ]1 − x̂h(k))− (x̂[T ] − x̂h(k))‖22 = ‖z [T ] 1 − x̂h(k)‖22 − 2Re〈z [T ] 1 − x̂h(k), x̂[T ] − x̂h(k)〉+ ‖x̂[T ] − x̂h(k)‖22
Therefore, we have,
‖x̂[T ] − x̂h(k)‖22 ≤ 2Re〈z [T ] 1 − x̂h(k), x̂[T ] − x̂h(k)〉
≤ 2|〈z[T ]1 − x̂h(k), x̂[T ] − x̂h(k)〉|
≤ 2‖z[T ]1 − x̂h(k)‖2‖x̂[T ] − x̂h(k)‖2
If ‖x̂[T ] − x̂h(k)‖2 > 0, then ‖x̂[T ] − x̂h(k)‖2 ≤ 2‖z [T ] 1 − x̂h(k)‖2. Now note that
z [T ] 1 = x̂+ F ∗e− F ∗(F (x̂− x̂[T−2]) + e)S = x̂+ F ∗e− (F ∗)S(F (x̂− x̂[T−2]) + e) = x̂+ (F ∗ − (F ∗)S)e− (F ∗)SF (x̂− x̂[T−2])
Using the fact that (F ∗)S = F ∗ − (F ∗)S , we can simplify the above to get:
‖z[T ]1 − x̂h(k)‖2 = ‖(F ∗)SFx̂t(k) + (F ∗)Se− (F ∗)SF (x̂h(k) − x̂[T−2])‖2 Therefore,
‖x̂[T ] − x̂h(k)‖2 ≤ 2 ( ‖(F ∗)SF‖2→2‖x̂t(k)‖2 + ‖(F ∗)S‖2→2‖e‖2 + ‖(F ∗)SF (x̂h(k) − x̂[T−2])‖2 ) ≤ 2 ( ‖x̂t(k)‖2 + ‖e‖2 ) + 2‖(F ∗)SF (x̂h(k) − x̂[T−2])‖2
where we use ‖(F ∗)S‖2→2 ≤ ‖F ∗‖2→2 = 1. Now since x̂h(k) − x̂[T−2] is 2k-sparse, we can use the result of Lemma 9 to get:
‖x̂[T ] − x̂h(k)‖2 ≤ 2 ( ‖x̂t(k)‖2 + ‖e‖2 ) + 2
(√ 2ktc
n
) ‖x̂[T−2] − x̂h(k)‖2
Now let ρ = 2 √ 2 √
ktc n , τ(1− ρ) = 2 and note that if ρ < 1, we can use induction on T to get (5). Then for any 0 < < 1 and any T ≥ (
log(1/ )+log(‖x̂h(k)‖2) log(1/ρ) ) , we have ρT (‖x̂h(k)‖2) ≤ which
gives us (6).
A.3 BASIS PURSUIT
Definition 10. The matrix A ∈ Cm×N satisfies the robust null space property with constants 0 < ρ < 1, τ > 0 and norm ‖ · ‖ if for every set S ⊆ [N ] with card(S) ≤ s and for every v ∈ CN we have ‖vS‖1 ≤ ρ‖vS‖1 + τ‖Av‖ Definition 11. The matrix A ∈ Cm×N satisfies the `q robust null space property of order s with constants 0 < ρ < 1, τ > 0 and norm ‖ · ‖ if for every set S ⊆ [N ] with card(S) ≤ s and for every v ∈ CN we have
‖vS‖q ≤ 1
s1−1/q ρ‖vS‖1 + τ‖Av‖
Note that if q = 1 then this is simply the robust null space property.
The proof of Theorem 2 requires the following theorem (whose full proof is given in the Foucart & Rauhut (2017)). Theorem 12 (Theorem 4.33 in Foucart & Rauhut (2017)). Let a1, . . . , aN be the columns of A ∈ Cm×N , let x ∈ CN with s largest absolute entries supported on S, and let y = Ax + e with ‖e‖2 ≤ η. For δ, β, γ, θ, τ ≥ 0 with δ < 1, assume that:
‖A∗SAS − I‖2→2 ≤ δ, max l∈S ‖A∗Sal‖2 ≤ β,
and that there exists a vector u = A∗h ∈ CN with h ∈ Cm such that ‖uS − sgn(xS)‖2 ≤ γ, ‖uS‖∞ ≤ θ, and ‖h‖2 ≤ τ √ s.

heading: If ρ := θ + βγ(1−δ) < 1, then a minimizer x
text: # of ‖z‖1 subject to ‖Az − y‖2 ≤ η satisfies:
‖x# − x‖2 ≤ 2
(1− ρ)
( 1 +
β
(1− δ)
) ‖xS‖1 + ( 2(µγ + τ √ s)
1− ρ
( 1 + β
1− δ
) + 2µ ) η
where µ := √
1+δ 1−δ and sgn(x)i =  0, xi = 0 1, xi > 0
−1. xi < 0 .
Lemma 13. LetA ∈ Cn×2n, if ‖Ax‖22 ≤ (1+δ)‖x‖22 for all x ∈Mk,t, then, ‖A∗SAS−I‖2→2 ≤ δ, for any S ∈ Sk,t.
Proof. Let S ∈ Sk,t be given. Then for any x ∈ CS , we have
‖ASx‖22 − ‖x‖22 ≤ δ‖x‖22 We can re-write this as : ‖ASx‖22 − ‖x‖22 = 〈ASx,ASx〉 − 〈x, x〉 = 〈(A∗SAS − I)x, x〉. Noting that A∗SAS − I is Hermitian, we have:
‖A∗SAS − I‖2→2 = max x∈CS\{0} 〈(A∗SAS − I)x, x〉 ‖x‖22 ≤ δ
Proof of Theorem 2. We will derive (7) by showing that the matrix A satisfies all the hypotheses in Theorem 12 for every vector in Mk,t.
First note that by Theorem 7,A satisfies theMk,t-RIP property with constant δk,t := √ ckt n . Therefore, by Lemma 13, for any S ∈ Sk,t, we have ‖A∗SAS − I‖2→2 ≤ δk,t. Since A∗SAS is a positive semi-definite matrix, it has only non-negative eigenvalues that lie in the range [1 − δk,t, 1 + δk,t]. Since δk,t < 1 by assumption, A∗SAS is injective. Thus, we can set: h = AS(A ∗ SAS)
−1sgn(xS) and get:
‖h‖2 = ‖AS(A∗SAS)−1sgn(xS)‖2 ≤ ‖AS‖2→2‖(A∗SAS)−1‖2→2‖sgn(xS)‖2 ≤ τ √ k + t
where τ = √
1+δk,t 1−δk,t and we have used the following facts: since ‖A ∗ SAS − I‖2→2 ≤ δk,t < 1, we get that ‖(A∗SAS)−1‖2→2 ≤ 11−δk,t and that the largest singular value of AS is less than √ 1 + δk,t. Now let u = A∗h, then ‖uS − sgn(xS)‖2 = 0. Now we need to bound the value ‖uS‖∞. Denoting row j of A∗
S AS by the vector vj , we see that it has at most max{k, t} non-zero entries and that
|(vj)l|2 ≤ cn for l = 1, . . . , (k + t). Therefore, for any element (uS)j , we have:
|(uS)j | = |〈(A ∗ SAS) −1sgn(xS), (vj)∗〉| ≤ ‖(A∗SAS)−1‖2→2‖sgn(xS)‖2‖vj‖2 ≤ √ k + t
1− δk,t
√ max{k, t}c
n Defining β := √
max{k,t}c n and θ :=
√ k+t
1−δk,t β, we get ‖uS‖∞ ≤ θ < 1 and also observe that maxl∈S ‖A∗Sal‖2 ≤ β. Therefore, all the hypotheses of Theorem 12 have been satisfied. Note that y = Fx̂+ e = A[x̂h(k) e]
T + Fx̂t(k), Therefore, setting x# = BP(y,A, ‖x̂t(k)‖2), we use the fact ‖Fx̂t(k)‖2 = ‖x̂t(k)‖2 combined with the bound in Theorem 12 to get (7):
‖x̂# − x̂h(k)‖2 ≤ ( 2τ √ k + t
1− θ
( 1 +
β
1− δk,t
) + 2τ ) ‖x̂t(k)‖2
where we write x# = [x̂#, e#]T with x̂#, e# ∈ Cn.
We now focus on proving Theorem 3. In order to do so, we will need some lemmas that will be used in the main proof.
Lemma 14. If a matrix A ∈ Cm×N satisfies the `2 robust null space property for S ⊂ [N |, with card(S) = s, then it satisfies the `1 robust null space property for S with constants 0 < ρ < 1, τ ′ := τ √ s > 0.
Proof. For any v ∈ CN , ‖vS‖2 ≤ ρ√s‖vS̄‖1 + τ‖Av‖. Then, using the fact that ‖vS‖1 ≤ √ s‖vS‖2, we get:‖vS‖1 ≤ ρ‖vS̄‖1 + τ √ s‖Av‖.
Lemma 15 (Theorem 4.20 in Foucart & Rauhut (2017)). If a matrix A ∈ Cm×N satisfies the `1 robust null space property (with respect to ‖.‖) and for 0 < ρ < 1 and τ > 0 for S ⊂ [N |, then:
‖z − x‖1 ≤ 1 + ρ
1− ρ (‖z‖1 − ‖x‖1 + 2‖xS̄‖1) +
2τ
1− ρ ‖A(z − x)‖
for all z, x ∈ CN . Lemma 16 (Proposition 2.3 in Foucart & Rauhut (2017)). For any p > q > 0 and x ∈ Cn,
inf z∈Mk
‖x− z‖p ≤ 1
(k) 1 q− 1 p
‖x‖q
Proof of Theorem 3. Let 0 < ρ < 1 be arbitrary. Since F is a unitary matrix, for any S ⊆ [n] and v ∈ Cn, we have
‖vS‖2 ≤ ρ√ k ‖vS‖1 + τ‖v‖2 = ρ√ k ‖vS‖1 + τ‖Fv‖2 (17)
where τ = 1. Now let S ⊆ [n] such that card(S) ≤ k. Then, F satisfies the `2 robust null space property for S. Next, using Lemma 14 we get ‖vS‖1 ≤ ρ‖vS̄‖1 + τ √ k‖Fv‖2 for all v ∈ Cn. Now let x# = BP(y, F, η), then we know ‖x#‖1 ≤ ‖x̂‖1. Fixing S ⊆ [n] to be the support of x̂h(k) and using Lemma 15 , we get:
‖x# − x̂‖1 ≤ 1 + ρ
1− ρ (‖x#‖1 − ‖x̂‖1 + 2‖x̂t(k)‖1) +
2τ √ k 1− ρ ‖F (x# − x̂)‖2
≤ 1 + ρ 1− ρ
( 2‖x̂t(k)‖1 ) + 2τ √ k
1− ρ ‖F (x# − x̂)‖2
≤ 1 + ρ 1− ρ
( 2‖x̂t(k)‖1 ) + 4τ √ k
1− ρ ‖e‖2
≤ 1 + ρ 1− ρ
( 2‖x̂t(k)‖1 ) + 4τ √ k
1− ρ η
Letting ρ → 0 and recalling that τ = 1 gives (8). Now let S be the support of (x# − x̂)h(k). Note ‖(x# − x̂)S‖2 = infz∈Mk ‖(x# − x̂)− z‖2. Then, using Lemma 16 and (17), we see that
‖x# − x̂‖2 ≤ ‖(x# − x̂)S‖2 + ‖(x # − x̂)S‖2
≤ 1√ k ‖(x# − x̂)‖1 + ρ√ k ‖(x# − x̂)S‖1 + τ‖F (x # − x)‖2
≤ 1 + ρ√ k ‖(x# − x̂)‖1 + 2τη
≤ (1 + ρ) 2
√ k(1− ρ)
( 2‖x̂t(k)‖1 ) + 4τ(1 + ρ)
(1− ρ) η + 2τη
= (1 + ρ)2√ k(1− ρ)
( 2‖x̂t(k)‖1 ) +
( 4τ(1 + ρ)
(1− ρ) + 2τ
) η
Recalling τ = 1 and letting ρ→ 0 gives the desired result.
A.4 DANTZIG SELECTOR
Next we introduce the Dantzig Selector algorithm with an additional constraint. We first prove its recovery guarantees for `∞-norm and then explain the reasoning behind the additional constraint.
Proof of Theorem 4. The proof follows the same structure as the proof of Theorem 3. Therefore we provide a sketch and leave out the complete derivation. Let 0 < ρ < 1 be arbitrary. Since F is a unitary matrix, for any S ⊆ [n] and v ∈ Cn, we have
‖vS‖2 ≤ ρ√ k ‖vS‖1 + ‖vS‖2 ≤ ρ√ k ‖vS‖1 +
√ k‖v‖∞ =
ρ√ k ‖vS‖1 +
√ k‖F ∗Fv‖∞
The rest of the argument is the same as in the proof of Theorem 3.

Review summaries:
This paper extends the compressive recovery defense framework introduced by Bafna et al. (2018), which is mainly against l_0 attacks, to l_2 and l_∞ attacks. They provide guarantees for some recovery algorithms in the case of different kinds of norm bounded noises. The difference between their work and the previous work is clearly clarified.