Questions tagged [random-matrices]
Statistics of spectral properties of matrix-valued random variables.
841
questions
1
vote
0
answers
234
views
Independence of random projection and orthogonal projection
Suppose we have three fixed unit vectors $x, y, z \in \mathbb{R}^d$ and an (arbitrary) distribution over random matrices $M \in \mathbb{R}^{k \times d}$: let $P_M = M^T(MM^T)^{-1}M$ and $P^{\perp}_M = ...
1
vote
1
answer
115
views
Probabilistic lower and upper-bounds for a certain random quartic form involving gaussian random matrices
Let $d,m \to \infty$ (integers) with $m/d \to \rho \in (0, \infty)$. Let $C$ be a $d \times d$ psd matrix with $trace(C)=\mathcal O(1)$, and let $w_1,\ldots,w_m$ be iid uniformly distributed on the ...
1
vote
1
answer
246
views
Bound on $i$th largest eigenvalue in a large Erdos-Renyi graphs
Typical magnitude of $i$th largest eigenvalue of an Erdos-Renyi random graph seems to decay at least exponentially with $i$. Is there an analytic expression for the constant in the exponent, or a nice ...
4
votes
1
answer
257
views
Subspaces with all vectors having large $\|x\|_{\infty}/\|x\|_2$ value
I am able to show that any $k$-dimensional subspace of $\mathbf{R}^{Ck\log(k)}$ must contain a unit vector $x$ such that $\|x\|_{\infty} \ge c\sqrt{1/\log(k)}$ for a small enough constant $c$.
But is ...
0
votes
1
answer
202
views
Factorisation of Gaussian random matrix into random Hermitian and correction factor
By the Bartlett decomposition, one has that for $k \leq n$ and $\mathbf{\Gamma}_{n\times k} \in \mathbb{R}^{n\times k}$ a standard Gaussian matrix with independent entries
$$\mathbf{\Gamma}_{n\times k}...
2
votes
1
answer
163
views
Random sequence with positive Lyapunov exponent?
Consider the following self-adjoint matrix
$A_X = \begin{pmatrix} 0 & -i \\ i & X \end{pmatrix},$ where $i$ is the imaginary unit and $X$ is a uniformly distributed random variable on some ...
4
votes
1
answer
160
views
What is the distribution of eigenvalues of $A^TA$, where $A \sim N(\mu, \Sigma)$?
Let $A$ be a random matrix following multivariate normal distribution $N(\mu, \Sigma)$.
What is the distribution of the eigenvalues of $A^TA$?
A reference to the literature would be most welcome.
6
votes
0
answers
243
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
votes
1
answer
178
views
How can I prove a randomly generated matrix has distinct non-zero eigenvalues?
Consider the following $M×M$ matrix
$$
\mathbf A=\sum_{k=1}^K =a_k \mathbf h_k \mathbf h_k^H,(M≥K)
$$
where $a_k$'s are real values and $h_k$'s are $M×1$ randomly generated vectors, e.g., complex ...
2
votes
1
answer
278
views
Two-level correlation function of eigenvalues for large random matrices
One can define the density of eigenvalues of a $N\times N$ Hermitian random matrix $H$ as:
\begin{equation}
\rho(\lambda)=\left \langle\frac{1}{N} \operatorname{Tr} \delta(\lambda-H)\right\rangle
\end{...
2
votes
0
answers
89
views
Maximum volume submatrices of a Khatri-Rao product of matrix exponentials
My question requires quite a bit of setup, which leads to a conjecture. So I split my question into three parts, Setup, Conjecture, and Question.
Setup:
Pick any two right stochastic matrices $\...
3
votes
1
answer
402
views
Use statistical physics ideas ("replica trick") to compute asymptotic value of $\inf_{\|w\| \le r} (1/n)\|Xw-y\|^2$ for random $X$ and $y$
I'm trying to get my head around the "replica trick" and it's mathematically rigorous formulations (due to Talagrand, Parchenko, etc.). I was wondering to myself that a solution or insight ...
1
vote
1
answer
84
views
Difference between identity and a random projection
Suppose a random projection $P$ in $\mathbb{R}^d$ onto a random n-dimensional subspace in $\mathbb{R}^d$ uniformly distributed in the Grassmannian $G_{d, n}$ (the projection of the row space of a ...
4
votes
0
answers
187
views
Dyadic distribution of $0/1$ permanents
Fix reals $a,b\in(1,2)$ satisfying $1<b<a<ab<2$.
What fraction of $0/1$ matrices of dimensions $n\times n$ have permanents
in $[b2^m,a2^m]$ at some $m\in\{0,1,2,\dots,\lfloor\log_2n!\...
2
votes
0
answers
129
views
condition number of random submatrices
If we randomly pick $k\ll n$ columns from a fixed $n\times n$ matrix $A$, what can one say about the distribution of the 2-norm condition number of the resulting $n\times k$ matrices $A_k$?
I'd expect ...
2
votes
1
answer
205
views
Eigenvalues of large symmetric random tensors
I am studying the eigenvalues of large random tensors and realise that very little is known about it. I was wondering what is already known and what could be potential leads to find their limiting ...
3
votes
2
answers
437
views
Fourier transform of eigenvalue distribution of GUE matrices
I am interested in explicit expression or bounds for the Fourier transform (characteristic function) of the joint probability distribution of eigenvalues of random matrices $X\sim \mathrm{GUE} (d)$, ...
2
votes
1
answer
616
views
Concentration inequality for the sample covariance matrix
I'd like to know if there is a concentration inequality for the sample covariance matrix that don't assume the knowledge of the true mean.
Background.
Given a probability distribution $\mu$ on $\...
2
votes
1
answer
240
views
Spectral gap of $AA^{T}$ for Bernoulli random matrix A
I need the following answer for research purposes.
Let $A$ be a $m \times n$ random matrix with iid ${\rm Bernoulli}(p)$ entries. Is there any result on the spectral gap of $AA^{T}$ (similar to well ...
1
vote
1
answer
142
views
Probability finite precision random matrix has distinct eigenvalues
copied from math stack exchange
There is a theorem which says the probability/size of a random matrix having repeated eigenvalues is 0 and this result is used in many fields. What I am wondering is, ...
2
votes
0
answers
135
views
Asymptotic lower and upper bounds for the eigenvalues of hadamard product $W \circ W$, where $W$ is a large Wishart matrix
Let $n$ and $d$ be large positive integers with $n,d \to \infty$ such that $n/d \to \gamma \in (0,\infty)$. Let $X$ be a random $n \times d$ random matrix with iid copies of log-concave isotropic ...
2
votes
1
answer
142
views
Lower bound of the probability of singular random matrix over $\{\pm1\}$ in ``Singularity of random Bernoulli matrices"
Suppose $M_{n}$ is an $n \times n$ matrix with independent ±1 entries. Recent breakthrough shows that the probability $\mathbb{P}(M_{n} \text{ is singular})$ is
$$(1) \quad\quad\qquad \mathbb{P}(M_{n} ...
3
votes
1
answer
162
views
Combinatorial formula to compute the moments of the product of two free random variables
I found in the PhD thesis Moments method for random matrices with applications to wireless communication the following combinatorial formula to compute the free moments of the product of two random ...
3
votes
0
answers
187
views
Eigenvalues of Hadamard product of two Wishart-type matrices
Given two independent Gaussian matrices with i.i.d. entries: $A\in\mathbb{R}^{n\times p}$ and $B\in\mathbb{R}^{n\times q}$, where and $A_{i,j},B_{i,j}\sim\mathcal{N}(0,1)$. Assume that $\max(p,q)<n....
1
vote
1
answer
85
views
Asymptotics of the right singular vectors as the number of rows diverge [duplicate]
Write $X_m \in \mathbb{R}^{m \times n}$ as a Gaussian ensemble, so that $(X_m)_{ij} \sim \mathcal{N}(0, 1)$ are independent and identically distributed. Assume that $m \geq n$. Write $X_m = U_m \...
1
vote
1
answer
241
views
How to compute the first moment of the distribution of the convolution of Marcenko-Pastur law with a not iid matrix?
Let $\mathbf{F}$ denote an M × N matrix whose entries are independent zero-mean complex random variables, the limiting eigenvalue distribution is given by the Marchenko Pastur law $MP_{\beta}$, where $...
2
votes
1
answer
515
views
Distribution of eigenvectors of random matrices and link with the components of the matrix
Let $M$ be a real symmetric matrix of size $N$ with its components $M_{ij}$ following a normal distribution centered around 0.
Let $x\in\mathbb{R}^N$ be an eigenvector of $M$ with eigenvalue $\lambda\...
3
votes
1
answer
113
views
General formula for the integral w.r.t to Marchenko-Pastur density, of the ratio of degree $\le 2$ polynomials
Question. Is there a closed-form formula (via standard objects like rational functions, radicals, special functions, special numbers like Catalan numbers, etc.) expressing integrals of rational ...
3
votes
2
answers
746
views
Expectation of product of random matrices
Let $X$ and $Y$ be independent random symmetric matrices. What can one say about $\mathbb{E} [X Y X Y]$ or $\mathrm{trace} \mathbb{E} [X Y X Y]$ in terms of properties of $X$ and $Y$?
In particular, ...
1
vote
1
answer
122
views
Limiting eigenvalue distribution of $YY^\top$ where $Y_{ij} = X_{ij} + a$ and $X$ has iid rows from an isotropic log-concave distribution
Let $a \in \mathbb R$ be a determinstic scalar and let $X$ be and $n \times d$ such that the $n \times n$ psd random matrix $S=XX^T$ has limiting eigenvalue distribution $\mu$, when $n,d \to \infty$ ...
2
votes
1
answer
189
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 ...
2
votes
1
answer
362
views
High-probability lower bound for norm of least squares solution when both design matrix $X$ and response vector $y$ are random (and independent)
Let $n,d \to \infty$ with $n/d \to \gamma \in (0,\infty)$. Let $X$ be a random $n \times d$ matrix independent rows uniformly distributed on the the unit-sphere in $\mathbb R^d$ and let $y$ be a ...
0
votes
0
answers
124
views
Is it possible to reduce eigenvalues of tensors to an matrix eigenvalue problem?
Can we construct a larger matrix $M$ such that its eigenvalues are the same as the eigenvalues of a tensor $T$ of order 3?
Let $\mathbf{T}$ be a fully symmetric tensor of order $3$ and size $N$. Its ...
3
votes
0
answers
227
views
Using linearization trick (free probability) to compute limiting singular-value density of $R=XY+Z+A$ (or equivalently, of $RR^\top$)
Disclaimer. I only started learning the subject of free probability $1$ day ago, and I'm still trying to absorb the fundamentals, while applying them to my own specific problems arizing in the ...
1
vote
0
answers
201
views
Distribution and expectation of inverse of a random Bernoulli matrix
This question cropped up as a part of my research. Let us assume a $n\times n$ random matrix $\mathbf{M}$ with elements iid distributed to a Bernoulli distribution that takes values $\{0,1\}$ with ...
1
vote
1
answer
139
views
Bounds for the extreme singular-values of random matrix with thresholded entries
Let $n,d,k$ be large positive integers such that $\max(n/d,k/d) =: \lambda < 1$. Let $X$ be a random $n \times d$ matrix with entries drawn iid from $N(0,1/d)$ and let $W$ be a $k \times d$ random ...
2
votes
2
answers
509
views
Can the eigenvalues of a real symmetric tensor be complex?
Let $T$ be a fully symmetric tensor of rank $3$ and size $N$.
Using the following definition of eigenvalues, let $x\in \mathbb{C}^N$ and $\lambda\in\mathbb{C}$ such that:
\begin{equation}
\sum_{jk}^...
2
votes
1
answer
200
views
Variance of projection of vectors onto random subspace
Let $x_i, y_i \in \mathbb{R}^n$ for $i=1, \dots, k < n$ satisfy
$$
\sum_{i=1}^k x_i^\top y_i = 0.
$$
Let $E$ be a random subspace of dimension $m < n$ in $\mathbb{R}^n$ distributed uniformly on ...
2
votes
1
answer
636
views
Lower-bound for smallest eigenvalue of random $k \times $k matrix $C(W)$ defined by $C(W)_{i,j} := 2(w_i^\top w_j)^2 + \|w_i\|^2\|w_j\|^2$
Let $k$ and $d$ be positive integers such that $d/k:=\lambda > 1$. Let $W$ be $k \times d$ random matrix with rows $w_1,\ldots,w_k \in \mathbb R^d$ drawn iid from $N(0,(1/d)I_d)$, and define the $k ...
0
votes
1
answer
156
views
Expected pseudo-inverse of isotropic random matrix
Suppose I have a random $m \times m$ matrix $R \sim \mu$ that is possibly singular. Is it true that
$ E[R] \propto I$ implies that there exists a scalar $r_{\mu, m}$ such that $E[R^+] = r_{\mu, m}I$, ...
0
votes
1
answer
603
views
Why is the determinant of a large random matrix equal to zero? (Heuristics) [closed]
Let $\mathbf{A}$ be a matrix of size $N\times N$ whose elements $A_{ij}$ (with $1\leq i,j\leq N$) are I.I.D following some distribution.
If we set set $\langle A_{ij}\rangle=0$ and $\langle {A_{ij}}^2\...
1
vote
0
answers
93
views
Concentration for $\sum_{i=1}^n y_i \psi(x_i^\top u)$, for $y_1,\ldots,y_n \sim \{\pm 1\}$ and $x_1,\ldots,x_n$ uniform iid on hypersphere
Let $y_1,\ldots,y_n$ be drawn iid uniformly from $\{\pm 1\}$ and let $x_1,\ldots,x_n$ be drawn iid uniformly from the unit-sphere $(d-1)$-dimensional sphere $\mathbb S_{d-1}$, and independently from ...
1
vote
1
answer
54
views
Limit laws for random matrix products covergence
I'm trying to understand Theorem 1.1 in Limit laws for random matrix products.
It states that a specific product of random matrices converges to a set matrix but I don't know which kind of convergence ...
7
votes
1
answer
303
views
Iterating projections to random halfspaces
Consider the following process:
Start with a set $S = \mathbb R^n$. Repeat $L$ times: choose a random orthonormal basis $u_1, \ldots, u_n$, and consider the cone $C = \{ \sum \alpha_i u_i : \alpha_i \...
3
votes
1
answer
325
views
Concentration inequality for norm of solution to nonlinear least-squares problem
Define the piecewise-linear function $\psi(t):=\max(t,0)$ for all $t \in \mathbb R$.
Let $d,n,k \to \infty$ at the same rate (i.e $n \asymp k \asymp d$).
Let $y_1,\ldots,y_n \in \{-1,1\}$ uniformly ...
8
votes
0
answers
268
views
Maximum probability of a set of vectors from $ \mathbb{F}_2^n $ being linearly independent
Suppose $ m $ vectors from the vector space $ \mathbb{F}_2^n $ are selected independently according to a distribution $ P $ over $ \mathbb{F}_2^n $. Here $ \mathbb{F}_2 $ denotes the field with two ...
0
votes
1
answer
214
views
Product of random matrices which commute almost surely
In the paper "Matrix concentration for products" it is stated, that the following is easy to show.
Let $X_1,\dots X_n$ be independent, bounded, square matrices, which commute almost surely. ...
1
vote
0
answers
62
views
About symmetric rank-1 random matrices
Consider a $2n-$dimensional symmetric random matrix $M$ of form, $M = \begin{bmatrix} aa^T & ab^T \\ ba^T & bb^T \end{bmatrix}$ where $a$ and $b$ are $n$ dimensional random vectors.
Are there ...
3
votes
0
answers
112
views
Applications of products of random matrices
I'm studying the paper "Matrix concentration for products" and I'm trying to find simple applications of the inequalities for the expected value of the spectral norm of products of random ...
2
votes
0
answers
151
views
The CDF of determinant of wishart distribution
Assuming $b>0$, $\mathbf{A} \in \mathbb{C}^{m\times n}$ with $m\leq n$ and each element of $\mathbf{A}$ is i.i.d. $\mathcal{CN}(0,1)$ distributed, how to obtain $\mathbb{P} \left[ \det\left( \...