Sparse Recovery Problem Solution

Hello all,

I am working on a communication system where I physically have Np triplets {hp,taup,ap}. From these Np triplets I can build the exact channel matrix.

In practice however I need to estimate the channel. To estimate the channel I first build the dictionaries tau of cardinality Nt and a of cardinality Na. From these dictionaries I form the equation Ax=z, where z is the noisy observation vector, A=[Gamma1*Lambda1*s ... Gamma1*LambdaNt*s .... GammaNa*Lambda1*s .... GammaNa*LambdaNt*s] and x=[x(1,1) ...x(1,Nt) .... x(Na,Nt)]=[x1 ... x_NaNt]. s is the known pilot symbols.

Obviously, x is sparse, and I am using the Basis Pursuit (BP) algorithm to find it. The problem is that when solving the problem x contains much more that Np non-zero elements. How can I find Np unique triplets from Ax=z? This means there is no two triplets share the same hp, taup or ap?

Thanks

[Matt J]

From what I understand, A and x are both supposed to be Na x Nt matrices. If so, then explain the equation Ax=z. The left hand side can't be a matrix-vector multiplication if both A and x are Na x Nt. So how is the equation to be interpreted? You have Na*Nt unknowns. How do you get as many equations?

And why is x "obviously" sparse?

[S. David]

Actually A is N-by-(Na*Nt) matrix and x is (Na*Nt)-by-1 vector. Each Gamma_b for b=1,...,Na and Lambda_t for t=1,...,Nt are N-by-N square matrix. The noisy observation vector z and the pilot vector s are both N-by-1 vectors.

Note that Gamma_b*Lambda_t corresponds to the bth entry of the dictionary a, and t th entry of dictionary tau. Hence x contains the channel gains that correspond to each combination of a and tau entries, which are Na*Nt combinations. So, x contains Na*Nt>>Np entries, where Np is the actual number of physical paths. That is why x is obviously sparse.

I hope this answers your question.

Note: The cardinality of dictionary a is Na not Np and Na>Np.

[Matt J]

What code are you using to solve the BP problem? Maybe there is a problem in your implementation of that.

[Cedric]

He provided the code in this thread.

[S. David]

Thanks Cedric Wannaz.

Actually, I have found a set of algorithms on the Internet and I used one of them, which is Basis Pursuit (BP). I don't know how the algorithm is implemented, because it is not my scope. I am just using it.

[Matt J]

Did you test the BP code on simpler problems to see if it gives reasonable results? What about something with a predictable result, like the problem

 min norm(x,1)
 s.t. ones(1,N)*x=1

[S. David]

How to write this problem in the form Ax=z to test it? and what is expected result of this?

[Matt J]

Isn't it obvious that A=ones(1,N) and z=1? How were you interpreting your previous A*x=z if not the constraints of an L1 minimization problem?

The solution I would expect is an x of the form

   x=zeros(N,1);
   x(j)=1;

This is the sparsest solution you can have: only 1 non-zero element.

[S. David]

Thanks for explanation.

Indeed, just one entry, which is the first entry of the solution, is 1 and the rest are zeros.