1

Deep-LMS for gigabit transmission over unshielded
twisted pair cables

arXiv:1705.10459v1 [cs.IT] 30 May 2017

Avi Zanko∗,\ , Itsik Bergel∗ (Senior Member, IEEE), Amir Leshem∗ (Senior Member, IEEE)

Abstract— In this paper we propose a rapidly converging LMS
algorithm for crosstalk cancellation. The architecture is similar
to deep neural networks, where multiple layers are adapted
sequentially. The application motivating this approach is gigabit
rate transmission over unshielded twisted pairs using a vectored
system. The crosstalk cancellation algorithm uses an adaptive
non-diagonal preprocessing matrix prior to a conventional LMS
crosstalk canceler. The update of the preprocessing matrix is
inspired by deep neural networks. However, since most the
operations in the Deep-LMS algorithm are linear, we are capable
of providing an exact convergence speed analysis. The role of
the preprocessing matrix is to speed up the convergence of the
conventional LMS crosstalk canceler and hence the convergence
of the overall system. The Deep-LMS is important for crosstalk
cancellation in the novel G.fast standard, where traditional LMS
converges very slowly due to the ill-conditioned covariance matrix
of the received signal at the extended bandwidth. Simulation
results support our analysis and show significant reduction in
convergence time compared to existing LMS variants.
Index Terms—Crosstalk canceler, DSL, LMS, G.fast.

I. I NTRODUCTION
The Digital Subscriber Line (DSL) family of technologies
provides high speed digital data transmission over unshielded
twisted pairs (UTP) of copper wires that were originally used
for telephone services [2, 3]. The performance of a DSL
system may be significantly degraded by the effect of crosstalk
due to electromagnetic coupling between adjacent pairs. We
distinguish between two types of crosstalk: near end crosstalk
(NEXT) is the interference that is measured at the same side
as the interfering transmitter. Far end crosstalk (FEXT) is
the interference measured at the other end of the cable with
respect to the interfering transmitter. In DSL systems, NEXT
is avoided by using frequency division duplexing (FDD) [2],
or time division duplexing (TDD) [4]. FEXT suppression
involves spectrum shaping, advanced precoding or crosstalk
cancellation (also known as vectoring or DSM level 3). A
detailed surveys of these techniques can be found in e.g., [5–
8].
Over the last few decades, DSL technologies have advanced
in many directions to support the increasing demand for high
data rates without replacing the existing copper infrastructure.
Examples of such directions include increasing the bandwidth, using advanced algorithms for FEXT cancellation, and
deploying fibers closer to the customer-premise equipment
(CPE) so shorter copper lines can be used. For vectored
VDSL modems, the downstream channel is weakly row-wise

diagonally dominated, whereas for the upstream it is columnwise diagonal dominant. Hence, approximate matrix inversion
is used instead of the ZF linear precoding [9]. Alternatively
adaptive LMS based techniques for computing the precoder
have been suggested [10–14]. Similarly, for the upstream,
adaptive linear cancelers have proved to be very efficient
[15, 16].
Gigabit over DSL was presented as early as 2003 [17].
Recently, the G.fast standard was introduced [4] to provide
aggregate data rates of up to 1Gb/sec over short lines up to
250m in length. For this purpose, the bandwidth was increased
from 30MHz to 106MHz in G.fast [4] or 212MHz in the more
advanced version. However, this increased bandwidth has led
to new challenges: At high frequencies the channel matrices
become non-diagonal dominant [9]. Traditional DSL algorithms for crosstalk cancellation/precoding have thus become
inefficient or converge very slowly, because of this significant
increase in bandwidth.
This paper focuses on designing a per tone adaptive
crosstalk canceler for the upstream transmissions in G.fast
systems. Given the tremendous amount of data to be processed
each second1 , low complexity algorithms are necessary. In the
literature, several adaptive algorithms have been proposed that
minimize the mean square error (MSE) at the output of the
crosstalk canceler. Clearly, the most popular algorithm is the
least mean square (LMS) algorithm [18]. LMS is a stochastic
optimization method that under certain conditions converges
to the Minimum MSE (MMSE) solution. The popularity of the
LMS algorithm derives primarily from its simplicity. However,
it is well known that bad conditioning of the input correlation
matrix may lead to slow convergence of the algorithm.
Because it is a stochastic optimization algorithm, the rate
of convergence of the LMS algorithm is controlled by the
step-size parameter µ. While small step size leads to better
precision of the steady state solution, a large step size is
preferable for short transient state (fast convergence). However, if the step size is too large the system becomes unstable,
and the algorithm may not converge at all. Thus, even for an
optimal choice of the step size, the convergence rate strongly
depends on the statistics of the input signal: the conventional
LMS algorithm uses a fixed step-size parameter µ to control
the correction applied to the solution at each iteration. An
exponential convergence in the mean and in the mean square
were shown if the step size is bound by a term that is
inversely proportional to the largest eigenvalue and to the trace

∗

Faculty of Engineering, Bar-Ilan University, Ramat-Gan, 52900, Israel.
Corresponding author, email: avizanz@gmail.com.
These results will be partially presented at EUSIPCO 2016 [1].
\

1 In G.fast there are 2048/4096 sub-carriers and a discrete multitone (DMT)
symbol rate of 48kSymbol/sec [4].

2

(respectively) of the input signal’s correlation matrix and the
rate of convergence was shown to be determined by the spread
of the eigenvalues of the correlation matrix [19–21].
Several LMS derivatives exhibit a faster convergence. In the
normalized LMS (NLMS)[22], a step-size that is normalized
with the power of the input is used (for low power inputs, a
certain regulation parameter is typically used). In the diagonal
step-size matrix approach, a diagonal matrix is used instead
of the scalar step size µ [23]. Another family of algorithms
that converge to the optimal value in the mean square uses a
time variant step-size parameter such that µ = µ(n) is made
inversely proportional to the iteration number n [24]. However,
a decrease in the step-size impairs the tracking performance
of the algorithm when the optimal solution is time variant.
So far, we have assumed a single step size µ for the update
of the solution. However, it is possible to use a diagonal stepsize matrix M instead of µ [23]. The step-size matrix M can
be thought of as a pre-processing of the input vector of the
LMS algorithm in which an appropriate diagonal matrix M
results in a ”new” input vector to the LMS algorithm with an
improved eigenvalue spread of its correlation matrix. Such an
approach was taken in [25], where the LMS algorithm was
applied to an orthogonal transformation of the input signal
(e.g., discrete Fourier transform (DFT) and discrete cosine
transform (DCT)) such that different frequency components of
the filter were assigned different step sizes2 . The Leaky LMS
algorithm is similar to the conventional LMS but minimizes a
slightly modifying cost function [26]. This modification can be
interpreted as an addition of white noise with a certain variance
to the input of the LMS (also known as pre-whitening). If this
variance is appropriately chosen, there is improvement in the
convergence rate. This improvement can be explained by the
fact that the algorithm can be recast as a conventional LMS
with a decreased eigenvalue spread.
Another framework of solutions to accelerate the LMS
utilize a variety of averaging methods of the LMS coefficients
(see for example [27]). In the accelerated LMS, the LMS
component are updated off-line as in the conventional LMS,
but the actual filter that is applied to the data at each iteration
n is a certain averaged version of previous filters. It should be
mentioned that the averaging method showed no asymptotic
improvement; i.e., when a decreasing step-size is used, the
optimal rate of convergence of both systems was the same.
A study of two adaptive filters in tandem [28] showed that
the convergence rate of the system decreased compared to a
single adaptive filter and increased the variance in the steady
state. An extension of the result for multiple filters in tandem
was given in [29]. The tandem scheme is fundamentally
different from the deep-LMS algorithm. As will be shown in
what follows, the deep-LMS algorithm serially concatenates
the blocks. Therefore, the equivalent scheme is the product of
the two blocks and not the sum as in the tandem scheme [29].
Moreover, in the tandem scheme, both LMS components are
updated in each iteration. In our scheme, the preprocessing
matrix is updated infrequently.
2 Note that the orthogonal transformation by itself does not change the
eigenvalue spread of the correlation matrix.

