A third line of work originates in the compressed sensing literature. Here low-dimensional intrinsic structure and often small noise levels, including adversarial noise, are studied.
Small noise might be a realistic assumption for many classification data sets from the machine learning literature. On data sets such as CIFAR-10 [1]} or MNIST [2]} state of the art algorithms achieve test errors smaller than \(0.5\%\) , implying that the proportion of flipped labels in the full data set is also small.
On the theoretical side, pioneering work by Wojtaszczyk [3]} has shown that minimum-\(\ell _1\) -norm interpolation, introduced by [4]} as basis pursuit, is robust to small, adversarial errors in sparse linear regression. This has recently been extended to other minimum-norm-solutions in linear regression [5]} and phase-retrieval [6]}.
