License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.SOSA.2019.19
URN: urn:nbn:de:0030-drops-100455
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10045/
Go to the corresponding OASIcs Volume Portal

Karmalkar, Sushrut ; Price, Eric

Compressed Sensing with Adversarial Sparse Noise via L1 Regression

pdf-format:
OASIcs-SOSA-2019-19.pdf (0.5 MB)

Abstract

We present a simple and effective algorithm for the problem of sparse robust linear regression. In this problem, one would like to estimate a sparse vector w^* in R^n from linear measurements corrupted by sparse noise that can arbitrarily change an adversarially chosen eta fraction of measured responses y, as well as introduce bounded norm noise to the responses.
For Gaussian measurements, we show that a simple algorithm based on L1 regression can successfully estimate w^* for any eta < eta_0 ~~ 0.239, and that this threshold is tight for the algorithm. The number of measurements required by the algorithm is O(k log n/k) for k-sparse estimation, which is within constant factors of the number needed without any sparse noise.
Of the three properties we show - the ability to estimate sparse, as well as dense, w^*; the tolerance of a large constant fraction of outliers; and tolerance of adversarial rather than distributional (e.g., Gaussian) dense noise - to the best of our knowledge, no previous polynomial time algorithm was known to achieve more than two.

BibTeX - Entry

@InProceedings{karmalkar_et_al:OASIcs:2018:10045,
  author =	{Sushrut Karmalkar and Eric Price},
  title =	{{Compressed Sensing with Adversarial Sparse Noise via L1 Regression}},
  booktitle =	{2nd Symposium on Simplicity in Algorithms (SOSA 2019)},
  pages =	{19:1--19:19},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-099-6},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{69},
  editor =	{Jeremy T. Fineman and Michael Mitzenmacher},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10045},
  URN =		{urn:nbn:de:0030-drops-100455},
  doi =		{10.4230/OASIcs.SOSA.2019.19},
  annote =	{Keywords: Robust Regression, Compressed Sensing}
}

Keywords: Robust Regression, Compressed Sensing
Collection: 2nd Symposium on Simplicity in Algorithms (SOSA 2019)
Issue Date: 2018
Date of publication: 08.01.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI