Tight bounds for minimum l1-norm interpolation of noisy data

Guillaume Wang, Konstantin Donhauser, Fanny Yang

We provide matching upper and lower bounds of order ${\sigma }^2/\log (d/n)$ for the prediction error of the minimum ${\ell }_1$-norm interpolator, a.k.a. basis pursuit. Our result is tight up…