Sparse PCA in TFOCS

TFOCS
1

I am trying to implement Sparse PCA as described in 6 of http://www.eecs.berkeley.edu/~elghaoui/Pubs/SPCAhandbookSV.pdf
this is my code:

X = randn(20,20);

R = X’*X;

d = 20;

e = ones(d,1);

lambda = 0.5;

mu = 1e-4;

opts = [];

opts.stopCrit = 4;
opts.printEvery = 1;
opts.tol = 1e-4;
opts.maxIts = 25;
%opts.errFcn{1} = @(f,d,p) norm(p{1}+p{2}-X,‘fro’)/norm(X,‘fro’);
largescale = true;

x0 = {e*e’};

z0 = [];
obj={proj_psdUTrace(1)};

affine = { -R 0;1 0};

dualProx = {proj_spectral,proj_linf(lambda)} ;

[x,out,optsOut] = tfocs_SCD( obj, affine, dualProx, mu, x0, z0, opts);

Y=x{1};

however this is not working correctly(err like matrix dimension not agree)… Plz tell me where I am wrong…
In particular, can any body help me to tell what should be obj, affine and dualProx for this problem…?
In particular how can we solve this problem for large sized matrices in tfocs, cvx code for the problem is as follows:
variable X(d,d) symmetric;

X == semidenite(d);

minimize(-trace(RX)+lambda(e’*abs(X)*e));

subject to

trace(X)==1;

cvx end

1 Like
2

With a day’s struggle I have come up with this version… Y = randn(10,20);
R = Y’*Y;

d=size(R,1);

e = ones(size(R,1),1);

lambda = 5;

mu = 1e-4;

opts = [];

opts.stopCrit = 4;

opts.printEvery = 1;

opts.tol = 1e-6;

opts.maxIts = 50;

%opts.errFcn{1} = @(f,d,p) norm(p{1}+p{2}-X,‘fro’)/norm(X,‘fro’);
% largescale = false;
x0 = e*e’;

z0 = [];

obj=smooth_linear(-R);

A=linop_handles({[size(R,1),size(R,2)],[size(R,1),size(R,2)]},@(X)(eye(size(R,1))*X),@(y)(eye(size(R,1))’*y),‘R2R’);

affine = {A ,0; A,0};
dualProx={prox_maxEig(1),proj_linf(lambda)} ;

[u,out,optsOut] = tfocs_SCD( obj,affine, dualProx, mu, x0, z0, opts);
It is giving a nearly rank1 soln with many sparse for higher values of lambda. But sum of eigenvalues of u is not 1. Plz tell if the implementation for Sparse PCA is correct.

3

Here’s one way to do it. I modified proj_psdUTrace.m to take in an extra trace term (since this is just a linear term). An extra linear term is quite common so we may take care of it nicely in a future release of TFOCS. For now, the modified proj_psdUTrace.m is in github, so head there to get the latest version.

First, setup the problem

rng(100);
d = 20;
X = randn(d);
R = X'*X; % Sigma
e = ones(d,1);
lambda = 0.5;

Now solve in CVX so we can verify we’re solving the right problem

cvx_begin
cvx_precision best
 variable X(d,d) semidefinite
 minimize( -R(:)'*X(:)+lambda*norm(X(:),1) )
 subject to
 trace(X)==1;
cvx_end
toc
X_CVX = X;

And the TFOCS solve:

mu = 1e-2;
largescale  = ( d > 200 );
is_real     = true;
obj= proj_psdUTrace( 1, largescale, is_real, [], -R );
linear = linop_vec( [d,d] );
affine = { linear };
dualProx    = proj_linf(lambda);
x0      = [];
z0      = [];
opts    = struct('printEvery',4,'tol',1e-10,'maxIts',500,'L0',1);
opts.errFcn     = @(f,d,p) norm(p-X_CVX,'fro')/norm(X_CVX,'fro');
opts.restart    = 50;
[x,out,optsOut] = tfocs_SCD( obj, affine, dualProx, mu, x0, z0, opts );

which gives the following output on my computer:

Auslender & Teboulle's single-projection method
Iter    Objective   |dx|/|x|    step      errors
----+----------------------------------+----------
4   | -6.82076e+01  2.53e-01  1.52e+00 | 1.06e-01
8   | -6.70352e+01  9.12e-02  2.32e+00 | 6.26e-02
12  | -6.67141e+01  4.09e-02  3.54e+00 | 2.97e-02
16  | -6.66041e+01  2.35e-02  5.40e+00 | 1.44e-02
20  | -6.65586e+01  1.25e-02  8.23e+00 | 7.41e-03
24  | -6.65371e+01  7.68e-03  1.25e+01 | 4.15e-03
28  | -6.65259e+01  5.42e-03  1.91e+01 | 2.42e-03
32  | -6.65197e+01  3.74e-03  2.91e+01 | 1.43e-03
...
100 | -6.65105e+01  2.10e-06  2.63e+01*| 2.39e-07
101 | -6.65105e+01  4.26e-05  2.93e+01 | 3.13e-08 | restarted
104 | -6.65105e+01  3.68e-08  9.84e+00*| 1.11e-08
108 | -6.65105e+01  6.13e-09  1.50e+01*| 1.97e-09
112 | -6.65105e+01  2.03e-09  1.04e+01*| 3.20e-10
116 | -6.65105e+01  5.92e-10  1.59e+01*| 2.86e-10
120 | -6.65105e+01  1.24e-10  2.42e+01*| 1.72e-10
123 | -6.65105e+01  9.59e-11  1.32e+01*| 1.71e-10
Finished: Step size tolerance reached