A Graph Theoretic Approach for Training Overhead
Reduction in FDD Massive MIMO Systems
Nadisanka Rupasinghe∗, Yuichi Kakishima† , Haralabos Papadopoulos†, İsmail Güvenç∗
of Electrical and Computer Engineering, North Carolina State University, Raleigh, NC, 27606
† DOCOMO Innovations, Inc., Palo Alto, CA, 94304
rprupasi@ncsu.edu, {kakishima, hpapadopoulos}@docomoinnovations.com, iguvenc@ncsu.edu

arXiv:1802.01014v1 [] 3 Feb 2018

∗ Department

Abstract—The overheads associated with feedback-based channel acquisition can greatly compromise the achievable rates of
FDD based massive MIMO systems. Indeed, downlink (DL) training and uplink (UL) feedback overheads scale linearly with the
number of base station (BS) antennas, in sharp contrast to TDDbased massive MIMO, where a single UL pilot trains the whole
BS array. In this work, we propose a graph-theoretic approach
to reducing DL training and UL feedback overheads in FDD
massive MIMO systems. In particular, we consider a single-cell
scenario involving a single BS with a massive antenna array serving to single-antenna mobile stations (MSs) in the DL. We assume
the BS employs two-stage beamforming in the DL, comprising
DFT pre-beamforming followed by MU-MIMO precoding. The
proposed graph-theoretic approach exploits knowledge of the
angular spectra of the BS-MS channels to construct DL training
protocols with reduced overheads. Simulation results reveal that
the proposed training-resources allocation method can provide
approximately 35% sum-rate performance gain compared to
conventional orthogonal training. Our analysis also sheds light
into the impact of overhead reduction on channel estimation
quality, and, in turn, achievable rates.
Index Terms—Conflict graph, FDD, massive MIMO, MMSE
channel estimation, regularized zero-forcing (RZF).

I. I NTRODUCTION
Massive multi-input multi-output (MIMO) is envisioned as
one of the key technologies for future wireless communication systems, due to its potential to significantly improve
spectral/energy efficiency [1]–[3]. Interest in time-divisionduplexing (TDD) massive MIMO systems has recently surged
[4]–[7], due, in part, to their inherent scalability with the
number of base station (BS) antennas. In particular, in TDD
massive MIMO systems, the channel state information at the
transmitter (CSIT) can be obtained by leveraging the channel
reciprocity [8].
However, achieving massive MIMO gains for frequencydivision-duplexing (FDD) cellular networks still carries critical
importance since the vast majority of currently deployed
cellular networks operate in FDD. The main challenge that
arises in introducing massive-MIMO to FDD networks stems
from the fact that downlink (DL) channel training and uplink
(UL) CSI feedback overheads scale linearly with the number
of transmit antennas, M at the BS (i.e., O(M )). In [9], an
open-loop and closed-loop training framework is proposed to
reduce the training and feedback overhead in FDD massive
MIMO systems. In particular, by exploiting long-term channel
statistics and previously received training signals at the mobile

station (MS), improved channel estimation is achieved with a
training sequence that is much shorter than the BS array size.
A joint CSIT acquisition scheme based on low-rank matrix
completion is proposed in [10] to reduce the DL training and
UL feedback overhead. In [11], a compressive sensing (CS)
based solution is proposed by exploiting spatially joint sparsity
of multiple users’ channel matrices, to reduce the training
and feedback overhead in FDD massive MIMO systems. An
adaptive CS-based channel estimation technique with adaptive
training overhead and feedback scheme is proposed in [12]
for FDD massive MIMO systems, by exploiting the spatially
common sparsity and the temporal correlation of massive
MIMO channels.
The recently proposed joint spatial division and multiplexing (JSDM) technique focuses on training and feedback overhead reduction in FDD massive MIMO systems
by exploiting the spatial correlation structure of the BSMS channels [13], [14]. JSDM partitions users in a given
geographical area into groups with approximately the same
channel covariance eigenspace and exploits two-stage DL
beamforming. User scheduling is done to maximize multiplexing gain/beamforming gain, while suppressing overlapping
regions of angular spectra of users (user groups) scheduled
together [13]. However, one main assumption in JSDM when
identifying the correlation structure of the channel vectors of
users (user groups) is that, common regions in the angular
spectra (corresponding to common scatterers) of different
users (user groups) are completely overlapping. This may be
considered a fairly reasonable modeling assumption for some
macro-BS scenarios, as motivated in [13]. However, it does
not hold in small-cell real-environment scenarios. Indeed, the
type of joint user-channel group structure considered in [13],
is not present in the channel models used by 3GPP [15] to
evaluate the efficacy of new techniques for standardization.
In this work we consider a realistic radio propagation environment, whereby the dominant angular spectra of different
users may exhibit full, partial, or no overlap. In particular,
we consider an environment where scatterers and MSs are
uniformly randomly distributed. The second-order channel
statistics are then derived for each user in this environment. We
consider a single group consisting of all the users and employ
two-stage DL beamforming as in [14]. We restrict our attention
to DFT prebeamforming, since our focus is on the large-scale
antenna array regime. Indeed, with uniform-linear antenna

