Timezone: »
Poster
Column Selection via Adaptive Sampling
Saurabh Paul · Malik Magdon-Ismail · Petros Drineas
Selecting a good column (or row) subset of massive data matrices has found many applications in data analysis and machine learning. We propose a new adaptive sampling algorithm that can be used to improve any relative-error column selection algorithm. Our algorithm delivers a tighter theoretical bound on the approximation error which we also demonstrate empirically using two well known relative-error column subset selection algorithms. Our experimental results on synthetic and real-world data show that our algorithm outperforms non-adaptive sampling as well as prior adaptive sampling approaches.
Author Information
Saurabh Paul (Paypal Inc)
Malik Magdon-Ismail (RPI)
Petros Drineas (Rensselaer Polytechnic Institute)
More from the Same Authors
-
2015 Poster: Approximating Sparse PCA from Incomplete Data »
ABHISEK KUNDU · Petros Drineas · Malik Magdon-Ismail -
2013 Workshop: Large Scale Matrix Analysis and Inference »
Reza Zadeh · Gunnar Carlsson · Michael Mahoney · Manfred K. Warmuth · Wouter M Koolen · Nati Srebro · Satyen Kale · Malik Magdon-Ismail · Ashish Goel · Matei A Zaharia · David Woodruff · Ioannis Koutis · Benjamin Recht -
2011 Poster: Sparse Features for PCA-Like Linear Regression »
Christos Boutsidis · Petros Drineas · Malik Magdon-Ismail -
2010 Poster: Permutation Complexity Bound on Out-Sample Error »
Malik Magdon-Ismail -
2010 Poster: Random Projections for $k$-means Clustering »
Christos Boutsidis · Anastasios Zouzias · Petros Drineas -
2009 Poster: Unsupervised Feature Selection for the $k$-means Clustering Problem »
Christos Boutsidis · Michael W Mahoney · Petros Drineas -
2008 Poster: Adapting to a Market Shock: Optimal Sequential Market-Making »
Sanmay Das · Malik Magdon-Ismail