All Questions
Tagged with pr.probability random-matrices
478 questions
45
votes
1
answer
6k
views
Anti-concentration bound for permanents of Gaussian matrices?
In a recent paper with Alex Arkhipov on "The Computational Complexity of Linear Optics," we needed to assume a reasonable-sounding probabilistic conjecture: namely, that the permanent of a matrix of i....
- 9,833
42
votes
3
answers
5k
views
The probability for a symmetric matrix to be positive definite
Let me give a reasonable model for the question in the title. In ${\rm Sym}_n({\mathbb R})$, the positive definite matrices form a convex cone $S_n^+$. The probability I have in mind is the ratio $p_n=...
- 52.3k
40
votes
1
answer
5k
views
When should we expect Tracy-Widom?
The Tracy-Widom law describes, among other things, the fluctuations of maximal eigenvalues of many random large matrix models. Because of its universal character, it obtained his position on the ...
- 2,135
36
votes
0
answers
2k
views
Correspondence between eigenvalue distributions of random unitary and random orthogonal matrices
In the course of a physics problem (arXiv:1206.6687), I stumbled on a curious correspondence between the eigenvalue distributions of the matrix product $U\bar{U}$, with $U$ a random unitary matrix and ...
- 188k
32
votes
3
answers
12k
views
What is the Katz-Sarnak philosophy?
It has been recently mentioned by a speaker (his talk is completely not relevant to random matrix theory/RMT though) that modern statistics, especially random matrices theory, will help solving some ...
- 8,071
27
votes
3
answers
13k
views
What is known about the distribution of eigenvectors of random matrices?
Let $A$ be a real asymmetric $n \times n$ matrix with i.i.d. random, zero-mean elements. What results, if any, are there for the eigenvectors of $A$? In particular:
How are individual eigenvectors ...
- 433
25
votes
1
answer
4k
views
What kind of random matrices have rapidly decaying singular values?
I've been told that in machine learning it's common to compute the singular value decomposition of matrices in order to throw out all information in the matrix except that corresponding to, say, the $...
- 118k
22
votes
2
answers
1k
views
Laws of Iterated Logarithm for Random Matrices and Random Permutation
The law of iterated logarithm asserts that if $x_1,x_2,\dots$ are i.i.d $\cal N(0,1)$ random variables and $S_n=x_1+x_2+\cdots+x_n$, then
$$\limsup_{n \to \infty} S_n/\sqrt {n \log \log n} = \sqrt 2, $...
- 24.7k
22
votes
1
answer
1k
views
Random distance matrices
My question is motivated by the following recent paper:
Gadgil, Siddhartha; Krishnapur, Manjunath, Lipschitz correspondence between metric measure spaces and random distance matrices, Int. Math. Res. ...
- 3,626
21
votes
0
answers
2k
views
The Fourier Transform of taking Eigenvalues
The purpose of this question is to ask about the Fourier transform of the map which associate to an $n$ by $n$ matrix its $n$ eigenvalues, or some function of the $n$ eigenvalues. The main motivation ...
- 24.7k
20
votes
6
answers
19k
views
Intuition for Haar measure of random matrix
What is an intuitive way to understand Haar measure as defined for random matrices, say, $N\times N$ orthogonal or unitary matrices?
My understanding for what Haar measure means for $U(1)$ is that it ...
- 1,890
20
votes
0
answers
3k
views
+200
What does a product of many Gaussian matrices converge to?
Let $A$ be a product of $n$ $d\times d$ matrices with IID standard Gaussian entries and consider the value of $g(x)=x f(x)$ where $f(x)$ is the density of squared singular values of $A/\|A\|$.
Is ...
- 2,252
19
votes
2
answers
569
views
Repeated random two-steps in $\mathbb{R}^3$: unbounded?
I created a random isometry $T$ of $\mathbb{R}^3$ by generating
a random orthogonal matrix $M$,
uniformly distributed among all such,
and a random displacement $v$, whose coordinates
are drawn from a ...
- 151k
18
votes
1
answer
1k
views
How fast can extreme eigenvalues of the average of random matrices converge to their expectation?
Suppose that $X_1,X_2,\ldots,X_m$ are independent $d\times d$ random matrices and let $\overline{X} := \frac{1}{m}\sum_{i=1}^m X_i$. One of the questions studied under the theory of random matrices is ...
- 181
17
votes
1
answer
9k
views
Intuitive understanding of the Stieltjes transform
I have been using random matrix theory in signal processing and have some trouble understanding what the Stieltjes transform does.
The gist of my work is that I have an $N\times N$ true covariance ...
16
votes
5
answers
2k
views
Expected value of determinant of simple infinite random matrix
Suppose we have a matrix $A \in \mathbb{R}^{n\times n}$ where
$$A_{ij} = \begin{cases} 1 & \text{with probability} \quad p\\ 0 &\text{with probability} \quad1-p\end{cases}$$
I would like to ...
- 355
16
votes
4
answers
597
views
The lattice spanned by $m$ random 0-1 vectors of length $n$
Consider $m$ random 0-1 vectors of length $n$. Let $L$ be the lattice spanned by them. What is the value of $m$ (as a function of $n$) for which it is true with positive probability that $L=Z^n$? More ...
- 24.7k
15
votes
2
answers
3k
views
What do we actually know about logarithmic energy ?
In potential theory, the $\textit{logarithmic energy}$ of a Radon measure $\mu$ acting on $\mathbb{C}$ is defined by
$$I(\mu)=\iint\log\frac{1}{|x-y|}\mu(dx)\mu(dy).$$ Of course it is not well ...
- 2,135
15
votes
1
answer
1k
views
Has the technique of "sprinkling" been used in studying random matrices?
In 1982, while studying the component sizes of random subgraphs of a hypercube, Ajtai, Komlós, and Szemerédi introduced a technique that came to be known as sprinkling. In this technique, the edges of ...
- 4,922
15
votes
2
answers
6k
views
Distribution of inverse of a random matrix
I got stuck into a problem and couldn't find its
satisfactory answer anywhere.
My question is simple. Suppose I have a fat random matrix (i,e., $R$ has dimensions $k\times d$ where $k<d$) whose
...
- 151
14
votes
1
answer
1k
views
A Question on Random Matrices
Consider the following $n\times n$ random matrix $V_{n}$ where the $(p,q)$ entry is given by
$$
V_{n}(p,q):= \frac{1}{\sqrt{n}}\exp(2\pi i(p-1) x_{q})
$$
where $x_{1},x_{2},\ldots,x_{n}$ are iid ...
- 3,626
14
votes
1
answer
449
views
References for reasoning about the spectrum of a convex body?
By "spectrum of a convex body", I mean: start with a convex body $B$ in $\mathbb{R}^d$, then consider the corresponding $d \times d$ covariance matrix resulting from a uniform distribution over $B$ -- ...
- 143
13
votes
4
answers
1k
views
Why only three classical matrix ensembles in random matrix theory?
I am just starting out on understanding random matrix theory from a background in applied mathematics. I have a very basic question about the Gaussian ensembles: why are there only three classical ...
- 1,890
13
votes
2
answers
879
views
The expected square of the determinant of a random row stochastic matrix
In this
question Anthony Quas asks about the expected absolute value of
the determinant of an $n\times n$ row stochastic matrix $A$, where
the rows are independently selected from the uniform ...
- 50.8k
13
votes
1
answer
889
views
Probability that random nonnegative integer matrix is singular
Q. What is the probability that an $n \times n$ matrix, whose elements
are independent uniformly random integers in $\{0,1,\ldots,k\}$, is singular?
For example, for $n=3$ and $k=2$, the first ...
- 151k
13
votes
1
answer
696
views
$\ell^1$-norm of eigenvectors of Erdős-Renyi Graphs
Setting. Let $G(n,p)$ denote the usual Erdős-Renyi (random) graphs. For each such graph there is an associated Laplacian matrix $L = D - A$ where $D$ collects the degrees on the diagonal and $A$ is ...
13
votes
2
answers
656
views
Random matrix with given singular values
Let $\sigma_1\geq\sigma_2\geq...\geq\sigma_n\geq0$ be any deterministic sequence of positive real numbers such that $\sum_{i=1}^n\sigma_i^2=1$. Let
$$D=diag\{\sigma_1,...,\sigma_n\}\in\mathbb{R}^{n\...
- 1,495
12
votes
1
answer
628
views
A function with unexpectedly simple Legendre transformation
Let $I(x) = \frac{1}{2\pi} \int_{-2}^2 \sqrt{4-y^2}\ln|x-y|dy$. Then $I(x)$ is a concave function and
\begin{equation}
I(x)=
\begin{cases}
\frac{1}{4}x^2-\frac{1}{2}, &\text{if } |x|\leq2 \\
\...
- 1,608
11
votes
8
answers
2k
views
Semicircle law universality elsewhere
Wigner's semicircle distribution is:
$$f(x)=\frac{1}{2 \pi}\sqrt{4-x^2}, \ \ -2\leq x\leq 2.$$
Under reasonable conditions, the rescaled eigenvalue density of random symmetric matrices $M_n$ follows ...
- 4,952
11
votes
1
answer
636
views
A simple proof for a theorem of Szekeres and Turán
Szekeres and Turán found in 1937 a formula for the sum of the squares and the sum of the fourth powers of determinants of all $n$ by $n$ matrices with $\pm 1$ entries. (The sum of squares case follows ...
- 24.7k
11
votes
2
answers
2k
views
Expected values of traces of products of random matrices
Suppose I want to compute a quantity of the type:
$\mathbb{E}\mathrm{tr}(AUBU^{\ast})$
where averaging is over Haar measure on the unitary group $\mathcal{U}(n)$ (one can of course consider higher ...
- 3,323
11
votes
1
answer
919
views
Average over Random Permutations
Consider $S_{n}$ the symmetric group and for each $\sigma\in S_{n}$ let $U_{\sigma}$ be its $n\times n$ permutation matrix. Let $A$ be an Hermitian $n\times n$ matrix. I'm interested in computing the ...
- 3,626
10
votes
2
answers
2k
views
Intuition behind the spectral density of random matrices
Hi,
I have read that the spectral density of an NxN random matrix consisting of iid random variables with zero mean and unit variance converges as N goes to infinity to the uniform distribution on ...
- 349
10
votes
5
answers
3k
views
Reviews of Probability in High Dimension not by Van Handel
I'm completely in love with Ramon van Handel's lecture notes Probability in High Dimension and I would like to find more learning resources. Lecture notes or reviews would be ideal as anything in this ...
- 273
10
votes
2
answers
3k
views
Statistics for Haar measure of random matrices?
Let's say I have $M$ samples of $N\times N$ real orthogonal matrices. What statistics can I calculate to test if they could have been drawn from a distribution consistent with Haar measure over $O(N)$?...
- 1,890
10
votes
1
answer
441
views
Probability that a random distance function is metric
Take a random $n \times n$ nonnegative symmetric matrix $D$ with zero diagonal. What is the probability that it is an abstract distance matrix, i.e. satisfies $D_{xy}+D_{yz} \geq D_{xz}$ for all index ...
- 6,962
10
votes
2
answers
1k
views
Probability of random (0,1) Toeplitz matrix being invertible
A Toeplitz matrix or diagonal-constant matrix is a matrix in which each descending diagonal from left to right is constant.
What is the probability that a random $n \times n$ binary Toeplitz ...
user32786
10
votes
1
answer
492
views
(Asymmetric) matrix power series in closed form: $\sum_{i=0}^{\infty} A^i \left(A^i\right)^{\top}={?}$
Let $A\in \mathbb{S}^{N\times N}$ be a symmetric, real and stable matrix, i.e., $\rho(A)<1$, where $\rho(A)$ stands for the spectral radius of $A$. Then, $$\sum\limits_{i=0}^{\infty} A^{2i}=\left( ...
- 767
10
votes
3
answers
1k
views
Random walks and Lyapunov exponents
Given a sequence $Y_1, Y_2, \dots$ of i.i.d. matrices in $\mathrm{GL}_n(\mathbb R)$, there is a theorem of Furstenberg and Kesten which says that if $\mathbb E(\log\|Y_1\|)$ is finite, there exists a ...
- 315
10
votes
4
answers
645
views
Expected value of Bernoulli quadratic forms
Let $\mathbf{Y}\in\mathbb{R}^{n\times n}$ be a symmetric matrix. Let $\mathbf{x}\in\mathbb{R}^n$ be random vectors with entries i.i.d. $\pm 1$ with equal probability. I'm interested in a lower bound ...
- 363
10
votes
1
answer
514
views
Largest eigenvalue of finite band random matrices
Let $\mathbf{M}_n$ be an $n \times n$ symmetric matrix
$$
\mathbf{M}_n = \begin{cases}
X_{j-i,i}\ &\text{if }i\leq j\leq r+i\\
0\ &\text{if }r+i< j\leq n\end{cases}
$$
for some fixed $r>...
- 73
10
votes
1
answer
1k
views
Probability a random Toeplitz matrix is singular
Consider Toeplitz matrices where the entries in the first row and column (which define the whole matrix) are independently chosen to be either $1$ or $0$ with probability $1/2$. Define $p_n$ to be the ...
- 3,377
9
votes
3
answers
3k
views
For positive definite $A,B$ why does $AB+BA$ tend to be positive definite?
Let $A$ and $B$ be two positive definite $n \times n$ matrices. It is, of course, not true that $AB+BA$ is necessarily positive definite.
Consider, though, the results of the following numerical ...
- 117
9
votes
1
answer
652
views
Scaling in Mehta's integral
The following expression is known as Mehta's integral and deeply connected to random matrix theory:
$$\frac{1}{(2\pi)^{n/2}}\int_{-\infty}^{\infty} \cdots \int_{-\infty}^{\infty} \prod_{i=1}^n e^{-...
- 124
9
votes
2
answers
496
views
Is there a determinantal point process proof of the Keating-Snaith formula for the cumulants of the log characteristic polynomial of a random matrix?
For $U$ a unitary $N \times N$ matrix, randomly distributed according to Haar measure, we have the complex-valued random variable $\log (\det (1-U))$. The real part and imaginary parts of $\log (\det (...
- 148k
9
votes
1
answer
372
views
Why impossible events have some drawbacks or pathologies in probability theory?
It is said by Halmos, P.R.; in "Lectures on ergodic theory"
"Many of the difficulties of measure theory and all the pathology of the subject arise from the existence of sets of measure ...
9
votes
1
answer
886
views
Concentration of sum of powers of normals
Let $Z_1,Z_2,\ldots,Z_n$ be i.i.d. copies of a random variable $Z$ distributed as $\frac{1}{\sqrt{2}}X+i\frac{1}{\sqrt{2}}Y$ with $X$ and $Y$ independent standard Normal random variables i.e.~$X\sim\...
- 859
9
votes
2
answers
4k
views
Eigenvalue densities of sample covariance matrices when the population covariance matrix is a perturbed identity matrix
TLDR: I'm looking for a random matrix theory reference for the eigenvalue densities of sample covariance matrices (both dimensions approaching infinity at the same rate) when the true (population) ...
9
votes
2
answers
366
views
Iterating Random Matrix Operations
Consider the following probability measure on the integers concentrated around $0$: the probability of drawing $0$ is $\frac{1}{2}$, of drawing ($1$ or $-1$) is $\frac{1}{4}$ split evenly among the ...
- 15.5k
9
votes
1
answer
657
views
Samuel Karlin's problem: Probability of positive solution to system of random linear equations
I came to know this problem from Dr. W. Bryc's slides (at University of Cincinnati), and I have been continually working on this problem for almost 5 days using different techniques. But I am only ...
- 984