Efficient Large Sparse Arrays Synthesis by Means of Smooth Re-Weighted L1 Minimization

Abstract

In this paper, we present an efficient technique for the synthesis of very large sparse arrays, with arbitrary circularly-symmetrical upper bounds for the pattern specifications. The algorithm, which is based on iterative smooth re-weighted L1 minimizations, is very flexible and is capable of achieving very good performances with respect to competitive algorithms. Furthermore, thanks to its efficiency, planar arrays of hundreds of wavelengths can be synthesized with limited computational effort.

1. Introduction

Antenna arrays are one of the most important technologies that allows responding to the challenges of the close future communication systems, particularly in the 5G and IoT frameworks [1,2,3,4]. In this perspective, the use of sparse, non-regular, arrays is particularly appealing, since it has been shown that a sparse array is often capable of achieving the same performance of regular lattice ones, with a much lower number of radiating elements, and a strong reduction of the issue of grating lobes.

Unfortunately, the synthesis of a sparse array is a much tougher task with respect to the synthesis of regular lattice ones. This difference is due to the fact that the relationship between the radiated field and the excitation of the radiating elements is linear. This allows the use of efficient linear and convex programming techniques for the determination of the elements’ excitation once the position of the radiators is fixed. Instead, the relationship between the radiated field and the element’s positions is non-linear and non-convex, and no optimal algorithms capable of solving this problem are currently known.

In the last few decades, researchers have followed different approaches to face the synthesis of sparse arrays. They can be roughly summarized into two main categories. In the first one, we have all evolutionary computation-based methods [5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20], which exploit the capability of genetic algorithms, particle swarm optimization, and similar techniques to face the multiple minima that arise from the aforementioned non-linearity and non-convexity.

A second category is represented by a number of different approaches in which the general synthesis problem is substituted by a simpler one, which can be faced by means of deterministic techniques [21,22,23,24,25,26,27,28,29,30,31,32,33].

Both approaches show advantages and disadvantages. The former class is advantaged from the fact that a well-designed evolutionary algorithm is capable of asymptotically finding the optimal solution of a given problem. The main issue is represented by the word “asymptotically”. The number of iterations needed to get “close” to the global optimum is an exponential function of the number of unknowns, so it is very hard to deal with evolutionary algorithms when the dimension of the desired array is very large: we get a solution, but it is often impossible to say how close to the optimum we are [34].

For the latter category, instead, the execution is—generally speaking—fast, and we are usually allowed to solve, with relative ease, large problems. However, again, since the starting problem solved is a sub-optimal one, we do not usually obtain the global optimum.

The aforementioned classification is obviously a very simplified one, since the years hybrid and mixed strategies have been presented [35,36,37,38,39,40,41]; furthermore, the recent development of compressive sensing [42], and related algorithms, has provided effective and computationally-efficient algorithms [43,44,45,46,47,48,49,50,51,52,53]. In particular, the synthesis of sparse linear arrays of hundreds of wavelengths was shown in [53], a result that to the best knowledge of the authors is currently unmatched.

The synthesis of planar arrays of more than a hundred of wavelengths is instead an open issue. This kind of problems is computationally very difficult to face, because of the huge number of unknowns, with evolutionary algorithms; no results have been shown in the open literature by using other kinds of algorithms.

In this contribution, we will propose a sub-optimal, yet effective, approach to the solution of this kind of problem, to be used for circularly-symmetric beam pattern specifications. In particular, the circular symmetry of the specifications will be used to simplify the layout: we will look for antenna arrays with the elements displaced in circular concentric rings, with a reduction of the number of unknowns to optimize for. Furthermore, we will exploit a smooth re-weighted ${\ell }_1$-norm minimization, a compressive sensing-inspired approach, to look for the minimum number of rings; finally, each ring will be populated with a number of elements as small as possible, to achieve an overall minimum number of radiators.

The paper will be organized as follows. First of all, we will discuss the synthesis problem formulation (Section 2), then we will propose the use of a compressive sensing-like approach for the determination of the number of rings (Section 3) and the population of rings with radiating elements (Section 4). In Section 5, we will provide some numerical results to validate the proposed approach; and conclusions follow (Section 6).

