Matching Pursuit Optimization Based on Quantum Genetic Algorithm

Abstract:

The Matching Pursuit algorithm (MP) utilizes an iterative procedure to project a given waveform onto a particular dictionary, and uses a greedy strategy to optimize the signal approximation at each step. The computation complexity of MP is very high. In this paper we propose an improved decomposition algorithm based on MP and Quantum Genetic Algorithm (QGA), which is called Quantum Genetic Matching Pursuit (QGMP). The improved algorithm can not only get the best matching atom, but also greatly reduce the computation complexity of MP and, therefore, makes the MP can be used in practical system.

• Periodical: Advanced Materials Research (Volume 950)
• Pages: 221-226
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.950.221
• Online since: June 2014
• Authors: Lei Chen*, Lai Bo Zheng, Sheng Ping Qin
• Keywords: Atomic Decomposition, Matching Pursuit, Quantum Genetic Algorithm

References

[1] Cohen, Leon. Time-frequency distributions-a review., Proceedings of the IEEE 77. 7 (1989): 941-981.

[2] Mallat, Stephane G., and Zhifeng Zhang. Matching pursuits with time-frequency dictionaries., Signal Processing, IEEE Transactions on 41. 12 (1993): 3397-3415.

DOI: 10.1109/78.258082

[3] Mallat, Stephane G., and M. Avellaneda. Greedy adaptive approximation.,J. Constr. Approx 13 (1997): 57-98.

DOI: 10.1007/bf02678430

[4] da Silva, Adelino R. Ferreira. Atomic decomposition with evolutionary pursuit., Digital signal processing 13. 2 (2003): 317-337.

DOI: 10.1016/s1051-2004(02)00028-3

[5] Q. Gao, A study of genetic algorithms and its applications in fault diagnosis. Dissertation, Xi'an Jiaotong University, PRC, (2005).

[6] McClure, Mark R., and Lawrence Carin. Matching pursuits with a wave-based dictionary., Signal Processing, IEEE Transactions on 45. 12 (1997): 2912-2927.

DOI: 10.1109/78.650250

[7] Narayanan, Ajit, and Mark Moore. Quantum-inspired genetic algorithms., Evolutionary Computation, 1996., Proceedings of IEEE International Conference on. IEEE, (1996).

DOI: 10.1109/icec.1996.542334

[8] Han, Kuk-Hyun, and Jong-Hwan Kim. Genetic quantum algorithm and its application to combinatorial optimization problem., Evolutionary Computation, 2000. Proceedings of the 2000 Congress on. Vol. 2. IEEE, (2000).

DOI: 10.1109/cec.2000.870809

[9] Lobo, Arthur P., and Philipos C. Loizou. Voiced/unvoiced speech discrimination in noise using gabor atomic decomposition. " Acoustics, Speech, and Signal Processing, 2003. Proceedings. (ICASSP, 03). 2003 IEEE International Conference on. Vol. 1. IEEE, (2003).

DOI: 10.1109/icassp.2003.1198907

[10] Qian, Shie, and Dapang Chen. Signal representation using adaptive normalized Gaussian functions., Signal processing 36. 1 (1994): 1-11.

DOI: 10.1016/0165-1684(94)90174-0

[11] Herley, Cormac, et al. Tilings of the time-frequency plane: Construction of arbitrary orthogonal bases and fast tiling algorithms., Signal Processing, IEEE Transactions on 41. 12 (1993): 3341-3359.

DOI: 10.1109/78.258078

[12] Nielsen, Michael A., and Isaac L. Chuang. Quantum computation and quantum information. Cambridge university press, (2010).

[13] Shor, Peter W. Algorithms for quantum computation: discrete logarithms and factoring., Foundations of Computer Science, 1994 Proceedings, 35th Annual Symposium on. IEEE, (1994).

DOI: 10.1109/sfcs.1994.365700

[14] Yang, Junan, Bin Li, and Zhenquan Zhuang. Research of Quantum Genetic Algorith and its application in blind source separation., Journal of Electronics (China) 20. 1 (2003): 62-68.

DOI: 10.1007/s11767-003-0089-4

[15] Zhang, Ge-xiang, et al. Novel quantum genetic algorithm and its applications., Frontiers of Electrical and Electronic Engineering in China 1. 1 (2006): 31-36.