Exercise 1.12.5

Reuse the example 1 from I.8, where $A=\left[\begin{array}{cc}\hfill 3\hfill & \hfill 0\hfill \\ \hfill 4\hfill & \hfill 5\hfill \end{array}\right]$. Its closest rank 1 matrix $A_1={\sigma }_1{u}_1{v}_1^T=\sqrt{45}\frac{1}{\sqrt{10}}\left[\begin{array}{c}\hfill 1\hfill \\ \hfill 3\hfill \end{array}\right]\frac{1}{\sqrt{2}}\left[\begin{array}{cc}\hfill 1\hfill & \hfill 1\hfill \end{array}\right]=\left[\begin{array}{cc}\hfill \frac{3}{2}\hfill & \hfill \frac{3}{2}\hfill \\ \hfill \frac{9}{2}\hfill & \hfill \frac{9}{2}\hfill \end{array}\right]$

def find_minimumV(A, U): 
   # We solve (u^Tu)v = u^TA, u is nx1, A: nxn 
   # The result V has shape 1xn 
   rhs = np.matmul(U.transpose(), A) 
   lhs = np.matmul(U.transpose(), U).flatten() 
   res = rhs/lhs 
   res = res.reshape(1, -1) 
   return res 
 
def find_minimumU(A, V): 
   # We solve (vv^T)vu= Av^T, V is 1xn, A: nxn 
   # The result U has shape nx1 
   rhs = np.matmul(A, V.transpose()) 
   lhs = np.matmul(V, V.transpose()).flatten() 
   res = rhs/lhs 
   res = res.reshape(-1, 1) 
   return res 
 
def calc_forbenius_norm(M): 
   m, n = M.shape 
   F = 0 
   for i in np.arange(m): 
       for j in np.arange(n): 
           F += M[i,j]**2 
   return F 
 
def find_minimum(A, max_it = 1000, tol = 1): 
   """Minimize ||A-UV||^2_{F} using alterating minimization method. Where UV has rank 1 
   U has dimension nx1, and V has dimension 1xn 
   """ 
 
   #Initial U 
   U = np.ones((A.shape[0], 1)) 
 
   for it in np.arange(max_it): 
       V=find_minimumV(A, U) 
       U=find_minimumU(A, V) 
       M = A - np.matmul(U, V) 
       norm = calc_forbenius_norm(M) 
       if norm < tol: 
           print(’Stopped␣at␣iteration:␣’, it) 
           break 
   print(’Final␣norm:␣’, norm) 
   approxA = np.matmul(U,V) 
   print(’Final␣approx␣A:␣’, approxA) 
   return norm, approxA

A = np.array([[3,0],[4,5]]) 
find_minimum(A)

Final norm:  5.0
Final approx A:  [[1.5 1.5]
 [4.5 4.5]]

(5.0, array([[1.5, 1.5],
        [4.5, 4.5]]))