2. Problem Formulation

For the sake of simplicity, we will consider the case of isotropic radiators; most of the considerations that we will discuss in the remainder of the paper can be extended to cases in which we take into account the element factor with minimum effort.

Let us now consider the array factor of N number of sources placed on the $\{x,y\}$ plane:

$$F(\theta ,\varphi )=\sum _{n=1}^N{a}_n{e}^{j\beta (x_{n}sin\theta cos\varphi +y_{n}sin\theta sin\varphi )}$$

(1)

where $\beta =2\pi /\lambda$ is the free space wavenumber, $\lambda$ is the wavelength, $\{x_n,y_n\}$ are the coordinates of the n-th radiating element, and $a_n$ is its excitation

The sparse array synthesis problem consists of finding the position and excitation of the N radiating elements in order to satisfy a chosen array factor specification. As an example, we could require that:

$$\left|F\right(\theta ,\varphi \left)\right|\le M_{UP}(\theta ,\varphi )$$

(2)

$$F(0,0)=1$$

(3)

which represent the typical specifications of a pattern with arbitrary upper bounds.

Some considerations are now in order. First, the number N of radiators could not be specified, and it could also be one of the outputs of the optimization, since such a number is often required to be as small as possible. Second, in some specific applications, we would like all the radiating elements to share the same excitations (i.e., “uniform excitation” arrays) or we suppose that the power delivered to each radiator, which could be also of two or more different kinds, is equal (i.e., “isophoric” arrays).

As stated in the Introduction, the general solution of this kind of problem, even in the case of convex constraints for the pattern specifications, leads to a non-linear and non-convex problem, which is usually very hard to solve, and no deterministic techniques for its optimal solution are known.

It is now worth recalling that, when the array elements are arranged into circles, equally-spaced along each ring (Figure 1), the array factor (1) can be recast in a very convenient way:

$$F(\theta ,\varphi )=\sum _{p=1}^P{A}_p{N}_p\sum _{m=-\infty }^{+\infty }{J}_{m{N}_p}(\beta R_{p}sin\theta )e^{jm{N}_p\Xi (\theta ,\varphi )}$$

(4)

where P is the overall number of rings, $N_p$ is the number of antennas along the p-th ring, $A_p$ is the common excitation of the elements belonging to the p-th ring of radius $R_p$, $J_h(\ast )$ is the n-th order Bessel function of the first kind, and $\Xi (\theta ,\varphi )$ is a function of the angular variables, inessential for our purposes [54].

The main advantage of the Formulation (4) is due to the fact that the Bessel functions, other than the zero-order ones, tend to become very small under very simple conditions; in particular, it is well known that $|J_a\left(b\right)|<<1$ when $b<<a$, so looking to the worst case of $m=1$ if:

$$\beta R_{p}sin\theta <<N_p\approx 2\pi R_p/d$$

(5)

where d is the distance between two radiating elements on the same ring. Recasting (5) gives:

$$d<<\lambda /sin\theta$$

(6)

This means that as long as the elements belonging to the same ring are not too widely spaced, the array factor can be conveniently approximated by:

$$F(\theta ,\varphi )\approx F\left(\theta \right)=\sum _{p=1}^P{A}_p{N}_p{J}_0(\beta R_{p}sin\theta )$$

(7)

This approximation is particularly useful, since the synthesis can be done analyzing the $\theta$ angular direction only, with a significant computational improvement. Obviously, this simplification is applicable only to the synthesis of a radiation pattern with a circular symmetry (i.e., $M_{UP}(\theta ,\varphi )=M_{UP}\left(\theta \right)$).

In the next section, we will discuss how we can use a compressive sensing approach to synthesize very large sparse arrays exploiting (7).

3. Smooth Re-Weighted L1 Minimization

For the sake of simplicity, in the next section, we will call $e_p=A_p{N}_p$ the ring excitation. The synthesis problem will be then recast as finding the number of rings, their radii, and excitations in order to satisfy the given pattern specifications; the choice of the balancing between $A_p$ and $N_p$ will depend on the antenna architecture specifications (i.e., constant excitation $A_p$ for isophoric arrays).

