An improved approximation algorithm for the column subset selection problem

By Christos Boutsidis, Michael W. Mahoney, Petros Drineas. 2008

421 citations recorded by the source corpus.

We consider the problem of selecting the "best" subset of exactly k columns from an m x n matrix A. In particular, we present and analyze a novel two-stage algorithm that runs in O(min{mn2, m2n}) time and returns as output an m x k matrix C consisting of exactly k columns of A. In the first stage (the randomized stage), the algorithm randomly selects O(k log k) columns according to a judiciously-chosen probability distribution that depends on information in the top-k right singular subspace of A. In the second stage (the deterministic stage), the algorithm applies a deterministic column-selection procedure to select and return exactly k columns from the set of columns selected in the first stage. Let C be the m x k matrix containing those k columns, let PC denote the projection matrix onto the span of those columns, and let Ak denote the "best" rank-k approximation to the matrix A as computed with the singular value decomposition. Then, we prove that [EQUATION] with probability at least 0.7. This spectral norm bound improves upon the best previously-existing result (of Gu and Eisenstat [21]) for the spectral norm version of this Column Subset Selection Problem. We also prove that [EQUATION] with the same probability. This Frobenius norm bound is only a factor of √k log k worse than the best previously existing existential result and is roughly O(√k!) better than the best previous algorithmic result (both of Deshpande et al. [11]) for the Frobenius norm version of this Column Subset Selection Problem.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Networks and Communications

Citations in the corpus

Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm (2013, neutral): “sampling – where it goes by the name of leverage score sampling. The resulting sampling methods are again proportional to the squared Euclidean norms of rows and columns of the underlying matrix. See [5, 25, 44, 9], and references therein for applications to the column subset selection problem and m”
See all by looking at a few: Sparse modeling for finding representative objects (2012, neutral): “When the collection of data points is low-rank, Rank Revealing QR (RRQR) algorithm [5, 6] tries to select a few data points by finding a permutation of the data that gives the best conditioned submatrix.”
Efficient Volume Sampling for Row/Column Subset Selection (2010, methodology): “A recent article by Mahoney and Drineas [18] highlights the limitations of PCA and gives experimental data on practical applications of low-rank approximation based on row/column-subset selection.”
Online sketching hashing (2015, methodology): “An extensive body of algorithms exist, including CUR decomposition [5], random projection [31, 22], column sampling method [7, 1], and Nyström method [6].”
Efficient Multi-label Classification with Many Labels (2013, methodology): “Finally, the algorithm in (Boutsidis et al., 2009) involves an additional RRQR decomposition after the sampling step, which takes O(c 2 k log √ c) = O(k 3 log 2 k log(k log k)) time for c = Θ(k log k).”
Large Scale Spectral Clustering with Landmark-Based Representation (2011, methodology): “Besides random selection, several methods were proposed for landmark points selection (Kumar , Mohri, and Talwalkar 2009; Boutsidis, Mahoney, and Drineas 2009).”
Exploring Energy and Accuracy Tradeoff in Structure Simplification of Trained Deep Neural Networks (2018, positive): “It has been shown in [1] that using pivoted QR factorization, the resulting matrix Xp satisfies Ep = ||X − GXp||F √n − p · 2p · σp+1(X) (8)”
Handbook of Big Data (2016, methodology): “…source the software, generate an artiﬁcial data matrix of normal random numbers, generate an instance of an AN from it, and start up by creating a window showing a blockplot of correlations as they arise from pure random association among 100 variables given a sample size of 200, divided into…”
Sampling Methods for the Nyström Method (2012, neutral): “…error bounds using adaptive sampling techniques (Deshpande et al., 2006; Har-peled, 2006); and, relative error bounds based on distributions derived from the singular vectors of the input matrix, in work related to the column-subset selection problem (Drineas et al., 2008; Boutsidis et al., 2009).”
Sketching as a Tool for Numerical Linear Algebra (2014, methodology): “For a more detailed discussion of this CX problem, which is also known as CSSP (Column Subset Selection Problem) see [20, 19, 57].”
The Why and How of Nonnegative Matrix Factorization (2014, background): “It is important to points out that separable NMF is closely related to several problems, including • Column subset selection which is a long-standing problem in numerical linear algebra (see [12] and the references therein).”
A Survey of Modern Questions and Challenges in Feature Extraction (2015, methodology): “Filter methods select a subset of features based on the notion of an importance score that is computed independent of the classifier (Gu et al., 2012; Boutsidis et al., 2009; He et al., 2005; Chen and Lin, 2006).”
Revisiting the Nystrom Method for Improved Large-scale Machine Learning (2013, methodology): “The structural bound of the form of Equation (12) was originally proven for q = 1 in [14], where it was applied to the Column Subset Selection Problem.”
Fast approximation of matrix coherence and statistical leverage (2011, background): “, 2010) and low-rank matrix approximation (Sarlós, 2006; Drineas et al., 2008; Mahoney & Drineas, 2009; Boutsidis et al., 2009).”