Iterative thresholding for sparse approximations. (English) Zbl 1175.94060

Summary: Sparse signal expansions represent or approximate a signal using a small number of elements from a large collection of elementary waveforms. Finding the optimal sparse expansion is known to be NP hard in general and non-optimal strategies such as matching pursuit, orthogonal matching pursuit, basis pursuit and basis pursuit de-noising are often called upon. These methods show good performance in practical situations, however, they do not operate on the \(\ell _{0}\) penalised cost functions that are often at the heart of the problem.
In this paper we study two iterative algorithms that are minimising the cost functions of interest. Furthermore, each iteration of these strategies has computational complexity similar to a matching pursuit iteration, making the methods applicable to many real world problems. However, the optimisation problem is non-convex and the strategies are only guaranteed to find local solutions, so good initialisation becomes paramount. We here study two approaches. The first approach uses the proposed algorithms to refine the solutions found with other methods, replacing the typically used conjugate gradient solver. The second strategy adapts the algorithms and we show on one example that this adaptation can be used to achieve results that lie between those obtained with matching pursuit and those found with orthogonal matching pursuit, while retaining the computational complexity of the matching pursuit algorithm.


94A20 Sampling theory in information and communication theory
94A13 Detection theory in information and communication theory
68Q25 Analysis of algorithms and problem complexity
41A46 Approximation by arbitrary nonlinear expressions; widths and entropy
90C27 Combinatorial optimization
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
68W25 Approximation algorithms
68W40 Analysis of algorithms


Full Text: DOI Link


