# Efficient Rotating Synthetic Aperture Radar Imaging via Robust Sparse Array
Synthesis

Wei Zhao, , Cai Wen, , Quan Yuan, , Rong Zheng Manuscript received 16 January
2023; revised 14 April 2023; accepted 14 August 2023. (Corresponding Author:
Cai Wen; Rong Zheng.)Wei Zhao, Rong Zheng and Quan Yuan are with the
department of Computing and Software, McMaster University, Hamilton, ON L8S
4L8 Canada (e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>yuanq4@mcmaster.ca).Cai Wen is with the School of Information Science and
Technology, Northwest University, Xi’an, China. He is also with the department
of Computing and Software, McMaster University, Hamilton, Canada. (e-mail:
wencai@nwu.edu.cn).

###### Abstract

Rotating Synthetic Aperture Radar (ROSAR) can generate a 360° image of its
surrounding environment using the collected data from a single moving track.
Due to its non-linear track, the Back-Projection Algorithm (BPA) is commonly
used to generate SAR images in ROSAR. Despite its superior imaging
performance, BPA suffers from high computation complexity, restricting its
application in real-time systems. In this paper, we propose an efficient
imaging method based on robust sparse array synthesis. It first conducts
range-dimension matched filtering, followed by azimuth-dimension matched
filtering using a selected sparse aperture and filtering weights. The aperture
and weights are computed offline in advance to ensure robustness to array
manifold errors induced by the imperfect radar rotation. We introduce robust
constraints on the main-lobe and sidelobe levels of filter design. The
resultant robust sparse array synthesis problem is a non-convex optimization
problem with quadratic constraints. An algorithm based on feasible point
pursuit and successive convex approximation is devised to solve the
optimization problem. Extensive simulation study and experimental evaluations
using a real-world hardware platform demonstrate that the proposed algorithm
can achieve image quality comparable to that of BPA, but with a substantial
reduction in computational time up to 90%.

###### Index Terms:

Rotating SAR, sparse array, robust design, successive convex approximation

##  I Introduction

Synthetic Aperture Radar (SAR) has been widely used in military reconnaissance
and remote sensing, because of its all-weather all-day acquisition
capabilities [1]. Conventional SAR working modes include “stripmap”,
“spotlight” and “scan”[2]. In these modes, high range resolutions are achieved
by transmitting large bandwidth signals, while the high resolution in the
cross-range dimension is achieved by utilizing the Doppler effect induced by
the relative motion between the radar platform and the target. However, the
imaging swaths of these SAR modes are relatively small due to the limited beam
footprint and the restricted moving track. Different from the aforementioned
imaging schemes, Rotating SAR (ROSAR) systems mount antennas on the edge of
rotation platforms with a certain radius[3]. Through platform rotating, ROSAR
systems are able to scan the surrounding environment continuously and generate
a 360° image using the collected data from a single moving track[4]. ROSAR can
overcome limited (angular) field-of-view of radar boards and allow imaging
without translational movements of the platform making it a promising low-cost
solution in helicopter-borne SAR imaging[5, 6, 7], indoor imaging[8] and so
on. In indoor environments, ROSAR can be used for mapping and localization in
case of fire emergencies or situations where other sensors fail due to high
heat and low visibility.

Due to the highly non-linear moving track of ROSAR, Back-Projection Algorithm
(BPA)[9, 10] is typically employed, where its basic idea is to perform range-
azimuth matched filtering with the prior knowledge of the distance between the
target and each phase center. Although the conventional BPA can produce high-
quality images without any limitation on the array geometry, it suffers
extremely high computation complexity making it inadequate for real-time high-
resolution imaging systems. The computational complexity of BPA is
proportional to the number of pixels, the number of fast-time samples per
pulse and the number of pulses needed to generate one image. In a practical
system, all three parameters can be very large: the number of pixels depends
on the image resolution; a high pulse repetition frequency (PRF) and
consequently dense virtual array elements are required to avoid aliasing[11];
and a large signal bandwidth, which results in a large number of fast-time
samples, is needed to ensure the high range-resolution. However, due to the
unique array geometry of ROSAR, frequency domain processing algorithms such as
Chirp Scaling Algorithm[12] and Omega-K[13] that assume linear motions of the
radar platform relative to the scene are not applicable. In the past decades,
much effort has been made in improving the efficiency of BPA and many
algorithms have been proposed. For example, fast factorized Back-Projection
(FFBP)[14, 15], Cartesian factorized BPA[16] and its variant[17]. The core
idea of these algorithms is sub-aperture fusion. In sub-aperture fusion, the
entire aperture is split into many small apertures and BPA is applied to each
sub-aperture to obtain coarse images. A high-quality image can then be
obtained by fusing these coarse-grained images together. However, all of them
assume a linear aperture too and cannot be applied to circular aperture
directly. In addition, sparse array synthesis is also a technique with low
complexity. Conventional ways to select sparse elements, e.g., randomly or
uniformly, are not optimal under every condition. Compressive sensing-based
algorithms [18, 19] still suffer from high complexity, the requirement of
sparse environment and sensitivity to array manifold error.

In this work, we propose a new sparse array synthesis technique to reduce the
computation complexity of BPA[20]. A key novelty of our design lies in the
consideration of array geometry mismatch. Mismatch is prevalent in practical
ROSAR systems due to imperfect rotational control or measurements. To solve
for sparse complex weights of the virtual array elements, we formulate a
robust constrained optimization problem and devise an algorithm based on
feasible point pursuit (FPP) [21] and successive convex approximation (SCA)
[22]. Compared with conventional aforementioned method, the proposed method is
optimal subject to sidelobe constraints and robust to a certain level of array
manifold error. Besides, thanks to the symmetry of the circular array, the
algorithm only needs to be executed in an offline manner for one azimuth
direction per range bin in the radar coverage area, and the results can be
used for range bins in any direction. The resulting sparse weights effectively
reduce the number of pulses needed in BPA. To further reduce the complexity of
the proposed algorithm, we perform range-dimension matched filtering by
employing Fast Fourier Transform (FFT). For a specific target in space, only
the signals from the appropriate range bins at each phase center is selected.
The sparse array design constitutes an important step toward realizing ROSAR
on mobile devices with limited in space, battery power and computation
capacity.

We have implemented the proposed algorithms in MATLAB. Extensive numerical
simulations are conducted to evaluate the impact of the parameter settings on
the sparsity of the design and array patterns. Additionally, we simulate radar
transmission and receiving signals using the MATLAB Phased Array Toolbox and
collect real-world data from indoor environments from a rotational hardware
platform. The evaluation study shows that in both simulations and real
experiments the proposed algorithm can reduce the total computation time by
more than 90% while generating SAR images with comparable quality as BPA.

The rest of the paper is organized as follows. Section II gives the system
model of ROSAR and formulates the sparse array synthesis problem for ROSAR.
Problem transformation and the solution approach are proposed in Section III.
Section III-D introduces range-dimension filtering using range-FFT to further
reduce computation complexity. We validate our approach in Section IV by
numerical evaluation and simulation study as well as experiments in real
environment in Section IV-F. Section V concludes the paper.

##  II System Model and Problem Formulation

In this section, we introduce the ROSAR system geometry, signal model,
preprocessing steps and give the formal problem formulation of spare array
design at the end. Frequently used symbols are summarized in Table I.

TABLE I: Frequently Used Symbols $N$ |  # of virtual phase centers per circle
---|---
$n$ |  Index of phase centers
$\phi_{n}$ |  Bore-sight direction of the $n$-th phase center
$\phi_{t}$, $R_{t}$ |  The direction and range of target $t$
$\phi_{v}$ |  The angle such that if $\phi_{n}\in(\pi/2-\phi_{v},\pi/2+\phi_{v})$, the target is visible to the $n$-th phase center
$\theta_{n}$, $R_{n}$ |  The distance and direction observed from the $n$-th phase center to the target
$p(\cdot)$ |  Antenna radiation pattern
$x(t)$ |  Transmitted chirp signal
$y_{n}(t)$ |  Received signal at the $n$-th phase center
$y_{\text{IF},n}(t)$ |  IF signal at the $n$-th phase center
$y_{\text{IF},n}(m)$ |  Sampled IF signal at the $n$-th phase center
$y_{\text{1D},n}(l)$ |  The data in the $l$-th range bin at the $n$-th phase center
$\mathbf{y}_{\text{1D},n}$ |  Data vector after applying range-FFT at the $n$-th phase center
$\mathbf{Y}_{\text{IF}}$, $\mathbf{Y}_{\text{1D}}$ |  Valid data matrix for SAR
$\mathbf{a}(\phi;\ R)$ |  Steering vector
$F(\phi;R)$ |  Array pattern
$\mathbf{w}$ |  Weight vector
$\mathbf{e}$ |  Array error vector
$\left(\cdot\right)^{T}$ |  Matrix transpose
$\left(\cdot\right)^{H}$ |  Matrix conjugate-transpose

###  II-A Radar Geometry

Figure 1: Imaging geometry of a ROSAR system

Consider a stationary ROSAR system in Fig. 1. The radar is moving along the
edge of a circle centered at the origin with radius $r$. The bore-sight of the
antenna always faces outwards along the radial directions. The antenna
radiation pattern in azimuth is assumed to be cosine-shape and non-zero within
$\left[-\frac{\pi}{2},\frac{\pi}{2}\right]$. The radar transmits chirp signals
at a constant rate, e.g., $N$ times per circle. Due to the symmetry, without
loss of generality, we define a 2D coordinate frame such that a point target
$R_{t}$ distance away from the circle center locates at $(0,R_{t})$ and the
first (indexed by 0) phase center (with respect to the $X$-axis counter-clock
wise) is at $(r,0)$. Then, the bore-sight direction of the antenna at the
$n$-th radar position (phase center) is

$\phi_{n}=\frac{2\pi n}{N},$ (1)

where $n=0,1,..,N-1$. Let $R_{n}$ and $\theta_{n}$ be the distance and the
direction from the $n$-th phase center to the target with respect to its bore-
sight direction, respectively. Due to the cosine antenna beam pattern, the
target is in the field of view (FoV) of only a subset of antenna positions.
Denote by $\phi_{v}$ the angle such that if
$\phi_{n}\in(\pi/2-\phi_{v},\pi/2+\phi_{v})$, the target is visible to the
$n$-th phase center. $R_{n}$, $\theta_{n}$ and $\phi_{v}$ can be derived from
trigonometry relationships, i.e.,

$\displaystyle R_{n}$ $\displaystyle=$
$\displaystyle\sqrt{R_{t}^{2}+r^{2}-2rR_{t}\cos\left(\phi_{n}-\phi_{t}\right)},$
(2) $\displaystyle\theta_{n}$ $\displaystyle=$
$\displaystyle\arctan\frac{R_{t}\cdot\sin\left(\left|\phi_{n}-\phi_{t}\right|\right)}{R_{t}\cdot\cos\left(\left|\phi_{n}-\phi_{t}\right|\right)-r},$
(3) $\displaystyle\phi_{v}$ $\displaystyle=$
$\displaystyle\arccos\frac{r}{R_{t}}.$ (4)

The indices of the phase centers where the target is in their FOV are given by

$n=N_{\min},N_{\min}+1,N_{\min}+2,\ldots,N_{\max},$ (5)

where
$N_{\min}=\left\lceil\frac{\frac{\pi}{2}-\phi_{v}}{\phi_{\Delta}}\right\rceil$,
$N_{\max}=\left\lfloor\frac{\frac{\pi}{2}+\phi_{v}}{\phi_{\Delta}}\right\rfloor$
and $\phi_{\Delta}=\frac{2\pi}{N}$. To generate the image of the target, only
signals received by those phase centers are used.

###  II-B Signal Model and Preprocessing

Let the chirp signal transmitted by the radar be

$x(t)=e^{j2\pi\left(f_{c}t+\frac{1}{2}Kt^{2}\right)},$ (6)

where $f_{c}$ is the carrier frequency, $K$ is the chirp slope and $t$ is the
fast time. The received signal at the $n$-th phase center is

$y_{n}(t)=\alpha_{n}e^{j2\pi\left[f_{c}(t-\tau_{n})+\frac{1}{2}K(t-\tau_{n})^{2}\right]}+v(t),$
(7)

where $\alpha_{n}$ combines the complex reflection coefficient of the target,
the antenna radiation pattern and channel fading, $\tau_{n}={2R_{n}}/{c}$ is
the round-trip time delay, $c$ is the speed of the light, $v(t)$ is the
Gaussian white noise at the receiver side. Specifically, the antenna radiation
pattern is represented as