Let us now consider a dummy ring array, made of a huge number of closely-spaced rings, introducing a dense equispaced position $\nu$-element vector $\tilde{\mathbf{r}}$ in the range $[0,R]$, with an inter-element spacing $\delta$ much smaller than the wavelength $\lambda$, and a vector of observation points $\mathbf{w}=\{w_1,\dots w_{\zeta }\}\in [0,w_{max}]$, so that:

$$\mathbf{F}=\mathbf{A}\tilde{\mathbf{e}}$$

(8)

provides the relationship between the array factor sampled in $w_h=sin{\theta }_h$ and the vector of ring excitations $\tilde{\mathbf{e}}$, achieved by the radiation matrix $\mathbf{A}$, whose $h,k$ element is $a_{h,k}=J_0\left(\beta r_k{w}_h\right)$.

The radial and angular discretization of the array factor allow us to solve the synthesis problem by solving the following constrained minimization:

$$minimize\parallel \tilde{\mathbf{e}}{\parallel }_0$$

(9)

$$subjectto|\mathbf{A}\tilde{\mathbf{e}}|\le {\mathbf{M}}_{UP}$$

(10)

$${\mathbf{A}}_{\mathbf{0}}\tilde{\mathbf{e}}=1$$

(11)

where ${\parallel \mathbf{v}\parallel }_0$ represents the so-called ${\ell }_0$-norm of $\mathbf{v}$ vector, ${\mathbf{M}}_{UP}$ is the sampled version of the upper mask, and ${\mathbf{A}}_{\mathbf{0}}$ is the array factor in the direction of the desired maximum of the main beam. The ${\ell }_p$ norm of $\mathbf{v}$ is defined for $p\ge 1$ as ${\parallel \mathbf{v}\parallel }_p=({\sum }_k|v_k{{|}^p)}^{1/p}$. Strictly speaking, the so-called ${\ell }_0$-norm is not a norm, and it is given by the number of non-null elements of $\mathbf{v}$.

Once this minimization is solved, the sparse vector of the solution will give us the radii and excitations of the rings of our sparse array (2) and (3). In particular, this approach would lead to the layout employing the smallest number of rings.

Unfortunately, there are no known deterministic optimal techniques to solve the ${\ell }_0$-norm minimization, but as shown in [45,52,55,56], the ${\ell }_0$-norm minimization can be conveniently approximated in a computationally-efficient way by using a sequence of weighted ${\ell }_1$ minimizations. We could then try to solve the following convex problem iteratively:

$$minimize\parallel {\mathbf{g}}^p\circ {\tilde{\mathbf{e}}}^p{\parallel }_1$$

(12)

$$subjectto|\mathbf{A}{\tilde{\mathbf{e}}}^p|<{\mathbf{M}}_{UP}$$

(13)

$${\mathbf{A}}_{\mathbf{0}}{\tilde{\mathbf{e}}}^p=1$$

(14)

where ${\mathbf{g}}^p\circ {\tilde{\mathbf{e}}}^p$ is the Hadamard entry-wise product of the two vectors ${\mathbf{g}}^p$ and ${\tilde{\mathbf{e}}}^p$, ${\parallel \mathbf{v}\parallel }_1$ is the ${\ell }_1$-norm of the $\mathbf{v}$ vector, given by ${\sum }_k\left|v_k\right|$, p is the iteration index, and ${\mathbf{g}}^p=[g_1^p,\cdots ,g_{\nu }^p]$ is a proper weighting vector.

As shown in [52], by means of a non-local, “smooth” weighting vector, it is possible to reduce the step of the radial discretization, preserving the small “clusters” that arise in the solution of the ${\ell }_1$-norm minimization. In particular, we have used:

$$g_k^p=\frac{1}{max(z_k^{p-1},\eta )}$$

(15)

where ${\tilde{\mathbf{z}}}^{p-1}=[z_1^{p-1},\cdots ,z_{\nu }^{p-1}]$ and:

$${\tilde{\mathbf{z}}}^{p-1}=\left|{\tilde{\mathbf{e}}}^{p-1}\right|\ast \mathbf{d}$$