[1] Donoho, D.L., Vetterli, M., DeVore, R.A., Daubechies, I.: Data compression and harmonic analysis. IEEE Trans. Inf. Theory 44, 2435–2476 (1998) · Zbl 1125.94311 · doi:10.1109/18.720544
[2] Mallat, S., Falzon, F.: Analysis of low bit rate image transform coding. IEEE Trans. Signal Process. 46, 1027–1042 (1998) · doi:10.1109/78.668554
[3] Donoho, D.L.: De-noising by soft-thresholding. IEEE Trans. Inf. Theory 41(3), 613–627 (1995) · Zbl 0820.62002 · doi:10.1109/18.382009
[4] Davies, M., Mitianoudis, N.: A simple mixture model for sparse overcomplete ICA. IEE Proc. Vis. Image Signal Process. 151, 35–43 (2004) · doi:10.1049/ip-vis:20040304
[5] Blumensath, T., Davies, M.: Sparse and shift-invariant representations of music. IEEE Trans. Audio, Speech Lang. Process. 14, 50–57 (2006) · doi:10.1109/TSA.2005.860346
[6] Donoho, D.L., Elad, M.: Optimally-sparse representation in general (non-orthogonal) dictionaries via l1 minimization. Proc. Natt. Acad. Sci. 100, 2197–2202 (2003) · Zbl 1064.94011 · doi:10.1073/pnas.0437847100
[7] Tropp, J.: Just relax: Convex programming methods for identifying sparse signals in noise. IEEE Trans. Inf. Theory 51(3), 1031–1051 (2006) · Zbl 1288.94025
[8] Mallat, S.: A Wavelet Tour of Signal Processing. Academic, New York (1999) · Zbl 0998.94510
[9] Davis, G.: Adaptive nonlinear approximations. PhD thesis, New York University (1994) · Zbl 0854.94005
[10] Natarajan, B.K.: Sparse approximate solutions to linear systems. SIAM J. Comput. 24, 227–234 (1995) · Zbl 0827.68054 · doi:10.1137/S0097539792240406
[11] Mallat, S., Zhang, Z.: Matching pursuits with time-frequency dictionaries. IEEE Trans. Signal Process. 41(12), 3397–3415 (1993) · Zbl 0842.94004 · doi:10.1109/78.258082
[12] Tropp, J.A.: Greed is good: algorithmic results for sparse approximation. IEEE Trans. Inf. Theory 50(10), 2231–2242 (2004) · Zbl 1288.94019 · doi:10.1109/TIT.2004.834793
[13] Gribonval, R., Vandergheynst, P.: On the exponential convergence of matching pursuits in quasi-incoherent dictionaries. IEEE Trans. Inf. Theory 52(1), 255–261 (2006) · Zbl 1309.94038 · doi:10.1109/TIT.2005.860474
[14] Murray, J.F., Kreutz-Delgado, K.: An improved FOCUSS-based learning algorithm for solving sparse linear inverse problems. In: Conf. Record of the Thirty-Fifth Asilomar Conf. on Signals, Systems and Computers, pp. 347–351 (2001)
[15] Chen, S.S., Donoho, D.L., Saunders, M.A.: Atomic decomposition by basis pursuit. SIAM J. Sci. Comput. 20(1), 33–61 (1998) · Zbl 0919.94002 · doi:10.1137/S1064827596304010
[16] Daubechies, I., Defries, M., De Mol, C.: An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. Commun. Pure Appl. Math. 57, 1413–1457 (2004) · Zbl 1077.65055 · doi:10.1002/cpa.20042
[17] Bect, J., Blanc Féraud, L., Aubert, G., Chambolle, A.: In: A l1-Unified Variational Framework for Image Restoration. Lecture Notes in Computer Sciences, vol. 3024, pp. 1–13. Springer, New York (2004) · Zbl 1098.68728
[18] Elad, M.: Why simple shrinkage is still relevant for redundant representation. IEEE Trans. Inf. Theory 52(12), 5559–5569 (2006) · Zbl 1309.94035 · doi:10.1109/TIT.2006.885522
[19] Elad, M., Matalon, B., Zibulevsky, M.: Coordinate and subspace optimization methods for linear least squares with non-quadratic regularization. Appl. Comput. Harmon. Anal. 23, 346–367 (2007) · Zbl 1133.65022 · doi:10.1016/j.acha.2007.02.002
[20] Candès, E., Romberg, J.: Practical signal recovery from random projections. In: Proc. SPIE Conf., Wavelet Applications in Signal and Image Processing XI, Jan. 2005
[21] Bredies, K., Lorenz, D.A.: Iterated hard shrinkage for minimization problems with sparsity constraints (2006) · Zbl 1170.46067
[22] Kingsbury, N.G.: Complex wavelets for shift invariant analysis and filtering of signals. J. Appl. Comput. Harmon. Anal. 10, 234–253 (2001) · Zbl 0990.94005 · doi:10.1006/acha.2000.0343
[23] Herrity, K.K., Gilbert, A.C., Tropp, J.A.: Sparse approximation via iterative thresholding. In: Proceedings of the Int. Conf. on Acoustics, Speech and Signal Processing, 2006
[24] Nowak, R., Figueiredo, M.: Fast wavelet-based image deconvolution using the EM algorithm. In: Proceedings of the 35th Asilomar Conference on Signals, Systems, and Computers, (Monterey), November 2001
[25] Figueiredo, M., Nowak, R.: An EM algorithm for wavelet-based image restoration. IEEE Trans. Image Process. 12(8), 906–916 (2003) · Zbl 1279.94015 · doi:10.1109/TIP.2003.814255
[26] Starck, J., Nguyen, M., Murtagh, F.: Wavelet and curvelet for image deconvolution: A combined approach. J. Signal Process. 83(10), 2279–2283 (2003) · Zbl 1145.94329 · doi:10.1016/S0165-1684(03)00150-6
[27] Elad, M., Matalon, B., Shtok, J., Zibulevsky, M.: A wide-angle view at iterated shrinkage algorithms. In: SPIE (Wavelet XII) (San-Diego, CA, USA), August 2007
[28] Combettes, P.L., Wajs, V.R.: Signal recovery by proximal forward-backward splitting. SIAM J. Multiscale Model. Simul. 4, 1168–1200 (2005) · Zbl 1179.94031 · doi:10.1137/050626090
[29] Lange, K., Hunter, D.R., Yang, I.: Optimization transfer using surrogate objective functions. J. Comput. Graph. Stat. 9, 1–20 (2006)
[30] Lange, K.: Optimization. Springer, New York (2004)
[31] Landweber, L.: An iterative formula for Fredholm integrals of the first kind. Am. J. Math. 73, 615–624 (1951) · Zbl 0043.10602 · doi:10.2307/2372313
[32] Kingsbury, N.G., Reeves, T.H.: Iterative image coding with overcomplete complex wavelet transforms. In: Proc. Conf. on Visual Communications and Image Processing, 2003
[33] Donoho, D., Tsaig, Y., Drori, I., Starck, J.: Sparse solutions of underdetermined linear equations by stagewise orthogonal matching pursuit (2006) · Zbl 1365.94069
[34] Krustulovic, S., Gribonval, R.: MPTK: Matching pursuit made tractable. In: Proc. Int. Conf. on Acoustic Speech and Signal Processing (Toulouse, France), May 2006
[35] Rudin, W.: Principles of Mathematical Analysis. McGraw-Hill, New York (1976) · Zbl 0346.26002
[36] Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1985) · Zbl 0576.15001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.