Bernstein-type inequality

148 Views Asked by At

I'm stuck on the proof of a claim (which is for brevity omitted) from a research paper. The objective is to approximate the following non-convex constraint with a convex one:

$\textrm{Pr}\Big( \sum_{m=1}^{N_c} \big( \mathbf{v}_{mnk}^H \mathbf{Q}_{mnk}\mathbf{v}_{mnk} + 2\textrm{Re}\{ \mathbf{v}_{mnk}^H \mathbf{u}_{mnk} \} + c_{mnk} \big) \geq \sigma_{nk}^2 \Big)\geq 1-\rho, ~~~ \forall (n,k)$

where $\mathbf{v}_{mnk}\in\mathbb{C}^{N_t\times 1}$ and $\mathbf{v}_{mnk}\sim\mathcal{CN}(\mathbf{0},\mathbf{I}_{N_t})$, $\mathbf{Q}_{mnk}\in \mathbb{C}^{N_t\times N_t}$ and is Hermitian, $\mathbf{u}_{mnk}\in\mathbb{C}^{N_t\times 1}$, $c_{mnk}\in\mathbb{R}$, $\textrm{Re}\{.\}$ denotes the real part of a number, and $\sigma^2_{mnk}$ and $\rho$ are real positive constants.

Using the following lemma, the paper claims that the probabilistic inequality can be approximated with

$\sqrt{\sum_{m=1}^{N_t} (\lVert \mathbf{Q}_{mnk}\rVert^2_F + 2\lVert \mathbf{u}_{mnk} \rVert^2 )} \leq \frac{1}{\sqrt{2\delta_{nk}}} \Big( \sum_{m=1}^{N_t} [\textrm{trace}(\mathbf{Q}_{mnk})+c_{mnk}] - \delta_{nk} x_{nk} -\sigma_{nk}^2 \Big), ~ \forall (n,k).$

The lemma, known as the Bernstein-Lemma, is as follows:

Lemma. Let $G = \mathbf{v}^H\mathbf{Q}\mathbf{v} + 2\textrm{Re}\{\mathbf{v}^H\mathbf{u}\}$ where $\mathbf{Q} \in \mathbb{H}^{N_t}$ is a complex Hermitian matrix, $\mathbf{u} \in \mathbb{C}^{N_t}$, and $\mathbf{v} \sim \mathcal{CN}(0, \mathbf{I})$. Then for any $\delta > 0$, we have

Pr$\Big( G \geq \textrm{trace}(\mathbf{Q}) -\sqrt{2\delta}\sqrt{\lVert \mathbf{Q}\rVert^2_F + 2\lVert \mathbf{u} \rVert^2} - \delta s^+(−\mathbf{Q}) \Big) \geq 1 - e^{-\delta}$

where $s^+(\mathbf{Q}) = \max\{\lambda_{max}(−\mathbf{Q}), 0\}$ in which $\lambda_{max}(−\mathbf{Q})$ denotes the maximum eigenvalue of matrix $−\mathbf{Q}$, and $\lVert .\rVert_F$ denotes the matrix Frobenius norm.

Question. I can prove the claim using the lemma if the summation over $m$ didn't exist, i.e., if $m$ was fixed, but not with the summation. Can anybody help?

Edit: Okay, so, I have so far tried introducing the slack variable $t_{mnk}\geq \mathbf{v}_{mnk}^H \mathbf{Q}_{mnk}\mathbf{v}_{mnk} + 2\textrm{Re}\{ \mathbf{v}_{mnk}^H \mathbf{u}_{mnk} \} + c_{mnk}, ~ m\neq n$, (and introducing a corresponding second probabilistic constraint and applying the lemma to it) but still the solution I get is different from that in the paper. Specifically, this is what I've done.

$\textrm{Pr}\Big( \mathbf{v}_{nnk}^H \mathbf{Q}_{nnk}\mathbf{v}_{nnk} + 2\textrm{Re}\{ \mathbf{v}_{nnk}^H \mathbf{u}_{nnk} \} + c_{nnk} + \sum_{m\neq n} t_{mnk} \geq \sigma_{nk}^2 \Big)\geq 1-\rho, ~~~ \forall (n,k)\\ \textrm{Pr}\Big( t_{mnk} \geq \mathbf{v}_{mnk}^H \mathbf{Q}_{mnk}\mathbf{v}_{mnk} + 2\textrm{Re}\{ \mathbf{v}_{mnk}^H \mathbf{u}_{mnk} \} + c_{mnk} \Big) \geq 1-\mu, ~~ m\neq n$

Then, I can easily apply the lemma to get

$\sqrt{ (\lVert \mathbf{Q}_{nnk}\rVert^2_F + 2\lVert \mathbf{u}_{nnk} \rVert^2 )} \leq \frac{1}{\sqrt{2\delta_{nk}}} \Big( [\textrm{trace}(\mathbf{Q}_{nnk})+c_{nnk} + \sum_{m\neq n}t_{mnk}] - \delta_{nk} x_{nk} -\sigma_{nk}^2 \Big), ~ \forall (n,k),~\delta_{nk}=-\ln\rho,$

$\sqrt{ (\lVert \mathbf{-Q}_{mnk}\rVert^2_F + 2\lVert \mathbf{-u}_{mnk} \rVert^2 )} \leq \frac{1}{\sqrt{2\delta'_{nk}}} \Big( [\textrm{trace}(\mathbf{-Q}_{mnk})-c_{mnk}] - \delta'_{nk} y_{nk} + t_{mnk} \Big), ~ \forall (n,k),~ \delta'_{nk}=-\ln\mu,$

with the following additional constraints

$x_{nk}\geq 0, y_{nk}\geq 0\\ x_{nk}\mathbf{I}+\mathbf{Q}_{nnk} \succeq 0\\ y_{nk}\mathbf{I}-\mathbf{Q}_{mnk} \succeq 0, ~ m\neq n.$

My formulation is obviously different from the one in the paper and I still need to find a relation between $\mu$ and $\rho$.