Alternating direction method of multipliers for penalized zero-variance discriminant analysis

Brendan Ames, Mingyi Hong

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 a heuristic, called sparse zero-variance discriminant analysis (SZVD), 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 induce sparse structures in the resulting vectors. To approximately solve the resulting nonconvex problem, we develop a simple algorithm based on the alternating direction method of multipliers. 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. Finally, we establish theoretical guarantees for convergence of our algorithm to stationary points of the original nonconvex problem, and empirically demonstrate the effectiveness of our heuristic for classifying simulated data and data drawn from applications in time-series classification.

Introduction

In modern data science, the "curse of dimensionality" presents a significant hurdle for traditional statistical methods. When the number of features ($p$) vastly exceeds the number of observations ($n$), classical Linear Discriminant Analysis (LDA) fails because the within-class covariance matrix ($W$) becomes singular. In such cases, the standard LDA objective—maximizing the ratio of between-class scatter to within-class scatter—can be made arbitrarily large, rendering the resulting discriminant vectors meaningless.

To address this, researchers often turn to Zero-Variance Discriminant Analysis (ZVD), which identifies discriminant vectors within the null space of $W$. While ZVD effectively handles the singularity of the covariance matrix, it typically produces "dense" vectors where every feature contributes to the classification. This lack of sparsity makes the resulting models difficult to interpret and computationally expensive to deploy in resource-constrained environments. This paper introduces Sparse Zero-Variance Discriminant Analysis (SZVD), a framework that integrates sparsity-inducing penalties into the ZVD objective to achieve simultaneous dimensionality reduction and feature selection.

Methodology: The SZVD Framework

SZVD leverages the mathematical "failure" of a singular covariance matrix by treating the null space of $W$ as a source of high-certainty information for class separation. The core objective is to find a discriminant vector that maximizes between-class scatter while remaining in the null space of $W$, subject to an $\ell_1$-norm penalty to enforce sparsity.

Optimization via ADMM

The resulting optimization problem is non-convex and computationally challenging. To solve it, the authors employ the Alternating Direction Method of Multipliers (ADMM). By splitting the variables, the algorithm decomposes the complex global problem into two manageable sub-steps:

  1. Soft-Thresholding: A standard operator in LASSO-style problems that induces sparsity by setting small feature weights to zero.
  2. Linear System Solve: A step that updates the discriminant vector to maximize class separation.

Beyond classification, the authors demonstrate that this ADMM framework is generalizable to a broader class of penalized generalized eigenvalue problems, including specific relaxations of Sparse Principal Component Analysis (Sparse PCA). Crucially, the paper provides theoretical guarantees that the algorithm converges to stationary points of the original non-convex problem.

Empirical Results

The effectiveness of SZVD was evaluated using both synthetic simulations and real-world time-series datasets from the UCR Time-Series Repository.

Synthetic Data

In simulations involving high feature correlation (e.g., $r=0.9$), SZVD significantly outperformed competing methods like Penalized LDA (PLDA) and Sparse Discriminant Analysis (SDA). While methods relying on diagonal approximations of $W$ failed to account for feature dependencies, SZVD remained robust, often achieving near-zero error rates.

Real-World Applications

The model was tested on three specific time-series tasks:

  • Coffee: Distinguishing between Arabica and Robusta beans using spectrograms.
  • OliveOil: Identifying the country of origin for olive oils.
  • ECGFiveDays: Classifying electrocardiogram measurements from different days.

In the ECGFiveDays dataset, SZVD reduced the feature set from 136 to approximately 32 while maintaining high accuracy. Furthermore, the sparse vectors produced by SZVD were found to be highly interpretable, aligning with physical characteristics of the data (such as specific peaks in ECG signals) rather than the high-frequency noise often captured by unpenalized ZVD.

Conclusion

SZVD offers a powerful alternative for high-dimensional classification by embracing the singularity of covariance matrices rather than attempting to regularize it away. By combining the precision of the ZVD null space with the interpretability of $\ell_1$-penalization, the method achieves superior accuracy and extreme sparsity. Additionally, the ADMM-based implementation is significantly faster than iterative alternatives like SDA, making it a viable tool for large-scale genomic or spectroscopic analysis. Future work may explore the consistency of the estimator and the extension of this framework to non-linear kernel-based methods.

Summary updated

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 a heuristic, called sparse zero-variance discriminant analysis (SZVD), 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 induce sparse structures in the resulting vectors. To approximately solve the resulting nonconvex problem, we develop a simple algorithm based on the alternating direction method of multipliers. 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. Finally, we establish theoretical guarantees for convergence of our algorithm to stationary points of the original nonconvex problem, and empirically demonstrate the effectiveness of our heuristic for classifying simulated data and data drawn from applications in time-series classification.
BibTeX
@misc{ames2014alternating,
  author = {Brendan Ames and Mingyi Hong},
  title = {{Alternating direction method of multipliers for penalized zero-variance discriminant analysis}},
  year = {2014},
  eprint = {1401.5492},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1401.5492},
}
Figure