# Smart Ocean: A New Fast Deconvolved Beamforming Algorithm for Multibeam Sonar
## 2 Beamforming and Deconvolution
### Deconvolved Beamforming
#### 2.2.4 Accelerated R-L Algorithm and Fast Accelerated R-L Algorithm  
[PERSON] and [PERSON] pointed out the problem that the speed of the iteration of the R-L algorithm is too slow in Reference [15], and they proposed a method of vector extrapolation to accelerate the speed of iteration. The technique calculates the direction as the difference between the current iteration and the previous iteration. If \(\hat{S}_{k}\) is the iterated point, \(S_{k}^{\prime}\) is the predicted point, \(\hat{S}_{k}-\hat{S}_{k-1}\) is the direction vector, and \(\alpha_{k}\) is the acceleration parameter, then  
\[S_{k}^{\prime}=\hat{S}_{k}+\alpha_{k}(\hat{S}_{k}-\hat{S}_{k-1}) \tag{8}\]  
where  
\[\hat{S}_{k}=\hat{S}_{k-1}(\textbf{F}_{p}*\frac{\textbf{F}}{F_{k-1}^{\prime}}) \tag{9}\]  
\[\textbf{F}_{k}^{\prime}=\textbf{F}_{p}\otimes S_{k}^{\prime} \tag{10}\]  
\[\alpha_{k}=\frac{g_{k-1}^{T}\cdot\hat{S}_{k-2}}{g_{k-2}^{T}\cdot\hat{S}_{k-2}} \tag{11}\]  
\[\textbf{g}_{k}=\hat{S}_{k+1}-\textbf{S}_{k}^{\prime} \tag{12}\]  
The detailed derivation of \(\alpha_{k}\) is given in the appendix of Reference [15]. The amount of calculation of a single iteration is greater than Algorithm 1 and Algorithm 2, but the total iteration, which needs to reach the same result, becomes less. A description of its iterative algorithm is given as Algorithm 3, from which we can estimate, per iteration, that the multiplication number is \(2N^{2}+4N\), the division number is \(N+1\), the addition number is \(2N^{2}+N-2\), and the subtraction number is \(2N\). For a single iteration of Algorithm 3, we can also utilize the FFT technique to reduce the number of calculations of the convolution and correlation. Finally, we obtain the optimum algorithm (hereinafter referred to as Algorithm 4) that requires the least amount of calculation, from which we can estimate, per iteration, that the multiplication number is \(8N\log_{2}N+12N\), the division number is \(2N+1\), the addition number is \(2N^{2}+N-2\), and the subtraction number is \(2N\). It is worth noting that Algorithm 3 and Algorithm 4 start to iterate after k is greater than 2. When \(k\) equals 1 or 2, it should still use Algorithm 1 and Algorithm 2, respectively, because \(\alpha_{k}\) cannot be calculated when \(k\) equals 1 or 2. The multiplication times of the four algorithms of a single iteration is shown in Table 1. It is proved in the next section that the total amount of calculation that is needed to reach the same result satisfies Algorithm 1 > Algorithm 2 > Algorithm 3 > Algorithm 4 when the beam number issmall, and Algorithm 1 \(>\) Algorithm 3 \(>\) Algorithm 2 \(>\) Algorithm when the beam number is large. Table 2 summarizes the differences between the four algorithms. ```
Initialization: \(\hat{S}_{0}=F\) (or \(\hat{S}_{0}=[1,1,\ldots,1]_{1\times N}^{T}\)), \(N\) is the number of elements of \(\hat{S}_{0}\) or the number of beams. for \(k=3\),\(4\),... \(\hat{S}_{k}^{\prime}=\hat{S}_{k}+\alpha_{k}(\hat{S}_{k}-\hat{S}_{k-1})\); Predict \(\mathcal{S}\) at the iteration time \(k\) \(F_{k}^{\prime}=F_{p}\otimes S_{k}^{\prime}\); Predict \(\mathcal{F}\) at the iteration time \(k\) \(\hat{S}_{k+1}=\hat{S}_{k}(F_{p}\cdot\frac{F}{F_{k}^{\prime}})\); Estimate \(\mathcal{S}\) at the iteration time \(k+1\) \(g_{k}=\hat{S}_{k+1}-S_{k}^{\prime}\); Calculate the gradient of \(\mathcal{S}\) at the iteration time \(k\) \(\alpha_{k+1}=\frac{g_{k}^{T}\cdot\hat{S}_{k-1}}{\hat{S}_{k-1}^{T}\cdot\hat{S}_ {k-1}}\); Calculate the acceleration factor at the iteration time \(k+1\) }
```  
**Algorithm 3** Accelerated R-L algorithm. ```
Initialization: \(\hat{S}_{0}=F\) (or \(\hat{S}_{0}=[1,1,\ldots,1]_{1\times N}^{T}\)).\(N\) is the number of elements of \(\hat{S}_{0}\) or the number of beams. \(\textbf{H}_{p}=fft(\textbf{F}_{p})\); Calculate the fast Fourier transform of \(F_{p},fft(\ldots)\) denotes the fast Fourier transform operation.