Feature Extraction Using Sequential Semidefinite Programming

Abstract

Many feature extraction approaches end up with a trace quotient formulation. Since it is difficult to directly solve the trace quotient problem, conventionally the trace quotient cost is replaced by an approximation such that the generalised eigen-decomposition can be applied. In this work we directly optimise the trace quotient. It is reformulated as a quasi-linear semidefinite optimisation problem, which can be solved globally and efficiently using standard off-the-shelf semidefinite programming solvers. Also this optimisation strategy allows one to enforce additional constraints (e.g., sparseness constraints) on the projection matrix. Based on this optimisation framework, a novel feature extraction algorithm is designed. Its advantages are demonstrated on several UCI machine learning benchmark dataseis, USPS handwritten digits and ORL face data.