1
$\begingroup$

I am interested in finding a better upper bound for $|u^*Av|$, with $A$ a random Hermitian matrix that satisfies $(1-\delta)I\preceq A \preceq (1+\delta)I$ with high probability- at least $1-C\mathrm{e}^{-c(\delta)}$, with $C$, $c$ absolute constants independent of $A$ or its size.

It's obvious that
\begin{align} |u^*Av|\leq\|A\|\|u\|\|v\| \end{align} but I believe that there are cases where the bound can be improved, in particular for the off-diagonal terms, i.e. $|e_i^\mathsf{T}Ae_j|$ with $e_n$ the $n$-th canonical vector and $i\neq j$.

I am aware of the Hanson-Wright inequality for the tail of these inner products (see this MO answer), but wasn't sure how to use this to bound the inner product in reference to $\delta$.

$\endgroup$

1 Answer 1

2
$\begingroup$

Since $(1-\delta)I \preceq A \preceq (1+\delta)I$ w.h.p., we have $-\delta I \preceq A-I \preceq \delta I$ w.h.p., i.e. $\|A-I\| \le \delta$ w.h.p.

Hence, we can trivially derive the bound \begin{align*} |u^*Av| &= \left|u^*v + u^*(A-I)v\right| \\ &\le |u^*v| + |u^*(A-I)v| \\ &\le |u^*v|+\|A-I\|\|u\|\|v\| \\ &\le |u^*v|+\delta\|u\|\|v\| \end{align*} with high probability. If $u$ and $v$ are nearly parallel (or anti-parallel), this will be similar to the bound you obtained. But if $u$ and $v$ are nearly orthogonal and $\delta$ is small, this bound will be much smaller than $(1+\delta)\|u\|\|v\|$.

$\endgroup$
1
  • 1
    $\begingroup$ Thanks, this is exactly what I was aiming for and didn't even realize this. $\endgroup$
    – cjferes
    Aug 20, 2021 at 19:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .