Optimization Online


Spectral Bounds for Sparse PCA: Exact & Greedy Algorithms

Baback Moghaddam (baback***at***merl.com)
Yair Weiss (yweiss***at***cs.huji.ac.il)
Shai Avidan (avidan***at***merl.com)

Abstract: 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.

Keywords: Courant-Fischer Theorem, Inclusion Principle, Eigenvalue Bounds

Category 1: Applications -- Science and Engineering (Statistics )

Category 2: Applications -- OR and Management Sciences (Finance and Economics )

Category 3: Combinatorial Optimization

Citation: Advances in Neural Information Processing Systems (NIPS), Vol. 18, pps. 915-922, MIT Press, Cambridge MA, 2006

Download: [PDF]

Entry Submitted: 02/17/2006
Entry Accepted: 02/17/2006
Entry Last Modified: 02/17/2006

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society