# Sparse PCA in TFOCS

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

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.

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``````