Fast ℓ1-regularized space-time adaptive processing using alternating direction method of multipliers

Lilong Qin; Manqing Wu; Xuan Wang; Zhen Dong

doi:10.1117/1.JRS.11.026004

12 April 2017 Fast ℓ₁-regularized space-time adaptive processing using alternating direction method of multipliers

Lilong Qin, Manqing Wu, Xuan Wang, Zhen Dong

Author Affiliations +

Funded by: Natural Science Foundation of China

Journal of Applied Remote Sensing, Vol. 11, Issue 2, 026004 (April 2017). https://doi.org/10.1117/1.JRS.11.026004

Abstract

Motivated by the sparsity of filter coefficients in full-dimension space-time adaptive processing (STAP) algorithms, this paper proposes a fast ℓ1-regularized STAP algorithm based on the alternating direction method of multipliers to accelerate the convergence and reduce the calculations. The proposed algorithm uses a splitting variable to obtain an equivalent optimization formulation, which is addressed with an augmented Lagrangian method. Using the alternating recursive algorithm, the method can rapidly result in a low minimum mean-square error without a large number of calculations. Through theoretical analysis and experimental verification, we demonstrate that the proposed algorithm provides a better output signal-to-clutter-noise ratio performance than other algorithms.

1. Introduction

Space-time adaptive processing (STAP) can effectively suppress strong ground/sea clutter and improve the moving target indication performance for airborne/spaceborne radar systems.¹ In full-dimension STAP algorithms, however, a large number of independent and identically distributed (I.I.D.) training snapshots are required to yield an average signal-to-clutter-noise ratio (SCNR) loss of $\sim 3 dB$ .² Moreover, full-dimension STAP algorithms have a high system complexity and require many memory elements.³ In practical applications, it is generally difficult to satisfy these requirements.

To date, many algorithms have been proposed to overcome the drawbacks of full-dimension STAP algorithms. Reduced-rank STAP algorithms can reduce the clutter space while maintaining the performance of fully STAP algorithms.⁴^,⁵ Consequently, the required number of snapshots can be reduced. However, eigenvalue decomposition is used, which is computationally expensive. To reduce the computational expense and the number of training snapshots simultaneously, some typical reduced-dimension STAP algorithms have been proposed, such as the joint domain localized approach, auxiliary channel processing, etc.⁶^–⁸ However, the nonadaptive selection of the reduced-dimension projection matrix, which relies on intuitive experience, results in a performance degradation to a certain extent.²

The sparsity of the filter coefficients in STAP has recently been studied, and the theoretical framework for sparsity-based STAP algorithms using the $ℓ_{1}$ -regularized constraint, which is the so-called least absolute shrinkage and selection operator (LASSO), has been established.⁹^–¹² The classical algorithms for solving the LASSO problem adopt convex optimization, e.g., the interior point algorithm, to obtain a sparse solution. The complexity of the algorithms can be very high when the size of the problem is large, which is not pragmatic in practice. To effectively solve the optimization problem, the $ℓ_{1}$ -regularized recursive least-squares STAP (RLS-STAP) algorithm,¹³ the $ℓ_{1}$ -regularized least-mean-square STAP algorithm,¹⁴ and the homotopy-STAP algorithm¹⁵ have been proposed. Compared with conventional STAP methods, sparsity-based STAP techniques have been shown to provide high resolution and exhibit better performance than conventional STAP algorithms.¹⁶

The alternating direction method of multipliers (ADMM) is a technique used to combine the decomposability of dual ascent with the rapid convergence speed of the method of multipliers.¹⁷^,¹⁸ This technique is well suited for solving the optimization problems of the $ℓ_{1}$ constraint, particularly large-scale problems.¹⁹ The ADMM technique can converge within a few tens of iterations, which is acceptable in practical use.²⁰ In this study, according to the optimal criterion of minimizing the mean-square error, we propose an algorithm based on the ADMM technique to solve the $ℓ_{1}$ -regularized STAP problem. The proposed method provides better performance with a small number of I.I.D. training snapshots and without a large number of calculations.

The reminder of this paper is organized as follows. The system model of the generalized side-lobe canceler (GSC) form of the sparsity-based STAP is introduced in Sec. 2. In Sec. 3, the theory of the ADMM algorithm is introduced, and the $ℓ_{1}$ -regularized ADMM-STAP algorithm is proposed. The associated optimization problem is formulated and solved analytically. The performance improvement of the proposed algorithm is shown in Sec. 4. Section 5 provides the conclusion.

Notation: In this paper, a variable, a column vector, and a matrix are represented by a lowercase letter, a lowercase bold letter, and a capital bold letter, respectively. The operations of transposition, complex conjugation, and conjugate transposition are denoted by ${(\cdot)}^{T}$ , ${(\cdot)}^{*}$ , and ${(\cdot)}^{H}$ , respectively. The symbol $\otimes$ ; denotes the Kronecker product, and the symbol ${‖ \cdot ‖}_{n}$ denotes the $ℓ_{n}$ -norm operator. $E (x)$ denotes the expected value of $x$ , $| x |$ indicates the absolute value of $x$ , and ${(x)}_{+} ≜ \max (0, x)$ . $sign (\cdot)$ is the component-wise sign function.¹³

2. Background and Problem Formulation

2.1.

System Model

The STAP technique is known for its ability to suppress clutter energy interference while detecting moving targets. Consider an airborne radar system equipped with a uniform linear array (ULA) consisting of $N$ receiving elements, as shown in Fig. 1. The radar transmits $K$ identical pulses at a constant pulse repetition frequency (PRF) $f_{r} ≜ 1 / T_{r}$ during a coherent processing interval (CPI), where $T_{r}$ is the pulse repetition interval. The received signal from the range bin of interest is represented as $x = x_{t} + x_{c} + n$ , where $x_{t}$ is the target vector, $x_{c}$ is the clutter vector, and $n$ is the thermal noise vector with noise power $σ_{n}^{2}$ on each channel and pulse. The space-time clutter vector can be represented as²¹

