# SVD-based low-rank approximation doesn't work

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?

• 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) Jul 18, 2023 at 15:10

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.

• 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? Jul 19, 2023 at 12:06
• 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. Jul 19, 2023 at 12:42