All Questions
Tagged with pr.probability random-matrices
51 questions
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
7
votes
1
answer
880
views
Bound for largest eigenvalue of symmetric matrices of uniform random variables over $[0,1]$ and fixed $1$s along diagonal and scattered $1$s
Given a $n\times n$ symmetric random matrix whose diagonal elements are all fixed as $1$. In addition, there are $k$ $1$s will be randomly scattered in upper triangular (of course, the corresponding ...
- 272
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
6
votes
1
answer
274
views
Spectrum asymptotics for a product of $k$ random matrices?
How does the spectrum of a product of $k$ random matrices behave around 0?
In particular, I'm wondering if the CDF of squared singular values behaves as $x^{\frac{1}{k+1}}$ around 0. The result for $k=...
- 2,252
4
votes
1
answer
626
views
How to get the lower bound of the following $\tau$?
Let $A=\{a_{ij}\}_{1\le i,j\le n}$ be an $n$ by $n$ normalized Gaussian random matrix with $E[a_{ij}]=0$ and $E[a_{ij}^2]=1/n$. Ordering its eigenvalues by $\lambda_1\le \lambda_2\le \cdots \lambda_n$ ...
- 288
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
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
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
4
votes
2
answers
1k
views
Expectation of the trace of inverse of a Gaussian random matrix
Given a $N×M$ random complex gaussian matrix $X$ and $N×K$ random complex gaussian matrix $Y$ I'm interested in approximating the expectation expressed as:
\begin{align}
E[trace({(aX{X^H} + I)^{ - ...
- 377
4
votes
1
answer
485
views
Expected norms of Wishart matrices
Suppose $x_i \stackrel{\text{i.i.d}}{\sim} \mathcal{N}(\mu,\Sigma)$. What can we say about dependence on $b$ of Frobenius/spectral norm quantities below?
$$f(b)=\left\|\frac{1}{b}\sum_{i=1}^b x_i x_i^...
- 2,252
3
votes
1
answer
3k
views
Singular value decomposition of random rectangular matrices
Let $A$ be a $m\times n$ real matrix, whose entries are independent, identically distributed random variables, following standard normal distributions (mean zero and unit variance).
What is the ...
- 884
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
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
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
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
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
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
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) ...
8
votes
0
answers
232
views
Decay of orthogonal contributions in a random set of vectors
Suppose we sample $k$ vectors $v$ from normal distribution centered at zero and diagonal covariance with diagonal entries $1,\frac{1}{2},\ldots,\frac{1}{d}$ and normalize $v$:
$$\frac{v_1}{\|v_1\|},\...
- 2,252
7
votes
4
answers
476
views
What does $\mathbb E_V \max_{x \in V,\,\|x\|=1} x^T Ax$ evaluate to when $V$ is random $k$-dim suspace of $\mathbb R^n$ and $A$ is fixed psd matrix?
Let $G_{k,n}$ be the grassmannian of $k$-dimensional vector spaces of $\mathbb R^n$. By the Courant–Fisher characterization, the $k$th largest eigenvalue of an $n \times n$ psd matrix $A$ is given by
$...
- 6,853
7
votes
1
answer
857
views
Trace of inverse of random positive-definite matrix in high dimension?
Consider a random matrix $A \in \mathbb{R}^{n\times n}$ with i.i.d. entries, with symmetric law and finite variance. I am curious about the behavior of $$\mathrm{Tr}( (A^T A + \lambda \mathrm{Id})^{-1}...
- 2,306
6
votes
0
answers
1k
views
Relationship between R-transform and free convolution of random matrices?
I've been using the R-transform to calculate the free convolution of the eigenvalue spectra of two random matrices and I am trying to understand how it works, and in particular how it relates to ...
- 1,890
6
votes
0
answers
295
views
Dimension-free sample complexity for estimating Gaussian covariance
(also asked on math.se, with no answers)
Suppose I have $m$ samples drawn from a Gaussian in $\mathbb{R}^n$, and need sample covariance $\Sigma_m$ to be $\epsilon$-close to true covariance $\Sigma$:
$$...
- 2,252
6
votes
1
answer
837
views
Average minimum number of random k-sparse vectors in GF(2) to span the whole space?
What is the average minimum required number of independent $k$-sparse (having at most $k$ non-zero elements) random vectors belonging to $\mathbb{F}_2^n$ to span the whole space of $\mathbb{F}_2^n$? ...
- 307
5
votes
0
answers
235
views
Riemann theta function inequality for a class of large random matrices
The following is essentially the same question as in this previous post, but since I have completely re-formulated it (hopefully for the better ;-), I decided to post a new question instead of an edit....
- 686
4
votes
0
answers
970
views
Expected operator norm of inverse Wishart matrix
Let $ W\sim W_p(n,I)$ be a white $p\times p$ Wishart matrix, and assume $n>p+1$, which ensures that $W$ is invertible almost surely. Let $\|W^{-1}\|_{\text{op}}$ be the operator norm (maximum ...
- 41
4
votes
1
answer
637
views
Characterizations of the GOE/GUE family of distributions
This question is somewhat related to this one. Loosely speaking, when should I expect a GOE/GUE distribution? The angle of my approach to this is not through statements such as "there is a natural ...
- 4,952
4
votes
1
answer
225
views
Is the inequality of the random matrices correct?
I am not familiar with random matrices but I need to confirm the correctness of the inequality below.
Let $\xi_i\in\{\pm 1\}$ be independent random signs, and let
$A_1,\ldots, A_n$ be $m\times m$ ...
- 131
3
votes
1
answer
206
views
Asymptotic results for smallest gap of Gaussian random matrix
For a symmetric Gaussian random matrix $G=\{G\}_{1\le i,j \le n}$ with iid $E[G_{ij}]=0$ and $E[G_{ij}^2]=1/n$ (it is normalized), ordering its eigenvalues $\lambda_1\le \lambda_2\le\cdots \lambda_n$.
...
- 288
3
votes
1
answer
184
views
Why is number of single cell clusters always greatest in a random matrix?
Consider a large $N\times N$ square lattice, where each cell has a probability $p$ of being "occupied" (let's call denote them as "black") and a probability $1-p$ of being empty (let's denote them as "...
user125648
3
votes
0
answers
202
views
Difficult Gaussian-sum inequality for large random Bernoulli-Toeplitz matrices
I have come across the following problem in an attempt to prove an entropy bound for large random Bernoulli-Toeplitz matrices (Conjecture 1 on p. 16 of this preprint by Clifford et al. 2015), which is ...
- 686
2
votes
0
answers
173
views
Why do larger random matrices maximize their number of clusters with lower densities?
Consider a matrix whose elements are independently assigned a value $1$ with probability $p$ and a value $0$ with probability $1-p$.
Define a cluster of cells as a maximal connected component in the ...
- 41
2
votes
3
answers
999
views
Sum of Square of the Eigenvalues of Wishart Matrix
Let $A\in\mathbb{R}^{m\times d}$ matrix with iid standard normal entries, and $m\geqslant d$, and define $S=A^T A$.
I want to have a tight upper bound for $\sum_{k=1}^d \lambda_k^2$, where $\...
- 1,096
2
votes
1
answer
591
views
Resolvent (Green's function) of this random matrix
I have a matrix $A$ as follows:
$$
A=\begin{pmatrix}
0 & \boldsymbol{W} \\
\boldsymbol{W}^{\dagger} & \boldsymbol{H}
\end{pmatrix}
$$
where $H$ and $W$ are a random Hermitian $N\times N$ ...
- 375
2
votes
1
answer
834
views
Jacobian of changing of variables to singular value decomposition
It is well known that changing variables from a symmetric matrix to its eigenvalue decomposition involves a Jacobian which is just the Vandermonde determinant of the eigenvalues.
Now suppose I have a ...
- 884
2
votes
1
answer
796
views
Can we get that $ P(N^{2/3}(\lambda_N-\lambda_{N-1})\le c)\ge 1-\epsilon$?
Following this question: Can we apply the continuous mapping theorem for the limiting joint distribution of the Tracy-Widom law?.
We know that
$$
\lim_{N\to\infty}P(N^{2/3}(\lambda_N-2)\le s_1,\dotsc,...
- 288
2
votes
1
answer
378
views
Distribution of the Gram matrix
Let $\mathbf{X}$ be an $m\times k$ random matrix ($m>k$) of rank $k$, having the density function $f_\mathbf{X}(X)$. What is the distribution of $\mathbf{Y}=\mathbf{XX}^T$? Basically my question is ...
- 141
2
votes
1
answer
936
views
Upper-bound for spectral norm of the covariance matrix of a certain Gaussian vector with correlated entries
Let $n$ and $m$ be large positive integers. Let $x=(x_1,\ldots,x_n)$ be a vector of independent random variables from $N(0,1)$. It is clear that the covariance matrix of $x$ is $I_n$, the identity ...
- 6,853
2
votes
1
answer
212
views
Prove / disprove: If $1 \le n < N$ and $A$ is an $N \times n$ matrix with iid from $\mathcal N(0,1)$, then $s_\min(A) \ge c\sqrt{N}$ w.p $1-2e^{-N}$
Let $1 \le n < N$ be integers and $A$ be a random $N\times n$ matrix with iid entries from $\mathcal N(0,1)$. This paper (Rudelson and Vershynin) claims in the paragraph just before formula (3.4) ...
- 6,853
2
votes
1
answer
90
views
Generalization: (The "number" of) smaller sized clusters in large random binary matrices follow a descending order. Why?
This is a sequel to the question: Why is number of single cell clusters always greatest in a random matrix?
In their answer, @Aaron Meyerowitz came up with a nice strategy to prove why the number of ...
user125648
2
votes
1
answer
213
views
For fixed $\lambda \ge 0$, Integrate the function $f_\lambda(x):=x/(x + \lambda)^2$ w.r.t. Marchenko-Pastur density
In trying to solve another the problem posed in the question https://www.mathoverflow.net/q/385777/78539, I'm led to consider the following problem.
Let $\mu_\gamma$ be the Marchenko-Pastur ...
- 6,853
2
votes
1
answer
905
views
Diagonalizability of Gaussian random matrices
Let $X$ be an $n\times n$ matrix whose elements are i.i.d. sampled from a normal distribution of zero mean and unit variance. Is $X$ diagonalizable over $\mathbb{C}$ with probability 1? Is there a ...
- 123
2
votes
1
answer
132
views
Independent decomposition of coordinate distribution
Let $\mathbf{x}$ be a random Gaussian vector in $\mathbb{R}^n$, i.e. $\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I}_n)$. Then for any fixed unit vector $\mathbf{u}$, one has $\mathbf{u}\mathbf{u}^\...
- 515
2
votes
1
answer
299
views
Can this particular random matrix model be converted/related to any existing graph theory model?
Context:
This a sequel to the question: Is the Erdős–Rényi giant component result applicable here?
Consider a matrix whose elements are independently assigned a value
$1$ with probability $p$ ...
user123818
1
vote
1
answer
84
views
Asymptotic property of the left singular vectors of i.i.d. data matrix
Let $\mathbf{X}$ be $(n \times p)$-dimensional data matrix ($n > p$) whose rows $\mathbf{x}_i$ are i.i.d. with some finite moments:
$$
\mathbf{X}^\top = [\mathbf{x}_1, \ldots \mathbf{x}_n]^\top.
...
- 284
1
vote
1
answer
415
views
Approximate the singular values of a certain random dot-product kernel matrix (in the sense of El Karoui, Cheng-Singer, etc.)
Let $g:\mathbb R \to \mathbb R $ be a continuous function which is
"sufficiently smooth" (e.g $\mathcal C^3$) around $0$, and
"sufficiently integrable" (e.g integrable w.r.t $N(0,...
- 6,853
1
vote
0
answers
83
views
Tracy Widom type results for asymptotic distribution of the $k$-th largest eigenvalue of the sample covariance when $n, p \to \infty$?
Earlier I asked a question: Distribution of the $k$-th largest eigenvalue of in the sample covariance matrix?, but I forgot to mention that I'd like results for asymtotic regime. So, I'm posting here ...
- 1,467
0
votes
0
answers
115
views
Distribution of the $k$-th largest eigenvalue of in the sample covariance matrix?
Let us assume we've a rectangular data matrix $X=[x_1 \dots x_n] \in \mathbb{R}^{p \times n}$, where the $x_i \in \mathbb{R}^{p \times 1}$ are iid column vectors. I'm not assuming here that the ...
- 1,467
0
votes
1
answer
203
views
LDP for Marchenko Pastur with k/n tending to 0
I am interested in the determinant of $W = X * X'$, where $X \in \mathbb{R}^{k \times n}$ is a matrix with each row drawn IID from some sub-Gaussian distribution on $\mathbb{R}^{n}$. (I am aware of ...
- 435