All Questions
Tagged with measure-concentration random-matrices
65 questions
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
10
votes
1
answer
931
views
Non-probabilistic proof of the Johnson–Lindenstrauss lemma
The Johnson–Lindenstrauss lemma states that a small set of points in a high-dimensional space can be embedded into a space of much lower dimension in such a way that distances between the points are ...
- 225
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
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
7
votes
0
answers
759
views
Product of two random Gaussian matrices - orthant probability
Let $X \in \mathbb{R}^{m \times n}$ and $Y \in \mathbb{R}^{n \times k} $ be two independent Gaussian random matrices, i.e., with entries independently sampled from $\mathcal{N}(0,1)$ (a normal ...
- 968
6
votes
0
answers
554
views
a variation on Hanson-Wright inequality
The classic Hanson-Wright inequality states that for a Gaussian random vector $\mathbf{x}\in\mathbb{R}^n$ distributed as $\mathcal{N}(\mathbf{0},\mathbf{I})$ and $\mathbf{A}\in\mathbb{R}^{n\times n}$ ...
- 859
5
votes
1
answer
402
views
Lower tail of random rank one sums?
Let $\{x_i\}_{i\geq 1}$ be iid random elements of the sequence space $\ell^2(\mathbb{N})$;
assume that $\|x_i\|_2 \leq 1$ almost surely. Let $\Sigma = \mathbb{E}[x_1 \otimes x_1]$.
Define
$$
\Sigma_n =...
- 380
5
votes
1
answer
282
views
What is the spectral norm of a random projection times a diagonal?
Take $n\ll N$. Let $P$ be an $n\times N$ matrix of iid $\mathcal{N}(0,1)$ random variables, and let $D$ be an $N\times N$ diagonal matrix.
What can be said about the distribution of the largest ...
- 7,633
5
votes
1
answer
332
views
Matrix concentration bound
Suppose we have $N$ constant matrices $A_i \in R^{m\times m}, 1\leq i \leq N$. Consider $N$ random rotation-matrices $R_i \in SO(m), 1\leq i \leq N$. Is it possible to obtain a concentration bound on
$...
- 51
5
votes
1
answer
765
views
Measure concentration for weakly dependent random variables
For an application quite alien to probability theory, I'd like to have a kind of measure concentration estimate, in the following spirit. Suppose that to every $1\le i,j\le n$ there corresponds a zero-...
- 23k
5
votes
1
answer
284
views
concentration of random matrices involving normal random variables
Define the random variable
\begin{align*}
A=|a_1|^2\mathbf{a}\mathbf{a}^*
\end{align*}
where $\mathbf{a}\in\mathbb{c}^n$ is a random vector distributed as $\mathcal{N}(0,\mathbf{I}/2)+i\mathcal{N}(0,\...
- 859
5
votes
0
answers
327
views
Eigenvalues of Random Regular Bipartite Graphs
I am looking for a way of getting a good estimate of the eigenvalues of random bipartite d-regular graphs. The literature has very precise values the proofs of which are very involved and since I am ...
- 161
5
votes
0
answers
397
views
Concentration of functions of random unitary matrices
Suppose $U$ and $V$ are $n \times n$ random unitary matrices, chosen independently from the Haar measure. Is there any kind of concentration inequality which would be applicable to polynomials $p(U,V)$...
- 2,449
4
votes
1
answer
356
views
Tail bounds on eigenvalue gaps for GUE
What I'm looking for is a non-asymptotic bound on the probability that the smallest gap between eigenvalues of a GUE matrix does not exceed a certain value.
I'm aware of the bounds in
http://imrn....
- 53
4
votes
1
answer
286
views
Upper tail concentration of sample covariance matrices
I'm interested in concentration of the following random matrix sum in spectral norm
$\frac{1}{m}\sum_{k=1}^m b_k^2\mathbf{a}_k\mathbf{a}_k^*$
Here $\mathbf{a}_k\in\mathbb{R}^n$ are i.i.d. standard ...
- 363
4
votes
0
answers
643
views
Comparison of concentrations of different $L^p$-norms of (sub) Gaussian distributions
It's well-known that the Euclidean $2$-norm of subgaussian random vectors concentrates in high dimensions, e.g. when $X \sim \mathcal{N}(0,I_n),$ (or in general $X$ is subgaussian with independent co-...
- 1,467
4
votes
0
answers
418
views
concentration of functions of Gaussian processes
Let $\mathcal{C}\in\mathbb{R}^n$ be a subset of the unit ball. Also let $\mathbf{a}_1,\mathbf{a}_2,\ldots,\mathbf{a}_m\in\mathbb{R}^n$ be i.i.d. random Gaussian vectors $\mathcal{N}(\mathbf{0},\mathbf{...
- 859
3
votes
1
answer
179
views
Tail probability of random projection
Suppose $v\in R^n$ is a constant unit vector. $P_l$ is a random projection matrix to an $l$ dimensional subspace of $R^n$ which is uniformly sampled from $G(l,R^n)$ which is the collection of all $l$-...
- 1,495
3
votes
1
answer
159
views
About concentration of eigenvalues values of a random symmetric matrix in a specific interval
Given a random symmetric matrix $M$ and two numbers $\lambda_\min$ and $\lambda_\max$ how do we calculate the expected or high probability value of the fraction of its eigenvalues which lie in the ...
- 2,246
3
votes
2
answers
394
views
Strictly positive solutions of a random linear system
Suppose $B\in\mathbb{R}^{m\times n}$ is a random binary matrix with i.i.d entries and $c\in \mathbb{R}^m$ is a strictly positive vector, that is $c_i>0$ for $i=1,2,\cdots m$. Also assume $m<n$, ...
- 127
3
votes
1
answer
436
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 ...
- 6,853
3
votes
0
answers
335
views
Tail bound on trace norm / nuclear norm / Schatten-1 norm of Rademacher matrix
Let $0 < r \leq d$ integers. Let $X$, $Y$ be $d \times r$ matrices of independent Rademacher variables, that is, $X,Y \in \mathbb{R}^{d \times r}$ with entries $\pm1$ with probability $1/2$. I am ...
- 223
3
votes
0
answers
93
views
Explaning why the spectrum of a setting simple structure random matrix is always spiked ($d-1$ eigenvalues close to zero, and $1$ away from zero)
For concreteness, let $m=500$, $d=600$, $N=1000$. Let $W$ be and $d \times m$ matrix with unit-norm rows and let $u$ be a uni-norm vector of length $m$. Given a binary vector $b$ of length $m$, length ...
- 6,853
3
votes
0
answers
226
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....
- 31
3
votes
1
answer
379
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 ...
- 6,853
3
votes
0
answers
307
views
Upper-bound for eigenvalues of $E [UU^T]$, where $U$ is uniformly distributed on the unit $n$-sphere
Let $X$ be a $\sigma$-subGaussian random vector on $\mathbb R^n$ (for large $n \ge 3$), meaning that the random variable $X^Tv$ is $\sigma$-subGaussian for every unit vector $v \in \mathbb R^n$. ...
- 6,853
3
votes
0
answers
166
views
Matrix Chernoff sampling with out replacement
I am interested to know if the matrix Chernoff bound (see Theorem 5.1.1 in https://arxiv.org/pdf/1501.01571.pdf) holds if one samples without replacement.
For example, the Bernstein inequality is ...
- 221
3
votes
0
answers
77
views
A concentration problem of product of matrices
Let $A$ be an $n \times m$ matrix with non-negative entries and $B \in \mathbb{R^{n\times n}_{\geq 0}}, C \in \mathbb{R^{m\times m}_{\geq 0}}$ be random matrices where B and C are both symmetric and ...
- 195
3
votes
0
answers
126
views
Concentration of sums of random matrices around the mean, in the Loewner order
Recently, I have found myself interested in concentration properties of random matrices.
Specifically I would like to answer questions of the following sort
Let $\{X_i\}_{i=1}^n$ be i.i.d. copies ...
- 393
3
votes
0
answers
372
views
On the precise concentration of permanent of $\pm1$ matrices
Obtain $M\in\{-1,+1\}^{n\times n}$ by unbiased coin flipping.
What is known about the distribution of permanent $\mathsf{Perm}(M)$? It seems to be bimodal.
Given a function $g(n)$ what is the ...
user94040
2
votes
1
answer
669
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 ...
- 6,853
2
votes
2
answers
228
views
Minimal conditions on random vector $X \in R^n$ to ensure that $\lim_{t\to 0^+}\sup_{\|w\|_p = 1}\sup_{u \in \mathbb R}\mathbb P(|X'w-u| \le t)=0$
Let $X$ be a random variable on $\mathbb R^n$ and let $S_p^n := \{w \in \mathbb R^n \mid \|w\|_p = 1\}$ be the unit-sphere w.r.t to the $\ell_p$-norm in $\mathbb R^n$. We will be particularly ...
- 6,853
2
votes
1
answer
90
views
Asymptotics of $w^\top G^2 w$, where $w$ is a unit-vector, $G:=X^T(XX^T+t I_n)^{-1}X$, $t > 0$, and $X$ is an $n\times d$ gaussian random matrix
Let $X$ be an random $n \times d$ matrix with entries drawn iid from $N(0,1/d)$ and let $w$ be a unit-vector in $\mathbb R^d$. With $\lambda>0$, and define $G:=X^\top(XX^\top + \lambda I_n)^{-1}X$. ...
- 6,853
2
votes
1
answer
187
views
Compute the limit of trace of inverse of square of rank-1 perturbation of Wishart matrix
Let $a \ge 0$, $b,c>0$ be fixed constants, and let $X$ be an $m \times d$ random matrix with entries drawn iid from $N(0,1/d)$. Consider the random psd matrix $S := a 1_m 1_m^\top + b XX^\top + c ...
- 6,853
2
votes
1
answer
947
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
329
views
Matrix Bernstein's inequality: from tail probability to expectation
Let $X_i$ be independent, mean zero, $n\times n$, symmetric random matrices. $\|X_i\|\leq K$ almost sure for $\forall I$.
We have matrix Bernstein's inequality for the tail probability as follows
$$\...
- 49
2
votes
0
answers
131
views
Large deviation principle for product of iid bounded symmetric random variables
Let $n$ and $k$ be positive integers. Let $X$ be the empirical mean of $n$ iid Rademacher random variables. Note that the distribution of $X$ is symmetric about 0, and also $|X| \le 1$ w.p 1. Let $X_1,...
- 6,853
2
votes
0
answers
51
views
Spectral approximation of $(XX^\top/d)\circ(X\Sigma_dX^\top/d)$ where $X$ is an $n \times d$ random matrix with iid rows from $N(0,\Sigma_d)$
Let $X \in \mathbb R^{n \times d}$ be a random matrix with iid rows from $N(0,\Sigma_d)$ where $\Sigma_d$ is a $d \times d$ psd matrix verifying w.h.p,
$\mbox{trace}(\Sigma_d/d)= 1$.
$\|\Sigma_d\|_{...
- 6,853
2
votes
0
answers
172
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 ...
- 6,853
2
votes
1
answer
416
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 ...
- 6,853
2
votes
0
answers
140
views
Matrices with i.i.d. Heavy tail Columns
I'm wondering if there are any known results about minimum eigenvalue of matrices with i.i.d. heavy tailed columns. In particular, Theorem 5.62 of Roman Vershynin's notes (http://www-personal.umich....
- 859
1
vote
1
answer
207
views
Anti-concentration inequality for the eigenvalue of Gaussian matrix
Let $f(x) = f(x_1, . . . , x_n)$ be a polynomial of degree $d$ and $\text{Var}[f] = 1$. One result by Carbery and Wright shows that for any $t\in\mathbb{R}$ and $ε > 0$,
$$
\text{Pr}_{x\sim N^n}[|f(...
- 91
1
vote
1
answer
195
views
Concentration of a certain simple / well-structured random multilinear polynomial with growing degree
Let $k$ and $N_1$ be positive integers and set $N=kN_1$. Partition $[N] := \{1,2,\ldots,N\}$ $k$ disjoint from $G_1,\ldots,G_k$ of each of size $N_1$, and let $\mathcal T(k,N_1)$ be a transversal of ...
- 6,853
1
vote
1
answer
104
views
Limiting value of $\dfrac{1_n^\top B^{-1} A B^{-1} 1_n}{d}$, where $A=WW^\top + a I_n$, $B = WW^\top + b I_n$, and $W \sim N(0,\Sigma_d)$
Let $n$ and $d$ be positive integers with
$$
n,d \to \infty, \quad n/d \to \rho \in (0,\infty).
$$
Let $\Sigma_d$ be a psd matrix such that
$\mbox{trace}(\Sigma_d) = 1$.
$\|\Sigma_d\|_{op} = \mathcal ...
- 6,853
1
vote
1
answer
144
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 ...
- 6,853
1
vote
1
answer
201
views
Upper bound for $\mathbb P(|f(A+XX^T)-f(A)| > \epsilon)$, where $A$ is a fixed pd matrix and $X$ has random iid entries
Let $A$ be a fixed $n$ by $n$ real symmetric positive definite matrix with eigenvalues $\lambda_1 \ge \lambda_2 \ge \ldots \ge \lambda_n > 0$, and let $f(A):=\sum_{i=1}^n\log\lambda_i$, and let $X$ ...
- 6,853
1
vote
1
answer
409
views
The problems of global asymptotic freeness
Let $X_{N}\in\mathcal{M}_{N}\big(L^{\infty-}(\Omega,\mathbb{P})\big)$ be a $N\times N$ random complex matrix such its entries $(x_{ij}, 1\leq i, j\leq N)$ be $i.i.d.$, centred with variance $1$. $X_{...
- 137
1
vote
0
answers
57
views
Limiting value of expectation of trace of truncated Gram matrix
Let $n$ and $d$ be large positive integers such that $d/n = a \in (0,1)$, fixed. Let $x_1,\ldots,x_n$ be iid random vectors from $N(0,I_d)$. Fix $b \in (0,1]$ and a unit-vector $v \in \mathbb R^d$, ...
- 6,853
1
vote
0
answers
129
views
Concentration of a combinatorial sum
Let $X=(x_1,\ldots,x_p)$ be an $p \times n$ random matrix with iid entries from $\{\pm 1\}$, distributed so that $\mathbb P(x_{ij} = 1) \equiv 1/2$, where $x_i=(x_{i1},\ldots,x_{in})$. Let $y$ be a ...
- 6,853