Comments on Nuit Blanche: Compressed Sensing: Subspace Pursuit Code, Fast Ma...

In a simple example,length of sparse vector=N=5num...

2008-04-14T08:08:00.000-05:00

In a simple example,length of sparse vector=N=5
number of measured samples=M=4
Sparsity=S=2

Creating Partial fourier matrix(without randomizing the rows) and normalizing its columns
F=dftmtx(N);
F=normalize(F(1:M,:));
I have sparse vector x
x=[0 0 0 0.6820 0.5253];

The RIP condition
(1-delta)norm(x)^2 <= norm(Fx)^2 <= (1+delta) norm(x)^2

is satisfied for delta=0.11(<1.0)

But if we see the eigen values of matrix F*F are[0.75,1.25] which doesnot lie between [1-delta,1+delta]
Hence even if for some sparse vector x,the RIP condition is satisfied but it doesnt imply about the bounds on eigen values.

Thanks
Samra

Samra,Do you have an example ?Igor.

2008-04-11T05:33:00.000-05:00

Samra,

Do you have an example ?

Igor.

Hi,If i want to check the Restricted Isometry prop...

2008-04-10T08:53:00.000-05:00

Hi,

If i want to check the Restricted Isometry property for measurement matrix F,it should satisfy fo all S-sparse vectors x,the following relationship,

(1-delta)norm(x)^2 <= norm(Fc)^2 <= (1+delta) norm(x)^2

In the paper of Candes Decoding by Linear Programming,its written that if above condition is satisfied,all eigen values of (F*F),where F* is the Hermitian of F,should lie between (1-delta) and (1+delta).

I have a question regarding eigen values of F*F.I have checked there may exist F which satsifies the above Restricted Isometry for all S sparse vectors but still the eigen values of F*F may not lie between (1-delta) and (1+delta)?
Can anybody clarify this.

Thanks
Samra

Samra,The beginning of an answer:http://www.acm.ca...

2008-03-20T12:29:00.000-05:00

Samra,

The beginning of an answer:

http://www.acm.caltech.edu/~wakin/papers/randProjManifolds-03june2007.pdf

"....Whitney’s Embedding Theorem [29] actually suggests for certain K-dimensional manifolds that the number of measurements need be no larger than 2K +1 to ensure an embedding. However, as it offers no guarantee of stability, the practical recovery of a signal on the manifold could be complicated. Interestingly, the number 2K also arises in CS as the number of random measurements required to embed the set of all K-sparse signals (but again with no
guarantee on the conditioning of the recovery problem); see [3]..."

[3] is this reference:
http://www.dsp.ece.rice.edu/cs/DCS112005.pdf

and it explains that the reason we need more than 2K measurements has to do with the fact that we are solving an l_1 problem (where 2K measurements are needed) instead of an l_0 (where only K measurements would be Ok). Somehow, there is an inefficiency in using basis pursuit as opposed to the combinatorial approach. The ratio between the two 2K/K could be the reason why the isometry constant is for 2S in the 1S-sparse case.

I know it does not answer specifically your question, but I seem to have read something specific on this 2S-3S restricted isometry constant in one of Candes's paper but I can't find it for the moment.

Maybe you could ask Candes directly ?

Igor.

Thanks igor,1)I have infact first looked at paper ...

2008-03-20T11:50:00.000-05:00

Thanks igor,

1)I have infact first looked at paper by Candes,but I couldnot understand why we are looking at isometry constants corresponding to twice or three times the actual sparsity of a signal.I mean why we dont look at simply isometry constant values corresponding to S sparse signal(not higher).
2)In the Candes paper on Compressed Sensing,I have constructed Gaussian measurement matrix as explained in Candes paper page 9 and made simulation to give corresponding isometry constants which turn out to be much higher(0.8-0.9).

Thanks
Samra

Samra,Quick answer, some of these results have bee...

2008-03-20T10:25:00.000-05:00

Samra,

Quick answer, some of these results have been shown in some of the papers of Candes, check out the first papers in :

http://www.google.com/search?&q=isometry+site%3Ahttp%3A%2F%2Fwww.acm.caltech.edu%2F%7Eemmanuel

Igor.

Hi,While reading and implementing CS basics,want t...

2008-03-20T08:43:00.000-05:00

Hi,

While reading and implementing CS basics,want to ask restricted isometric property.

1)If signal is S-sparse,inorder to have perfect reconstruction,why do we require the measurement matrix(such as gaussian etc) should satisfy isometry property for 2S or 3S sparse signals?

2)I have checked through simulations that for gaussian measurement matrix,the isometry property is only satisfied if signal has very few nonzeros,where as with fourier measurement matrix,we get isometry property satsified for larger values of sparsity S.Does this happen actually?

Thanks
Samra