Eq. (1)

x_{c} = \sum_{n = 1}^{N_{c}} σ_{c, n} v (f_{d, n}, f_{s, n}),

where

N_{c}

denotes the number of clutter patches in the range bin of interest and

σ_{c, n}

denotes the random complex reflection coefficient.

f_{d, n} ≜ 2 v_{p} T_{r} \sin ϕ_{n} / λ

and

f_{s, n} ≜ d \sin ϕ_{n} / λ

are the Doppler frequency and spatial frequency for the

n

’th clutter patch, respectively, where

λ

is the wavelength and

d

is the innersensor spacing of the ULA.

v (f_{d, n}, f_{s, n}) \in C^{N K \times 1}

is the space-time steering vector, which is defined as a Kronecker product of the temporal and spatial steering vectors, i.e.,

v (f_{d}, f_{s}) = v_{d} (f_{d}) \otimes v_{s} (f_{s})

, where

Eq. (2)

v_{d} (f_{d}) = {[\begin{matrix} 1 & \exp (j 2 π f_{d}) & \dots & \exp [j 2 π f_{d} (K - 1)] \end{matrix}]}^{T} v_{s} (f_{s}) = {[\begin{matrix} 1 & \exp (j 2 π f_{s}) & \dots & \exp [j 2 π f_{s} (N - 1)] \end{matrix}]}^{T} .

The target vector is

x_{t} = σ_{t} v (f_{d, t}, f_{s, t})

, where

f_{d, t} ≜ 2 v_{p} T_{r} \sin ϕ_{t} / λ + 2 v_{t} T_{r} / λ

and

f_{s, t} ≜ d \sin ϕ_{t} / λ

.

v_{t}

is the radial velocity of the moving target, and

ϕ_{t}

represents the angle of arrival (AOA) of the target. Note that in the following,

v (f_{d, t}, f_{s, t})

is rewritten as

v_{t}

for convenience.

Fig. 1

Radar platform flies at speed $v_{p}$ along the azimuth direction ( $x$ -axis). Without loss of generality, the center of elements is defined as the origin of coordinates. $h_{p}$ is the flight height, and $ϕ$ represents the AOA of the clutter patch in the isorange clutter ring.

To clearly illustrate how the STAP method works, the GSC form of the STAP method is shown in Fig. 2. $B \in C^{N K \times (N K - 1)}$ is the signal blocking matrix, which satisfies $B^{H} v_{t} = 0$ and ${BB}^{H} = I$ . Generally, $B$ can be obtained by singular value decomposition (SVD):

Eq. (3)

[\begin{matrix} U & S & V \end{matrix}] = svd (v_{t}^{H}), B = V (:, 2 : N K) .

After the transformation by

b = B^{H} x \in C^{(N K - 1) \times 1}

,

N K - 1

clutter data are available. In the full-dimension STAP, all the data are selected to cancel the clutter. The output is

Eq. (4)

y = d_{0} - ω_{b}^{H} b,

where

d_{0} = v_{t}^{H} x

and

ω_{b} = R_{b}^{- 1} r_{b d}

.

R_{b} = E ({bb}^{H})

is the clutter covariance matrix, and

r_{b d} = E (b d_{0}^{*})

is the cross-correlation vector between

d_{0}

and

b

. The output clutter power can be computed as

Eq. (5)

P = v_{t}^{H} R_{x} v_{t} - r_{b d}^{H} R_{b}^{- 1} r_{b d},

where

R_{x} = E ({xx}^{H})

is the input covariance matrix. The output SCNR can be expressed as

Eq. (6)

ξ = \frac{N M {| α |}^{2}}{v_{t}^{H} R_{x} v_{t} - r_{b d}^{H} R_{b}^{- 1} r_{b d}} .

Maximizing the output SCNR is equivalent to maximizing the detection probability. However,

R_{b}

and

r_{b d}

are unknown in practice, and the secondary training snapshots are required to estimate these parameters.¹⁵ The best performance can be achieved if there are sufficient I.I.D. training snapshots. However, in many practical cases, it is impossible to obtain sufficient snapshots, and the performance degrades significantly.

Fig. 2

(a) GSC form of the conventional STAP and (b) GSC form of the sparsity-based STAP.

2.2.

Sparsity-Based STAP

According to the STAP theory, it has been shown that the rank of clutter covariance is far lower than the DOFs of the system.²²^,²³ Consequently, some RR-STAP and RD-STAP algorithms have been used to reduce the filter length, i.e., the filter coefficient vector obtained by full-dimension STAP is sparse.¹⁴ Hence, in the GSC form of the sparsity-based STAP algorithm (see Fig. 2), the filter coefficient vector $ω_{b}$ can be replaced by ${\tilde{ω}}_{b} = V ω_{b}$ , where $V \overset{Δ}{=} diag (v)$ and $v \in C^{N K - 1}$ denote a sparse vector. Then, we obtain

Eq. (7)

z = V^{H} b \in C^{(N K - 1) \times 1} .

The output of the sparsity-based STAP is

Eq. (8)

y_{r} = d_{0} - ω_{b}^{H} z = [\begin{matrix} 1 & ω_{b}^{H} - ω_{b}^{H} V^{H} \end{matrix}] [\begin{matrix} y \\ b \end{matrix}] .

