Average Case Column Subset Selection for Entrywise $\ell_1$-Norm Loss

Nevertheless, we show that under certain minimal and realistic distributional settings, it is possible to obtain a (1+ɛ)-approximation with a nearly linear running time and poly(k/ɛ) + O(k log n) columns. Namely, we show that if the input matrix A has the form A = B +E, where B is an arbitrary rank-k matrix, and E is a matrix with i.i.d.