Alternating direction method of multipliers for sparse zero-variance discriminant analysis and principal component analysis
Preprint
Abstract
We consider the task of classification in the high-dimensional setting where the number of features of the given data is significantly greater than the number of observations. To accomplish this task, we propose sparse zero-variance discriminant analysis (SZVD) as a method for simultaneously performing linear discriminant analysis and feature selection on high-dimensional data. This method combines classical zero-variance discriminant analysis, where discriminant vectors are identified in the null space of the sample within-class covariance matrix, with penalization applied to the discriminant vectors to induce sparse solutions. We propose a simple algorithm based on the alternating direction method of multipliers for approximately solving the resulting nonconvex optimization problem. Further, we show that this algorithm is applicable to a larger class of penalized generalized eigenvalue problems, including a particular relaxation of the sparse principal component analysis problem. Theoretical guarantees for convergence of our algorithm to stationary points of the original nonconvex problem and the results of numerical experiments evaluating performance of our classification heuristic on simulated data and data drawn from applications in time-series classification are also provided.Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- On the linear convergence of the alternating direction method of multipliersMathematical Programming, 2016
- Convex approximations to sparse PCA via Lagrangian dualityOperations Research Letters, 2011
- Modified linear discriminant analysis approaches for classification of high-dimensional microarray dataComputational Statistics & Data Analysis, 2009
- Eigenvalues of large sample covariance matrices of spiked population modelsJournal of Multivariate Analysis, 2006
- Regularized linear discriminant analysis and its application in microarraysBiostatistics, 2006
- Regularization and Variable Selection Via the Elastic NetJournal of the Royal Statistical Society Series B: Statistical Methodology, 2005
- FTIR Spectroscopy and Multivariate Analysis Can Distinguish the Geographic Origin of Extra Virgin Olive OilsJournal of Agricultural and Food Chemistry, 2003
- Discrimination of Arabica and Robusta in Instant Coffee by Fourier Transform Infrared Spectroscopy and ChemometricsJournal of Agricultural and Food Chemistry, 1996
- On the Douglas—Rachford splitting method and the proximal point algorithm for maximal monotone operatorsMathematical Programming, 1992
- THE USE OF MULTIPLE MEASUREMENTS IN TAXONOMIC PROBLEMSAnnals of Eugenics, 1936