TY - GEN

T1 - A convex programming approach to the trace quotient problem

AU - Chunhua, Shen

AU - Hongdong, Li

AU - Brooks, Michael J.

PY - 2007

Y1 - 2007

N2 - The trace quotient problem arises in many applications in pattern classification and computer vision, e.g., manifold learning, low-dimension embedding, etc. The task is to solve a optimization problem involving maximizing the ratio of two traces, i.e., maxiy Tr(f(W))/Tr(h(W)). This optimization problem itself is non-convex in general, hence it is hard to solve it directly. Conventionally, the trace quotient objective function is replaced by a much simpler quotient trace formula, i.e., maxw Tr (h(W)-1 f (W)), which accommodates a much simpler solution. However, the result is no longer optimal for the original problem setting, and some desirable properties of the original problem are lost. In this paper we proposed a new formulation for solving the trace quotient problem directly. We reformulate the original non-convex problem such that it can be solved by efficiently solving a sequence of semidefinite feasibility problems. The solution is therefore globally optimal. Besides global optimality, our algorithm naturally generates orthonormal projection matrix. Moreover it relaxes the restriction of linear discriminant analysis that the projection matrix's rank can only be at most c - 1, where c is the number of classes. Our approach is more flexible. Experiments show the advantages of the proposed algorithm.

AB - The trace quotient problem arises in many applications in pattern classification and computer vision, e.g., manifold learning, low-dimension embedding, etc. The task is to solve a optimization problem involving maximizing the ratio of two traces, i.e., maxiy Tr(f(W))/Tr(h(W)). This optimization problem itself is non-convex in general, hence it is hard to solve it directly. Conventionally, the trace quotient objective function is replaced by a much simpler quotient trace formula, i.e., maxw Tr (h(W)-1 f (W)), which accommodates a much simpler solution. However, the result is no longer optimal for the original problem setting, and some desirable properties of the original problem are lost. In this paper we proposed a new formulation for solving the trace quotient problem directly. We reformulate the original non-convex problem such that it can be solved by efficiently solving a sequence of semidefinite feasibility problems. The solution is therefore globally optimal. Besides global optimality, our algorithm naturally generates orthonormal projection matrix. Moreover it relaxes the restriction of linear discriminant analysis that the projection matrix's rank can only be at most c - 1, where c is the number of classes. Our approach is more flexible. Experiments show the advantages of the proposed algorithm.

UR - http://www.scopus.com/inward/record.url?scp=38149124167&partnerID=8YFLogxK

M3 - Conference contribution

SN - 9783540763895

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 227

EP - 235

BT - Computer Vision - ACCV 2007 - 8th Asian Conference on Computer Vision, Proceedings

T2 - 8th Asian Conference on Computer Vision, ACCV 2007

Y2 - 18 November 2007 through 22 November 2007

ER -