Hence, the output clutter power for the sparsity-based STAP can be computed as

Eq. (9)

P_{r} = v_{t}^{H} R_{x} v_{t} - r_{b d}^{H} R_{b}^{- 1} r_{b d} + ϵ^{H} R_{b} ϵ,

where

ϵ = ω_{b} - {\tilde{ω}}_{b}

is the weight error vector caused by the sparsity constraint. Note that the target signal power is not affected by the sparsity constraint. The output SCNR can be expressed as

Eq. (10)

ξ_{r} = \frac{N M | α |^{2}}{v_{t}^{H} R_{x} v_{t} - r_{b d}^{H} R_{b}^{- 1} r_{b d} + ϵ^{H} R_{b} ϵ} .

Hence, the aim is to minimize the mean-square error

ϵ^{H} R_{b} ϵ

. The objective function of the minimization problem can be rewritten as

Eq. (11)

ϵ^{H} R_{b} ϵ = r_{b d}^{H} R_{b}^{- 1} r_{b d} - r_{b d}^{H} {\tilde{ω}}_{b} - {\tilde{ω}}_{b}^{H} r_{b d} + {\tilde{ω}}_{b}^{H} R_{b} {\tilde{ω}}_{b} .

{\tilde{ω}}_{b}

is sparse, i.e., most of its elements are considerably smaller than the others. Hence, the minimization problem can be expressed as

Eq. (12)

\min - r_{b d}^{H} {\tilde{ω}}_{b} - {\tilde{ω}}_{b}^{H} r_{b d} + {\tilde{ω}}_{b}^{H} R_{b} {\tilde{ω}}_{b} + λ {‖ {\tilde{ω}}_{b} ‖}_{0},

where

λ

is the regularization parameter for regulating the sparseness of

{\tilde{ω}}_{b}

. However, the

ℓ_{0}

-norm problem is nonconvex. Consequently, it is intractable even for optimization problems with a moderate size. Equation (12) can be further programmed as an LASSO algorithm

Eq. (13)

\min - r_{b d}^{H} {\tilde{ω}}_{b} - {\tilde{ω}}_{b}^{H} r_{b d} + {\tilde{ω}}_{b}^{H} R_{b} {\tilde{ω}}_{b} + λ {‖ {\tilde{ω}}_{b} ‖}_{1} .

In contrast to Eq. (12), Eq. (13) is convex and can be solved by convex optimization algorithms, such as the interior point method (IPM). The complexity of IPM-STAP can be very high when the size of the problem is large, which is not pragmatic in practice.

3. Proposed ℓ₁-Regularized STAP Algorithm

3.1.

Variable Splitting

In general, the ADMM algorithm can converge rapidly when a modest-accuracy result is acceptable. Fortunately, this is the case for the parameter estimation problem in the STAP application that we are considering. For statistical problems, solving a parameter estimation problem to a very high accuracy often yields little improvement.¹⁹ The ADMM-STAP algorithm is based on the algorithm of variable splitting, i.e., we split the variable ${\tilde{ω}}_{b}$ into a pair of variables, say, ${\tilde{ω}}_{b}$ and $z$ , and add a constraint that the two variables are equal. Moreover, the objective function is split as the sum of two functions, and then we minimize the sum of the two functions. Explicitly, Eq. (13) can be rewritten in the ADMM form

Eq. (14)

\min_{{\tilde{ω}}_{b}, z} r_{b d}^{H} {\tilde{ω}}_{b} - {\tilde{ω}}_{b}^{H} r_{b d} + {\tilde{ω}}_{b}^{H} R_{b} {\tilde{ω}}_{b} + λ {‖ z ‖}_{1} s.t. {\tilde{ω}}_{b} = z .

The problems of Eqs. (13) and (14) are clearly equivalent. In many cases, it is easier to solve the constrained problem Eq. (14) than the original unconstrained problem. As in the method of multipliers, the augmented Lagrangian function is formed as¹⁹^,²⁰

Eq. (15)

L_{ρ} ({\tilde{ω}}_{b}, z, y) = - r_{b d}^{H} {\tilde{ω}}_{b} - {\tilde{ω}}_{b}^{H} r_{b d} + {\tilde{ω}}_{b}^{H} R_{b} {\tilde{ω}}_{b} + λ {‖ z ‖}_{1} + (ρ / 2) {‖ {\tilde{ω}}_{b} - z ‖}_{2}^{2} + y^{H} ({\tilde{ω}}_{b} - z),

where

ρ > 0

is the augmented Lagrangian parameter and

y

is a vector of Lagrange multipliers.

3.2.

ℓ₁-Regularized ADMM-STAP

Define the residual and the scaled dual variable as $r = {\tilde{ω}}_{b} - z$ and $d = (1 / ρ) y$ , respectively. Then, we have

Eq. (16)

(ρ / 2) {‖ {\tilde{ω}}_{b} - z ‖}_{2}^{2} + y^{H} ({\tilde{ω}}_{b} - z) = (ρ / 2) {‖ r ‖}_{2}^{2} + y^{H} r = (ρ / 2) {‖ r + d ‖}_{2}^{2} - (ρ / 2) {‖ d ‖}_{2}^{2} .

Subsequently, the ADMM-STAP algorithm can be rewritten in a convenient form

Eq. (17)

{\tilde{ω}}_{b}^{(k + 1)} = \underset{{\tilde{ω}}_{b}}{\arg \min} (- r_{b d}^{H} {\tilde{ω}}_{b} - {\tilde{ω}}_{b}^{H} r_{b d} + {\tilde{ω}}_{b}^{H} R_{b} {\tilde{ω}}_{b} + (ρ / 2) {‖ {\tilde{ω}}_{b} - z^{(k)} + d^{(k)} ‖}_{2}^{2}), z^{(k + 1)} = \underset{z}{\arg \min} (λ {‖ z ‖}_{1} + (ρ / 2) {‖ {\tilde{ω}}_{b}^{(k + 1)} - z + d^{(k)} ‖}_{2}^{2}), d^{(k + 1)} = d^{(k)} + r^{(k + 1)},

