Compressive sensing with non square matrices

Question

I'm implementing the algorithm in the following paper:

"Compressive sensing for wideband cognitive radios"

http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=04218361

However I've run into a problem with my solver for the linear program.

I need to solve a linear program where I minimise the $L_1$ norm of a vector subject to the constraint that the vector, when multiplied by some matrix equals a known set of measurements i.e. $$ \min \lVert x\rVert_{1} \text{ s.t } Ax=y. $$

The difficulty I'm facing is that $A$ is not necessarily a square matrix and so solvers like l1-magic using the primal dual algorithm won't work.

Can anyone suggest an algorithm/solver that will solve this type of convex optimisation problem?

Answer 1

Compressive sensing is all about non-square matrices, as the point is that we are dealing with the "undersampling" regime where we have less measurements than the ambient dimension.

I thought l1-magic works just fine. Did you try it? If you want a generic convex optimization toolbox, you might consider cvx also http://cvxr.com/cvx/.

Also related to compressed sensing, depending on what you want there's a jungle of solvers here (definitely way more than what you want): https://sites.google.com/site/igorcarron2/cs#reconstruction

---

If you use Cvx:

cvx_begin 
  variable z(N);
  minimize norm(z,1);
  subject to 
        Az==b;
cvx_end

This minimizes the $l^1$ norm over $Az=b$, and $z$ will hold the minimizer.

Answer 2

L_1 magic must be failing for a different reason than the fact that A is non-square. L_1 magic is specially geared toward solving compressive sensing problems for which A is rectangular (non square).

If it doesn't work out for you, here are potential reasons:

1. you are not trying to find the sparsest solution to this system of equation. i.e. the solution given by L_1 magic is not the one you are seeking.
2. A doesn't satisfy a necessary and sufficient condition for the recovery of sparse unknowns.
3. the number of rows of A is not large enough to find the sparsest solution to your problem

hope this helps.

Answer 3

What was the issue in the end?

I'm having a similar problem. I'm trying to use l1 magic to reconstruct an image from a single pixel camera I've developed. The test functions used are random binary patterns projected onto the object scene, so each pattern is represented as a row vector of 0's and 1's and form the rows of the test function matrix A. (To later be multiplied by a transform matrix to express the image in a basis where the coefficients are sparse)

However, this matrix is not positive definite, so the basis persuit function throws out an error. This is confusing me as most of the literature promotes using random test functions. Is there something wrong here? Do you have to ensure your "random" test functions eventually form a positive definite matrix?

Any help appreciated.

Answer 4

I've tried to recreate the code you were describing and got this below:

X = zeros(1,512);
positions = randi(512,[1,30]);
X(positions) = 1;
dctX = dct(X);
B = binornd(1,0.5,150,length(X));
y = B*X';
x0 = B'*y;
xhat = l1eq_pd(x0, B, [], y, 1e-3);

This generates a vector with 30 random spikes, then applies a dct and a random beroulli(0.5) matrix before solving an l1 program.This code works without a hitch for me.

Did you find out what was wrong?

Answer 5

Please refer to the following page for the correction of this line of code in 1leq_pd.m:

http://compsens.eecs.umich.edu/sensing_tutorial.php.

Once the code is updated, it works for me.