d1
d2
dN

H[n]

ν1

ν2

νN


r1
r2

u1
u2

w1 [ n ] 

w 2 [ n] 

𝐖𝑷 [𝑛]

rN

uN

w N [ n]

W  n



x1


x2 


d2

xN 


dN

d1

Fig. 1. The Deep-LMS crosstalk canceler.

As mentioned above, at high frequencies, G.fast channel
matrices typically have no diagonal dominant structure. Hence,
at these frequencies the received signal’s covariance matrix
is badly conditioned even in cases where the direct channel
gains of all users are of the same order. Therefore, using the
conventional LMS algorithms for FEXT cancellation in G.fast
systems is impractical due to the long convergence times.
Main contributions: In this paper, we propose a new
algorithm dubbed Deep-LMS, which enjoys almost the same
complexity as the conventional LMS algorithm but exhibits a
much faster convergence. The key idea behind the proposed
algorithm can be summarized as follows: the asymptotic
convergence of the LMS algorithm is guaranteed if the step
size is properly chosen. Thus, some progress must be achieved
by the LMS algorithm; i.e., by waiting a sufficiently long time.
This progress is harnessed by the Deep-LMS by updating the
adaptive preprocessing matrix such that the effective channel
matrix becomes more diagonal dominant. Hence, the convergence of the overall system is accelerated.
The update of the preprocessing matrix is inspired by
deep neural networks. However, since all the operations in
the Deep-LMS algorithm are linear, we are able to derive
an exact analysis. In particular, we prove that if the initial
SINR of all users is sufficiently high, the rate of convergence
of the LMS crosstalk canceler is accelerated at each update
of the preprocessing matrix (assuming that there are enough
iterations between the updates).
The structure of this paper is as follows. Section II describes
the system model and the proposed algorithm. Section III
the conventional LMS crosstalk canceler is described. In
Section IV the Deep-LMS algorithm is presented. In section
V we analyze the transition of the Deep-LMS algorithm and
discuss the effects on the overall system. The proof of the
main theorem is given in Section VI. Section VII provides
simulation results for the Deep-LMS algorithm. Section VIII
concludes the paper.
II. S YSTEM MODEL
In this section we describe the model of the received signal.
For simplicity of presentation, the model is described for a
single frequency bin. The operation at other frequency bins is
similar and independent of the operation at any other bin.
Let d[n] denote the transmitted data symbols of all N
users at a certain frequency bin, where d[n] is drawn with
Gaussian i.i.d components and is assumed to be known at
the receiver. More formally, d[n] is a zero mean Gaussian
vector with a correlation matrix of E{d[n]dH [n]} = I and
E{d[n]dH [m]} = 0 for m 6= n, where I is a N × N identity

3

matrix and AH is the conjugate transpose of the matrix A.
The received signal at the output of the channel is
r̆[n] =

√

pHH [n]d[n] + ν̆[n],

(1)

where p is the transmitted power (at that frequency bin),
H[n] = [h1 [n], h2 [n], · · · , hN [n]] is the channel gain matrix,
ν̆[n] is an additive white Gaussian noise (AWGN), ν̆[n] ∈
CN 0, σ̆ν2 I . For convenience, we rewrite equation (1) by
normalizing it with respect to the transmitting power:
r[n] = HH [n]d[n] + ν[n],

√
such that r[n] = r̆[n]/ p, ν[n] ∈ CN 0, σν2 I and σν2 =

(2)
σ̆ν2
p .

III. T HE CONVENTIONAL LMS CROSSTALK CANCELER
In this section we describe the model for a multi-user DSL
system with a conventional LMS crosstalk canceler. An LMS
crosstalk canceler for the upstream transmission of N users
can be easily implemented by N parallel LMS blocks. To
avoid confusion (for reasons that will become clearer in what
follows) we denote the input signal (vector) to the LMS by
u[n]. In the conventual approach, the LMS crosstalk canceler
is directly applied on the received signal, i.e., u[n] = r[n].
The LMS crosstalk canceler (in each tone) can be described
as a matrix
W[n] , [w1 [n], w2 [n], · · · , wN [n]] .

(3)

Hence, the LMS recursion can be written in a matrix form as
W[n + 1] = W[n] − 2µu[n]eH [n]

(4)

and the output of the LMS crosstalk canceler can be written
as x[n] = WH u[n].

IV. T HE D EEP -LMS ALGORITHM
In this section, we present the novel Deep-LMS crosstalk
canceler. Unlike the conventional approach, in this algorithm
the LMS W[n] is not applied directly on the received signal.
Instead, the received signal is preprocessed by a matrix WP .
Hence, the input of the adaptive block can be written as
H
u[n] = WP
[n]r[n].

(5)

The model is illustrated in Fig .1.
The algorithm is initialized with an identity preprocessing
matrix and the preprocessing matrix is updated only at certain
time instances. Denote the set of all update time instances

by U. The algorithm is summarized with the following set of
equations:
W[0] = I

(6)

WP [0] = D̃[0]

(7)

u[n] =

H
WP
[n]r[n]
H

(8)

x[n] = W [n]u[n]

(9)

e[n] = d[n] − x[n]

(10)
H