where

r^{(k)} = {\tilde{ω}}_{b}^{(k)} - z^{(k)}

is the residual at the

k

’th iteration and

d^{(k)} = d^{(0)} + \sum_{j = 1}^{k} r^{(j)}

is the summation of the residuals. In the first line of Eq. (17), the objective is to minimize a strictly convex quadratic function, and the solution can be easily obtained as

Eq. (18)

{\tilde{ω}}_{b}^{(k + 1)} = {(R_{b} + ρ I)}^{- 1} [r_{b d} + ρ (z^{(k)} - d^{(k)})] .

As mentioned,

R_{b}

and

r_{b d}

are unknown in practice, and they can be estimated as

R_{b} = \sum_{l = 1}^{L} b (l) b^{H} (l) / L

and

r_{b d} = \sum_{l = 1}^{L} b (l) d_{0}^{*} (l) / L

, where

L

denotes the number of snapshots that are used. Moreover,

b (l) = B^{H} x (l)

and

d_{0} (l) = v_{t}^{H} x (l)

, where

x (l)

denotes the

l

’th space-time snapshot.¹³^–¹⁵

The solution of Eq. (18) can be obtained directly, i.e., noniteratively. However, it is impractical because the inversion of $(R_{b} + ρ I)$ has a high computational complexity of $O [{(N K - 1)}^{3}]$ . Note that, according to Fig. 3, the clutter covariance matrix constructed by the training snapshots with regard to the current detecting snapshot can be written as

Eq. (19)

R_{b} = {\overset{͡}{R}}_{b} + \sum_{m = 1}^{4} \frac{{(- 1)}^{m} b_{m} b_{m}^{H}}{L},

where

{\overset{͡}{R}}_{b}

is constructed by the training snapshots with regard to the previous detecting snapshot. Denote

P^{(0)} = {({\overset{͡}{R}}_{b} + ρ I)}^{- 1}

; then, according to the matrix inversion lemma,²⁴ we obtain

Eq. (20)

P^{(m)} = P^{(m - 1)} - \frac{P^{(m - 1)} b_{m} b_{m}^{H} P^{(m - 1)}}{\frac{L}{{(- 1)}^{m}} + b_{m}^{H} P^{(m - 1)} b_{m}}, m = 1,2, 3,4 .

It is clear that

P^{(4)} = {(R_{b} + ρ I)}^{- 1}

. Hence, the computational complexity can be reduced to

O [8 {(N K - 1)}^{2}]

. A full analysis of the computational complexity is presented in Table 1.

Fig. 3

Selection of I.I.D. training snapshots. The guard bands are used to guarantee that the training snapshots contain no components of the moving target.

Fig. 4

The detailed iterative procedure of ADMM-STAP.

Table 1

Computational complexity.

Algorithm	Complex multiplications	Complex additions
SMI-STAP	$O [{(N K - 1)}^{3}]$	$O [{(N K - 1)}^{3}]$
RLS-STAP	$[4 {(N K)}^{2} - 2 N K - 1] L$	$[3 {(N K)}^{2} - 3 N K] L$
OCD-STAP	$[4 {(N K)}^{2} - 5 N K + 2] L$	$[3 {(N K)}^{2} - 4 N K + 1] L$
ADMM-STAP	$(M + 8) {(N K - 1)}^{2} + 4 N K - 4$	$(M + 8) {(N K - 1)}^{2} + 4 M (N K - 1) - 4$

In the second line of Eq. (17), the $z$ -update can be represented as

Eq. (21)

z_{i}^{(k + 1)} = \underset{z_{i}}{\arg \min} [λ | z_{i} | + (ρ / 2) {(z_{i} - {\tilde{w}}_{i}^{(k + 1)} - d_{i}^{(k)})}^{2}] .

Although the absolute value function is not differentiable, a simple closed-form solution can easily be obtained. Explicitly, the solution is

Eq. (22)

z_{i}^{(k + 1)} = S_{λ / ρ} ({\tilde{w}}_{i}^{(k + 1)} + d_{i}^{(k)}),

where

S_{λ} (z)

is the soft-thresholding operator. The soft-thresholding operator is essentially a shrinkage operator, which moves a point toward zero.

In the ADMM-STAP algorithm, ${\tilde{ω}}_{b}$ and $z$ are updated alternately, which accounts for the term alternating direction. The reasonable stopping criteria are that the primal and dual residuals must be small,

Eq. (23)

{‖ {\tilde{ω}}_{b}^{(k)} - z^{(k)} ‖}_{2} \leq ϵ_{pri} and {‖ ρ (z^{(k)} - z^{(k - 1)}) ‖}_{2} \leq ϵ_{dual},

where

ϵ_{pri}

and

ϵ_{dual}

are thresholds that are chosen by absolute and relative criteria

Eq. (24)

ϵ_{pri} = \sqrt{p} ϵ_{abs} + ϵ_{rel} \max {{‖ {\tilde{ω}}_{b}^{(k)} ‖}_{2}, {‖ z^{(k)} ‖}_{2}}, ϵ_{dual} = \sqrt{n} ϵ_{abs} + ϵ_{rel} {‖ y^{(k)} ‖}_{2} .

A reasonable value for

ϵ_{rel}

is

10^{- 4} - 10^{- 3}

