Skip to main content
MathOverflow

Return to Question

edited tags
Link
tony
tony
  • 405
  • 2
  • 8
Capitalise title
Source Link
LSpice
LSpice
  • 12.9k
  • 4
  • 45
  • 69

upper Upper bounding a inner product between gaussian wignerWigner matrix and a rank 2 matrix

Let $W$ be a standard gaussian Wigner matrix, i.e., $W_{ij}=W_{ji}$, $W_{ii}$ is iid standard gaussian. Consider

$$\langle W,QQ^T\rangle$$

where $\langle,\rangle$ is FrobenuousFrobenius inner product, $Q$ is a $n\times 2$ matrix such that the $i$-row is $[\cos\theta_i,\sin\theta_i]$, and $\theta_i\in[0,2\pi]$. Thus it is equivalent to the form $$\sum_{i,j}W_{ij}\cos(\theta_i-\theta_j)$$$$\sum_{i,j}W_{ij}\cos(\theta_i-\theta_j).$$

My question is: what is the upper bound for it? Could we obtain $$\forall Q, \langle W,QQ^T\rangle\leq n\log n$$$$\forall Q, \langle W,QQ^T\rangle\leq n\log n?$$

If not, how small we could achieve?

Note that we need the upper bound uniformly hold for all $Q$, in other words, for all $\theta\in[0,2\pi]^n$. If we fix one $Q$, then $\langle W,QQ^T\rangle\leq n\log n$ holds with high probability.

Motivation This question comes from my research, and the bound I obtained is $n^{3/2}$ by standard $\epsilon$-net argument (discretilizediscretize the region into equally spaced points, and do union bound over them), however this bound is suboptimal for my purpose. I am seeking for a better upper bound, that smaller than $n^{3/2}$. The smaller, the better. And $n\log n$ is the best.

upper bounding a inner product between gaussian wigner matrix and a rank 2 matrix

Let $W$ be a standard gaussian Wigner matrix, i.e., $W_{ij}=W_{ji}$, $W_{ii}$ is iid standard gaussian. Consider

$$\langle W,QQ^T\rangle$$

where $\langle,\rangle$ is Frobenuous inner product, $Q$ is a $n\times 2$ matrix such that the $i$-row is $[\cos\theta_i,\sin\theta_i]$, and $\theta_i\in[0,2\pi]$. Thus it is equivalent to the form $$\sum_{i,j}W_{ij}\cos(\theta_i-\theta_j)$$

My question is: what is the upper bound it? Could we obtain $$\forall Q, \langle W,QQ^T\rangle\leq n\log n$$

If not, how small we could achieve?

Note that we need the upper bound uniformly hold for all $Q$, in other words, for all $\theta\in[0,2\pi]^n$. If we fix one $Q$, then $\langle W,QQ^T\rangle\leq n\log n$ holds with high probability.

Motivation This question comes from my research, and the bound I obtained is $n^{3/2}$ by standard $\epsilon$-net argument (discretilize the region into equally spaced points, and do union bound over them), however this bound is suboptimal for my purpose. I am seeking for a better upper bound, that smaller than $n^{3/2}$. The smaller, the better. And $n\log n$ is the best.

Upper bounding a inner product between gaussian Wigner matrix and a rank 2 matrix

Let $W$ be a standard gaussian Wigner matrix, i.e., $W_{ij}=W_{ji}$, $W_{ii}$ is iid standard gaussian. Consider

$$\langle W,QQ^T\rangle$$

where $\langle,\rangle$ is Frobenius inner product, $Q$ is a $n\times 2$ matrix such that the $i$-row is $[\cos\theta_i,\sin\theta_i]$, and $\theta_i\in[0,2\pi]$. Thus it is equivalent to the form $$\sum_{i,j}W_{ij}\cos(\theta_i-\theta_j).$$

My question is: what is the upper bound for it? Could we obtain $$\forall Q, \langle W,QQ^T\rangle\leq n\log n?$$

If not, how small we could achieve?

Note that we need the upper bound uniformly hold for all $Q$, in other words, for all $\theta\in[0,2\pi]^n$. If we fix one $Q$, then $\langle W,QQ^T\rangle\leq n\log n$ holds with high probability.

Motivation This question comes from my research, and the bound I obtained is $n^{3/2}$ by standard $\epsilon$-net argument (discretize the region into equally spaced points, and do union bound over them), however this bound is suboptimal for my purpose. I am seeking for a better upper bound, that smaller than $n^{3/2}$. The smaller, the better. And $n\log n$ is the best.

Source Link
tony
tony
  • 405
  • 2
  • 8

upper bounding a inner product between gaussian wigner matrix and a rank 2 matrix

Let $W$ be a standard gaussian Wigner matrix, i.e., $W_{ij}=W_{ji}$, $W_{ii}$ is iid standard gaussian. Consider

$$\langle W,QQ^T\rangle$$

where $\langle,\rangle$ is Frobenuous inner product, $Q$ is a $n\times 2$ matrix such that the $i$-row is $[\cos\theta_i,\sin\theta_i]$, and $\theta_i\in[0,2\pi]$. Thus it is equivalent to the form $$\sum_{i,j}W_{ij}\cos(\theta_i-\theta_j)$$

My question is: what is the upper bound it? Could we obtain $$\forall Q, \langle W,QQ^T\rangle\leq n\log n$$

If not, how small we could achieve?

Note that we need the upper bound uniformly hold for all $Q$, in other words, for all $\theta\in[0,2\pi]^n$. If we fix one $Q$, then $\langle W,QQ^T\rangle\leq n\log n$ holds with high probability.

Motivation This question comes from my research, and the bound I obtained is $n^{3/2}$ by standard $\epsilon$-net argument (discretilize the region into equally spaced points, and do union bound over them), however this bound is suboptimal for my purpose. I am seeking for a better upper bound, that smaller than $n^{3/2}$. The smaller, the better. And $n\log n$ is the best.