Poster
Average Case Column Subset Selection for Entrywise -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
]
Abstract:
We study the column subset selection problem with respect to the entrywise -norm loss. It is known that in the worst case, to obtain a good rank- approximation to a matrix, one needs an arbitrarily large number of columns to obtain a -approximation to an matrix. Nevertheless, we show that under certain minimal and realistic distributional settings, it is possible to obtain a -approximation with a nearly linear running time and poly columns. Namely, we show that if the input matrix has the form , where is an arbitrary rank- matrix, and is a matrix with i.i.d. entries drawn from any distribution for which the -th moment exists, for an arbitrarily small constant , then it is possible to obtain a -approximate column subset selection to the entrywise -norm in nearly linear time. Conversely we show that if the first moment does not exist, then it is not possible to obtain a -approximate subset selection algorithm even if one chooses any columns. This is the first algorithm of any kind for achieving a -approximation for entrywise -norm loss low rank approximation.
Live content is unavailable. Log in and register to view live content