2
$\begingroup$

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

Improve this question
$\endgroup$
6
  • $\begingroup$ matlab can do this for you; the restriction to SPD is not necessary. $\endgroup$
    – Suvrit
    Commented Jan 25, 2011 at 16:38
  • $\begingroup$ But how does matlab do it? $\endgroup$
    – Zenon
    Commented Jan 25, 2011 at 16:40
  • $\begingroup$ Well, this is not a forum for matlab questions (see mathworks.com/matlabcentral/answers) but did you try 'help norm' in matlab? $\endgroup$
    – Dirk
    Commented Jan 25, 2011 at 20:18
  • 1
    $\begingroup$ 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? $\endgroup$
    – Yemon Choi
    Commented Jan 25, 2011 at 20:40
  • 2
    $\begingroup$ 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 $\endgroup$
    – Suvrit
    Commented Jan 25, 2011 at 20:54

3 Answers 3

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
0
1
$\begingroup$

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).

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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$ $\endgroup$
    – Suvrit
    Commented Jan 25, 2011 at 21:50
  • $\begingroup$ 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$ $\endgroup$
    – Suvrit
    Commented Jan 25, 2011 at 21:53
  • $\begingroup$ Thanks Suvrit, finally this is what I wanted. This is the first time I use the forum, should I delete this question and ask the more precise one? Or could you create an answer and I could give you the points? $\endgroup$
    – Zenon
    Commented Jan 25, 2011 at 22:32
  • $\begingroup$ I think Zenon, you will benefit from also visiting the sister site: math.stackexchange.com Let me add my comments as an answer so that your question gets an "answered" status. Also, it is good to leave all these comments; might prove useful to someone else searching google for proofs. However, I did want to stress that since your question requested textbook knowledge, I pointed you to matlab and numerics book. $\endgroup$
    – Suvrit
    Commented Jan 25, 2011 at 22:48
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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)? $\endgroup$
    – Zenon
    Commented Jan 25, 2011 at 20:29
  • $\begingroup$ 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). $\endgroup$
    – user11046
    Commented Jan 25, 2011 at 21:14

You must log in to answer this question.

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