International E-publication: Publish Projects, Dissertation, Theses, Books, Souvenir, Conference Proceeding with ISBN.  International E-Bulletin: Information/News regarding: Academics and Research

Sparse Signal Recovery based on Hybrid Genetic Algorithm

    , , ,

Author Affiliations

  • 1Department of Electronic Engineering, Faculty of Engineering and Technology International Islamic University Islamabad, PAKISTAN
  • 2 Department of Electronic Engineering, Air University, Institute of Signals, Systems and Soft computing (ISSS), Islamabad, PAKISTAN
  • 3 Department of Electrical Engineering, COMSATS Institute of Information Technology, Islamabad, PAKISTAN

Res. J. Recent Sci., Volume 3, Issue (5), Pages 86-93, May,2 (2014)

Abstract

This paper introduces a novel technique of recovering an S-sparse signal from lesser number of random measurements (under sampled signal) using hybrid genetic algorithm (GA). The proposed method uses a chromosome-based cross over to produce the off springs with better fitness. The l_0minimizationconstraint is directly incorporated in population to achieve the desired sparsity level. The slow and premature convergence of GA is prevented with the help of modified parallel coordinate descent (PCD) algorithm. This hybrid mechanism of GA along with modified PCD makes the sparse signal recovery faster and accurate. The performance of the proposed algorithm is verified by comparing its results with those of PCD and separable surrogate functional (SSF) algorithms. The effectiveness of hybrid GA is further demonstrated experimentally by faithfully recovering a synthetic one-dimensional sparse signal. The simulation results show that an accurate sparse signal reconstruction is possible with hybrid GA using only a small number of observations.

References

  1. Needell D., Tropp J. and Vershynin R. Greedy signal recovery review, Signals, Systems and Computers, 2nd Asilomar Conference, 1048-1050, IEEE (2008)
  2. Tropp J.A. and Wright S.J., Computational methods for sparse solution of linear inverse problems, Proc. IEEE, 98(6), 948 -958 (2010)
  3. Olver Shakiban, Applied linear algebra, ISBN-13: 9780131473829 (2005)
  4. Cand E.J., egrave;s and M.B. Wakin, An introduction to compressive sampling, IEEE Signal Process Mag., 25(2), 21-30 (2008)
  5. Schmidt M., Least squares optimization with 11-norm regularization, Technical report, (2005)
  6. Beck Amir and Marc Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems,SIAM Journal on Imaging Sciences, 2(1), 183-202 (2009)
  7. Lustig M., Donoho D.L., Santos J.M. and Pauly J.M.,Compressed sensing MRI, Signal Processing Magazine, IEEE, 25(2), 72-82 (2008)
  8. Gorodnitsky Irina F., Bhaskar D. Rao, Sparse signal reconstruction from limited data using FOCUSS: A reweighted minimum norm algorithm, Signal Processing, IEEE Transactions, 45(3), 600-616 (1997)
  9. Candès E., Romberg J. and Tao T., Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Trans.Inform. Theory, 52(2), 489–509 (2006)
  10. Candès E., Romberg J. and Tao T., Stable signal recovery from incomplete and inaccurate measurements, Comm. Pure Appl. Math 59(8), 1207–1223 (2006)
  11. D. Donoho, Compressed sensing, IEEE Trans. Inform. Theory, 52(4),1289–1306 (2006)
  12. Mendelson S., Pajor A. and Tomczak-Jaegermann N., Uniform uncertainty principle for Bernoulli and subgaussian ensembles. Constructive Approximation, 28(3),277-289 (2008)
  13. Baraniuk, Richard G. Compressive sensing [lecture notes], Signal Processing Magazine, IEEE, 24(4), 118-121 (2007)
  14. Tibshirani R., Regression shrinkage and selection via the lasso, Journal of the Royal Statistical Society, Series B (Methodological), 267-288 (1996)
  15. Chen S.S., Donoho D.L. and Saunders M.A., Atomic decomposition by basis pursuit, SIAM journal on scientific computing, 20(1), 33-61 (1998)
  16. Grant Michael and Stephen Boyd, CVX: Matlab software for disciplined convex programming (web page and software), URL http://stanford. edu/boyd/cvx (2008)
  17. Candes E., Romberg J., l1-magic: Recovery of sparse signals via convex programming, URL: www. acm. caltech. edu/l1magic/downloads/l1magic. pdf, 4 (2005)
  18. Tropp J.A. and Gilbert A.C., Signal recovery from random measurements via orthogonal matching pursuit, Information Theory, IEEE Transaction, 53(12), 4655-4666 (2007)
  19. Needell D. and Tropp J.A., Cosamp: iterative signal recovery from incomplete and inaccurate samples, Communications of the ACM, 53(12), 93-100 (2010)
  20. Tropp J.A., Greed is good: Algorithmic results for sparse approximation, Information Theory, IEEE Transactions, 50(10), 2231-2242 (2004)
  21. Elad M., Sparse and redundant representations: from theory to applications in signal and image processing,Springer, (2010)
  22. Blumensath T. and Davies M.E. Iterative hard thresholding for compressed sensing. Applied and Computational Harmonic Analysis, 27(3), 265-274 (2009)
  23. Wipf David P. and Bhaskar D. Rao., Sparse Bayesian learning for basis selection, Signal Processing, IEEE Transactions, 52(8), 2153-2164 (2004)
  24. Chartrand R., Exact reconstruction of sparse signals via nonconvex minimization, Signal Processing Letters, IEEE, 14(10), 707-710 (2007)
  25. Hastie T., Tibshirani R. and Friedman J., Linear Methods for Regression, Springer New York, (2009)
  26. Mohimani, G. Hosein, MassoudBabaie-Zadeh, Christian Jutten, Complex-valued sparse representation based on smoothed 0 norm, Acoustics, Speech and Signal Processing, IEEE International Conference, 3881-3884 (2008)
  27. Haupt Randy L., Sue Ellen Haupt. Practical genetic algorithms, John Wiley & Sons, (2004)
  28. Craenen B.G.W., A.E. Eiben, E. Marchiori, How to handle constraints with evolutionary algorithms, Practical Handbook of Genetic Algorithms: Applications, 341-361,(2001)
  29. Rocha, Miguel, José Neves, Preventing premature convergence to local optima in genetic algorithms via random offspring generation, Multiple Approaches to Intelligent Systems, Springer Berlin Heidelberg, 127-136 (1999)
  30. Elad M., Why simple shrinkage is still relevant for redundant representations?, Information Theory, IEEE Transactions, 52(12), 5559-5569 (2006)