nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

A Simple Tool for Bounding the Deviation of Random Matrices on Geometric Sets

verfasst von : Christopher Liaw, Abbas Mehrabian, Yaniv Plan, Roman Vershynin

Erschienen in: Geometric Aspects of Functional Analysis

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Let A be an isotropic, sub-gaussian m × n matrix. We prove that the process \(Z_{x}\,:=\,\left \|Ax\right \|_{2} -\sqrt{m}\left \|x\right \|_{2}\) has sub-gaussian increments, that is, \(\|Z_{x} - Z_{y}\|_{\psi _{2}} \leq C\|x - y\|_{2}\) for any \(x,y \in \mathbb{R}^{n}\). Using this, we show that for any bounded set \(T \subseteq \mathbb{R}^{n}\), the deviation of ∥ Ax ∥ ₂ around its mean is uniformly bounded by the Gaussian complexity of T. We also prove a local version of this theorem, which allows for unbounded sets. These theorems have various applications, some of which are reviewed in this paper. In particular, we give a new result regarding model selection in the constrained linear model.

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 Royen’s Proof of the Gaussian Correlation Inequality

Nächstes Kapitel On Multiplier Processes Under Weak Moment Assumptions

In this paper, we sometimes hide absolute constants in the inequalities marked \(\lesssim\).

Recall that a set T is called star-shaped if t ∈ T implies λt ∈ T for all λ ∈ [0, 1].

This restriction is not explicitly mentioned in the statement of Theorem 4.1 in [10], but it is used in the proof. Indeed, this result is derived from their Theorem 1.3, which explicitly requires that γ(T) be large enough. Without such requirement, Theorem 4.1 in [10] fails e.g. when T is a singleton, since in that case we have w(T) = 0.

D. Amelunxen, M. Lotz, M.B. McCoy, J.A. Tropp, Living on the edge: phase transitions in convex programs with random data. Inf. Inference 3 (3), 224–294 (2014). doi:10.1093/imaiai/iau005. http://dx.doi.org/10.1093/imaiai/iau005

S. Artstein-Avidan, A. Giannopoulos, V.D. Milman, Asymptotic geometric analysis. Part I, in Mathematical Surveys and Monographs, vol. 202 (American Mathematical Society, Providence, RI, 2015)

V. Chandrasekaran, B. Recht, P.A. Parrilo, A.S. Willsky, The convex geometry of linear inverse problems. Found. Comput. Math. 12 (6), 805–849 (2012)MathSciNetCrossRefMATH

S. Dirksen, Tail bounds via generic chaining. Electron. J. Probab. 20 (53), 1–29 (2015). doi:10.1214/EJP.v20-3760. http://dx.doi.org/10.1214/EJP.v20-3760

Y.C. Eldar, G. Kutyniok, Compressed Sensing: Theory and Applications (Cambridge University Press, Cambridge, 2012)CrossRef

S. Foucart, H. Rauhut, A mathematical introduction to compressive sensing, in Applied and Numerical Harmonic Analysis (Birkhäuser/Springer, New York, 2013) doi:10.1007/978-0-8176-4948-7. http://dx.doi.org/10.1007/978-0-8176-4948-7

Y. Gordon, On Milman’s inequality and random subspaces which escape through a mesh in R ⁿ, in Geometric Aspects of Functional Analysis (1986/87). Lecture Notes in Mathematics, vol. 1317 (Springer, Berlin, 1988), pp. 84–106. doi:10.1007/BFb0081737. http://dx.doi.org/10.1007/BFb0081737

D. Gross, Y.K. Liu, S.T. Flammia, S. Becker, J. Eisert, Quantum state tomography via compressed sensing. Phys. Rev. Lett. 105 (15), 150,401 (2010)

W.B. Johnson, J. Lindenstrauss, Extensions of Lipschitz mappings into a Hilbert space. Contemp. Math. 26 (1), 189–206 (1984)MathSciNetCrossRefMATH

10.

B. Klartag, S. Mendelson, Empirical processes and random projections. J. Funct. Anal. 225 (1), 229–245 (2005). doi:10.1016/j.jfa.2004.10.009. http://dx.doi.org/10.1016/j.jfa.2004.10.009

11.

G. Lecué, S. Mendelson, Learning subgaussian classes: upper and minimax bounds (2013). Available at http://arxiv.org/abs/1305.4825

12.