, and the choice of

ϵ_{abs}

depends on the scale of the typical variable values. The detailed iterative procedure of ADMM-STAP is shown in Fig. 4.

3.3.

Analysis of Convergence

A proof of the convergence result is presented in this section. First, we begin our proof by presenting the following theorem.

Theorem 1

(Eckstein–Bertsekas):²⁵ Consider the problem

Eq. (25)

\min_{u} f_{1} (u) + f_{2} (v) \begin{matrix} s.t. v = Gu \end{matrix},

in the case where the functions

f_{1} (\cdot)

and

f_{2} (\cdot)

are closed, proper, and convex and

G

has a full column rank. Let

{η_{k} \geq 0, k = 0, 1, \dots}

and

{γ_{k} \geq 0, k = 0, 1, \dots}

be two sequences such that

Eq. (26)

\sum_{k = 0}^{\infty} η_{k} < 0 and \sum_{k = 0}^{\infty} γ_{k} < 0 .

Assume that there are three sequences ${u_{k}, k = 0,1, \dots}$ , ${v_{k}, k = 0,1, \dots}$ , and ${t_{k}, k = 0,1, \dots}$ that satisfy

Eq. (27)

η_{k} \geq ‖ u_{k + 1} - \underset{u}{\arg \min} {f_{1} (u) + (ρ / 2) {‖ Gu - v_{k} - t_{k} ‖}_{2}^{2}} ‖ γ_{k} \geq ‖ v_{k + 1} - \underset{v}{\arg \min} {f_{2} (v) + (ρ / 2) {‖ {Gu}_{k + 1} - v - t_{k} ‖}_{2}^{2}} ‖ t_{k + 1} = t_{k} - ({Gu}_{k + 1} - v_{k + 1}) .

Then, if Eq. (25) has an optimal solution

u^{†}

, the sequence

{u_{k}}

converges to this solution, i.e.,

u_{k} \to u^{†}

.

First, since Eq. (14) is a particular instance when $G = I$ , the full-rank condition in Theorem 1 can be satisfied. Second, it is clear that $f_{1} ({\tilde{ω}}_{b}) = - r_{b d}^{H} {\tilde{ω}}_{b} - {\tilde{ω}}_{b}^{H} r_{b d} + {\tilde{ω}}_{b}^{H} R_{b} {\tilde{ω}}_{b}$ and $f_{2} (z) = 2 λ {‖ z ‖}_{1}$ in Eq. (14) are closed, proper, and convex. Moreover, the sequences ${{\tilde{ω}}_{b}^{(k)}}$ , ${z^{(k)}}$ , and ${u^{(k)}}$ generated by Eq. (17) satisfy the conditions of Eq. (27) in a strict sense ( $η_{k} = γ_{k} = 0$ ). Hence, the convergence is guaranteed.

3.4.

Analysis of Computational Complexity

A comparison of the computational complexities of four STAP algorithms, namely, the conventional sample matrix inversion (SMI) STAP,² $ℓ_{1}$ -regularized RLS-STAP,¹⁴ $ℓ_{1}$ -regularized online coordinate descent (OCD) STAP,²⁶ and the proposed ADMM-STAP algorithms, is presented in Table 1. The computational complexity is measured by the number of complex multiplications and additions. As shown in Table 1, the ADMM-STAP algorithm has a computational complexity of $O [(M + 8) {(N K - 1)}^{2}]$ , where $M$ is the number of iterations. According to the simulation in Sec. 4, the algorithm can converge to an acceptable solution within a few tens of iterations, i.e., $M + 8$ would be less than $4 L$ and $N K - 1$ . Hence, the ADMM-STAP algorithm has the lowest level of computational complexity.

4. Simulation Results

The simulation parameters for the ground moving target indication application are listed in Table 2: a radar system equipped with a side-looking ULA is employed, and the elements are spaced half a wavelength apart, i.e., $d = λ / 2$ . Additive noise is modeled as spatially and temporally independent complex Gaussian noise with zero mean and unit variance. $f_{r} = 4 v_{p} / λ$ ; hence, $β = 2 v_{p} T_{r} / d = 1$ . All the results are obtained from the average of 100 independent Monte–Carlo simulations.

Table 2

Simulation parameters for airborne radar.

Parameter	Notation	Value	Unit
Antenna array spacing	$d$	$λ / 2$	m
Pulse repetition frequency	$f_{r}$	2314	Hz
Carrier frequency	$f_{c}$	1.24	GHz
Array element number	$N$	10	—
CPI pulse number	$K$	10	—
Bandwidth	—	10	MHz
Platform velocity	$v_{p}$	140	m/s
Platform height	$h_{p}$	8000	m
Signal-to-noise ratio	SNR	0	dB

4.1.

Setting of Regularization Parameter

The regularization parameter provides a tradeoff between the SCNR steady-state performance and the convergence speed. Although it is clear that the value of $λ$ should be proportional to the noise power and be inversely proportional to the rank of the clutter covariance matrix, it is still difficult to determine the optimal value. Adjusting the regularization parameter adaptively is an interesting research area (e.g., Refs. 13 and 14). However, this area is not the main focus of our paper. In this paper, the regularization parameter is selected from a fixed set $Ω = {0.1, 1,10, 50}$ .