$p\left(\theta\right)=\left\\{\begin{matrix}\cos\left(\theta\right)&\theta\in\left(-\frac{\pi}{2},\frac{\pi}{2}\right),\\\
0&\text{otherwise}.\\\ \end{matrix}\right.$ (8)

After down-converting and deramping, the resulting intermediate frequency (IF)
signal is

$\begin{array}[]{r@{}l}y_{\text{IF},n}(t)=&y_{n}(t)^{*}\cdot x(t)\\\
=&\alpha_{n}e^{j2\pi\left[\tau_{n}Kt+\left(f_{c}\tau_{n}-\frac{1}{2}K\tau_{n}^{2}\right)\right]}+v_{\text{IF}}(t)\\\
\approx&\alpha_{n}e^{j2\pi\left[\tau_{n}Kt+f_{c}\tau_{n}\right]}+v_{\text{IF}}(t),\end{array}$
(9)

where $v_{\text{IF}}(t)=v^{*}(t)\cdot x(t)$. The residual video phase (RVP)
term $-\frac{1}{2}K\tau_{n}^{2}$ is negligible compared with other phase
terms. Let the sampling frequency, the total number of samples, sampling
interval, sampling start time in one chirp be $F_{s}$, $M$, $t_{s}$
($t_{s}={1}/{F_{S}}$), $T_{Start}$, respectively. The sampled IF signal is

$y_{\text{IF},n}(m)=\alpha_{n}e^{j2\pi\left[\tau_{n}K\left(mt_{s}+T_{Start}\right)+f_{c}\tau_{n}\right]}+v_{\text{IF}}(m),$
(10)

where $m$ is the sampling index, $0\leq m\leq M-1$. Combining all the samples,
we get the following vector representation

$\mathbf{y}_{\text{IF},n}=\begin{bmatrix}\alpha_{n}e^{j2\pi\left[\tau_{n}K\left(0\cdot
t_{s}+T_{Start}\right)+f_{c}\tau_{n}\right]}\\\
\alpha_{n}e^{j2\pi\left[\tau_{n}K\left(1\cdot
t_{s}+T_{Start}\right)+f_{c}\tau_{n}\right]}\\\ \vdots\\\
\alpha_{n}e^{j2\pi\left[\tau_{n}K\left((M-1)\cdot
t_{s}+T_{Start}\right)+f_{c}\tau_{n}\right]}\\\
\end{bmatrix}+\mathbf{v}_{\text{IF}},$ (11)

where
$\mathbf{v}_{\text{IF}}=\left[v_{\text{IF}}(0),v_{\text{IF}}(1),\ldots,v_{\text{IF}}(M-1)\right]^{T}$.
Let $k={2\pi\left(KT_{start}+f_{c}\right)}/{c}$. Substituting the $\tau_{n}$’s
in each entry by ${2R_{n}}/{c}$ and rearranging items in (11), we have

$\mathbf{y}_{\text{IF},n}=\begin{bmatrix}\alpha_{n}e^{j2\pi\tau_{n}K\cdot
0\cdot t_{s}}e^{j2kR_{n}}\\\ \alpha_{n}e^{j2\pi\tau_{n}K\cdot 1\cdot
t_{s}}e^{j2kR_{n}}\\\ \vdots\\\ \alpha_{n}e^{j2\pi\tau_{n}K\cdot(M-1)\cdot
t_{s}}e^{j2kR_{n}}\\\ \end{bmatrix}+\mathbf{v}_{\text{IF}}.$ (12)

Now, the data matrix from the effective phase centers used for SAR is

$\mathbf{Y}_{\text{IF}}=\left[\mathbf{y}_{\text{IF},N_{\min}},\mathbf{y}_{\text{IF},N_{\min}+1},\ldots,\mathbf{y}_{\text{IF},N_{\max}}\right].$
(13)

The conventional BPA images a point with parameter
$\left(\phi_{t},R_{t}\right)$ by computing the Hadamard product of
$\mathbf{Y}_{\text{IF}}$ and a matrix $\mathbf{W}_{\text{BP}}$ of size
$M\times\left(N_{\max}-N_{\min}+1\right)$, where the element locating at the
$i$-th row and $j$-th column is

$\mathbf{W}_{\text{BP},(i,j)}\\!=\\!\alpha_{N_{\min}+j-1}e^{-j2\pi\tau_{N_{\min}+j-1}K(i-1)t_{s}}e^{-j2kR_{N_{\min}+j-1}}.$

Then, the intensity of the point is

$I\left(\phi_{t},R_{t}\right)=\mathbf{1}^{T}\cdot\left(\mathbf{W}_{\text{BP}}\odot\mathbf{Y}_{\text{IF}}\right)\cdot\mathbf{1},$
(14)

where $\odot$ is the symbol of Hadamard product. If the target indeed locates
at $\left(\phi_{t},R_{t}\right)$ in polar coordinates, all the phases of the
sampled data are perfectly compensated, and (14) achieves its maximum.
However, the computation complexity of imaging a rectangular area using
conventional BPA is $O\left(L_{x}\times L_{y}\times M\times N\right)$, where
$L_{x}$ and $L_{y}$ is the number of grids along $X$ and $Y$ direction of the
area. Clearly, the complexity grows linearly with $M$, $N$ and area size. From
the complexity analysis, it can be deduced that two possible ways to lower the
complexity of BPA are, (1) reducing the number of phase centers to be used,
i.e., reducing $N$, and (2) apply range-dimension matched filtering and select
the appropriate range bin instead of using all $M$ data samples in each pulse.

In the subsequent sections, we first develop a Sparse Array Synthesis (SAS)
method that selects a subset of the phase centers and assigns appropriate
complex weights. Then, we investigate the use of range-dimension matched
filter (or more commonly known as range FFT) to further reduce computation
complexity. The two approached are abbreviated to “SAS” and “FFT+SAS”
respectively for simplicity.

###  II-C Problem Formulation for Robust Sparse Array Synthesis

For simplicity, we assume that the reflection coefficient is always 1. Due to
complex multipath reflection, wall penetration in indoor environments and the
small diameter of the rotation platform relative to the dimension of the
environment, the channel fading factor can be approximated to be a constant
for the same range bin in all directions and thus we omit it in the
formulation. Thus,

$\alpha_{n}=p\left(\theta_{n}\right).$ (15)

BPA can be viewed as a form of range-azimuth two-dimension filtering. To
generalize it to sparsely-selected phase centers, we first apply a
compensation matrix to $\mathbf{Y}_{\text{IF}}$ to remove the phase items
related to fast-time sampling, i.e.,

$\displaystyle\mathbf{Y}_{\text{IF}}^{\prime}$ $\displaystyle=$
$\displaystyle\mathbf{W}_{\text{SA}}\odot\mathbf{Y}_{\text{IF}},$
$\displaystyle=$
$\displaystyle\begin{bmatrix}\alpha_{N_{\min}}e^{j2kR_{N_{\min}}}&\cdots&\alpha_{N_{\max}}e^{j2kR_{N_{\max}}}\\\
\alpha_{N_{\min}}e^{j2kR_{N_{\min}}}&\cdots&\alpha_{N_{\max}}e^{j2kR_{N_{\max}}}\\\
\vdots&\ddots&\vdots\\\
\alpha_{N_{\min}}e^{j2kR_{N_{\min}}}&\cdots&\alpha_{N_{\max}}e^{j2kR_{N_{\max}}}\\\
\end{bmatrix},$

where the $i$-th row and $j$-th column element of $\mathbf{W}_{\text{SA}}$ is
$\mathbf{W}_{\text{SA},(i,j)}=e^{-j2\pi\tau_{N_{\min}+j-1}K\cdot(i-1)\cdot
t_{s}}$. The steering vector of the ROSAR array to a near-field target located
at range $R$ can be represented as

$\mathbf{a}(\phi;R)=\begin{bmatrix}\cos(\theta^{{}^{\prime}}_{N_{\min}})e^{j2k\sqrt{R^{2}+r^{2}-2Rr\cos(\phi-\phi_{N_{\min}})}}\\\
\cos(\theta^{{}^{\prime}}_{N_{\min}+1})e^{j2k\sqrt{R^{2}+r^{2}-2Rr\cos(\phi-\phi_{N_{\min}+1})}}\\\
\vdots\\\
\cos(\theta^{{}^{\prime}}_{N_{\max}})e^{j2k\sqrt{R^{2}+r^{2}-2Rr\cos(\phi-\phi_{N_{\max}})}}\\\
\end{bmatrix},$ (16)

where
$\theta^{{}^{\prime}}_{n}=\arctan\frac{R\sin(\left|\phi-\phi_{n}\right|)}{R\cos(\left|\phi-\phi_{n}\right|)-r}$,
and the array pattern can also be calculated as

$F(\phi;R)=\mathbf{w}^{H}\mathbf{a}(\phi;R),$ (17)

where $\mathbf{w}$ is a sparse complex weight vector to be designed and some
of its elements can be equal or be close to zero. Note that, $\mathbf{w}$ is
also a function of $R$, but we omit the subscript $R$ for simplicity. To focus
a point target locating at $(\phi_{t},R_{t})$, we need to compute

$\displaystyle I\left(\phi_{t},R_{t}\right)\\!\\!\\!$ $\displaystyle=$
$\displaystyle\\!\\!\\!\mathbf{1}^{T}\cdot\left(\mathbf{w}^{H}\circ\mathbf{Y}_{\text{IF}}^{\prime}\right)\cdot\mathbf{1}$
$\displaystyle=$
$\displaystyle\\!\\!\\!\mathbf{1}^{T}\cdot\left(\mathbf{w}^{H}\circ\mathbf{W}_{\text{SA}}\odot\mathbf{Y}_{\text{IF}}\right)\cdot\mathbf{1},$

where $\circ$ is the Khatri-Rao product.

Due to the vibration of the rotation platform, odometry errors and antenna
pattern mismatch (e.g., cosine pattern), there exist array manifold errors,
which may lead to blurred images. To obtain an SAR image with good quality in
this situation, the sparse weight vector $\mathbf{w}$ must be carefully
designed with consideration of robustness to array errors.

We formulate the way to obtain the desirable $\mathbf{w}$ as to solve an
optimization problem. In the optimization, the first constraint is that the
power of the main-lobe peak, locating at $\phi_{m}=\frac{\pi}{2}$, should be
larger than or equal to a threshold $U$, i.e.,

$\left|\mathbf{w}^{H}\left(\mathbf{a}\left(\phi_{m};R\right)+\mathbf{e}_{m}\right)\right|^{2}\geq
U,\ \ \left\|\mathbf{e}_{m}\right\|\leq\Delta_{R},$ (18)

where $\mathbf{e}_{m}$ is the array error vector caused by measurement and
imperfect radar rotations, and we assume that $\mathbf{e}_{m}$ is bounded by a
ball with radius $\Delta_{R}$
($0\leq\Delta_{R}\leq\left\|\mathbf{a}(\phi;R)\right\|$). Second, to restrict
the main-lobe width and the sidelobe level, we put limitations on the received
power at some uniformly spaced discrete directions except for the desired main
lobe area, i.e.,

$\left|\mathbf{w}^{H}\left(\mathbf{a}\left(\phi_{s};R\right)+\mathbf{e}_{s}\right)\right|^{2}\leq\eta
U,\ \ s=1,2,\ldots,S;\left\|\mathbf{e}_{s}\right\|\leq\Delta_{R},$ (19)

where $\mathbf{e}_{s}$ is the error vector for sidelobe area with the same
properties as $\mathbf{e}_{m}$, $S$ is the number of uniformly spaced discrete
directions,
$\phi_{s}\in\left[\phi_{N_{\min}},\frac{\pi}{2}-\phi_{\text{MW}}\right]\cup\left[\frac{\pi}{2}+\phi_{\text{MW}},\phi_{N_{\max}}\right]$,
$\phi_{\text{MW}}$ is the half of the desirable main-lobe width, $\eta$ is the
pre-set power ratio of the main-lobe to the sidelobe. Third, to avoid
amplifying the noise level, we impose a constraint on the gain of noise power:

$\left\|\mathbf{w}\right\|_{2}^{2}=1.$ (20)

Lastly, to guarantee a sufficient gain on the target, we set another
constraint $U\geq U_{\min}$.

The objective is to minimize the number of virtual phase centers given by
$\left\|\mathbf{w}\right\|_{0}$. To this end, we formulate the sparse array
synthesis problem as

$\min_{\mathbf{w},U,\mathbf{e}_{m},\mathbf{e}_{s}}\left\|\mathbf{w}\right\|_{0}$
$s.t.\\!\\!\left\\{\\!\\!\\!\\!\begin{array}[]{l}C1\\!\\!:\\!\\!\left|\mathbf{w}^{H}\left(\mathbf{a}\left(\phi_{m};R\right)+\mathbf{e}_{m}\right)\right|^{2}\geq
U,\left\|\mathbf{e}_{m}\right\|\leq\Delta_{R},\\\
C2\\!\\!:\\!\\!\left|\mathbf{w}^{H}(\mathbf{a}(\phi_{s};R)\\!+\\!\mathbf{e}_{s})\right|^{2}\\!\\!\leq\\!\\!\eta
U,s\\!=\\!1,2,\ldots,S;\\!\left\|\mathbf{e}_{s}\right\|\\!\\!\leq\\!\\!\Delta_{R},\\\
C3\\!\\!:\\!\\!\left\|\mathbf{w}\right\|_{2}^{2}=1,\\\ C4\\!\\!:\\!\\!U\geq
U_{\min}.\\\ \end{array}\right.$ (21)

Problem (21) is a non-convex optimization problem since both the objective
function and constraints C1 and C3 are non-convex. Because of the
consideration of robustness to array errors, the problem formulation is
markedly different from those in conventional sparse array synthesis[23, 24,
25, 26, 27, 28], rendering existing techniques inapplicable. In the next
section, we develop a customized algorithm based on FPP and SCA to solve (21).

##  III Solution Approach for Robust Sparse Array Synthesis (SAS)

###  III-A Problem Transformation

Directly solving (21) is hard, since $l^{0}$-norm minimization problem
requires intractable combinatorial search. To reduce the complexity, we
replace the $l^{0}$-norm objective function with $l^{1}$-norm, i.e.,
$\left\|\mathbf{w}\right\|_{1}$ as suggested by [29, 30].

C1 and C2 contain additional control variables $\mathbf{e}_{m}$ and
$\mathbf{e}_{s}$ to express robustness constraints. They can be simplified by
considering the worst case scenarios. Specifically, by using the Cauchy-
Schwarz inequality and the triangle inequality, we can find the minimum of
main-lobe response and the maximum of sidelobe response respectively as
follows

$\displaystyle\begin{array}[]{r@{}l}\left|\mathbf{w}^{H}(\mathbf{a}(\phi_{m};R)+\mathbf{e}_{m})\right|^{2}\\!\\!=&\left|\mathbf{w}^{H}\mathbf{a}(\phi_{m};R)+\mathbf{w}^{H}\mathbf{e}_{m}\right|^{2}\\\
\geq&(|\mathbf{w}^{H}\mathbf{a}(\phi_{m};R)|-\left|\mathbf{w}^{H}\mathbf{e}_{m}\right|)^{2}\\\
\geq&(|\mathbf{w}^{H}\mathbf{a}(\phi_{m};R)|-\left\|\mathbf{w}\right\|_{2}\left\|\mathbf{e}_{m}\right\|_{2})^{2}\\\
\geq&(|\mathbf{w}^{H}\mathbf{a}(\phi_{m};R)|-1\cdot\Delta_{R})^{2},\end{array}$
(26)
$\displaystyle\begin{array}[]{r@{}l}\left|\mathbf{w}^{H}(\mathbf{a}(\phi_{s};R)+\mathbf{e}_{s})\right|^{2}\\!\\!=&\left|\mathbf{w}^{H}\mathbf{a}(\phi_{s};R)+\mathbf{w}^{H}\mathbf{e}_{s}\right|^{2}\\\
\leq&(|\mathbf{w}^{H}\mathbf{a}(\phi_{s};R)|+\left|\mathbf{w}^{H}\mathbf{e}_{s}\right|)^{2}\\\
\leq&(|\mathbf{w}^{H}\mathbf{a}(\phi_{s};R)|+\left\|\mathbf{w}\right\|_{2}\left\|\mathbf{e}_{s}\right\|_{2})^{2}\\\
\leq&(|\mathbf{w}^{H}\mathbf{a}(\phi_{s};R)|+1\cdot\Delta_{R})^{2}.\end{array}$
(31)

The equalities hold when $\mathbf{e}=a\cdot\mathbf{a}(\phi;R)$
($a\in\mathbb{R}$). Substituting (26) and (31) into C1 and C2, we obtain the
worst-case constraints as

$\displaystyle(|\mathbf{w}^{H}\mathbf{a}(\phi_{m};R)|-\Delta_{R})^{2}\\!\\!$
$\displaystyle\geq$ $\displaystyle\\!\\!U$ (32)
$\displaystyle(|\mathbf{w}^{H}\mathbf{a}(\phi_{s};R)|+\Delta_{R})^{2}\\!\\!$
$\displaystyle\leq$ $\displaystyle\\!\\!\eta U,s=1,2,\ldots,S$ (33)

Taking the square root of both sides of (32) and (33), and re-arranging items
in the inequalities, we have

$C1:(U^{{}^{\prime}}+\Delta_{R})^{2}-\mathbf{w}^{H}\mathbf{a}(\phi_{m};R)\mathbf{a}^{H}(\phi_{m};R)\mathbf{w}\leq
0,$ (34) $\displaystyle
C2:\mathbf{w}^{H}\mathbf{a}(\phi_{s};R)\mathbf{a}^{H}(\phi_{s};R)\mathbf{w}-(\sqrt{\eta}U^{{}^{\prime}}-\Delta_{R})^{2}\leq
0,$ $\displaystyle s=1,2,\ldots,S,$ (35)

where $U^{{}^{\prime}}=\sqrt{U}$. $C3$ in (21) can be replaced by two
inequality constraints as

$C3:\left\|\mathbf{w}\right\|_{2}^{2}-1\leq 0,$ (36)
$C4:1-\left\|\mathbf{w}\right\|_{2}^{2}\leq 0,$ (37)

and $C4$ is replaced by

$C5:U^{{}^{\prime}}\geq U_{\min}^{{}^{\prime}},$ (38)

where $U_{\min}^{{}^{\prime}}=\sqrt{U_{\min}}$. The optimization problem is
thus transformed to

$\min_{\mathbf{w},U^{{}^{\prime}}}\left\|\mathbf{w}\right\|_{1}$
$s.t.\\!\\!\left\\{\\!\\!\\!\\!\begin{array}[]{l}C1\\!:\\!(U^{{}^{\prime}}+\Delta_{R})^{2}-\mathbf{w}^{H}\mathbf{a}(\phi_{m};R)\mathbf{a}^{H}(\phi_{m};R)\mathbf{w}\leq
0,\\\
C2\\!:\\!\mathbf{w}^{H}\mathbf{a}(\phi_{s};R)\mathbf{a}^{H}(\phi_{s};R)\mathbf{w}-(\sqrt{\eta}U^{{}^{\prime}}-\Delta_{R})^{2}\leq
0,\\\ \hfill s=1,2,\ldots,S,\\\
C3\\!:\\!\left\|\mathbf{w}\right\|_{2}^{2}-1\leq 0,\\\
C4\\!:\\!1-\left\|\mathbf{w}\right\|_{2}^{2}\leq 0,\\\
C5\\!:\\!U^{{}^{\prime}}\geq U_{\min}^{{}^{\prime}}.\\\
\end{array}\right.\\!\\!\\!\\!$ (39)

###  III-B FPP-SCA-based Algorithm

The reformulated problem (39) is still non-convex which is hard to be solved
directly, and it is also tricky to find feasible initial solutions, but it is
now amenable to the convex approximation technique. Inspired by the idea of
FPP [21], we introduce three slack variables $b$, $b_{1}$, $b_{2}$
($b,b_{1},b_{2}>0$) for C1–C4, and we construct the following slacked
surrogate problem of (39)

$\min_{\mathbf{w},U^{{}^{\prime}},b,b_{1},b_{2}}{\left\|\mathbf{w}\right\|_{1}+\lambda_{b}\left(b+b_{1}+b_{2}\right)}$
$s.t.\\!\\!\left\\{\\!\\!\\!\\!\begin{array}[]{l}C1\\!:\\!(U^{{}^{\prime}}+\Delta_{R})^{2}-\mathbf{w}^{H}\mathbf{a}(\phi_{m};R)\mathbf{a}^{H}(\phi_{m};R)\mathbf{w-}b_{1}\leq
0,\\\
C2\\!\\!:\\!\\!\mathbf{w}^{H}\mathbf{a}(\phi_{s};R)\mathbf{a}^{H}(\phi_{s};R)\mathbf{w}-(\sqrt{\eta}U^{{}^{\prime}}-\Delta_{R})^{2}-b_{2}\leq
0,\\\ \hfill s=1,2,\ldots,S,\\\
C3\\!:\\!\left\|\mathbf{w}\right\|_{2}^{2}-1-b\leq 0,\\\
C4\\!:\\!1-b-\left\|\mathbf{w}\right\|_{2}^{2}\leq 0,\\\
C5\\!:\\!U^{{}^{\prime}}\geq U_{\min}^{{}^{\prime}},\end{array}\right.$ (40)

where $\lambda_{b}$ ($\lambda_{b}>0$) is a pre-set coefficient to penalize
constraint violations.

To handle the non-convex terms in above constraints, i.e.,
$-\mathbf{w}^{H}\mathbf{a}\left(\phi_{m};R\right)\mathbf{a}^{H}\left(\phi_{m};R\right)\mathbf{w}$
in $C1$, $-(\sqrt{\eta}U^{{}^{\prime}}-\Delta_{R})^{2}$ in $C2$ and
$-\left\|\mathbf{w}\right\|_{2}^{2}$ in $C4$, we next apply SCA [22]. SCA is
an iterative method and its core idea is to replace non-convex terms with
convex approximations (usually upper bounds of these non-convex terms) in each
iteration. In our case, given $\\{\mathbf{w}_{(i)},U_{(i)}^{{}^{\prime}}\\}$
after the $i$-th iteration, the convex upper bounds of the three non-convex
terms are derived by applying their respective first-order Taylor expansions
as

$\begin{array}[]{r@{}l}&-\mathbf{w}^{H}\mathbf{a}\left(\phi_{m};R\right)\mathbf{a}^{H}\left(\phi_{m};R\right)\mathbf{w}\\\
\leq&-\mathbf{w}_{(i)}^{H}\mathbf{a}\left(\phi_{m};R\right)\mathbf{a}^{H}\left(\phi_{m};R\right)\mathbf{w}_{(i)}\\\
&-2\text{Re}\\{\mathbf{w}_{(i)}^{H}\mathbf{a}\left(\phi_{m};R\right)\mathbf{a}^{H}\left(\phi_{m};R\right)\left(\mathbf{w}-\mathbf{w}_{(i)}\right)\\}\\\
=&\mathbf{w}_{(i)}^{H}\mathbf{a}\left(\phi_{m};R\right)\mathbf{a}^{H}\left(\phi_{m};R\right)\mathbf{w}_{(i)}\\\
&-2\text{Re}\\{\mathbf{w}_{(i)}^{H}\mathbf{a}\left(\phi_{m};R\right)\mathbf{a}^{H}\left(\phi_{m};R\right)\mathbf{w}\\},\end{array}$
(41) $\begin{array}[]{r@{}l}&-(\sqrt{\eta}U^{{}^{\prime}}-\Delta_{R})^{2}\\\
\leq&-(\sqrt{\eta}U_{(i)}^{{}^{\prime}}-\Delta_{R})^{2}-2(\eta
U_{(i)}^{{}^{\prime}}-\sqrt{\eta}\Delta_{R})(U^{{}^{\prime}}-U_{(i)}^{{}^{\prime}})\\\
=&2(\sqrt{\eta}\Delta_{R}-\eta
U_{(i)}^{{}^{\prime}})U^{{}^{\prime}}+\eta{U_{(i)}^{{}^{\prime}2}}-\Delta_{R}^{2},\end{array}$
(42)
$\displaystyle\begin{array}[]{r@{}l}-\left\|\mathbf{w}\right\|_{2}^{2}&\leq-\left\|\mathbf{w}_{(i)}\right\|_{2}^{2}-2Re\\{\mathbf{w}_{(i)}^{H}\left(\mathbf{w}-\mathbf{w}_{(i)}\right)\\}\\\
&=\left\|\mathbf{w}_{(i)}\right\|_{2}^{2}-2Re\\{\mathbf{w}_{(i)}^{H}\mathbf{w}\\}.\end{array}$
(45)

Replacing the non-convex terms in C1, C2 and C4 with the convex upper bounds
in (41)–(45), we finally transform (21) to a convex sub-problem in (46).

$\min_{\mathbf{w},U^{{}^{\prime}},b,b_{1},b_{2}}{\left\|\mathbf{w}\right\|_{1}+\lambda_{b}\left(b+b_{1}+b_{2}\right)}$
$s.t.\
\left\\{\begin{array}[]{l}C1:(U^{{}^{\prime}}+\Delta_{R})^{2}+\mathbf{w}_{(i)}^{H}\mathbf{a}\left(\phi_{m};R\right)\mathbf{a}^{H}\left(\phi_{m};R\right)\mathbf{w}_{(i)}-2\text{Re}\\{\mathbf{w}_{(i)}^{H}\mathbf{a}\left(\phi_{m};R\right)\mathbf{a}^{H}\left(\phi_{m};R\right)\mathbf{w}\\}-b_{1}\leq
0,\\\
C2:\mathbf{w}^{H}\mathbf{a}\left(\phi_{s};R\right)\mathbf{a}^{H}\left(\phi_{s};R\right)\mathbf{w}+2(\sqrt{\eta}\Delta_{R}-\eta
U_{(i)}^{{}^{\prime}})U^{{}^{\prime}}+\eta{U_{(i)}^{{}^{\prime}}}^{2}-\Delta_{R}^{2}-b_{2}\leq
0,\ \ s=1,2,\ldots,S,\\\ C3:\left\|\mathbf{w}\right\|_{2}^{2}-1-b\leq 0,\\\
C4:1-b+\left\|\mathbf{w}_{(i)}\right\|_{2}^{2}-2\text{Re}\\{\mathbf{w}_{(i)}^{H}\mathbf{w}\\}\leq
0,\\\ C5:U^{{}^{\prime}}\geq U_{\min}^{{}^{\prime}}.\\\ \end{array}\right.$
(46)

Repeatedly solving (46) with the values from the previous iteration until the
number of iterations reaches a pre-set value $ITER$. Let
$J^{(i)}=\left\|\mathbf{(w)}_{i}^{\star}\right\|_{1}+\lambda_{b}(b^{(i)}+b_{1}^{(i)}+b_{2}^{(i)})$
be the value of the objective function after the $i$-th iteration,
$\mathbf{R}$ be a vector of target range bins of concern,
${\Delta}_{\mathbf{R}}$ be a vector of the maximum $l^{2}$-norm of
$\mathbf{e}$ for all range bins. Algorithm 1 and 2 summarize the proposed
approaches to determine the sparse weight vector for each range bin and to
apply the resulting weight vector for SAR imaging, respectively.

Algorithm 1 Computing sparse weight vectors

Input $\mathbf{R}$, $\Delta_{\mathbf{R}}$, $\phi_{MW}$, $\eta$, $\lambda_{b}$,
$N$, $J$, $\mathbf{w}_{(0)}$, $U_{(0)}^{{}^{\prime}}$;

${W}^{\star}\leftarrow\varnothing$; $i\leftarrow 0$;

for each $R$, $\Delta_{R}$ in $\mathbf{R}$, $\Delta_{\mathbf{R}}$ do

Calculate $\phi_{v}$, $\phi_{\Delta}$, $N_{\min}$, $N_{\max}$,
$a\left(\phi_{m};R\right)$, $a\left(\phi_{s};R\right)$

repeat

$i\leftarrow i+1$;

Compute $\mathbf{w}_{(i)}$, $U_{(i)}^{{}^{\prime}}$ by solving (46) with
$\mathbf{w}_{(i-1)}$, $U_{(i-1)}^{{}^{\prime}}$;

until $i>ITER$

Save $\mathbf{w}_{(i)}$ to the set ${W}^{\star}$;

end for

Output ${W}^{\star}$.

Algorithm 2 The proposed approach for ROSAR imaging

Input $\mathbf{Y}_{\text{IF}}$, $R_{t}$, $\phi_{t}$;

Compute the index of range bin, i.e., $\mathcal{I}_{R_{t}}$, for $R_{t}$;

Compute the central index of the phase center
$\mathcal{I}_{\phi_{t}}\leftarrow round(\phi_{t}/\phi_{\Delta})$;

$\mathbf{w}^{\star}\leftarrow{W}^{\star}\left(\mathcal{I}_{R_{t}}\right)$111${W}^{\star}(i)$
represents the $i$-th vector in the ordered set ${W}^{\star}$.;

$\mathbf{Y}_{\text{IF}}^{{}^{\prime}}\leftarrow\mathbf{Y}_{\text{IF}}(:,\mathcal{I}_{\phi_{t}}-\left(|\mathbf{w}^{\star}|-1\right)/{2}:\mathcal{I}_{\phi_{t}}+\left(|\mathbf{w}^{\star}|-1\right)/{2})$;

Output $I(\phi_{t},R_{t})\leftarrow\mathbf{1}^{T}\cdot(\mathbf{w}^{\star
H}\circ(\mathbf{W}_{\text{SA}}\odot\mathbf{Y}_{\text{IF}}^{{}^{\prime}}))\cdot\mathbf{1}$.

###  III-C Initial values and parameter settings for Algorithms 1 and 2

####  III-C1 Initial Value Settings

The proposed approach is able to work with any initial values of the control
variables since the constraints are always feasible due to the introduced
slack variables. In our implementation, the initial value of $\mathbf{w}$ is
chosen as $\mathbf{w}_{(0)}=\frac{1}{\sqrt{N_{\max}-N_{\min}+1}}\mathbf{1}$
and $U_{(0)}^{{}^{\prime}}=|\mathbf{w}_{(0)}^{H}\mathbf{a}(\phi;R)|^{2}$.

####  III-C2 Parameter Settings

To ensure convergence, $ITER$ and $Th$ can be set to around $50\sim 100$ and
$10^{-4}\sim 10^{-3}$, respectively. $\phi_{\text{MW}}$ and $\eta$ are design
parameters of the sparse array. We found that any value lower than both
$\phi_{\text{MW}}=1\degree$ and $\eta=-33dB$ makes the SCA diverge.
$\Delta_{R}$ should be chosen by considering practical limitations of target
platforms. For example, in Section IV-A, the simulation setup and experiments
take the unstable rotation speed of a ROSAR platform into account. The
direction of each phase center under unstable rotations is modeled as a
Gaussian distribution

${\widehat{\phi}}_{n}\sim\mathcal{N}\left(\frac{2\pi n}{N},\sigma\right),$
(47)

where the $\sigma$ is the standard deviation of the direction. The error
vector is computed from $\mathbf{e}=\widehat{\mathbf{a}}(\phi;\
R)-\mathbf{a}(\phi;\ R)$, where $\widehat{\mathbf{a}}(\phi;R)$ is determined
by substituting $\phi_{n}$ with ${\widehat{\phi}}_{n}$. Let
${\widehat{\Delta}}_{R}=\left\|\mathbf{e}\right\|$. By repeatedly sampling
from (47), we can obtain the cumulative distribution function (CDF) of
${\widehat{\Delta}}_{R}$, and choose the ${\widehat{\Delta}}_{R}$
corresponding to 99% of the cumulative probability as $\Delta_{R}$. The
testbed evaluations in Section IV-F show that this model is reasonable in
realistic settings. Note since the phase error $\mathbf{e}$ differs among
range bins, one specific $\Delta_{R}$ must be pre-computed for each range bin.

To ensure accurate results, the angle interval should be less than or equal to
the angular resolution of ROSAR. However, reducing the angle interval
increases the number of grid points and leads to higher computation costs.
Since there is no closed-form solution to the angular resolution of a circular
array, we use the results of a linear array as a reference. The determination
of $U_{\min}$ is based on the expected image quality in target applications.
It should be large enough to guarantee a sufficient gain for all range bins.
Otherwise, there could be light and dark strips on the generated SAR image.

Increasing $\lambda_{b}$ improves the sparsity of $\mathbf{w}$ but when
$\lambda_{b}$ is too large, (36) is no longer feasible. As a general rule of
thumb, $\lambda_{b}$ should be several times larger than the maximum of
$\left\|\mathbf{w}\right\|_{1}$ to ensure that the slack variables converge to
zero. Since the $l^{1}$-norm differs $l^{0}$-norm and cannot enforce sparsity
in itself, we must manually set any term in $\mathbf{w}^{\star}$ lower than a
pre-defined threshold to 0. Thus, in Algorithm 2, only the nonzero entries in
$\mathbf{w}^{\star}$ are included in computing $\mathbf{w}^{\star
H}\circ\mathbf{W}_{\text{SA}}\odot\mathbf{Y}_{\text{IF}}^{{}^{\prime}}$.
Moreover, a final step must be taken to verify the solution. This can be
accomplished by checking if the slack variables are sufficiently small, i.e.,
$b+b_{1}+b_{2}<b_{\text{min}}$ and $b_{\text{min}}$ is set to ${10}^{-5}$ in
the experiments.

###  III-D Complexity Reduction for Real-implementation

Since applying range compression along fast time samples[31] (denoted as
“FFT+BPA”) can reduce the processing time of conventional BPA, we borrow its
idea to further reduce the complexity of the proposed SAS approach (denoted as
“FFT+SAS”). Ignoring the noise term in (10) and applying range-FFT to
$\mathbf{y}_{\text{IF},n}$, we have

$\displaystyle Y_{\text{1D},n}(l)\\!\\!\\!\\!\\!\\!$ $\displaystyle=$
$\displaystyle\\!\\!\\!\\!\\!\\!\sum_{m=0}^{M-1}{y_{\text{IF},n}(m)e^{-j2\pi\frac{l}{L}m}}$
(48) $\displaystyle=$
$\displaystyle\\!\\!\\!\\!\\!\\!\alpha_{n}e^{j2\pi\left(\tau
KT_{Start}+f_{c}\tau\right)}\\!\\!\\!\sum_{m=0}^{M-1}e^{j2\pi\left(\tau
Kt_{s}-\frac{l}{L}\right)m}$ $\displaystyle=$
$\displaystyle\\!\\!\\!\\!\\!\\!\alpha_{n}e^{j4\pi\frac{KT_{Start}+f_{c}}{c}R_{n}}\\!\\!\\!\sum_{m=0}^{M-1}e^{j2\pi\left(\frac{2R_{n}Kt_{s}}{c}-\frac{l}{L}\right)m},$

where $l=0,1,\ldots,L-1$ and $L$ is the number of range bins. Let
$k=\frac{2\pi\left(KT_{\text{Start}}+f_{c}\right)}{c}$. We have

$Y_{\text{1D},n}(l)=\alpha_{n}e^{j2kR_{n}}\sum_{m=0}^{M-1}e^{j2\pi\left(\frac{2R_{n}Kt_{s}}{c}-\frac{l}{L}\right)m},$
(49)

and $Y_{\text{1D},n}(l)$ reaches the maximum for

$l_{n}^{\star}=round\left(\frac{2R_{n}Kt_{s}L}{c}\right),$ (50)

which is the range bin where the target is located. The data vector at the
$n$-th phase center now becomes

$\mathbf{y}_{\text{1D},n}=\left[Y_{\text{1D},n}(0),Y_{\text{1D},n}(1)\ldots,Y_{\text{1D},n}(L-1)\right]^{T}.$
(51)

The data matrix from effective phase centers used for SAR is given by

$\mathbf{Y}_{\text{1D}}=\left[\mathbf{y}_{\text{1D},N_{\min}},\mathbf{y}_{\text{1D},N_{\min}+1},\ldots,\mathbf{y}_{\text{1D},N_{\max}}\right].$
(52)

To focus a point locating at $\left(\phi_{t},R_{t}\right)$ in polar
coordinates, we need to compute

$I(\phi_{t},R_{t})={\mathbf{w}^{H}\cdot\mathbf{Y}_{\text{1D}}(l_{N_{\min}}^{\star},l_{N_{\min}+1}^{\star},\ldots,l_{N_{\max}}^{\star})},$
(53)

where
$\mathbf{Y}_{\text{1D}}(l_{N_{\min}}^{\star},l_{N_{\min}+1}^{\star},l_{N_{\min}+2}^{\star},\ldots,l_{N_{\max}}^{\star})=[\mathbf{y}_{\text{1D},N_{\min}}(l_{N_{\min}}^{\star}),\mathbf{y}_{\text{1D},N_{\min}+1}(l_{N_{\min}+1}^{\star}),\ldots,\mathbf{y}_{\text{1D},N_{\max}}(l_{N_{\max}}^{\star})]^{T}$
and $\mathbf{y}_{\text{1D},n}(l)$ represents the $l$-th entry of the vector
$\mathbf{y}_{\text{1D},n}$. $\mathbf{w}$ in (53) can be the sparse weight
vector of the corresponding range bin determined by Algorithm 2, or the weight
vector of BPA with the $j$-th entry being
$\mathbf{w}_{\text{BP},j}=\alpha_{N_{\min}+j-1}\cdot
e^{-j2kR_{N_{\min}+j-1}}$.

###### Remark 1

The steering vector may differ from the origin one in (16) after applying
range-FFT, since substituting (50) into (49) cannot fully cancel the phase
summation term in some cases (e.g., when $R_{n}$ is not multiple of the length
of range bin). In our implementation, $\mathbf{w}^{\star}$ is still obtained
from the original steering vector. Thus, the array pattern could deviate from
the desired one. However, doing so can lead to computation reduction.

###### Remark 2

The computation complexity of SAS is $O(L_{x}\times L_{y}\times M\times
N^{\prime})$, where $N^{\prime}$ is number of phased centers corresponding to
non-zero weights. $N^{\prime}$ is typically less than a half of $N$. As for
FFT+SAS, the computation complexity is given by $O(N^{\prime}\times
M\log_{2}M+L_{x}\times L_{y}\times N^{\prime})$. When $L_{x}\times L_{y}\gg
M$, the second term dominates. Thus, the overall reduction in complexity by
combining FFT and SAS is substantial compared with that of the conventional
BPA algorithm. Since the proposed algorithms conduct filtering pixel-by-pixel
independently, they can be further accelerated by separating these pixels into
multiple groups and processing them in a parallel manner.

##  IV Performance

In this section, we conduct experimental study to evaluate the effectiveness
of the proposed ROSAR imaging algorithms.

###  IV-A Hardware and Software Implementation

We implement the proposed algorithms on a PC equipped with an Intel Core 8700
CPU and 16GB RAM. The PC has been installed MATLAB and Phased Array Toolbox.
We also build a real ROSAR system, which hardware consists of a radar board, a
rotation plate, motor and odometry sensors mounted on a rover platform as
shown in Fig. 2. The radar uses is Taxes Instruments IWR6843ISK, which
generates millimeter wave (mmWave) signals. A 3D-printed plate holding the
radar and counter weight is connected to a step motor and a wheel encoder.

The whole system is controlled by Robot Operating System (ROS), including the
radar signal sending/receiving and rotation speed. Radar data is collected
from the antenna board and angle reading is obtained from the encoder of the
rotation platform. Both data is streamed to the PC and processed by MATLAB
programs for SAR imaging.

Figure 2: ROSAR system

To estimate phase center errors from wheel encoder, we mount several optical
markers on the rotation plate. Markers can be tracked by OptiTrack, an optical
motion capture system treated as ground truth (position accuracy: 0.2 mm). We
rotate the platform multiple rounds and compare the angle difference between
the data from tick’s encoder and the OptiTrack system. Fig. 3 shows the mean
value is $3.9\times{10}^{-4}$ degree. If the data is fitted by a Gaussian
distribution, the standard deviation is $\sigma=0.086$. Thus, we can assume
the direction of the $n$-th phase center follows
${\widehat{\phi}}_{n}\sim\mathcal{N}\left(\frac{2\pi n}{N},0.086\right)$.

Figure 3: Direction deviation of phase centers

###  IV-B Parameter Settings

The detailed parameters of the ROSAR system are summarized in Table II. From
the settings, the range resolution is given by
$R_{\Delta}=\frac{c}{2B}=0.0435m$, where $B$ is the bandwidth of the sampled
chirp signal. The maximum unambiguous range is
$R_{\max}=\frac{cF_{s}}{4K}\approx 4.8686m$. If we choose $\Delta_{R}$ to
represent 99% of the probability of the cumulative distribution function
(CDF), Fig. 4(a) shows an example CDF for $R=2$ and $\Delta_{R}=0.035$. Fig.
4(b) shows $\Delta_{R}$ as a function of range, from which we can see
${\Delta}_{R}$ decreases as the range becomes larger. It is because a small
displacement from the desirable positions of phase centers has less impact
when the radar is further away from the target. The detailed calculation steps
have been given in Section III-C2.

(a) The CDF of $\widehat{\Delta}_{R}$ ($R=2$)

(b) ${\Delta}_{R}$ for all range bins

Figure 4: ${\Delta}_{R}$ calculation TABLE II: Parameters of the ROSAR System
Radar Settings
---
$r$ | 0.145 m
Rotation speed | 60 RPM
Rotation time | 1 s
# Of TX | 1
# Of RX | 1
Antenna Pattern | Cosine
Antenna FOV | [-90°, 90°]
Start rotating direction | 0°
Rotation direction | Counter-clockwise
TX power | 12 dBm
Antenna gain | 7 dBi
RX gain | 48 dB
Chirp Signal Settings
Start Frequency | 60 GHz
End Frequency | 64 GHz
Ramp start time | 0 us
Ramp end time | 58 us
$T_{Start}$ | 7 us
Sampling end time | 57 us
$F_{s}$ | 4.5 MHz
$M$ | 225
$N$ | 800
$K$ |  $6.8\times 10^{13}$ Hz/s
$L$ | 225

All the sparse weight vector $\mathbf{w}$ for each range bin are computed in
advance using Algorithm 1 with parameters listed in Table III. We use CVX and
Mosek solver[32] to find the optimal values in each iteration of SCA.

TABLE III: SAS Parameters $ITER$ | 50
---|---
$Th$ | 0.001
$\phi_{\text{MW}}$ | 1°
Sampled angle interval | 0.5°
$\lambda_{b}$ | 50
$\eta$ | 0.0005 (-33 dB)
$U_{\min}$ | 5

###  IV-C Baseline Algorithm and Metrics

We implement four algorithms: “BPA”, “FFT+BPA”, “SAS”, “FFT+SAS”, “RBPA” (BPA
with randomly selected phase centers) and “FFT+RBPA” for different comparison
purposes. The following metrics are used in quantitative evaluations:

  * •

Half main lobe width $\phi_{\text{MW}}$: The half main lobe width is defined
as the angle interval between the peak and the closest local minima on either
side of the main lobe.

  * •

Peak-to-integral sidelobe ratio (PISR): The PISR $\mathcal{R}$ for a specific
range bin $R$ is calculated as

$\mathcal{R}=\frac{\left|I\left(\phi_{m},R\right)\right|^{2}}{\sum_{s=1}^{S}\left|I\left(\phi_{s},R\right)\right|^{2}}.$
(54)

  * •

SAR computation cost: The elapsed time of generating a SAR image.

  * •

Image entropy [33]: Let $E=\sum_{\phi}{\sum_{R}\left|I(\phi,R)\right|^{2}}$ be
the total energy of the image, and
$d_{(\phi,R)}=\frac{\left|I(\phi,R)\right|^{2}}{\
E=\sum_{\phi}{\sum_{R}\left|I(\phi,R)\right|^{2}}}$ be the energy density of a
pixel. The image entropy is defined as

$E_{I}=-\sum_{\phi,R}{d_{(\phi,R)}\ln d_{(\phi,R)}}.$ (55)

The targets are well focused on the SAR image if $\mathcal{R}$ is large and
$E_{I}$ is small.

###  IV-D Numerical Results and Analysis

####  IV-D1 Solution to the Optimization Problem

We first give the numerical result through imaging a point target locating at
$\left(\frac{\pi}{2},2m\right)$. In this case, the number of effective phase
centers, i.e., the length of synthesized aperture, is calculated to be 381 by
(5). Fig. 5 shows the magnitude of each element in $\mathbf{w}^{\star}$ out
and robust design, respectively. In both cases, we can see
$\left\|\mathbf{w}\right\|_{0}$ is less than a half of the total number of
phase centers from Table IV. However, the robust design, the sparsity is
slightly reduced.

(a) Non-robust design

(b) Robust design

Figure 5: The magnitude of each element in $\mathbf{w}^{*}$ under different scenarios TABLE IV: Solution to the Optimization Problem | $\left\|\mathbf{w}\right\|_{0}$ | $U^{\prime}$
---|---|---
Non-Robust ($\Delta_{R}=0$) | 141 | 8.21
Robust ($\Delta_{R}=0.035$) | 157 | 8.38

####  IV-D2 Array Pattern

Fig. 6 shows the array patterns of the SAS out and considering robust design
for $R=2$. Fig. 6(b) and Fig. 6(d) are the main lobe area of Fig. 6(a) and
6(c). The array pattern is calculated by $F(\phi;2)={\mathbf{w}^{\star
H}}\mathbf{a}(\phi;2)$ for
$\phi=\left[\frac{\pi}{2}-\phi_{v},\frac{\pi}{2}+\phi_{v}\right]$. The blue
and red lines show the array pattern out and adding phase errors $\mathbf{e}$,
respectively. The yellow line is the array pattern of BPA phase errors. As we
can see, the main lobe is in $[-1{{}^{\circ}},1{{}^{\circ}}]$, which meets the
design parameters. As shown in Fig. 6(a), the power of the sidelobes when
there is no error $\mathbf{e}$ in the steering vector is mostly -33dB lower
than that of the main lobe peak. The few exceptions fall in between angle grid
points of interval 0.5° and thus their power levels are not enforced by the
constraints. Although denser grid points (and consequently more constraints)
can reduce the chance of requirement violation, the computation cost of SCA
grows drastically. When there are errors in the steering vector, most of the
sidelobes do not meet the -33dB criteria in non-robust design. In contrast,
the robust design (the red line in Fig. 6(c)), this is no longer the case.
Furthermore, the average power of the sidelobes is lower than -33dB robust
design even in absence of steering vector errors. This is due to the worst
case assumption of robustness design as evident in (34) and (35). The PISRs
are given in Table V. High values are better. The conventional BPA gives the
best PISR due to its low sidelobes but needs much more computation time.

(a) Non-robust design

(b) Main lobe region of (a)

(c) Robust design

(d) Main lobe region of (c)

Figure 6: The Array Pattern in Different Scenarios TABLE V: Peak-to-Integral Sidelobe Ratio Algorithms & Settings | w/o error | w. error
---|---|---
SAS w. Robust | 0.1256 | 0.1253
SAS w/o robust | 0.1308 | 0.1303
BPA w. error | N/A | 0.2339

####  IV-D3 Results for All Range Bins

Fig. 7 shows the values of $\left\|\mathbf{w}\right\|_{0}$ and $U^{\prime}$
for all range bins when $U_{\text{min}}=0$. Clearly, the sparsity of the array
holds in all range bins. We observe that all $U^{\prime}$s are small. In this
case, although the array is very sparse, the SNR is low (recall that
$U^{\prime}$ is the magnitude of main-lobe peak and the noise power is
constant from C3). Setting $U_{\text{min}}=5$ can bound the SNR at the cost of
reduced sparsity as shown in Fig. 8.

(a) $\left\|\mathbf{w}\right\|_{0}$

(b) $U^{\prime}$

Figure 7: The solutions of the SCA $U_{\min}=0$ for different range bins

(a) $\left\|\mathbf{w}\right\|_{0}$

(b) $U^{\prime}$

Figure 8: The solutions of the SCA $U_{\min}=5$ for different range bins

###  IV-E SAR Imaging Simulation for a Point Target

By using MATLAB Phased Array Toolbox, we simulated a point target locating at
$\left(\frac{\pi}{2},2m\right)$, a rotating radar and the sending/receiving
signals of radar antennas. Fig. 9(a), 9(c) and 9(e) show the imaging results
of the target area by conventional BPA, SAS and RBPA, while Fig. 9(b), 9(d)
and 9(f) show the SAR images by employing FFT acceleration. The SAR image
quality and computation cost is summarized in Table VI. Although the entropy
of the SAR image generated by SAS is slightly worse than that by BPA, the
computational time is significantly reduced. Furthermore, although BPA with
randomly selected phase centers takes less time as well, the resulting image
quality is much worse than others.

(a) BPA

(b) FFT + BPA

(c) SAS

(d) FFT + SAS

(e) RBPA

(f) FFT + RBPA

Figure 9: The SAR Image (Contour) of a point at $\left(\frac{\pi}{2},2m\right)$ TABLE VI: SAR image quality and time cost Algorithm | $E_{I}$ | Time Cost (s)
---|---|---
BPA | 3.7489 | 43.66
FFT + BPA | 3.9812 | 29.43
SAS | 4.4073 | 18.03
FFT + SAS | 4.4703 | 3.61
RBPA | 5.7850 | 18.03
FFT + RBPA | 5.8728 | 5.86

###  IV-F Testbed Evaluation

Although simulations can provide insights on the impacts of configuration
parameters and the performance of the proposed approach in simulated
environments, existing packages in MATLAB cannot model the reflection,
diffusion and deflection properties of mmWave signals in indoor environments
well. In this section, the performance and efficiency of the proposed approach
is validated through two real-world experiments. The size of SAR area is set
to be 9.8756m$\times$9.8756m with grid size being 0.04m$\times$0.04m.

####  IV-F1 Scenario 1: Corner Reflector

We put a radar platform (red dot) and a corner reflector (blue dot) in a lab
(see Fig. 10). In addition to a corner reflector which can be treated as the
point target with strong reflection in practice, there are also computer
desks, wood cabinet, metal cases and other equipment in the environment. Fig.
11, 12 and 13 illustrate the SAR images under different algorithms and
settings. The numerical results are summarized in Table VII. It can be
observed from the figures, BPA gives the clearest image among all approaches.
The inclusion of robust design can improve sharpness of the image. At
$\phi_{\text{MW}}=1\degree$ and $\eta=-33$dB, the image entropy from SAS is
comparable to that of the BPA but takes only one fifth of the total
computation time. Range-FFT can work in conjunction with both BPA and SAS.
When comparing all these figures, we find that range-dimension match filtering
degrades image sharpness slightly. This is also corroborated by the image
entropy results in Table VII. Among all approaches, “FFT+SAS” incurs the least
amount of compute time – close to 13 times faster than BPA while achieving
acceptable image quality.

(a) Geometry Relation

(b) Experimental Scenario

Figure 10: Experiment setup for imaging a corner reflector

(a) Back-projection
algorithm

(b) SAS, $\phi_{\text{MW}}\\!\\!=\\!\\!1\degree$,$\eta\\!\\!=\\!\\!-30$dB,w/o
Robust

(c) SAS, $\phi_{\text{MW}}=1\degree$, $\eta=-30$dB, Robust

(d) SAS, $\phi_{\text{MW}}=1\degree$, $\eta=-33$dB, Robust

Figure 11: SAR Images of a corner reflector (BPA and SAS)

(a) FFT + Back-projection
algorithm

(b) FFT + SAS,
$\phi_{\text{MW}}\\!\\!=\\!\\!1\degree$,$\eta\\!\\!=\\!\\!-30$dB,w/o Robust

(c) FFT + SAS, $\phi_{\text{MW}}=1\degree$, $\eta=-30$dB, Robust

(d) FFT + SAS, $\phi_{\text{MW}}=1\degree$, $\eta=-33$dB, Robust

Figure 12: SAR images of a corner reflector (FFT + BPA and FFT + SAS)

(a) RBPA

(b) FFT + RBPA

Figure 13: SAR images of a corner reflector (RBPA and FFT + RBPA) TABLE VII: Imaging Performance with Different Approaches in Corner Reflector Case Algorithm |  Settings | $E_{I}$ |  Time Cost (s)
---|---|---|---
BPA |  N/A | 6.0472 |  151.84
FFT+BPA |  N/A | 6.3400 |  21.69
SAS |  $\phi_{\text{MW}}\\!\\!=\\!\\!1\degree$,$\eta\\!\\!=\\!\\!-30$dB,w/o Robust | 7.2607 |  28.04
|  $\phi_{\text{MW}}=1\degree$,$\eta=-30$dB,Robust | 7.1717 |  28.94
|  $\phi_{\text{MW}}=1\degree$,$\eta=-33$dB,Robust | 6.8913 |  30.56
FFT+SAS |  $\phi_{\text{MW}}\\!\\!=\\!\\!1\degree$,$\eta\\!\\!=\\!\\!-30$dB,w/o Robust | 7.3989 |  11.45
|  $\phi_{\text{MW}}=1\degree$,$\eta=-30$dB,Robust | 7.3227 |  12.14
|  $\phi_{\text{MW}}=1\degree$,$\eta=-33$dB,Robust | 7.1170 |  12.31
RBPA |  N/A | 8.3060 |  25.02
FFT+RBPA |  N/A | 8.3179 |  13.07

####  IV-F2 Scenario 2: Corridor Corner

Next we collect data from the corner of a corridor. The floor map is given in
Fig. 14, where the red dot indicates the location of the system, the blue area
corresponds to the corridor and the white space with labels represents
different rooms. Figs. 15, 16 and 17 show the SAR images from different
algorithms and parameter settings. The numerical results are summarized in
Table VIII. From the figures, one can discern the outline of the corridor
corner. Due to the penetration of mmWave signals through drywalls, the steel
bars inside the walls are visible in the figures. Additionally, an object in
the Room 128 and the contour of Room 132 are also visible. Similar to the case
with corner reflector, the consideration of robust design can indeed improve
image quality. When $\eta$ is set to -33dB and robust design, the sidelobes
are less visible. Moreover, inclusion of range-domain FFT can indeed greatly
reduce the compute time. BPA with randomly selected phase centers takes less
time, but the generated image is blurred. The proposed robust design, with
$\phi_{\text{MW}}=1\degree$ and $\eta=-33$dB, gives comparable image quality
as that of BPA and consume much less computation time.

Figure 14: Floor map of the corridor corner

(a) Back-projection
algorithm

(b) SAS, $\phi_{\text{MW}}\\!\\!=\\!\\!1\degree$,$\eta\\!\\!=\\!\\!-30$dB,w/o
Robust

(c) SAS, $\phi_{\text{MW}}=1\degree$, $\eta=-30$dB, Robust

(d) SAS, $\phi_{\text{MW}}=1\degree$, $\eta=-33$dB, Robust

Figure 15: SAR images of corridor corner (BPA and SAS)

(a) FFT + Back-projection
algorithm

(b) FFT + SAS,
$\phi_{\text{MW}}\\!\\!=\\!\\!1\degree$,$\eta\\!\\!=\\!\\!-30$dB,w/o Robust

(c) FFT + SAS, $\phi_{\text{MW}}=1\degree$, $\eta=-30$dB, Robust

(d) FFT + SAS, $\phi_{\text{MW}}=1\degree$, $\eta=-33$dB, Robust

Figure 16: SAR images of corridor corner (FFT + BPA and FFT + SAS)

(a) RBPA

(b) FFT + RBPA

Figure 17: SAR images of corridor corner (RBPA and FFT + RBPA) TABLE VIII: Imaging Performance with Different Approaches in Corridor Corner Case Algorithm |  Settings | $E_{I}$ |  Time Cost (s)
---|---|---|---
BPA |  N/A | 6.4436 |  151.22
FFT+BPA |  N/A | 6.6881 |  21.85
SAS |  $\phi_{\text{MW}}\\!\\!=\\!\\!1\degree$,$\eta\\!\\!=\\!\\!-30$dB,w/o Robust | 7.3802 |  27.75
|  $\phi_{\text{MW}}=1\degree$,$\eta=-30$dB,Robust | 7.2871 |  29.30
|  $\phi_{\text{MW}}=1\degree$,$\eta=-33$dB,Robust | 7.0251 |  30.25
FFT+SAS |  $\phi_{\text{MW}}\\!\\!=\\!\\!1\degree$,$\eta\\!\\!=\\!\\!-30$dB,w/o Robust | 7.5309 |  12.50
|  $\phi_{\text{MW}}=1\degree$,$\eta=-30$dB,Robust | 7.4562 |  12.21
|  $\phi_{\text{MW}}=1\degree$,$\eta=-33$dB,Robust | 7.2425 |  12.47
RBPA |  N/A | 8.3671 |  25.35
FFT+RBPA |  N/A | 8.3801 |  13.28

##  V Conclusion

In this paper, we propose a new fast imaging algorithm based on robust sparse
array synthesis for ROSAR. Since radar path is circular, such an algorithm
only needs to pre-compute the complex weights of the imaging filter offline
for one direction per range bin. Due to the external influence could affect
the sidelobe level, we add robust design to maintain the image quality. To
meet our pre-set expectation and solve this problem, our proposed algorithm
employs feasible point pursuit and successive convex approximation technology.
On that basis, we also give another algorithm based on range-FFT to further
reduce the computation complexity.

According to the simulation and testbed results, we conclude that our approach
can generate an SAR image with the quality comparable to that of BPA.
Meanwhile, the proposed approach is able to reduce the computational cost
significantly and is robust to the array error.

Nonetheless, we must sacrifice some image quality if employing FFT-based
range-dimensional matched filtering. Thus, exploring a better approach for the
processing based on range FFT is our future research direction.

## References

  * [1] C. Willey, “Synthetic aperture radars–a paradigm for technology evolution,” _IEEE Trans. Aerospace Elec. Sys_ , vol. 21, pp. 440–443, 1985.
  * [2] A. Moreira, J. Mittermayer, and R. Scheiber, “Extended chirp scaling algorithm for air-and spaceborne sar data processing in stripmap and scansar imaging modes,” _IEEE Transactions on geoscience and remote sensing_ , vol. 34, no. 5, pp. 1123–1136, 1996.
  * [3] H. Klausing, “Feasibility of a synthetic aperture radar with rotating antennas (rosar),” in _1989 19th European Microwave Conference_. IEEE, 1989, pp. 287–299.
  * [4] F. Ali, A. Urban, and M. Vossiek, “A short range synthetic aperture imaging radar with rotating antenna,” _International Journal of Electronics and Telecommunications_ , vol. 57, pp. 97–102, 2011.
  * [5] D. Li, H. Liu, Y. Liao, and X. Gui, “A novel helicopter-borne rotating sar imaging model and algorithm based on inverse chirp-z transform using frequency-modulated continuous wave,” _IEEE Geoscience and Remote Sensing Letters_ , vol. 12, no. 8, pp. 1625–1629, 2015.
  * [6] Y. Nan, X. Huang, and Y. J. Guo, “A panoramic synthetic aperture radar,” _IEEE Transactions on Geoscience and Remote Sensing_ , vol. 60, pp. 1–13, 2022.
  * [7] J. Zhang, G. Liao, S. Zhu, J. Xu, and F. Liu, “Wavenumber-domain autofocus algorithm for helicopter-borne rotating synthetic aperture radar,” _IET Signal Processing_ , vol. 12, no. 3, pp. 294–300, 2018.
  * [8] F. Ali, G. Bauer, and M. Vossiek, “A rotating synthetic aperture radar imaging concept for robot navigation,” _IEEE transactions on microwave theory and techniques_ , vol. 62, no. 7, pp. 1545–1553, 2014.
  * [9] I. Cumming and J. Bennett, “Digital processing of seasat sar data,” in _ICASSP’79. IEEE International Conference on Acoustics, Speech, and Signal Processing_ , vol. 4. IEEE, 1979, pp. 710–718.
  * [10] D. Zeng, T. Zeng, C. Hu, and T. Long, “Back-projection algorithm characteristic analysis in forward-looking bistatic sar,” in _2006 CIE International Conference on Radar_. IEEE, 2006, pp. 1–4.
  * [11] M. E. Yanik and M. Torlak, “Near-field mimo-sar millimeter-wave imaging with sparsely sampled aperture data,” _Ieee Access_ , vol. 7, pp. 31 801–31 819, 2019.
  * [12] R. K. Raney, H. Runge, R. Bamler, I. G. Cumming, and F. H. Wong, “Precision sar processing using chirp scaling,” _IEEE Transactions on geoscience and remote sensing_ , vol. 32, no. 4, pp. 786–799, 1994.
  * [13] R. Zhu, J. Zhou, G. Jiang, and Q. Fu, “Range migration algorithm for near-field mimo-sar imaging,” _IEEE Geoscience and Remote Sensing Letters_ , vol. 14, no. 12, pp. 2280–2284, 2017.
  * [14] L. M. Ulander, H. Hellsten, and G. Stenstrom, “Synthetic-aperture radar processing using fast factorized back-projection,” _IEEE Transactions on Aerospace and electronic systems_ , vol. 39, no. 3, pp. 760–776, 2003.
  * [15] L. Zhang, H.-l. Li, Z.-j. Qiao, and Z.-w. Xu, “A fast bp algorithm with wavenumber spectrum fusion for high-resolution spotlight sar imaging,” _IEEE Geoscience and Remote Sensing Letters_ , vol. 11, no. 9, pp. 1460–1464, 2014.
  * [16] Q. Dong, G.-C. Sun, Z. Yang, L. Guo, and M. Xing, “Cartesian factorized backprojection algorithm for high-resolution spotlight sar imaging,” _IEEE Sensors Journal_ , vol. 18, no. 3, pp. 1160–1168, 2017.
  * [17] Y. Luo, F. Zhao, N. Li, and H. Zhang, “A modified cartesian factorized back-projection algorithm for highly squint spotlight synthetic aperture radar imaging,” _IEEE Geoscience and Remote Sensing Letters_ , vol. 16, no. 6, pp. 902–906, 2018.
  * [18] H. Bi, G. Bi, B. Zhang, W. Hong, and Y. Wu, “From theory to application: Real-time sparse sar imaging,” _IEEE Transactions on Geoscience and Remote Sensing_ , vol. 58, no. 4, pp. 2928–2936, 2019.
  * [19] B. Zhang, W. Hong, and Y. Wu, “Sparse microwave imaging: Principles and applications,” _Science China Information Sciences_ , vol. 55, no. 8, pp. 1722–1754, 2012.
  * [20] C. Wen, Y. Huang, J. Peng, G. Zheng, W. Liu, and J.-K. Zhang, “Reconfigurable sparse array synthesis with phase-only control via consensus-admm-based sparse optimization,” _IEEE Transactions on Vehicular Technology_ , vol. 70, no. 7, pp. 6647–6661, 2021.
  * [21] O. Mehanna, K. Huang, B. Gopalakrishnan, A. Konar, and N. D. Sidiropoulos, “Feasible point pursuit and successive approximation of non-convex qcqps,” _IEEE Signal Processing Letters_ , vol. 22, no. 7, pp. 804–808, 2014.
  * [22] A. Beck, A. Ben-Tal, and L. Tetruashvili, “A sequential parametric convex approximation method with applications to nonconvex truss topology design problems,” _Journal of Global Optimization_ , vol. 47, no. 1, pp. 29–51, 2010.
  * [23] S. E. Nai, W. Ser, Z. L. Yu, and H. Chen, “Beampattern synthesis for linear and planar arrays with antenna selection by convex optimization,” _IEEE Transactions on Antennas and Propagation_ , vol. 58, no. 12, pp. 3923–3930, 2010\.
  * [24] B. Fuchs, “Synthesis of sparse arrays with focused or shaped beampattern via sequential convex optimizations,” _IEEE Transactions on Antennas and Propagation_ , vol. 60, no. 7, pp. 3499–3503, 2012.
  * [25] Y. Liu, Z. Nie, and Q. H. Liu, “Reducing the number of elements in a linear antenna array by the matrix pencil method,” _IEEE Transactions on Antennas and Propagation_ , vol. 56, no. 9, pp. 2955–2962, 2008.
  * [26] Y. Liu, Q. H. Liu, and Z. Nie, “Reducing the number of elements in the synthesis of shaped-beam patterns by the forward-backward matrix pencil method,” _IEEE Transactions on Antennas and Propagation_ , vol. 58, no. 2, pp. 604–608, 2009.
  * [27] W. P. Keizer, “Linear array thinning using iterative fft techniques,” _IEEE Transactions on Antennas and Propagation_ , vol. 56, no. 8, pp. 2757–2760, 2008.
  * [28] W. P. Du Plessis, “Weighted thinned linear array design with the iterative fft technique,” _IEEE transactions on antennas and propagation_ , vol. 59, no. 9, pp. 3473–3477, 2011.
  * [29] E. J. Candes, M. B. Wakin, and S. P. Boyd, “Enhancing sparsity by reweighted l1 minimization,” _Journal of Fourier analysis and applications_ , vol. 14, no. 5, pp. 877–905, 2008.
  * [30] D. L. Donoho, “Compressed sensing,” _IEEE Transactions on information theory_ , vol. 52, no. 4, pp. 1289–1306, 2006.
  * [31] M. T. Crockett and D. Long, “An introduction to synthetic aperture radar: A high-resolution alternative to optical imaging,” 2013.
  * [32] M. Grant and S. Boyd, “CVX: Matlab software for disciplined convex programming, version 2.1,” http://cvxr.com/cvx, Mar. 2014.
  * [33] G. Xu, L. Yang, L. Zhang, Y.-C. Li, and M.-D. Xing, “Weighted minimum entropy autofocus algorithm for isar imaging,” _Journal of Electronics & Information Technology_, vol. 33, no. 8, pp. 1809–1815, 2011.

Wei Zhao received his B.Eng. degree in Automation from Xidian University,
M.A.Sc. degree in Electrical & Computer Engineering from McMaster University.
He is a Ph.D. candidate in the Department of Computing and Software in
McMaster University since 2017.
---
Cai Wen (M’19) received the B.E. degree from the School of Electronic
Engineering, Xidian University, Xi’an, China, in 2009, and the Ph.D. degree
from the National Laboratory of Radar Signal Processing, Xidian University,
Xi’an, China, in 2014. He was a Research Scientist with the China NORINCO
Group from Jan. 2015 to Oct. 2016. From Nov. 2019 to Mar. 2023, he was with
the Department of Electrical and Computer Engineering, McMaster University,
Hamilton, Canada, as a Post-Doctoral Research Fellow. Since Nov. 2016 he has
been with the School of Information Science and Technology, Northwest
University, Xi’an, China, where he is currently an Associate Professor. His
current research interests include sensor array signal processing, MIMO radar
signal processing, integrated sensing and communication, and mathematical
optimization.
---
Quan Yuan received the Bachelor of Engineering degree from McMaster
University, Canada, in 2022. He is currently working towards the Master of
Engineering degree on Computing and Software under the supervision of Dr. Rong
Zheng at McMaster University, Canada.
---
Rong Zheng received the B.E. and M.E. degrees in electrical engineering from
Tsinghua University, Beijing, China, in 1996 and 1998, respectively, and the
Ph.D. degree from the Department of Computer Science, University of Illinois
at Urbana–Champaign, Champaign, IL, USA, in 2004. She is currently a Professor
with the Department of Computing and Software, McMaster University, Hamilton,
ON, Canada.
---


# Patient-centric health risk identification: How NLP can help?

(2022)

###### Abstract.

A clear and well-documented LaTeX document is presented as an article
formatted for publication by ACM in a conference proceedings or journal
publication. Based on the “acmart” document class, this article presents and
explains many of the common variations, as well as many of the formatting
elements an author may use in the preparation of the documentation of their
work.

Health informatics, Natural language processing, XXX

††copyright: acmcopyright††journalyear: 2022††doi: XXXXXXX.XXXXXXX††journal:
CSUR††journalvolume: 0††journalnumber: 0††article: 0††publicationmonth:
0††ccs: Information systems Retrieval models and ranking††ccs: Applied
computing Life and medical sciences††ccs: General and reference Surveys and
overviews††ccs: Computing methodologies Information extraction

##  1\. Introduction

#### what is family history and why it is useful

The value of family history information has long been recognized.

Family history, genetic susceptibility, shared environmental and behavioral
factors.

Cardiovascular diseases, type 2 diabetes, many cancers.

Different from genetic susceptibility that can be obtained via genetic
profiling, family history information captures the complex interactions
between genetic, environmental, and behavioral factors.

##### A motivating example

  * •

Pancreatic cancer is the fourth leading cause of cancer death in the United
States, while an estimated 466,003 people died from it worldwide in 2020.
111https://www.cancer.net/cancer-types/pancreatic-cancer/statistics

  * •

Due to its few sign and symptoms until in well-advanced cancer stages,
pancreatic cancer is referred to as silent killer: around 73% patients die
within the first year of their diagnosis (mehrabi-mayo-2015-family-history).

  * •

Several risk factors such as family history, pancreatic cysts, obesity,
smoking, and alcohol intake have been found:

    * –

It is estimated that 10% of pancreatic cancers have a familial basis.

    * –

Risk is increased 7-9 fold if one first-degree relative (parents, siblings or
children) has pancreatic cancer.

  * •

Other examples include the risk assessment of hypertrophic cardiomyopathy
(shen-mayo-2021-jmir-n2c2-2019-fh).

We are interested in identifying health risks from patient-centred data,
including medical history, family history and social history (social
determinants of health).

  * •

Social determinants of health (SDOH) are the conditions in which people live
that affect quality-of-life and health
outcomes.222https://health.gov/healthypeople/priority-areas/social-
determinants-health

milne-auckland-2009-family-hisory study the associations between family
history of four psychiatric disorders—depression, anxiety, alcohol dependence
and drug dependence—and clinical features of these disorders in probands (the
first diagnosed family member). They suggest that family history is useful for
determining patients’ clinical prognosis and for selecting cases for genetic
studies.

Family history can be used to estimate the risk of a patient developing
certain diseases such as breast cancer, colorectal cancer, ovarian cancer,
osteoporosis, cardiovascular disease, psychiatric disorders, and diabetes
(polubriaginof-columbia-2015-amia-family-history). It can also signal the need
for further genetic counseling or preventative health screening (bill-
minnesota-2014-amia-family-history). For example, permuth-egan-2009-familial-
cancer find that individuals with a family history of pancreatic cancer have
nearly a two-fold increased risk for developing pancreatic cancer to those
without such a history. They suggest that families with two or more pancreatic
cancer cases may benefit from comprehensive risk assessment using detailed
family history data, and that those at highest risk may be referred to
screening programs.

In addition to risk assessment, claassen-vumc-2010-bmc-family-history point
out that family history information can be used to personalize health
messages, which motivate at-risk individuals to adopt and maintain healthy
lifestyles in order to prevent disease.

*********************************

#### Why we need NLP for family history extraction

Modern health care system have enabled structured information about family
history that are filled by patients through paper forms or on-line programs,
however, a notable fraction of family history information is contained in
free-text clinical notes, which are written by clinicians or xx after they
encounter with patients. polubriaginof-2015-amia-family-history assessed the
quality of family history data captured in an established commercial EHR at a
medical centre. After analysing differences between 10,000 free-text and 9,121
structured family history observations, they find that free-text notes contain
more information than the structured notes.

Most of these data are stored in unstructured/semi-structured format,
therefore we need to employ NLP tools to convert these data into a structured
format.

  * •
  * •

140,038 observations defined in the EHR; of those, 653 are family history
related (polubriaginof-2015-amia-family-history).

The Epic EHR includes a dedicated portion for collecting family history
information. The portion allows for structured entry of problems (selected
from a list of 210 values such as cancer and diabetes), family member
(selected from a list of 21 values such as mother and brother), age of onset
(a numeric value such as 68), and a free-text field called _comment_. chen-
vermont-2012-amia-family-history conduct a manual review on $3,358$ unique
comments to identify reasons for use of the comment field and what types of
information are contained within them. They find that greater than one-third
of these comments are used to collect information that should be entered into
available structured fields (a problem that can be selected from the list of
210 values or a specific onset age, such as ‘breast cancer at 70’).

##  2\. Tasks and Resources

In this section, we review what NLP tasks have been addressed in previous
work, and what resources have been available to enable the development of NLP
models for family history extraction.

Figure 1. NLP Tasks studied in the literature.

###  2.1. Tasks

#### Family history sentence identification

Although it is common to have a dedicated section of family history in
clinical reports, lewis-ibm-2011-ieee-parsing-family-history found that, in
their dataset, only 36% of family history information belongs to these
dedicated sections. In other words, family history is buried in various places
of clinical text, and usually mixed with patient medical history. Therefore,
the first component in a family history extraction pipeline is to determine if
one sentence contains a family history statement (bill-minnesota-2014-amia-
family-history).

#### Family member detection

The simplest format of family member detection task is to identify specific
words, e.g., ‘brother’, ‘son’, in text that refer to the relative of the
patient. However, there are several constraints that make the task less
straightforward. The first one is that non-blood relatives, e.g., ‘adopted
siblings’, ‘partner’s sister’, are usually excluded as their information are
not helpful to analyse familial history of the patient. The second one is that
the possible surface forms need to be normalized with the side of family. For
example, the family member described in ‘The mother has a brother who is an
alcoholic and …’ is not the ‘brother’ of the patient but the ‘uncle’, and the
side of family is ‘maternal’. The third issue is that information about two or
more family members may be mentioned together. For example, there are two
individuals mentioned in the sentence ‘both cousins suffered from high blood
pressure’, and the model needs to distinguish them when constructing the
patient’s family tree.

  * •

Section segmentation: identifying a family history section and sentences
within this section (IU)

    * –

If clinical notes are CDA 1.0 compliant—sections have been codified, this step
can skipped (mehrabi-mayo-2015-family-history).

  * •

Entity identification, including family member and medical concept
identification (IU; n2c2 2019). The family history elements may include
disease, family member, cause, medication, age of onset of diagnosis, length
of disease, etc shen-mayo-2021-jmir-n2c2-2019-fh.

  * •

Living status

  * •

Relation extraction, including relations between medical observations and
family members (IU; n2c2 2019)

  * •

Negation detection (IU; n2c2 2019).

#### Medical concept identification

Depending on the downstream application, this may include any health-related
problem including diseases, smoking, suicide and drinking (shen-
mayo-2021-jmir-n2c2-2019-fh). Another challenge, pointed out by shen-
mayo-2021-jmir-n2c2-2019-fh, is that medical observations beyond first or
second degree should be excluded.

Diseases, diagnoses, various types of mutations, test results, treatments, and
vital state.

lewis-sfsu-2011-bicob-family-history; lewis-ibm-2011-ieee-parsing-family-
history extract family history as a tuple consisting of a family member and a
disease name, and the disease name must be resolvable to a 3 digit ICD9 code.

#### Clinical event recognition

rama-oslo-2018-louhi-family-history distinguish between clinical event
(something happens and then is over, for example, the patient has a heart
attachk) and clinical condition (a prolonged state, for example, the patient
has heart disease).

#### Attributes

Side; age; negation; amount; temporal

#### Relation

hoder; moidifer; related to, subset

#### Other

chen-vermont-2012-amia-family-history focus on free-text comments within the
‘structured’ family history section and aim to identify reasons for use of the
comments field.

###  2.2. Resources

Most of early studies on family history use in-house data, which are not
publicly available. For example, friedlin-mcdonald-2006-amia-family-history
use admission notes dictated at a primary care hospital in Indianapolis,
Indiana. goryachev-harvard-2008-amia-family-history use discharge summaries
and outpatient notes from two hospitals in Boston, Massachusetts. chen-
vermont-2012-amia-family-history use EHRs from a tertiary care academic
medical center affiliated with the University of Vermont. Until recently, XXX.
We describe these openly available resources and provide a summary of these
resources in Table 1.

MTSample dataset, used in (lewis-ibm-2011-ieee-parsing-family-history; lewis-
sfsu-2011-bicob-family-history; bill-minnesota-2014-amia-family-history), is
an openly available resource that contains sample transcription reports for 40
specialties (e.g., general medicine, cardiovascular, urology). These reports
have been anonymized and submitted by transcriptions and clinicians, and they
can be used as a proxy of the kinds of texts generated in a clinical setting.
It is worthy noting that because MTSample is not a dedicated family history
resource, the family history statements are relatively scarce. lewis-
ibm-2011-ieee-parsing-family-history find that, out of 3940 clinical reports,
there are only 1220 unique sentences mentioning at least one family member.
Similarly, bill-minnesota-2014-amia-family-history find that only $284$ out of
$23,155$ sentences contain family history statements.

To standardize evaluation on family history extraction, shen-
mayo-2021-jmir-n2c2-2019-fh organize the BioCreative/OHNLP family history
extraction shared task in 2018 and then the n2c2/OHNLP shared task in 2019.
The 2019 shared task focuses on identifying family members and clinical
observations, and extracting the association of the living status, side of the
family and clinical observations with family members. shen-
mayo-2021-jmir-n2c2-2019-fh curate the deidentified clinical narrative from
family history sections of clinical notes at Mayo Clinic Rochester. Note that
automatically generated semi-structured texts and sections that combine the
patients’ social history with the family history are excluded in their corpus.
The corpus is annotated by a 5-member annotator team, and each document is
annotated by 2 annotators. One coordinator worked as the adjudicator to
resolve discrepancies.

rama-oslo-2018-louhi-family-history develop the annotation guidelines for
family history extraction using synthetically produced clinical text in an
iterative fashion. That is, the domain expert participates both in the
annotation and development of guidelines. Synthetic examples are generated to
challenge the annotation guidelines and then the guidelines are revised based
on the annotation disagreements. In addition to ‘Family’ members, rama-
oslo-2018-louhi-family-history use ‘Self’ to refer the patient under
consideration, and ‘Index’ to the proband—the first identified family member
with a genetic disorder. Medical concepts—diseases, diagnoses, mutations, test
results, treatments and vital state—are grouped into one entity category
called ‘Condition’; ‘Event’ (e.g., has a heart attack) is distinguished from
‘Condition’ (e.g., have heart disease); a set of modifiers—side of the family,
age, negation cues, amount, temporal—are annotated to assist semantic
interpretation of family history information. rama-oslo-2018-louhi-family-
history also define several relations between entities: holder (between
Condition and Family/Self/Index entities); modifier (between modifiers and
other entities); related to (between family members); subset (used when
multiple family members are mentioned at the same time, e.g., between ‘two
brothers’ and ‘one of them’); partner (between no kinship family members that
are able to provide offspring, e.g., between ‘husband’ and ‘wife’).

azab-umich-2019-emnlp-family-history collect natural language
interactions—answers to a family history questionnaire—and then annotate
medical family histories. The questionnaire consists of questions targeting
the medical history of the patient and their relatives up to third degree, and
answers are collected from volunteers through crowd-sourcing or test cases of
genetic counseling sessions. Finally, a genetic counseling expert manually
annotate family members, their attributes (e.g., name, gender, age), and their
illnesses.

Data | Size |  Description
---|---|---
n2c2/OHNLP 2019 (shen-mayo-2021-jmir-n2c2-2019-fh) | 99 (Tr) 117 (Te) |
UMich (azab-umich-2019-emnlp-family-history) | 4,304 sentences; 41,831 tokens |  Cancer
UiO (rama-oslo-2018-louhi-family-history) | 477 sentences; 6,030 tokens |  Cardiac disease
MTSamples (lewis-sfsu-2011-bicob-family-history) | 1274 reports |  Sample medical transcription reports
MTSamples (lewis-ibm-2011-ieee-parsing-family-history) | 3940 reports
MTSamples (bill-minnesota-2014-amia-family-history) | 491 reports
Table 1. A summary of openly available resources used in previous studies.

##  3\. Methods

###  3.1. Family history statement detection

  * •

Rule-based

    * –

SecTag (mehrabi-mayo-2015-family-history)

lewis-sfsu-2011-bicob-family-history identifies candidate family history
sentences based on the presence of ‘sign-post’ words (e.g., ‘mother’,
‘brother’). They aim to extract family histories from any section within a
clinical report, rather than only titled sections of family history (friedlin-
mcdonald-2006-amia-family-history; goryachev-harvard-2008-amia-family-
history). bill-minnesota-2014-amia-family-history use a classification
approach of family history statement detection. Their method takes the section
heading, subsection heading and sentence text as input together, and then use
N-gram-tokenized text as predictors to the SVM classifier.

###  3.2. Relation extraction

friedlin-mcdonald-2006-amia-family-history develop a rule-based system for
extracting family history for $12$ diseases and categorizing relative degrees
(primary or secondary). They first map noun phrases to the UMLS concepts of
family member and diagnosis, and then use a set of co-occurrence based rules
to associate diagnoses to family members. When the system is evaluated on a
set of $613$ hospital admission notes, it achieves greater than $.95$
sensitivity and positive predictive value for both disease extraction and
relative categorization.

  * •

Ytex (mehrabi-mayo-2015-family-history)

  * •

Deep-learning based (zhan-hit-2021-jmir-family-history)

almeida-matos-2020-sac-family-history employ the Neji tool (CITATION), which
relies on a dictionary complied from the UMLS Metathesaurus (CITATION).

model entity identification as a sequence labeling problem using a CRF
classifier, taking lexical features, part-of-speech features and manually
designed binary features as input.

goryachev-harvard-2008-amia-family-history employ a set of rules to associate
the diagnosis with the most relevant family members. Their method is able to
accurately ($F_{1}$ score of $0.9231$) assign the diagnoses to specific family
members, when evaluated on a set of $350$ sentences. goryachev-
harvard-2008-amia-family-history find that errors are likely to occur in those
sentences with multiple groups of diagnoses or multiple groups of family
members, whereas human annotators agree perfectly on these annotations.

  * •

Rule-based (mehrabi-mayo-2015-family-history)

  * •

Deep-learning based (zhan-hit-2021-jmir-family-history)

almeida-matos-2020-sac-family-history follow the shortest path in the
dependency graph—build using Stanford CoreNLP (CITATION)—to associate disease
mentions to family members.

#### String matching

bill-minnesota-2014-amia-family-history rely on two external resources for
family member detection and observation recognition. That is, they search for
matches to phrases in the HL7 Clinical Genomics family history model for
family member detection and phrases defined by the UMLS Semantic Groups as
disorders and procedures for observation recognition. The identified family
member and observation entities are then linked together by an indicator word
or phrase thus forming a predication relation. A lexicon of indicator words
and phrases, including possession words (e.g., has, is, with) and experience
indicators (e.g., suffered a, died of, recovered from), is constructed from
the annotated training set.

#### Syntactic approach

lewis-sfsu-2011-bicob-family-history employs a set of dependency-based
syntactic patterns to link a family member to its diagnosis. For example, if a
sentence contains a direct object dependency (_dobj_) and a nominal subject
dependency (_nsubj_), and both dependencies share the same governor, their
method recognizes the dependent of the _dobj_ dependency as disease and the
dependent of the _nsubj_ dependency as family member. Similarly, lewis-
ibm-2011-ieee-parsing-family-history compile 107 unique dependency paths
(e.g., ‘mother’ $\to$ _nsubj_ $\to$ ‘has’ $\to$ _dobj_ $\to$ ‘cancer’) from
225 family history sentences. They find that the most frequent 10 dependency
paths can recover 57% of the family history tuples.

#### Machine learning approach

rama-oslo-2018-louhi-family-history model entity (family member and
observation) recognition as a sequence labeling problem using a linear SVM
model. The model takes features corresponding to individual word—lexical
features of current and surrounding words, POS tags of current and surrounding
words, and entity types of previous words—as input, and predict entity type
for each word. Similarly, azab-umich-2019-emnlp-family-history use a CRF model
for entity identification.

For relation classification, a simil rama-oslo-2018-louhi-family-history uses
a SVM model—based on lexical features, POS tags, dependency features, and
entity types—for relation classification. azab-umich-2019-emnlp-family-history
builds a binary relation classifier to determine the relation between every
pair of entities in the sentence. The input features of the classifier include
pre-trained word embeddings, position features and outputs from entity
identification model, and a bi-directional LSTM classifier is used to
determine whether the relation holds between given pair of entities. azab-
umich-2019-emnlp-family-history show that it can achieve high $F_{1}$
score—$0.98$—when a given sentence includes information regarding a single
person, but relatively lower $F_{1}$—$0.87$—when the given sentence talks
about two or more different persons.

zhan-hit-2021-jmir-family-history propose a graph-based model with biaffine
attention for family history extraction from cliniacl text.

(azab-michigan-2019-emnlp-family-history) use a neural network with a CRF
layer to produce attribute annotations, and then a neural network for binary
classification of relations

(bill-2014-amia-family-history) incorporate family history functionality into
an open-source NLP system, BioMedICUS. It contains five pipeline components:

Family history sentence detection that determines if the sentence contains a
family history statement.

Constituent mapping: annotate the family history members from the HL7 clinical
genomics family history model as family-member entities, and annotate all the
disorders or procedures from SNOMED CT as observation entities.

Relationship extraction: identified by “indicator phrases” (i.e.,
predication). Coordination and list resolution: transforms relationships that
have lists of family members and/or observations into a list of relationships
that specify a single family member and single observation.

Attributes scanning: search patterns to identify the essential attributes of a
relationship: vital status, certainty, age of diagnosis, side of family.

###  3.3. Negation detection

  * •

DEEPEN (mehrabi-mayo-2015-family-history)

  * •

Rule-based (zhan-hit-2021-jmir-family-history)

The negation detection implementation in (bill-minnesota-2014-amia-family-
history) scans terms to the left of the constituent object in question. Taking
the phrase ‘father, but not mother’ as an example, the negation component will
add a negation attribute to only the ‘mother’ entity of the phrase.

##  4\. Open Research Directions

We identify challenges regarding data, task, modelling

###  4.1. How can we obtain (annotated) data describing family history?

The development of NLP models, especially models based on machine learning
techniques, usually requires the access to manually annotated data. Clinical
text describing patients’ family history

Synthetic data may not be fully representative of real clinical notes.

Health-related information stored in Electronic Health Records (EHRs) is
private and should be protected. Although some resources based on anonymized
health records

governed by data

Common inter-annotator disagreement: semantic discrepancies (require domain
knowledge) and temporal and negation-related information (rama-2018-louhi-
family-history).

goryachev-harvard-2008-amia-family-history find that the prevalence of family
histories in clinical records is relatively low and family history information
is not always documented clearly under sections ‘family history’. In other

Previous studies rely on synthetic clinical text (rama-oslo-2018-louhi-family-
history)

How do these models trained on synthetic clinical text perform on real world
clinical text? How do they perform across different instituitions.

Cross text-type (azab-umich-2019-emnlp-family-history)

azab-michigan-2019-emnlp-family-history point out an interesting direction
that a dialog agent may be able to collect data from the patient.

Clinical notes, admission reports, questionnaires

###  4.2. How can we construct family tree from narrative texts?

In addition to identifying

###  4.3. Clinician-AI interaction

Hubert et al., (2022)

lewis-sfsu-2011-bicob-family-history experiment with different visualization
schemes—disease-centered view or family member centered view. However, it is
unclear how clinicians interact with different views and how the interaction
might affect clinician’s perceptions toward system outputs.

#### Patient embeddings

#### Can we infer the pedigree of a patient from text?

text to pedigree chart? text to family graph? text to tabular formats directly
usable in risk calcutators

rama-oslo-2018-louhi-family-history: transform statemsnes about pedigree into
tabular formats directly usable in risk calculators.

Given one patient’s family history data, can we infer the pedigree chart,
where nodes—the blood relatives of the patient—are organized in a tree
structure.

Deploy a dialog agent to collect family history; away from pressured
consultation environment

(Emery1999) point out that further work is needed to improve extraction of
certainty and temporal modifications.

(Friedlin2006; Welch2013; Lewis2011; goryachev-2008-amia-family-history)

Transferability: models trained on data from one institution may not work well
on other institutions.

• The original plan was writing a survey of family history extraction.
However, it is not easy to find a lot of related work on FHE. Citation numbers
of these work are also very low. • We decide to focus on the topic of
’Patient-centric health risk identification’. – We focus on the idea of
’preventing’, because if we cannot prevent healthy people from becoming
patients, ’treating’ causes larger impact on both people and health system –
We emphasis ‘Patient-centric’ here, because we want to identify health risks
from patient-related data, such as EHR, in contrast to other sources such as
scholarly articles – We identify health risk from patient _medical_ history;
_family_ history; and _social_ history. – Adverse drug events may be related
as well, for example, we can identify risks from patient medical history,
known allergies (mahendran-mcinnes-2021-amia-ade). ADE caused by drug-drug
interactions is excluded, because it is not ’patient-centric’

#### Why we need family history data

Knowing that a patient is at increased risk of developing a disease based on
family history enables disease prevention, varying from intensive screening to
prophylactic surgery (polubriaginof-2015-amia-family-history). For example,
the risk assessment of hypertrophic cardiomyopathy considers 1 or more first-
degree relatives with a history of sudden cardiac death under age 40 as a
significant factor of sudden cardiac death risk (shen-2021-jmir-n2c2-faimily-
history) The guidelines from the American Cancer Society recommend that
patients who have a lifetime risk of breast cancer should have screening MRI
in addition to mammography. The assessment heavily relies on family history
and presence of risk factors (polubriaginof-2015-amia-family-history).

(almeida-matos-2020-sac-family-history) (azab-umich-2019-emnlp-family-history)
(bill-minnesota-2014-amia-family-history) (chen-vermont-2012-amia-family-
history) (clift-mayo-2022-family-history) (dai-2019-bmc-family-member) (dai-
csiro-2021-cikm-searchehr) (dai-nkust-2020-jmir-family-history) (endevelt-
maccabi-2015-family-history) (friedlin-mcdonald-2006-amia-family-history)
(goryachev-harvard-2008-amia-family-history) (lewis-ibm-2011-ieee-parsing-
family-history) (lewis-sfsu-2011-bicob-family-history) (liu-mayo-2018-bio-
creative) (lybarger-washington-2021-jbi-sdoh) (mehrabi-mayo-2015-family-
history) (mehrabi-mayo-2016-amia-family-history) (milne-auckland-2009-family-
hisory) (ozanne-drohan-2012-mri-screening) (permuth-egan-2009-familial-cancer)
(polubriaginof-columbia-2015-amia-family-history) (rama-oslo-2018-louhi-
family-history) (roch-2015-pancreatic-cyst) (rybinski-csiro-2021-jmir-family-
history) (shen-mayo-2021-jmir-n2c2-2019-fh) (shi-hit-2019-bmc-family-history)
(stubbs-kotfila-2015-jbi-i2b2-2014) (wang-mayo-2017-amia-family-history)
(welch-kawamoto-2013-jamia-personalized-medicine) (zhan-hit-2021-jmir-family-
history)

(almeida-matos-2020-sac-family-history) (azab-umich-2019-emnlp-family-history)
(bill-minnesota-2014-amia-family-history) (chen-vermont-2012-amia-family-
history) (claassen-vumc-2010-bmc-family-history) (clift-mayo-2022-family-
history) (dai-2019-bmc-family-member) (dai-csiro-2021-cikm-searchehr) (dai-
nkust-2020-jmir-family-history) (endevelt-maccabi-2015-family-history)
(friedlin-mcdonald-2006-amia-family-history) (goryachev-harvard-2008-amia-
family-history) (lewis-ibm-2011-ieee-parsing-family-history) (lewis-
sfsu-2011-bicob-family-history) (liu-mayo-2018-bio-creative) (lybarger-
washington-2021-jbi-sdoh) (mehrabi-mayo-2015-family-history) (mehrabi-
mayo-2016-amia-family-history) (milne-auckland-2009-family-hisory) (ozanne-
drohan-2012-mri-screening) (permuth-egan-2009-familial-cancer) (polubriaginof-
columbia-2015-amia-family-history) (rama-oslo-2018-louhi-family-history)
(roch-2015-pancreatic-cyst) (rybinski-csiro-2021-jmir-family-history) (shen-
mayo-2021-jmir-n2c2-2019-fh) (shi-hit-2019-bmc-family-history) (stubbs-
kotfila-2015-jbi-i2b2-2014) (wang-mayo-2017-amia-family-history) (welch-
kawamoto-2013-jamia-personalized-medicine) (zhan-hit-2021-jmir-family-history)