Advances in Random Matrix Theory-Let there be tools.ppt

1、10/9/2018,1,Advances in Random Matrix Theory: Let there be tools,Alan Edelman Brian Sutton, Plamen Koev, Ioana Dumitriu, Raj Rao and others MIT: Dept of Mathematics, Computer Science AI Laboratories World Congress, Bernoulli Society Barcelona, Spain Wednesday July 28, 2004,10/9/2018,2,Message,Ingred

2、ient: Take Any important mathematics Then Randomize! This will have many applications! We cant keep this in the hands of specialists anymore: Need tools!,10/9/2018,3,Tools,So many applications Random matrix theory: catalyst for 21st century special functions, analytical techniques, statistical techn

3、iques In addition to mathematics and papers Need tools for the novice! Need tools for the engineers! Need tools for the specialists!,10/9/2018,4,Themes of this talk,Tools for general beta What is beta? Think of it as a measure of (inverse) volatility in “classical” random matrices. Tools for complic

4、ated derived random matrices Tools for numerical computation and simulation,5,Wigners Semi-Circle,The classical S known as the Gaussian Orthogonal Ensemble Normalized eigenvalue histogram is a semi-circle Precise statements require n etc.,n=20; s=30000; d=.05; %matrix size, samples, sample dist e=;

5、%gather up eigenvalues im=1; %imaginary(1) or real(0) for i=1:s,a=randn(n)+im*sqrt(-1)*randn(n);a=(a+a)/(2*sqrt(2*n*(im+1); v=eig(a); e=e v; end hold off; m x=hist(e,-1.5:d:1.5); bar(x,m*pi/(2*d*n*s); axis(square); axis(-1.5 1.5 -1 2); hold on; t=-1:.01:1; plot(t,sqrt(1-t.2),r);,10/9/2018,6,sym matr

6、ix to tridiagonal form,Same eigenvalue distribution as GOE:O(n) storage ! O(n2) compute,10/9/2018,7,General beta,beta: 1: reals 2: complexes 4: quaternions,Bidiagonal Version corresponds To Wishart matrices of Statistics,10/9/2018,8,Tools,Motivation: A condition number problem Jack & Hypergeometric

7、of Matrix Argument MOPS: Ioana Dumitrius talk The Polynomial Method The tridiagonal numerical 109 trick,10/9/2018,9,Tools,Motivation: A condition number problem Jack & Hypergeometric of Matrix Argument MOPS: Ioana Dumitrius talk The Polynomial Method The tridiagonal numerical 109 trick,10/9/2018,10,

8、Numerical Analysis: Condition Numbers,(A) = “condition number of A” If A=UV is the svd, then (A) = max/min . Alternatively, (A) = max (AA)/ min (AA) One number that measures digits lost in finite precision and general matrix “badness” Small=good Large=bad The condition of a random matrix?,10/9/2018,

9、11,Von Neumann & co.,Solve Ax=b via x= (AA) -1A bM A-1Matrix Residual: |AM-I|2|AM-I|2 2002 n How should we estimate ?Assume, as a model, that the elements of A are independent standard normals!,10/9/2018,12,Von Neumann & co. estimates (1947-1951),“For a random matrix of order n the expectation value

10、 has been shown to be about n”Goldstine, von Neumann“ we choose two different values of , namely n and 10n”Bargmann, Montgomery, vN“With a probability 1 10n”Goldstine, von Neumann,X ,10/9/2018,13,Random cond numbers, n,Distribution of /n,Experiment with n=200,10/9/2018,14,Finite n,n=10 n=25n=50 n=10

11、0,10/9/2018,15,Condition Number Distributions,P(/n x) 2/x,P(/n2 x) 4/x2,Real n x n, n,Complex n x n, n,Generalizations: : 1=real, 2=complex finite matrices rectangular: m x n,10/9/2018,16,Condition Number Distributions,P(/n x) 2/x,P(/n2 x) 4/x2,Real n x n, n,Complex n x n, n,Square, n: P(/n x) (2-1/

12、()/x (All Betas!) General Formula: P(x) C/x (n-m+1),where = (n-m+1)/2th moment of the largest eigenvalue of Wm-1,n+1 ()and C is a known geometrical constant.Density for the largest eig of W is known in terms of 1F1(/2)(n+1), (/2)(n+m-1); -(x/2)Im-1) from which is availableTracy-Widom law applies pro

13、bably all beta for large m,n. Johnstone shows at least beta=1,2.,10/9/2018,17,Tools,Motivation: A condition number problem Jack & Hypergeometric of Matrix Argument MOPS: Ioana Dumitrius talk The Polynomial Method The tridiagonal numerical 109 trick,10/9/2018,18,Multivariate Orthogonal Polynomials &

14、Hypergeometrics of Matrix Argument,Ioana Dumitrius talk The important special functions of the 21st century Begin with w(x) on I p(x)p(x) (x) i w(xi)dxi = Jack Polynomials orthogonal for w=1 on the unit circle. Analogs of xm,10/9/2018,19,Multivariate Hypergeometric Functions,10/9/2018,20,Multivariat

15、e Hypergeometric Functions,10/9/2018,21,Wishart (Laguerre) Matrices!,10/9/2018,22,Plamens clever idea,10/9/2018,23,Tools,Motivation: A condition number problem Jack & Hypergeometric of Matrix Argument MOPS: Ioana Dumitrius talk The Polynomial Method The tridiagonal numerical 109 trick,10/9/2018,24,M

16、ops (Dumitriu etc.) Symbolic,10/9/2018,25,A=randn(n); S=(A+A)/2; trace(S4),det(S3),Symbolic MOPS applications,10/9/2018,26,Symbolic MOPS applications,=3; hist(eig(S),10/9/2018,27,Smallest eigenvalue statistics,A=randn(m,n); hist(min(svd(A).2),10/9/2018,28,Tools,Motivation: A condition number problem

17、 Jack & Hypergeometric of Matrix Argument MOPS: Ioana Dumitrius talk The Polynomial Method - Raj! The tridiagonal numerical 109 trick,10/9/2018,29,RM Tool Raj!,Courtesy of the Polynomial Method,10/9/2018,30,10/9/2018,31,The Riemann Zeta Function,On the real line with x1, for example,May be analytica

18、lly extended to the complex plane, with singularity only at x=1.,10/9/2018,32,-3 -2 -1 0 1 2 3,The Riemann Hypothesis,All nontrivial roots of (x) satisfy Re(x)=1/2. (Trivial roots at negative even integers.),10/9/2018,33,-3 -2 -1 0 1 2 3,The Riemann Hypothesis,All nontrivial roots of (x) satisfy Re(

19、x)=1/2. (Trivial roots at negative even integers.),|(x)| along Re(x)=1/2,Zeros =.5+i*14.134725142 21.022039639 25.010857580 30.424876126 32.935061588 37.586178159 40.918719012 43.327073281 48.005150881 49.773832478 52.970321478 56.446247697 59.347044003,10/9/2018,34,Computation of Zeros,Odlyzkos fan

20、tastic computation of 10k+1 through 10k+10,000 for k=12,21,22.See http:/ behave like the eigenvalues of A=randn(n)+i*randn(n); S=(A+A)/2;,10/9/2018,35,Nearest Neighbor Spacings & Pairwise Correlation Functions,10/9/2018,36,Painlev Equations,10/9/2018,37,Spacings,Take a large collection of consecutiv

21、e zeros/eigenvalues. Normalize so that average spacing = 1. Spacing Function = Histogram of consecutive differences (the (k+1)st the kth) Pairwise Correlation Function = Histogram of all possible differences (the kth the jth) Conjecture: These functions are the same for random matrices and Riemann z

22、eta,10/9/2018,38,Tools,Motivation: A condition number problem Jack & Hypergeometric of Matrix Argument MOPS: Ioana Dumitrius talk The Polynomial Method The tridiagonal numerical 109 trick,10/9/2018,39,Everyones Favorite Tridiagonal,10/9/2018,40,Everyones Favorite Tridiagonal,1 (n)1/2,+,+,10/9/2018,4

23、1,Stochastic Operator Limit,10/9/2018,42,Largest Eigenvalue Plots,10/9/2018,43,MATLAB,beta=1; n=1e9; opts.disp=0;opts.issym=1; alpha=10; k=round(alpha*n(1/3); % cutoff parameters d=sqrt(chi2rnd( beta*(n:-1:(n-k-1); H=spdiags( d,1,k,k)+spdiags(randn(k,1),0,k,k); H=(H+H)/sqrt(4*n*beta); eigs(H,1,1,opt

24、s),10/9/2018,44,Tricks to get O(n9) speedup,Sparse matrix storage (Only O(n) storage is used) Tridiagonal Ensemble Formulas (Any beta is available due to the tridiagonal ensemble)The Lanczos Algorithm for Eigenvalue Computation ( This allows the computation of the extreme eigenvalue faster than typi

25、cal general purpose eigensolvers.) The shift-and-invert accelerator to Lanczos and Arnoldi (Since we know the eigenvalues are near 1, we can accelerate the convergence of the largest eigenvalue) The ARPACK software package as made available seamlessly in MATLAB (The Arnoldi package contains state of

26、 the art data structures and numerical choices.) The observation that if k = 10n1/3 , then the largest eigenvalue is determined numerically by the top k k segment of n. (This is an interesting mathematical statement related to the decay of the Airy function.),10/9/2018,45,Level Densities,10/9/2018,46,Open Problems,The distribution for general beta Seems to be governed by a convection-diffusion equation,10/9/2018,47,Random matrix tools!,