text: We provide recovery guarantees for compressible signals that have been corrupted with noise and extend the framework introduced in [1] to defend neural networks against @math -norm and @math -norm attacks. Concretely, for a signal that is approximately sparse in some transform domain and has been perturbed with noise, we provide guarantees for accurately recovering the signal in the transform domain. We can then use the recovered signal to reconstruct the signal in its original domain while largely removing the noise. Our results are general as they can be directly applied to most unitary transforms used in practice and hold for both @math -norm bounded noise and @math -norm bounded noise. In the case of @math -norm bounded noise, we prove recovery guarantees for Iterative Hard Thresholding (IHT) and Basis Pursuit (BP). For the case of @math -norm bounded noise, we provide recovery guarantees for BP. These guarantees theoretically bolster the defense framework introduced in [1] for defending neural networks against adversarial inputs. Finally, we experimentally demonstrate this defense framework using both IHT and BP against the One Pixel Attack [21], Carlini-Wagner @math and @math attacks [3], Jacobian Saliency Based attack [18], and the DeepFool attack [17] on CIFAR-10 [12], MNIST [13], and Fashion-MNIST [27] datasets. This expands beyond the experimental demonstrations of [1].
  @cite_0: We give a new algorithm for approximating the Discrete Fourier transform of an approximately sparse signal that is robust to worst-case L0 corruptions, namely that some coordinates of the signal can be corrupt arbitrarily. Our techniques generalize to a wide range of linear transformations that are used in data analysis such as the Discrete Cosine and Sine transforms, the Hadamard transform, and their high-dimensional analogs. We use our algorithm to successfully defend against worst-case L0 adversaries in the setting of image classification. We give experimental results on the Jacobian-based Saliency Map Attack (JSMA) and the CW L0 attack on the MNIST and Fashion-MNIST datasets as well as the Adversarial Patch on the ImageNet dataset.
  @cite_19: 
  @cite_15: At the intersection of mathematics, engineering, and computer science sits the thriving field of compressive sensing. Based on the premise that data acquisition and compression can be performed simultaneously, compressive sensing finds applications in imaging, signal processing, and many other domains. In the areas of applied mathematics, electrical engineering, and theoretical computer science, an explosion of research activity has already followed the theoretical results that highlighted the efficiency of the basic principles. The elegant ideas behind these principles are also of independent interest to pure mathematicians.A Mathematical Introduction to Compressive Sensing gives a detailed account of the core theory upon which the field is build. With only moderate prerequisites, it is an excellent textbook for graduate courses in mathematics, engineering, and computer science. It also serves as a reliable resource for practitioners and researchers in these disciplines who want to acquire a careful understanding of the subject. A Mathematical Introduction to Compressive Sensing uses a mathematical perspective to present the core of the theory underlying compressive sensing.
summary: The authors of @cite_0 introduced the CRD framework which inspired this work. The main theorem (Theorem 2.2) of @cite_0 is an analog of our Theorem and provides a similar bound the approximation error for recovery via IHT. First note that the statement of the Theorem 2.2 of @cite_0 is missing the required hypothesis @math . This hypothesis appears in Lemma 3.6 of @cite_0 , which is used to prove Theorem 2.2, but it appears to have been accidentally dropped from the statement of Theorem 2.2. We note that, by making the constants explicit, the proof of Lemma 3.6 of @cite_0 gives the same restricted isometry property that we do in Theorem . Therefore, the guarantees we obtain for IHT are essentially the same as in @cite_0 . The main difference is that, to derive recovery guarantees for IHT from the restricted isometry property, we utilize Theorem below (which is a modified version of Theorem 6.18 of @cite_15 ) while the authors of @cite_0 utilize Theorem 3.4 in @cite_0 (which is taken from @cite_19 ).