1
$\begingroup$

The equivalence of vector norms on finite dimensional spaces immediately implies that all induced matrix norms are equivalent. Theorem 1, here, gives some of the popular induced norms. I am interested in the $\|A\|_{2,1}$ and $\|A\|_{2,2}$ norm, where \begin{equation*} \|A\|_{2,1}=\sup\{\|A\mathbf{x}\|_1:\|\mathbf{x}\|_2=1\} \end{equation*} and \begin{equation*} \|A\|_{2,2}=\sup\{\|A\mathbf{x}\|_2:\|\mathbf{x}\|_2=1\} \end{equation*}

According to my analysis so far; $\|A\|_{2,1}$ upper-bounds $\|A\|_{2,2}$. Can someone verify?

For a matrix $A\in\mathbb{R}^{n\times m}$

$\|A\|_{2,1}=\max_{u\in\{1,-1\}^n}\|A^Tu\|_2\leq \sqrt{\sum_{i=1}^m(\sum_{j=1}^n|a_{ij}|)^2}$.

And $\|A\|_{2,2}=\lambda_{\max}(A^TA)=\sigma_{\max}(A)\leq\|A\|_F= \sqrt{\sum_{i=1}^m\sum_{j=1}^n|a_{ij}|^2}$,

$\implies$ \begin{equation} \|A\|_{2,2}^2\leq{\sum_{i=1}^m\sum_{j=1}^n|a_{ij}|^2}\leq{\sum_{i=1}^m\left(\sum_{j=1}^n|a_{ij}|\right)^2} \end{equation}.

$\endgroup$

1 Answer 1

1
$\begingroup$

Your inequalities all go in the same direction, so you cannot possibly prove inequalities both ways.

You have the easy inequalities $$\|x\|_2\leq\|x\|_1\leq\sqrt n\,\|x\|_2.$$ So you immediately get (from the definition, not the characterization you quote) $$\tag{1}\bbox[5px,border:2px solid green]{\|A\|_{2,2}\leq\|A\|_{2,1}\leq\sqrt n\|A\|_{2,2}.} $$ These inequalities are sharp. For instance, if $A=E_{11}$, then $$ \|Ax\|_1=\|(x_1,0,\ldots,0)\|_1=|x_1|=\|x\|_2. $$ So $\|A\|_{2,2}=\|A\|_{1,1}$. And if $A=I_m$, then $\|Ax\|_1=\|x\|_1$, so $$ \|A\|_{2,1}=\max\{\|x\|_1:\ \|x\|_2=1\}=\sqrt n, $$ while $\|A\|_{2,2}=1$. So $\|A\|_{2,1}=\sqrt n\|A\|_{2,2}$.

Edit: here is a short proof of the inequalities $(1)$, in case they are not obvious.

You have, for any nonzero $x$. $$ \frac{\|Ax\|_2}{\|x\|_2}\leq\frac{\|Ax\|_1}{\|x\|_2}\leq\|A\|_{2,1}. $$ Now you take supremum (forget about the term on the middle) and you obtain $$ \|A\|_{2,2}\leq\|A\|_{1,1}. $$ Similarly, start with $$ \frac{\|Ax\|_1}{\|x\|_2}\leq\sqrt{n}\,\frac{\|Ax\|_2}{\|x\|_2}\leq\sqrt{n}\,\|A\|_{2,2}. $$ Now forget the middle term and take supremum, to obtain $$ \|A\|_{2,1}\leq\sqrt{n}\,\|A\|_{2,2}. $$

$\endgroup$
10
  • $\begingroup$ what do you mean by characterization? $\endgroup$
    – amj
    Commented Dec 1, 2017 at 23:42
  • 1
    $\begingroup$ The definition is \begin{equation*} \|A\|_{2,1}=\sup\{\|A\mathbf{x}\|_1:\|\mathbf{x}\|_2=1\}. \end{equation*} You also have the characterization $$\|A\|_{2,1}=\max_{u\in\{1,-1\}^n}\|A^Tu\|_2.$$ $\endgroup$ Commented Dec 2, 2017 at 0:08
  • $\begingroup$ Regarding your answer, we have to take supremum over $\|A\mathbf{x}\|$ such that $\|\mathbf{x}\|_2=1$, but there could be alot of $\mathbf{x}$ with unit $\ell_2$ norm and some $\mathbf{x}$ that maximizes $\|A\mathbf{x}\|_{2}$ might not maximize $\|A\mathbf{x}\|_{1}$. $\endgroup$
    – amj
    Commented Dec 3, 2017 at 22:28
  • $\begingroup$ Not sure how you think that affects my answer. $\endgroup$ Commented Dec 3, 2017 at 22:36
  • $\begingroup$ Let $\mathbf{x}'$ and $\mathbf{x}''$ be such that $\|.\|_2=1$ for both of them. Now, let $\sup\|A\mathbf{x}\|_1=\|A\mathbf{x}'\|_1$ and $\sup\|A\mathbf{x}\|_2=\|A\mathbf{x}''\|_2$, then your inequalities might not hold! $\endgroup$
    – amj
    Commented Dec 3, 2017 at 22:42

You must log in to answer this question.

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