# Secrecy Capacity in Large Cooperative Networks in Presence of Eavesdroppers
with Unknown Locations

Authors
Sharif University of Technology, Tehran, Iran Email<EMAIL_ADDRESS>Amir Hossein Hadavi, Narges Kazempour, Mahtab Mirmohseni and Mohammad Reza
Aref
Information Systems and Security Lab (ISSL)
Department of Electrical Engineering, Sharif University of Technology, Tehran,
Iran
Email: {ah_hadavi,narges_kazempour}<EMAIL_ADDRESS>
###### Abstract

In this paper, an extended large wireless network under the secrecy constraint
is considered. In contrast to works which use idealized assumptions, a more
realistic network situation with unknown eavesdroppers locations is
investigated: the legitimate users only know their own Channel State
Information (CSI), not the eavesdroppers CSI. Also, the network is analyzed by
taking in to account the effects of both fading and path loss. Under these
assumptions, a power efficient cooperative scheme, named _stochastic virtual
beamforming_ , is proposed. Applying this scheme, an unbounded secure rate
with any desired outage level is achieved, provided that the density of the
legitimate users tends to infinity. In addition, by tending the legitimate
users density to the infinity, the tolerable density of eavesdroppers will
become unbounded too.

##  I Introduction

Nowadays, secrecy is an essential quality of service which is harder to meet
in wireless networks, because their broadcast nature increases the possibility
of eavesdropping. Common methods rely on using algorithms with high
computational complexity that are hard to break for an adversary [1]. Another
field which focuses on the attackers with unlimited computational power is
information-theoretic physical layer secrecy. Wiretap channel, the basic model
for information-theoretic secrecy, was introduced by Wyner in [2] through
which reliable and secure transmission is possible if the channel between the
transmitter and the eavesdropper is the degraded version of the direct
channel, i.e., between the transmitter and the receiver.

There are many research works on wireless networks with few nodes [3], but
wireless systems are getting larger and larger and their exact performance
analysis is getting complex, actually impossible. This leads the research
community to turn into the scaling laws and analyzing the asymptotic behavior.
Large wireless networks was first investigated in [4] by Gupta and Kumar from
the scaling laws point of view. They considered an ad hoc large network with
$n$ randomly located nodes and the total rate that they achieved is
$O(\sqrt{n})$. Effects of secrecy on large wireless networks was investigated
in [5] for the first time, where a large wireless network has been
investigated that the distributions of the legitimate and eavesdropper nodes
are according to the Poisson point processes with densities $\lambda_{l}$ and
$\lambda_{e}$, respectively. The result of [5] is that the secure
communication with total rate of $O(\sqrt{n})$ is possible, as long as
$\lambda_{e}/\lambda_{l}=O((\log{n})^{2})$, where $n$ is the number of the
legitimate nodes. These works showed that it is possible to achieve the total
rate that scales like $\sqrt{n}$ under per node power constraint, with and
without secrecy. However, their main limiting assumption was considering a
point-to-point multihopping communication which excludes the possibility of
cooperation using relays.

Authors in [6] proposed a cooperative scheme to achieve a total rate with near
linear scaling under per node power constraint in a large wireless network
without secrecy constraints. In addition, they showed the possibility of zero
cost communication, i.e., unbounded total rate for fixed total power
constraint. In [7] using active cooperative relaying based schemes and with a
bound on the number of the eavesdroppers, the authors showed that zero cost
secure communication is also possible. Recent developments in wireless
technology (e.g., self interference cancellation, power allocation scheme at
the PHY layer, proper MAC protocol for the efficient implementation of the
full-duplex transmission mode [8]) support the relaying based cooperative
models, in contrast to the traditional multi-hop interference limited
networks.

In the model of [5, 7], the Channel State Information (CSI) is known to the
legitimate transmitter. However, knowing CSI leads to the knowledge of the
location of the passive eavesdroppers; that is not reasonable in many
practical cases. So the natural questions here are that if zero cost secure
communication is possible under unknown CSI. And, how should the cooperative
strategies change to achieve this result? In addition, another important
aspect of wireless network, ignored in many works, is fading. How fading
affects the secrecy rate in wireless systems is a challenging question.

The secrecy rate in large networks with _unknown CSI_ is investigated in some
recent works. In [9, 10], the total rate of order 1 was achieved in a large
wireless network with fading when CSI is not known. The authors in [11] took
the advantage of path diversity to achieve the total rate of order
$\sqrt{\frac{n}{\ln(n)}}$ in the case of unknown CSI, by limiting the number
of the eavesdroppers that can be tolerated. Adding network coding has improved
this result in [12] to a scheme in which any number of eavesdroppers could be
tolerated without any change in the total achievable rate. The unknown CSI
assumption is also taken into account in other works such as [13, 14].
However, to the best of our knowledge, none of the existing works uses
relaying to achieve zero cost secure communication with unknown CSI and/or
fading.

In this paper, we answer the above question affirmatively by proposing a
scheme that achieves zero cost secure communication in a fading network and in
the case of unknown CSI (including the eavesdroppers location). We consider a
network with $n_{l}$ legitimate nodes and $n_{e}$ eavesdroppers that are
distributed according to the Poisson point processes with densities
$\lambda_{l}$ and $\lambda_{e}$. In contrary to the existing works, we achieve
zero cost secure communication, i.e., unbounded total secrecy rate, by using
cooperation and distributed beamforming. In order to overcome the lack of CSI
knowledge, we propose a new scheme called, _stochastic virtual beamforming_.
In this 2-stage scheme, we benefit from the fading diversity by exploiting
some relaying nodes near the transmitter. Actually, we design a decode and
forward scenario to direct the majority of the power toward the receiver
location. To make this possible, at the first step the transmitter sends the
secure message to all the relaying nodes by using wiretap coding. The security
of this transmission step is provided by using the distance advantage of the
relaying nodes in comparison with the eavesdroppers. So we leverage the path-
loss effect in a positive way. Then, at the second step, the relaying nodes
accomplish a distributed beamforming by setting their transmission
coefficients proportional to the complex conjugate of their channel gains to
the receiver.

##  II Network Model and Preliminaries

Throughout the paper, use upper case letters are used for denoting the random
variables and lower-case letters for their realizations. Also, superscripts
$l$ and $e$ are used for denoting legitimate users and eavesdroppers,
respectively. We note the desired secure rate and outage level by $R_{S}$ and
$\epsilon$, respectively. Also, we define $\epsilon^{\prime}$ to be equal to
$\frac{\epsilon}{7}$. Considering both path loss and fading effects, we use a
common model for characterizing the power attenuation in wireless mediums as
[15]: $\frac{P_{R}}{P_{T}}=C\alpha^{2}{10}^{\frac{x}{10}}d^{-\gamma}$, in
which, $P_{R}$ is the received power; $P_{T}$ is the transmitted power; $C$ is
a constant; $\alpha$ is the fading coefficient; $10^{\frac{x}{10}}$ denotes
the shadow fading where $X\sim N(0,\sigma^{2})$; $d$ is the distance between
the transmitter and the receiver; and $\gamma$ is the path loss exponent which
depends on the environment and normally $\gamma>=2$. $\alpha$ is assumed to
have Rayleigh distribution with parameter $\mu$. For simplicity, we ignore the
effect of shadow fading comparing with path loss effect (we remark that the
shadowing effect is a random variable varying with location not with time).
Also, because of different and stochastic paths between the transmitter and
the receiver, the phase of the received signal (shown by $\theta$) is modeled
by a uniform distribution on $[0,2\pi]$. The letters $h$ and $d$ with
appropriate subscripts and superscripts are used for indicating fading
coefficients and distances, respectively. So, the channel gain from the $i$th
legitimate user to the $j$th legitimate user and also, to the $k$th
eavesdropper can be characterized by:

$\displaystyle G_{i,j}^{l}$ $\displaystyle=$ $\displaystyle
h_{i,j}^{l}(d_{i,j}^{l})^{-\gamma/2}e^{j\theta_{ij}^{l}}$ (1) $\displaystyle
G_{i,k}^{e}$ $\displaystyle=$ $\displaystyle
h_{i,k}^{e}(d_{i,k}^{e})^{-\gamma/2}e^{j\theta_{ik}^{e}}.$ (2)

We assume that the environment is isotropic. Hence the fading statistics is
the same between every two nodes. We consider a network with $n_{l}$
legitimate nodes and $n_{e}$ eavesdroppers that are distributed according to
the Poisson point processes with densities $\lambda_{l}$ and $\lambda_{e}$. We
consider the eavesdroppers as passive attackers with no collusion between
them. In addition, we assume that neither the location nor the fading
coefficient of any eavesdropper channel is not known to the legitimate users.
We consider an extended wireless network. In order to establish consistency
between the density of legitimate users ($\lambda_{l}$) and their total number
($n_{l}$,), we consider the network as a square with the side equal to
$\sqrt{\frac{n_{l}}{\lambda_{l}}}$. Also, for the sake of simplicity we let
the transmitter to be located at the center of the square. The Rayleigh
assumption for fading results in $\mathbb{E}\left[H^{2}\right]=2\mu$. Also,
for simplicity we assume that the noise variances of all the channels, either
legitimate or non-legitimate, are the same and equal to unity.

##  III Main Results

The main result of this paper is summarized in the following theorem. This
theorem states that the zero-cost secure communication is possible by using
our proposed scheme when eavesdroppers CSI is not known to the legitimate
users. The rest of this section is devoted to the proof of this result, where
we analyze the scheme in detail and derive six constraints for different
parameters of the network. These constraints are consistent and can be
selected step by step.

###### Theorem 1

In the extended network with fading and unknown eavesdroppers CSI (defined in
Section II), under the constant power constraint and by letting the legitimate
users density to be sufficiently large, any desired pair of secure rate and
outage level denoted by ($R_{S}$,$\epsilon$) is achievable.

###### Proof:

We propose a scheme which achieves the desired result. Our proof has two
steps: (i) In the first step, we consider the transmission from the
transmitter (source) to the relaying nodes and guarantee a specific secure
rate $R_{S}$ with high probability for this transmission. Our technique is
based on defining two circles, denoted by $B_{l}$ and $B_{e}$, centered at the
transmitter and radii $a_{l}$ and $a_{e}$, while $a_{l}<a_{e}$ (see Fig.1).
Then $\lambda_{l}$, $\lambda_{e}$, $a_{l}$, and $a_{e}$ are chosen such that
the following three requirements are provided. First, with the probability
greater than $1-{\epsilon^{\prime}}$, no eavesdropper lies in $B_{e}$. Second,
with the probability greater than $1-\epsilon^{\prime}$ at least $n_{r}$
legitimate users lie in $B_{l}$. Third, the difference of the worst legitimate
channel and the best eavesdropper channel be greater than $R_{S}$ with a
probability greater than $1-\epsilon^{\prime}$. (ii) In the second step, we
analyze the rate from the relay nodes to the receiver and guarantee the second
rate using the cooperation of $n_{r}$ relaying nodes. Actually, we make this
distributed Multiple-Input Single-Output Single-antenna Eavesdropper (MISOSE)
situation to concentrate the most of the transmitted power in a neighboring
region of the receiver. It can be deduced from our following calculations that
by increasing $n_{r}$, both $R_{S}$ and $\epsilon$ can be improved, i.e.,
increased and decreased, respectively.

###  III-A Step 1: First rate analysis

In this step, we guarantee a secure rate $R_{S}$ for the transmission from the
transmitter to the relaying nodes with an outage level of
$2\epsilon^{\prime}$. To make this possible, we choose the radius of the
circles $B_{l}$ and $B_{e}$ in a way that even with considering possible
exacerbating effects of the fading, the difference between the capacities of
the worst legitimate channel and the best eavesdropper channel be greater than
$R_{S}$ which is done by obtaining proper upper and lower bounds on $a_{l}$
and $a_{e}$, respectively. Hence, the following constraint must hold:

$\min_{1\leq i\leq n_{r},1\leq j\leq n_{e}}{C_{i}^{l}-C_{j}^{e}}>R_{S}$ (3)

where $C_{i}^{l}$ is the rate of the link from the transmitter to the $i$-th
legitimate user and $C_{j}^{e}$ is the rate of the link from the transmitter
to the $j$-th eavesdropper. To simplify the analysis, we work with a
suboptimum problem and we guarantee the following two inequalities:

$\displaystyle\min_{1<i<n_{r}}{C^{l}_{i}}$ $\displaystyle>(1+\rho)R_{S},$ (4)
$\displaystyle\max_{1<j<n_{e}}{C^{e}_{j}}$ $\displaystyle<\rho R_{S}.$ (5)

in which, $\rho$ is an arbitrary positive constant and the problem can be
optimized over $\rho$. Now, to establish (4) and (5), we present appropriate
upper and lower bounds on $a_{l}$ and $a_{e}$, respectively, where each bound
holds with an outage level of $\epsilon^{\prime}$.

####  III-A1 The legitimate rate analysis

In the following theorem, considering the constraint on $C^{l}_{i}$, we derive
an appropriate upper bound on $a_{l}$.

######  Theorem 2 (Upper bound on $a_{l}$)

A sufficient condition for having (4), with an outage level of
$\epsilon^{\prime}$, is:

$a_{l}<\Big{(}\frac{-P_{T}\mu\ln{(1-\frac{\epsilon^{\prime}}{n_{r}})}}{2^{(1+\rho)R_{S}}-1}\Big{)}^{\frac{1}{\gamma}}.$
(6)

###### Proof:

Using the union bound we guarantee the outage level of
$\frac{\epsilon^{\prime}}{n_{r}}$ for the rate of each of the $n_{r}$ relaying
nodes in $B_{l}$, to guarantee the outage level of $\epsilon^{\prime}$ for the
minimum of these rates. We write for one of them, chosen arbitrarily:

$\displaystyle\log{(1+P_{T}h^{2}d_{l}^{-\gamma})}$
$\displaystyle>\log{(1+P_{T}h^{2}a_{l}^{-\gamma})}>(1+\rho)R_{S}\Rightarrow$
$\displaystyle a_{l}^{\gamma}$
$\displaystyle<\frac{Ph^{2}}{2^{(1+\rho)R_{S}}-1}.$ (7)

where $d_{l}$ and $h$ are the distance and the channel gain (respectively)
between the transmitter and the chosen relay, so $d_{l}<a_{l}$. We require the
validity of (7) with a probability more than
$1-\frac{\epsilon^{\prime}}{n_{r}}$. With respect to the Rayleigh distribution
assumption for $h$, the distribution of $h^{2}$ is exponential with parameter
$\frac{1}{\mu}$. Hence, with the probability of
$1-\frac{\epsilon^{\prime}}{n_{r}}$, we have:
$h^{2}>-\mu\ln{(1-\frac{\epsilon^{\prime}}{n_{r}})}$. Thus, if $a_{l}$
satisfies the bound in (6), the inequality (7) holds with a probability more
than $1-\frac{\epsilon^{\prime}}{n_{r}}$. ∎

####  III-A2 Network Layering scheme and eavesdropper rate analysis

To analyze the eavesdroppers rates, one can follow a similar approach to what
presented in the previous part. However, the eavesdroppers are distributed in
all around the network and their distances from the transmitter vary from
$a_{e}$ to the radius of the network. Hence, following the same approach would
yield a loose bound on $a_{e}$. For deriving a tighter bound we propose a
network layering scheme. In this scheme, as shown in Fig. 1, the network is
divided to a number of layers and the eavesdroppers rates in each layer is
analyzed separately. To be precise, the $k$-th layer is defined as the region
of the network between the radii $2^{k-1}a_{e}$ and $2^{k}a_{e}$. We repeat
this procedure till the boundary of the network. In the following, we propose
a lower bound on $a_{e}$ using this idea. We denote the number of layers by
$K_{L}$ and the $k$-th layer by $L_{k}$.

Figure 1: The inner and outer circles and the two first layers in the network
layering scheme

The area of $L_{k}$, denoted by $S_{k}$, is equal to
$S_{k}=\pi\left(2^{2k}-2^{2(k-1)}\right)a_{e}^{2}=3\pi 2^{2(k-1)}a_{e}^{2}$.
To bound the number of eavesdroppers in each layer we present two following
lemmas.

######  Lemma 1 (Number of eavesdroppers in each layer)

For any positive constant $\beta_{k}$, define $t_{k}$ as:

$t_{k}\triangleq\big{(}\frac{\beta_{k}}{\epsilon^{\prime}}.\frac{1}{\lambda_{e}S_{k}}\big{)}^{\frac{1}{2}}.$
(8)

Then, with a probability larger than $1-\frac{\epsilon^{\prime}}{\beta_{k}}$,
the number of eavesdroppers in $L_{k}$ (denoted as $n_{e,k}$) satisfies:

$n_{e,k}<(1+t_{k})\lambda_{e}S_{k}.$ (9)

###### Proof:

Considering Poisson distribution of eavedroppers locations, we use Chebyshev’s
inequality for $n_{e,k}$ to write:

$\displaystyle\Pr\left\\{n_{e,k}>\lambda_{e}S_{k}+t_{k}{\lambda_{e}S_{k}}\right\\}$
$\displaystyle<\Pr\left\\{|n_{e,k}-\lambda_{e}S_{k}|>t_{k}\sqrt{\lambda_{e}S_{k}}\sqrt{\lambda_{e}S_{k}}\right\\}$
$\displaystyle<\frac{1}{t_{k}^{2}\lambda_{e}S_{k}}.$

∎

###### Lemma 2

If in Lemma 1, we set $\beta_{k}$s such that
$\sum_{k=1}^{K_{L}}{\frac{1}{\beta_{k}}}<1$ holds, then, the inequality (9)
will be valid for all the layers, with a probability larger than
$1-\epsilon^{\prime}$.

###### Proof:

Using the union bound for the undesired event in each layer, we can bound the
global undesired event. Therefore, the probability that the inequality (9)
does not hold in at least one layer is bounded by:

$\sum_{k=1}^{K_{L}}{\frac{\epsilon^{\prime}}{\beta_{k}}}={\epsilon^{\prime}}\sum_{k=1}^{K_{L}}{\frac{1}{\beta_{k}}}.$

Assuming the condition introduced in the lemma on $\beta_{k}$s, this quantity
will be less than $\epsilon^{\prime}$. ∎

Now we derive a proper bound on $a_{e}$ using the above lemmas. In fact, each
layer imposes a lower bound on $a_{e}$ and the largest lower bound is the main
constraint on $a_{e}$. Our technique of deriving these bounds is summarized in
the following. We divide the tolerable error $\epsilon^{\prime}$ between all
the layers, dedicating the tolerable error
$\epsilon_{k}=\frac{\epsilon^{\prime}}{2^{k}}$ to the $L_{k}$, and we find a
proper lower bound to guarantee the outage probability of $\epsilon_{k}$ for
this layer. In the analysis of each layer we apply the union bound for the
eavesdroppers in that layer. Finally, we apply the union bound on the outage
events of these layers to find a bound on the probability of the total outage
event. This total outage probability is less than $\epsilon^{\prime}$, because
of how $\epsilon_{k}$s are allocated.

Using Lemmas 1 and 2, we work with $(1+t_{k})\lambda_{e}S_{k}$ as the maximum
number of eavesdroppers in $L_{k}$. The following lemma gives the constraint
on $a_{e}$ concluded from $L_{k}$.

###### Lemma 3

Given the inequality (9), a sufficient condition to have,

$\max_{j\in L_{k}}{C^{e}_{j}}<\rho R_{S}$ (10)

with a probability greater than $1-\epsilon_{k}$, is the following constraint
on $a_{e}$:

$\displaystyle a_{e}$ $\displaystyle>a_{e}^{(k)}\triangleq
2^{-(k-1)}\Big{(}\frac{-P_{T}\mu}{2^{\rho
R_{S}}-1}\ln{(\frac{\epsilon^{\prime}}{2^{k}\lambda_{e}(1+t_{k})S_{k}})}\Big{)}^{\frac{1}{\gamma}}.$
(11)

###### Proof:

To guarantee the outage level of $\frac{\epsilon^{\prime}}{2^{k}}$ for the
validity of (10), relying on the union bound, we guarantee the outage level of
$\frac{\epsilon^{\prime}}{2^{k}n_{e,k}}$ for the validity of the following
inequality:

$C^{e}_{j}<\rho R_{S}$ (12)

for each of the eavesdroppers, e.g., the $j$-th eavesdropper, in this layer.
Considering the condition (9) on $n_{e,k}$, it suffices to guarantee the
outage level of $\frac{\epsilon^{\prime}}{2^{k}\lambda_{e}(1+t_{k})S_{k}}$ for
each of the eavesdroppers. For one of the eavesdroppers, arbitrarily chosen,
we write:

$\displaystyle\log{(1+Ph^{2}d_{e}^{-\gamma})}<\log{(1+Ph^{2}(2^{-{k-1}}a_{e})^{-\gamma})}<\rho
R_{S}.$

The first inequality is deduced from $d_{e}<2^{k-1}a_{e}$, in which $d_{e}$ is
the distance between the transmitter and the chosen eavesdropper. For
simplicity, the other indices are eliminated. We want the second inequality to
be valid with a probability greater than
$1-\frac{\epsilon^{\prime}}{2^{k}\lambda_{e}(1+t_{k})S_{k}}$. With the same
probability, for the coefficient $h^{2}$, considering its exponential
distribution, the following inequality holds:

$h^{2}<h^{2}_{\text{max}}\triangleq-\mu\ln{\left(\frac{\epsilon^{\prime}}{2^{k}\lambda_{e}(1+t_{k})S_{k}}\right)}.$

Hence, to provide the desired outage level, it suffices to guarantee the
inequality

$\log{(1+Ph^{2}_{\text{max}}(2^{-(k-1)}a_{e})^{-\gamma})}<\rho R_{S},$

by proper choice of $a_{e}$. With a little algebraic efforts and displacing
the variables, the recent inequality can be converted to (11). ∎

Now, we put all the results together in the following theorem. Then, from this
theorem and by some substitutions and calculations, we conclude the Corollary
1 in which an appropriate lower bound is finalized for $a_{e}$.

###### Theorem 3

Given the coefficients $t_{k}$ and $\beta_{k}$ consistent with the assumptions
presented in Lemmas 1 and 2 and by choosing

$a_{e}>\max_{1\leq k\leq K_{L}}{a_{e}^{(k)}},$ (13)

the rate inequality (5) holds with an outage probability less than
$2\epsilon^{\prime}$.

###### Proof:

Note that the inequality (5) is valid if and only if the one in (10) is valid.
We define the binary random variable $O_{k}$ as

