Norms of structured random matrices. (English) Zbl 1540.60010
For \( m,n\in\mathbb{N}\) let \(X = (X_{i, j})_{1\leq i \leq m,1\leq j\leq n}\) be a random matrix, \(A = (a_{i, j})_{ 1\leq i \leq m,1\leq j \leq n}\) be a deterministic matrix with real numbers as entries, and \(X_{A}= X\circ A\) the corresponding Hadamard product that is a structured random matrix. Bounds of the expected operator norm of \(X_{A}, \) considered as a random operator between \(\ell^{n}_{p}\) and \(\ell^{n}_{q}, 1\leq p, q \leq \infty,\) are studied. They are of optimal order and can be expressed in terms of the entries of the matrix \(A\). The understanding of such expressions and related quantities is relevant in the study of the worst-case error of optimal algorithms which are based on random information in function approximation problems, see [D. Krieg and M. Ullrich, Found. Comput. Math. 21, No. 4, 1141–1151 (2021; Zbl 1481.41014)], or the quality of random information for the recovery of vectors from an \(\ell\)-ellipsoid where the radius of the optimal information is given by Gelfand numbers of a diagonal operator, see [A. Hinrichs et al., J. Approx. Theory 293, Article ID 105919, 19 p. (2023; Zbl 1531.52005)].
For optimal bounds up to logarithmic terms when \(X\) has i. i. d. Gaussian entries, independent mean-zero bounded entries are deduced. Indeed, if \(D_{1}= || A\circ A: \ell^{n}_{p/2} \rightarrow\ell^{m}_{q/2} ||^{1/2}\) and \(D_{2}= || (A\circ A)^{T} :\ell^{m}_{q^{*}/2} \rightarrow\ell^{n}_{p^{*}/2} ||^{1/2},\) where \(p^{*}\) denotes the Hölder conjugate of \(p,\) then \[ D_{1} + D_{2} \lesssim \mathbb{E} ||X_{A}: l^{n}_{p} \rightarrow l^{m}_{q}||\lesssim (\ln( n) )^{1/p^{*}} (\ln( m))^{1/q}[ \sqrt{ \ln (mn)} D_{1} + \sqrt{ \ln (n)} D_{2}]. \] When one deals with particular ranges of \(p,q\) the precise order of the expected norm up to constants is determined.
The core of the paper are two conjectures. Conjecture 1 deals with estimates of \(\mathbb{E}||X_{A}:\ell^{n}_{p}\rightarrow\ell^{n}_{q}||.\) Conjecture 2 states that the boundedness of the linear operator \(X_{A}\) given by an infinite dimensional matrix \(A\) is equivalent to the fact that \(A\circ A\) defines a bounded linear operator between \(\ell_{p/2} (\mathbb{N})\) and \(\ell_{q/2} (\mathbb{N}),\) \((A\circ A)^{T}\) defines a bounded linear operator between \(\ell_{q^{*}/2} (\mathbb{N})\) and \(\ell_{p^{*}/2} (\mathbb{N}),\) as well as some extra conditions depending on the norms of the infinite row and column vectors of \(A\) and the values of \( p\) and \(q\) hold.
In addition to the cases \(p=q=2\) obtained in [R. Latała et al., Invent. Math. 214, No. 3, 1031–1080 (2018; Zbl 1457.60011)], and \(p=1, q\geq2\) proved in [O. Guédon et al., Lect. Notes Math. 2169, 151–162 (2017; Zbl 1366.60010)], in the paper under review Conjecture 1 is confirmed when \(p\in \{1,\infty\}, 1\leq q \leq \infty,\) and when \(q\in \{1,\infty\}, 1\leq p \leq \infty. \) In all the other cases, the upper bounds are proved only up to logarithmic (in the dimensions \(m,n\)) multiplicative factors. Conjecture 2 holds in the same situations as Conjecture 1 is stated.
The motivation of the problems analyzed in this paper is well stated, and the presentation is very friendly for a reader even without expertise in the topic.
For optimal bounds up to logarithmic terms when \(X\) has i. i. d. Gaussian entries, independent mean-zero bounded entries are deduced. Indeed, if \(D_{1}= || A\circ A: \ell^{n}_{p/2} \rightarrow\ell^{m}_{q/2} ||^{1/2}\) and \(D_{2}= || (A\circ A)^{T} :\ell^{m}_{q^{*}/2} \rightarrow\ell^{n}_{p^{*}/2} ||^{1/2},\) where \(p^{*}\) denotes the Hölder conjugate of \(p,\) then \[ D_{1} + D_{2} \lesssim \mathbb{E} ||X_{A}: l^{n}_{p} \rightarrow l^{m}_{q}||\lesssim (\ln( n) )^{1/p^{*}} (\ln( m))^{1/q}[ \sqrt{ \ln (mn)} D_{1} + \sqrt{ \ln (n)} D_{2}]. \] When one deals with particular ranges of \(p,q\) the precise order of the expected norm up to constants is determined.
The core of the paper are two conjectures. Conjecture 1 deals with estimates of \(\mathbb{E}||X_{A}:\ell^{n}_{p}\rightarrow\ell^{n}_{q}||.\) Conjecture 2 states that the boundedness of the linear operator \(X_{A}\) given by an infinite dimensional matrix \(A\) is equivalent to the fact that \(A\circ A\) defines a bounded linear operator between \(\ell_{p/2} (\mathbb{N})\) and \(\ell_{q/2} (\mathbb{N}),\) \((A\circ A)^{T}\) defines a bounded linear operator between \(\ell_{q^{*}/2} (\mathbb{N})\) and \(\ell_{p^{*}/2} (\mathbb{N}),\) as well as some extra conditions depending on the norms of the infinite row and column vectors of \(A\) and the values of \( p\) and \(q\) hold.
In addition to the cases \(p=q=2\) obtained in [R. Latała et al., Invent. Math. 214, No. 3, 1031–1080 (2018; Zbl 1457.60011)], and \(p=1, q\geq2\) proved in [O. Guédon et al., Lect. Notes Math. 2169, 151–162 (2017; Zbl 1366.60010)], in the paper under review Conjecture 1 is confirmed when \(p\in \{1,\infty\}, 1\leq q \leq \infty,\) and when \(q\in \{1,\infty\}, 1\leq p \leq \infty. \) In all the other cases, the upper bounds are proved only up to logarithmic (in the dimensions \(m,n\)) multiplicative factors. Conjecture 2 holds in the same situations as Conjecture 1 is stated.
The motivation of the problems analyzed in this paper is well stated, and the presentation is very friendly for a reader even without expertise in the topic.
Reviewer: Francisco Marcellán (Leganes)
MSC:
| 60B20 | Random matrices (probabilistic aspects) |
| 15B52 | Random matrices (algebraic aspects) |
| 46B09 | Probabilistic methods in Banach space theory |
| 52A23 | Asymptotic theory of convex bodies |
| 60G15 | Gaussian processes |
| 60E15 | Inequalities; stochastic orderings |
Keywords:
Gaussian random matrix; operator norm; structured random matrix; \(\psi_r\) random variableReferences:
| [1] | Achlioptas, D., Mcsherry, F.: Fast computation of low-rank matrix approximations, J. ACM 54(2), 9-es, (2007) · Zbl 1311.94031 |
| [2] | Adamczak, R.; Latała, R.; Litvak, AE; Pajor, A.; Tomczak-Jaegermann, N., Chevet type inequality and norms of submatrices, Studia Math., 210, 1, 35-56, 2012 · Zbl 1253.60005 |
| [3] | Adamczak, R., Latała, R., Puchała, Z., Życzkowski, K.: Asymptotic entropic uncertainty relations, J. Math. Phys. 57(3), 032204, 24, (2016) · Zbl 1379.94024 |
| [4] | Ailon, N.; Chazelle, B., The fast Johnson-Lindenstrauss transform and approximate nearest neighbors, SIAM J. Comput., 39, 1, 302-322, 2009 · Zbl 1185.68327 |
| [5] | Akemann, G., Baik, J., Di Francesco, P. (eds.): The Oxford handbook of random matrix theory. Oxford University Press, Oxford (2015) · Zbl 1321.15005 |
| [6] | Anderson, GW; Guionnet, A.; Zeitouni, O., An introduction to random matrices, Cambridge Studies in Advanced Mathematics, 2010, Cambridge: Cambridge University Press, Cambridge · Zbl 1184.15023 |
| [7] | Bandeira, AS; van Handel, R., Sharp nonasymptotic bounds on the norm of random matrices with independent entries, Ann. Probab., 44, 4, 2479-2506, 2016 · Zbl 1372.60004 |
| [8] | Bennett, G., Schur multipliers, Duke Math. J., 44, 3, 603-639, 1977 · Zbl 0389.47015 |
| [9] | Bennett, G.; Goodman, V.; Newman, CM, Norms of random matrices, Pac. J. Math., 59, 2, 359-365, 1975 · Zbl 0325.47018 |
| [10] | Benyamini, Y.; Gordon, Y., Random factorization of operators between Banach spaces, J. Anal. Math., 39, 45-74, 1981 · Zbl 0474.47010 |
| [11] | Boucheron, S., Lugosi, G., Massart, P.: Concentration inequalities, Oxford University Press, Oxford. A nonasymptotic theory of independence, With a foreword by Michel Ledoux (2013) · Zbl 1279.60005 |
| [12] | Bourgain, J.; Dirksen, S.; Nelson, J., Toward a unified theory of sparse dimensionality reduction in Euclidean space, Geom. Funct. Anal., 25, 4, 1009-1088, 2015 · Zbl 1341.46007 |
| [13] | Carl, B.; Maurey, B.; Puhl, J., Grenzordnungen von absolut-\((r,\, p)\)-summierenden Operatoren, Math. Nachr., 82, 205-218, 1978 · Zbl 0407.47010 |
| [14] | Chafaï, D.; Guédon, O.; Lecué, G.; Pajor, A., Interactions between compressed sensing random matrices and high dimensional geometry, Panoramas et Synthèses [Panoramas and Syntheses], 2012, Paris: Société Mathématique de France, Paris · Zbl 1396.94015 |
| [15] | Davidson, KR; Szarek, SJ, Local Operator Theory, Random Matrices and Banach Spaces, Handbook of the Geometry of Banach Spaces, 317-366, 2001, Amsterdam: North-Holland, Amsterdam · Zbl 1067.46008 |
| [16] | Foucart, S.; Rauhut, H., A Mathematical Introduction to Compressive Sensing, 2013, Birkhäuser/Springer, New York: Applied and Numerical Harmonic Analysis, Birkhäuser/Springer, New York · Zbl 1315.94002 |
| [17] | Friedland, O., Youssef, P.: Approximating matrices and convex bodies, Int. Math. Res. Not. IMRN (8), 2519-2537, (2019) · Zbl 1432.15017 |
| [18] | Gluskin, E. D.: Norms of random matrices and diameters of finite-dimensional sets, Mat. Sb. (N.S.) 120(162)(2), 180-189, 286, (1983) · Zbl 0528.46015 |
| [19] | Gluskin, ED; Kwapień, S., Tail and moment estimates for sums of independent random variables with logarithmically concave tails, Studia Math., 114, 3, 303-309, 1995 · Zbl 0834.60050 |
| [20] | Goldstine, HH; von Neumann, J., Numerical inverting of matrices of high order. II, Proc. Am. Math. Soc., 2, 188-202, 1951 · Zbl 0043.12301 |
| [21] | Gordon, Y., Some inequalities for Gaussian processes and applications, Israel J. Math., 50, 4, 265-289, 1985 · Zbl 0663.60034 |
| [22] | Gordon, Y.; Litvak, AE; Schütt, C.; Werner, EM, Geometry of spaces between polytopes and related zonotopes, Bull. Sci. Math., 126, 9, 733-762, 2002 · Zbl 1032.46016 |
| [23] | Guédon, O., Hinrichs, A., Litvak, A. E., Prochno, J.: On the expectation of operator norms of random matrices, Geometric aspects of functional analysis, Lecture Notes in Math., vol. 2169, Springer, Cham, (2017), pp. 151-162 · Zbl 1366.60010 |
| [24] | Guédon, O.; Mendelson, S.; Pajor, A.; Tomczak-Jaegermann, N., Majorizing measures and proportional subsets of bounded orthonormal systems, Rev. Mat. Iberoam., 24, 3, 1075-1095, 2008 · Zbl 1207.46015 |
| [25] | Guédon, O.; Rudelson, M., \(L_p\)-moments of random vectors via majorizing measures, Adv. Math., 208, 2, 798-823, 2007 · Zbl 1114.46008 |
| [26] | Haagerup, U.: The best constants in the Khintchine inequality, Studia Math. 70(3) (1981), 231-283 (1982) · Zbl 0501.46015 |
| [27] | Hinrichs, A., Krieg, D., Novak, E., Prochno, J., Ullrich, M.: On the power of random information, Multivariate Algorithms and Information-Based Complexity (F. J. Hickernell and P. Kritzer, eds.), De Gruyter, Berlin/Boston, (1994), pp. 43-64 |
| [28] | Hinrichs, A.; Krieg, D.; Novak, E.; Prochno, J.; Ullrich, M., Random sections of ellipsoids and the power of random information, Trans. Am. Math. Soc., 374, 12, 8691-8713, 2021 · Zbl 1501.60008 |
| [29] | Hinrichs, A., Prochno, J., Sonnleitner, M.: Random sections of \(\ell_p\)-ellipsoids, optimal recovery and Gelfand numbers of diagonal operators, (2021) |
| [30] | Hinrichs, A.; Prochno, J.; Vybíral, J., Gelfand numbers of embeddings of Schatten classes, Math. Ann., 380, 3-4, 1563-1593, 2021 · Zbl 1480.46018 |
| [31] | Hitczenko, P.; Montgomery-Smith, SJ; Oleszkiewicz, K., Moment inequalities for sums of certain independent symmetric random variables, Studia Math., 123, 1, 15-42, 1997 · Zbl 0967.60018 |
| [32] | Hoeffding, W., Probability inequalities for sums of bounded random variables, J. Am. Statist. Assoc., 58, 13-30, 1963 · Zbl 0127.10602 |
| [33] | Krieg, D.; Ullrich, M., Function values are enough for \(L_2\)-approximation, Found. Comput. Math., 21, 4, 1141-1151, 2021 · Zbl 1481.41014 |
| [34] | Kwapień, S., Decoupling inequalities for polynomial chaos, Ann. Probab., 15, 3, 1062-1071, 1987 · Zbl 0622.60026 |
| [35] | Landau, HJ; Shepp, LA, On the supremum of a Gaussian process, Sankhyā Ser. A, 32, 369-378, 1970 · Zbl 0218.60039 |
| [36] | Latała, R., Tail and moment estimates for sums of independent random vectors with logarithmically concave tails, Studia Math., 118, 3, 301-304, 1996 · Zbl 0847.60031 |
| [37] | Latała, R., Some estimates of norms of random matrices, Proc. Am. Math. Soc., 133, 5, 1273-1282, 2005 · Zbl 1067.15022 |
| [38] | Latała, R.; Strzelecka, M., Comparison of weak and strong moments for vectors with independent coordinates, Mathematika, 64, 1, 211-229, 2018 · Zbl 1429.60027 |
| [39] | Latała, R., Świątkowski, W.: Norms of randomized circulant matrices, Electron. J. Probab. 27, Paper No. 80, 23, (2022) · Zbl 1492.60016 |
| [40] | Latała, R.; van Handel, R.; Youssef, P., The dimension-free structure of nonhomogeneous random matrices, Invent. Math., 214, 3, 1031-1080, 2018 · Zbl 1457.60011 |
| [41] | Ledoux, M., The Concentration of Measure Phenomenon, Mathematical Surveys and Monographs, 2001, Providence, RI: American Mathematical Society, Providence, RI · Zbl 0995.60002 |
| [42] | Ledoux, M.: Deviation inequalities on largest eigenvalues, Geometric aspects of functional analysis, Lecture Notes in Math., Springer. Berlin 2007, 167-219 (1910) · Zbl 1130.15012 |
| [43] | Ledoux, M., Talagrand, M.: Probability in Banach spaces, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 23, Springer-Verlag, Berlin, (1991), Isoperimetry and processes · Zbl 0748.60004 |
| [44] | Linial, N.; London, E.; Rabinovich, Y., The geometry of graphs and some of its algorithmic applications, Combinatorica, 15, 2, 215-245, 1995 · Zbl 0827.05021 |
| [45] | Matlak, D.: Oszacowania norm macierzy losowych, Master’s thesis, Uniwersytet Warszawski, (2017) |
| [46] | Naor, A.; Regev, O.; Vidick, T., Efficient rounding for the noncommutative Grothendieck inequality, Theory Comput., 10, 257-295, 2014 · Zbl 1302.68323 |
| [47] | Puchała, Z., Rudnicki, Ł., Życzkowski, K.: Majorization entropic uncertainty relations, J. Phys. A 46(27), 272002, 12, (2013) · Zbl 1270.81116 |
| [48] | Rauhut, H.: Compressive sensing and structured random matrices, Theoretical foundations and numerical methods for sparse recovery, Radon Ser. Comput. Appl. Math., vol. 9, Walter de Gruyter, Berlin, (2010), pp. 1-92 · Zbl 1208.15027 |
| [49] | Riemer, S.; Schütt, C., On the expectation of the norm of random matrices with non-identically distributed entries, Electron. J. Probab., 18, 29, 13, 2013 · Zbl 1284.60019 |
| [50] | Rudelson, M., Vershynin, R.: Sampling from large matrices: an approach through geometric functional analysis, J. ACM 54(4), Art. 21, 19, (2007) · Zbl 1326.68333 |
| [51] | Seginer, Y., The expected norm of random matrices, Combin. Probab. Comput., 9, 2, 149-166, 2000 · Zbl 0969.15009 |
| [52] | Slepian, D., The one-sided barrier problem for Gaussian noise, Bell Syst. Tech. J., 41, 463-501, 1962 |
| [53] | So, A. M.-C.: Moment inequalities for sums of random matrices and their applications in optimization, Math. Program. 130(1), Ser. A, 125-151, (2011) · Zbl 1231.60007 |
| [54] | Spielman, D. A., Teng, S.-H.: Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems, Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing (New York, NY, USA), STOC ’04, Association for Computing Machinery, (2004), p. 81-90 · Zbl 1192.65048 |
| [55] | Strzelecka, M.: Estimates of norms of log-concave random matrices with dependent entries, Electron. J. Probab. 24, Paper No. 107, 15, (2019) · Zbl 1427.60014 |
| [56] | Talagrand, M., A new look at independence, Ann. Probab., 24, 1, 1-34, 1996 · Zbl 0858.60019 |
| [57] | Tropp, JA, Norms of random submatrices and sparse approximation, C. R. Math. Acad. Sci. Paris, 346, 23-24, 1271-1274, 2008 · Zbl 1170.46012 |
| [58] | Tropp, JA, On the conditioning of random subdictionaries, Appl. Comput. Harmon. Anal., 25, 1, 1-24, 2008 · Zbl 1143.15026 |
| [59] | Tropp, JA, User-friendly tail bounds for sums of random matrices, Foundations of Computational Mathematics, 12, 4, 389-434, 2012 · Zbl 1259.60008 |
| [60] | Tropp, J. A.: An introduction to matrix concentration inequalities, Foundations and Trends^®in Machine Learning 8(1-2), 1-230, (2015) · Zbl 1391.15071 |
| [61] | van Handel, R., On the spectral norm of Gaussian random matrices, Trans. Am. Math. Soc., 369, 11, 8161-8178, 2017 · Zbl 1423.60017 |
| [62] | van Handel, R.: Structured random matrices, Convexity and concentration, IMA Vol. Math. Appl., vol. 161, Springer, New York, (2017), pp. 107-156 · Zbl 1376.15029 |
| [63] | Vershynin, R., Introduction to the Non-asymptotic Analysis of Random Matrices, Compressed Sensing, 210-268, 2012, Cambridge: Cambridge Univ. Press, Cambridge |
| [64] | Vershynin, R: High-dimensional probability, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 47, Cambridge University Press, Cambridge, (2018), An introduction with applications in data science, With a foreword by Sara van de Geer · Zbl 1430.60005 |
| [65] | von Neumann, J.; Goldstine, HH, Numerical inverting of matrices of high order, Bull. Am. Math. Soc., 53, 11, 1021-1099, 1947 · Zbl 0031.31402 |
| [66] | Wigner, EP, Characteristic vectors of bordered matrices with infinite dimensions, Ann. Math. (2), 62, 548-564, 1955 · Zbl 0067.08403 |
| [67] | Wigner, EP, Characteristic vectors of bordered matrices with infinite dimensions, II. Ann. Math., 2, 65, 203-207, 1957 · Zbl 0077.31901 |
| [68] | Wigner, EP, On the distribution of the roots of certain symmetric matrices, Ann. Math., 2, 67, 325-327, 1958 · Zbl 0085.13203 |
| [69] | Wishart, J., The generalised product moment distribution in samples from a normal multivariate population, Biometrika, 20A, 1-2, 32-52, 1928 · JFM 54.0565.02 |
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.
