(北方工业大学图像处理与模式识别研究所,100144,北京)
摘 要 本文通过基于压缩感知理论(CS)的一类贪婪算法求解P0问题,由正交匹配追踪算法(OMP),进而引入匹配追踪算法(MP)和弱匹配追踪算法(WMP)以及逐步正交匹配追踪(StOMP)算法,同时我们将另一类基追踪算法(BP)用来做图像重构实验的对比。通过算例,我们将看到各种方法在重构结果上的优缺点对比。
关键词 压缩感知;贪婪算法;正交匹配追踪;图像重构
A family of Pursuit Algorithms and their performence in Image Reconstruction
Zou Jiancheng Zhang Li
(Institute 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.