5
$\begingroup$

Consider the matrix $\ell_{\infty} \to \ell_{\infty}$ operator norm for some matrix $A \in \mathbb{R}^{m \times n}$, given by $$ \| A \|_{\infty} := \sup_{x: \| x \|_{\infty} = 1} \| A x \|_{\infty} := \max_{j \in [m]} \| A_{i, :} \|_1. $$

Question: Prove (or disprove via counterexample) the following inequality: $$ \left\| V \begin{bmatrix} I_{k_1} & 0 \\ 0 & -I_{k_2} \end{bmatrix}V^\top \right\|_{\infty} \leq C \| V V^\top \|_{\infty}, $$ for $V$ satisfying $V^\top V = I$ and $V \in \mathbb{R}^{n \times k}$, with $k_1 + k_2 = k$.

This is not a homework problem, and I have been unable to come up with a counterexample (for randomly generated $V$, I find $C < 2$). I'm looking for some $C$ which is ideally in the range $o(\sqrt{k})$.

$\endgroup$
9
  • $\begingroup$ So what is C? Are you just trying to say that thing is bounded? $\endgroup$
    – Ovi
    Dec 13, 2019 at 20:17
  • $\begingroup$ @Ovi: I'm looking for as small a constant $C$ as possible. I edited the question to reflect this. $\endgroup$
    – VHarisop
    Dec 13, 2019 at 20:21
  • $\begingroup$ It is easy to prove that a $C$ such that the inequality holds must exist, if that's what you mean by "prove the inequality" without giving us a particular $C$. $\endgroup$ Dec 13, 2019 at 20:43
  • $\begingroup$ Could you give us some context for this problem? Would such a $C$ be useful for some goal? $\endgroup$ Dec 13, 2019 at 20:44
  • $\begingroup$ @Omnomnomnom: Sure. This inequality shows up as a step in analyzing the convergence rate of orthogonal iteration (for Hermitian matrices), when distance between eigenvectors and iterates is measured in the $\ell_{\infty}$ norm (up to an arbitrary rotation of the subspace). If $C \ll \sqrt{n}$, where $n$ is the size of the original matrix, we can ensure faster convergence than in the case where we care about the spectral norm (although they are asymptotically similar). $\endgroup$
    – VHarisop
    Dec 13, 2019 at 21:03

1 Answer 1

1
$\begingroup$

Let $V:=[v_1,\ldots,v_k]$ written as column vectors. Then $V^\top V=I$ means that $v_i$ are orthonormal.
Now, for any vector $x$,\begin{align} \|VJV^\top x\|_\infty&\le\|VJV^\top x\|_2\\ &=\|(v_1\cdot x)v_1+\cdots-(v_k\cdot x)v_k\|_2\\ &=\sqrt{\sum_{i=1}^k(v_i\cdot x)^2}\\ &=\|(v_1\cdot x)v_1+\cdots+(v_k\cdot x)v_k\|_2\\ &=\|VV^\top x\|_2\\ &\le\sqrt{n}\,\|VV^\top x\|_\infty\\ &\le\sqrt{n}\,\|VV^\top\|_\infty\|x\|_\infty \end{align}

Hence $\|VJV^\top\|_\infty\le\sqrt{n}\,\|VV^\top\|_\infty$.

That $\sqrt{n}$ cannot be improved upon much can be seen from this example:

$V:=[v_1,v_2]$, $v_1=(a,b,\ldots,b)$, $v_2=(-a,b,\ldots,b)$. The condition $V^\top V=I$, i.e., $v_1,v_2$ are orthonormal, then forces $a=\frac{1}{\sqrt{2}}$, $b=\frac{1}{\sqrt{2(n-1)}}$.

With $J=\begin{pmatrix}1&0\\0&-1\end{pmatrix}$, $$\|VV^\top\|_\infty=\left\|\begin{pmatrix}2a^2&0&\cdots&0\\0&2b^2&\cdots&2b^2\\\vdots\end{pmatrix}\right\|_\infty=2\max(a^2,(n-1)b^2)=1$$ $$\|VJV^\top\|_\infty=\left\|\begin{pmatrix}0&2ab&\cdots&2ab\\2ab&0&\cdots&0\\\vdots\end{pmatrix}\right\|_\infty=2(n-1)ab=\sqrt{n-1}$$

$\endgroup$

You must log in to answer this question.

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