The output SCNR versus the number of snapshots that are used with different values of the regularization parameter $λ$ is shown in Fig. 5. In this simulation, we assume that the signal of the moving target impinges the array from a DOA of 90 deg and that the radial velocity of the moving target $v_{t}$ is $28 m / s$ (the Doppler frequency of the moving target is nearly 231 Hz). The results in Fig. 5 indicate that (i) the value of $λ$ is crucial to the output SCNR performance, and there is a reasonable range of values, i.e., $1 \leq λ \leq 10$ , that can improve the convergence speed and the output SCNR steady-state performance simultaneously; (ii) the output SCNR is degraded when $λ$ is too large since the filter weight vector is shrunk to zero; and (iii) the output SCNR performance is not considerably improved when $λ$ is too small. In this case, the output SCNR performance is nearly similar to that of the conventional STAP algorithm.

Fig. 5

Output SCNR versus the number of used snapshots with different regularization parameters. (a) $CNR = 20 dB$ and (b) $CNR = 40 dB$ .

The output SCNR performance versus the Doppler frequency of the moving target at a DOA of 90 deg is shown in Fig. 6. The range of potential Doppler frequency is from $- 500$ − to 500 Hz, and 60 snapshots are used to optimize the filter vector. The same conclusion can be obtained. This figure shows that the ADMM-STAP algorithm with $1 \leq λ \leq 10$ provides a satisfactory output SCNR performance.

Fig. 6

Output SCNR performance versus Doppler frequency with different regularization parameters, and the range of Doppler frequency is from $- 500$ to 500 Hz. (a) $CNR = 20 dB$ and (b) $CNR = 40 dB$ .

The number of iterations with different values of $λ$ is shown in Fig. 7. As shown, if we choose $λ$ from an appropriate range ( $0.5 \leq λ \leq 10$ ), then the ADMM-STAP algorithm can converge rapidly within a few tens of iterations, which is acceptable in practice. Otherwise, the number of iterations increases significantly, and the iteration output cannot converge to the optimal solution leading, to a performance degradation to a certain extent.

Fig. 7

Number of iterations versus the value of $λ$ . The radial velocity of the moving target is $28 m / s$ , and 60 snapshots are used in the simulation. (a) $CNR = 20 dB$ and (b) $CNR = 40 dB$ .

4.2.

Comparison with Other Algorithms

In this section, we will compare the output SCNR performance of our proposed algorithm with that of IPM-STAP, OCD-STAP, and RLS-STAP algorithms. The regularization parameter $λ$ is set to 1 for all the algorithms, and the other parameters are the same as in the previous simulations. The output SCNR performances versus the number of used snapshots and the target Doppler frequency are compared in Figs. 8 and 9. As shown in these figures, we can see that (i) the output SCNR performance of the IPM-STAP algorithm is superior to that of the RLS-STAP and OCD-STAP algorithms. However, it is achieved at a high computational cost and (ii) the output SCNR performance of the ADMM-STAP algorithm can outperform that of the IPM-STAP algorithm, which supports our previous conclusion that optimizing the problem of parameter estimation to a high accuracy generally yields no improvement.

Fig. 8

Output SCNR versus the number of used snapshots when the radial velocity of the moving target is $28 m / s$ . (a) $CNR = 20 dB$ and (b) $CNR = 40 dB$ .

Fig. 9

Output SCNR performance versus Doppler frequency with 60 snapshots, and the range of Doppler frequency is from $- 500$ to 500 Hz. (a) $CNR = 20 dB$ and (b) $CNR = 40 dB$ .

5. ℓ₁-Regularized STAP with Mountaintop Data

The performance of the $ℓ_{1}$ -regularized STAP approaches is verified here using the Mountaintop data set (data No. t38pre01v1) acquired with the experimental radar system RSTER (radar surveillance technology experimental radar) sponsored by the Advanced Research Projects Agency. The Mountaintop program is devoted to supporting the mission requirements of next-generation airborne early warning platforms and to supporting the evaluation of STAP algorithms. The antenna for the system is a 5-m wide by 10-m high horizontally polarized array composed of 14 column elements. The CPI pulse number is 16, the antenna array spacing is 0.333 m, the PRF is 625 Hz, the carrier frequency is 435 MHz, and the bandwidth is 500 kHz. The transmit beam is steered to illuminate a mountain range (a large clutter scatter).

The data set is divided into two subsets in our experiment. The first subset, including 100 snapshots, is used to train the STAP filters. The second subset, including 100 snapshots, is used to test the performance. Two simulated moving targets are added to the test data subset. The signal of the first target impinges the array from a DOA of $- 25 \deg$ , and the Doppler frequency is 62.5 Hz. The signal of the second target impinges the array from a DOA of 20 deg, and the Doppler frequency is 187.5 Hz. Hence, the first target can essentially be regarded as a ground moving vehicle in the mountain, and the second target can be regarded as an aircraft near the mountain. The minimum variance distortionless response (MVDR) spectra of the two subsets are shown in Fig. 10.

Fig. 10

(a) MVDR spectrum of the training subset and (b) MVDR spectrum of the test subset.

The improvement factor (IF) performance, which is defined as the ratio of the output SCNR to the input SCNR, is investigated in Fig. 11. The regularization parameter $λ$ is set to 1 for all the algorithms. As shown, the IF performance of the proposed ADMM-STAP approach substantially outperforms that of the other approaches. Hence, the effectiveness of the proposed approach is confirmed by an experimental multichannel radar system RSTER.

Fig. 11

(a) IF performance versus the number of used snapshots for the first target and (b) IF performance versus the number of used snapshots for the second target.

6. Conclusions

In this paper, we proposed a sparsity-based approach based on an $ℓ_{1}$ -regularized constraint to accelerate the convergence speed of STAP. The optimization problem with an additional $ℓ_{1}$ -regularized constraint was solved using the ADMM, and the detailed iterative procedure of ADMM-SATP was derived. Through the examples, it was demonstrated that the proposed method can effectively decrease the required number of secondary snapshots and provide better performance than the $ℓ_{1}$ -regularized OCD-STAP and $ℓ_{1}$ -regularized RLS-STAP methods.

