alternative asymptotic bounds

52 Views Asked by At

I have an $n$ by 1 vector of weights $w$, and an $n$ by $k$ matrix, $\Gamma$. I have that $w'w$ is $\mathcal{O}(1)$, $\frac{\Gamma'\Gamma}{n}=\mathcal{O}(1)$ and $\frac{\Gamma\Gamma'}{n}=\mathcal{O}(1)$ as $n \rightarrow \infty$. But, I am working with the scalar expression $w'\Gamma\Gamma'w$, and I am trying to show this scalar term is $\mathcal{O}(1)$. The difficulty is that the weight vector, $w$, is not simply $1/n$.

I am trying $\,\, (\gamma_i$ is $k$ by 1 for each $i=1,\dots,n$)

\begin{align} w'\Gamma\Gamma'w &=\sum_{i=1}^n \sum_{j=1}^n w_i^2 \gamma'_i\gamma_j \\ &\leq \sum_{j=1}^n \gamma_j' \left(\sum_{i=1}^n w_i^2 \gamma_i' \right)^2 \gamma_j \\ & \leq \sum_{i=1}^n w_i^4 \sum_{j=1}^n \gamma_j'(\Gamma'\Gamma)\gamma_j \end{align} Where I apply Cauchy Schwarz to the sum over $j$ for the first inequality, and then again to the inner term's sum (the one being squared). I know that $\sum_{i=1}^N w_i^4=\mathcal{O}(1)$, but then it appears I'm left with an expression $\sum_{j=1}^N \gamma_j'(\Gamma'\Gamma)\gamma_j$ which is rising in $n$.

Alternatively, I also tried, \begin{align} w'\Gamma\Gamma'w \leq w'w \cdot \lambda_{max}(\Gamma\Gamma') \end{align} Where $\lambda_{max}(\cdot)$ denotes the maximum eigenvalue of the matrix in its argument. But $\lambda_{max}(\Gamma\Gamma')$ is $\mathcal{O}(n)$, again rising with $n$.

I was thinking to possibly work with the $k$ x $1$ object $\Gamma'w$ since $w'\Gamma\Gamma'w=||\Gamma'w||_2^2$ and make an assumption on this norm in the worse case scenario, but it seems that the assumption can possibly be contradicted since there is enough structure embedded into these objects as is?

Any help would be appreciated.

1

There are 1 best solutions below

0
On BEST ANSWER

Take $w = e_1 = (1, 0, 0, \dots)$ to be a standard basis vector and take $\Gamma$ to be "diagonal" with entries $\sqrt{n}$. Then, if I am not horribly mistaken, $w^T \Gamma \Gamma^T w = n$.