Timezone: »

 
Poster
Average Case Column Subset Selection for Entrywise $\ell_1$-Norm Loss
Zhao Song · David Woodruff · Peilin Zhong

Thu Dec 12 05:00 PM -- 07:00 PM (PST) @ East Exhibition Hall B + C #1
in Algorithms -- Components Analysis (e.g., CCA, ICA, LDA, PCA) »
We study the column subset selection problem with respect to the entrywise $\ell_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^{\Omega(1)}$ number of columns to obtain a $(1+\epsilon)$-approximation to an $n \times n$ matrix. Nevertheless, we show that under certain minimal and realistic distributional settings, it is possible to obtain a $(1+\epsilon)$-approximation with a nearly linear running time and poly$(k/\epsilon)+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. entries drawn from any distribution $\mu$ for which the $(1+\gamma)$-th moment exists, for an arbitrarily small constant $\gamma > 0$, then it is possible to obtain a $(1+\epsilon)$-approximate column subset selection to the entrywise $\ell_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+\epsilon)$-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+\epsilon)$-approximation for entrywise $\ell_1$-norm loss low rank approximation.
Keywords: Theory · Components Analysis (e.g., CCA, ICA, LDA, PCA) · Algorithms; Algorithms
[ Paper]  [ Poster] 

Author Information

Zhao Song (University of Washington)
David Woodruff (Carnegie Mellon University)
Peilin Zhong (Columbia University)

More from the Same Authors