zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Iterative hard thresholding for compressed sensing. (English) Zbl 1174.94008
In the presented paper, it is shown that one of the previously by the authors developed iterative hard thresholding algorithms (termed IHTs) has similar performance guarantees to those of Compressed Sampling Matching Pursuit. Section 2 of the paper starts with a definition of sparse signal models and a statement of the compressed sensing problem. In Section 3, an iterative hard thresholding algorithm is discussed. The rest of the paper shows that this algorithm is able to recover, with high accuracy, signals from compressed sensing observations. This result is formally stated in the theorems of the first subsection of Section 4. The rest of Section 4 is devoted to the proof of the theorems. In fact, the derived result is near-optimal as shown in Section 5. Section 6 takes a closer look at a stopping criterion for the algorithm, which guarantees certain estimation accuracy. The results of the paper are similar to those for the Compressed Sampling Matching Pursuit algorithm and a more detailed comparison is given in Section 7. However, as discussed in Section 8, uniform guarantees are not the only consideration and in practice marked differences in the average performance of different methods are apparent. For many small problems, the restricted isometry property of random matrices is often too large to explain the behavior of the different methods. Furthermore, it has long been observed that the distribution of the magnitude of the non-zero coefficients also has an important influence on the performance of different methods. Whilst the theoretical guarantees derived in the presented and similar papers are important to understand the behavior of an algorithm, it is also clear that other facts have to be taken into account in order to predict the typical performance of algorithms in many practical situations.
94A20Sampling theory
94A13Detection theory
[1]Blumensath, T.; Davies, M.: Iterative thresholding for sparse approximations, J. Fourier anal. Appl. 14, No. 5, 629-654 (2008) · Zbl 1175.94060 · doi:10.1007/s00041-008-9035-z
[2]T. Blumensath, M. Davies, A simple, efficient and near optimal algorithm for compressed sensing, in: Proceedings of the Int. Conf. on Acoustics, Speech and Signal Processing, 2009
[3]Candès, E.; Romberg, J.: Quantitative robust uncertainty principles and optimally sparse decompositions, Found. comput. Math. 6, No. 2, 227-254 (2006) · Zbl 1102.94020 · doi:10.1007/s10208-004-0162-x
[4]Candès, E.; Romberg, J.; Tao, T.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE trans. Inform. theory 52, No. 2, 489-509 (2006) · Zbl 1231.94017 · doi:10.1109/TIT.2005.862083
[5]Candès, E.; Romberg, J.; Tao, T.: Stable signal recovery from incomplete and inaccurate measurements, Comm. pure appl. Math. 59, No. 8, 1207-1223 (2006) · Zbl 1098.94009 · doi:10.1002/cpa.20124
[6]Dai, W.; Milenkovic, O.: Subspace pursuit for compressive sensing signal reconstruction, IEEE trans. Inform. theory 55, No. 5, 2230-2249 (2009)
[7]Donoho, D.: Compressed sensing, IEEE trans. Inform. theory 52, No. 4, 1289-1306 (2006)
[8]Gorodnitsky, I. F.; George, J. S.; Rao, B. D.: Neuromagnetic source imaging with focuss: A recursive weighted minimum norm algorithm, Neurophysiology 95, No. 4, 231-251 (1995)
[9]N.G. Kingsbury, T.H. Reeves, Iterative image coding with overcomplete complex wavelet transforms, in: Proc. Conf. on Visual Communications and Image Processing, 2003
[10]Mallat, S.; Davis, G.; Zhang, Z.: Adaptive time – frequency decompositions, SPIE J. Opt. eng. 33, No. 7, 2183-2191 (1994)
[11]Mendelson, S.; Pajor, A.; Tomczak-Jaegermann, N.: Reconstruction and subgaussian operators in asymptotic geometric analysis, Geom. funct. Anal. 17, 1248-1282 (2007) · Zbl 1163.46008 · doi:10.1007/s00039-007-0618-7
[12]Mendelson, S.; Pajor, A.; Tomczak-Jaegermann, N.: Uniform uncertainty principle for Bernoulli and subgaussian ensembles, Constr. approx. 28, No. 3, 277-289 (2008) · Zbl 1230.46011 · doi:10.1007/s00365-007-9005-8
[13]Needell, D.; Tropp, J. A.: Cosamp: iterative signal recovery from incomplete and inaccurate samples, Appl. comput. Harmon. anal. 26, No. 3, 301-321 (2009) · Zbl 1163.94003 · doi:10.1016/j.acha.2008.07.002
[14]Needell, D.; Vershynin, R.: Signal recovery from incomplete and inacurate measurements via regularized orthogonal matching pursuit
[15]Needell, D.; Vershynin, R.: Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit, Found. comput. Math. 9, 317-334 (2009) · Zbl 1183.68739 · doi:10.1007/s10208-008-9031-3
[16]Nyquist, H.: Certain topics in telegraph transmission theory, Trans. A.I.E.E., 617-644 (1928)
[17]M. Rudelson, R. Vershynin, Sparse reconstruction by convex relaxation: Fourier and gaussian measurements, in: 40th Annual Conference on Information Sciences and Systems, 2006
[18]Shannon, C. A.; Weaver, W.: The mathematical theory of communication, (1949) · Zbl 0041.25804
[19]Tropp, J. A.; Gilbert, A. C.: Signal recovery from partial information via orthogonal matching pursuit, IEEE trans. Inform. theory 53, No. 12, 4655-4666 (2006)
[20]Vetterli, M.; Marziliano, P.; Blu, T.: Sampling signals with finite rate of innovation, IEEE trans. Signal process. 50, No. 6, 1417-1428 (2002)