# is it true that the infinity norm can be bounded using the $L_2$ norm the following way?

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.

-
In finite dimensional spaces spaces, norms are equivalent. – Mhenni Benghorbal Sep 4 '12 at 16:35
@Mhenni I am not sure how this answers my question? – kloop Sep 4 '12 at 16:47

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}}$.

-
could you explain the first equality equation you wrote? (and the reference please) – sara Sep 4 '12 at 17:19
For any row vector $w$ and matrix $M$ with compatible dimensions, the $i$'th entry of $wM$ is the product of $w$ and the $i$'th column of $M$. – Robert Israel Sep 4 '12 at 17:21
thanks Robert -- your answers are always very concise and accurate. – kloop Sep 7 '12 at 1:50

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<n$ (infinity norm of a matrix is the maximum absolute row sum of the matrix). And with the same argument $\|B\|_1<m$.

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)

-
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$ – sara Sep 4 '12 at 17:15