Skip to main content

All Questions

Filter by
Sorted by
Tagged with
0 votes
1 answer
108 views

RMT for modified Wishard matrix $Y'Y$ (where $i$th row of $Y$ is zero if $|x_i^\top u| \le \theta$; else it equals $x_i$)

Let $n$ and $d$ be positive integers tending to infinity such that $d/n \to \phi \in (0,\infty)$. Let $X$ be an $n \times d$ random matrix with iid rows $x_1,\ldots,x_n$ from $N(0, \Sigma)$, where $\...
dohmatob's user avatar
  • 6,853
-1 votes
1 answer
163 views

Is it true that if a random vector has independent coordinates each bounded by $1$ then $P[ \|X\| \leq \epsilon\sqrt{n}] \leq (C\epsilon)^{n}$?

I'm studying Vershynin's well-written book on "High Dimensional Probability" and the third chapter on concentration of random vectors. Exercise 3.1.7 from the book is the following. Let $X =...
user135520's user avatar
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$, ...
dohmatob's user avatar
  • 6,853
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 =...
Drew Brady's user avatar
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(...
qmww987's user avatar
  • 91
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 $$\...
happyle's user avatar
  • 49
2 votes
0 answers
130 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,...
dohmatob's user avatar
  • 6,853
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 ...
dohmatob's user avatar
  • 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 ...
dohmatob's user avatar
  • 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 ...
dohmatob's user avatar
  • 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 ...
arriopolis's user avatar
0 votes
1 answer
108 views

On the invertibility of $Z^\top Z$, where $Z$ is a Random matrix with concentrated weakly correlated entries

Let $d$, $n$, and $m$ be large positive integers. Let $X=(x_1,\ldots,x_n) \in \mathbb R^{n \times d}$ be a random matrix iid rows from some distribition $P$ on $\mathbb R^d$ which admits a density. ...
dohmatob's user avatar
  • 6,853
2 votes
1 answer
946 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 ...
dohmatob's user avatar
  • 6,853
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 ...
dohmatob's user avatar
  • 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 ...
dohmatob's user avatar
  • 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\|_{...
dohmatob's user avatar
  • 6,853
1 vote
1 answer
160 views

Given iid $w_1,\dotsc,w_N \sim N(0,1/d)$ iid, find a simple matrix $A$ s.t $\|aa^T-A\|_\text{op}\to0$, where $a_i := E_{G \sim N(0,1)}[f(\|w_i\| G)]$

Let $d$ and $N$ be two large comparable integers, for example assume $$ N,d \to \infty, \quad d/N \to \gamma \in (0,\infty). $$ Let $w_1,\dotsc,w_N$ be iid from $N(0,(1/d)I_d)$ and let $f:\mathbb R \...
dohmatob's user avatar
  • 6,853
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,...
dohmatob's user avatar
  • 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$. ...
dohmatob's user avatar
  • 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 ...
dohmatob's user avatar
  • 6,853
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 ...
dohmatob's user avatar
  • 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 ...
dohmatob's user avatar
  • 6,853
3 votes
0 answers
225 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....
M-Brust's user avatar
  • 31
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 ...
dohmatob's user avatar
  • 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 ...
dohmatob's user avatar
  • 6,853
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 ...
dohmatob's user avatar
  • 6,853
1 vote
0 answers
96 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 ...
dohmatob's user avatar
  • 6,853
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 ...
dohmatob's user avatar
  • 6,853
1 vote
0 answers
57 views

Good lower-bound for $\inf_{x \in \Delta_n} \|Gx\|$ where $G$ is an $N \times n$ random matrix with iid entries from $\mathcal N(0,1/\sqrt{N})$

Let $G$ be an $N \times n$ random matrix with independent entries distributed according to a centered Gaussian with variance $1/\sqrt{N}$ and let $n/N = \lambda \in (0, 1)$. Let $\Delta_n$ be the $(n-...
dohmatob's user avatar
  • 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) ...
dohmatob's user avatar
  • 6,853
0 votes
1 answer
280 views

Lower-bound on smallest singular-value of rectangular random matrix

Let $X$ be a random $N \times n$ matrix with iid entries from $\mathcal N(0, 1)$ and with $n/N =: \lambda(N,n) \le \lambda_0$, for some $\lambda_0 \in (0, 1)$. That is, $X$ is genuinely rectangular (...
dohmatob's user avatar
  • 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$ ...
dohmatob's user avatar
  • 6,853
-1 votes
1 answer
138 views

On the concentration of Lipschitz functions near its expectation, where the vector has identical but not independent, components

Consider the random vector $X:=(X_1\dots X_1) \in \mathbb{R}^n, X_1 \sim \mathcal{N}(0,1).$ Notice the identical components, they're identically distributed but not independent. Now, I was wondering ...
Learning math's user avatar
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 ...
gradstudent's user avatar
  • 2,246
0 votes
1 answer
379 views

Concentration of norm of linearly transformed normal random vector as dimension go to infinity

Earlier asked on MSE, but didn't get an answer, so posting here: Let $X=(X_1 \dots X_n) \in \mathbb{R}^n, X_i\sim N(0,1), iid.$ Let $B: \mathbb{R}^n \to \mathbb{R}^n $ be the diagonal linear map: $...
Learning math's user avatar
0 votes
1 answer
58 views

Good upper-bound for $\mathbb E_A[e^{-t\|A\|_2}]$, for $t\ge0$ and random m by n matrix with iid entries with law $N(0,1)$

Let $A$ be a random $m$-by-$n$ matrix with iid $N(0,1)$ entries, $m$ and $n$ large with $n/m \longrightarrow \alpha \in (0, 1)$ . Let $\|A\|_2$ be the largest singular value of $A$ (i.e the spectral ...
dohmatob's user avatar
  • 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$. ...
dohmatob's user avatar
  • 6,853
4 votes
0 answers
641 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-...
Learning math's user avatar
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_{...
Iliyo's user avatar
  • 137
3 votes
1 answer
178 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$-...
neverevernever's user avatar
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 ...
felasfaw's user avatar
  • 221
1 vote
0 answers
175 views

Matrix Bernstein for spherical random variables

Theorem 4.1 in Tropp's Matrix Concentration Inequalities provides an exponential concentration inequality for the spectral norm of a matrix $Z = \sum_i \gamma_i B_i $, where $\gamma_i$ are an i.i.d. ...
VHarisop's user avatar
  • 111
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 ...
ie86's user avatar
  • 195
3 votes
0 answers
125 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 ...
Cain's user avatar
  • 393
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....
mohi's user avatar
  • 859
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}$ ...
mohi's user avatar
  • 859
1 vote
0 answers
146 views

minimum eigenvalue of Katri-Rao product of two Gaussian matrices

Let $\mathbf{A}\in\mathbb{R}^{k\times n}$ and $\mathbf{B}\in\mathbb{R}^{d\times n}$ be independent matrices with i.i.d. $\mathcal{N}(0,1)$ entries. I'm interested in lower bounding the minimum ...
Anahita's user avatar
  • 363
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 ...
user avatar
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 ...
Daniel Soudry's user avatar
1 vote
0 answers
295 views

One-sided Talagrand concentration inequality for empirical processes

Let $\mathcal{F}$ denote a function class. A classic result by Talagrand states that \begin{align*} \mathbb{P}\bigg\{\sup_{f\in\mathcal{F}}\big|\sum_{i=1}^nf(X_i)-\mathbb{E}\big[\sum_{i=1}^nf(X_i)\...
mohi's user avatar
  • 859