Average Case Column Subset Selection for Entrywise _1-Norm Loss

Code

• github.com/zpl7840/noise_l1_low_rank_approximation
  Officialnone★ 0

Abstract

We study the column subset selection problem with respect to the entrywise _1-norm loss. It is known that in the worst case, to obtain a good rank-k approximation to a matrix, one needs an arbitrarily large n^(1) number of columns to obtain a (1+)-approximation to an n n matrix. 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 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. entries drawn from any distribution for which the (1+)-th moment exists, for an arbitrarily small constant > 0, then it is possible to obtain a (1+)-approximate column subset selection to the entrywise _1-norm in nearly linear time. Conversely we show that if the first moment does not exist, then it is not possible to obtain a (1+)-approximate subset selection algorithm even if one chooses any n^o(1) columns. This is the first algorithm of any kind for achieving a (1+)-approximation for entrywise _1-norm loss low rank approximation.

Reproductions