Timeline for On the induced matrix norm $\| \cdot \|_{2,\infty}$
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 4, 2014 at 8:02 | vote | accept | f10w | ||
| Oct 4, 2014 at 8:01 | comment | added | f10w | @NathanielJohnston: In that paper, $\| A \|_{p,q}$ denotes $\sup_{x\in\mathbb{R}^n\setminus \{0\}} \frac{\|Ax\|_q}{\|x\|_p}$, which is like the other, so it is probably mistaken. Thanks and +1. Suvrit: hmm, it seems that there is no conventional notation. I have seen some authors used $\|\cdot\|_{pq}$ or $\|\cdot\|_{p\to q}$ to denote the induced norm of the linear operator mapping $l_p\to l_q$, but haven't seen any thing like $\|\cdot\|_{qp}$ :P (In addition, some use $\|\cdot\|_{pq}$ or $|\cdot |_{pq}$ for the vector norm). | |
| Oct 4, 2014 at 0:53 | comment | added | Nathaniel Johnston | Either Paper 1 is mistaken/has a typo, or there's a notational mix-up in it that I'm missing. $\|A\|_{\infty,2}$ can't be the largest 2-norm of any row. For a counterexample, let $A$ be the matrix with first row all $1$ and elsewhere all $0$... multiplying $A$ by the all-ones vector shows that $\|A\|_{\infty,2} \geq n$, but the largest $2$-norm of a row is just $\sqrt{n}$. | |
| Oct 3, 2014 at 21:08 | comment | added | Suvrit | @Nesbit: I haven't looked into the paper you cited, but can mention that people often switch the labels on the norms (often $\|A\|_{p,q}$ is not even the induced norm, just a vector norm) | |
| Oct 3, 2014 at 19:48 | comment | added | f10w | But now I have another problem. The paper you cited (Paper 2) contradicts the paper that I cited (Paper 1). The equation (2h) in Paper 1 says that $\|A\|_{\infty,2}$ is the largest 2-norm of any row, while in Paper 2 this should be the value of $\|A\|_{2,\infty}$. | |
| Oct 3, 2014 at 19:48 | comment | added | f10w | Thanks, Suvrit and @NathanielJohnston. I had figured it out too. The adjoint operator of $A$, mapping $(\mathbb R^m , \| \cdot \|_p^*) = (\mathbb R^m , \| \cdot \|_{p/(p-1)})$ to $(\mathbb R^n, \| \cdot \|_q^*) = (\mathbb R^n, \| \cdot \|_{p/(p-1)})$ is the transpose matrix $A^T$. Since $\|A\|_{p,q} = \|A^T\|_{q/(q-1),p/(p-1)}$, we have $\|A\|_{2,\infty}=\|A^T\|_{1,2}$ and so we can apply the result of the case $1\to 2$. (next below) | |
| Oct 3, 2014 at 19:00 | history | edited | Suvrit | CC BY-SA 3.0 |
fixed citation to proof of 2 infty
|
| Oct 3, 2014 at 18:09 | comment | added | Suvrit | @NathanielJohnston: ah thanks! I just guessed the answer given what holds for the induced $\infty$-norm :-) | |
| Oct 3, 2014 at 17:34 | comment | added | Nathaniel Johnston | In fact, the Barak et. al. paper that you linked explicitly says that the $2\rightarrow\infty$ norm is just the largest 2-norm of any row of the matrix (on page 3). | |
| Oct 3, 2014 at 17:23 | history | answered | Suvrit | CC BY-SA 3.0 |