(16)

and $\mathbf{d}$ is a smoothing vector of positive numbers, while the convolution “*” returns only the central part of it, of the same size as $|{\tilde{\mathbf{e}}}^{p-1}|$.

Once the algorithm has reached a satisfactory solution, it is very easy to extract the ring radii $R_p$ and excitations $e_p$ from vector $\tilde{\mathbf{e}}$, by means of the refined clustering approach described in [52].

One of the further advantages of the smooth re-weighted minimization is that, when the iterations have converged (i.e., ${\tilde{\mathbf{e}}}^p={\tilde{\mathbf{e}}}^{p-1}$), if some easy conditions are verified [52], we have that:

$$\parallel {\mathbf{g}}^p\circ {\tilde{\mathbf{e}}}^p{\parallel }_1\approx {\mathcal{N}}_c$$

(17)

where ${\mathcal{N}}_c$ is the number of clusters of non-null elements of ${\tilde{\mathbf{e}}}^p$, i.e., the number of rings of the sparse concentric ring array synthesized. It should be underlined that, because of the non-convex nature of the synthesis problem, the iterative algorithm could not reach the absolute minimum value of ${\mathcal{N}}_c$ (even if it is among one of the possible solutions of the algorithm), since it could stop in a local minimum.

Last but not least, the possibility to reduce the discretization step $\delta$, allowed by the “smooth” weight, is particularly beneficial from a computational point of view, because each ${\ell }_1$ minimization iteration requires a computation time that is at least a quadratic function of the number of variables, which is proportional to $1/\delta$. This efficiency is numerically confirmed by the quick computation times needed for achieving the results in Section 5.

4. Ring Population from the Calculated Excitation

As stated in Section 2, the ring excitation represents the product of the number of elements and the relative excitation of the radiators belonging to a certain ring. The same ring excitation could be achieved by different combinations of the two factors; the specific choice we need to perform to synthesize the array layout will depend on a particular “ring population strategy”.

In this section, we will discuss two different ring population strategies: the former, to be used in equal amplitude and isophoric arrays; the latter to be used in arrays with variable excitation of the radiating elements.

The key point in both strategies is reducing as much as possible the number of radiators, trying always to limit the effect of the higher order Bessel terms of (4).

For isophoric arrays, we need first to identify the index of the “minimally-populated ring” (MPR), the ring that presents the lowest ratio of the excitation $e_p$ and the ring radius $R_p$. Once the MPR has been identified, the number of radiators $N_{MPR}$ on such a ring can be chosen in order to verify:

$$J_{N_{MPR}}(\beta R_{MPR}sin\theta )<\frac{T}{e_{MPR}}$$

(18)

where T is a threshold that depends on the required side lobe level (SLL)—usually one hundredth of the SLL is sufficient. The value of $N_{MPR}$ can be determined numerically, and then, the number of radiators on all the other rings can be obtained as:

$$N_p=e_p\frac{N_{MPR}}{e_{MPR}}$$

(19)

The ring population strategy for arrays with variable elements’ excitation consists, instead, of finding for each ring the minimum number of radiators that allows limiting the effect of higher order Bessel terms:

$$J_{N_p}(\beta R_{p}sin\theta )<\frac{T}{e_p}$$

(20)

Once such a number is found, the element excitation can be achieved by:

$$A_p=\frac{e_p}{N_p}$$

(21)

Obviously, those two strategies aim at the reduction of the number of radiators, and slightly modified versions could be used if other specifications need to be met (for instance, a fixed overall number of radiators). Moreover, the aforementioned strategies can be easily modified to include non-overlapping constraints for the radiators.

The synthesis approach consists of the following steps:

• Choose the values of $\delta$, $\mathbf{d}$, and $\eta$ to use.
• Iteratively solve the problem (12)–(14); usually, less than twenty iterations allow the convergence;
• we extract the ring radii and excitations from the sparse vector $\tilde{\mathbf{e}}$;
• we populate the ring according to one of the discussed strategies, using (19) or (21).

