Greedy Column Subset Selection: New Bounds and Distributed Algorithms

The problem of matrix column subset selection
has recently attracted a large body of research,
with feature selection serving as one obvious and
important application. Among the techniques
that have been applied to solve this problem, the
greedy algorithm has been shown to be quite
effective in practice. However, our theoretical
guarantees on its performance have not been ex-
plored thoroughly, especially in a distributed set-
ting. In this paper, we study the greedy algorithm
for the column subset selection problem from a
theoretical and empirical perspective and show
its effectiveness in a distributed setting. In par-
ticular, we provide an improved approximation
guarantee for the greedy algorithm, and present
the first distributed implementation of this algo-
rithm with provable approximation factors. We
use the idea of randomized composable core-
sets, developed recently in the context of sub-
modular maximization. Finally, we validate the
effectiveness of this distributed algorithm via an
empirical study.

• Algorithms and Theory

• Machine Intelligence