Approximation of the average of some random matrices

DOI10.1016/J.JFA.2020.108684MaRDI QIDQ785881zbMATH OpenOpenAlexFDO

Authors Márton Naszódi, Aleksandr A. Polyanskii, Grigory M. Ivanov

Publication date 12 August 2020

Published in Journal of Functional Analysis (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1909.08316

zbMATH Keywords

John decompositionLust-Picard inequalitymatrix approximationpositive definite matricesRudelson's theorem

Mathematics Subject Classification ID

Miscellaneous inequalities involving matrices (15A45) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Random matrices (algebraic aspects) (15B52) Local theory of Banach spaces (46B07) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) Inequalities and extremum problems involving convexity in convex geometry (52A40)

Abstract: Rudelson's theorem states that if for a set of unit vectors $u_i$ and positive weights $c_i$, we have that $sum{c}_i{u}_{i}otimes{u}_i$ is the identity operator $I$ on ${mathbbR}^d$, then the sum of a random sample of $Cdlnd$ of these diadic products is close to $I$. The $lnd$ term cannot be removed. On the other hand, the recent fundamental result of Batson, Spielman and Srivastava and its improvement by Marcus, Spielman and Srivastava show that the $lnd$ term can be removed, if one wants to show the existence of a good approximation of $I$ as the average of a few diadic products. It is known that essentially the same proof as Rudelson's yields a more general statement about the average of positive semi-definite matrices. First, we give an example of an average of positive semi-definite matrices where there is no approximation of this average by $Cd$ elements. Thus, the result of Batson, Spielman and Srivastava cannot be extended to this wider class of matrices. Next, we present a stability version of Rudelson's result on positive semi-definite matrices, and thus, extend it to certain non-symmetric matrices. This yields applications to the study of the Banach--Mazur distance of convex bodies. Finally, we show that in some cases, one needs to take a subset of the vectors of order $d^2$ to approximate the identity.

Recommendations

• Random vectors in the isotropic position
• Estimating the probability that a given vector is in the convex hull of a random sample
• Random polytopes obtained by matrices with heavy-tailed entries
• Sudakov-type minoration for Gaussian chaos processes
• scientific article; zbMATH DE number 4076218
• Convex geometry. Abstracts from the workshop held December 17--23, 2006.
• Invertibility via distance for noncentered random matrices with continuous distributions
• Bounded law of iterated logarithm for matrix-normalized sums of independent random vectors

Cites work

• Approximating matrices and convex bodies
• Contact points of convex bodies
• Ellipsoids defined by Banach ideal norms
• Ellipsoids of maximal volume in convex bodies
• scientific article; zbMATH DE number 3951374 (Why is no real title available?)
• scientific article; zbMATH DE number 194266 (Why is no real title available?)
• scientific article; zbMATH DE number 1216173 (Why is no real title available?)
• scientific article; zbMATH DE number 1149836 (Why is no real title available?)
• scientific article; zbMATH DE number 3052220 (Why is no real title available?)
• Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem
• John's decomposition in the general case and applications
• John's decomposition of the identity in the non-convex case
• John's theorem for an arbitrary pair of convex bodies
• Non commutative Khintchine and Paley inequalities
• On contact points of convex bodies
• Random vectors in the isotropic position
• Sampling convex bodies: a random matrix approach
• Sparse sums of positive semidefinite matrices
• Sums of random Hermitian matrices and an inequality by Rudelson
• The expected norm of a sum of independent random matrices: an elementary approach
• The masked sample covariance estimator: an analysis using matrix concentration inequalities
• Twice-Ramanujan sparsifiers

Cited in

(8)

• Random vectors in the isotropic position
• Upper and lower bounds for matrix discrepancy
• Counting formulas associated with some random matrix averages
• Sampling convex bodies: a random matrix approach
• Average approximation of tensor product-type random fields of increasing dimension
• No-dimension Tverberg's theorem and its corollaries in Banach spaces of type \(P\)
• Approximating matrices and convex bodies
• Two observations regarding embedding subsets of Euclidean spaces in normed spaces

This page was built for publication: Approximation of the average of some random matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q785881)