# An ADS-Based Sparse Optimization Method for Sonar Imaging Sensor Arrays
## 2 Almost Difference Set and Sparse Optimization of Mills Cross Array  
### Almost Difference Sets  
Let \(D\) be a \(K\) subset of an Abelian group \(G\) of order \(N\), and the differences between any two nonzero elements in \(D\) will form a set \(F\). If \(t\) nonzero elements in \(G\) appear in each of \(\Lambda\) times, and the remaining (\(N\)-\(t\)-1) nonzero elements appear (\(\Lambda+1\)) times each, then \(D\) is said to be (\(N\), \(K\), \(\Lambda\), \(t\))-ADS [14; 15].  
If the set \(D\) is (\(N\), \(K\), \(\Lambda\), \(t\))-ADS, and there is a binary sequence of length \(N\) that satisfies \(D\), where the \(n\)-\(th\) element is represented as:  
\[a_{n}=\left\{\begin{array}{ll}1,\ n\in D\\ 0,\ \mathrm{other}\end{array}\right. \tag{1}\]  
Then, the characteristic binary sequence (that corresponding to \(D\)) \(S=\{s_{n},\ n\in Z\}\) is expressed as:  
\[s_{n}=\left\{\begin{array}{ll}1,\ \mathrm{mod}_{N}(n)\in D\\ 0,\ \mathrm{other}\end{array}\right. \tag{2}\]  
where, \(\mathrm{mod}_{N}(n)\) means taking the modulus of \(N\), and there exists a periodic autocorrelation function \(C_{s}(z)\) about \(S_{n}\):  
\[C_{s}(z)=\sum_{n=0}^{N-1}S_{n}S_{n+z},\ \mathrm{z}\in\mathbb{Z} \tag{3}\]  
The autocorrelation function is characterized as \"three-valued\":  
\[C_{s}(z)=\left\{\begin{array}{ll}K,&\mathrm{z}=0\\ \Lambda+1,&z\in L\\ \Lambda,&\mathrm{other}\end{array}\right.,\ K\geq\Lambda+1 \tag{4}\]  
In the period \(z\in[0,N-1]\), \(L\) being a set of \(N-1-t\) elements (i.e., \(L=\{l_{p}\in\mathbb{Z};p=1,...,N-1-t\}\)). For illustrative purposes, let us consider the examples of ADSs reported in Table 1 of the literature [16] together with the corresponding binary sequences and autocorrelation functions. In the interest of saving space, however, only two ADS sequences \(D_{1}\) and \(D_{2}\) are given. They are [5, 6, 9] and [0, 1, 3, 13, 16, 17], respectively. The autocorrelation functions \(C_{s}^{\mathrm{ADS}}(z)\) of \(D1\) and \(D2\) are shown in Figure 1.  
\begin{table}
\begin{tabular}{c c c c c} \hline \hline \(K\) & **Sparse Ratio** & \(E\{\mathbf{\Phi}_{N}^{\text{min}}\}\) & \(PSL_{\text{min}}^{\text{opt}}\) (dB) & \(PSL_{\text{max}}^{\text{opt}}\) (dB) \\ \hline
20 & 50\% & 2.65 & \(-13.5\) & \(-7.57\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: All Peak Side Lobe Levels (\(PSLLs\)) for the arrays thinned by ADS.  
Figure 1: Autocorrelation function \(C_{s}^{\mathrm{ADS}}(z)\) of \(D\).  
Through the comparison and analysis, we can see that the autocorrelation function \(C_{s}^{\text{ADS}}(z)\) of a (\(N\), \(K\), \(\Lambda\), \(t\))-ADS is close to that of the (if any) corresponding (\(N\), \(K\), \(\Lambda\))-CDS.  
\[C_{s}^{\text{CDS}}(z)=\left\{\begin{array}{cc}K&z=0\\ \Lambda&\text{other}\end{array}\right. \tag{5}\]  
In addition, the ADSs share several other properties with the CDSs; for example, both ADS and ADS cannot be defined for every value of \(N\), \(K\), \(\Lambda\) and \(t\). However, it should be noted that the autocorrelation function of CDS is \"binarity\". As a result, the condition limitations of ADS are fewer than those of CDS. Therefore, ADS is able to generate more sets and arrays, and thus it is easier to obtain the array form achieving the designed beam pattern [16].  
\[K(K+1)=t\Lambda(N-1-t)(\Lambda+1) \tag{6}\]  
Another characteristic of ADS is cyclic shift, assuming that \(D^{(o)}\) is a sequence obtained by cyclic shifting \(\sigma\) of the original ADS sequence. These shifted ADS sequences are called the isomorphic ADS sequences and have the same parameters as the original ADS sequences (\(N\), \(K\), \(\Lambda\), \(t\)). Since the maximum number of cyclic shifts \(\sigma\) is the length \(N\) of the original ADS sequence, \(N\) different isomorphic ADS sequences can be obtained by cyclic shift, which are expressed as:  
\[D^{(o)}=\left\{d_{k}^{(o)}=\text{mod}_{N}(d_{k}+\sigma),k=1,...,K\right\} \tag{7}\]  
Here, \(\sigma\in\mathbb{Z}\).