Why Does FISTA Algorithm Not Work for Signed Signals?

Question

Using the FISTA Algorithm for compressive sensing from Tiep H. Vu - FISTA, I created the matlab example below.

I created 2 sparse signals x_signed and x_pos, where the latter only contains positive values.

Using opts.pos = false as input to the FISTA, I assume, that the algorithm also works for signed input signals.

As visible, the FISTA algorithm is able to perfectly reconstruct x_pos, but not x_signed.

s = rng(5);
close all;
nrbins = 5;
N = 120;
m = 24;
%create input signals
x_pos = [round(10*rand(nrbins,1));zeros(N-nrbins,1)];
x_signed = [10*randn(nrbins,1);zeros(N-nrbins,1)];

%random shuffle
x_signed = x_signed(randperm(size(x_signed,1)));
x_pos = x_pos(randperm(size(x_pos,1)));

%Compressive Measurements on positive signal
A = 0.5*(sign(randn(m,N))+ones(m,N));
y = A*x_pos;

opts.pos = true;
opts.lambda = 0.01;
opts.tol = 1e-14;
opts.max_iter = 1000;
xrec_pos = fista_lasso(y,A,[],opts);

%Compressive Measurements on signed signal

A = 0.5*(sign(randn(m,N))+ones(m,N));
ysigned = A*x_signed;

opts.pos = false;
opts.lambda = 0.01;
opts.tol = 1e-14;
opts.max_iter = 1000;
xrec_signed = fista_lasso(ysigned,A,[],opts);



%plot positive
figure;
scatter(1:size(x_pos,1),x_pos);
hold on;
plot(xrec_pos);

legend('x','xrec\_pos');

%plot signed
figure;
scatter(1:size(x_signed,1),x_signed);
hold on;
plot(xrec_signed);

legend('x','xrec\_signed');

How can I reconstruct a signed signal using the FISTA algorithm?

For what reason does the option "pos" exist? Does it have performance implications?

Answer 1

I will try explaining why would someone use such an option as defining the solution as positive.
The Proximal Gradient Method which is the hurt of the FISTA algorithm is basically a generalization of Projected (Sub) Gradient Descent Method.
As such, if one knows that the solution lies in a Convex Set and one knows the projection onto that set one could utilize it inside the method by a projection step.

Hence, if you know your solution is indeed in the convex set of the positive orthant you should use that information by projection the solution onto this set.
The projection is fairly simple:

$$ {P}_{ \mathbb{R}_{+}^{n} } \left( y \right) = \arg \min_{x \in \mathbb{R}_{+}^{n}} {\left\| x - y \right\|}_{2}^{2} = \max \left( y, 0 \right) $$

This is actually implemented in the package you linked to in the Proj files.
For instant, in the latest version of proj_l1.m you can see the code:

if opts.pos 
    X = max(0, U - lambda);
else 
    X = max(0, U - lambda) + min(0, U + lambda);
end

Which implements the projection onto the $ {L}_{1} $ norm ball and the positive orthant as written above.