1
$\begingroup$

Using the FISTA Algorithm for compressive sensing from https://github.com/tiepvupsu/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');



enter image description here

enter image description here

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

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

$\endgroup$
  • $\begingroup$ FISTA solves LASSO problem. The recovery of the sparse atoms or locations depend on the regularization parameter used to induce sparsity via the $\ell_1$-norm. Perhaps, you might want to tune your regularization parameter. $\endgroup$ – Maxtron Jul 19 '19 at 18:25
  • $\begingroup$ ok great thanks, i increased the regularization parameter from 0.01 to 1 and get useful results. Don't really understand why though $\endgroup$ – Mr Vinagi Jul 22 '19 at 8:14
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.