Penalized Versus Constrained Generalized Eigenvalue Problems

ABSTRACT

We investigate the difference between using an ℓ₁ penalty versus an ℓ₁ constraint in generalized eigenvalue problems arising in multivariate analysis. Our main finding is that the ℓ₁ penalty may fail to provide very sparse solutions; a severe disadvantage for variable selection that can be remedied by using an ℓ₁ constraint. Our claims are supported both by empirical evidence and theoretical analysis. Finally, we illustrate the advantages of the ℓ₁ constraint in the context of discriminant analysis and principal component analysis. Supplementary materials for this article are available online.

KEYWORDS:

• Discriminant analysis
• Duality gap
• Nonconvex optimization
• Variable selection

Supplementary Materials

• Supplementary file: Proofs for all Propositions and derivation of Algorithm 1 (pdf file).

• Computer code: All the R script files and C extensions with R wrappers that were used for simulations and real data calculations performed in the article (zip file).

Acknowledgments

The authors thank Michael Todd for a useful discussion of duality theory and Daniela Witten for the helpful comments on the earlier drafts of this manuscript. The authors also thank the associate editor and two anonymous referees for valuable comments and suggestions that helped to improve this manuscript. This research was partially supported by NSF grants DMS-1208488 and DMS-0808864.