Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
An Invitation to Compressive Sensing Kapitel lesen Erstes Kapitel lesen

2013 | OriginalPaper | Buchkapitel

8. Advanced Tools from Probability Theory

verfasst von : Simon Foucart, Holger Rauhut

Erschienen in: A Mathematical Introduction to Compressive Sensing

Verlag: Springer New York

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

This chapter is dedicated to advanced probability results required in the more involved arguments on random measurement matrices, notably precise bounds for Gaussian random matrices and the analysis of random partial Fourier matrices. First, norms of Gaussian vectors in expectation are discussed, followed by Rademacher sums and the symmetrization principle. Khintchine inequalities provide bounds for moments of Rademacher sums. Then decoupling inequalities are covered. They allow one to simplify the analysis of double sums of random variables by replacing one instance of a random vector by an independent copy. The noncommutative Bernstein inequality treated next bounds the tail of a sum of independent random matrices in the operator norm. Dudley’s inequality bounds the supremum of a subgaussian process by an integral over covering numbers with respect to the index set of the process. Slepian’s and Gordon’s lemma compare certain functions of Gaussian vectors in terms of their covariance structures. Together with the concentration of measure principle for Lipschitz functions of Gaussian vectors covered next, they provide powerful tools for the analysis of Gaussian random matrices. Finally, the chapter discusses Talagrand’s inequality, i.e., a Bernstein-type inequality for suprema of empirical processes.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Basic Tools from Probability Theory
Nächstes Kapitel Sparse Recovery with Random Matrices
Literatur
2.
R. Adamczak, A tail inequality for suprema of unbounded empirical processes with applications to Markov chains. Electron. J. Probab. 13(34), 1000–1034 (2008)MathSciNetMATH
6.
R. Ahlswede, A. Winter, Strong converse for identification via quantum channels. IEEE Trans. Inform. Theor. 48(3), 569–579 (2002)MathSciNetMATHCrossRef
11.
K. Alexander, Probability inequalities for empirical processes and a law of the iterated logarithm. Ann. Probab. 12(4), 1041–1067 (1984)MathSciNetMATHCrossRef
22.
J.-M. Azais, M. Wschebor, Level Sets and Extrema of Random Processes and Fields (Wiley, Hoboken, NJ, 2009)MATHCrossRef
33.
A. Barvinok, Measure concentration. Lecture notes, University of Michigan, Michigan, USA, 2005
35.
I. Bechar, A Bernstein-type inequality for stochastic processes of quadratic forms of Gaussian variables. Preprint (2009)
59.
S. Boucheron, O. Bousquet, G. Lugosi, P. Massart, Moment inequalities for functions of independent random variables. Ann. Probab. 33(2), 514–560 (2005)MathSciNetMATHCrossRef
60.
S. Boucheron, G. Lugosi, P. Massart, Concentration inequalities using the entropy method. Ann. Probab. 31(3), 1583–1614 (2003)MathSciNetMATHCrossRef
61.
S. Boucheron, G. Lugosi, P. Massart, Concentration inequalities. A nonasymptotic theory of independence. Oxford University Press (2013)MATH
66.
J. Bourgain, L. Tzafriri, Invertibility of ‘large’ submatrices with applications to the geometry of Banach spaces and harmonic analysis. Isr. J. Math. 57(2), 137–224 (1987)MathSciNetMATHCrossRef
68.
O. Bousquet, A Bennett concentration inequality and its application to suprema of empirical processes. C. R. Math. Acad. Sci. Paris. 334(6), 495–500 (2002)MathSciNetMATHCrossRef
69.
O. Bousquet, Concentration inequalities for sub-additive functions using the entropy method. In Stochastic Inequalities and Applications, ed. by E. Gin, C. Houdr, D. Nualart. Progress in Probability, vol. 56 (Birkhäuser, Basel, 2003), pp. 213–247
74.
75.
A. Buchholz, Optimal constants in Khintchine type inequalities for fermions, Rademachers and q-Gaussian operators. Bull. Pol. Acad. Sci. Math. 53(3), 315–321 (2005)MathSciNetMATHCrossRef
142.
E. Davies, B. Simon, Ultracontractivity and the heat kernel for Schrödinger operators and Dirichlet Laplacians. J. Funct. Anal. 59, 335–395 (1984)MathSciNetMATHCrossRef
146.
V. de la Peña, E. Giné, Decoupling: From Dependence to Independence. Probability and its Applications (New York) (Springer, New York, 1999)
175.
R.M. Dudley, The sizes of compact subsets of Hilbert space and continuity of Gaussian processes. J. Funct. Anal. 1, 290–330 (1967)MathSciNetMATHCrossRef
184.
Y. Eldar, H. Rauhut, Average case analysis of multichannel sparse recovery using convex relaxation. IEEE Trans. Inform. Theor. 56(1), 505–519 (2010)MathSciNetCrossRef
193.
X. Fernique, Regularité des trajectoires des fonctions aléatoires gaussiennes. In École d’Été de Probabilités de Saint-Flour, IV-1974. Lecture Notes in Mathematics, vol. 480 (Springer, Berlin, 1975), pp. 1–96
194.
X. Fernique, Fonctions Aléatoires Gaussiennes, Vecteurs Aléatoires Gaussiens. Université de Montréal, Centre de Recherches Mathématiques, 1997
233.
234.
Y. Gordon, Elliptically contoured distributions. Probab. Theor. Relat. Field. 76(4), 429–438 (1987)MATHCrossRef
247.
L. Gross, Logarithmic Sobolev inequalities. Am. J. Math. 97(4), 1061–1083 (1975)
253.
U. Haagerup, The best constants in the Khintchine inequality. Studia Math. 70(3), 231–283 (1982), 1981MathSciNetMATH
260.
D. Hanson, F. Wright, A bound on tail probabilities for quadratic forms in independent random variables. Ann. Math. Stat. 42, 1079–1083 (1971)MathSciNetMATHCrossRef
296.
W.B. Johnson, J. Lindenstrauss (eds.), Handbook of the Geometry of Banach Spaces Vol I (North-Holland Publishing Co., Amsterdam, 2001)
301.
304.
305.
H. König, S. Kwapień, Best Khintchine type inequalities for sums of independent, rotationally invariant random vectors. Positivity. 5(2), 115–152 (2001)MathSciNetMATHCrossRef
306.
N. Kôno, Sample path properties of stochastic processes. J. Math. Kyoto Univ. 20(2), 295–313 (1980)MathSciNetMATH
307.
F. Krahmer, S. Mendelson, H. Rauhut, Suprema of chaos processes and the restricted isometry property. Comm. Pure Appl. Math. (to appear)
312.
M.A. Krasnosel’skij, Y.B. Rutitskij, Convex Functions and Orlicz Spaces. (P. Noordhoff Ltd., Groningen, The Netherlands, 1961), p. 249
319.
J. Lederer, S. van de Geer, The Bernstein-Orlicz norm and deviation inequalities. Preprint (2011)
320.
321.
M. Ledoux, The Concentration of Measure Phenomenon. AMS, 2001.
322.
M. Ledoux, M. Talagrand, Probability in Banach Spaces (Springer, Berlin, Heidelberg, NewYork, 1991)MATHCrossRef
326.
M. Lifshits, Lectures on Gaussian Processes. Springer Briefs in Mathematics (Springer, New York, 2012)
336.
F. Lust-Piquard, Inégalités de Khintchine dans C p \((1 < p < \infty )\). C. R. Math. Acad. Sci. Paris 303, 289–292 (1986)MathSciNetMATH
337.
339.
L. Mackey, M. Jordan, R. Chen, B. Farrell, J. Tropp, Matrix concentration inequalities via the method of exchangeable pairs. Preprint (2012)
343.
M. Marcus, L. Shepp, Sample behavior of Gaussian processes. In Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability (Univ. California, Berkeley, Calif., 1970/1971), Vol. II: Probability Theory, pp. 423–441. University of California Press, Berkeley, 1972
346.
P. Massart, Rates of convergence in the central limit theorem for empirical processes. Ann. Inst. H. Poincaré Probab. Statist. 22(4), 381–423 (1986)MathSciNetMATH
347.
P. Massart, About the constants in Talagrand’s concentration inequalities for empirical processes. Ann. Probab. 28(2), 863–884 (2000)MathSciNetMATHCrossRef
348.
P. Massart, Concentration Inequalities and Model Selection. Lecture Notes in Mathematics, vol. 1896 (Springer, Berlin, 2007)
360.
F. Nazarov, A. Podkorytov, Ball, Haagerup, and distribution functions. In Complex Analysis, Operators, and Related Topics. Operator Theory: Advances and Applications, vol. 113 (Birkhäuser, Basel, 2000), pp. 247–267
373.
R. Oliveira, Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges. Preprint (2009)
374.
380.
G. Peškir, Best constants in Kahane-Khintchine inequalities for complex Steinhaus functions. Proc. Am. Math. Soc. 123(10), 3101–3111 (1995)MATH
381.
G. Peškir, A.N. Shiryaev, The Khintchine inequalities and martingale expanding sphere of their action. Russ. Math. Surv. 50(5), 849–904 (1995)MATHCrossRef
391.
G. Pisier, Conditions d’entropie assurant la continuité de certains processus et applications à l’analyse harmonique. In Seminar on Functional Analysis, 1979–1980 (French), pp. 13–14, 43, École Polytech., 1980
392.
G. Pisier, The Volume of Convex Bodies and Banach Space Geometry. Cambridge Tracts in Mathematics (Cambridge University Press, Cambridge, 1999)
411.
H. Rauhut, Compressive sensing and structured random matrices. In Theoretical Foundations and Numerical Methods for Sparse Recovery, ed. by M. Fornasier. Radon Series on Computational and Applied Mathematics, vol. 9 (de Gruyter, Berlin, 2010), pp. 1–92
413.
H. Rauhut, J.K. Romberg, J.A. Tropp, Restricted isometries for partial random circulant matrices. Appl. Comput. Harmon. Anal. 32(2), 242–254 (2012)MathSciNetMATHCrossRef
421.
E. Rio, Inégalités de concentration pour les processus empiriques de classes de parties. Probab. Theor. Relat. Field. 119(2), 163–175 (2001)MathSciNetMATHCrossRef
422.
E. Rio, Une inégalité de Bennett pour les maxima de processus empiriques. Ann. Inst. H. Poincaré Probab. Stat. 38(6), 1053–1057 (2002)MathSciNetMATHCrossRef
430.
448.
459.
460.
M. Talagrand, Isoperimetry and integrability of the sum of independent Banach-space valued random variables. Ann. Probab. 17(4), 1546–1570 (1989)MathSciNetMATHCrossRef
461.
462.
463.
465.
466.
M. Talagrand, The Generic Chaining. Springer Monographs in Mathematics (Springer, Berlin, 2005)
467.
M. Talagrand, Mean Field Models for Spin Glasses. Volume I: Basic Examples (Springer, Berlin, 2010)
480.
J.A. Tropp, Norms of random submatrices and sparse approximation. C. R. Math. Acad. Sci. Paris 346(23–24), 1271–1274 (2008)MathSciNetMATHCrossRef
481.
486.
490.
A. Tsybakov, Introduction to Nonparametric Estimation. Springer Series in Statistics (Springer, New York, 2009)
500.
R. Vershynin, Frame expansions with erasures: an approach through the non-commutative operator theory. Appl. Comput. Harmon. Anal. 18(2), 167–176 (2005)MathSciNetMATHCrossRef
Metadaten
Titel
Advanced Tools from Probability Theory
verfasst von
Simon Foucart
Holger Rauhut
Copyright-Jahr
2013
Verlag
Springer New York
Buch
A Mathematical Introduction to Compressive Sensing

Print ISBN: 978-0-8176-4947-0

Electronic ISBN: 978-0-8176-4948-7

Copyright-Jahr: 2013

DOI
https://doi.org/10.1007/978-0-8176-4948-7_8