（北方工業大學圖像處理與模式識別研究所，100144，北京）
摘 要 本文通過基于壓縮感知理論（CS）的一類貪婪算法求解P0問題，由正交匹配追蹤算法（OMP），進而引入匹配追蹤算法（MP）和弱匹配追蹤算法（WMP）以及逐步正交匹配追蹤（StOMP）算法，同時我們將另一類基追蹤算法（BP）用來做圖像重構實驗的對比。通過算例，我們將看到各種方法在重構結果上的優缺點對比。
關鍵詞 壓縮感知；貪婪算法；正交匹配追蹤；圖像重構
A family of Pursuit Algorithms and their performence in Image Reconstruction
Zou Jiancheng Zhang Li
�。↖nstitute of Image Processing and Pattern Recognition, North China Univ. of Tech.,
100144, Beijing, China)
Abstract This paper mainly focus on solving P0 problem using a family of greedy algorithms which is based on the Compressed Sensing (CS) , from OMP algorithm, we are introducing MP WMP and other variants algorithm like StOMP, still we'll compare with another BP algorithm base on different idea but in fact doing the same performance. In the examples, we'll see their performance on image reconstruction, from the comparison of the result, we'll tell each one's advantages and disadvantages.
Keywords Compressed Sensing；Greedy algorithm； OMP； Image Reconstruction
參 考 文 獻
[1]. L.A. Karlovitz, Construction of nearest points in the , p even and norms, Journal of Approximation Theory, 3:123–127, 1970.
[2]. V.N. Temlyakov, Greedy algorithms and m-term approximation, Journal of Approximation
Theory, 98:117–145, 1999.
[3]. A. Cohen, R.A. DeVore, P. Petrushev, and H. Xu, Nonlinear approximation and the space BV(IR2), American Journal of Mathematics, 121(3):587-628, June,1999.
[4]. G. Davis, S. Mallat, and M. Avellaneda, Adaptive greedy approximations, Journal of Constructive Approximation, 13:57–98, 1997.
[5]. G. Davis, S. Mallat, and Z. Zhang, Adaptive time-frequency decompositions, Optical-Engineering, 33(7):2183–91, 1994.
[6]. R.A. DeVore and V. Temlyakov, Some Remarks on Greedy Algorithms, Advances in Computational Mathematics, 5:173–187, 1996.
[7]. I.F. Gorodnitsky and B.D. Rao, Sparse signal reconstruction from limited data using FOCUSS: A re-weighted norm minimization algorithm, IEEE Trans. On Signal Processing, 45(3):600–616, 1997.
[8]. R. Gribonval and P. Vandergheynst, On the exponential convergence of Matching Pursuits in quasi-incoherent dictionaries, IEEE Trans. Information Theory,52(1):255–261, 2006.
[9]. S. Mallat, A Wavelet Tour of Signal Processing, Academic-Press, 1998.
[10]. S. Mallat and Z. Zhang, Matching pursuits with time-frequency dictionaries,IEEE Trans. Signal Processing, 41(12):3397–3415, 1993.
[11]. D. Needell and J. A. Tropp, CoSaMP: Iterative signal recovery from incompleteand inaccurate samples, Applied Computational Harmonic Analysis, 26:301–321, May 2009.
[12]. B.D. Rao and K. Kreutz-Delgado, An affine scaling methodology for best basis selection, IEEE Trans. on signal processing, 47(1):187–200, 1999.
[13]. S.S. Chen, D.L. Donoho, and M.A. Saunders, Atomic decomposition by basis pursuit, SIAM Journal on Scientific Computing, 20(1):33–61 (1998).
[14]. S.S. Chen, D.L. Donoho, and M.A. Saunders, Atomic decomposition by basis pursuit, SIAM Review, 43(1):129–159, 2001.
[15]. V.N. Temlyakov, Weak greedy algorithms, Advances in Computational Mathematics,5:173–187, 2000.
[16]. J.A. Tropp, Greed is good: Algorithmic results for sparse approximation, IEEE Trans. On Information Theory, 50(10):2231–2242, October 2004.
[17]. I. Daubechies, M. Defrise, and C. De-Mol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Communications on Pure and Applied Mathematics, LVII:1413–1457, 2004.
[18]. D.L. Donoho, De-noising by soft thresholding, IEEE Trans. on Information Theory, 41(3):613–627, 1995.
