2
$\begingroup$

In Latent Semantic Analysis one uses the SVD to perform a dimensional reduction of the term-document matrix, via the Eckart-Young theorem.

Now, the rank $k$ approximation obtained by E-Y is proven to be the best approximation in the Euclidean norm as well as in the Frobenius norm.

The whole literature I'm reading about LSA says something like:

"For the purposes of LSA, we consider the best approximation in the Frobenius norm, provided by Eckart-Young."

But nobody says why. I mean, why not in the Euclidean norm?

Thanks.

$\endgroup$
  • $\begingroup$ $\min_{rank(Y)=k}\|X-Y\|_F.$ $X=U\Sigma V^*,$ $\|X-Y\|_F=\|\Sigma-U^*YV\|_F$ since the factors $U,$ $V$ do not change F-norm. $\min_{rank(Z)=k}\|\Sigma-Z\|_F$ is attained only when $Z$ is diagonal and takes the largest $\sigma$'s ($\Sigma=diag(\sigma_i)$). $\endgroup$ – Hui Zhang Apr 22 '14 at 7:47
1
$\begingroup$

There is no such thing as the Euclidean norm of a matrix. It is only defined for vectors in ${\mathbb R}^n$. You need to decide whether you want to consider a matrix as an element of the vector space ${\mathbb R}^{n \times m}$, in which case the Frobenius norm is simply the easiest one to compute. Alternatively, you could consider a matrix as an operator ${\mathbb R}^m \rightarrow {\mathbb R}^n$ in which case the $l_2$ norm is very awkward to compute (it is the largest singular value) and one could go with the $l_1$ or $l_\infty$ norms which are the maximal sums of absolute values of matrix elements over rows or columns. In the end, the Frobenius norm is typically just the simplest norm to compute if you don't think of the matrix as an operator.

$\endgroup$
  • 1
    $\begingroup$ I disagree with your statement "There is no such thing as the Euclidean norm of a matrix." One can induce a matrix norm from a vector norm, leading to the terminology, "(induced) Euclidean matrix norm". $\endgroup$ – Geoff Oxberry Apr 21 '14 at 6:31
  • $\begingroup$ Correct -- you can induce the operator norm that matches the Euclidean vector norm. But it's not called the "Euclidean norm" of a matrix -- it's called the spectral or $l_2$ norm of the matrix, and it's pretty complicated to compute in practice. The point I wanted to make is that if you think that the Euclidean norm of a matrix would just be the square root of the sum of squares of entries, then you are mistaken: That is the Frobenius norm, and if we want to consider the matrix norm that corresponds to the Euclidean vector norm, then that is something completely different. $\endgroup$ – Wolfgang Bangerth Apr 21 '14 at 19:58
  • $\begingroup$ But, as you correctly pointed out, the spectral (sometimes referred as euclidean in literature) norm is automatically given by the SVD. I cannot see any complication in its computation: you have to compute SVD anyway, for LSA purposes... $\endgroup$ – MadHatter Apr 22 '14 at 12:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.