TR2006-007

Spectral Bounds for Sparse PCA: Exact & Greedy Algorithms


    •  Moghaddam, B., Weiss, Y., Avidan, S., "Spectral Bounds for Sparse PCA: Exact & Greedy Algorithms", Tech. Rep. TR2006-007, Mitsubishi Electric Research Laboratories, Cambridge, MA, February 2006.
      BibTeX Download PDF
      • @techreport{MERL_TR2006-007,
      • author = {Moghaddam, B. and Weiss, Y. and Avidan, S.},
      • title = {Spectral Bounds for Sparse PCA: Exact & Greedy Algorithms},
      • institution = {MERL - Mitsubishi Electric Research Laboratories},
      • address = {Cambridge, MA 02139},
      • number = {TR2006-007},
      • month = feb,
      • year = 2006,
      • url = {http://www.merl.com/publications/TR2006-007/}
      • }
  • Research Area:

    Computer Vision


Sparse PCA seeks approximate sparse "eigenvectors" whose projections capture the maximal variance of data. As a cardinality-constrained and non-convex optimization problem, it is NP-hard and yet it is encountered in a wide range of applied fields, from bio-informatics to finance. Recent progress has focused mainly on continuous approximation and convex relaxation of the hard cardinality constraint. In contrast, we consider an alternative discrete spectral formulation based on variational eigenvalue bounds and provide an effective greedy strategy as well as provably optimal solutions using branch-and-bound search. Moreover, the exact methodology used reveals a simple renormalization step that improves approximate solutions obtained by any continuous method. The resulting performance gain of discrete algorithms is demonstrated on real-world benchmark data and in extensive Monte Carlo evaluation trials.