Spectral Bounds for Sparse PCA and Sparse LDA
We develop exact methods for optimizing quadratic performance criteria (e.g., minimizing mean-squared-error or maximizing variance) subject to "sparsity" constraints (i.e., the solution vector must have few non-zero elements). Such cardinality-constrained optimization problems are encountered in a wide range of applied fields, from bioinformatics (gene selection) to computational finance (portfolio optimization). In specific, we have focused on sparse modeling techniques for computer vision and machine learning. We have developed an efficient and near-optimal greedy algorithm which yields better than state-of-the-art performance on "sparse PCA" benchmarks used in the statistics community. In addition, we derive a variational spectral method for finding optimal solutions using branch-and-bound search. Our algorithms have been fruitfully applied to various real-world computer vision and machine learning tasks.
Background & Objective: Engineering and the applied sciences use numerical optimization techniques to maximize gain (or minimize loss) while satisfying various operational constraints. With the mathematical sophistication of modern-day (non)linear programming techniques, optimization problems involving hundreds of (in)equality constraints are solved routinely by general purpose computers. But despite all this progress, there is one (nonlinear) constraint that still remains a challenge: "sparseness", where in addition to satisfying (in)equality constraints, the solution vector must have many of its elements be (exactly) zero. In this way, the solution will involve fewer measurements (variables), thus reducing associated costs, lowering computational complexity and perhaps even improving performance in some cases. Unfortunately, sparse constraints (mathematically equivalent to an L0-norm) are inherently non-convex and NP-hard, with combinatorial complexity.
Technical Discussion: Recently, in sparse signal representation (basis pursuit with over-complete dictionaries) important advances towards L0-norm optimization have been made. Working independently, researchers at Stanford (Donoho) and MIT (Willsky) have shown that under certain conditions (coherence of bases with linear transforms) an Lp-norm (p<1) on the solution vector of a set of linear equalities (Ax=b) is equivalent to an L0-norm. Hence, resulting in a sparse solution with minimized cardinality. Remarkably, this means that a formerly NP-hard combinatorial problem essentially becomes convex (under these conditions) thus leading to globally optimal solutions which can be obtained by standard polynomial-time optimization algorithms.
However, with sparse PCA the objective function (a Rayleigh quotient) and the cardinality constraint are quadratic and therefore harder to optimize/satisfy (i.e., sparse PCA is not subject to any known equivalence conditions). Recent advances in sparse PCA were achieved mainly through continuous approximation techniques and convex relaxations of the hard cardinality constraint. In contrast, we considered an alternative discrete spectral formulation based on variational eigenvalue bounds. We have devised an efficient near-optimal greedy algorithm that is several orders of magnitude faster than competing continuous methods. More importantly, our discrete approach leads to provably optimal solutions using branch-and-bound search. Furthermore, the discrete approach provides a simple renormalization step that improves approximate solutions obtained by any continuous method.
| Technical Reports: | |
| Generalized Spectral Bounds for Sparse LDA | |
| Spectral Bounds for Sparse PCA : Exact & Greedy Algorithms | |
Technology Areas:
Computer Vision
Artificial Intelligence
Sensor and Data Systems
Modification Date: September 12, 2007