On the interval of fluctuation of the singular values of random matrices

  • Olivier Guédon

    University Paris-Est, Marne-la-Vallée, France
  • Alexander E. Litvak

    University of Alberta, Edmonton, Canada
  • Alain Pajor

    University Paris-Est, Marne-la-Vallée, France
  • Nicole Tomczak-Jaegermann

    University of Alberta, Edmonton, Canada
On the interval of fluctuation of the singular values of random matrices cover
Download PDF

A subscription is required to access this article.

Abstract

Let AA be a matrix whose columns X1,,XNX_1,\dots, X_N are independent random vectors in Rn\mathbb R^n. Assume that the tails of the 1-dimensional marginals decay as P(Xi,at)Ctp\mathbb P(|\langle X_i, a\rangle|\geq t)\leq C t^{-p} uniformly in aSn1a\in S^{n-1} and iNi\leq N. Then for p>4p>4 we prove that with high probability A/nA/\sqrt{n} has the Restricted Isometry Property (RIP) provided that Euclidean norms Xi|X_i| are concentrated around n\sqrt{n}. We also show that the covariance matrix is well approximated by empirical covariance matrices and establish corresponding quantitative estimates on the rate of convergence in terms of the ratio n\/Nn\/N. Moreover, we obtain sharp bounds for both problems when the decay is of the type exp (tα)(-t^{\alpha}), with α(0,2]\alpha \in (0,2], extending the known case α(1,2]\alpha \in (1,2].

Cite this article

Olivier Guédon, Alexander E. Litvak, Alain Pajor, Nicole Tomczak-Jaegermann, On the interval of fluctuation of the singular values of random matrices. J. Eur. Math. Soc. 19 (2017), no. 5, pp. 1469–1505

DOI 10.4171/JEMS/697