Hello,

Yes, OMP needs the sparsity level as an input.

See Algorithm 3 in:

http://www.stat.yale.edu/~snn7/courses/stat679fa13/references/omptrogil.pdf

thank you amirafshar

 if OMP requires sparsity of the original signal how sparseLAB toolbox is able to reconstruct the original signal with out giving sparsity as one of the input parameter, do you know any OMP methods like in sparseLAB tool box where they are not using sparsity of the original signal for reconstruction

Hi,

Yes it does require the sparsity. Please find a code we wrote in our group. Notice that the greedy selection is done q times (where q is the size of the support of the sparse vector). 

When the greedy OMP algorithm runs more than q times, i think one of the following happens: 

- It either reselects the previous entries.

- or it overestimates the sparse support.

You need to check what happens.

BR,

Ahmad. 

Actually SparseLAB needs also sparsity level as an input. The 3rd input parameter "maxIters" defined as "number of atoms in the decomposition" which is also the sparsity level.

BR,

Amir

thank you ahmad and amirafshar

hello,

while i was performing monte-carlo simulations of  ''probabilty of exact recovery vs sparsity''  using IID gaussian measurement matrix with OMP and BP(Basis pursuit) for sparse signal recovery(sparse in time domain), the BP is acting almost same for all the type of input sparse signals(like guassian distributed elements,  +1/-1 elements) but OMP is showing better performance(better than BP) for Guassian distributed elements than random +1/-1 elements. why is OMP behaving differently for different input signals and what is its reliability.

Hi,

I am confused  a little bit. What do you mean by "different input signals"?

Somewhere you said matrix, and somewhere else you said sparse signals.

hello amirafshar

usually we have y=Ax form in that A which is measurement matrix (here i had choosen as IID guassian measurement matrix)

the different time sprase signals  x  are obtained by choosing 

i) elements of x  from guassian distribution

ii) elements as random +1/-1 with probability 1/2

In all these cases OMP is behaving differently for different x's . where as BP is behaving almost similar to all these type of signals, is OMP reliable?

hi

In one of the paper they had given that if the input signal is near to zero it has strong effect on greedy methods. so while i was doing the experiment i had used randn and it has mean 0 and variance 1 that may be the reason for the unpredictable behavior of OMP for that particular input signal.

But they hadnt given the reason can any one help

There are (at least) two ways you can control the number of iterations for OMP. You can explicitly specify the support size. Thus, you are interested in recovering exactly K non-zero coefficients in the representation of the signal. Alternatively, you may specify a threshold on the residual obtained during the reconstruction. In this case, you are not specifying the support size explicitly. OMP keeps on going till residual is below the specified threshold. These different ways of controlling the ending of OMP algorithm are known as halting criteria.

You can read more about OMP in my tutorial notes at https://sparse-plex.readthedocs.io/en/latest/book/pursuit/omp/index.html