Acknowledgments

The authors thank the National Natural Science Foundation of China under Grant No. 61101178 and the China Scholarship Council for their support.

References

1.

H. Wang et al., “Robust waveform design for MIMO-STAP to improve the worst-case detection performance,” EURASIP J. Adv. Signal Process., 2013 (1), 1 –8 (2013). http://dx.doi.org/10.1186/1687-6180-2013-52 Google Scholar

2.

W. L. Melvin, “A STAP overview,” IEEE Aerosp. Electron. Syst. Mag., 19 (1), 19 –35 (2004). http://dx.doi.org/10.1109/MAES.2004.1263229 IESMEA 0885-8985 Google Scholar

3.

X. Guo et al., “Modified reconstruction algorithm based on space-time adaptive processing for multichannel synthetic aperture radar systems in azimuth,” J. Appl. Remote Sens., 10 (3), 035022 (2016). http://dx.doi.org/10.1117/1.JRS.10.035022 Google Scholar

4.

R. Fa and R. C. De Lamare, “Reduced-rank STAP algorithms using joint iterative optimization of filters,” IEEE Trans. Aerosp. Electron. Syst., 47 (3), 1668 –1684 (2011). http://dx.doi.org/10.1109/TAES.2011.5937257 IEARAX 0018-9251 Google Scholar

5.

R. Fa, R. C. de Lamare and L. Wang, “Reduced-rank STAP schemes for airborne radar based on switched joint interpolation, decimation and filtering algorithm,” IEEE Trans. Signal Process., 58 (8), 4182 –4194 (2010). http://dx.doi.org/10.1109/TSP.2010.2048212 ITPRED 1053-587X Google Scholar

6.

R. Li et al., “Reduced-dimension space-time adaptive processing based on angle-Doppler correlation coefficient,” EURASIP J. Adv. Signal Process., 2016 (97), 1 –9 (2016). http://dx.doi.org/10.1186/s13634-016-0395-2 Google Scholar

7.

W. Zhang et al., “Multiple-input multiple-output radar multistage multiple-beam beamspace reduced-dimension space-time adaptive processing,” IET Radar Sonar Navig., 7 (3), 295 –303 (2013). http://dx.doi.org/10.1049/iet-rsn.2012.0078 Google Scholar

8.

W. Zhang et al., “A method for finding best channels in beam-space post-Doppler reduced-dimension STAP,” IEEE Trans. Aerosp. Electron. Syst., 50 (1), 254 –264 (2014). http://dx.doi.org/10.1109/TAES.2013.120145 IEARAX 0018-9251 Google Scholar

9.

K. Sun, H. Meng and F. Lapierre, “Registration-based compensation using sparse representation in conformal-array STAP,” Signal Process., 91 (10), 2268 –2276 (2011). http://dx.doi.org/10.1016/j.sigpro.2011.04.008 Google Scholar

10.

K. Sun, H. Meng and Y. Wang, “Direct data domain STAP using sparse representation of clutter spectrum,” Signal Process., 91 (9), 2222 –2236 (2011). http://dx.doi.org/10.1016/j.sigpro.2011.04.006 Google Scholar

11.

S. Sen, “OFDM radar space-time adaptive processing by exploiting spatio-temporal sparsity,” IEEE Trans. Signal Process., 61 (1), 118 –130 (2013). http://dx.doi.org/10.1109/TSP.2012.2222387 ITPRED 1053-587X Google Scholar

12.

Z. Yang, X. Li and H. Wang, “Space-time adaptive processing based on weighted regularized sparse recovery,” Prog. Electromagnet. Res. B, 42 245 –262 (2012). http://dx.doi.org/10.2528/PIERB12051804 Google Scholar

13.

Z. Yang, R. C. De Lamare and X. Li, “L1-regularized STAP algorithm with a generalized side-lobe canceler architecture for airborne radar,” IEEE Trans. Signal Process., 60 (2), 674 –686 (2012). http://dx.doi.org/10.1109/TSP.2011.2172435 ITPRED 1053-587X Google Scholar

14.

Z. Gao et al., “L1-regularised joint iterative optimisation space-time adaptive processing algorithm,” IET Radar Sonar Navig., 10 (3), 435 –441 (2016). http://dx.doi.org/10.1049/iet-rsn.2015.0044 Google Scholar

15.

Z. Yang et al., “Sparsity-based space-time adaptive processing using complex-valued homotopy technique for airborne radar,” IET Signal Process., 8 (5), 552 –564 (2014). http://dx.doi.org/10.1049/iet-spr.2013.0069 Google Scholar

16.

M. Shen et al., “An efficient moving target detection algorithm based on sparsity-aware spectrum estimation,” Sensors, 14 (9), 17055 –17067 (2014). http://dx.doi.org/10.3390/s140917055 SNSRES 0746-9462 Google Scholar

17.

J. Qin, I. Yanovsky and W. Yin, “Efficient simultaneous image deconvolution and upsampling algorithm for low-resolution microwave sounder data,” J. Appl. Remote Sens., 9 (1), 095035 (2015). http://dx.doi.org/10.1117/1.JRS.9.095035 Google Scholar

18.

H. Zhai et al., “Reweighted mass center based object-oriented sparse subspace clustering for hyperspectral images,” J. Appl. Remote Sens., 10 (4), 046014 (2016). http://dx.doi.org/10.1117/1.JRS.10.046014 Google Scholar

19.

S. Boyd et al., “Distributed optimization and statistical learning via the alternating direction method of multipliers,” Found. Trends Mach. Learn., 3 (1), 1 –122 (2010). http://dx.doi.org/10.1561/2200000016 Google Scholar

