To avoid any ambiguity in the definition of the square root of a matrix, it is best to start from norm of a matrix as the induced norm / operator norm coming from the norm of the vector spaces. So in your case it seems that . Then, it holds by the definition of the operator norm

By taking the square and expanding the norm to the -scalar product, one arrives at the Rayleigh quotient of

To lay the question to rest, let me do two things: (i) restate it; (ii) answer it. · By , we mean the Euclidean 2-norm throughout. · Show that the induced 2-norm is given by · The proof is textbook material. For the lazy, here is an informal sketch. · Notice that since without loss of generality, we may rescale vector , hence we may equivalently consider maximizing such that . · Consider, . The matrix is SPD, so it has the eigendecomposition , where is a nonnegative diagonal matrix. Thus, we have . This, implies that because and . · To conclude the proof we now need to show that in fact . But this is trivial, because picking (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 at some point.

The first point is proven as follows.

From the SVD of we can see that eigenvalues of are just squared ones from . At the same time the columns of are the eigenvectors of . So, exploiting orthogonality of eigenvectors

The proof is based on the property of the second matrix norm

.

The same reasoning from the first point says that the eigenvalues of are just the ones of being squared. So

Edit

The inequality becomes after the notion that , because eigenvalues of could be negative.

This example with norm and random data

A = randn(2000,2000);
tic; 
n1 = norm(A) 
toc;

gives

n1 =  89.298
Elapsed time is 2.16777 seconds.

You can try eigs to find only one (the largest) eigenvalue of the symmetric matrix A'*A (or A*A' if it is smaller for A rectangular). It uses a Lanczos iteration method.

tic; 
B = A'*A; % symmetric positive-definite. B = A*A' if it is smaller
n2 = sqrt(eigs(B, 1)), 
toc

it outputs:

n2 =  89.298
Elapsed time is 0.311942 seconds.

If you don't want to use norm or eigs, and your matrix A has good properties (singular values properly separated), you can try to approximate it with a power iteration method:

tic; 
B = A'*A; % or B = A*A' if it is smaller
x = B(:,1); % example of starting point, x will have the largest eigenvector
x = x/norm(x); 
for i = 1:200 
   y = B*x; 
   y = y/norm(y);
   % norm(x - y); % <- residual, you can try to use it to stop iteration
   x = y; 
end; 
n3 = sqrt(mean(B*x./x)) % translate eigenvalue of B to singular value of A
toc

which for the same random matrix (not particularly good properties) gives a ~0.1% accurate solution:

n3 =  89.420
Elapsed time is 0.428032 seconds.

There are three important types of matrix norms. For some matrix $A$

• Induced norm, which measures what is the maximum of $\frac{\|Ax\|}{\|x\|}$ for any $x \neq 0$ (or, equivalently, the maximum of $\|Ax\|$ for $\|x\|=1$).

• Element-wise norm, which is like unwrapping $A$ into a long vector, then calculating its vector norm.

• Schatten norm, which measures the vector norm of the singular values of $A$.

So, to answer your question:

• Frobenius norm = Element-wise 2-norm = Schatten 2-norm

• Induced 2-norm = Schatten $\infty$-norm. This is also called Spectral norm.

So if by "2-norm" you mean element-wise or Schatten norm, then they are identical to Frobenius norm. If you mean induced 2-norm, you get spectral 2-norm, which is $\le$ Frobenius norm. (It should be less than or equal to)

As far as I can tell, if you don't clarify which type you're talking about, induced norm is usually implied. For example, in matlab, norm(A,2) gives you induced 2-norm, which they simply call the 2-norm. So in that sense, the answer to your question is that the (induced) matrix 2-norm is $\le$ than Frobenius norm, and the two are only equal when all of the matrix's eigenvalues have equal magnitude.

As pointed out by Bungo in the comments, all eigenvalues of $A^TA$ are non-negative and real. So there is no need to take absolute values before you compare them.

The 2-norm of a linear transformation $A$ is (assuming finite dimensions) the maximal value of $\|Av\|$ among all unit vectors $v$ in the domain of $A$. We have $$ \|Av\| = \sqrt{v^TA^TAv} $$ The spectral theorem ($A^TA$ is a symmetric matrix) says that the domain of $A^TA$ (which is also the domain of $A$) has an orthonormal basis consisting of eigenvectors of $A^TA$. Thus if we decompose $v$ into this basis, we see that the largest possible value of $v^TA^TAv$ is exactly the largest eigenvalue of $A^TA$.