PDF

Description

We examine the problem of approximating, in the Frobenius-norm sense, a positive, semidefinite symmetric matrix by a rank-one matrix, with an upper bound on the cardinality of its eigenvector. The problem arises in the decomposition of a covariance matrix into sparse factors, and has wide applications ranging from biology to finance. We use a modification of the classical variational representation of the largest eigenvalue of a symmetric matrix, where cardinality is constrained, and derive a semidefinite programming based relaxation for our problem. We also discuss Nesterov's smooth minimization technique applied to the SDP arising in the direct sparse PCA method. The method has complexity O(n^4 square root of log(n) / epsilon), where n is the size of the underlying covariance matrix, and epsilon is the desired absolute accuracy on the optimal value of the problem.

Details

Files

Statistics

from
to
Export
Download Full History