All Questions
29 questions with no upvoted or accepted answers
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
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
0
answers
638
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
416
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
0
answers
334
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
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
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 ...
- 393
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
129
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
415
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
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
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 \...
- 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,...
- 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 ...
- 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-...
- 6,853
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. ...
- 111
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 ...
- 363
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)\...
- 859
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 $\...
- 6,853