Approximation of the average of some random matrices (Q785881): Difference between revisions

The focus of this paper is a major result of \textit{M. Rudelson} [J. Funct. Anal. 164, 60--72 (1999; Zbl 0929.46021)], which states that if a set of vectors \(u_i\in\mathbb{S}^{n-1}\) and positive real numbers \(c_i\) verify that \(\sum c_iu_i\otimes u_i=I\) (\(I\) is the identity on \(\mathbb{R}^d\)), then there exists a constant \(C>0\) such that the sum of a random sample consisting of \(Cd\log d\) of those products is close to \(I\). Here, the \(\log d\) factor cannot be removed. In this paper, the authors rely on Rudelson's proof to get the following more general result: for \(0<\varepsilon<1\), if \(Q_1,\dots,Q_k\) are \(k\) independent random matrices distributed according to probability distributions \(P_1,\dots,P_k\) on the set \(\mathcal{P}^d\) of \(d\times d\) positive real semi-definite matrices, such that \(\mathbb{E}Q_i=A\) for some \(A\in\mathcal{P}^d\), \(1\leq i\leq k\), and satisfying that \(c\bigl(1+\|A\|\bigr)\mathbb{E}\bigl(\max_i\|Q_i\|\bigr)\log d/\varepsilon^2\leq k\) (for some absolute constant \(c>0\)), then \(\mathbb{E}\left\|(1/k)\sum_iQ_i-A\right\|\leq\varepsilon\). Moreover, they show that the \(\log d\) term cannot be removed in this setting and that, in general, there is no good approximation of size \(O(d)\). Next, the authors show extensions of the above result to the case of non-symmetric matrices, the geometric motivation behind comes from the famous John theorem (see [\textit{F. John}, Studies Essays, pres. to R. Courant, 187--204 (1948; Zbl 0034.10503)]) and its extension by \textit{K. Ball} [Geom. Dedicata 41, No. 2, 241--250 (1992; Zbl 0747.52007)]. Indeed, a stability version of Rudelson's theorem is proved: if a convex body \(K\) is very close to the Euclidean ball, then the identity can be approximated with diadic products arising from \(O(d\log d)\) contact points. Applications to the study of the Banach-Mazur distance of convex bodies are obtained as a consequence.