Rank minimization with TFOCS


#1

Hello,

I would like to solve a problem a bit similar to the problem solved in the paper “Phase Retrieval via Matrix Completion” of Candès et al. My problem can be expressed as:

Min trace(X)
st   |A(X)-b| <=eps
    X>=0

where A(x) stands for–> trace(A_k X)=b_k for k=1…K

The function SOLVER_SSDP solves the following function

% SOLVER_SSDP Generic semi-definite programs (SDP). Uses smoothing.
% [ x, out, opts ] = solver_sSDP( C, A, b, mu, X0, z0, opts )
%    Solves the smoothed standard form Semi-Definite Program (SDP)
%        minimize trace(C'*X) + 0.5*mu*||X-X0||_F^2
%        s.t.     A * vec(X) == b and X >= 0
%           where X >= 0 indicates that X is positive semi-definite.

I am interested in change:

A * vec(X)==b

for

abs(A * vec(X))==b

How can I perform that change?

Thanks in advance

%----------------------------EDIT-------------------------------

I am trying to modify some TFOCS functions in order to solve my problem.

Based in two examples provided with the software and in the user guide, I would like to construct my optimization problem:

EXAMPLE 1.
In example 1 the following problem is solved:

Min trace(C*X)
st  X>=0
    A*vec(X)==b

after some other operations, the tofcs_SCD function is finally called

tfocs_SCD(obj, aff, dualProxF, mu,x0, z0, opts)

where

obj=smooth_linear(C);
aff={1,0,A,b}
dualProxF={proj_psd, proj_Rn}

EXAMPLE 2.
In the second example, the following example is solved:

Min ||x||_1 + 1/2mu ||x||_2^2
st    ||Ax-b||_2<=eps

after some other operations, the tfocs_SCD function is finally called with:

obj=prox_l1;
aff={A,-b};
dualProxF=prox_l2(eps);

MY PROBLEM.
I want to solve:

Min trace(C*X)
st  X>=0 
    ||A*vec(X) -b||_2 <=eps 

I called tfocs_SCD with the following commands

obj=smooth_linear(C);
aff={A,-b};
dualProxF={proj_psd, prox_l2(eps)

Am I doing it ok?

Thanks in advance,
Ignacio


(Michael C. Grant) #2

No, I’m afraid that’s not possible. that’s not convex.


(Mark L. Stone) #3

But the stated optimization problem at the beginning of the post has <=, not == in the constraint, and is convex. So what problem is the OP really trying to solve?


#4

I think this problem is pretty common in “Phase Retrieval” problems. Althougt my problem is not related to imaging applications, it has a similar mathematical expressions. I have solved it with CVX for small cases without “non-convex” issues.


(Michael C. Grant) #5

You could not have specified abs(A*vec(X))==b in CVX. If you meant abs(A*vec(X))<=b then it’s fine. There is no way to modify SOLVER_SSDP to do what you want, either way.


(Michael C. Grant) #6

It’s certainly possible to solve your model using TFOCS, but not straightforward. You’ll need to use the “SCD” (smoothed conic dual) mode of TFOCS, as discussed in the paper & manual. TFOCS just isn’t as easy to use as CVX, I’m afraid.


#7

Yes, you are right. Actually, what I did is abs(A*vec(X))-b<=e
I know it is not as easy as CVX, I am going to give a try anyway because it is the only way that I know that it can be solved.
Thanks again


(Stephen Becker) #8

Here’s a solution for some of the formulations (e.g., A*vec(X) ~= b), with the CVX code and the TFOCS code:

n = 10;
m = round(n/2);
A = randn(m,n^2);
b = randn(m,1);
epsilon = .1;

%% Solve in CVX
cvx_begin
  cvx_precision best
  variable X(n,n)
  minimize trace(X)
  subject to
    X == semidefinite(n)
    norm( A*vec(X) - b, Inf ) <= epsilon
cvx_end
X_CVX = X;
%% Solve in TFOCS
linear  = linop_compose( linop_matrix(A), linop_vec([n,n]) );
affneF = { linear, -b };
objectiveF   = prox_trace;
dualproxF    = prox_l1(epsilon);
mu           = 0.1;
opts = struct('tol',1e-6,'maxIts',100);
opts.errFcn = @(fcn,dual,primal) norm( primal-X_CVX,'fro');
opts.continuation   = true;
x0   = zeros(n,n);
z0   = [];
[X,out,opts] = tfocs_SCD( objectiveF, affineF, dualproxF, mu, x0, z0, opts );