The core of the procedure is represented by the second step; for convenience of the reader, a simple CVX [57] code implementing the weighted ${\ell }_1$ minimization is provided below:

cvx_begin

 cvx_solver sedumi

 variable e(nu)

 minimize (norm (G*e, 1))

 subject to

  abs (A*e) <= Mup

  A0*e == 1

cvx_end

In this code, we use SeDuMi as the solver, “e(nu)” is the $\nu$ length column vector ${\tilde{\mathbf{e}}}^p$, “G” is a diagonal matrix implementing the smooth weight (15), “A" and “Mup” are, respectively, the matrix and the column vector implementing (13), and “A0” is a row vector implementing (14).

5. Numerical Examples

In this section, we will provide some examples that will show the effectiveness of the proposed approach. For all the tests, we have used an inter-ring spacing of $\delta =\lambda /20$; the smoothing vector is $\mathbf{d}=[0.1,0.5,0.99,1,0.99,0.5,0.1]$, and the tolerance factor is $\eta =max\left(\right|{\tilde{\mathbf{x}}}^p|/100)$. All the minimizations have been solved by means of CVX [57] in MATLAB.

5.1. Large Array with Variable Excitation

In the first example, we will consider the synthesis of a sparse array with the same specification of the 718 elements array of [39]; this sparse array is able to radiate a pattern with a side lobe level lower than −37.05 dB for $w\ge 0.074$. By means of the proposed approach, we are able to synthesize a sparse array of 597 elements organized into 12 rings (Figure 2), which satisfies the same specifications with a reduction of the radiating elements’ number of about $17\%$ with respect to the reference layout.

In particular, the parameters of the found array are provided in

Table 1. Parameters of the synthesized 597 element array.

#	${\mathit{R}}_{\mathit{p}}$ ($\mathit{\lambda }$)	${\mathit{N}}_{\mathit{p}}$	${\mathit{A}}_{\mathit{p}}$
1	0.9	7	0.693
2	1.805	15	1
3	2.665	22	0.943
4	3.55	29	0.794
5	4.476	37	0.72
6	5.403	45	0.631
7	6.352	53	0.52
8	7.309	61	0.464
9	8.222	68	0.368
10	9.161	76	0.269
11	10.15	85	0.277
12	11.85	99	0.15

. The minimum, average, and maximum spacing between the rings are, respectively, 0.860$\lambda$, 0.995$\lambda$, and 1.700$\lambda$. The dynamical ratio of the excitations, the ratio of the maximum and minimum excitation of the elements, is $16.5$ dB. The array factor of the synthesized array is displayed in Figure 3 and Figure 4. It is interesting to observe from Figure 3 that the $\varphi$-cuts were perfectly superimposed up to about 56°, confirming the fact that the Bessel function terms other than the zero-order ones are correctly limited by the right choice of the element number per ring.

The calculation of the layout is very quick: ten iterations are needed, and each iteration took about 10 s on an Intel i7 8700k processor.

5.2. Small Isophoric Sparse Array

In the second example, we will consider the synthesis of a sparse array with the same specifications of the 185-element array of [51]; this sparse array has been synthesized by means of an approach similar to the one proposed in this paper, but does not employ the smooth weighting function. The reference sparse array is able to radiate a pattern with a side lobe level lower than −23.51 dB and shows a first null beamwidth (FNBW) of 14.2°. By means of our approach, we are able to synthesize a sparse array of 167 elements organized into six rings (Figure 5), which satisfies the same SLL specifications with a reduction of beamwidth (in our case. the FNBW is 13.5°) and a reduction of the radiating element number of about $10\%$.

In particular, the parameters of the found array are provided in

Table 2. Parameters of the synthesized 167-element array.

#	${\mathit{R}}_{\mathit{p}}$ ($\mathit{\lambda }$)	${\mathit{N}}_{\mathit{p}}$
1	1.127	14
2	1.85	22
3	2.7	27
4	3.5	27
5	4.317	29
6	5.45	48

. The minimum, average, and maximum spacing between the rings are, respectively, 0.72273$\lambda$, 0.86454$\lambda$, and 1.1333$\lambda$. The array factor of the synthesized array is displayed in Figure 6 and Figure 7.