W̆[n + 1] = W[n] + 2µu[n]e [n]
(
W̆[n + 1] n ∈
/U
W[n + 1] =
I
n∈U
(
WP [n]
WP [n + 1] =
WP [n]W̆[n + 1]D̃[n + 1]

(11)
(12)
n∈
/U
n∈U

(13)

where D̃[n] is the diagonal normalization matrix that satisfies
(HWP [n])i,i = 1 for all i. As can be seen, for n ∈
/ U
the preprocessing matrix remains unchanged and the LMS
block W[n] is updated exactly as in the conventional LMS
crosstalk canceler. For n ∈ U the preprocessing matrix WP [n]
is updated to include the combined effect of the preprocessing
and the current LMS, and the LMS W[n] is initiated back to
I.
The role of the preprocessing matrix is to speed up the
convergence of the LMS crosstalk canceler W[n] between the
updates, i.e., n ∈
/ U and hence speed up the convergence of
the overall system.
V. A NALYSIS OF THE D EEP -LMS ALGORITHM
In this section, we analyze the convergence of the DeepLMS algorithm through a characterization of the minimal
signal to interference plus noise ratio (SINR) at the input
and the output of the LMS crosstalk canceler between two
consecutive updates of the preprocessing matrix. The main
result of this paper (Theorem 1) states that if the update time
is properly chosen, the rate of improvement in the SINR at
the output of the Deep-LMS will be higher after the update
of the preprocessing matrix.
Formally, let H̃[n] = Wp [n]H[n] denote the effective
channel matrix for the LMS crosstalk canceler; i.e., after the
preprocessing. The SINR at the i-th input of the LMS crosstalk
canceler; i.e., the SINR that is measured in ui [n], see Fig. 1
is given by:
Φi [n] = X

|h̃i,i [n]|2
|h̃j,i [n]|2 + σ̃i [n]

,

(14)

j6=i

where σ̃i [n] is the variance of the i-th entry of the colored
H
noise ν̃[n] = WP
[n]ν[n]. The minimal input SINR to the
LMS block is defined as Φ[n] = min Φi [n].
i
In the following analysis, we focus on the set of times
between two updates of the preprocessing matrix; i.e., the set
of times F` , {n` , n` + 1, . . . , n`+1 − 1}, where n` ∈ U
and n`+1 = min{n > n` }, i.e., n`+1 is the first update
n∈U

of the preprocessing matrix WP [n] after time n` . Note that
Wp [n] and H̃[n] do not change during the analyzed interval,

4

and hence Φ[k] = Φ[m] for any k, m ∈ F` . Therefore, it is
convenient to denote the minimal input SINR at these times
by Φ` . The same argument applies to the covariance matrix
R` = E{u[n]uH [n]}.

(15)

In addition, for the sake of readability, the time index n is
omitted in cases where it is clear from the context that n ∈ F` .
Also note that at time n` ∈ U, the LMS crosstalk canceler is
initiated and therefore W[n` ] = I. Hence, at the update time
instance, the input SINR to the LMS block is also the output
SINR of the the Deep-LMS; i.e., the SINR that is measured
in xi [n].
1
, the minimal SINR
Theorem 1. Assuming that µ = 3Tr(R
`)
at time n`+1 is lower bounded by

−1
−1
Φ`+1 ≥ c · an`+1 −n` Φ`
+ η∞ (`)
− 1,
(16)

where

−1
c = 1 + δ (Φ` )
, δ (Φ) = 1+2α(Φ)
Φ−α(Φ) ,

−1

a = 1 − 89 g N1 (1 − α(Φ)+1
,
Φ+1 )
√
√
α(Φ) = N − 1 + N − 1 Φ + 2(N − 1), g(x) = x − 12 x2
for complex LMS and g(x) = x − x2 for LMS over the reals
and η∞ (`) is the maximal MSE of the LMS W at steady state.
1
Note that µ = 3Tr(R
is the maximal update constant sug`)
gested in [21]. This value is a popular choice as it guarantees
the LMS convergence.
Theorem 1 has several important implications. Note that
η∞ (`) is in fact the excess MSE which can be tuned by
decreasing the step size µ at the price of a longer convergence
time. Moreover, η∞ (`) approaches zero when the variance of
the noise approaches zero. This fact is critical in DSL systems,
where the crosstalk interference is much stronger than the
background noise. Thus, η∞ (`) is typically negligible. The
Theorem 1 implications can be summarized (for high SINR)
by:
Φ`+1 & c · an`+1 −n` Φ` .

Furthermore, if Φ` > 1.5N 2 + 3N , both c and a > 1 are
monotonically increasing functions of Φ` . Hence, updating the
preprocessing matrix WP at (sufficiently large) time n`+1 ;
i.e., when c · an`+1 −n` is large enough, will improve the input
SINR of the LMS component at times n > n`+1 . Once the
preprocessing matrix is updated, the (new) minimal SINR at
the input of the LMS is improved accordingly, leading to an
increase in c and a, and hence to a faster convergence rate
of the LMS. Hence, each update of the preprocessing matrix
speeds up the convergence of the entire system.
VI. P ROOF OF T HEOREM 1
Due to the length of the proof, we present the proof through
a sequence of lemmas, but the proofs of most the lemmas
are given in the appendix. Also, for the sake of readability,
we begin by a sketch of the proof: we focus on the set of
times between two updates of the preprocessing matrix; i.e.,
the set of times F` ∪ {n`+1 }. First, we follow the steps in

[20, 21] and characterize the propagation of the MSE at the
output of the crosstalk canceler using a propagation matrix
F` . Then, Lemma 3 upper bounds the maximal MSE at the
output of the Deep-LMS for n ∈ F` in terms of the condition
number of R` , the norm of the propagation matrix F` and
the maximal MSE at the output of the Deep-LMS at time
n` . Lemma 4 and Lemma 5 use a novel bounding analysis to
upper bound each of these terms using the knowledge of the
minimal input SINR. Then, we argue that the operation of the
Deep-LMS at the update time instance n`+1 is composed of
an additional step of the LMS followed by the normalization
D̃. Since a normalization by any diagonal matrix has no effect
on the SINR, we conclude the proof by using Lemma 6 that
characterizes the relationship between the input/output SINR
and the maximal MSE at the output of the LMS block.
−1
Note that if (c · an`+1 −n` Φ` ) + η∞ (`) ≥ 1 the bound
in (16) is negative (or zero) and hence trivial. Furthermore,
this case is not relevant here because it addresses the case
of very low SNR in which the FEXT canceler has no advantages. Thus, in the following we prove Theorem 1 for
−1
(c · an`+1 −n` Φ` ) + η∞ (`) < 1.
For the first lemma, we follow Horowitz et al. [20] and
Feuer et al. [21],3 and write the propagation of the MSE of the
crosstalk canceler coefficients in a recursive form. To that end,
certain notations are needed: let UH
` Λ` U` be the eigenvalue
decomposition of R` , the correlation matrix of the signal after
preprocessing (see 15). Let
V[n] = U` (W[n] − W`∗ ) ,

(17)

W`∗ = R−1
` Rud

(18)

where
is the optimal estimator of d from u and Rud = E{udH }.
Denote by vi [n] and vi,j [n] the i-th column of matrix V[n],
and the j-element in this vector, respectively. We also define
matrix S[n], in which the i, j element is
si,j [n] = E{|vi,j [n]|2 }.

(19)

Let ∗ be the minimum attainable MSE vector; i.e., the vector
that minimizes the cost function J[n] = k[n]k2`2 by choosing
W[n] = W`∗ . Note that
−1
∗i := E{di } − rH
udi R` rudi

(20)

is not affected by the preprocessing matrix and hence does not
depend on n, where rudi = E{ud∗i } and d∗i is the conjugate
of di . Denote the eigenvalues of R` by
0 < λ`,1 ≤ λ`,2 ≤ · · · ≤ λ`N .
Lemma 2. The propagation of the MSE of the coefficients of
W for n ∈ F` can be written as
S[n + 1] = F` S[n] + 4µ2 λ` T∗

(21)

3 It should be mentioned that the convergence analysis of the LMS in [20,
21] was based on the assumption that various data vectors were mutually
independent. In general uses of LMS this assumption is not true (e.g. in
transversal filters). However, in the FEXT cancellation case, this independence
assumption is accurate.

5

where
F` = diag(ρ` ) + 4µ2 λ` λT` ,

(22)

ρ` := [ρ`,1 , ρ`,2 , · · · , ρ`,N ], λ` := [λ`,1 , λ`,2 , · · · , λ`,N ],
ρ`,i = 1 − 4µ` λ`,i + 8qµ2` λ2`,i such that q = 12 for complex
LMS and q = 1 for LMS over the reals. Furthermore, the MSE
vector at the output of the Deep-LMS for n ∈ F` is given by
T

 [n] =

