The norm of the inverse of n by n matrix with i.i.d. subgaussian entries is at most Cn^1.5/e with probability 1-e, if e>c/n^0.5

Analysis, Probability and Statistics 1 Minute

You need to know: Probability (denoted by P), mean, variance, normal distribution, abbreviation i.i.d. for independent identically distributed random variables, Euclidean space {\mathbb R}^n, notation |x| for length of x \in {\mathbb R}^n, matrix, matrix multiplication, inverse matrix, norm ||A||=\sup\limits_{x \in {\mathbb R}^n}\frac{|Ax|}{|x|} of n \times n matrix A.

Background: A random variable X is called subgaussian if there exist constants
B and b such that P(|X|>t) \leq Be^{-bt^2} for all t>0. For integer n>0, let A_{n,X} be an n \times n matrix whose entries a_{ij} are i.i.d. with the same distribution as X.

The Theorem: On 30th June 2005, Mark Rudelson submitted to the Annals of Mathematics a paper in which he proved the following result. Let X be a subgaussian random variable with mean 0 and variance 1. Then there are positive constants C_1, C_2, and C_3 such that for any integer n>0, and any \epsilon > C_1/\sqrt{n}, the inequality \|A_{n,X}^{-1}\| \leq C_2\cdot n^{3/2}/\epsilon holds with probability greater than 1-\epsilon/2-4e^{-C_3n}.

Short context: As a special case, the Theorem applies to matrices whose i.i.d. entries are equal to \pm 1 with equal chances (Bernoulli matrices). It is known that such random matrix A is invertible with probability exponentially close to 1. The Theorem provides a bound for the norm \|A^{-1}\| of the inverse matrix. The bound is polynomial in n and holds with probability greater than 1-\epsilon if n is large enough. Previously, similar bound was known only if i.i.d. entries a_{ij} of A follow the normal distribution.

Links: Free arxiv version of the original paper is here, journal version is here. See also Section 8.11 of this book for an accessible description of the Theorem.

Go to the list of all theorems

Unknown's avatar

Published by Bogdan Grechuk

Published

3 thoughts on “The norm of the inverse of n by n matrix with i.i.d. subgaussian entries is at most Cn^1.5/e with probability 1-e, if e>c/n^0.5”

  1. Pingback: The norm of the inverse of n by n matrix with i.i.d. Bernoulli entries is polynomially bounded with probability 1-1/n^C, for any C>0 – Theorems of the 21st century
  2. Pingback: The norm of the inverse of n by n matrix with i.i.d. subgaussian entries is at most n^0.5/e with probability 1-Ce-c^n – Theorems of the 21st century
  3. Pingback: Theorems of the 21st century

Leave a comment