Rank minimization with TFOCS


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

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


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

How can I perform that change?

Thanks in advance


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:

In example 1 the following problem is solved:

Min trace(C*X)
st  X>=0

after some other operations, the tofcs_SCD function is finally called

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


dualProxF={proj_psd, proj_Rn}

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:


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

dualProxF={proj_psd, prox_l2(eps)

Am I doing it ok?

Thanks in advance,

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

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?

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.

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.

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.

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

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_precision best
  variable X(n,n)
  minimize trace(X)
  subject to
    X == semidefinite(n)
    norm( A*vec(X) - b, Inf ) <= epsilon
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 );
1 Like