2
$\begingroup$

Let $v \in \mathbb{R}^k$, and let $A \in \mathbb{R}^{m \times k}$ and let $B \in \mathbb{R}^{m \times n}$ such that each column of $B$, $B_i$, has $||B_i||_2 \le 1.$

Is it true that:

  1. $||v A^{\top} B||_{\infty} \le ||v A^{\top}||_2$ ?

  2. If the spectral norm of $A$ is such that $||A||_{\mathrm{spectral}} \le 1$, is it true that $||v A^{\top}||_2 \le ||v||_2$ ?

Thanks.

  • 3
    @Mhenni I am not sure how this answers my question?2012-09-04

2 Answers 2

2

1) Cauchy-Schwarz says $|(v A^T B)_i| = |v A^T B_i| \le \|v A^T\|_2 \|B_i\|_2 \le \|v A^T\|_2$

2) Yes because the spectral norm is the operator norm corresponding to the $2$-norm on vectors, and $\|A\|_{\text{spectral}} = \|A^T\|_{\text{spectral}}$.

  • 0
    thanks Robert -- your answers are always very concise and accurate.2012-09-07
2

I give it a try with your first question: If $A\in\mathbb{R}^{m\times n}$ then $\frac{1}{\sqrt{n}}\|A\|_\infty\leq \|A\|_2\leq \sqrt{m}\|A\|_\infty$ $\frac{1}{\sqrt{m}}\|A\|_1\leq \|A\|_2\leq \sqrt{n}\|A\|_1$

Also $\|AB\|_a\leq \|A\|_a\|B\|_a$

Note that $\|B_i\|_2<1$ implies that absolute value of the every element of matrix B is less than 1, $|B_{ij}|<1$, then $\|B\|_\infty (infinity norm of a matrix is the maximum absolute row sum of the matrix). And with the same argument $\|B\|_1.

Then using these properties we have $\|vA^TB\|_\infty\leq \sqrt{n}\|vA^TB\|_2\leq \sqrt{n} \|vA^T\|_2\|B\|_2\leq \sqrt{nm} \|vA^T\|_2\|B\|_\infty\leq n\sqrt{nm} \|vA^T\|_2$ or $\|vA^TB\|_\infty\leq \sqrt{n}\|vA^TB\|_2\leq \sqrt{n} \|vA^T\|_2\|B\|_2\leq n \|vA^T\|_2\|B\|_1\leq nm \|vA^T\|_2$ (these are conservative bounds you can probably obtain a tighter bound)

  • 0
    I think the answer to the second question is yes. Spectral norm is the 2-induced norm for a square matrix then $\|A\|_{spectral}=\|A^T\|_{spectral}$. $\|vA^T\|_{spectral}\leq \|v\|_2\|A^T\|_2=\|v\|_2\|A\|_2\leq \|v\|_2$2012-09-04