## 6 Modified Unitary R-D Root MUSIC
Since \(d=1\), ideally the implemented solution needs to find only one single root closest to the unit circle and inside it. However, due to AWGN, that root does not need to be inside the unit circle, in mathematical terms,  
\[ \begin{array}{ll}\arg\min&(|\lambda_{i}|-1)^{2}\\ \text{s.t.}&p(\lambda_{i})=0\\ &\lambda_{i}\in\{\lambda_{1},\lambda_{2},\ldots,\lambda_{4M-4}\}.\end{array}  \tag{51}\]  
```
Input: The polynomial \(p(z)\) in which \(p(z)=p_{x}(z)\) or \(p(z)=p_{y}(z)\). Output: The roots of \(p(z)\) and their conjugate, \(\lambda_{1},\lambda_{2},\ldots,\lambda_{4M-4}\). 1 Define the companion matrix \(\mathbf{P}\in\mathbb{C}^{(2M-2)\times(2M-2)}\) of \(p(z)\) as described in Equation (47). 2 Solve the complex EVD via equivalent real formulation as explained previously. Therefore, let's define a real matrix from \(\mathbf{P}\), that is, \[\mathbf{P}_{R}\triangleq \begin{bmatrix}\operatorname{Re}(\mathbf{P})&- \operatorname{Im}(\mathbf{P})\\ \operatorname{Im}(\mathbf{P})&\operatorname{Re}(\mathbf{P})\end{bmatrix} \in \mathbb{R}^{(4M-4)\times(4M-4)}.\]
3 Apply the Balancing technique in \(\mathbf{P}_{R}\) to reduce the rounding errors sensitivity of eigenvalues. 4 Reduce the balanced \(\mathbf{P}_{R}\) to Hessenberg form to speed up the execution of Shifted QR Algorithm. 5 Apply the Shifted QR Algorithm to the Hessenberg form of the balanced \(\mathbf{P}_{R}\) to get its eigenvalues, \(\lambda_{1},\lambda_{2},\ldots,\lambda_{4M-4}\). ```  
**Algorithm 3**Polynomial Finding Roots Method  
The implemented solution applies Algorithm 4 to solve the optimization problem (51). However, instead of applying the complex absolute operator (\(|\cdot|\)), the algorithm uses its squared value (\(|\cdot|^{2}\)), to avoid calling the square root method in every iteration of line three. The square root method usually is an iterative algorithm and it needs to converge to a point. However, modern processors have a built-in circuit for square roots. Despite that, by avoiding that operation the execution time of Algorithm 4 is slightly decreased. In lines 2-6, observe that the algorithm finds the eigenvalue (\(\lambda_{solution}\)), which is the closest to the unit circle. However, its conjugate also is the closest to the unit circle since \((|\overline{\lambda}_{solution}|^{2}-1)^{2}=(|\lambda_{solution}|^{2}-1)^{2}\). Thus, in lines 7-9, the algorithm finds which one is the root of the polynomial \(p(z)\). That is,if the eigenvalue \(\lambda_{solution}\) is also a root, then \(|p(\lambda_{solution})|^{2}\ll 1\) which means \(|p(\lambda_{solution})|^{2}<|p(\overline{\lambda}_{solution})|^{2}\), otherwise, its conjugate is the root. In that way, the algorithm does not need to check if the eigenvalue is the polynomial root in every iteration (lines 2-6) which saves execution time. ```
Input: The eigenvalues of \(\textbf{P},\lambda_{1},\lambda_{2},\cdots,\lambda_{4M-2}\). Output:\(\lambda_{solution}\) which is the root of \(p(z)\) that is closest to the unit circle. 1 Define \(\lambda_{solution}\leftarrow\lambda_{1}\)for\(i=2,\cdots,4M-4\)do
2 if\((|\lambda_{i}|^{2}-1)^{2}<(|\lambda_{solution}|^{2}-1)^{2}\)then
3\(\lambda_{solution}\leftarrow\lambda_{i}\)
4 end if
5
6 end for
7 if\(|p(\overline{\lambda}_{solution})|^{2}<|p(\lambda_{solution})|^{2}\)then
8\(\lambda_{solution}\leftarrow\overline{\lambda}_{solution}\)
9 end if
```  
**Algorithm 4**Find the eigenvalue which is the root closest to the unit circle