It is worth noting that the calculation of the layout is almost instantaneous: only three iterations are needed, and each iteration took less than 2 s on an Intel i7 8700k processor.

5.3. Very Large Isophoric Sparse Array

In this section, we instead will discuss the synthesis of a large sparse array with constant element excitation, with a diameter of about 290$\lambda$. To the best knowledge of the authors, there are no results available in the open literature with sparse arrays of these dimensions, confirming the capability of the proposed approach to handle synthesis problems of very high size.

The particular array sought should be able to radiate a pencil beam with a side lobe level lower than −30 dB for $w\ge 0.005$ and to scan it on the whole Earth’s surface from GEO orbit, always satisfying the SLL constraint within the Earth’s surface (that is seen as a solid angle of about ${8.5}^{\circ }$ (deg) radius). For this reason, the synthesis will be performed in the angular region with $w_{max}=0.287$, following the guidelines in [31].

By means of the proposed approach, we are able to synthesize a sparse array of 3516 elements organized into 17 rings; see Figure 8, which perfectly satisfies the same chosen specifications.

In particular, the parameters of the found array are provided in

Table 3. Parameters of the synthesized 3516-element array.

#	${\mathit{R}}_{\mathit{p}}$ ($\mathit{\lambda }$)	${\mathit{N}}_{\mathit{p}}$
1	19.602	144
2	30.594	192
3	38.25	139
4	43.45	167
5	48.647	103
6	52	117
7	60.1	119
8	63.45	130
9	69.048	162
10	75.5	238
11	80.84	232
12	90.75	301
13	103.45	272
14	110.95	264
15	118.721	223
16	126.9	215
17	144.459	498

. The minimum, average, and maximum spacing between the rings are, respectively, 3.350$\lambda$, 7.804$\lambda$, and 17.559$\lambda$. The array factor of the synthesized array is displayed in Figure 9 and Figure 10; in Figure 11, we also show a scanned beam at the edge of the Earth’s surface, as seen from GEO orbit.

In this case, the calculation of the layout is slower than the previous cases: 41 iterations are needed, and each iteration took about 70 s on an Intel i7 8700k processor; but considering the dimension of the achieved layout, this is indeed an excellent result.

6. Discussion and Conclusions

A very efficient algorithm for the synthesis of sparse arrays has been presented.

The approach is capable of synthesizing sparse arrays with variable or constant excitation of the elements, allowing the satisfaction of circularly-symmetrical constraints for the upper bounds of the pattern.

The results shown, summarized in

Table 4. Results’ summary. FNBW, first null beamwidth.

Layout	N	Main Beam	SLL (dB)	Iterations	Iteration Time (s)
Figure 2	597	$w\le 0.074$	−37.05	10	10
Ref. [39]	718	$w\le 0.074$	−37.05	n.a.	n.a.
Figure 5	167	FNBW = 13.5°	−23.51	3	2
Ref. [51]	185	FNBW = 14.2°	−23.51	n.a.	n.a.
Figure 8	3516	$w\le 0.005$	−30	41	70

Computation times refer to an i7 8700k PC.

, are very good, and the obtained layouts present a lower number of elements with respect to other algorithms in the literature, when the same pattern specifications are met. Obviously, we do not believe that our algorithm is able to provide the best solutions, since the problem it solves is just an approximation of the more general synthesis problem. Accordingly, the method does not assure the optimality of the solution.

It is worth noting that, due to the complex non-linear characteristic of the synthesis problem object of the paper, no method (including genetic algorithms) assures the convergence toward the optimal solution in finite time. Furthermore, the radiators are “forced” into concentric rings, instead of being freely placed on a plane. However, the good quality of the results obtained, together with the relative quickness of the method even for very large arrays, make us confident of the significance of our approach.

It has also to be underlined that the computational efficiency of the approach allows to face also problems of very large size: in one of the examples a sparse planar array of about three hundred wavelengths is demonstrated, and in other numerical tests, not shown here for sake of brevity, we were able to synthesize even larger arrays.

In a future development we plan to extend the proposed synthesis method to the case of shaped beams.