## Provably Correct Algorithms for Matrix Column Subset Selection with Selectively Sampled Data

*Yining Wang, Aarti Singh*; 18(156):1−42, 2018.

### Abstract

We consider the problem of matrix column subset selection, which
selects a subset of columns from an input matrix such that the
input can be well approximated by the span of the selected
columns. Column subset selection has been applied to numerous
real-world data applications such as population genetics
summarization, electronic circuits testing and recommendation
systems. In many applications the complete data matrix is
unavailable and one needs to select representative columns by
inspecting only a small portion of the input matrix. In this
paper we propose the first provably correct column subset
selection algorithms for partially observed data matrices. Our
proposed algorithms exhibit different merits and limitations in
terms of statistical accuracy, computational efficiency, sample
complexity and sampling schemes, which provides a nice
exploration of the tradeoff between these desired properties for
column subset selection. The proposed methods employ the idea of
feedback driven sampling and are inspired by several sampling
schemes previously introduced for low-rank matrix approximation
tasks (Drineas et al., 2008; Frieze et al., 2004; Deshpande and
Vempala, 2006; Krishnamurthy and Singh, 2014). Our analysis
shows that, under the assumption that the input data matrix has
incoherent rows but possibly coherent columns, all algorithms
provably converge to the best low-rank approximation of the
original data as number of selected columns increases.
Furthermore, two of the proposed algorithms enjoy a relative
error bound, which is preferred for column subset selection and
matrix approximation purposes. We also demonstrate through both
theoretical and empirical analysis the power of feedback driven
sampling compared to uniform random sampling on input matrices
with highly correlated columns.

[abs][pdf][bib]