$O_{k}=\left\\{\begin{array}[]{rl}0&\text{if }\max_{j\in
L_{k}}{C^{e}_{j}}<\rho R_{S},\\\ 1&\text{if }\max_{j\in L_{k}}{C^{e}_{j}}>\rho
R_{S}.\end{array}\right.$ (14)

In addition, we define the binary random variable $Q_{k}$ as

$Q_{k}=\left\\{\begin{array}[]{rl}0&\text{if
}n_{e,k}<(1+t_{k})\lambda_{e}S_{k},\\\ 1&\text{if
}n_{e,k}>(1+t_{k})\lambda_{e}S_{k}.\end{array}\right.$ (15)

Now, using the union bound, we write:

$\Pr\left\\{\max_{1<j<n_{e}}{C^{e}_{j}}>\rho
R_{S}\right\\}<\sum_{k=1}^{L_{K}}{\Pr\left\\{O_{k}=1\right\\}}.$ (16)

Also, we expand the occurrence probability of $O_{k}$ in $Q_{k}$ as the
following:

$\displaystyle\Pr\left\\{O_{k}=1\right\\}$
$\displaystyle=\sum_{i=0,1}{\Pr\left\\{Q_{k}=i\right\\}\Pr\left\\{O_{k}=1|Q_{k}=i\right\\}}$
$\displaystyle\stackrel{{\scriptstyle\text{{(a)}}}}{{\leq}}\Pr\left\\{O_{k}=1|Q_{k}=0\right\\}+\Pr\left\\{Q_{k}=1\right\\}.$
(17)

Considering that the value of the probability function is not never more than
the unity, the terms $\Pr\left\\{Q_{k}=0\right\\}$ and
$\Pr\left\\{O_{k}=1|Q_{k}=1\right\\}$ in the inequality (a) are replaced by 1.
First, we investigate the first term of (17). Given (13), the offered
sufficient condition presented in the Lemma 3 ((11)) holds for all the layers.
So, considering this lemma, we have:

$\Pr\left\\{O_{k}|Q_{k}=0\right\\}<\frac{\epsilon^{\prime}}{2^{k}}.$ (18)

By summing up in all the layers, we write:

$\sum_{k=1}^{L_{K}}{\Pr\left\\{O_{k}|Q_{k}=0\right\\}}<\sum_{k=1}^{L_{k}}{\frac{\epsilon^{\prime}}{2^{k}}}<{\epsilon^{\prime}}.$
(19)

Now we consider the second term in (17). For the summation of these terms,
according to the Lemma 2, we have:

$\sum_{k=1}^{K_{L}}{\Pr\left\\{Q_{k}=1\right\\}}<{\epsilon^{\prime}}.$ (20)

Now the proof is completed by applying (17) in (16) and then using the
inequalities (19) and (20). ∎

###### Corollary 1

By choosing

$a_{e}=\frac{(P_{T}\mu)^{\frac{1}{\gamma}}}{(2^{\rho
R_{S}}-1)^{\frac{1}{\gamma}}}(\ln{\frac{-\ln{(1-\epsilon^{\prime})^{6}}}{\epsilon^{\prime}}}+\sqrt{\frac{2\epsilon^{\prime}}{\left(-\ln{(1-\epsilon^{\prime})^{3}}\right)^{3}}}),$
(21)

the outage probability of (5) is less than $2\epsilon^{\prime}$.

###### Proof:

We start from the right side of the constraint (13) in the recent theorem and
insert the value of $a_{e}^{(k)}$ from (11). Also, we replace $t_{k}$ by its
calculated value from (8) and for any $1\leq k\leq K_{L}$, we set:

$\beta_{k}=2^{k}.$ (22)

It’s clear that by this choice, the required condition in the Lemma 2 for
$\beta_{k}$s is established. Furthermore, we replace $\lambda_{e}$ by its
value from (48). Now, we can write:

$\displaystyle a_{e}$ $\displaystyle=\max_{1\leq k\leq K_{L}}{a_{e}^{(k)}}$
$\displaystyle=\left(\frac{P\mu}{2^{\rho
R_{S}}-1}\right)^{\frac{1}{\gamma}}\max_{1\leq k\leq
K_{L}}{-2^{-(k-1)}\ln{\frac{\epsilon^{\prime}}{2^{k}\lambda_{e}S_{k}(1+t_{k})}}}$
$\displaystyle=\left(\frac{P\mu}{2^{\rho
R_{S}}-1}\right)^{\frac{1}{\gamma}}\max_{1\leq k\leq
K_{L}}{2^{-(k-1)}\times\ln{\frac{-3\times
2^{3k-2}\ln{(1-\epsilon^{\prime})}+\left(\frac{4}{-3\epsilon^{\prime}\ln{(1-\epsilon^{\prime})}}\right)^{\frac{1}{2}}\beta_{k}^{\frac{1}{2}}}{\epsilon^{\prime}}}}$
$\displaystyle\stackrel{{\scriptstyle\text{{(a)}}}}{{=}}\left(\frac{P\mu}{2^{\rho
R_{S}}-1}\right)^{\frac{1}{\gamma}}\max_{1\leq k\leq
K_{L}}{2^{-(k-1)}\ln{\left(c_{1}2^{3k}+c_{2}2^{\frac{k}{2}}\right)}}$
$\displaystyle=\left(\frac{P\mu}{2^{\rho
R_{S}}-1}\right)^{\frac{1}{\gamma}}\max_{1\leq k\leq
K_{L}}{2^{-(k-1)}\ln{c_{1}2^{3k}\left(1+\frac{c_{2}}{c_{1}}2^{\frac{-5}{2}k}\right)}}$
$\displaystyle\stackrel{{\scriptstyle\text{{(b)}}}}{{<}}\left(\frac{P\mu}{2^{\rho
R_{S}}-1}\right)^{\frac{1}{\gamma}}\max_{1\leq k\leq
K_{L}}{2^{-(k-1)}(3k\ln{2}+\ln{c_{1}}+\frac{c_{2}}{c_{1}}2^{-\frac{5}{2}k})}$
$\displaystyle\stackrel{{\scriptstyle\text{{(c)}}}}{{=}}\left(\frac{P\mu}{2^{\rho
R_{S}}-1}\right)^{\frac{1}{\gamma}}\left(3\ln{2}+\ln{c1}+\frac{c_{2}}{4\sqrt{2}c_{1}}\right)$

In the equation (a), the following definitions are used:

$\displaystyle c_{1}$
$\displaystyle\triangleq\frac{-3\ln{(1-\epsilon^{\prime})}}{4\epsilon^{\prime}},$
(23) $\displaystyle c_{2}$
$\displaystyle\triangleq\sqrt{\frac{4}{-3\epsilon^{\prime}\ln{(1-\epsilon^{\prime})}}}.$
(24)

Inequality (b) is deduced from $\ln{x}<x-1$ for $x>0$ and $x\neq 1$. The
inequality (c) is obtained by considering that the argument of maximization is
a decreasing function in $k$, so it takes its maximum at $k=1$. Substituting
this value for $k$, the last line is obtained. ∎

By replacing $c_{1}$ and $c_{2}$ by their values we reach to the same value in
the relation (21). Now we set $a_{e}$ equal to this value. Hence, the desired
condition in the theorem 3 will be valid, too.

###### Remark 1

We remark that the proposed idea for layering the network is really effective.
In fact, as it’s clear from (21), the final constraint on $a_{e}$ is
independent of the number of the eavesdroppers (and so from the size of the
network). Therefore, by extending the network and so increasing the total
number of the eavesdroppers, it’s not necessary to limit the eavesdropper-free
region anymore.

###  III-B Step 2: Second rate analysis

In this subsection we analyze the second rate, i.e., forward rate, and from it
we derive the proper constraint on $n_{r}$.

####  III-B1 Fading calculations

In this part we pick arbitrarily one of the eavesdroppers and do the
calculations for it. We denote the channel gain vector between the source and
the legitimate and the non-legitimate users, respectively, as:

$\displaystyle\underline{g}^{l}$
$\displaystyle=\left((d_{1}^{l})^{-\gamma/2}h_{1}^{l}e^{j\theta_{1}^{l}},\dots,(d_{n_{r}}^{l})^{-\gamma/2}lh_{n_{r}}^{l}e^{j\theta_{n_{r}}^{l}}\right),$
(25) $\displaystyle\underline{g}^{e}$
$\displaystyle=((d_{1}^{e})^{-\gamma/2}h_{1}^{e}e^{j\theta_{1}^{e}},\dots,(d_{n_{r}}^{e})^{-\gamma/2}h_{n_{r}}^{e}e^{j\theta_{n_{r}}^{e}}).$
(26)

We assume that the distance between every two users is greater than half of
the wavelength. This assumption yields the uncorrelation of different fading
gains and phases [16]. We establish a virtual and distributed MISOSE situation
using adequate relaying nodes. This scheme has two advantage comparing with
conventional Multiple-Input Multiple-Output (MIMO) schemes. First, it does not
need the devices to be equipped with multiple antennas. Second, as noted in
[1], the maximum number of antennas in practical MIMO systems has physical
limitation. But, in this scheme we can exploit more relaying nodes and benefit
more from channel diversity. In [17], for MISOSE situation with ergodic
capacity criterion and known CSI and only for legitimate users, it has been
proved that the efficient strategy for the beamforming of the transmission
vector is to align it in the direction of the fading vector. Thus, by a
similar technique, we align the beamforming vector in the direction of complex
conjugate of channel gain vector, i.e., $(\underline{g}^{l})^{*}$, to maximize
the correlation between these two vectors. In order to control the total
consumed power, we set the beamforming vector equal to
$\frac{(\underline{g}^{l})^{*}}{n_{r}}$. Given only legitimate users CSI, it
is a reasonable strategy.

Message transmission scheme: For the message set $M=[1:2^{nR}]$ and for any
$m\in M$, a proper codeword $X^{n}$ generated from Wyner wiretap coding is
chosen and transmitted by the transmitter. We denote the average power of the
transmitter by $P_{T}$. The relaying nodes decode their received sequence to
obtain the transmitted message $m$. In the next step, the $i$-th relaying node
uses the same codebook to send the sequence
$F_{i}=\frac{1}{\sqrt{n_{r}}}(d_{i}^{l})^{-\gamma/2}h_{i}X^{n}e^{-j\theta_{i}^{l}}$
in $n$ transmission intervals. So the power consumed by the $i$-th relaying
node and the total consumed power equal to:

$\displaystyle P_{i}$
$\displaystyle=\frac{1}{n_{t}n_{r}}\sum_{t=1}^{n_{t}}{(d_{i}^{l})^{-\gamma}h_{i}^{2}|X(t)|^{2}}=\frac{(d_{i}^{l})^{-\gamma}h_{i}^{2}}{n_{r}}P_{T},$
(27) $\displaystyle P_{T}^{\text{(tot)}}$
$\displaystyle=\sum_{i=1}^{n_{r}}{P_{i}}=(\frac{1}{n_{r}}\sum_{i=1}^{n_{r}}{(d_{i}^{l})^{-\gamma}h_{i}^{2}})P_{T}.$
(28)

Furthermore, the received signals at the end of the $t$-th transmission
interval are:

$\displaystyle Y(t)$
$\displaystyle=(\frac{1}{\sqrt{n_{r}}}\sum_{i=1}^{n_{r}}{(d_{i}^{l})^{-\gamma}(h_{i}^{l})^{2}})X(t),$
$\displaystyle Z(t)$
$\displaystyle=(\frac{1}{\sqrt{n_{r}}}\sum_{i=1}^{n_{r}}{(d_{i}^{l})^{-\gamma/2}(d_{i}^{e})^{-\gamma/2}h_{i}^{l}h_{i}^{e}e^{j(\theta_{i}^{e}-\theta_{i}^{l})}})X(t).$

Finally, the received powers at the legitimate user and the eavesdroppers are:

$\displaystyle P_{l}$
$\displaystyle=(\frac{1}{\sqrt{n_{r}}}\sum_{i=1}^{n_{r}}{(d_{i}^{l})^{-\gamma}h_{i}^{2}})^{2}P_{T},$
(29) $\displaystyle P_{e}$
$\displaystyle=\Big{|}\frac{1}{\sqrt{n_{r}}}\sum_{i=1}^{n_{r}}{(d_{i}^{l})^{-\gamma/2}(d_{i}^{e})^{-\gamma/2}h_{i}^{l}h_{i}^{e}e^{j({\theta_{i}^{e}-\theta_{i}^{l}})}}\Big{|}^{2}P_{T}.$
(30)

Now we consider these two recent random variables (i.e., $P_{l},P_{e}$) and
give bounds on their expected values and variances. Having these in hand, we
can use a bounding inequality, like Chebyshev’s inequality, to predict the
behavior of these two quantities with high probability.

Probabilistic results: Based on the assumptions we noted previously about the
fading coefficients, we proved the following bounds for the expected value and
variances of $P_{l}$ and $P_{e}$. The proof is provided in appendix III-C2.

###### Theorem 4

By appropriate choices for $\eta$ and $\nu$, the following bounds hold:

$\displaystyle\frac{\mathbb{E}\left[P_{l}\right]}{P_{T}}$ $\displaystyle>\eta
n_{r}(d_{TR}+a_{l})^{-2\gamma},$ (31)
$\displaystyle\frac{\mathbb{E}\left[P_{e}\right]}{P_{T}}$
$\displaystyle<{\eta}(a_{e}-a_{l})^{-\gamma}(d_{TR}-a_{l})^{-\gamma},$ (32)
$\displaystyle\frac{\sigma^{2}(P_{l})}{P_{T}^{2}}$
$\displaystyle<{\nu^{2}}{n_{r}}(d_{TR}-a_{l})^{-4\gamma},$ (33)
$\displaystyle\begin{split}\frac{\sigma^{2}(P_{e})}{P_{T}^{2}}&<{\nu^{2}}(a_{e}-a_{l})^{-2\gamma}(d_{TR}-a_{l})^{-2\gamma}.\end{split}$
(34)

where, $d_{TR}$ is the distance between the transmitter and the receiver. It
is assumed that the receiver is out of the inner circle ($B_{l}$).

To continue, we look for the sufficient number of relaying nodes in order to
attain the secure rate $R_{S}$ with outage probability less than
$2\epsilon^{\prime}$. We use Chebyshev’s inequality to establish proper bounds
on probability of the undesired events defined on the amount of $P_{l}$ and
$P_{e}$. We wish to have $C_{l}-\max_{i\in\mathcal{E}}{C_{i}^{e}}>R_{S}$ with
a probability greater than $1-\epsilon^{\prime}$. But, for the sake of
simplicity, we guarantee the following bounds, each with the probability of
$1-\epsilon^{\prime}$:

$\displaystyle C_{l}$ $\displaystyle>(1+\kappa)R_{S},$ (35)
$\displaystyle\max_{i\in\mathcal{E}}{C_{i}^{e}}$ $\displaystyle<\kappa R_{S}.$
(36)

where, $\kappa$ is an arbitrary positive constant which can be optimized if
necessary. Now, we derive the proper bounds on the network parameters by
analyzing the above limitations. Instead of (36), using a union bound
approach, we consider the following constraint for each eavesdropper:

$C_{i}^{e}<\kappa R_{S}$ (37)

with the probability of $1-\frac{\epsilon^{\prime}}{n_{e}}$.

####  III-B2 Legitimate rate analysis

The constraint in (35) implies
$\Pr\left\\{C_{l}=\log{(1+P_{l})}<(1+\kappa)R_{S}\right\\}<\epsilon^{\prime}$,
or equivalently:

$\Pr\left\\{P_{l}<2^{(1+\kappa)R_{S}}-1\right\\}<\epsilon^{\prime}.$ (38)

Now, we apply Chebyshev’s inequality and drive a lower bound on $n_{r}$ which
guarantees (38). Noting the expected value and the variance of $P_{l}$ by
$\eta_{l}$ and $\nu_{l}^{2}$, respectively, we apply the inequalities of
Theorem 4 for these two values. First, we write:

$\displaystyle\Pr\left\\{P_{l}<2^{(1+\kappa)R_{S}}-1\right\\}$
$\displaystyle\stackrel{{\scriptstyle\text{{(a)}}}}{{<}}\Pr\left\\{P_{l}<\eta_{l}-\alpha\nu_{l}\right\\}$
$\displaystyle<\Pr\left\\{|P_{l}-\eta_{l}|>\alpha\nu_{l}\right\\}\stackrel{{\scriptstyle\text{{(b)}}}}{{<}}\frac{1}{\alpha^{2}}\stackrel{{\scriptstyle\text{{(c)}}}}{{\leq}}\epsilon^{\prime}.$

where, (b) follows from Chebyshev’s inequality,for (c) we set:
$\alpha=\sqrt{\frac{1}{\epsilon^{\prime}}}$, and for (a), it’s sufficient to
have: $2^{(1+\kappa)R_{S}}-1<\eta_{l}-\alpha\nu_{l}$, or equivalently:
$\nu_{l}<\frac{1}{\alpha}(\eta_{l}-2^{(1+\kappa)R_{S}}+1$. Considering (31)
and (33), it’s sufficient to establish the following chain:

$\displaystyle\nu_{l}$
$\displaystyle\stackrel{{\scriptstyle\text{{(d)}}}}{{<}}{\nu}{\sqrt{n_{r}}}(d_{TR}-a_{l})^{-2\gamma}P_{T}$
$\displaystyle\stackrel{{\scriptstyle\text{{(e)}}}}{{<}}\frac{1}{\alpha}(\eta{n_{r}}(d_{TR}+a_{l})^{-2\gamma}P_{T}-2^{(1+\kappa)R_{S}}+1)$
$\displaystyle\stackrel{{\scriptstyle\text{{(f)}}}}{{<}}\frac{1}{\alpha}(\eta_{l}-2^{(1+\kappa)R_{S}}+1).$

where, (d) and (f) are deduced from Theorem 4. We establish (e) by choosing
$n_{r}$ sufficiently large. After some algebraic calculations, (e) can be
written as the following quadratic inequality in $\sqrt{n_{r}}$:

$\displaystyle
n_{r}(\eta(d_{TR}+a_{l})^{-2\gamma}P_{T})-\sqrt{n_{r}}(\alpha{\nu}(d_{TR}-a_{l})^{-2\gamma}P_{T})$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad-2^{(1+\kappa)R_{S}}+1>0.$

in which only one of the two roots is positive and so acceptable. By choosing
$n_{r}$ greater than the square of this root, we reach a constraint on $n_{r}$
presented in the following theorem.

######  Theorem 5 (Lower bound for $n_{r}$)

A sufficient condition on $n_{r}$ for guaranteeing (35) with an outage level
of $\epsilon^{\prime}$ is to have:

$\displaystyle n_{r}$
$\displaystyle>\frac{(d_{TR}-a_{l})^{-4\gamma}}{4\eta^{2}(d_{TR}+a_{l})^{-4\gamma}}({\frac{\nu}{\sqrt{\epsilon^{\prime}}}+\sqrt{\zeta}})^{2},$
(39) $\displaystyle\zeta$
$\displaystyle=\frac{\nu^{2}}{\epsilon^{\prime}}+4\eta\frac{(d_{TR}+a_{l})^{-2\gamma}}{P_{T}(d_{TR}-a_{l})^{-4\gamma}}(2^{(1+\kappa)R_{S}}-1).$

In order to get an intuition from the behavior of this constraint, we put a
simplifying assumption on $a_{l}$, which makes this constraint independent of
$a_{l}$. For this, we assume:

$a_{l}<d_{TR}/2.$ (40)

We justify this assumption by noting that if the receiver lies in $B_{l}$, it
is not necessary to exploit the _stochastic virtual beamforming_ scheme.
Actually in this situation, based on the calculations for the first rate, the
message can be delivered securely to the receiver by direct transmission.
Here, for the sake of simplicity, after choosing a valid value for $a_{l}$,
i.e., a value which satisfies the constraint in (6), we divide it by two. By
this choice, we can send the secure message directly to the receiver whenever
the receiver is in the distance of at most $2a_{l}$. Therefore, we use our
proposed scheme, i.e., the _stochastic virtual beamforming_ , only when (40)
holds. Using this, constraint (39) is turned to the following simplified
version. The proof is simple and is completed by bounding $d_{TR}\pm a_{l}$
properly.

###### Corollary 2

A simplified sufficient condition on $n_{r}$ to guarantee (35) with the outage
level of $\epsilon^{\prime}$ is to have:

$n_{r}>\frac{81}{4\eta^{2}}\Big{(}\frac{\nu}{\sqrt{\epsilon^{\prime}}}+\sqrt{\frac{\nu^{2}}{\epsilon^{\prime}}+\frac{4\eta}{P_{T}}d_{TR}^{2\gamma}(2^{(1+\kappa)R_{S}}-1)}\Big{)}^{2}.$
(41)

####  III-B3 Eavesdropper rate analysis

Now, we proceed in a similar way to obtain another constraint to guarantee
(37) for the eavesdropper rate with high probability. As noted previously, for
the arbitrarily chosen eavesdropper, we wish to have:
$\Pr\left\\{\log(1+P_{e})>\kappa R_{S}\right\\}=\Pr\left\\{P_{e}>2^{\kappa
R_{S}}-1\right\\}<\frac{\epsilon^{\prime}}{n_{e}}$. Similar to the previous
part, we use $\eta_{e}$ and $\nu_{e}^{2}$ to denote the expected value and the
variance of $P_{e}$. We start with:

$\displaystyle\Pr\left\\{P_{e}>2^{\kappa R_{S}}-1\right\\}$
$\displaystyle\stackrel{{\scriptstyle\text{{(a)}}}}{{<}}\Pr\left\\{P_{e}>\eta_{e}+\alpha\nu_{e}\right\\}$
$\displaystyle<\Pr\left\\{|P_{e}-\eta_{e}|>\alpha\nu_{e}\right\\}\stackrel{{\scriptstyle\text{{(b)}}}}{{<}}\frac{1}{\alpha^{2}}\stackrel{{\scriptstyle\text{{(c)}}}}{{\leq}}\frac{\epsilon^{\prime}}{n_{e}},$

where (b) follows from Chebyshev’s inequality and for (c) we set
$\alpha=\sqrt{\frac{n_{e}}{\epsilon^{\prime}}}$. Similar to the previous part,
for establishing (a), it’s sufficient to have
$\nu_{e}<\frac{1}{\alpha}(2^{\kappa R_{S}}-\eta_{e}-1)$. Now, considering (32)
and (34), it is sufficient to establish the following chain,

$\displaystyle\nu_{e}$
$\displaystyle\stackrel{{\scriptstyle\text{{(d)}}}}{{<}}\nu(a_{e}-a_{l})^{-\gamma}(d_{TR}-a_{l})^{-\gamma}P_{T}$
$\displaystyle\stackrel{{\scriptstyle\text{{(e)}}}}{{<}}\frac{1}{\alpha}\left(2^{\kappa
R_{S}}-\eta(a_{e}-a_{l})^{-\gamma}(d_{TR}-a_{l})^{-\gamma}P_{T}-1\right)$
$\displaystyle\stackrel{{\scriptstyle\text{{(f)}}}}{{<}}\frac{1}{\alpha}\left(2^{\kappa
R_{S}}-\eta_{e}-1\right).$

By some substitution and assuming the other parameters to be constant, the
inequality (e) can be converted to a constraint on $n_{e}$, as follows:

$\displaystyle n_{e}<{\epsilon^{\prime}}\big{(}\frac{2^{\kappa
R_{s}}-\eta(a_{e}-a_{l})^{-\gamma}(d_{TR}-a_{l})^{-\gamma}-1}{\nu(a_{e}-a_{l})^{-\gamma}(d_{TR}-a_{l})^{-\gamma}P_{T}}\big{)}^{2}.$
(42)

###  III-C Poisson calculations

####  III-C1 Constraint related to the inner circle

We must have at least $n_{r}$ legitimate relaying nodes in the circle $B_{l}$,
where $n_{r}$ is chosen appropriately regarding the former constraint in (39).
In the following, we start by bounding the probability of undesirable event,
i.e., having less than $n_{r}$ nodes in $B_{l}$, using Chebyshev’s inequality.
Then, using this bound, we derive a sufficient condition for $\lambda_{l}$, in
order to keep the probability of undesirable event less than
${\epsilon^{\prime}}$. By defining the $k_{l}$ as the number of legitimate
nodes in $B_{l}$, we write:

$\displaystyle\Pr\left\\{k_{l}<n_{r}\right\\}$
$\displaystyle<\Pr\left\\{|k_{l}-\lambda_{l}\pi a_{l}^{2}|>\lambda_{l}\pi
a_{l}^{2}-n_{r}\right\\}$ $\displaystyle=\Pr\left\\{|k_{l}-\lambda_{l}\pi
a_{l}^{2}|>\sqrt{\lambda_{l}\pi a_{l}^{2}}\frac{\lambda_{l}\pi
a_{l}^{2}-n_{r}}{\sqrt{\lambda_{l}\pi a_{l}^{2}}}\right\\}$
$\displaystyle<\frac{\lambda_{l}\pi a_{l}^{2}}{(\lambda_{l}\pi
a_{l}^{2}-n_{r})^{2}}.$ (43)

To satisfy the outage probability constraint, it suffices to set (43) less
than or equal to ${\epsilon^{\prime}}$. In the equality case, we reach the
following equation from which a lower bound on $\lambda_{l}$ is deduced. By
satisfying this constraint, we have at least $n_{r}$ legitimate nodes in the
inner circle, $B_{l}$, with probability larger than $1-{\epsilon^{\prime}}$.

$\displaystyle\lambda_{l}^{2}(\pi^{2}a_{l}^{4})-\lambda_{l}(2n_{r}+\frac{1}{\epsilon^{\prime}})\pi
a_{l}^{2}+n_{r}^{2}=0\Rightarrow$
$\displaystyle\lambda_{l}=\frac{n_{r}+\frac{1}{2\epsilon^{\prime}}\pm\sqrt{\left(n_{r}+\frac{1}{2\epsilon^{\prime}}\right)^{2}-n_{r}^{2}}}{\pi
a_{l}^{2}}$ (44)

Note that the smaller solution in (44) is not acceptable, because it yields
values for $\lambda_{l}$ which are lower than $\frac{n_{r}}{\pi a_{l}^{2}}$.
So we work with the greater solution. As a sufficient condition, we can choose
$\lambda_{l}$ to be greater than this solution. Therefore,

$\displaystyle\lambda_{l}>\frac{n_{r}+\frac{1}{2\epsilon^{\prime}}+\sqrt{(n_{r}+\frac{1}{2\epsilon^{\prime}})^{2}-n_{r}^{2}}}{\pi
a_{l}^{2}}=$ $\displaystyle\frac{n_{r}}{\pi
a_{l}^{2}}\big{(}\underbrace{1+\frac{1}{2\epsilon^{\prime}n_{r}}+\sqrt{(1+\frac{1}{2\epsilon^{\prime}n_{r}})^{2}-1}}_{\beta_{l}(\epsilon)}\big{)}.$
(45)

By the above definition of $\beta_{l}(\epsilon)$, we summarize the constraint
as:

$\displaystyle\lambda_{l}>\beta_{l}(\epsilon).\frac{n_{r}}{\pi a_{l}^{2}}.$
(46)

####  III-C2 Constraint related to the outer circle

As mentioned previously we need the circle $C^{e}$ to be free of
eavesdroppers, with probability larger than $1-{\epsilon^{\prime}}$. By
defining $k_{e}$ as the number of eavesdroppers in $B_{e}$, we want to have:

$\displaystyle\Pr\left\\{k_{e}=0\right\\}>1-{\epsilon^{\prime}}\Rightarrow
e^{-\lambda_{e}\pi a_{e}^{2}}>1-{\epsilon^{\prime}}$ (47)

which results in the constraint:

$\displaystyle\lambda_{e}<\frac{-\ln(1-{\epsilon^{\prime}})}{\pi a_{e}^{2}}$
(48)

The main six constraints for $a_{l}$, $a_{e}$, $n_{r}$, $n_{e}$, $\lambda_{l}$
and $\lambda_{e}$ are given in (6), (21), (41), (42), (46) and (48),
respectively. To achieve any desired pair of $(R_{S},\epsilon)$, we proceed as
follows. First, we set $n_{r}$ satisfying (41), which just depends on $R_{S}$
and $\epsilon$ and not the other five parameters. Knowing $n_{r}$, we choose
$a_{l}$ properly from its constraint in (6). Then, the required $\lambda_{l}$
is calculated by inserting the value of $n_{r}$ and $a_{l}$ in (46). In
addition, minimum of $a_{e}$ is computed by knowing $R_{S}$ and $\epsilon$
from (21). Then, the maximum tolerable amount of $\lambda_{e}$ is derived from
(48). It is seen that by tending $\lambda_{l}$ to infinity, the maximum
tolerable density of eavesdroppers tends to infinity, too. This completes the
proof. ∎ [proof of theorem 4] First, we consider the problem without the path
loss effect and analyze the four desired quantities for this case. Then, we
add the effect of path loss and update the previous bounds for this case.

The following fading vectors are in fact the simplified versions of channel
gain vectors, $\underline{g}^{l}$ and $\underline{g}^{e}$, when all the
coefficients related to path loss effect are substituted by unity:

$\displaystyle\underline{h}^{l}=(h_{1}^{l}e^{j\theta_{1}^{l}},\dots,h_{n_{r}}^{l}e^{j\theta_{n_{r}}^{l}}),$
(49)
$\displaystyle\underline{h}^{e}=(h_{1}^{e}e^{j\theta_{1}^{e}},\dots,h_{n_{r}}^{e}e^{j\theta_{n_{r}}^{e}}).$
(50)

In the following lemma, the values of the four desired quantities are given
when the path loss effect is eliminated.

###### Lemma 4

Under the assumptions noted in the paper for the fading coefficients, the mean
and the variance of $P_{l}$ and $P_{e}$ satisfy the following constraints,
when the path loss effect is eliminated:

$\displaystyle\frac{\mathbb{E}\left[P_{l}\right]}{P_{T}}$
$\displaystyle=(n_{r}-1)\mathbb{E}^{2}\left[H^{2}\right]+\mathbb{E}\left[H^{4}\right]$
$\displaystyle>(n_{r}-1)\mathbb{E}^{2}\left[H^{2}\right]+\mathbb{E}^{2}\left[H^{2}\right]=n_{r}\mathbb{E}^{2}\left[H^{2}\right],$
(51) $\displaystyle\frac{\mathbb{E}\left[P_{e}\right]}{P_{T}}$
$\displaystyle=\mathbb{E}^{2}\left[H^{2}\right],$ (52)
$\displaystyle\frac{\sigma^{2}(P_{l})}{P_{T}^{2}}$
$\displaystyle=4n_{r}\left(\mathbb{E}\left[H^{4}\right]\mathbb{E}^{2}\left[H^{2}\right]-\mathbb{E}^{4}\left[H^{2}\right]\right)+\dots=\text{{O}}\left(n_{r}\right),$
(53) $\displaystyle\frac{\sigma^{2}(P_{e})}{P_{T}^{2}}$
$\displaystyle=\frac{1}{n_{r}}\mathbb{E}^{4}\left[H^{2}\right]+\dots=\text{{O}}\left(1\right).$
(54)

###### Proof:

Analysis for mean of $P_{l}$:

$\displaystyle\frac{\mathbb{E}\left[P_{l}\right]}{P_{T}}$
$\displaystyle=\mathbb{E}\left[\left(\frac{1}{\sqrt{n_{r}}}\sum_{i=1}^{n_{r}}{(h_{i}^{l})^{2}}\right)^{2}\right]$
$\displaystyle=\frac{1}{n_{r}}\mathbb{E}\left[\sum_{i=1}^{n_{r}}\sum_{k=1}^{n_{r}}{(h_{i}^{l})^{2}(h_{k}^{l})^{2}}\right]$
$\displaystyle=\frac{1}{n_{r}}\left(n_{r}\mathbb{E}\left[H^{4}\right]+n_{r}(n_{r}-1)\mathbb{E}^{2}\left[H^{2}\right]\right)$
$\displaystyle=(n_{r}-1)\mathbb{E}^{2}\left[H^{2}\right]+\mathbb{E}\left[H^{4}\right]$
$\displaystyle>(n_{r}-1)\mathbb{E}^{2}\left[H^{2}\right]+\mathbb{E}^{2}\left[H^{2}\right]=n_{r}\mathbb{E}^{2}\left[H^{2}\right].$

Analysis for mean of $P_{e}$:

$\displaystyle\begin{split}\frac{\mathbb{E}\left[P_{e}\right]}{P_{T}}&=\mathbb{E}\left[\left|\frac{1}{\sqrt{n_{r}}}\sum_{i=1}^{n_{r}}{h_{i}^{l}h_{i}^{e}e^{j({\theta_{i}^{e}-\theta_{i}^{l}})}}\right|^{2}\right]\\\
&=\frac{1}{n_{r}}\mathbb{E}\left[\sum_{i=1}^{n_{r}}\sum_{k=1}^{n_{r}}{h_{i}^{l}h_{i}^{e}h_{k}^{l}h_{k}^{e}e^{j(\theta_{i}^{e}-\theta_{i}^{l}-\theta_{k}^{e}+\theta_{k}^{l})}}\right]\\\
&\stackrel{{\scriptstyle\text{{(a)}}}}{{=}}\frac{1}{n_{r}}\sum_{i=1}^{n_{r}}{\mathbb{E}\left[(h_{i}^{l})^{2}\right]\mathbb{E}\left[(h_{i}^{e})^{2}\right]}+\frac{n_{r}(n_{r}-1)}{n_{r}}\sum_{i=1}^{n_{r}}\sum_{k\neq
i}{\mathbb{E}\left[h_{i}^{l}h_{i}^{e}h_{k}^{l}h_{k}^{e}\right]\underbrace{\mathbb{E}\left[e^{j\theta_{i}^{e}}\right]}_{0}\mathbb{E}\left[e^{j(-\theta_{i}^{l}-\theta_{k}^{e}+\theta_{k}^{l})}\right]}\\\
&=\frac{n_{r}}{n_{r}}\mathbb{E}^{2}\left[H^{2}\right]=\mathbb{E}^{2}\left[H^{2}\right].\end{split}$

where (a) is deduced from the uniform distribution assumption for the random
phases and the independence of the fading coefficients and also the phases of
the legitimate and non-legitimate channels.

Analysis for variance of $P_{l}$:

$\displaystyle\frac{\sigma^{2}(P_{l})}{P_{T}^{2}}$
$\displaystyle=\mathbb{E}\left[\left(\frac{\left(\sum_{i=1}^{n_{r}}{(h_{i}^{l})^{2}}\right)^{2}}{n_{r}}-\left(\mathbb{E}\left[H^{4}\right]+(n_{r}-1)\mathbb{E}^{2}\left[H^{2}\right]\right)\right)^{2}\right]$
$\displaystyle=\frac{1}{n_{r}^{2}}\mathbb{E}\left[\left(\sum_{i=1}^{n_{r}}{h_{i}^{4}}+\sum_{k=1}^{n_{r}}\sum_{q\neq
k}{h_{k}^{2}h_{q}^{2}}-n_{r}\mathbb{E}\left[H^{4}\right]-n_{r}(n_{r}-1)\mathbb{E}^{2}\left[H^{2}\right]\right)^{2}\right]$
$\displaystyle=\frac{1}{n_{r}^{2}}\mathbb{E}\left[\left(\underbrace{\sum_{i=1}^{n_{r}}{h_{i}^{4}-\mathbb{E}\left[H^{4}\right]}}_{S_{1}}+\underbrace{\sum_{k=1}^{n_{r}}{\sum_{q\neq
k}{h_{k}^{2}h_{q}^{2}-\mathbb{E}^{2}\left[H^{2}\right]}}}_{S_{2}}\right)^{2}\right]$
$\displaystyle=\frac{1}{n_{r}^{2}}\left(\mathbb{E}\left[S_{1}^{2}\right]+2\mathbb{E}\left[S_{1}S_{2}\right]+\mathbb{E}\left[S_{2}^{2}\right]\right),$

where

$\displaystyle 2\mathbb{E}\left[S_{1}S_{2}\right]$
$\displaystyle\stackrel{{\scriptstyle\text{{}}}}{{=}}4n_{r}(n_{r}-1)\mathbb{E}\left[(H_{1}^{4}-\mathbb{E}\left[H^{4}\right])(H_{1}^{2}H_{2}^{2}-\mathbb{E}^{2}\left[H^{2}\right])\right]$
$\displaystyle=4n_{r}(n_{r}-1)(\mathbb{E}\left[H^{6}\right]\mathbb{E}\left[H^{2}\right]-\mathbb{E}\left[H^{4}\right]\mathbb{E}^{2}\left[H^{2}\right]),$
$\displaystyle\mathbb{E}\left[S_{1}^{2}\right]$
$\displaystyle\stackrel{{\scriptstyle\text{{}}}}{{=}}n_{r}\mathbb{E}\left[(H^{4}-\mathbb{E}\left[H^{4}\right])^{2}\right]$
$\displaystyle=n_{r}(\mathbb{E}\left[H^{8}\right]-\mathbb{E}^{2}\left[H^{4}\right]),$
$\displaystyle\mathbb{E}\left[S_{2}^{2}\right]$
$\displaystyle\stackrel{{\scriptstyle\text{{}}}}{{=}}n_{r}(n_{r}-1)(\mathbb{E}^{2}\left[H^{4}\right]-\mathbb{E}^{4}\left[H^{2}\right])+4n_{r}(n_{r}-1)(n_{r}-2)\mathbb{E}\left[(H_{1}^{2}H_{2}^{2}-\mathbb{E}^{2}\left[H^{2}\right])(H_{1}^{2}H_{3}^{2}-\mathbb{E}^{2}\left[H^{2}\right])\right]$
$\displaystyle=n_{r}(n_{r}-1)(\mathbb{E}^{2}\left[H^{4}\right]-\mathbb{E}^{4}\left[H^{2}\right])+4n_{r}(n_{r}-1)(n_{r}-2)\left(\mathbb{E}\left[H^{4}\right]\mathbb{E}^{2}\left[H^{2}\right]-\mathbb{E}^{4}\left[H^{2}\right]\right).$

Hence:

$\displaystyle\frac{\sigma^{2}(P_{l})}{P_{T}^{2}}$
$\displaystyle=\frac{1}{n_{r}^{2}}\Big{(}n_{r}(\mathbb{E}\left[H^{8}\right]-\mathbb{E}^{2}\left[H^{4}\right])+n_{r}(n_{r}-1)(\mathbb{E}^{2}\left[H^{4}\right]-\mathbb{E}^{4}\left[H^{2}\right])$
$\displaystyle\quad+4n_{r}(n_{r}-1)(n_{r}-2)\left(\mathbb{E}\left[H^{4}\right]\mathbb{E}^{2}\left[H^{2}\right]-\mathbb{E}^{4}\left[H^{2}\right]\right)$
$\displaystyle\quad+4n_{r}(n_{r}-1)(\mathbb{E}\left[H^{6}\right]\mathbb{E}\left[H^{2}\right]-\mathbb{E}\left[H^{4}\right]\mathbb{E}^{2}\left[H^{2}\right])\Big{)}$
$\displaystyle\stackrel{{\scriptstyle\text{{}}}}{{=}}\frac{4(n_{r}-1)(n_{r}-2)}{n_{r}}\Big{(}\mathbb{E}\left[H^{4}\right]\mathbb{E}^{2}\left[H^{2}\right]-\mathbb{E}^{4}\left[H^{2}\right]\Big{)}+\underbrace{\cdots}_{\text{}}.$

Analysis for variance of $P_{e}$:

$\displaystyle\frac{\sigma^{2}(P_{e})}{P_{T}^{2}}$
$\displaystyle=\mathbb{E}\left[\left(\left|\frac{1}{\sqrt{n_{r}}}\sum_{i=1}^{n_{r}}{h_{i}^{l}h_{i}^{e}e^{j({\theta_{i}^{e}-\theta_{i}^{l}})}}\right|^{2}-\mathbb{E}^{2}\left[H^{2}\right]\right)^{2}\right]$
$\displaystyle=\frac{1}{n_{r}^{2}}\mathbb{E}\left[\left(\underbrace{\sum_{i=1}^{n_{r}}{(h_{i}^{l})^{2}(h_{i}^{e})^{2}-\mathbb{E}^{2}\left[H^{2}\right]}}_{A_{1}}+\underbrace{\sum_{k=1}^{n_{r}}{\sum_{q\neq
k}{h_{k}^{l}h_{k}^{e}h_{q}^{l}h_{q}^{e}e^{j(\theta_{k}^{l}-\theta_{k}^{e}-\theta_{q}^{l}+\theta_{q}^{e})}}}}_{A_{2}}\right)^{2}\right]$
$\displaystyle=\frac{1}{n_{r}^{2}}\left(\mathbb{E}\left[A_{1}^{2}\right]+2\mathbb{E}\left[A_{1}A_{2}\right]+\mathbb{E}\left[A_{2}^{2}\right]\right),$

where

$\displaystyle\mathbb{E}\left[A_{1}^{2}\right]$
$\displaystyle\stackrel{{\scriptstyle\text{{}}}}{{=}}n_{r}\mathbb{E}\left[\left(H_{1}^{2}H_{2}^{2}-\mathbb{E}^{2}\left[H^{2}\right]\right)^{2}\right]=n_{r}\left(\mathbb{E}^{2}\left[H^{4}\right]-\mathbb{E}^{4}\left[H^{2}\right]\right),$
$\displaystyle\mathbb{E}\left[A_{2}^{2}\right]$
$\displaystyle\stackrel{{\scriptstyle\text{{}}}}{{=}}n_{r}(n_{r}-1)\mathbb{E}^{4}\left[H^{2}\right],$
$\displaystyle 2\mathbb{E}\left[A_{1}A_{2}\right]$
$\displaystyle\stackrel{{\scriptstyle\text{{}}}}{{=}}0.$

results in:

$\displaystyle\frac{\sigma^{2}(P_{e})}{P_{T}^{2}}$
$\displaystyle=\frac{n_{r}-1}{n_{r}}\mathbb{E}^{4}\left[H^{2}\right]+\frac{1}{n_{r}}\left(\mathbb{E}^{2}\left[H^{4}\right]-\mathbb{E}^{4}\left[H^{2}\right]\right)\stackrel{{\scriptstyle\text{{}}}}{{=}}\mathbb{E}^{4}\left[H^{2}\right]+\dots.$

∎

###### Corollary 3

There are positive coefficients $\eta$ and $\nu$, such that for the without
path loss case, we have:

$\displaystyle\frac{\mathbb{E}\left[P_{l}\right]}{P_{T}}$ $\displaystyle>\eta
n_{r},$ (55) $\displaystyle\frac{\mathbb{E}\left[P_{e}\right]}{P_{T}}$
$\displaystyle=\eta,$ (56) $\displaystyle\frac{\sigma^{2}(P_{l})}{P_{T}^{2}}$
$\displaystyle<{\nu^{2}}{n_{r}},$ (57)
$\displaystyle\frac{\sigma^{2}(P_{e})}{P_{T}^{2}}$ $\displaystyle<\nu^{2}.$
(58)

###### Proof:

For $\eta$ we just set

$\eta=\mathbb{E}^{2}\left[H^{2}\right]=4\mu^{2}.$ (59)

The existence of $\nu$ is proved by considering (53) and (54) and the final
expression is obtained for these two quantities and the finiteness of the
Rayleigh distribution moments. By substituting the required moments in that
final expressions, this coefficient can be chosen and it can be shown that it
is not too large. Note that these coefficients just depend on the statistical
behavior of Rayleigh distribution and its parameter and are chosen independent
of other parameters of our scheme like $R_{S}$, $\epsilon$ and $P_{T}$. ∎

Now, we prove the main results proposed in the Theorem 4, i.e., the results
for the complete model when the path loss effect is taken in to account.
First, we prove (31) and (32). The proofs of (33) and (34) are more elaborate
and needs two lemmas to be proved.

###### Proof:

Considering the geometry of the network, we have the following common bounds
for all $d_{i}^{l}$s and $d_{i}^{e}$s:

$\displaystyle d_{TR}-a_{l}<$ $\displaystyle d_{i}^{l}<d_{TR}+a_{l},$ (60)
$\displaystyle a_{e}-a_{l}<$ $\displaystyle d_{i}^{e}.$ (61)

By using these bounds, we extract the quantities related to the path loss
effect from the summations in the expressions of (29) and (30), so that the
remaining terms in the summations change to the same expressions related to
the case without considering the path loss effect. Now, using the results
stated in Corollary 3 and by considering the linearity and monotonicity of the
expected value function, (31) and (32) are simply concluded. ∎

Now we prove the two variance results ((33) and (34)). First, we present the
following lemmas.

###### Lemma 5

For any non-negative random variable $H$, with positive mean, the following
inequality is true:

$\mathbb{E}\left[H^{3}\right]\geq\mathbb{E}\left[H^{2}\right]\mathbb{E}\left[H\right].$
(62)

###### Proof:

Since $H\geq 0$, by using Cauchy-Schwartz inequality for the two random
variables ${H^{\frac{1}{2}}}$ and $H^{\frac{3}{2}}$, we can write:

$\displaystyle\mathbb{E}\left[H^{3}\right]\mathbb{E}\left[H\right]$
$\displaystyle=\mathbb{E}\left[\left(H^{3/2}\right)^{2})\right]\mathbb{E}\left[\left(H^{1/2}\right)^{2}\right]$
$\displaystyle\geq\mathbb{E}^{2}\left[H^{2}\right]\geq\mathbb{E}\left[H^{2}\right]\mathbb{E}^{2}\left[H\right].$

Now, considering its positivity, we divide the above relations by
$\mathbb{E}\left[H\right]$ to obtain the inequality (62). ∎

###### Lemma 6

For every two i.i.d. random variables $X$ and $Y$ with positive mean and
variance and for any two positive constants $a$ and $b$ such that $a<b$, the
following inequality is true:

$\text{Var}[(aX+bY)^{2}]<b^{4}\text{Var}[(X+Y)^{2}].$ (63)

###### Proof:

By expanding the left side, we show that substituting $a$ by $b$ will increase
the variance.

$\displaystyle\text{Var}[(aX+bY)^{2}]=$
$\displaystyle\text{Var}[a^{2}X^{2}+b^{2}Y^{2}+2abXY]$ $\displaystyle=$
$\displaystyle\mathbb{E}\left[\left(a^{2}(X^{2}-\mathbb{E}\left[X^{2}\right])+b^{2}(Y^{2}-\mathbb{E}\left[Y^{2}\right])+2ab(XY-\mathbb{E}\left[XY\right])\right)^{2}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[a^{4}(X^{2}-\mathbb{E}\left[X^{2}\right])^{2}\right]+\mathbb{E}\left[b^{4}(Y^{2}-\mathbb{E}\left[Y^{2}\right])^{2}\right]+\mathbb{E}\left[4a^{2}b^{2}(XY-\mathbb{E}\left[XY\right])^{2}\right]$
$\displaystyle+2a^{2}b^{2}\mathbb{E}\left[(X^{2}-\mathbb{E}\left[X^{2}\right])(Y^{2}-\mathbb{E}\left[Y^{2}\right])\right]+4a^{3}b\mathbb{E}\left[(X^{2}-\mathbb{E}\left[X^{2}\right])(XY-\mathbb{E}\left[XY\right])\right]$
$\displaystyle+4ab^{3}\mathbb{E}\left[(Y^{2}-\mathbb{E}\left[Y^{2}\right])(XY-\mathbb{E}\left[XY\right])\right].$

In the last equality, the three first terms are clearly non-negative and
increasing the coefficients, will increase the total result. So, substituting
$a$ by $b$ increases the Variance. According to the independence assumption,
the forth term can be decomposed to two expected value terms, which both of
them are zero. The fifth and the sixth sentence have a similar form. We show
below that the fifth term is always positive. A similar argument is true for
the sixth term.

$\displaystyle\mathbb{E}\left[(X^{2}-\mathbb{E}\left[X^{2}\right])(XY-\mathbb{E}\left[XY\right])\right]$
$\displaystyle\stackrel{{\scriptstyle\text{{(a)}}}}{{=}}\mathbb{E}\left[X^{3}\right]\mathbb{E}\left[Y\right]-\mathbb{E}\left[X^{2}\right]\mathbb{E}\left[X\right]\mathbb{E}\left[Y\right]$
$\displaystyle=\mathbb{E}\left[Y\right]\left(\mathbb{E}\left[X^{3}\right]-\mathbb{E}\left[X^{2}\right]\mathbb{E}\left[X\right]\right)\stackrel{{\scriptstyle\text{(b)}}}{{>}}0.$

where (a) is deduced from the independence assumption; (b) is concluded from
Lemma 5 and the positivity of the mean of $Y$. So, the fifth and also the
sixth sentence are positive and therefore all the six sentences have a non-
negative value. Hence, replacing $a$ by $b$ will increase the amount of the
variance and the validity of (63) is established. ∎

###### Proof:

Using induction, the recent lemma can be generalized to any number of random
variables. Considering the independence of the fading coefficients and their
Rayleigh distribution and using the inequalities (60) and (61), the
generalization of Lemma 6 results in (33) and (34). ∎

## References

  * [1] M. Bloch and J. Barros, _Physical-layer security: from information theory to security engineering_ , 2011.
  * [2] A. D. Wyner, “The wire-tap channel,” _Bell System Technical Journal, The_ , vol. 54, no. 8, pp. 1355–1387, 1975.
  * [3] A. Mukherjee, S. A. Fakoorian, J. Huang, A. L. Swindlehurst _et al._ , “Principles of physical layer security in multiuser wireless networks: A survey,” _Communications Surveys & Tutorials, IEEE_, vol. 16, no. 3, pp. 1550–1573, 2014.
  * [4] P. Gupta and P. R. Kumar, “The capacity of wireless networks,” _IEEE Trans. Inf. Theory_ , vol. 46, no. 2, pp. 388–404, Mar. 2000.
  * [5] O. O. Koyluoglu, C. E. Koksal, and H. E. Gamal, “On secrecy capacity scaling in wireless networks,” _Information Theory, IEEE Transactions on_ , vol. 58, no. 5, pp. 3000–3015, 2012.
  * [6] L.-L. Xie and P. R. Kumar, “A network information theory for wireless communications: Scaling laws and optimal operation,” _IEEE Trans. Inf. Theory_ , vol. 50, no. 5, pp. 748–767, May 2004.
  * [7] M. Mirmohseni and P. Papadimitratos, “Scaling laws for secrecy capacity in cooperative wireless networks,” in _INFOCOM, 2014 Proceedings IEEE_ , 2014, pp. 1527–1535.
  * [8] X. Zhang, W. Cheng, and H. Zhang, “Full-duplex transmission in phy and mac layers for 5g mobile wireless networks,” _Wireless Communications, IEEE_ , vol. 22, no. 5, pp. 112–121, 2015.
  * [9] D. Goeckel, S. Vasudevan, D. Towsley, S. Adams, Z. Ding, and K. Leung, “Artificial noise generation from cooperative relays for everlasting secrecy in two-hop wireless networks,” _Selected Areas in Communications, IEEE Journal on_ , vol. 29, no. 10, pp. 2067–2076, 2011.
  * [10] A. Sheikholeslami, D. Goeckel, H. Pishro-Nik, and D. Towsley, “Physical layer security from inter-session interference in large wireless networks,” in _INFOCOM, 2012 Proceedings IEEE_ , 2012, pp. 1179–1187.
  * [11] Ç. Çapar, D. Goeckel, B. Liu, and D. Towsley, “Secret communication in large wireless networks without eavesdropper location information,” in _INFOCOM, 2012 Proceedings IEEE_ , 2012, pp. 1152–1160.
  * [12] Ç. Çapar and D. Goeckel, “Network coding for facilitating secrecy in large wireless networks,” in _Information Sciences and Systems (CISS), 2012 46th Annual Conference on_ , 2012, pp. 1–6.
  * [13] S. Vasudevan, D. Goeckel, and D. F. Towsley, “Security-capacity trade-off in large wireless networks using keyless secrecy,” in _Proceedings of the eleventh ACM international symposium on Mobile ad hoc networking and computing_ , 2010, pp. 21–30.
  * [14] J. Zhang, L. Fu, and X. Wang, “Asymptotic analysis on secrecy capacity in large-scale wireless networks,” _IEEE/ACM Transactions on Networking (TON)_ , vol. 22, no. 1, pp. 66–79, 2014.
  * [15] M. Schwartz, _Mobile wireless communications_ , 2004.
  * [16] A. Goldsmith, _Wireless communications_ , 2005.
  * [17] S. Shafiee and S. Ulukus, “Achievable rates in gaussian MISO channels with secrecy constraints,” in _Information Theory, 2007. ISIT 2007. IEEE International Symposium on_ , 2007, pp. 2466–2470.


# Online Signal Recovery via Heavy Ball Kaczmarz

Benjamin Jarman1, Yotam Yaniv1, Deanna Needell1  1Department of Mathematics,
University of California, Los Angeles
{bjarman, yotamya<EMAIL_ADDRESS>
###### Abstract

Recovering a signal $x^{\ast}\in\mathbb{R}^{n}$ from a sequence of linear
measurements is an important problem in areas such as computerized tomography
and compressed sensing. In this work, we consider an online setting in which
measurements are sampled one-by-one from some source distribution. We propose
solving this problem with a variant of the Kaczmarz method with an additional
heavy ball momentum term. A popular technique for solving systems of linear
equations, recent work has shown that the Kaczmarz method also enjoys linear
convergence when applied to random measurement models, however convergence may
be slowed when successive measurements are highly coherent. We demonstrate
that the addition of heavy ball momentum may accelerate the convergence of the
Kaczmarz method when data is coherent, and provide a theoretical analysis of
the method culminating in a linear convergence guarantee for a wide class of
source distributions.

##  I Introduction

###  I-A The Kaczmarz Method

Recovering a signal $x^{\ast}\in\mathbb{R}^{n}$ from a collection of linear
measurements is an important problem in computerized tomography [1], sensor
networks [2], compressive sensing [3, 4], machine learning subroutines [5],
and beyond. When the collection of linear measurements is finite, say of size
$m$, and accessible at any time, the problem is equivalent to solving a system
of linear equations $Ax=b$ with $A\in\mathbb{R}^{m\times n}$ and
$b\in\mathbb{R}^{m}$, which has been well-studied. A popular method for
solving this classical problem is the Kaczmarz method [6]: beginning with an
initial iterate $x_{0}$, at each iteration a row of the system is sampled and
the previous iterate is projected onto the hyperplane defined by the solution
space given by that row. More precisely, if the row $a_{i}^{\top}x=b_{i}$ is
sampled at iteration $k$, the update has the form

$x_{k}=x_{k-1}-\frac{\langle a_{i},x_{k-1}\rangle-
b_{i}}{\left\|a_{i}\right\|^{2}}a_{i}.$

The original method proposed cycling through rows in order, such that
$i=k\text{ mod }m$. In [7] it was observed empirically that randomized row
selection accelerates convergence, and in the landmark work [8] it was proven
that selecting rows at random with probability proportional to their Euclidean
norm yields linear convergence in expectation.

In this work, we consider an online model in which at each discrete time
$t=1,2,\dots$ a linear measurement
$(\varphi_{t},y_{t})\in\mathbb{R}^{n}\times\mathbb{R}$ is received. We assume
that each measurement is noiseless, i.e.
$\langle\varphi_{t},x^{\ast}\rangle=y_{t}$ for all $t$, and that measurements
are _streamed_ through memory and are not stored. Note that the linear system
setting described above is a special case of this model, but we now allow for
measurements to be sampled from a more general source. The Kaczmarz method is
well-suited to this setting as it requires access to only a single measurement
at each iteration. See, for example, [9], where measurement data is viewed as
being sampled i.i.d. from some distribution $\mathcal{D}$ on $\mathbb{R}^{n}$.
We assume the noiseless, i.i.d. setting throughout this paper. A Kaczmarz
update in this setting has the following form, when initialized with some
arbitrary $x_{0}$: at discrete times $t=1,2,\dots$, a measurement
$(\varphi_{t},y_{t})\in\mathbb{R}^{n}\times\mathbb{R}$ is received, where
$\varphi_{t}\sim\mathcal{D}$, and a Kaczmarz iteration is computed

$x_{t}=x_{t-1}-\frac{\langle\varphi_{t},x_{t-1}\rangle-
y_{t}}{\left\|\varphi_{t}\right\|^{2}}\varphi_{t}.$

In [9] it was shown that under certain conditions on $\mathcal{D}$, the method
enjoys linear convergence in expectation. Further related works have placed
online Kaczmarz in the context of learning theory [10], and have analyzed
sparse online variants [11, 12]. Random vector models have also appeared in
analyses of Kaczmarz methods for phase retrieval [13] and for sparsely
corrupted data [14].

###  I-B Heavy Ball Momentum

Heavy ball momentum is a popular addition to gradient descent methods, in
which an additional step is taken in the direction of the previous iteration’s
movement. Proposed initially in [15], it has proven very popular in machine
learning [16, 17, 18, 19], with a guarantee of linear convergence for
stochastic gradient methods with heavy ball momentum proven in [20] (improving
on earlier sublinear guarantees in [21, 22]). A gradient descent method itself
[23], the Kaczmarz method may be modified with heavy ball momentum to give
updates of the following form:

$x_{t+1}=x_{t}-\frac{\langle\varphi_{t},x_{t}\rangle-
y_{t}}{\left\|\varphi_{t}\right\|^{2}}\varphi_{t}+\beta(x_{t}-x_{t-1}),$

where $\beta\geq 0$ is a momentum parameter. In [20] it was shown that when
applied to a linear system (i.e., when each $\varphi_{t}$ is sampled from the
rows of a matrix $A$), the Kaczmarz method with heavy ball momentum converges
linearly in expectation. Experimental results indicate accelerated convergence
compared to the standard Kaczmarz method on a range of datasets, while the
momentum term does not affect the order of the computational cost.

In this work, we propose an _online_ variant of the Kaczmarz method with heavy
ball momentum. We prove that our method converges linearly in expectation for
a wide range of distributions $\mathcal{D}$, and offer particular examples.
This theory is supported by numerical experiments on both synthetic and real-
world data, which in particular demonstrate the benefits of adding momentum
when measurements are highly coherent.

##  II Proposed Method & Empirical Results

We propose an online variant of the Kaczmarz method, modified to include a
heavy ball momentum term $\beta\in(0,1)$, which we call OHBK($\beta$) (see
Algorithm 1). We note that our method is a generalization of the momentum
Kaczmarz method for systems of linear equations introduced in [20]. The method
requires only a single measurement to be held in storage at a time, while
leveraging information about previous measurements through the momentum term.

Algorithm 1 Online Heavy Ball Kaczmarz

1:procedure OHBK($\beta$) (Input: initial iterate $x_{0}$, measurements
$\\{(\varphi_{t},y_{t})\\}_{t=1}^{\infty}$, momentum parameter $\beta$ )

2: Set $x_{1}=x_{0}$

3: for $t=1,2,\dots$ do

4: Update $x_{t+1}=x_{t}-\frac{\langle\varphi_{t},x_{t}\rangle-
y_{t}}{\left\|\varphi_{t}\right\|^{2}}\varphi_{t}+\beta(x_{t}-x_{t-1})$

5: end for

6:end procedure

We test our method on synthetic and real-world data. For each data source, we
compare our method OHBK($\beta$) for a variety of $\beta$ to an online
Kaczmarz method without momentum, which we denote by OK (equivalently,
OHBK($0$)).

We first experiment on synthetic data. We sample $x^{\ast}\in\mathbb{R}^{50}$
with standard Gaussian entries, and take $\\{\varphi_{t}\\}_{t=1}^{\infty}$ to
be vectors of length 50 with $U[0,1]$ entries. We note that this process
produces particularly coherent data, that is, the vectors
$\\{\varphi_{t}\\}_{t=1}^{\infty}$ have small pairwise inner products. Each
$y_{t}$ is then computed as $y_{t}=\langle\varphi_{t},x^{\ast}\rangle$ to
ensure measurements are noiseless. In Figure 2 we perform a parameter search
over 100 trials for $\beta$ and plot the median error after 100 iterations
versus $\beta$ with shading for the 25th through 75th percentiles. Introducing
some amount of momentum provides an acceleration, however, taking $\beta$ to
be too large places too much weight on previous information and is less
effective. In Figure 1 we show convergence down to machine epsilon of
OHBK($\beta$) versus online randomized Kaczmarz (i.e. OHBK($0$)) for a
selection of $\beta$ (averaging over 10 trials), and the acceleration provided
by momentum is clear.

In Figure 3, we investigate the effect of momentum on highly coherent systems
further. We perform $4000$ iterations of OHBK($\beta$) on $U[\varepsilon,1]$
signals of length $50$, for $\varepsilon\in[0,1]$, for a range of momentum
parameters $\beta$ (again averaged over 10 trials). We see that momentum
provides a significant speedup in convergence even for highly coherent systems
(i.e. for large $\epsilon$). However, as $\epsilon\to 1$, recovering the
signal becomes intractable.

We compare the effect of the signal length $n$ on the optimal momentum
parameter $\beta$ in Figure 4. We perform parameter searches for signals of
length $n\in\\{50,100,500,1000\\}$ and mark the optimal values of $\beta$. The
optimal choice of $\beta$ does not appear to vary significantly with $n$.

In Figure 5 we use a system generated from the Wisconsin Diagnostic Breast
Cancer (WDBC) dataset, where each measurement is computed from a digitized
image of a fine needle aspirate of a breast mass and describes characteristics
of the cell nuclei present [24]. We stream through each measurement of the
699-row, 10-feature dataset once to replicate the online model, and again see
that the addition of momentum provides a noteworthy acceleration to
convergence.

Figure 1: Error versus iteration for OHBK($\beta$) applied to $U[0,1]$ signals
of length 50. Figure 2: $\left\|x_{100}-x^{\ast}\right\|$ versus $\beta$ for a
range of $\beta\in[0,0.6]$, for $U[0,1]$ signals of length 50. Figure 3:
$\log\left\|x_{4000}-x^{\ast}\right\|$ versus $\varepsilon$ for OHBK($\beta$)
applied to $U[\varepsilon,1]$ signals of length 50. Figure 4:
$\log\left\|x_{4000}-x^{\ast}\right\|$ versus $\beta$ for OHBK($\beta$)
applied to $U[0,1]$ signals of length $n$. The gray verticals show the value
of $\beta$ yielding the minimum error. Figure 5: Error versus iteration for
OHBK($\beta$) applied to the WDBC dataset.

##  III Theoretical Results

Throughout our theory, we assume that $\\{\varphi_{t}\\}_{t=1}^{\infty}$ is a
sequence of independent samples from some distribution $\mathcal{D}$. We
provide a general linear convergence (in expectation) result with a rate
depending on the matrix
$W:=\mathbb{E}_{\mathcal{D}}\left[\frac{\varphi\varphi^{\top}}{\left\|\varphi\right\|^{2}}\right]$,
in particular on its smallest and largest singular values
$\sigma_{\mathrm{min}}(W)$ and $\sigma_{\mathrm{max}}(W)$.

######  Theorem 1 (Convergence in Expectation of OHBRK).

Suppose that measurement vectors $\\{\varphi_{t}\\}_{t=1}^{\infty}$ are
sampled independently from $\mathcal{D}$, and
$W=\mathbb{E}_{\mathcal{D}}\left[\frac{\varphi\varphi^{\top}}{\left\|\varphi\right\|^{2}}\right]$.
Then if $\beta$ is small enough such that

$4\beta+4\beta^{2}-(1+\beta)\sigma_{\mathrm{min}}(W)+\beta\sigma_{\mathrm{max}}(W)<0,$

the iterates produced by OHBK($\beta$) satisfy the following guarantee: for
some $\delta>0$, $q\in(0,1)$, we have

$\mathbb{E}[\left\|x_{t}-x^{\ast}\right\|^{2}]\leq
q^{t}(1+\delta)\left\|x_{0}-x^{\ast}\right\|^{2}.$

More interpretable conditions on $\beta$ may be obtained for particular
classes of distribution $\mathcal{D}$. In particular, if
$\varphi/\left\|\varphi\right\|$ is distributed uniformly on the unit sphere
(which is the case if $\mathcal{D}$ itself is the uniform distribution on the
unit sphere, or if $\mathcal{D}$ is the standard $n$-dimensional Gaussian),
then $W=\frac{1}{n}I$ and we require

$\beta+\beta^{2}<\frac{1}{4n}$

to guarantee linear convergence in expectation.

##  IV Proof of Main Result

In this section we prove Theorem 1 by following the steps of ([20], Theorem
1), making modifications for the online case and simplifications to some of
the constants for our special case. First we present a lemma from [20] which
we will use in our convergence proof.

######  Lemma 2 ([20], Lemma 9).

Let $\\{F_{t}\\}_{t\geq 0}$ be a sequence of non-negative real numbers with
$F_{0}=F_{1}$ that satisfies the relation $F_{t+1}\leq
a_{1}F_{t}+a_{2}F_{t-1}$ for all $t\geq 1$, with $a_{2}>0$ and
$a_{1}+a_{2}<1$. Then the following inequality hold for all $t\geq 1$

$F_{t+1}\leq q^{t}(1+\delta)F_{0},$

where $q=\frac{a_{1}+\sqrt{a_{1}^{2}+4a_{2}}}{2}<1$, $\delta=q-a_{1}$ and
$q\leq a_{1}+a_{2}$.

A proof of this lemma can be found in [20].

We begin our convergence analysis by writing the squared $L2$ error at the
$(t+1)$th iteration and substituting the OHBK($\beta$) update into it,

$\displaystyle\left\|x_{t+1}-x^{\ast}\right\|^{2}=\left\|x_{t}-\frac{\langle\varphi_{t},x_{t}\rangle-
y_{t}}{\left\|\varphi_{t}\right\|^{2}}\varphi_{t}+\beta(x_{t}-x_{t-1})-x^{\ast}\right\|^{2}.$

Next, we group our equation into three terms:

$\displaystyle\begin{split}\left\|x_{t+1}-x^{\ast}\right\|^{2}&=\left\|x_{t}-x^{\ast}-\frac{\langle\varphi_{t},x_{t}\rangle-
y_{t}}{\left\|\varphi_{t}\right\|^{2}}\varphi_{t}\right\|^{2}\\\
+&\beta^{2}\left\|x_{t}-x_{t-1}\right\|^{2}\\\ +&2\beta\langle
x_{t}-x^{\ast}-\frac{\langle\varphi_{t},x_{t}\rangle-
y_{t}}{\left\|\varphi_{t}\right\|^{2}}\varphi_{t},x_{t}-x_{t-1}\rangle\end{split}$
(1)

We bound the first term of Equation 1 by following a standard Kaczmarz
convergence argument and the fact that
$y_{t}=\langle\varphi_{t},x^{\ast}\rangle$. We have that

$\displaystyle\left\|x_{t}-x^{\ast}-\frac{\langle\varphi_{t},x_{t}\rangle-
y_{t}}{\left\|\varphi_{t}\right\|^{2}}\varphi_{t}\right\|^{2}$
$\displaystyle=$
$\displaystyle\left\|x_{t}-x^{\ast}\right\|^{2}+\left\|\frac{\langle\varphi_{t},x_{t}\rangle-
y_{t}}{\left\|\varphi_{t}\right\|^{2}}\varphi_{t}\right\|^{2}-$
$\displaystyle\qquad 2\left\langle\frac{\langle\varphi_{t},x_{t}\rangle-
y_{t}}{\left\|\varphi_{t}\right\|^{2}}\varphi_{t},x_{t}-x^{\ast}\right\rangle$
$\displaystyle=$
$\displaystyle\left\|x_{t}-x^{\ast}\right\|^{2}+\frac{(\langle\varphi_{t},x_{t}\rangle-
y_{t})^{2}}{\left\|\varphi_{t}\right\|^{2}}-2\frac{(\langle\varphi_{t},x_{t}\rangle-
y_{t})^{2}}{\left\|\varphi_{t}\right\|^{2}}$ $\displaystyle=$
$\displaystyle\left\|x_{t}-x^{\ast}\right\|^{2}-\frac{(\langle\varphi_{t},x_{t}\rangle-
y_{t})^{2}}{\left\|\varphi_{t}\right\|^{2}}.$

We bound the second term of Equation 1 by first adding and subtracting
$x^{\ast}$

$\displaystyle\beta^{2}\left\|x_{t}-x_{t-1}\right\|^{2}=\beta^{2}\left\|(x_{t}-x^{\ast})+(x^{\ast}-x_{t-1})\right\|^{2}.$

Then by applying the fact that $\left\|a+b\right\|^{2}\leq
2\left\|a\right\|^{2}+2\left\|b\right\|^{2}$ we have that

$\displaystyle\beta^{2}\left\|(x_{t}-x^{\ast})+(x^{\ast}-x_{t-1})\right\|^{2}$
$\displaystyle\leq
2\beta^{2}\left\|x_{t}-x^{\ast}\right\|^{2}+2\beta^{2}\left\|x_{t-1}-x^{\ast}\right\|.$

Thus we have that

$\displaystyle\beta^{2}\left\|x_{t}-x_{t-1}\right\|^{2}\leq
2\beta^{2}\left\|x_{t}-x^{\ast}\right\|^{2}+2\beta^{2}\left\|x_{t-1}-x^{\ast}\right\|.$

Finally we bound the third term of Equation 1 as

$\displaystyle 2\beta\left\langle
x_{t}-x^{\ast}-\frac{\langle\varphi_{t},x_{t}\rangle-
y_{t}}{\left\|\varphi_{t}\right\|^{2}}\varphi_{t},x_{t}-x_{t-1}\right\rangle=$
$\displaystyle\qquad 2\beta\langle x_{t}-x^{\ast},x_{t}-x_{t-1}\rangle+$
$\displaystyle\qquad 2\beta\left\langle\frac{\langle\varphi_{t},x_{t}\rangle-
y_{t}}{\left\|\varphi_{t}\right\|^{2}}\varphi_{t},x_{t-1}-x_{t}\right\rangle$
$\displaystyle=2\beta\left\|x_{t}-x^{\ast}\right\|^{2}+2\beta\langle
x_{t}-x^{\ast},x^{\ast}-x_{t-1}\rangle+$ $\displaystyle\qquad
2\beta\left\langle\frac{\langle\varphi_{t},x_{t}\rangle-
y_{t}}{\left\|\varphi_{t}\right\|^{2}}\varphi_{t},x_{t-1}-x_{t}\right\rangle$
$\displaystyle=\beta\left\|x_{t}-x^{\ast}\right\|^{2}+\beta\left\|x_{t}-x_{t-1}\right\|^{2}-\beta\left\|x_{t-1}-x^{\ast}\right\|^{2}+$
$\displaystyle\qquad 2\beta\left\langle\frac{\langle\varphi_{t},x_{t}\rangle-
y_{t}}{\left\|\varphi_{t}\right\|^{2}}\varphi_{t},x_{t-1}-x_{t}\right\rangle$
$\displaystyle\leq\beta\left\|x_{t}-x^{\ast}\right\|^{2}+\beta\left\|x_{t}-x_{t-1}\right\|^{2}-\beta\left\|x_{t-1}-x^{\ast}\right\|^{2}-$
$\displaystyle\qquad\beta\langle\frac{\langle\varphi_{t},x_{t}\rangle-
y_{t}}{\left\|\varphi_{t}\right\|^{2}}\varphi_{t},x_{t}-x^{\ast}\rangle+$
$\displaystyle\qquad\beta\langle\frac{\langle\varphi_{t},x_{t-1}\rangle-
y_{t}}{\left\|\varphi_{t}\right\|^{2}}\varphi_{t},x_{t-1}-x^{\ast}\rangle.$

Combining the three bounds, we have

$\displaystyle\left\|x_{t+1}-x^{\ast}\right\|^{2}\leq\left\|x_{t}-x^{\ast}\right\|^{2}-\frac{(\langle\varphi_{t},x_{t}\rangle-
y_{t})^{2}}{\left\|\varphi_{t}\right\|^{2}}$ $\displaystyle+$ $\displaystyle
2\beta^{2}\left\|x_{t}-x^{\ast}\right\|^{2}+2\beta^{2}\left\|x_{t-1}-x^{\ast}\right\|^{2}$
$\displaystyle+$
$\displaystyle\beta\left\|x_{t}-x^{\ast}\right\|^{2}+\beta\left\|x_{t}-x_{t-1}\right\|^{2}-\beta\left\|x_{t-1}-x^{\ast}\right\|^{2}-$
$\displaystyle\qquad\beta\langle\frac{\langle\varphi_{t},x_{t}\rangle-
y_{t}}{\left\|\varphi_{t}\right\|^{2}}\varphi_{t},x_{t}-x^{\ast}\rangle+$
$\displaystyle\qquad\beta\langle\frac{\langle\varphi_{t},x_{t-1}\rangle-
y_{t}}{\left\|\varphi_{t}\right\|^{2}}\varphi_{t},x_{t-1}-x^{\ast}\rangle.$

Simplifying and grouping like terms we have

$\displaystyle\left\|x_{t+1}-x^{\ast}\right\|^{2}\leq(1+2\beta^{2}+\beta)\left\|x_{t}-x^{\ast}\right\|^{2}+$
$\displaystyle\qquad(2\beta^{2}-\beta)\left\|x_{t-1}-x^{\ast}\right\|^{2}-$
$\displaystyle\qquad\frac{(\langle\varphi_{t},x_{t}\rangle-
y_{t})^{2}}{\left\|\varphi_{t}\right\|^{2}}+\beta\left\|x_{t}-x_{t-1}\right\|^{2}-$
$\displaystyle\qquad\beta\langle\frac{\langle\varphi_{t},x_{t}\rangle-
y_{t}}{\left\|\varphi_{t}\right\|^{2}}\varphi_{t},x_{t}-x^{\ast}\rangle+$
$\displaystyle\qquad\beta\langle\frac{\langle\varphi_{t},x_{t-1}\rangle-
y_{t}}{\left\|\varphi_{t}\right\|^{2}}\varphi_{t},x_{t-1}-x^{\ast}\rangle.$

Applying the simplification for the second term of Equation 1 and simplifying
the inner products, we have

$\displaystyle\left\|x_{t+1}-x^{\ast}\right\|^{2}\leq(1+2\beta^{2}+3\beta)\left\|x_{t}-x^{\ast}\right\|^{2}+$
$\displaystyle\qquad(2\beta^{2}+\beta)\left\|x_{t-1}-x^{\ast}\right\|^{2}-$
$\displaystyle\qquad(\beta+1)\frac{\langle\varphi_{t},x_{t}-x^{\ast}\rangle^{2}}{\left\|\varphi_{t}\right\|^{2}}+$
$\displaystyle\qquad\beta\frac{\langle\varphi_{t},x_{t-1}-x^{\ast}\rangle^{2}}{\left\|\varphi_{t}\right\|^{2}}.$

Taking an expectation over our signal of our simplified equation

$\displaystyle\mathbb{E}[\left\|x_{t+1}-x^{\ast}\right\|^{2}]\leq(1+2\beta^{2}+3\beta)\left\|x_{t}-x^{\ast}\right\|^{2}+$
$\displaystyle\qquad(2\beta^{2}+\beta)\left\|x_{t-1}-x^{\ast}\right\|^{2}-$
$\displaystyle\qquad(\beta+1)\mathbb{E}[\frac{(\langle\varphi_{t},x_{t}-x^{\ast}\rangle)^{2}}{\left\|\varphi_{t}\right\|^{2}}]+$
$\displaystyle\qquad\beta\mathbb{E}[\frac{(\langle\varphi_{t},x_{t-1}-x^{\ast}\rangle)^{2}}{\left\|\varphi_{t}\right\|^{2}}]$
$\displaystyle=(1+2\beta^{2}+3\beta)\left\|x_{t}-x^{\ast}\right\|^{2}+$
$\displaystyle\qquad(2\beta^{2}+\beta)\left\|x_{t-1}-x^{\ast}\right\|^{2}-$
$\displaystyle\qquad(1+\beta)(x_{t}-x^{\ast})^{T}\mathbb{E}\left[\frac{\varphi_{t}\varphi_{t}^{T}}{\left\|\varphi_{t}\right\|^{2}}\right](x_{t}-x^{\ast})+$
$\displaystyle\qquad\beta(x_{t-1}-x^{\ast})^{T}\mathbb{E}\left[\frac{\varphi_{t}\varphi_{t}^{T}}{\left\|\varphi_{t}\right\|^{2}}\right](x_{t-1}-x^{\ast}).$

Let
$W:=\mathbb{E}\left[\frac{\varphi_{t}\varphi_{t}^{T}}{\left\|\varphi_{t}\right\|^{2}}\right]$.
We can then bound the above in terms of the largest and smallest singular
values of $W$:

$\displaystyle\mathbb{E}[\left\|x_{t+1}-x^{\ast}\right\|^{2}]\leq(1+2\beta^{2}+3\beta)\left\|x_{t}-x^{\ast}\right\|^{2}+$
$\displaystyle\qquad(2\beta^{2}+\beta)\left\|x_{t-1}-x^{\ast}\right\|^{2}-$
$\displaystyle\qquad(1+\beta)\sigma_{\min}(W)\left\|x_{t}-x^{\ast}\right\|^{2}+$
$\displaystyle\qquad\beta\sigma_{\max}(W)\left\|x_{t-1}-x^{\ast}\right\|^{2}$
$\displaystyle=(1+2\beta^{2}+3\beta-(1+\beta)\sigma_{\min}(W))\left\|x_{t}-x^{\ast}\right\|^{2}+$
$\displaystyle\qquad(2\beta^{2}+\beta+\beta\sigma_{\max}(W))\left\|x_{t-1}-x^{\ast}\right\|^{2}.$

Finally, we apply Lemma 2, wherein the two coefficients are given by
$a_{1}=1+2\beta^{2}+3\beta-(1+\beta)\sigma_{\min}(W)$ and
$a_{2}=2\beta^{2}+\beta+\beta\sigma_{\max}(W)$. Since we assumed that
$a_{1}+a_{2}=1+4\beta^{2}+4\beta+(1+\beta)\sigma_{\min}(W)+\beta\sigma_{\max}(W)<1$
and since $\beta>0$ then $a_{2}=2\beta^{2}+\beta+\beta\sigma_{\max}(W)>0$ thus
the assumptions for Lemma 2 hold, so we have that

$\mathbb{E}[\left\|x_{t}-x^{\ast}\right\|^{2}]\leq
q^{t}(1+\delta)\left\|x_{0}-x^{\ast}\right\|^{2}$

where $q=\frac{a_{1}+\sqrt{a_{1}^{2}+4a_{1}}}{2}$, $\delta=q-a_{1}$ and
$a_{1}+a_{2}\leq q<1$. Since $q\in(0,1)$ we have shown that the norm squared
error of the iterates produced by OHBK($\beta$) converges linearly in
expectation.

##  V Conclusion and Future Directions

In this work we discuss using a Kaczmarz method variant with momentum to solve
an online signal recovery problem. We leverage a heavy ball momentum term, a
classical acceleration method, to improve the convergence rate. We prove a
theoretical convergence rate for OHBK($\beta$), and verify this convergence
empirically on both synthetic and real-world data. We demonstrate empirically
that for coherent measurements, the addition of momentum indeed accelerates
convergence, and provided some initial exploration into the dependence of the
convergence rate on the signal length $n$ and momentum strength $\beta$.

It is notable that in our convergence analysis, we did not recover a
theoretically optimal value for $\beta$. Doing so, and comparing this value to
empirically best values, would be an interesting future direction.
Furthermore, we would like to obtain theoretical parameter relationships: for
example, how the optimal momentum strength depends on the signal length and
coherency of the measurements. It may in fact be optimal to adaptively adjust
the momentum parameter across iterations based on the current iterate and
properties of incoming measurements. Additionally, we would like to leverage
other accelerated gradient methods such as ADAM [25]. Finally, we would like
to consider solving the online signal recovery problem in the case where each
measurement is no longer exact, but instead contains some amount of noise
[26]. This could be achieved, for example, using relaxation.

## Acknowledgments

BJ and DN were partially supported by NSF DMS-2108479, YY and DN were
partially supported by NSF DMS-2011140.

## References

  * [1] F. Natterer, _The mathematics of computerized tomography_. SIAM, 2001.
  * [2] A. Savvides, C.-C. Han, and M. B. Strivastava, “Dynamic fine-grained localization in ad-hoc networks of sensors,” in _Proceedings of the 7th annual international conference on mobile computing and networking_ , 2001, pp. 166–179.
  * [3] Y. Eldar and G. Kutyniok, _Compressed Sensing: Theory and Applications_. Cambridge University Press, 2012.
  * [4] S. Foucart and H. Rauhut, _A Mathematical Introduction to Compressive Sensing_. Birkhäuser Basel, 2013.
  * [5] L. Bottou, “Large-scale machine learning with stochastic gradient descent,” in _COMPSTAT_ , 2010.
  * [6] S. Kaczmarz, “Angenäherte Auflösung von Systemen linearer Gleichungen,” _Bull. Internat. Acad. Polon.Sci. Lettres A_ , pp. 335–357, 1937.
  * [7] G. Herman and L. Meyer, “Algebraic reconstruction techniques can be made computationally efficient (positron emission tomography application),” _IEEE Transactions on Medical Imaging_ , vol. 12, no. 3, pp. 600–609, 1993\.
  * [8] T. Strohmer and R. Vershynin, “A randomized Kaczmarz algorithm with exponential convergence,” _Journal of Fourier Analysis and Applications_ , vol. 15, no. 2, pp. 262–278, 2009.
  * [9] X. Chen and A. Powell, “Almost Sure Convergence of the Kaczmarz Algorithm with Random Measurements,” _Journal of Fourier Analysis and Applications_ , vol. 18, 12 2012.
  * [10] J. Lin and D.-X. Zhou, “Learning Theory of Randomized Kaczmarz Algorithm,” _J. Mach. Learn. Res._ , vol. 16, no. 1, p. 3341–3365, 2015.
  * [11] Y. Lei and D.-X. Zhou, “Learning Theory of Randomized Sparse Kaczmarz Method,” _SIAM Journal on Imaging Sciences_ , vol. 11, no. 1, pp. 547–574, 2018.
  * [12] D. A. Lorenz, S. Wenger, F. Schöpfer, and M. A. Magnor, “A sparse Kaczmarz solver and a linearized Bregman method for online compressed sensing,” _2014 IEEE International Conference on Image Processing (ICIP)_ , pp. 1347–1351, 2014.
  * [13] Y. S. Tan and R. Vershynin, “Phase retrieval via randomized Kaczmarz: theoretical guarantees,” _Information and Inference: A Journal of the IMA_ , vol. 8, pp. 97–123, 2018.
  * [14] J. Haddock, D. Needell, E. Rebrova, and W. Swartworth, “Quantile-based Iterative Methods for Corrupted Systems of Linear Equations,” _SIAM Journal on Matrix Analysis and Applications_ , 2022.
  * [15] B. T. Polyak, “Some methods of speeding up the convergence of iteration methods,” _Ussr computational mathematics and mathematical physics_ , vol. 4, no. 5, pp. 1–17, 1964.
  * [16] I. Sutskever, J. Martens, G. Dahl, and G. Hinton, “On the importance of initialization and momentum in deep learning,” in _International conference on machine learning_. PMLR, 2013, pp. 1139–1147.
  * [17] A. Krizhevsky, I. Sutskever, and G. E. Hinton, “ImageNet Classification with Deep Convolutional Neural Networks,” _Commun. ACM_ , vol. 60, no. 6, p. 84–90, 2017.
  * [18] I. Gitman, H. Lang, P. Zhang, and L. Xiao, “Understanding the role of momentum in stochastic gradient methods,” _Advances in Neural Information Processing Systems_ , vol. 32, 2019.
  * [19] H. Xia, V. Suliafu, H. Ji, T. Nguyen, A. Bertozzi, S. Osher, and B. Wang, “Heavy ball neural ordinary differential equations,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 18 646–18 659, 2021.
  * [20] N. Loizou and P. Richtárik, “Momentum and stochastic momentum for stochastic gradient, newton, proximal point and subspace descent methods,” _Computational Optimization and Applications_ , vol. 77, no. 3, pp. 653–710, 2020.
  * [21] T. Yang, Q. Lin, and Z. Li, “Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimization,” _arXiv preprint arXiv:1604.03257_ , 2016.
  * [22] S. Gadat, F. Panloup, and S. Saadane, “Stochastic heavy ball,” _Electronic Journal of Statistics_ , vol. 12, no. 1, pp. 461–529, 2018.
  * [23] D. Needell, N. Srebro, and R. Ward, “Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm,” _Mathematical Programming: Series A_ , vol. 155, no. 1-2, pp. 549–573, 2016.
  * [24] D. Dua and C. Graff, “UCI machine learning repository,” 2017. [Online]. Available: http://archive.ics.uci.edu/ml
  * [25] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _International Conference on Learning Representations_ , 2014.
  * [26] D. Needell, “Randomized kaczmarz solver for noisy linear systems,” _BIT Numerical Mathematics_ , vol. 50, no. 2, pp. 395–403, 2010.