Exercise 5.1 (Clustering Points in a Plane). Describe how Algorithm 5.1 can also be applied to a set of points in the plane $\left{x_j \in \mathbb{R}^2\right}_{j=1}^N$ that are distributed around a collection of cluster centers $\left{\boldsymbol{\mu}i \in \mathbb{R}^2\right}{i=1}^n$ by interpreting the data points as complex numbers: ${z \doteq x+y \sqrt{-1} \in \mathbb{C}}$. In particular, discuss what happens to the coefficients and roots of the fitting polynomial $p_n(z)$.

Exercise 5.3 (Level Sets and Normal Vectors). Let $f(x): \mathbb{R}^D \rightarrow \mathbb{R}$ be a smooth function. For a constant $c \in \mathbb{R}$, the set $S_c \doteq\left{x \in \mathbb{R}^D \mid f(x)=c\right}$ is called a level set of the function $f ; S_c$ is in general a $(D-1)$-dimensional submanifold. Show that if $|\nabla f(x)|$ is nonzero at a point $x_0 \in S_c$, then the gradient $\nabla f\left(x_0\right) \in \mathbb{R}^D$ at $x_0$ is orthogonal to all tangent vectors of the level set $S_c$.

Exercise 5.7 (Two Subspaces in General Position). Consider two linear subspaces of dimension $d_1$ and $d_2$ respectively in $\mathbb{R}^D$. We say that they are in general position if an arbitrarily small perturbation of the position of the subspaces does not change the dimension of their intersection. Show that two subspaces are in general position if and only if
$$
\operatorname{dim}\left(S_1 \cap S_2\right)=\min \left{d_1+d_2-D ; 0\right} .
$$

Exercise 5.8. Implement the basic algebraic subspace clustering algorithm, Algorithm 5.4 , and test the algorithm for different subspace arrangements with different levels of noise.

Exercise 5.12 (Robust Estimation of Fitting Polynomials). We know that samples from an arrangement of $n$ subspaces, their Veronese lifting, all lie on a single subspace $\operatorname{span}\left(V_n(D)\right)$. The coefficients of the fitting polynomials are simply the null space of $\boldsymbol{V}_n(D)$. If there is noise, the lifted samples approximately span a subspace, and the coefficients of the fitting polynomials are eigenvectors associated with the small eigenvalues of $\boldsymbol{V}_n(D)^{\top} \boldsymbol{V}_n(D)$. However, if there are outliers, the lifted samples together no longer span a subspace. Notice that this is the same situation that robust statistical techniques such as multivariate trimming (MVT) are designed to deal with. See Appendix B.5 for more details. In this exercise, show how to combine MVT with ASC so that the resulting algorithm will be robust to outliers. Implement your scheme and find out the highest percentage of outliers that the algorithm can handle (for various subspace arrangements).