# How to compute the induced $||\cdot||_{2}$ matrix norm of an SPD matrix

Hi, I know they are related questions on the board but mine is more specific. Although the answer for any non-singular matrix would be also interesting. Thanks!

UPDATE: I am sorry I though this was clear, but as I know it the $||\cdot||_{2}$ norm is defined as follow: Let be $A\in \mathbb{R}^{m\times n};\;||A||_{2} = \displaystyle{max_{x \in \mathbb{R}^n} \frac{||Ax||_{2}}{||x||_{2}}}$

-
matlab can do this for you; the restriction to SPD is not necessary. –  Suvrit Jan 25 '11 at 16:38
But how does matlab do it? –  Zenon Jan 25 '11 at 16:40
Well, this is not a forum for matlab questions (see mathworks.com/matlabcentral/answers) but did you try 'help norm' in matlab? –  Dirk Jan 25 '11 at 20:18
It seems that what you are calling the induced 2-norm is often called the operator norm of the matrix (as a linear operator from one Euclidean space to another). Does that sound right? –  Captain Oates Jan 25 '11 at 20:40
So after your update to the question, SPD is no longer important? All you want is to compute the largest singular value. Depending on an actual matrix, different algorithms might be preferable (see some textbooks on Matrix computations and Numerical linear algebra); If the matrix $A$ is very large, then you might prefer ARPACK, etc.; I think the question needs more work, and in its current form might find more takers at math.stackexchange.com –  Suvrit Jan 25 '11 at 20:54
show 1 more comment

To lay the question to rest, let me do two things: (i) restate it; (ii) answer it.

By $\|x\|$, we mean the Euclidean 2-norm throughout.

Show that the induced 2-norm $$\max_{\|x\|\not= 0} \frac{\|Ax\|}{\|x\|}$$ is given by $\sqrt{\lambda_{\max}(A^TA)}$

The proof is textbook material. For the lazy, here is an informal sketch.

Notice that since without loss of generality, we may rescale vector $x$, hence we may equivalently consider maximizing $\|Ax\|$ such that $\|x\|=1$.

Consider, $\|Ax\|^2 = x^TA^TAx$. The matrix $A^TA$ is SPD, so it has the eigendecomposition $V\Lambda V^T$, where $\Lambda$ is a nonnegative diagonal matrix. Thus, we have $x^TA^TAx = x^TV\Lambda V^Tx = y^T\Lambda y = \sum_i \lambda_i y_i^2$. This, implies that $\|Ax\|^2 \le \lambda_{\max}y^Ty = \lambda_{\max}x^TV^TVx=\lambda_{\max}$ because $V^TV=I$ and $x^Tx=1$.

To conclude the proof we now need to show that in fact $\|Ax\|^2 = \lambda_{\max}$. But this is trivial, because picking $x=v_{\max}$ (eigenvector corr to max eigenvalue), we attain this equality.

PS: Other proofs based on Lagrange multipliers etc. can also be given, but ultimately one needs to invoke something like $A^TAx=\lambda x$ at some point.

-

For square matrices, isn't the induced 2-norm equivalent to the largest singular value of the matrix? Knowing this, you would use the optimal algorithm to find that value given knowledge that your matrix is SPD.

-
By definition: let be $A\in \mathbb{R}^{m\times n};\;||A||_{2} = max_{x \in \mathbb{R}^n} \frac{||Ax||_{2}}{||x||_{2}}$. So I understand how an $\textit{optimal algorithm}$ might be useful, but could you elaborate on it? (provide a link or state the algorithm)? –  Zenon Jan 25 '11 at 20:29
Oh, I just meant that there might be an algorithm designed specifically for SPD matrices that will let you calculate the largest eigenvalue. If you just want a solution in general, then you can use something like the Power Method, which you can probably find in both of the books that Suvrit cited, or on wikipedia (en.wikipedia.org/wiki/Power_iteration). –  user11046 Jan 25 '11 at 21:14
I fill bad about this but I found my answer thanks to the comment of Yemon Choi! After looking for operator norm on Wikipedia I got that: $||A||_{2} = \sqrt{\lambda_{max}(A^*A)}$ where $A^*$ is the conjugate transpose of $A$ (but since in my question I asked only for the values of $A\in\mathbb{R}$ it's only the tranpose) and $\lambda_{max}(B)$ is the largest eigenvalue of the matrix $B$. If someone can give me a proof for the real case, I will vote for his answer as the correct one (if I am allowed to do that in the rules since I'm slightly changing the question).
the proof that you want, can be found in the cited textbooks. Here is a short version of it (not writing as an answer, because this is really a math.SE question). Let us look at the matrix $A$. We want $\max \|Ax\| / \|x\|$, where $x \neq 0$. Since $\|\alpha x\| = |\alpha| \|x\|$, wlog, take $\|x\|=1$. Now, consider $\|Ax\|^2=x^TA^TAx$. We wish to maximize this quadratic form over $x^Tx=1$. Use eigendecomposition of $A^TA=V\Lambda V^T$; let $y=V^Tx$. Then, $x^TA^TAx=\sum_i \lambda_i y_i^2 \le \lambda_{\max}y^Ty = \lambda_{\max}$, since $y^Ty=x^TV^TVx=x^Tx=1$ –  Suvrit Jan 25 '11 at 21:50
to show that $\lambda_{\max}$ is the norm, we need to then only show that there is a vector $x$ for which actually the above inequality holds with equality. Based on the above, just pick $x=v_1$, the first eigenvector, and you have equality, concluding the proof. (note that proof also used $\lambda_i \ge 0$ –  Suvrit Jan 25 '11 at 21:53