M. Lustig, D. Donoho, J.M. Pauly, Sparse MRI: The application of compressed sensing for rapid MR imaging. Magn. Reson. Med. 58 (6), 1182–1195 (2007)CrossRef

13.

S. Mendelson, A. Pajor, N. Tomczak-Jaegermann, Reconstruction and subgaussian operators in asymptotic geometric analysis. Geom. Funct. Anal. 17 (4), 1248–1282 (2007). doi:10.1007/s00039-007-0618-7. http://dx.doi.org/10.1007/s00039-007-0618-7

14.

V.D. Milman, Geometrical inequalities and mixed volumes in the local theory of Banach spaces. Astérisque 131, 373–400 (1985)MathSciNetMATH

15.

V.D. Milman, Random subspaces of proportional dimension of finite dimensional normed spaces: approach through the isoperimetric inequality, in Banach Spaces (Springer, Berlin, 1985), pp. 106–115MATH

16.

S. Oymak, C. Thrampoulidis, B. Hassibi, Simple bounds for noisy linear inverse problems with exact side information (2013). Available at http://arxiv.org/abs/1312.0641

17.

S. Oymak, C. Thrampoulidis, B. Hassibi, The squared-error of generalized lasso: a precise analysis, in 51st Annual Allerton Conference on Communication, Control, and Computing, IEEE (2013), pp. 1002–1009

18.

A. Pajor, N. Tomczak-Jaegermann, Subspaces of small codimension of finite-dimensional banach spaces. Proc. Am. Math. Soc. 97 (4), 637–642 (1986)MathSciNetCrossRefMATH

19.

Y. Plan, R. Vershynin, Robust 1-bit compressed sensing and sparse logistic regression: a convex programming approach. IEEE Trans. Inform. Theory 59 (1), 482–494 (2013). doi:10.1109/TIT.2012.2207945. http://dx.doi.org/10.1109/TIT.2012.2207945

20.

Y. Plan, R. Vershynin, The generalized lasso with non-linear observations. IEEE Trans. Inform. Theory 62 (3), 1528–1537 (2016). doi:10.1109/TIT.2016.2517008 MathSciNetCrossRef

21.

Y. Plan, R. Vershynin, E. Yudovina, High-dimensional estimation with geometric constraints (2014). Available at http://arxiv.org/abs/1404.3749

22.

M. Rudelson, R. Vershynin, Hanson-Wright inequality and sub-Gaussian concentration. Electron. Commun. Probab. 18 (82), 1–9 (2013). doi:10.1214/ECP.v18-2865. http://dx.doi.org/10.1214/ECP.v18-2865

23.

G. Schechtman, Two observations regarding embedding subsets of Euclidean spaces in normed spaces. Adv. Math. 200 (1), 125–135 (2006). doi:10.1016/j.aim.2004.11.003. http://dx.doi.org/10.1016/j.aim.2004.11.003

24.

M. Talagrand, The generic chaining: upper and lower bounds of stochastic processes, in Springer Monographs in Mathematics (Springer, Berlin, 2005)MATH

25.

C. Thrampoulidis, S. Oymak, B. Hassibi, Simple error bounds for regularized noisy linear inverse problems, in IEEE International Symposium on Information Theory (ISIT), IEEE (2014), pp. 3007–3011

26.

R. Vershynin, How close is the sample covariance matrix to the actual covariance matrix? J. Theor. Probab. 25 (3), 655–686 (2012)MathSciNetCrossRefMATH

27.

R. Vershynin, Introduction to the non-asymptotic analysis of random matrices, in Compressed Sensing (Cambridge University Press, Cambridge, 2012), pp. 210–268

28.

R. Vershynin, Estimation in high dimensions: a geometric perspective, in Sampling Theory, A Renaissance (Birkhauser, Basel, 2015), pp. 3–66CrossRefMATH

29.

J. Von Neumann, Collected Works, ed. by A.H. Taub (Pergamon, Oxford, 1961)

Titel: A Simple Tool for Bounding the Deviation of Random Matrices on Geometric Sets
verfasst von: Christopher Liaw
Abbas Mehrabian
Yaniv Plan
Roman Vershynin
Verlag: Springer International Publishing
Buch: Geometric Aspects of Functional Analysis
Print ISBN: 978-3-319-45281-4

Electronic ISBN: 978-3-319-45282-1

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-45282-1_18

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"