Algorithm $6\mathrm{.}1$

procedure COMPACT$\_$SVD $(A)$

$,$Vlarreig$(A^{H}A)$

$larr\sqrt[\phantom{2}]{}$

$$ Calculate the eigenvalues and eigenvectors of $A^{H}A.$

$$ Calculate the singular values of $A.$

$larrsort(),$ Sort the singular values from greatest to least.

Vlarrsort$(V),$ Sort the eigenvectors the same way as in the previous step.

rlarrcount$(0),$ Count the number of nonzero singular values $($the rank of $A).$

${}_1$larr${}_{\text{:}r},$ Keep only the positive singular values.

$V_{1}larr{V}_{\text{:},\text{:}r},$ Keep only the corresponding eigenvectors.

$U_1$larrA$\frac{V_1}{{}_1},$ Construct $U$ with array broadcasting.

return $U_1,{}_1,V_1^H$

Problem $1.$ Write a function that accepts a matrix A and a small error tolerance tol. Use

Algorithm $6\mathrm{.}1$ to compute the compact SVD of $A.$ In step $6,$ compute $r$ by counting the number

of singular values that are greater than tol.

Consider the following tips for implementing the algorithm.

The Hermitian $A^H$ can be computed with A$.$ conj$().$ T$.$

In step $4,$ the way that $$ is sorted needs to be stored so that the columns of $V$ can be

sorted the same way. Consider using np$.$argsort$()$ and fancy indexing to do this, but

remember that by default it sorts from least to greatest $($not greatest to least$).$

Step $9$ can be done by looping over the columns of $V,$ but it can be done more easily and

efficiently with array broadcasting.

Test your function by calculating the compact SVD for random matrices. Verify that $U$

and $V$ are orthonormal, that $U{V}^H=A,$ and that the number of nonzero singular values is

the rank of $A.$ You may also want to compre your results to SciPy's SVD algorithm.