1TN S̃[n]

+

T∗ ,

(23)

where S̃[n] := Λ` S[n].
Proof. The proof for the real case is given in [21]. An explicit
computation for the complex case is given in the Appendix.
As can be seen from (21), the eigenvalues of F` determine
the rate of convergence of S[n] (only between the updates of
the preprocessing matrix). In [21], it was pointed out that for
1
a real LMS, if µ ≤ 3Tr(R
all eigenvalues of F are less than
`)
1 and (21) converges. However, the analysis in [21] is not
sufficient to determine the rate of convergence.
From the recursion (21) it is obvious that
Λ` S[n + 1] =

Λ` F` Λ−1
` Λ` S[n]

+

4µ2` λ2` T∗ ,

(24)

where for any vector v, we use the notation (v2 )j = vj2 .
Denoting F̃` , Λ` F` Λ−1
` , (24) can be rewritten as
S̃[n + 1] = F̃` S̃[n] +

4µ2` λ2` T∗ .

(25)

Note that F̃` and F` are similar matrices and therefore they
share their eigenvalues. Combining (23) and (25) yields that
for any n ∈ F` :
T

 [n] =

`
1TN F̃n−n
S̃[n` ]
`

+

4µ2` 1TN

n−n
` −1
X

F̃k` λ2` T∗ + T∗ .

k=0

(26)
In Lemma 3, we upper bound k[n]k∞ for n ∈ F` , where
k · k∞ indicates the `∞ norm.
Lemma 3. For n ∈ F` , if all eigenvalues of F` are smaller
than 1, the maximal MSE at the output of the Deep-LMS is
given by
k[n]k∞ ≤

λmax (R` )
n−n`
(kF` k1 )
k[n` ]k∞ +η∞ (`), (27)
λmin (R` )

where k · k1 indicates the induced `1 norm. Furthermore,


−1
η∞ (`) ≤ 1 + 4µ2` λT` (I − F` ) λ` k∗ k∞ .

Lemma 4 uses Gershgorin circle theorem to develop bounds
that involves the eigenvalues of R`
Lemma 4. (a) The (`2 -norm based) condition number of R`
is upper bounded by:

where δ (Φ) is defined in Theorem 1.

where α (Φ) is defined in Theorem 1.
Proof. See Appendix A.
Lemma 3 upper bounds the MSE by an expression that
involves the `1 -norm of F` . In order to get the desired bound,
we need to bound kF` k1 using the minimal input SINR. To
that end, we first show that


8
λmin (R` )
kF` k1 = 1 − g
(30)
9
Tr (R` )
1
, where g(x) is defined in Theorem 1. Then,
for µ` = 3Tr(R
`)
using Lemma 4(b) and the monotonicity of g(x) in the relevant
region, we give a SINR-based upper bound on kF` k1 . Lemma
5 summarizes this approach.

Lemma 5. For N ≥ 2,
8
kF` k1 ≤ 1 − g
9




1
(1 − γ(Φ)) ,
N

(28)

(31)

where γ(Φ) is defined in Theorem 1.
Proof. See Appendix A.
1
Observation 1. It is known that for µ` = 3Tr(R
the
`)
eigenvalues of F` are smaller than 1 for LMS over the reals
[21]. Note that using the fact that |λ(F` )| ≤ kF` k1 for any
symmetric matrix and that 0 < g(x) < 1 for 0 ≥ x ≥ 1,
1
equation (30) implies that for µ` = 3Tr(R
the eigenvalues
`)
of F` are smaller than 1 for the complex case as well.

Combining Lemma 3, Lemma 4(a) and Lemma 5, and using
the definitions of a and c from Theorem 1, yields the following
inequality for n ∈ F`
k[n]k∞ ≤ c−1 · a−(n−n` ) k[n` ]k∞ + η∞ (`).

(32)

