Approximation of the average of some random matrices

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

l n d

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

C d

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.

Review text

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.

Recommendations

Cites work

Cited in

(8)

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)