Skip to yearly menu bar Skip to main content


Poster

Average Case Column Subset Selection for Entrywise 1-Norm Loss

Zhao Song · David Woodruff · Peilin Zhong

East Exhibition Hall B, C #1

Keywords: [ Theory ] [ Algorithms; Algorithms ] [ Components Analysis (e.g., CCA, ICA, LDA, PCA) ]


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(klogn) 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 no(1) columns. This is the first algorithm of any kind for achieving a (1+ϵ)-approximation for entrywise 1-norm loss low rank approximation.

Live content is unavailable. Log in and register to view live content