COMPUTER IMPLEMENTED METHOD FOR MAXIMIZING CANDIDATE SOLUTION TO CARDINALLY CONSTRAINED COMBINATORIAL OPTIMIZATION PROBLEM OF SPARSE PRINCIPAL COMPONENT ANALYSIS AND SOLVING THE OPTIMIZATION PROBLEM

摘要

PROBLEM TO BE SOLVED: To maximize candidate solutions to a cardinally-constrained combinatorial optimization problem of sparse principal component analysis.

SOLUTION: An approximate method has as input a covariance matrix A, a candidate solution and a sparsity parameter k. A variational renormalization for the candidate solution vector x with regards to the eigenvalue structure of the covariance matrix A and the sparsity parameter k is then performed by means of a sub-matrix eigenvalue decomposition of A to obtain a variance maximized k-sparse eigenvector x (^) that is the best possible solution. Another method solves the problem by means of a nested greedy search technique that includes a forward and backward pass. An exact solution to the problem initializes branch-and-bound search with the output of a greedy solution.

COPYRIGHT: (C)2007,JPO&INPIT