Skip to yearly menu bar Skip to main content


Optimal Sparse Linear Encoders and Sparse PCA

Malik Magdon-Ismail · Christos Boutsidis

Area 5+6+7+8 #131

Keywords: [ Component Analysis (ICA,PCA,CCA, FLDA) ] [ Sparsity and Feature Selection ] [ (Other) Unsupervised Learning Methods ]


Principal components analysis~(PCA) is the optimal linear encoder of data. Sparse linear encoders (e.g., sparse PCA) produce more interpretable features that can promote better generalization. (\rn{1}) Given a level of sparsity, what is the best approximation to PCA? (\rn{2}) Are there efficient algorithms which can achieve this optimal combinatorial tradeoff? We answer both questions by providing the first polynomial-time algorithms to construct \emph{optimal} sparse linear auto-encoders; additionally, we demonstrate the performance of our algorithms on real data.

Live content is unavailable. Log in and register to view live content