All Questions
Tagged with linear-algebra pr.probability
235 questions
1
vote
0
answers
91
views
How to optimize parametric information-theoretic bounds?
I am faced with an information-theoretic upper bound, such as
\begin{align}
\sqrt{\alpha'}2^{I_\alpha(X;Y)},
\end{align}
where $I_\alpha(X;Y)$ is the Rényi mutual information with parameter $\alpha>...
- 287
0
votes
0
answers
94
views
Infinite sequence of PSD non-moments in two variables
Define a 2d sequence to be a mapping $a: \mathbb{N}^2 \to \mathbb{R}$ (where $\mathbb{N} = \{0, 1, \dots\}$). Here are two definitions of types of 2d sequences:
We say that a 2d sequence $a$ is a ...
- 161
1
vote
0
answers
80
views
Inequality involving random vectors and absolute values
Let $\mathbb{X}, \mathbb{Y} \subset \mathbb{R}^d$ be finite sets. Suppose random vectors $X \in \mathbb{X}$ and $Y \in \mathbb{Y}$ are sampled according to a joint distribution $\mathbb{P}_{XY}$. ...
0
votes
1
answer
158
views
Techniques for bounding the operator norm of the expectation of random matrix?
Let $\mu$ be a distribution on the unit sphere in $\mathbb{R}^n$. Let $u \sim \mu$ and consider the random matrix
$$
A = I_n - uu^T.
$$
Question: What techniques are available to provide (reasonably ...
- 420
0
votes
0
answers
31
views
What is the Fisher information matrix of the von Mises-Fisher distribution?
Assuming the von Mises-Fisher distribution as
$$f_{p}(\mathbf{x}; \boldsymbol{\mu}, \kappa) = C_{p}(\kappa) \exp \left( {\kappa \boldsymbol{\mu}^\mathsf{T} \mathbf{x} } \right),$$
where $\kappa \ge 0$,...
- 287
1
vote
0
answers
50
views
Interpolation in convex hull
I'm reading a paper, Learning in High Dimension Always Amounts to Extrapolation, that provides a result I don't understand.
It provides this theorem which I do understand:
Theorem 1: (Bárány and ...
0
votes
1
answer
100
views
Projection on a countable union of linear subspace
For any natural number $n$, $V_n$ denotes a closed linear subspace of a $L_2(m)$ space, which is an Hilbert Space, where $m$ denotes a finite measure. Moreover $(V_n)$ is increasing, that is $V_n$ is ...
- 31
0
votes
0
answers
66
views
Random elliptical potential lemma
Elliptical Potential Lemma: Let $V_0 \in \mathbb{R}^{d \times d}$ be positive definite and $a_1,a_2,...,a_n \in \mathbb{R}^{d}$ be a sequence of vectors with $||a_t ||_2 \leq L < \infty$ for all $t ...
- 61
1
vote
1
answer
99
views
Maximum column norm of random $A^{-1}B$
Suppose that $A$ is an $n$ by $n$ Gaussian matrix (each component i.i.d. normal distributed with mean 0 and variance 1). Let $b$ be a $n$-Gaussian vector. Then it could be easily proven that the ...
- 33
1
vote
2
answers
66
views
Distribution of the constraint matrix conditioned on the solution of the linear system
Suppose that A is a random matrix in $R^{n\times n}$, with each component independently and identically distributed (iid) according to $\mathcal{N}(0,1)$. Additionally, b is a random vector in $R^n$, ...
- 33
1
vote
1
answer
141
views
Does a random matrix over $\mathbb{Z}_q$ map linearly independent vectors to statistically independent vectors?
Suppose $A \in \mathbb{Z}_q^{n \times m}$ is a random $n \times m$ matrix whose entries are i.i.d. uniform over $\mathbb{Z}_q=\mathbb{Z}/q\mathbb{Z}$, where $q\geq2$. Let $\mathbf{x}_1, \ldots, \...
- 503
4
votes
0
answers
1k
views
Number of arrangements that contain at least 1 path from top to bottom of 2D matrix
I have a $n\times n$ matrix of objects. $n'$ objects are black, and the rest $n^2-n'$ are white.
With that information, I can easily calculate the total number of black element arrangements that exist ...
- 47
7
votes
2
answers
347
views
Matrices over $\mathbb{F}_p$ that have nonzero determinant under any element permutation
$\DeclareMathOperator\GL{GL}$A few months ago, the following discussion took place on AoPS, concerning matrices that have nonzero determinant under any permutation of their entries: https://...
- 541
36
votes
4
answers
2k
views
Determinant of the random matrix $X^2+Y^2$
$\DeclareMathOperator\Prob{Prob}$Let $X,Y\in M_n(\mathbb{R})$ be $2$ random matrices. The entries of $X,Y$ are i.i.d. variables. They follow the standard normal law $N(0,1)$.
i) When $n=2,3,4$, one ...
- 3,741
0
votes
1
answer
67
views
Multivariate random variable problem [closed]
I'm stuck on this problem:
Let a random vector $X$ be given in $\mathbb{R^{10}}$ with the standard scalar product. It is known that $\mathbb{E}[XX^T] = 5I_{10}$, $I_{10}$ – identity matrix of order 10....
- 69
9
votes
2
answers
954
views
Direct proof of unique invariant distribution for ergodic, positive-recurrent Markov chain
I posted the following question on MSE, feeling that it perhaps isn't research level mathematics, but didn't get any bites. So, I am crossposting here.
The following ergodic theorem is well known.
...
- 165
2
votes
0
answers
269
views
Singular values of Kronecker product of random matrices
I'm looking for a way to evaluate $\mathbb{E} \| (\mathbf{X} \mathbf{Q})^+ \|$ for a random matrix $\mathbf{X} \in \mathbb{R}^{r \times n}$ and a (fixed) matrix $\mathbf{Q} \in \mathbb{R}^{n \times \...
- 121
2
votes
2
answers
215
views
How to analyze the value of convergence of functions of random matrices?
Consider a random i.i.d matrix $\mathbf{A}_{m\times n}$ with entries generated from a complex Gaussian distribution with zero mean and unit variance. I am interested in the large dimension analysis of ...
- 287
4
votes
1
answer
250
views
Does a subset with small cardinality represent the whole set?
Assume that we have heavy-tailed distribution $F(x)$ such that
\begin{align}
F(x)=\mathbb{P}[X\geq x]=x^{-0.5}.
\end{align}
Then, we produce $N$ independent samples $X_1,X_2,\ldots,X_N$ from this ...
- 287
8
votes
1
answer
324
views
On a matrix inequality
$\newcommand{\R}{\mathbb R}\newcommand{\tr}{\operatorname{tr}}$It follows from Proposition 7 and this recent answer that, for any positive-definite $n\times n$ symmetric real matrices $A$ and $B$,
$$\...
- 128k
1
vote
0
answers
64
views
Maximize trace of precision matrix
Let Q be the uniform distribution over the hypercube $\{1, -1\}^{d}$.
Let P be any distribution that has support including the hypercube.
Define $\Sigma=\mathbb{E}_{x \sim P}[x x^\top]$.
We'd like to ...
- 515
-1
votes
1
answer
77
views
Variance of the logarithm of the mixed Rademacher and complex Gaussian distribution
Consider the scenario where $X$ is a Rademacher random variable taking values $\{−1,+1\}$ with equal probability, and $Z$ is a complex Gaussian random variable with a mean of $0$ and a variance of $\...
- 287
0
votes
1
answer
103
views
Is it reasonable to consider the subgaussian property of the logarithm of the Gaussian pdf?
Let $Y$ denote a Gaussian random variable characterized by a mean $\mu$ and a variance $\sigma^2$. Consider $N$ independent and identically distributed (i.i.d.) copies of $Y$, denoted as $Y_1, Y_2, \...
- 287
2
votes
1
answer
239
views
Hoeffding's Lemma for bounded complex random variables?
If we have a real random variable $X$ such that $a\leq X\leq b$ almost surely, we can establish the following inequality:
\begin{align}
\mathbb{E}\left[\exp\Big(t(X-\mathbb{E}[X])\Big)\right]\leq\exp\...
- 287
14
votes
1
answer
417
views
Lipschitz property of the determinant
$\newcommand{\A}{\mathcal A}\newcommand{\Tr}{\operatorname{tr}}$For $c$ and $C$ such that $0<c<C<\infty$, let $\A_{d;c,C}$ denote the set of all symmetric positive-definite real $d\times d$ ...
- 128k
1
vote
1
answer
115
views
The effect of a small change of the probability distribution on the output of the function
Suppose $X$, $Y$, $X'$ and $Y'$ are random variables whose probability density follows the following relations.
\begin{align}
\|p_X-p_{X'}\|_{\mathrm{TV}}&\leq\epsilon_1,\\
\|p_Y-p_{Y'}\|_{\mathrm{...
- 287
6
votes
0
answers
279
views
Estimating $E[\operatorname{Tr}(ABABBA..)]$ for random shuffling of $A,B$?
How can I estimate the following value where $A,B$ are $d\times d$ matrices and expectation is taken over all random permutations of the product?
$$E_\text{shuffle}[\operatorname{Tr}\underbrace{AA\...
- 2,242
0
votes
1
answer
115
views
Approximation for an expectation expression
Let $\mathbf{x} \in \mathbb{C}^M$ is an unknown distributed random vector (certainly not gaussian), and matrix $\mathbf{A}\in \mathbb{C}^{M \times M}$ which is fix (known). Also, assume we know the ...
- 25
1
vote
0
answers
66
views
CLT of the left singular vectors of i.i.d. data matrix
Let $\mathbf{X}$ be $(n \times p)$-dimensional random 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]^\...
- 284
-1
votes
1
answer
68
views
Bound for an expectation of random matrix with quantized random variable
Let random matrix $\mathbf{X} \in \mathbb{C^{\mathrm{m} \times \mathrm{n}}}$ and random vector $\mathbf{y} \in \mathbb{C^{\mathrm{m} \times 1}}$ are unknown distributed, but their covariance and ...
- 25
1
vote
1
answer
165
views
Bound for expectation of random matrix
Let random matrix $\mathbf{X} \in \mathbb{C^{\mathrm{m} \times \mathrm{n}}}$ and random vector $\mathbf{y} \in \mathbb{C^{\mathrm{m} \times 1}}$ are unknown distributed, but their covariance and ...
- 25
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
82
views
Does the following expectation-based inequality hold?
Let $\mathcal{F}$ be the space of all functions that uniformly and independently map the alphabet $\mathcal{X}$ to the set $\{1,2,\ldots,A\}$. Let $p(x|y)$ be an arbitrary conditional probability ...
- 287
0
votes
1
answer
80
views
Probability of accurate sparse recovery
Suppose $\mathbf{A}_{k\times n}$ ($k<n$) is a matrix whose entries are generated i.i.d. from Gaussian distribution and $\mathbf{s}_{n\times 1}$ is a sparse vector with $m$ sparsity (i.e., $\|\...
- 287
3
votes
2
answers
262
views
Optimal Kelly criterion for process with N discrete outcomes
I am trying to come up with a generalisation of the Kelly formula for optimal fractional betting but and have hit a roadblock. The Kelly criterion is usually explained via a game that ends in 1 of 2 ...
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,242
1
vote
1
answer
185
views
A system of linear equations with way too many unknowns — constructing a bivariate distribution from marginals and "the diagonal"
Suppose we are given information about distributions of random permutations $\sigma, \tau : \Omega \to S_n$ as follows:
$$p^1_{k,l} = \mathbb P(\sigma(k) = l), p^2_{k',l'} = \mathbb P(\tau(k) = l), p^{...
- 677
2
votes
1
answer
330
views
Probability density of a hyperplane for a Gaussian distribution
I have a vector $\mathbf{x}$ with a multivariate Gaussian distribution
$$P[\textbf{x}\in S]
=\int_{\textbf{x}\in S}
\det(2\pi H^{-1})^{-1/2}\exp(-\frac{1}{2} \textbf{x}^T H\textbf{x}) \, d\textbf{x}$$...
- 162
7
votes
2
answers
1k
views
Why is the spectrum of Erdős–Renyi random graph approximately symmetric?
I am recently self-learning random matrix theory and made some simulations about the spectrum of Erdős–Renyi random graph $G(n,p)$ when $np\to\infty$,
and $np\to c=2,3$.
The plots above are already ...
- 715
2
votes
0
answers
89
views
Odd $k$-cycle counts in graph with adjacency matrix $A$ is leading term in $\operatorname{tr} A^k$?
In a recent paper of Neeman, Radin, and Sadun, Moderate Deviations in Cycle Count, in the first line of section 7.3 they wrote $\tau_k(A)=\frac{\operatorname{tr}A^k}{n^k}+O(\frac 1n)$, but I don't ...
- 715
2
votes
2
answers
104
views
Inequality for matrix with rows summing to 1
Let $A$ be real matrix with $M > 1$ rows and $K > 2$ columns, and each entry $a_{m,k} \in (0,1)$, with each row summing to $1$. For all $m$
$$
\sum_{k=1}^{K} a_{m,k} = 1
$$
I want to find out if ...
- 23
1
vote
1
answer
143
views
Permute a sparse random matrix to resemble a diagonal matrix as much as possible
Say we generate an $N \times N$ sparse random matrix $W$, where each element $W_{ij}$ was independently chosen to be $1$ with probability $p=\frac{a}{N}$, and $0$ with probability $1-p$. We are ...
- 433
1
vote
2
answers
122
views
Rank inequality for spectral measures
Let $A$ and $B$ be $n \times n$ Hermitian matrices and denote by $F_A$ and $F_B$ the distribution functions related to the spectral measures $L_A$ and $L_B$ of $A$ and $B$, respectively. Setting $k = \...
- 730
1
vote
1
answer
160
views
Estimates of product of eigenvalues gaps for Wigner matrices
Let $W_n$ be an $n\times n$ Wigner matrix$^{1}$, and let $\lambda_1\le \lambda_2\le \cdots \le \lambda_n$ be the eigenvalues of $\frac{W_n}{\sqrt{n}}$.
My question. For any fixed $i\in\{1,\dots,n\}$, ...
- 2,712
4
votes
0
answers
196
views
What is the minimum nonzero rank in a random subspace of matrices?
Fix positive integers $m$, $n$, and $k\leq mn$, and draw a $k$-dimensional subspace $S\leq\mathbb{R}^{m\times n}$ uniformly from the Grassmannian.
What is known about the random variable
$R(m,n,k):=\...
- 7,633
10
votes
1
answer
337
views
What are the predictive implications of conditional non-commutative probability?
To simplify things, let's consider the Hilbert approach to quantum probability over a finite dimensional vector space $V$ of dimension $n$.
In this context a state $S$ is a positive semi-definite ...
- 323
2
votes
2
answers
248
views
On an angle distribution of a random linear subspace of a given dimension
$\newcommand\R{\mathbb R}$ Let $u$ be a fixed unit vector in $\R^n$, and let $\Pi_u$ be the hyperplane in $\R^n$ with normal vector $u$. Let $B$ be the (say open) unit ball in $\R^n$ centered at the ...
- 128k
2
votes
0
answers
43
views
Approximation of Grassmanian cubatures through random noise
Let $G_{1,d}$ be the $1$-grassmanian in $d$ dimensions, that is the set of linear projections from $\mathbb R^d$ to $\mathbb R$. We can see it as $\mathbb S(\mathbb R^d)$, as any projection can be ...
- 686
1
vote
1
answer
158
views
Generating iid random vectors such that the distribution of their dot product is $\mathit{Uniform}[a, b]$
Take two independent and identically distributed random vectors $X_i$, $X_j$.
I want to find a multivariate distribution for these vectors such that the dot product $X_i^\top X_j \sim U[a, b]$.
This ...
- 119
3
votes
1
answer
843
views
Top singular value of large random matrices: concentration results
Let $A$ be a $n\times m$ random matrix, whose elements $a_{ij}$ are independent standard Gaussian random variables.
I am interested in the case $n=\alpha N\,$, $\,m=(1-\alpha)N$ for $\alpha\in(0,1)$ ...
- 311