Diminishing K-sparse parameter based Expander Graph Algorithms

Posted: September 4, 2010 in Uncategorized

Abstract: In this paper, I give my idea how to diminish K-sparse parameter which not to concern for aforementioned expander graph algorithms i.e. Sparse Matching Pursuit (SMP) and Sequence Sparse Matching Pursuit (SSMP).

Algorithms which combine geometrical and combinatorial methods have got a vast concerning in recently time since their performance are overwhelm others in aspect of  computing and update time, simplistic implement with modest requirement in storage. However, there is a significant notice from theory demonstration and simulation experiments in the coefficient of number measurement, it is greater five to ten times compare to the one of Linear Programming Algorithms. So, in the effort to reduces it, SMP and SSMP are deployed.

Their idea are similar to some state of the art algorithms, i.e. Subspace Pursuits and CoSaMP, which use voting-like mechanism and component-post-evaluating to select the best recover coefficients. This thing trades off  speed of algorithm a little bit O(log(N)) to a prominent improvement in required number measurement.

In the effort to reduce more, I would like to rudiment selection the best coefficients of the recovery  process and result in downgrading in computing time a order O(Nlong(N))  for an improvement  to approximate the limit bound in Expander Graph (~2Kd with d is the number of adjacent neighbors in an EG) . In addition,  to eliminate K-sparse parameter in the novel algorithm, I takes advantage of  finding components which makes minimum and maximum residue of signal and compare them to determine if stop algorithm or not.

For experiment and more detail,  I would like to refer to my paper :

Optimally Sequence Sparse Matching Pursuit.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s