20.

M. Afonso, J. Bioucas-Dias and M. Figueiredo, “Fast image recovery using variable splitting and constrained optimization,” IEEE Trans. Image Process., 19 (9), 2345 –2356 (2010). http://dx.doi.org/10.1109/TIP.2010.2047910 IIPRE4 1057-7149 Google Scholar

21.

Z. Yang et al., “On clutter sparsity analysis in space-time adaptive processing airborne radar,” IEEE Geosci. Remote Sens. Lett., 10 (5), 1214 –1218 (2013). http://dx.doi.org/10.1109/LGRS.2012.2236639 Google Scholar

22.

G. M. Herbert, “Clutter modeling for space-time adaptive processing in airborne radar,” IET Radar Sonar Navig., 4 (2), 178 –186 (2010). http://dx.doi.org/10.1049/iet-rsn.2009.0064 Google Scholar

23.

H. Sun et al., “Estimation of the ocean clutter rank for HF/VHF radar space-time adaptive processing,” IET Radar Sonar Navig., 4 (6), 755 –763 (2010). http://dx.doi.org/10.1049/iet-rsn.2009.0252 IETTAW 0018-9448 Google Scholar

24.

B. Chen et al., “Quantized kernel recursive least squares algorithm,” IEEE Trans. Neural Netw. Learn. Syst., 24 (9), 1484 –1491 (2013). http://dx.doi.org/10.1109/TNNLS.2013.2258936 Google Scholar

25.

J. Eckstein and D. Bertsekas, “On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators,” Math. Program., 55 (1), 293 –318 (1992). http://dx.doi.org/10.1007/BF01581204 MHPGA4 1436-4646 Google Scholar

26.

D. Angelosante, J. A. Bazerque and G. B. Giannakis, “Online adaptive estimation of sparse signals: where RLS meets the L1-norm,” IEEE Trans. Signal Process., 58 (7), 3436 –3447 (2010). http://dx.doi.org/10.1109/TSP.2010.2046897 ITPRED 1053-587X Google Scholar

Biography

Lilong Qin is working toward his PhD at the National University of Defense Technology, Changsha, China, and is working with Aalto University, Espoo, Finland. He received his BS degree in information engineering and his MS degree in circuit and system from the Electronic Engineering Institute, Hefei, China, in 2010 and 2013, respectively. His current research interests include synthetic aperture radar and adaptive beamforming.

Manqing Wu received his MS degree from the National University of Defense Technology, Changsha, China, in 1990. Currently, he is a professor with the China Electronics Technology Group Corporation, Beijing, China, and is a member of the Chinese Academy of Engineering. His research field is radar signal processing.

Xuan Wang received her PhD in signal and information processing from Beijing Institute of Technology, Beijing, China, in 2016. Currently, she is working at Delft University of Technology, Delft, the Netherlands. Her current research interest is synthetic aperture radar.

Zhen Dong received his PhD from the National University of Defense Technology, Changsha, China, in 2001. Currently, he is a professor with the National University of Defense Technology, and his research field includes synthetic aperture radar interferometry and array radar.

CC BY: © The Authors. Published by SPIE under a Creative Commons Attribution 4.0 Unported License. Distribution or reproduction of this work in whole or in part requires full attribution of the original publication, including its DOI.

Citation Download Citation

Lilong Qin, Manqing Wu, Xuan Wang, and Zhen Dong "Fast ℓ₁-regularized space-time adaptive processing using alternating direction method of multipliers," Journal of Applied Remote Sensing 11(2), 026004 (12 April 2017). https://doi.org/10.1117/1.JRS.11.026004

Received: 22 December 2016; Accepted: 25 March 2017; Published: 12 April 2017

Access the abstract

JOURNAL ARTICLE
13 PAGES

DOWNLOAD PAPER SAVE TO MY LIBRARY

GET CITATION

KEYWORDS

Detection and tracking algorithms

Algorithms

Doppler effect

Radar

Computer simulations

Optimization (mathematics)

Chemical elements

1.

Introduction

2.

Background and Problem Formulation

2.1.

System Model

Eq. (1)

Eq. (2)

Fig. 1

Eq. (3)

Eq. (4)

Eq. (5)

Eq. (6)

Fig. 2

2.2.

Sparsity-Based STAP

Eq. (7)

Eq. (8)

Eq. (9)

Eq. (10)

Eq. (11)

Eq. (12)

Eq. (13)

3.

Proposed ℓ1-Regularized STAP Algorithm

3.1.

Variable Splitting

Eq. (14)

Eq. (15)

3.2.

ℓ1-Regularized ADMM-STAP

Eq. (16)

Eq. (17)

Eq. (18)

Eq. (19)

Eq. (20)

Fig. 3

Fig. 4

Table 1

Eq. (21)

Eq. (22)

Eq. (23)

Eq. (24)

3.3.

Analysis of Convergence

Theorem 1

Eq. (25)

Eq. (26)

Eq. (27)

3.4.

Analysis of Computational Complexity

4.

Simulation Results

Table 2

4.1.

Setting of Regularization Parameter

Fig. 5

Fig. 6

Fig. 7

4.2.

Comparison with Other Algorithms

Fig. 8

Fig. 9

5.

ℓ1-Regularized STAP with Mountaintop Data

Fig. 10

Fig. 11

6.

Conclusions

Acknowledgments

References

Biography

Show All Keywords

Keywords/Phrases

Search In:

Publication Years

Proposed ℓ₁-Regularized STAP Algorithm

ℓ₁-Regularized ADMM-STAP

ℓ₁-Regularized STAP with Mountaintop Data