Timezone: »
We study how well one can recover sparse principal componentsof a data matrix using a sketch formed from a few of its elements. We show that for a wide class of optimization problems,if the sketch is close (in the spectral norm) to the original datamatrix, then one can recover a near optimal solution to the optimizationproblem by using the sketch. In particular, we use this approach toobtain sparse principal components and show that for \math{m} data pointsin \math{n} dimensions,\math{O(\epsilon^{-2}\tilde k\max{m,n})} elements gives an\math{\epsilon}-additive approximation to the sparse PCA problem(\math{\tilde k} is the stable rank of the data matrix).We demonstrate our algorithms extensivelyon image, text, biological and financial data.The results show that not only are we able to recover the sparse PCAs from the incomplete data, but by using our sparse sketch, the running timedrops by a factor of five or more.
Author Information
ABHISEK KUNDU (RENSSELAER POLYTECHNIC INST)
Petros Drineas (Rensselaer Polytechnic Institute)
Malik Magdon-Ismail (RPI)
More from the Same Authors
-
2015 Poster: Column Selection via Adaptive Sampling »
Saurabh Paul · Malik Magdon-Ismail · Petros Drineas -
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