# 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?

%----------------------------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?

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