Editing Operator norm (section)

== Table of common operator norms ==

By choosing different norms for the codomain, used in computing <math>\|Av\|</math>, and the domain, used in computing <math>\|v\|</math>, we obtain different values for the operator norm. Some common operator norms are easy to calculate, and others are [[NP-hard]]. 
Except for the NP-hard norms, all these norms can be calculated in <math>N^2</math> operations (for an <math>N \times N</math> matrix), with the exception of the <math>\ell_2 - \ell_2</math> norm (which requires <math>N^3</math> operations for the exact answer, or fewer if you approximate it with the [[Power iteration|power method]] or [[Lanczos algorithm|Lanczos iterations]]).

{| class="wikitable" style="text-align: center; width: 500px; height: 200px;"
|+ Computability of Operator Norms<ref>section 4.3.1, [[Joel Tropp]]'s PhD thesis, [http://users.cms.caltech.edu/~jtropp/papers/Tro04-Topics-Sparse.pdf]</ref>
|-
! scope="col" colspan = "2" rowspan = "2" |
! scope="col" colspan = "3" | Co-domain
|-
! scope="col" | <math>\ell_1</math>
! scope="col" | <math>\ell_2</math>
! scope="col" | <math>\ell_\infty</math>
|-
! scope = "row" rowspan="3" | Domain
! scope="row" | <math>\ell_1</math>
| Maximum <math>\ell_1</math> norm of a column || Maximum <math>\ell_2</math> norm of a column || Maximum <math>\ell_{\infty}</math> norm of a column
|-
! scope="row" | <math>\ell_2</math>
| NP-hard || Maximum singular value || Maximum <math>\ell_2</math> norm of a row
|-
! scope="row" | <math>\ell_\infty</math>
| NP-hard || NP-hard || Maximum <math>\ell_1</math> norm of a row
|}

The norm of the [[Conjugate transpose|adjoint]] or transpose can be computed as follows. 
We have that for any <math>p, q,</math> then <math>\|A\|_{p\rightarrow q} = \|A^*\|_{q'\rightarrow p'}</math> where <math>p', q'</math> are [[Hölder's inequality|Hölder conjugate]] to <math>p, q,</math> that is, <math>1/p + 1/p' = 1</math> and <math>1/q + 1/q' = 1.</math>