arrays (ULA) DFT prebeamforming effectively becomes an
eigen-preprocessor in the large antenna regime [14]. Due to
the scattering geometry, different users will have different
dominant eigenmodes of user channel that can be identified
using the second order channel statistics, and we focus on
those dominant eigenmodes when realizing multi-user (MU)MIMO precoding. In particular, for each MS channel, we
define the notion of the dominant beam angular spectrum,
comprising the set of the dominant DFT eigenbeams (since
DFT vectors are a good approximation of eigen vectors for
large antenna arrays [14]), that is the beams with power
exceeding a predefined gain threshold.
By altering the gain threshold, the perceived effective sparsity of the dominant beam angular spectrum can be modified,
where the different users will have different dominant beam
angular spectra with highly variable extent of overlap. Hence,
by considering the dominant beam angular spectra of all users
jointly, a conflict graph is created to capture the conflicts
between different DFT beams based on their existence in
the dominant beam angular spectra of different users. Our
proposed algorithm can then identify training resources for
different DFT beams as a solution to a graph coloring problem. In this way, users will have to estimate and feedback
only the channel dimensions corresponding to their dominant
eigenmodes captured in dominant beam angular spectra.
We analyze the sum user-rate performance and the userrate distribution when the sum user-rates are maximized. The
choice of the predefined gain threshold used to identify the
dominant eigenmodes in the user spectra, impacts the achievable rate performance in two ways: 1) the amount of training
overhead reduction, and 2) the resulting user-channel estimate
quality. Our analysis reveals that, when the system is degreesof-freedom (DoF) limited, overhead reduction can enhance
rate performance. However, overhead reduction comes at the
cost of increasing channel estimation error. Hence, there is
an optimum threshold where sum-rates can be maximized.
Our simulation results show that approximately 35% sum-rate
performance gain can be achieved with the proposed graphtheoretic training resources allocation approach compared to
conventional orthogonal training-resource allocation.
Notations: Bold and uppercase letters represent matrices
whereas bold and lowercase letters represent vectors. k · k,
| · |, (·)T , (·)H , (·)∗ , tr (·), and E{·} represent the Euclidean
norm, absolute-value norm, transpose, Hermitian transpose,
complex conjugation, trace of a matrix, and expectation operators, respectively. CN (m, C) denotes the complex-valued
multivariate Gaussian distribution with the mean vector m and
the covariance matrix C, and U[a, b] denotes the continuous
Uniform distribution over the interval [a, b]. IM is the M ×M
identity matrix.
II. S YSTEM M ODEL
We consider a system consisting of uniformly randomly
distributed scatterers and MSs in a given area as shown
in Fig. 1. We restrict our attention to single bounce paths
through a single scatterer. This layout can preserve spatial

"

BS

pth Scatterer

!
"!

kth MS
Fig. 1: Example involving a BS serving multiple MSs.

consistency feature as well. We consider the user set to be
NU = {1, 2, . . . , NMS } and consider NS scatterers. The BS
is equipped with a M antenna elements ULA, while each
MS is assumed to have a single antenna element. We assume
OFDM and a quasistatic block fading channel model whereby
the channel of the k-th user stays fixed within a fading block
(within the coherence time and bandwidth of the channel).
During a given fading block the channel response between
BS and k-th MS, hk (f ) (M × 1) can be given as:
hk (f ) =

NX
S +1

αk,p a (θk,p ) e−j2πτk,p f ,

(1)

p=1

where αk,p , θk,p , τk,p , and f are the complex gain, angleof-departure (AoD) (identified from underlying environment),
relative delay of the p-th path of k-th user channel, and
subcarrier frequency, respectively. a (θk,p ) is the steering
vector corresponding to AoD, θk,p . We consider directional
propagation loss, L(d) = (1 + d/ǫ)γ as in [16] where ǫ
and γ denote the break point distance and q
path loss (PL)
P
exponent, respectively. Therefore, |αk,p | =
βL(dp )L(dpk ) ,
with P being the transmit power and β being the reflector
attenuation. By assuming uncorrelated scattering, the channel
covariance matrix of the k-th MS, Rk (M × M ) can then be
derived using (1) as:


Rk = E hk (f )hH
k (f ) =

NX
S +1

|αk,p |2 a (θk,p ) aH (θk,p ) . (2)

p=1

A. Dominant Beam Angular Spectrum Generation
We will represent the set of available DFT beams at the
BS via the M × M matrix F = [b1 , b2 . . . , bM ], and as a set
B = {b1 , b2 . . . , bM }. Given that our focus is on the large M
case, we will assume that the DFT matrix F whitens Rk and
as a result the average channel gain corresponding to bi -th
DFT beam, λk (i) for k-th MS can be captured as λk (i) =
2
|bH
i Rk bi | . The set of entries in the angular spectrum, Gk of
k-th MS can be given as Gk = {λk (1), λk (2), . . . λk (M )}.
Then, the support of the dominant beam angular spectrum of
the k-th user is captured by
(
1; if λk (i) ≥ δ
gk (i) =
,
(3)
0; otherwise

!

MS 1
b1
b2

$
"

MS 2

b3

$

b4
#

b5

MS 3

b6

(a) Dominant beams of 3 MSs

$

(b) Dominant beam angular
spectra of 3 MSs

Fig. 2: Example of dominant beams and dominant beam angular
spectra for 3 MSs with respect to a 6-beam BS.
b1

b2

b3

b4

b5

b6

b1

0

1

1

0

1

0

b2

1

0

1

1

0

1

b3

1

1

0

0

1

0

b4

0

1

0

0

0

1

b5

1

0

1

0

0

0

b6

0

1

0

1

0

0

(a) Beam-beam association matrix

b1

of beams between different MSs is completely determined by
the underlying propagation environment.
The conventional DL training approach corresponds to allocating orthogonal training resources to different beams. This
guarantees that beams are observed at each MS interferencefree. Even though the conventional approach ensures that the
acquired channel estimates are free of pilot-contamination, this
comes at the cost of large training overheads that scale linearly
with the number of beams. For instance, in the example
depicted in Fig. 2, 6 orthogonal resources are required by the
conventional approach to train every MS on 6 beams.
The color-coded beams in Fig. 2a illustrate how knowledge
of the beam angular spectra, i.e., the gk ’s, at the BS can
be exploited to reduce DL training overheads. In particular,
the BS can exploit knowledge of the gk ’s, to design a beamtraining pattern which trains every MS on its dominant beams
and requires only 3 colors, that is, 3 orthogonal resources.

b4

A. Conflict Graph based Training Resource Allocation
b2

b5

b3

b6

(b) Conflict graph

Fig. 3: Beam-beam association matrix and associated conflict graph,
based on the beam angular spectra in Fig. 2. Each of the 1’s in the
beam-beam association matrix induces an edge in the conflict graph.

where δ denotes the predefined gain threshold. Specifically, we denote the dominant beam-set by Bk =
{bm ∈ B; gk (m) = 1}. The cardinality of the set, |Bk | is
Mk (≤ M ). With this notation, the common dominant spectra (i.e., overlap) between MSs i, j ∈ NU is captured by
Bi ∩ Bj , i, j ∈ NU , i 6= j. The amount of overhead reduction
depends on the sparsity of the dominant beam angular spectra,
gk , k ∈ NU . By altering the threshold δ, it is possible to
modify the sparsity of dominant beam angular spectrum.
III. G RAPH T HEORETIC A PPROACH FOR T RAINING
R ESOURCE A LLOCATION
In this section, we discuss in detail the proposed graphtheoretic approach to assign training resources to different
DFT beams by jointly analyzing the dominant beam angular
spectra, gk , k ∈ NU of all users. First, we provide the intuition
behind the proposed approach and then the graph-theoretic
solution is discussed in detail.
Consider first the example in Fig. 2, involving 3 MSs and
6 beams, i.e., NU = 1, 2, 3 and M = 6. As the figure reveals,
the dominant beam sets of the 3 MSs have been detected as
follows: B1 = {b1 , b2 , b3 }, B2 = {b1 , b3 , b5 } and B3 =
{b2 , b4 , b6 }. The respective dominant beam angular spectra,
gk , k ∈ {1, 2, 3} for all 3 MSs are also shown in Fig. 2b. It
can clearly be seen that some beams are detected by several
MSs. For instance, b1 is detected by both MS 1 and MS 2
and b2 is detected by both MS 2 and MS 3. This overlapping

In this section we describe a systematic resource-allocation
approach, which exploits knowledge of the MS dominant beam
angular spectra to allow all MSs to learn their dominant spectra
with reduced training overheads. The proposed method maps
the resource allocation problem into a graph coloring problem.
First, an M × M beam-beam association matrix, A, with ij-th
element
(
1 if ∃k ∈ NU , s.t., bi , bj ∈ Bk
aij =
,
(4)
0 otherwise
is identified. Subsequently, the beam-beam association matrix
is used to generate a conflict graph between beams. The beambeam association matrix and the associated conflict graph for
the example in Fig. 2 are shown in Fig. 3a and Fig. 3b,
respectively. Every vertex of the conflict graph shown in
Fig. 3b represents a conflict between two DFT beams. Distinct
vertex colors represent distinct (orthogonal) training resources.
Hence the problem of resource allocation has been recast into
determining the coloring assignment for all vertices of the
graph that uses the minimum number of colors, subject to the
constraint that no two connected vertices share the same color.
The optimization problem can thus be formulated as:
min Mtr , s. t. ci 6= cj , if aij = 1,

(5)

where Mtr is the required number of unique colors to color
the graph. For instance, any coloring assignment that yields
max Mtr = M corresponds to orthogonal training resource
allocation. Let cl , l ∈ {1, 2 . . . , M } represents the color
assigned to l-th vertex. Note that, we are not limiting the
number of times a color can be reused (which implicitly tells
that a training resource can be reused any number of times).
Since finding a coloring assignment that yields Mtr achieving the minimum value in (5) is an NP-hard problem, we
consider the use of greedy solutions. Similar to the discussion
in [17] Section IV, a low-complexity training resource allocation approach can be formulated here as a greedy solution to
the graph coloring problem in (5), as follows. First, vertices

Algorithm 1 Graph coloring algorithm
Input: Dominant beam angular spectra of users
Step 1: Generate conflict graph by using dominant beam angular
spectra and beam-beam association matrix
Step 2: Sort the vertices in the order b1 , b2 , . . . , bM with respect to
sn1 ≥ sn2 ≥ · · · ≥ snM
Step 3: Assign b1 the color c1 = 1
Step 4:
1: for bi , i ≥ 2
2:
If CiC = {1, 2, . . . , Mi−1 }, assign a new color, ci = Mi
3:
else, ci = m with m satisfying (7)
4: end for

in (1), DFT prebeamforming is employed to identify the
effective channel of the k-th MS, hk (M × 1)1 as [14]

are sorted with respect to the number of edges connected to
each of them. To avoid use of tedious re-indexing, we assume
without loss of generality that the beams in B are already indexed in order of non-increasing numbers of connected edges.
M
P
aik denote the total number of
Specifically, letting si =

h′k = BH
k hk ,

k=1

edges to node i (i.e., the number of beams in conflict with
beam bi ∈ B), we have s1 ≥ s2 ≥ · · · ≥ sM . The graph
coloring algorithm we consider is concisely described under
Algorithm 1 (shown at the top of the page). The algorithm
greedily assigns colors to the graph nodes sequentially starting
from graph node one. For convenience we denote by Mi the
number of colors used by the algorithm after it visits and
assigns colors to the first i vertices. The algorithm starts by
assigning to vertex 1 (beam b1 ) the first color, i.e., c1 = 1,
and sets the number of colors used to M1 = 1.
At each step i for i ≥ 2, a color is picked for node i. Given
that at step i, any node with index k ∈ {1, 2, . . . , i − 1} has
already been colored, avoiding a conflict between node i and
all previously colored nodes means picking a color ci for the
i-th node such that
ci 6= ck , if aik = 1, ∀k ∈ {1, 2, . . . , i − 1} .

(6)

Let CiC denote the set of all colors assigned to vertices in
{1, 2, . . . , i − 1} which are connected to node i. If CiC =
{1, 2, . . . , Mi−1 }, i.e., all the already assigned colors are
eliminated due to conflicts, a new color is assigned to vertex i, i.e., Mi = Mi−1 + 1, and ci = Mi . However, if
{1, 2, . . . , Mi−1 } − CiC is non-empty, one of the colors in this
set can be re-used to color ci , resulting in Mi = Mi−1 < i,
thereby avoiding the use of excess colors (and resources).
When the set {1, 2, . . . , Mi−1 } − CiC has multiple elements,
the algorithm sets ci = m,
m = arg

min

qk′ ,
C

(7)

k∈{1,2,...,Mi−1 }−Ci

where qk′ is the number of nodes in {1, 2, . . . , i − 1} that have
been assigned color k. Since colors of the vertices represent
training resources, colors and vertices mapping to training
resources and beams is straightforward.
IV. DL T RAINING , P RECODER G ENERATION AND DATA
T RANSMISSION
In this section, we describe the phases of DL channel
training and precoder generation, MU-MIMO precoding and,
finally, DL data transmission. By considering the user channel

hk = FH hk .

(8)

The MSs only estimate the dimensions captured in their
respective dominant beam angular spectra in effective channel.
Hereafter we use the term effective measured channel to refer
to this channel. The effective measured channel at k-th user,
h′k (Mk × 1) can be given as:
(9)

where Bk is a Mk × M matrix containing all the DFT beams
in Bk as column vectors.
A. DL Channel Training
We consider proposed graph-theoretic approach in Section III-A to assign DL training resources. Further, we assume
minimum-mean-squared-error (MMSE) channel estimation at
each MS. Recalling that the Mk beams in the k-th MS’s
dominant beam angular spectrum (connected by edges in the
conflict graph) have different colors, they are observed at MS
k
k over Mk distinct orthogonal resources. Letting Sm
denote
the set of all other beams that share the same color as beam
bm (k), the set of Mk relevant pilot observations collected by
MS k, he′ k have the following form:
P H

 H
bm hk
b1 (k)hk +
m∈S1k


P H

 H
bm hk 
 b2 (k)hk +
p


k
m∈S2
 + nk
he′ k = Ptr 


..


.


bH (k)h + P bH h 
k
m k
Mk
k
m∈SM

k

 P

bH
m hk



 P



bH
h


k
m
p
p


k
m∈S2
H

 + nk ,
= Ptr Bk hk + Ptr 

.
..


 P

H

bm hk 
m∈S1k

(10)

k
m∈SM

k

where Ptr is the transmit power for training and nk is the
Mk × 1 noise vector consisting of entries from CN (0, σ 2 IMk ).
We consider a fixed SNR ρtr = Pσtr2 for DL training in our
investigation. As per (10), each beam bi (k) ∈ Bk undergoes
beam-specific level of contamination that depends on the set
of beams in Sik and on the level of interference these beams
cause (i.e., on the λk (m)’s for all beams bm ∈ Sik ).
The observed effective measured channel in (10) can be
compactly re-expressed as follows:
p
p
he′ k = Ptr BH
Ptr Ck FH hk + nk ,
(11)
k hk +
1 Note that, unless stated otherwise, all channels are for subcarrier frequency f .

where Ck is a matrix consisting of 0’s and 1’s. For example,
1’s in the i-th row of Ck capture other DFT beams assigned
with the same training resource as beam bi (k).
With the noisy observation in (11), the MMSE estimate of
the h′k can be derived as follows:
    
 H −1
H
he′ k
E he′ k he′ k
hˆ′ k = E h′k he′ k
p

−1 e′
2
h k , (12)
=
Ptr BH
R
X
Ptr XH
k k k
k Rk Xk + σ IMk
{z
}
|
Wk

where, Xk = Bk + FCk .
1) Channel Estimation Error: The mean squared error
(MSE) due to MMSE channel estimation in (12) at k-th MS,
Jk can be derived as follows:


o
n
2
′
′
ˆ
(13)
Jk = E hk − h k
= tr R′k − Rˆ′ k ,

where R′k and Rˆ′ k are the covariance matrices of effective
measured channel and its estimate at the k-th MS, respectively.
Here, we considered the well-known MMSE decomposition,
hk = ĥk + êk to derive (13). Then, R′k can be derived as
follows:
o
n
n
H o
H
H
= E BH
R′k = E h′k h′ k
k hk hk Bk = Bk Rk Bk , (14)

where we used, Rk from (2). Further, Rˆ′ k can be given as,
′



′



′

H 




 H
= E Wk he′ k he′ k WHk

R̂ k = E ĥ k ĥ k
(15)


 H


H
2
= Wk E he′ k he′ k
WHk = Wk Ptr XH
k Rk Xk + σ IMk Wk ,

   
H
=
where we considered the fact that E he′ k he′ k

Ptr XH
k Rk Xk + IMk from (12). As a result, Jk in (13) can
be readily calculated using (14) and (15).
Finally, MS k feeds back its effective channel estimate
in (12) to the BS over a feedback channel for precoder
generation. As in [13], [14], we assume ideal and delay free
CSIT feedback. Next, we discuss the precoder generation
using the estimates of effective measured channel.
B. RZF Precoder Generation
In order to realize the MU-MIMO precoder, an estimate
of the effective channel in (8) is required. Hence, at the BS,
estimate of the effective channel of k-th MS, ĥk , k ∈ NU is
generated by inserting zeros to all dimensions that correspond
to beams not included in the dominant beam angular spectra of
the MS. As a consequence, when the support of the effective
measured channel decreases (with larger δ), the MSE of the
resulting effective channel estimate increases.
Given the effective user channel matrix Ĥ as
h
i
Ĥ = ĥ1 ĥ2 · · · ĥNMS ,
(16)

the BS constructs a regularized zero forcing (RZF) precoder
that can be defined as [14]:
P = ηKĤ,
(17)
i
h
H
where K = ĤĤ + σ 2 IM and where the power normalization factor η is given as:
v
u
NMS
u
o.
η=t n H
tr Ĥ KH FH FKĤ

(18)

Subsequently, the RZF precoder in (17) is used for DL data
transmission.
C. DL Data Transmission
The received signal at the k-th MS during the DL data
transmission can be expressed in the following form
P X H
P H
hk Fpk′ xk′ + nk ,
(19)
hk pk xk +
yk =
NMS
NMS ′
k 6=k

where P is the DL transmit power. The received SINR at the
k-th MS, SINRk can then be given as:
SINRk =

σ2 +

P
2 H
2
NMS η |ĥk Kĥk |
.
P H
P
P
2 H
2
2
|hk FKĥk′ |2
NMS η |êk Kĥk | + NMS η
k′ 6=k

(20)

Finally, the net (achievable) rate at the k-th MS within a
coherence block with T slots is given by,


b′
log(1 + SINRk ).
(21)
Ratek = 1 −
T
Here, b′ captures number of slots allocated for DL training
within the coherence block. For the conventional orthogonal
training resource allocation approach, b′ = M . With smaller
b′ , more resources can be assigned for data transmission. Note
here that, since there are more slots available for DL data
transmission with proposed approach, we scale down P with
respect to the transmission power of conventional orthogonal
training PTx as,
P =

(T − M )
× PTx .
(T − b′ )

(22)

The overhead reduction from the proposed approach comes
at the cost of increased channel estimation error. We try to
identify a balance between overhead reduction and channel
estimation error to maximize achievable rate performance.
V. N UMERICAL R ESULTS

AND

D ISCUSSION

In this section, we evaluate the achievable rate performance
of the proposed training resource allocation scheme. In particular, to understand the rate performance trends, we analyze both
the overhead reduction performance and channel estimation
error performance with different thresholds, δ in (3). For all
evaluations, we consider training SNR, ρtr = 30 dB. Further,

TABLE I: Simulation settings.
Value
0.5 km2
100
50, 100
Uniformly randomly
Uniformly randomly
−94 dBm
30 dBm
400
2M = 400
2.5
0.7

-15

-20

Non-orthogonal (N S = 50, Theo)

-25

Orthogonal (NS = 50, Theo)
Non-orthogonal (N S = 50, Sim)
Orthogonal (NS = 50, Sim)

-30

Non-orthogonal (N S = 100, Theo)
Orthogonal (NS = 100, Theo)
Non-orthogonal (N S = 100, Sim)
Orthogonal (NS = 100, Sim)

-35

350

1

Average overhead reduction (N S = 50)
Average overhead reduction (N S = 100)

250

0.7

0.5
150

0.4
0.3

100

-35

-30

-25

-20

-15

-10

0
-5

(dB)

Fig. 4: Average number of beams detected and associated overhead
reduction as a function of δ for two different scattering environments.

we average outcomes over large number of realizations to obtain meaningful results. Simulation parameters are summarized
in Table I.
Fig. 4 captures average number of beams seen by a MS and
amount of overhead reduction which is defined as,
Overhead Reduction =

-25

-20

-15

-10

Non-orthogonal (NS = 100 )

-4

0.1
-40

-30

Fig. 5: MSE of effective measured channel estimate versus δ for two
distinct NS values.

50

-45

-35

(dB)

0.2

0

-40

0.8

0.6

200

-45

0.9

# of resources: non-orthogonal training
# of resources: orthogonal training

,

as a function of threshold δ. Here, non-orthogonal training
refers to the case where training resources are allocated
considering proposed graph theoretic approach whereas orthogonal training refers to the conventional orthogonal training
resource allocation approach. As can be seen from Fig. 4, with
increasing δ, the number of detected beams decreases, making
the dominant beam angular spectra discussed in Section II-A
sparser. This, in turn, results in reduced training overheads
and as (21) clearly reveals, in a larger fraction of dimensions
left for data transmission. At the same time, this gain in
dimensions left for data transmission comes at a cost in
channel estimation error quality, and, in turn, as (21) reveals,
lower user SINRs.
Fig. 5 shows the MSE of the effective measured channel
in (9) versus δ. As the figure reveals, analytical (see Section IV-A1) and simulation estimation error results are matching. Furthermore, the MSE of the proposed non-orthogonal
resource allocation for training remains high throughout the
whole δ range. Moreover, it becomes significantly higher than
the MSE of the orthogonal scheme for δ > −30 dB, due

MSE of effective channel (dB)

Average beams detected (NS = 100)

300

Average overhead reduction

Average beams detected (NS = 50)

Average number of detected beams

MSE of effective measured channel (dB)

Parameter
Simulation area
No. of users, NMS
No. of scatterers, NS
User distribution
Scatterer distribution
Noise power, σ2
Transmit power, PTx
No. of BS ant., M
Time slots, T
Path loss exponent, γ
Reflector attenuation, β

Orthogonal (NS = 100 )
Non-orthogonal (NS = 50)
Orthogonal (NS = 50)

-6

-8

-10

-12

-14
-45

-40

-35

-30

-25

-20

-15

-10

(dB)

Fig. 6: MSE of effective channel estimate versus δ for two distinct
NS values.

to pilot contamination. Another observation that can be made
from Fig. 5 is that, estimation error (especially for orthogonal
training allocation) reduces with increasing δ. This is because,
the dimensionality of effective measured channel decreases
with δ as the error is over the detected beams and fewer (and
stronger) beams are detected.
Fig. 6 shows the MSE of the effective channel in (8) versus
δ. As the figure reveals, MSE increases with increasing δ.
This as discussed previously, is expected, since increasing δ
causes the MS to detect and estimate fewer dimensions and
zero out more dimensions. This issue is common to both
orthogonal and non-orthogonal training resource allocation
approaches. Due to the inherent pilot contamination in nonorthogonal training resource allocation, the effective channel
MSE increases further with the proposed approach.
Fig. 7 depicts the achievable rate performance of the proposed non-orthogonal training approach and of the conventional orthogonal training approach. As the figure reveals,
the achievable rate performance with the proposed approach
is maximized at about δ = −36 dB and compared to the
maximum achievable rate with non-orthogonal training, this
is approximately 35% gain. Further, with orthogonal training,

are uniformly randomly distributed and employ two-stage DL
beamforming; DFT preamforming and MU-MIMO precoding.
Our approach relies on identifying the support of the dominant
angular spectra of each user via thresholding, followed by
a graph-theoretic training resource allocation scheme, which
ensures that every user can estimate its channel restricted to
its dominant spectra support. As our investigation reveals,
by properly choosing the threshold and by applying our
graph-theoretic solution, non-orthogonal DL training resource
allocation schemes can be designed that yield significant gains
with respect to their orthogonal training counterparts, both in
achievable sum rates and in user-rate CDFs.

160
Non-orthogonal
140

Sum Rate (bits/s/Hz)

120
100
Orthogonal
80
60
Non-orthogonal (NS = 50)

40

Orthogonal (NS = 50)
Non-orthogonal (NS = 100 )

20
0

Orthogonal (NS = 100)

-45

-40

-35

-30

-25

-20

-15

-10

(dB)

Fig. 7: Achievable sum rate performance of orthogonal and the
proposed non-orthogonal training schemes versus δ, for two distinct
NS values: NS = {50, 100}.
1
Non-orthogonal (NS = 50)

0.9

Orthogonal (NS = 50)
Non-orthogonal (NS = 100)

0.8

Orthogonal (NS = 100)

0.7

CDF

0.6

Orthogonal

0.5
0.4
0.3

Non-orthogonal

0.2
0.1
0
0.9

1

1.1

1.2

1.3

1.4

1.5

1.6

1.7

Rate (bits/s/Hz)

Fig. 8: Individual user rate distribution of orthogonal and the proposed (sum-rate optimized) non-orthogonal training schemes, for two
distinct NS values: NS = {50, 100}.

this type of a behavior can not be observed. The reason
for observing a convex behavior in rate performance with
the proposed training resource allocation approach can be
explained as follows. As δ is increased (starting from the left
of the figure), initially the SINR loss in (21) is very small, and
the gains in the prelog factor of (1 − b′ /T ) in (21) manifest
themselves as improved achievable rates. However as δ is
increased beyond −36 dB the reduction in SINRs dominate
the gains provided by the prelog factor.
Finally, Fig. 8 captures the cumulative distribution functions
(CDFs) of individual user rates for the orthogonal and the
(sum-rate optimized) non-orthogonal training schemes. Inspection of the figure reveals that the proposed non-orthogonal
training schemes yield strictly better user rate CDFs than their
orthogonal training counterparts.
VI. C ONCLUDING R EMARKS
In this paper, we propose a graph-theoretic approach to reduce DL training overheads in FDD massive-MIMO systems.
We consider a realistic environment where users and scatterers

R EFERENCES
[1] E. G. Larsson, O. Edfors, F. Tufvesson, and T. L. Marzetta, “Massive
MIMO for next generation wireless systems,” IEEE Commun. Mag.,
vol. 52, no. 2, pp. 186–195, Feb. 2014.
[2] T. L. Marzetta, “Massive MIMO: An introduction,” Bell Labs Tech. J.,
vol. 20, pp. 11–22, Mar. 2015.
[3] E. Björnson, E. G. Larsson, and T. L. Marzetta, “Massive MIMO: Ten
myths and one critical question,” IEEE Commun. Mag., vol. 54, no. 2,
pp. 114–123, Feb. 2016.
[4] T. L. Marzetta, “Noncooperative cellular wireless with unlimited numbers of base station antennas,” IEEE Tran. Wireless Commun., vol. 9,
no. 11, pp. 3590–3600, 2010.
[5] Z. Li, N. Rupasinghe, O. Y. Bursalioglu, C. Wang, H. Papadopoulos, and
G. Caire, “Directional training and fast sector-based processing schemes
for mmwave channels,” in Proc. IEEE Int. Conf. Commun. (ICC), May
2017, pp. 1–7.
[6] H. Yin, D. Gesbert, M. Filippou, and Y. Liu, “A coordinated approach
to channel estimation in large-scale multiple-antenna systems,” IEEE J.
Sel. Areas Commun., vol. 31, no. 2, pp. 264–273, 2013.
[7] J. I. Vergara, I. Guvenc, S. Dikmese, and N. Rupasinghe, “Efficient noise
variance estimation under pilot contamination for large-scale MIMO
systems,” IEEE Trans. Vehic. Technol., vol. PP, no. 99, pp. 1–1, 2017.
[8] J. Hoydis, S. t. Brink, and M. Debbah, “Massive MIMO in the UL/DL
of cellular networks: How many antennas do we need?” IEEE J. Sel.
Areas Commun., vol. 31, no. 2, pp. 160–171, Feb. 2013.
[9] J. Choi, D. J. Love, and P. Bidigare, “Downlink training techniques for
FDD massive MIMO systems: Open-loop and closed-loop training with
memory,” IEEE J. Sel. Topics in Sig. Proc., vol. 8, no. 5, pp. 802–814,
Oct. 2014.
[10] W. Shen, L. Dai, B. Shim, S. Mumtaz, and Z. Wang, “Joint CSIT
acquisition based on low-rank matrix completion for FDD massive
MIMO systems,” IEEE Commun. Lett., vol. 19, no. 12, pp. 2178–2181,
Dec. 2015.
[11] X. Rao and V. K. N. Lau, “Distributed compressive CSIT estimation
and feedback for FDD multi-user massive MIMO systems,” IEEE Tran.
on Sig. Proc., vol. 62, no. 12, pp. 3261–3271, Jun. 2014.
[12] Z. Gao, L. Dai, Z. Wang, and S. Chen, “Spatially common sparsity based
adaptive channel estimation and feedback for FDD massive MIMO,”
IEEE Tran. on Sig. Proc., vol. 63, no. 23, pp. 6169–6183, Dec. 2015.
[13] A. Adhikary, E. A. Safadi, M. K. Samimi, R. Wang, G. Caire, T. S.
Rappaport, and A. F. Molisch, “Joint spatial division and multiplexing
for mm-wave channels,” IEEE J. Sel. Areas in Commun., vol. 32, no. 6,
pp. 1239–1255, Jun. 2014.
[14] A. Adhikary, J. Nam, J. Y. Ahn, and G. Caire, “Joint spatial division and
multiplexing - the large-scale array regime,” IEEE Trans. Info. Theo.,
vol. 59, no. 10, pp. 6441–6463, Oct. 2013.
[15] Technical Specification Group Radio Access Network, “Study on channel model for frequency spectrum above 6 GHz,” 3rd Generation
Partnership Project (3GPP), Tech. Rep. 3GPP TR38.900 v14.1.0, 2016.
[16] O. Y. Bursalioglu, C. Wang, H. Papadopoulos, and G. Caire, “A novel
alternative to cloud RAN for throughput densification: Coded pilots and
fast user-packet scheduling at remote radio heads,” in Proc. Asilomar
Conf. Sig., Sys. Comp., Nov. 2016, pp. 3–10.
[17] Z. Chen, X. Hou, and C. Yang, “Training resource allocation for usercentric base station cooperation networks,” IEEE Trans. Vehic. Technol.,
vol. 65, no. 4, pp. 2729–2735, Apr. 2016.