In order to complete the proof we need to characterize the
relation between the SINR and the MSE at the output of the
Deep-LMS. To that end, denote the SINR at the i-th output of
the Deep-LMS by Ψi [n] and consider the following lemma:
Lemma 6. (a) For n` ∈ U, Φi [n` ] = −1
i [n` ].
(b) If i [n] < 1, the SINR at the output of the Deep-LMS
Ψi [n] ≥ −1
i [n] − 1.
Proof. See Appendix A.
From (32) and Lemma 6(a) we have that for n ∈ F`
k[n]k∞ ≤ c−1 · a−(n−n` ) Φ−1
` + η∞ (`).

Proof. The proof will be given in Appendix A.

λmax (R` )
≤ 1 + δ (Φ` ) ,
λmin (R` )

(b) The ratio between the minimal eigenvalue of R` to the
trace of R` is lower bounded by:


1
α (Φ` ) + 1
λmin (R` )
≥
1−
,
(29)
Tr (R` )
N
Φ` + 1

(33)

The operation of the Deep-LMS at the update time n`+1
is composed of an additional step of the LMS followed by
the normalization by D̃. As the multiplication by a diagonal
matrix does not change the SINR, (33) can also be used for
the evaluation of the SINR at time n`+1 . Thus, the proof of
Theorem 1 is completed by applying Lemma 6(b) on (33) at
time n`+1 . Note that the condition i [n] = 1 is equivalent to
−1
(c · an`+1 −n` Φ` ) + η∞ (`) > 1 which was discussed at the
beginning of the proof.

6

10 5

10

1

10 -1

1.7

jHii j
min X
i
jHij j
j6=i

10 -3
0

50

100

150

200

f[MHz]
Fig. 2. An illustration of the eigenvalue spread of the correlation matrix of
the received signal and the non-diagonal dominant structure of the channel
matrix at high frequencies.

Avetage rate [Gb/sec]

10

3

6max
6min

1.6
1.5
1.4
Deep-LMS
LMS
Accelerated LMS
non-normalized Deep-LMS
Accelerated Deep-LMS

1.3
1.2
1.1
0

2000

4000

6000

8000

n
VII. N UMERICAL R ESULTS
In this section we demonstrate the performance of the DeepLMS algorithm and compare it to the performance of the
conventional LMS. We also examine the performance of the
accelerated versions where the LMS component is replaced by
its averaged version.
In [1], the performance of the Deep-LMS algorithm was
tested using model-based channel matrices. In this paper, we
used channel matrices measured by BT over a 100m 10
pair 0.5mm copper cable [30]. We simulated a typical upstream scenario with a transmit PSD mask as in [31] and a
colored background noise of −140dBm/Hz below 30M Hz
and −150dBm/Hz above 30M Hz [32].
An illustration of the eigenvalue spread of the received
signal correlation matrix is shown in Fig 2. The figure also
illustrates the non-diagonal dominant structure of the channel
matrix at high frequencies. The diagonal dominance is measured by the ratio between the diagonal term and the sum of the
absolute value of all non diagonal terms [33]. Most traditional
DSL algorithms require this ratio to be larger than 1. Thus
Fig. 2 demonstrates the need for novel vectoring algorithms
that can operate in the G.fast bandwidth.
Before we present the performance of the Deep-LMS algorithm, we need to characterize the choice of update times.
Since SINR estimation is an inherent part of the bit-loading
component of the DMT physical layer in DSL systems, the
set of update times U can be easily determined in real time
using the measured SINR. Thus, we update the preprocessing
matrix of the Deep-LMS whenever the SINR is improved by
5dB or when more than ñ iterations have elapsed since the
last non-SINR based update of the preprocessing matrix.
Fig. 3 shows the average sum rate per user in each iteration
using the Deep-LMS and the conventional LMS. The sum rate
of each user was computed by:

K 
X
Rt = W
log2 (1 + SINRi,k [n])
(34)
k=1

bmax

where SINRi,k [n] is the SINR at the output of each algorithm
at the i-th user at the k-th frequency, bmax = 12 is the maximal
number of bits per DMT frequency bin as defined in G.fast,

Fig. 3. Average (over all users) sum rate comparison (g.fast frequency bins
17MHz-200MHz).

[4]) and [x]b = min{x, b}. As can be seen, the Deep-LMS
algorithm converges much faster than the traditional LMS; for
example, it reaches 1.65Gbps in 103 iterations rather than the
3 · 103 iterations in the conventional LMS.
Fig. 3 also depicts the performance of the accelerated
LMS that uses filter averaging of [27]. In this algorithm
(marked AVG-LMS) the LMS component was updated as in
the conventional LMS (4) but the actual filter that was applied
to
at each iteration n was an averaged weight matrix
Pnthe data
n−i
W[i] with a forgetting factor of θ = 0.95. An anali=0 θ
ysis of a stochastic approximation with this averaging method
can be found for example in [34]. This averaging indeed
accelerates the convergence, but it is still much slower than the
Deep-LMS. Furthermore, the same averaging technique can
also be applied to the Deep-LMS (marked AVG Deep-LMS),
resulting in even faster convergence.
To further simplify the algorithm, we also tested performance when D̃ was set to I in (13); i.e., when we violated the
assumption that the preprocessing matrix was normalized such
that the direct effective channel gain of all users was 1. As can
be seen, the loss due to this simplification is negligible. Hence,
we conjecture that this normalization is required mostly for the
analysis, but has no significant effect on actual performance.
To better illustrate the behavior of the different algorithms,
Fig. 4 shows the minimal SINR at the output of the adaptive
crosstalk canceler for each of the algorithms in some specific
frequency bins. This figure provides a better understanding
of the nature of the proposed Deep-LMS algorithm. It shows
that the Deep-LMS starts exactly like the conventional LMS.
But, as soon as the traditional LMS manages to improve the
SINR above a certain point, the Deep-LMS takes advantage
of this improved SINR to produce a significant increase in the
convergence rate.
In the second set of simulations, we simulated a near-far
scenario. Fig 5 illustrates a typical G.fast near-far scenario.
Taking the same channel matrices as above [30] and rewriting

7

95MHz

40
20
0
100

200

300

400

2

20
10
0
0

2000

4000

6000

n

n

mini SINR [dB]

146MHz
15

Deep-LMS
LMS
Accelerated LMS
non-normalized Deep-LMS
Accelerated Deep-LMS

10
5
0
2000

4000

6000

Avetage rate [Gb/sec]

mini SINR [dB]

mini SINR [dB]

56MHz

Deep-LMS Near
Deep-LMS Far
LMS Near
LMS Far

1.5

1

0.5

0
0

0.5

8000

1

1.5

2

n

n

Fig. 4. Minimal output SINR (over all users) comparison at certain frequency
bins.

5 CPEs
5 CPEs
Multi port DPU
Fig. 5. A typical G.fast near far scenario (a FTTB deployment).

them in the form of 5 × 5 blocks


H11 H12
H=
,
H21 H22

(35)

we constructed the channel matries for a near-far scenario in
which there were 5 CPEs that were 100m away from the DPU
and 5 CPEs 200m away by


I
0
HN F =
H.
0 H22
In this set of simulations, we violated the assumption that the
pilots d[n] were zero mean Gaussian and used QPSK symbols
instead; i.e., each of the elements in d[n] was drawn uniformly
at random from the set { √12 (±1 + ±j)}. Fig. 6 shows the
average (achievable) sum rate per user in each iteration using
the Deep-LMS and the conventional LMS, where the rate was
computed as in (34). While the algorithms were computed
for all the users together, the averaging in the figure was
taken separately over the far-users and over the near-users
to better illustrate that our analysis in section V considered
the weakest user. As can be seen, the Deep-LMS algorithm
converges much faster than the traditional LMS; for example,
the average sum rate of the far users reached 600Mbps in
about one quarter of the time.
VIII. C ONCLUSION
In this paper we presented a new multilayer LMS-based
crosstalk canceler for upstream transmission in G.fast sys-

2.5
#10 4

Fig. 6. Average sum rate comparison (g.fast frequancy bins 17MHz-200MHz).

tems. The new crosstalk canceler preprocesses the received
signal using an adaptive matrix prior to a conventional LMS
crosstalk canceler. This preprocessing matrix is initialized by
the identity matrix and at any update of the preprocessing
matrix is set into the product of the current LMS crosstalk
canceler and the current preprocessing matrix. The main goal
of the preprocessing matrix is to modify the effective channel
matrix into a diagonal dominant structure. We showed that the
method can be used to speed up the convergence of the entire
system given that the SINR is sufficiently high. Since, the
preprocessing matrix is not frequently updated, the complexity
of the algorithm is approximately twice the complexity of the
conventional LMS. We believe that the proposed method can
be used to accelerate LMS algorithms in other contexts as
well.
A PPENDIX A
P ROOF OF L EMMAS
Proof of Lemma 2. Following the steps of [20] and adapting
to the complex case, we write (11) for n ∈ F` as

W[n + 1] = I − 2µu[n]uH [n] W[n] + 2µu[n]dH [n].
(36)
Let ũ[n] := Uu[n], then using (17) we can write that
V[n + 1] = U (W[n + 1] − W∗ )


= U I − 2µu[n]uH [n] W[n] + 2µu[n]dH [n] − W∗
= V[n] − 2µũ[n]ũH [n]UW[n] + 2µũ[n]dH [n]
= V[n] − 2µũ[n]ũH [n]U (W[n] − W∗ + W∗ ) +
2µũ[n]dH [n]

= I − 2µũ[n]ũH [n] V[n] + 2µũ[n]eH
∗ [n],

(37)

where the last equality is due to the fact that
e∗ [n] = d[n] − W∗H u.
Denote C(j) [n] = E{vj [n]vjH [n]}. Note that ũ[n] and
vj [n] are independent and that from the orthogonality property

8

we have that E{ũ[n]eH
∗ [n]} = 0. Hence, taking the expectation in (38), the cross terms are eliminated. Following [21] we
can write

`
F̃n−n
= Λ` F`n−n` Λ−1
` .
`

× vj [n]vjH [n] I − 2µũ[n]ũH [n]
4µ2 E{|e∗j [n]|2 ũ[n]ũH [n]}
(j)
(j)
[n] − 2µΛC
(j)

`
kF̃`n−n` S̃[n` ]k1 ≤ kF̃n−n
k1 kS̃[n` ]k1 .
`



+

[n]−

λmax (R` ) n−n`
kF
k1
λmin (R` ) `
λmax (R` )
n−n`
≤
(kF` k1 )
.
λmin (R` )

kF̃`n−n` k1 ≤

2

where the last term in (38) is derived using the identity
E{zzAzzH } = Tr (ΣA) Σ + ΣAΣ, where A is a (deterministic) matrix, Σ = E{zzH } and z is complex Gaussian
random vector.
Focusing on the ith diagonal element of C(j) [n + 1]:

(j)
cii [n + 1] = 1 − 4µλi + 4µ2 λ2i cii (j)[n]
+ 4µ λi

N
X

λp cpp (j)[n] + 4µ2 ∗j λi .

(39)

p=1


Recall that from (19) it follows that sj [n] = diag C(j) [n]
and rewriting (39) in a matrix form yields the propagation of
the MSE of the coefficients of the LMS block. The propagation
of the MSE of the output of the LMS in the complex case can
be derived following the steps of [21]: first, we write the MSE
of the ith output of the LMS as
i [n] = E{|di [n] −

H
w∗i
u[n]

H

2

− (wi [k] − w∗i ) u[n]| }.
(40)

H
By noting that E{u[n] di [n] − w∗i u[n] } = 0 and that
E{u} = 0, the cross terms are eliminated and we can write
that ∆[n] = i [n] − ∗i
H

∆[n] = E{(wi [n] − w∗i ) u[n]uH [n] (wi [n] − w∗i )}


H
= E{Tr (wi [n] − w∗i ) u[n]uH [n] (wi [n] − w∗i ) }


H
= Tr E{u[n]uH [n] (wi [n] − w∗i ) (wi [n] − w∗i ) }


H
= Tr E{u[n]uH [n]}E{(wi [n] − w∗i ) (wi [n] − w∗i ) }


= Tr RUH C(i) [n]U


= Tr UH ΛUUH C(i) [n]U




= Tr ΛC(i) [n]UUH = Tr ΛC(i) [n]
(41)
the lemma now follows.
Proof of Lemma 3. From (26), it is obvious that
`
k[n]k∞ ≤ k1TN F̃n−n
S̃[n` ]k∞ + η̃` · k∗ k∞ ,
`

where η̃` = 4µ2` 1TN

n−n
` −1
X

(42)

(46)

Since all entries of S̃ are non-negative real numbers we have
that
kS̃[n` ]k1 = k1TN S̃[n` ]k∞ = k[n` ]k∞ .
(47)
(27) follows from the fact that if all eigenvalues of F` are
smaller than 1, the first term in the RHS of (26) is eliminated
and therefore it is obvious that
η∞ (`) = 4µ2` 1TN

n−n
` −1
X

F̃k` λ2` k∗ k∞ + k∗ k∞ .

(48)

k=0

Substituting F̃` we have that
1TN

n−n
` −1
X

ΛFk Λ−1 λ2 =

n−n
` −1
X

k=0

λT Fk λ.

k=0

Since F is positive definite, we have that λT Fk λ > 0 for all
k > 0 and λ ∈ RN . Hence,
!
n−n
∞
∞
` −1
X
X
X
λ T Fk λ ≤
λ T Fk λ = λ T
Fk λ, (49)
k=0

k=0

k=0

The claim now follows.
Proof of Lemma 4. Note that since u[n] = H̃H [n]d[n] +
ν̃[n] and that d[n] and ν[n] are independent of each other,
the entries of R` = E{u[n]uH [n]} are given by:
(
kh̃i k22 + σ̃i2
i=j
(R` )i,j =
(50)
H
∗
h̃i h̃j + E{ν̃i ν̃j } i 6= j,
where h̃i is the i-th column of H̃. Define the sum of the
absolute valuesX
of the off-diagonal elements of the row i in
R` by B`,i ,
| (R` )i,j |. Recall that λ`,i i = 1, 2, · · · , N
j6=i

are the eigenvalues of R` . From Gershgorin circle theorem,
we have that all eigenvalues are in the union of the following
regions
|λ − (kh̃i k22 + σ̃i2 )| ≤ B`,i

i = 1, 2, · · · , N.

(51)

Rearranging the expression we have that

F̃k` λ2` + 1. Since all entries of F̃`

k=0

kh̃i k22 + σ̃i2 − B`,i ≤ λ ≤ kh̃i k22 + σ̃i2 + B`,i .

(52)

Since by assumption h̃ii [n] = 1, 1 ≤ kh̃i k22 + σ̃i2 . Hence,

and S̃[n] are non-negative real numbers we have that
`
`
k1TN F̃n−n
S̃[n` ]k∞ = kF̃n−n
S̃[n` ]k1 .
`
`

(45)

The fact that for all i and j we have that λ`,i > 0 and
(F` )ij ≥ 0 yields

2µC [n]Λ + 4µ ∗j Λ+
 


4µ2 Tr ΛC(j) [n] Λ + ΛC(j) [n]Λ , (38)

2

(44)

It is easy to verify that since F̃` = Λ` F` Λ−1
`

C(j) [n + 1] =E{vj [n + 1]vjH [n + 1]}


=E I − 2µũ[n]ũH [n] ×

=C

The sub-multiplicative property of the induced norm yields

(43)

1 − B`,i ≤ λ.

(53)

9

On the other hand, using (14) and Φ` = min Φi [n] implies
i
that
X
1
1
≥
=
|h̃j,k |2 + σ̃k2 .
(54)
Φ`
Φi [n]
j6=k

Hence, for any k and B ⊆ {k}c we have that
X
1
≥
|H̃j,k |2 + σ̃k2 = k(h̃k ){k}c k2 + σ̃k2 ≥ k(h̃k )B k2 .
Φ`
j6=k

(66)

2

By adding |h̃k,k | = 1 to both sides of (54) we have that
X
1
≥ |h̃k,k |2 +
1+
|h̃j,k |2 + σ̃k2 = kh̃k k22 + σ̃k2 . (55)
Φ`

Therefore, (65) becomes

j6=k

|h̃H
i h̃j | ≤

Hence,


X
1
Tr (R` ) =
kh̃k k22 + σ̃k ≤ N 1 +
.
Φ

(56)

1
+ |h̃j (i)| + |h̃i (j)|.
Φ`

(67)

Summing the expression in (67) over j 6= i yields

k

Combining (52), (53) and (55) yields
1
1 − B`,i ≤ λ ≤ 1 + + B`,i .
Φ
Hence,
1
1 − B` ≤ λmin (R` ) ≤ λmax (R` ) ≤ 1 + + B` ,
Φ

X
(57)

(58)

1 + Φ1 + B`
λmax (R` )
≤
.
λmin (R` )
1 − B`

(59)

On the other hand, combining (53) and (56) yields
λmin (R` )
1 − B`
.
≥
Tr (R` )
N 1 + Φ1

(60)

Lemma 7. B` is upper bounded by:
α (Φ` )
.
Φ`
Proof of Lemma 7. From (50)
X
X
B`,i ≤
|h̃H
|E{ν̃i ν̃j∗ }|.
i h̃j | +

=

|h̃i (i)h̃∗j (i)

+

j6=i

(61)

(68)

j6=i

From
the Cauchy-Schwartz inequality it is known that kxk1 ≤
√
nkxk2 , where n is the dimensionality of vector x. Hence,
√
N −1 X
+
|h̃j (i)| + N − 1k(h̃i ){i}c k2 .
Φ`
j6=i
j6=i
(69)
By the SINR assumption both k(h̃i ){i}c k22 and |h̃j (i)|2 are
less than or equal to Φ1` . Hence, from (69) we have that
|h̃H
i h̃j | ≤

X

|h̃H
i h̃j | ≤

N −1 N −1
+ √
+
Φ`
Φ`

r

N −1
.
Φ`

(70)

using the
The second term in (61) can be bounded by NΦ−1
`
q
fact that |E{ν̃i ν̃j∗ }| ≤ σ̃i2 σ̃j2 ≤ max{σ̃i2 , σ̃j2 } ≤ Φ1` (where
the first inequality is due to the CauchySchwarz inequality).
Lemma 7 now follows.

j6=i

Denote A = {i, j} then for i 6= j:
|h̃H
i h̃j |

X
N −1 X
+
|h̃j (i)| +
|h̃i (j)|.
Φ`

j6=i

B` ≤

j6=i

j6=i

X

where B` , maxj B`,j . Thus,

|h̃H
i h̃j | ≤

h̃i (j)h̃∗j (j)

+

X

h̃i (m)h̃∗j (m)|

Combining (59), (60) and Lemma 7 concludes the proof of
Lemma 4.

m∈Ac

(62)
≤

|h̃i (i)h̃∗j (i)|

+

|h̃i (j)h̃∗j (j)|

+|

X

h̃i (m)h̃∗j (m)|

Proof of Lemma 5. First, we use Lemma 8 to establish a
closed-form expression of kF` k1 .

m∈Ac

(63)
≤

|h̃i (i)h̃∗j (i)|

+

|h̃i (j)h̃∗j (j)|

+ k(h̃i )Ac k2 k(h̃j )Ac k2 ,
(64)

where the last step is due to the Cauchy-Schwarz inequality
and for any set A ⊆ {1, 2, · · · , N } and a vector v, vA denotes
the vector constructed from the entries of v indexed by A.
Since
h̃i,i = h̃i (i) = h̃j,j = h̃∗j (j) = 1

Lemma 8. For µ` =

1
3Tr(R)

we have that

8
kF` k1 = 1 − g
9



λmin (R` )
Tr (R` )


.

Proof. Since F` is symmetric and its entries are all nonnegative, we can write that
kF` k1 = max F`,i ,

we have that

(71)

i

∗
|h̃H
i h̃j | ≤ k(h̃i )Ac k2 k(h̃j )Ac k2 + |h̃j (i)| + |h̃i (j)|.

From the definition of Φ` :

−1
X
Φk = 
|H̃j,k |2 + σ̃k2  ≥ Φ` .
j6=k

(65)
where F`,i ,

X

(F` )i,j . From (22) we have that

j

F`,i = ρ`,i + 4µ2` λ`,i

X
j

λ`,j

(72)

10

1
λ`,j
3Tr(R` ) , Tr (R)` =

j2
λ`,i
8q
4 λ`,i
we
3 Tr(R` ) + 9
Tr(R` )

P

Since µ` =
ρ`,i = 1 −

F`,i = 1 −

8q
4 λ`,i
+
3 Tr (R` )
9



λ`,i
Tr (R` )

and

Lemma 5 now follows.

can write that

2

Proof of Lemma 6. From (2), (8) and (9) we have that

+ 4µ2` λ`,i Tr (R` )

2
λ`,i
4 λ`,i
+
Tr (R` )
9 Tr (R` )

2 !
8
λ`,i
λ`,i
=1−
−q
9 Tr (R` )
Tr (R` )


8
λ`,i
=1− g
.
(73)
9
Tr (R` )
=1−

4 λ`,i
8q
+
3 Tr (R` )
9



For complex-LMS, g(x) = x − 12 x2 is monotonically increasing in x ∈ [0, 1] and hence the maxima in (71) is obtained for
i = 1 and the proof is completed.
λ`,1
is a minimizer of
In what follows, we show that Tr(R
`)


λ`,i
g Tr(R` ) also for the real case and hence the lemma follows.
λ

`,i
To that end, it is convenient denote ψ`,i , Tr(R
for i =
`)
1, 2, · · · , N . Hence, combining (71) and (73) results in

8
kF` k = 1 − min g (ψ`,i ).
9 i

(74)

Since g(x) is concave, for any ψ`,1 ≤ ψ`,k ≤ ψ`,N k =
2, · · · , N −1 we have that g (ψ`,k ) ≥ min{g (ψ`,1 ) , g (ψ`,N )}.
Hence,
min g (ψ`,i ) = min{g (ψ`,1 ) , g (ψ`,N )}.
i

(75)

Note that g(x) is monotonically increasing when x ∈ [0, 0.5]
and monotonically decreasing when x ∈ (0.5, 1]. Hence, it is
obvious that if ψ`,N ≤ 0.5 we have that
g (ψ`,1 ) = min{g (ψ`,1 ) , g (ψ`,N )}.
On the other hand, since
we have that
ψ`,N = 1 −

N
X

H
H
x[n] = WH [n]WP
[n]HH [n]d[n] + WH [n]WP
[n]ν[n].
(77)
Denote the effective channel by Ȟ[n] , H[n]WP [n]W[n]
H
and the effective noise by ν̌[n] , WH [n]WP
[n]ν[n] and
2
denote the variance of ν̌i [n] by σ̌i . Thus, we can rewrite (77)
by

x[n] = ȞH [n]d[n] + ν̌[n].

It is easy to verify that the MSE at the i-th output of the
Deep-LMS is given by
X
i [n] = E{|di [n] − xi [n]|2 } = |1 − ȟii |2 +
|ȟjj |2 + σ̌i2 .
j6=i

(79)
On the other hand, the SINR at the i-th output of the DeepLMS is given by
Ψi [n] = X

|ȟii |2
|ȟjj |2 + σ̌i2

i=1

Hence, if ψ`,N > 0.5, we have that g (ψ`,N ) ≥
g (1 − (N − 1) ψ`,1 ). Denote ∆g = g (1 − (N − 1) ψ`,1 ) −
g (ψ`,1 ). It is easy to see that


1
∆g = N (N − 2)ψ`,1
− ψ`,1 .
N
X
1
Since N ≥ 2 and ψ`,1 ≤ N1
ψ`,j =
, we have that
N
j
∆g ≥ 0. Hence, g (ψ`,1 ) = min{g (ψ`,1 ) , g (ψ`,N )} and the
proof is completed.
λ

`,i
Since N ≥ 2, we have that Tr(R
≤ 0.5. Hence, from the
`)
monotonic property of g(x) in the region x ≤ 0.5 and Lemma
4(b) we have that




1 1 + α(Φ)
λ`,i
g
≥g
.
(76)
Tr (R` )
N Φ+1

(80)

Thus, combining (79) and (80) yields
Ψi [n] =

|ȟii |2
.
i [n] − |1 − ȟii |2

(81)

For n` ∈ U we have that ȟii [n] = 1 since at these times
W[n] is initiated to the identity matrix and WP is normalized
such that it has 1 on the diagonal. Hence, (a) follows.
Obviously, we can always write that

ψ`,i = 1 and ψ`,j > 0 for all j

ψ`,i ≤ 1 − (N − 1)ψ`,1 .

.

j6=i

Ψi [n] ≥

i=1
N
−1
X

(78)

|ȟii |2
.
i [n]

Hence, in the case that |ȟii | ≥ 1 (b) follows. Therefore, in the
rest of the proof we assume that |ȟii | < 1.
We observe that
|1 − ȟii |2 ≥ 1 − |ȟii |

2

.

(82)

Hence, from (81) it is implied that
|ȟii |2

Ψi [n] ≥

2
i [n] − 1 − |ȟii |
≥ min Ω(ω),
1>ω>0

(83)

2

ω
where Ω(ω) = i [n]−(1−ω)
2 . It is easy to verify that if
i [n] < 1, Ω(ω) is minimized when ω = 1 − , hence


Ψi [n] ≥ Ω 1 − i [n] = −1
i [n] − 1.

(84)

11

R EFERENCES
[1] A. Zanko, I. Bergel, and A. Leshem, “Gigabit DSL: a DeepLMS Approach,” submitted to EUSIPCO 2016, 2016.
[2] J. Bingham, ADSL, VDSL, and multicarrier modulation. Wiley
New York, 2000.
[3] T. Starr, J. Cioffi, and P. Silverman, Understanding digital
subscriber line technology. Prentice Hall PTR, 1999.
[4] ITU-T G.9700, “Fast access to subscriber terminals (G.fast)
Power spectral density specification,” 2014.
[5] J. Cioffi, M. Brady, V. Pourahmad, S. Jagannathan, W. Lee,
Y. Kim, C. Chen, K. Seong, D. Yu, and M. Ouzzif, “Vectored
DSLs with DSM: the road to ubiquitous gigabit DSLs,” 2006.
[6] S. Huberman, C. Leung, and T. Le-Ngoc, “Dynamic spectrum
management (DSM) algorithms for multi-user xDSL,” IEEE
Communications Surveys & Tutorials, vol. 14, no. 1, pp. 109–
130, 2012.
[7] I. Bergel and A. Leshem, “Signal Processing for Vectored Multichannel VDSL,” Academic Press Library in Signal Processing:
Communications and Radar Signal Processing, vol. 2, p. 295,
2013.
[8] C. Leung, S. Huberman, K. Ho-Van, and T. Le-Ngoc, “Vectored DSL: potential, implementation issues and challenges,”
Communications Surveys & Tutorials, IEEE, vol. 15, no. 4, pp.
1907–1923, 2013.
[9] A. Leshem and L. Youming, “A low complexity linear precoding technique for next generation VDSL downstream transmission over copper,” IEEE Transactions on Signal Processing,
vol. 55, no. 11, pp. 5527–5534, 2007.
[10] I. Bergel and A. Leshem, “Convergence analysis of downstream
VDSL adaptive multichannel partial FEXT cancellation,” IEEE
Transactions on Communications, vol. 58, no. 10, pp. 3021–
3027, 2010.
[11] I. Binyamini, I. Bergel, and A. Leshem, “Arbitrary partial FEXT
cancellation in adaptive precoding for multichannel downstream
VDSL,” IEEE Transactions on Signal Processing, vol. 60,
no. 11, pp. 5754–5763, 2012.
[12] R. Cendrillon, G. Ginis, and M. Moonen, “A near-optimal linear
crosstalk precoder for downstream VDSL,” IEEE Transactions
on Communications, vol. 55, no. 5, pp. 860–863, 2007.
[13] J. Louveaux and A. Van der Veen, “Adaptive DSL crosstalk
precancellation design using low-rate feedback from end users,”
IEEE Signal Processing Letters,, vol. 13, no. 11, pp. 665–668,
2006.
[14] ——, “Adaptive precoding for downstream crosstalk precancelation in DSL systems using sign-error feedback,” IEEE
Transactions on Signal Processing, vol. 58, no. 6, pp. 3173–
3179, 2010.
[15] R. Cendrillon, M. Moonen, G. Ginis, K. Van Acker, T. Bostoen,
and P. Vandaele, “Partial Crosstalk Cancellation for Upstream
VDSL,” EURASIP Journal on Advances in Signal Processing,
vol. 2004, no. 10, pp. 1–16, 2004.
[16] J. Homer, M. Gujrathi, R. Cendrillon, I. L. Clarkson, and
M. Moonen, “Adaptive NLMS partial crosstalk cancellation in
digital subscriber lines,” in Fortieth Asilomar Conference on
Signals, Systems and Computers, 2006. ACSSC’06.
IEEE,
2006, pp. 1385–1389.
[17] J. Cioffi, M. Mosheni, A. Leshem, and Y. Li, “GDSL (Gigabit
DSL),” T1E1.4 contribution T1E1.4/2003-487R1, 2003.
[18] B. Widrow and M. Hoff, “Adaptive switching circuits,” 1960.
[19] B. Widrow, “Adaptive filters,” Aspects of network and system
theory, pp. 563–587, 1971.
[20] L. Horowitz and K. Senne, “Performance advantage of complex
LMS for controlling narrow-band adaptive arrays,” IEEE Transactions on Circuits and Systems, vol. 28, no. 6, pp. 562–576,
1981.
[21] A. Feuer and E. Weinstein, “Convergence analysis of LMS
filters with uncorrelated Gaussian data,” IEEE Transactions on
Acoustics, Speech and Signal Processing, vol. 33, no. 1, pp.
222–230, 1985.

[22] J. Nagumo and A. Noda, “A learning method for system identification,” IEEE Transactions on Automatic Control, vol. 12,
no. 3, pp. 282–287, 1967.
[23] R. Harris, D. Chabries, and F. Bishop, “A variable step (VS)
adaptive filter algorithm,” IEEE Transactions on Acoustics,
Speech and Signal Processing, vol. 34, no. 2, pp. 309–316, Apr
1986.
[24] H. Kushner and G. Yin, Stochastic approximation and recursive
algorithms and applications. Springer Science & Business
Media, 2003, vol. 35.
[25] S. S. Narayan, A. M. Peterson, and M. J. Narasimha, “Transform domain LMS algorithm,” IEEE Transactions on Acoustics,
Speech and Signal Processing, vol. 31, no. 3, pp. 609–615,
1983.
[26] K. Mayyas and T. Aboulnasr, “Leaky LMS algorithm: MSE
analysis for Gaussian data,” IEEE Transactions on Signal Processing, vol. 45, no. 4, pp. 927–934, Apr 1997.
[27] H. J. Kushner and J. Yang, “Stochastic approximation with averaging of the iterates: Optimal asymptotic rate of convergence for
general processes,” SIAM Journal on Control and Optimization,
vol. 31, no. 4, pp. 1045–1062, 1993.
[28] K. Ho, “A study of two adaptive filters in tandem,” IEEE
Transactions on Signal Processing, vol. 48, no. 6, pp. 1626–
1636, 2000.
[29] ——, “Performance of multiple LMS adaptive filters in tandem,” IEEE Transactions on Signal Processing, vol. 49, no. 11,
pp. 2762–2773, 2001.
[30] “G.fast: Release of bt cable measurements for use in simulations,” TD 2012-11-4A-TC-BT-R2, 10 2012.
[31] ITU-T G.9701, “Fast Access to Subscriber Terminals (FAST)
Physical layer specification,” 2014.
[32] Coexistence of G. fast and VDSL in FTTdp and FTTC Deployments. Proceedings of the 23rd European Signal Processing
Conference (EUSIPCO-2015), 2015.
[33] I. Bergel and A. Leshem, “The performance of zero forcing
DSL systems,” IEEE Signal Processing Letters, vol. 20, no. 5,
pp. 527–530, 2013.
[34] I. Wang, E. Chong, and S. Kulkarni, “Weighted averaging and
stochastic approximation,” Mathematics of Control, Signals and
Systems, vol. 10, no. 1, pp. 41–60, 1997.

