0
$\begingroup$

Let $M$ be a matrix. Consider the singular value decomposition $$ M = U \Sigma V^*. $$ I've often been told that you can get the best low-rank approximation of $M$ using the SVD. Namely, you split up your SVD as $$ M = \begin{pmatrix} U_1 & U_2 \end{pmatrix} \begin{pmatrix} \Sigma_1 & 0 \\ 0 & \Sigma_2 \\ \end{pmatrix}\begin{pmatrix} V_1 & V_2\end{pmatrix} $$ and consider $M' = U_1 \Sigma_1 V_1^{*}$.

I've tried to see this in a simple example, but I cannot get it to work. I look at the matrix $$ M = \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix} $$ Then I end up with

U =
   -0.3251    0.7071    0.6280
   -0.8881   -0.0000   -0.4597
   -0.3251   -0.7071    0.6280
S =
    1.9319         0         0
         0    1.0000         0
         0         0    0.5176
V =
   -0.6280    0.7071    0.3251
   -0.4597    0.0000   -0.8881
   -0.6280   -0.7071    0.3251

If I then compute the rank-2 approximation of $M$ using the method outlined above, I find

M' =
    0.0693   -0.4440   -0.8321
    1.0774   -1.2131   -0.5577
    0.7194   -0.4440    0.4238

Yet, it's trivial to come up with better rank-2 approximations! Just consider the matrix $$ M' = \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & 1 \\ 0 & 0 & 0 \end{pmatrix} $$ which obviously has rank 2 and whose distance from $M$ is clearly smaller.

Where am I making a mistake?

$\endgroup$
1
  • 2
    $\begingroup$ To check, note that you should have $\|M-M'\| = \sigma_3 = 0.5176$ for the induced $2$-norm (and in this case the Frobenius norm since there is just one singular value left). m = [ 1 0 0 ; 1 1 1 ; 0 0 1] ; [u, s, v] = svd(m) ; d = s ; d(3,3) = 0 ; mp = u*d*v' ; norm(m-mp) $\endgroup$
    – copper.hat
    Jul 18, 2023 at 15:10

1 Answer 1

1
$\begingroup$

Check your calculations again. Setting the last singular value to zero I get

U,S,V = np.linalg.svd(A)
U,S,V
#>>> (array([[-3.25057584e-01,  7.07106781e-01,  6.27963030e-01],
#>>>         [-8.88073834e-01, -8.73009598e-17, -4.59700843e-01],
#>>>         [-3.25057584e-01, -7.07106781e-01,  6.27963030e-01]]),
#>>>  array([1.93185165, 1.        , 0.51763809]),
#>>>  array([[-6.27963030e-01, -4.59700843e-01, -6.27963030e-01],
#>>>         [ 7.07106781e-01,  2.11898069e-16, -7.07106781e-01],
#>>>         [ 3.25057584e-01, -8.88073834e-01,  3.25057584e-01]]))

[email protected](S)@V
#>>> array([[ 1.00000000e+00, -1.60602200e-16, -3.55621971e-16],
#>>>        [ 1.00000000e+00,  1.00000000e+00,  1.00000000e+00],
#>>>        [ 1.24555880e-16, -1.85454802e-16,  1.00000000e+00]])

S[2]=0

[email protected](S)@V
#>>> array([[ 0.89433757,  0.28867513, -0.10566243],
#>>>        [ 1.07735027,  0.78867513,  1.07735027],
#>>>        [-0.10566243,  0.28867513,  0.89433757]])

This last is different from your result, and is indeed a sensible approximation of the original matrix.


In mathematical theory the format of the SVD is always $M=U\Sigma V^T=\sum \sigma_iu_iv_i^T$, so that the left and right singular vectors are both the columns of $U$ and $V$, $Mv_i=\sigma_i u_i$. In interfaces for computer implementations one has to check what convention is used, transposition is a non-trivial operation, so often left out in the last factor.

$\endgroup$
2
  • $\begingroup$ Thanks. The main mistake seems to be that I thought $M = U * \Sigma * V^t$ instead of $M = U * \Sigma * V$. Could it be that there are different conventions regarding this? $\endgroup$
    – guest
    Jul 19, 2023 at 12:06
  • 1
    $\begingroup$ If you do mathematical theory, then indeed it is always $M=U\Sigma V^T=\sum \sigma_iu_iv_i^T$, so that the left and right singular vectors are both the columns of $U$ and $V$, $Mv_i=\sigma_i u_i$. In interfaces for computer implementations you will have to check what is used, transposition is a non-trivial operation, so often left out in the last factor. $\endgroup$ Jul 19, 2023 at 12:42

You must log in to answer this question.

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