Masked Toeplitz covariance estimation

arXiv:1709.09377v1 [cs.IT] 27 Sep 2017

Maryia Kabanava∗ and Holger Rauhut∗
September 28, 2017

Abstract
The problem of estimating the covariance matrix Σ of a p-variate distribution
based on its n observations arises in many data analysis contexts. While for n > p, the
classical sample covariance matrix Σ̂n is a good estimator for Σ, it fails in the highdimensional setting when n ≪ p. In this scenario one requires prior knowledge about
the structure of the covariance matrix in order to construct reasonable estimators.
Under the common assumption that Σ is sparse, a refined estimator is given by M · Σ̂n ,
where M is a suitable symmetric mask matrix indicating the nonzero entries of Σ and
· denotes the entrywise product of matrices. In the present work we assume that Σ
has Toeplitz structure corresponding to stationary signals. This suggests to average
the sample covariance Σ̂n over the diagonals in order to obtain an estimator Σ̃n of
Toeplitz structure. Assuming in addition that Σ is sparse suggests to study estimators
of the form M · Σ̃n . For Gaussian random vectors and, more generally, random vectors
satisfying the convex concentration property, our main result bounds the estimation
error in terms of n and p and shows that accurate estimation is indeed possible when
n ≪ p. The new bound significantly generalizes previous results by Cai, Ren and
Zhou and provides an alternative proof. Our analysis exploits the connection between
the spectral norm of a Toeplitz matrix and the supremum norm of the corresponding
spectral density function.

1

Introduction

1.1

Masked covariance estimation

Estimating the covariance matrix of a random vector X in Rp from n i.i.d. sample observations X1 , . . . , Xn plays a key role in various data analysis tasks. Recently, the case n ≪ p
of small sample size has attracted increasing attention due to its appearance in applications
including mobile communication problems, gene expression studies and more.
Let X be random vector in Rp which we assume to have mean zero throughout this
article. (The general case of non-zero mean can be handled as in [16, Remark 4].) Its
RWTH Aachen University, Lehrstuhl C für Mathematik (Analysis), Pontdriesch 10, 52062 Aachen,
Germany
∗

1

covariance matrix is defined as Σ = E XX T . The sample covariance matrix of a sequence of
n i.i.d. observations X1 , . . . , Xn of X is defined by
n

Σ̂n =

[σ̂st ]ps,t=1

1X
=
Xi XiT
n i=1

(1)

and it is an unbiased estimator of Σ. If X is Gaussian and n ≥ Cε−2 p then the estimation
error in the spectral norm satisfies
kΣ̂n − Σk ≤ ε
with probability at least 1 − 2 exp(−cn), see e.g. [23, Corollarly 5.50], or [23, Corollary 5.50]
for a variant for heavy-tailed distributions. Since the rank of Σ̂n is at most n, the given
bound of n in terms of p cannot be improved for general Σ, i.e., a sample size of n ≥ p is
necessary.
However, in modern applications it is desirable to find good estimators of the covariance
matrix Σ when n ≪ p. Such estimators reflect prior knowledge about the structure of Σ.
A common assumption is that Σ is sparse, i.e., a significant amount of entries of Σ is 0 or
close to 0. Then the so-called masked covariance estimator is defined as M · Σ̂n , where M is
a symmetric mask matrix and · denotes the entrywise product of matrices. Each entry mij
of M indicates how important it is to estimate the interaction between the i-th and j-th
variable. The masked approach was first introduced in [16] and it allows to describe several
regularization techniques such as banding or tapering of the covariance matrix in the case
of ordered variables [4, 6, 11], and thresholding in the case of unordered variables [3, 7, 10].
The accuracy of the masked estimator can be analyzed by splitting it into two terms via
the triangle inequality
kM · Σ̂n − Σk ≤ kM · Σ̂n − M · Σk + kM · Σ − Σk,

(2)

where k · k denotes the spectral norm of a matrix. The bias term kM · Σ − Σk describes how
well Σ fits the model described by M. The variance term kM · Σ̂n − M · Σk measures how
accurately the part of the sample covariance matrix approximates the corresponding part of
the true covariance matrix. The intuition behind the use of M is that M · Σ preserves the
essential structure of Σ, but at the same time M · Σ̂n does not deviate too much from its
mean.
In [16] the authors considered a p-variate Gaussian distribution and studied the problem
of estimating the variance term kM · Σ̂n −M ·Σk for an arbitrary fixed symmetric M ∈ Rp×p .
Theorem 1. Let X1 , . . . , Xn be drawn from a multivariate Gaussian distribution N(0, Σ).
Let M ∈ Rp×p . Then


kMk1,2 kMk
3
√
E kM · Σ̂n − M · Σk ≤ C log (2p)
kΣk,
(3)
+
n
n


P 2 1/2
where kMk1,2 = max
mij
.
j

i

2

In the particular case when the entries of M are either 0 or 1, estimate (3) leads to the
following corollary.
Corollary 1. Let X1 , . . . , Xn be drawn from a multivariate Gaussian distribution N(0, Σ).
Assume that the entries of M ∈ Rp×p are equal to 0 or 1 and that there are at most m
nonzero entries in each column. Then
r

m m
3
E kM · Σ̂n − M · Σk ≤ C log (2p)
kΣk.
(4)
+
n
n
The proof of Theorem 1 is based on decoupling, conditioning, covering argument and
Gaussian concentration inequality for Lipschitz functions. It also allows to achieve error
bounds that hold in probability.
By means of a matrix moment inequality an error estimate that holds in expectation was
generalized to arbitrary distributions with finite fourth moments in [9]. When restricted to
the Gaussian case it provides an improvement of (3) in the logarithmic factor.

1.2

Banding and tapering estimators of Toeplitz covariance matrices

In this paper we are interested in obtaining bounds similar to (3) and (4) under the additional
assumption that X is stationary, resulting in the covariance matrix Σ to be of Toeplitz
structure,


σ0 σ1 σ2 . . . . . . σp−1

.. 
 σ1 σ0 σ1 . . .
. 

.. 
.
.
.


. 
 σ2 σ1 . . . . . .
Σ= .
(5)
.
.. .. ..
 ..

.
.
.
σ
σ
1
2


 ..

..
 .
. σ1 σ0 σ1 
σp−1 . . . . . . σ2 σ1 σ0

Stationary signals appear in many applications including time series analysis and mobile
communications. Our intuition is that the additional structure allows to further reduce the
required number of samples. The easiest way to improve the sample covariance estimator
for this setting is to average the entries of Σ̂n in (1) over the diagonals. For 0 ≤ r ≤ p − 1,
set
1 X
σ̂st
σ̃r =
p − r s−t=r

and define a new unbiased estimator as the Toeplitz matrix Σ̃n = [σ̃st ]ps,t=1 with σ̃st = σ̃|s−t| .
Assuming that there is an ordering among the variables of X and that the variables,
which are far apart, are only weakly correlated, we may construct more accurate estimators
of Σ, so called banding and tapering estimators [6], that we describe here with the mask

3

formalism. For a given positive integer m ≤

r ≤ m2 ,
 1,
2 − 2r
, m2 < r ≤ m,
ar =
m

0,
otherwise,

p
2

and 0 ≤ r ≤ p − 1, set
and br =



1, r ≤ m,
0, otherwise.

The tapering and banding estimators are defined as Mtap · Σ̃n and Mband · Σ̃n , where
(Mtap )st = a|s−t|

and

(Mband )st = b|s−t| .

A bound on the variance term in the error bound (2) for either the tapering or banding
mask can be derived from results in [6], see eq. (22) and Lemma 5 of loc. cit.
Theorem 2. Let X1 , . . . , Xn be drawn from a multivariate Gaussian distribution N(0, Σ).
Let M ∈ Rp×p be a tapering or banding mask with m ≤ 2p . Then
s
m log(np)
E kM · Σ̃n − M · Σk ≤ C
.
(6)
np
Comparing (4) and (6), we see that there is an improvement by a factor of √1p in the
error bound for Toeplitz matrices. However, the result (6) holds only for the special type of
masks M, whereas (4) is valid for any symmetric M ∈ Rp×p . Our goal is to extend the error
estimate (6) to general Toeplitz masks and not necessarily Gaussian distributions.

1.3

Our contribution

Our result holds for distributions that satisfy the so-called convex concentration property,
see Definition 1 below which includes mean-zero Gaussian random vectors. The class of
such distribution is, however, much broader than the Gaussian class. For a Toeplitz mask
M ∈ Rp×p with Mst = ω|s−t| ≥ 0, we define the weighted ℓ1 - and ℓ2 -norm of its first row
ω = (ωℓ )p−1
ℓ=0 by
!1/2
p−1
p−1
X
X
ωℓ2
ωℓ
.
and kωk2,∗ =
kωk1,∗ =
p−ℓ
p−ℓ
ℓ=0
ℓ=0

Theorem 3. Let X1 , . . . , Xn be drawn from a distribution X ∈ Rp such that E X = 0,
Σ = E XX T is Toeplitz and X satisfies the convex concentration property with constant K.
Let the Toeplitz mask M ∈ Rp×p with first row ω. Then for every t > 0,
!!
r
t
kωk
t
1,∗
P kM · Σ̃n − M · Σk ≥ CK 2 kωk2,∗
≤ Cpe−t ,
(7)
+
n
n

and
E kM · Σ̃n − M · Σk ≤ CK

2

kωk2,∗
4

r

log(p)
log(p)
+ kωk1,∗
n
n

!

.

(8)

We note that error bound (8) in expectation also holds in the mean square error (MSE),
as follows easily from the probability bound (7) together with integration. The logarithmic
factor in (8) cannot be removed in general, see also Section 1.4 below.
By estimating the weighted ℓ1 and ℓ2 -norm of either the tapering or banding mask, we
obtain the following result which generalizes and very slightly improves Theorem 2 above
from [6]. Moreover, it provides an alternative proof.
Corollary 2. Let X1 , . . . , Xn be drawn from a distribution X ∈ Rp such that E X = 0,
Σ = E XX T is Toeplitz and X satisfies the convex concentration property with constant K.
Let M ∈ Rp×p be a tapering or banding mask with m ≤ 2p . Then
s
!
m
log(p)
m
log(p)
.
(9)
+
E kM · Σ̃n − M · Σk ≤ CK 2
pn
pn
In the Gaussian case X ∼ N(0, Σ), we have K 2 = 2kΣk, so that
s
!
m log(p) m log(p)
.
+
E kM · Σ̃n − M · Σk ≤ CkΣk
pn
pn

(10)

Corollary 2 implies that for an error tolerance ε ∈ (0, 1), the sample size
m
n ≥ C 2 ε−2 log(p)
p
is sufficient for
E kM · Σ̃n − M · Σk ≤ εkΣk.

Therefore, even though the number of observations may be significantly smaller than the
dimension of the underlying distribution, partial estimation of the covariance matrix is
performed with small error.
In some applications, Toeplitz covariance matrices may have a sparsity structure that is
more complicated than the one induced by the banding estimator in the sense that zeros in
ω interleave with nonzero entries. This includes spectrum sensing applications [25] where
one needs to test the occupancy of spectral bands for wireless communication purposes.
Man made signals, for instance in OFDM [8], may have statistics with Toeplitz covariance
matrices and non-trivial sparsity structure with some zeros close to the diagonal and some
non-zeros far away from the diagonal.
Denoting by S ⊂ {0, . . . , p − 1} the support of the first row of a sparse Toeplitz matrix
Σ, it is natural to work with a Toeplitz mask M having first row ω = 1S being the indicator
of S, i.e., ωj = 1 for j ∈ S and ωj = 0 for j ∈
/ S. The following weighted version of
the cardinality of S, introduced in similar form in [19], determines the required number of
samples,
X p
ν(S) =
.
p
−
ℓ
ℓ∈S

Observe that for ω = 1S , ν(S) = pkωk1,∗ = pkωk22,∗ . If S is contained in a band of length q,
p
#S and for q ≤ p/2 we have #S ≤ ν(S) ≤ 2#S. The
i.e., S ⊂ {0, . . . , q} then ν(S) ≤ p−q
following is an immediate consequence of Theorem 3.
5

Corollary 3. Let X1 , . . . , Xn be drawn from a distribution X ∈ Rp such that E X = 0,
Σ = E XX T is Toeplitz and X satisfies the convex concentration property with constant
K. Let M ∈ Rp×p be sparse Toeplitz with Mst = ω|s−t| ∈ {0, 1} where ω has support
S ⊂ {0, . . . , p − 1} of weighted cardinality ν(S). Then for every t > 0,
s
!!
ν(S)t
ν(S)t
P kM · Σ̃n − M · Σk ≥ CK 2
≤ Cpe−t ,
+
pn
pn
and
E kM · Σ̃n − M · Σk ≤ CK 2

s

ν(S) log(p) ν(S) log(p)
+
pn
pn

!

.

In the case of a Gaussian distribution this result reduces to the previously known Theorem 2 for the banding estimator if S = {0, . . . , m}, but may handle general sparsity patterns
(and more general distributions). For instance, if S ⊂ {0, . . . , p/2} of (small) cardinality
s = #S, then as few as
s
n ≥ Cε−2 log(p)
p
samples ensure kM · Σ̃n − M · Σk ≤ εkΣk with high probability.
Remark 1. It would be interesting to investigate whether the error bound (8) in expectation
can be generalized to heavier tailed distributions in the spirit of the main results in [9] which
only assume finite fourth moments. It is however presently not clear whether it is possible
to adapt the proof technique of [9] to our Toeplitz covariance structure.

1.4

Bounds over a class of smooth spectral densities

Let us shortly describe an application of our results studied in more detail in [6]. To a
Toeplitz covariance matrix Σ of the form (5) we associate its spectral density function
f (x) = fΣ (x) = σ0 + 2

p−1
X

σr cos rx,

r=1

x ∈ [−π, π].

(11)

The proof of our main result uses the fact that the spectral norm of Σ can be estimated by
the L∞ norm of f , kΣk ≤ kf k∞ := sup |f (x)|, see e.g. [12, Chapter 5.2].
x∈[−π,π]

As in [6] we introduce a class of Toeplitz covariance matrices related to a Lipschitz
condition on the spectral densities. For β = γ + α with γ ∈ N0 and α ∈ (0, 1], let
(
)
Fβ (L0 , L) =

(γ)

(γ)

Σ ≻ 0 : kΣk ≤ L0 , sup |fΣ (x + h) − fΣ (x)| ≤ Lhα

,

x∈[−π,π]

(γ)

where fΣ is the γ-th derivative of fΣ . Since the decay of Fourier coefficients is closely
connected to smoothness conditions, these two classes are contained in each other for certain
choices of parameters.
6

Choosing M = Mtap as the mask of the tapering estimator with parameter m, the spectral
function fMtap ·Σ equals fΣ ∗ Vm where ∗ denotes convolution and Vm is the so-called De la
Vallèe-Poussin kernel. Applying classical results from Fourier series, see e.g. [26, Chapter
3.13] yields kMtap · Σ − Σk ≤ kfΣ ∗ Vm − fΣ k∞ ≤ 4 inf q∈Tm kq − f k∞ . For Σ in Fβ (L0 , L) the
last term can further be estimated by 3Lm−β so that
kMtap · Σ − Σk ≤ 12Lm−β .

(12)

Under the assumption of Corollary 2 and assuming K 2 = ckΣk (as in the Gaussian case)
this leads together with (2) to
s
!
m log(p) m log(p)
E kMtap · Σ̃ − Σk ≤ CkΣk
+ 12Lm−β
+
pn
pn
Note that kΣk ≤ L0 due to Σ ∈ F(L0 , L). Choosing
$
1/(2β+1) %
np
L
m=
log(p)
L2β+2
0

(13)

and making the mild assumption m ≤ pn/ log(p), we obtain
E kMtap · Σ̃ − Σk ≤ CL



log(p)
np

β
 2β+1

.

(14)

Of course, a related probability estimate and an MSE estimate can be derived from (7). It
is shown in [6, Theorem 5] that this bound is optimal over the class Fβ (L0 , L). In particular,
the logarithmic factor log(p) in (14) cannot be removed. This means that the logarithmic
factor in our general bound (8) cannot be removed in general, either.
In a similar way [6], we can analyze the performance of the banding estimator over
Fβ (L0 , L). This leads to the estimate
s
!
m log(p) m log(p)
E kMband · Σ̃ − Σk ≤ CL0
+ 12L log(m)m−β .
+
pn
pn
Choosing
m=

$

np
2β+2 log(p)
L0
L

1/(2β+1)

log(p)1/β

leads to
4β+3

E kMband · Σ̃ − Σk ≤ CL

log(p) 4β+2
np

%

β
! 2β+1

.

Compared to the bound for the tapering estimator this is slightly worse.
The article [6] considers also a second class of Toeplitz covariance matrices, but for the
sake of brevity, we will not go into detail here.
7

1.5

Positive semidefinite estimator

It is natural to ask that a covariance estimator is positive semidefinite and some applications
will strictly require this. However, our masked estimator M · Σ̃n does not necessarily fulfill
this condition. In order to obtain a positive semidefinite Toeplitz estimator, we can apply
a procedure described in [6, Chapter 5], which is based on a circulant extension of our
original masked estimator. For the sake of completeness we present the construction here
and provide an approximation error of the true covariance matrix.
For an arbitrary (positive semidefinite) Toeplitz covariance matrix Σ ∈ Rp×p given by
(5) and corresponding spectral density function fΣ as in (11) we define a circulant matrix
Σcirc ∈ R(2p−1)×(2p−1) with entries
(
σ|s−t| ,
if |s − t| ≤ p − 1,
(Σcirc )st =
σ2p−1 − σ|s−t| , if p ≤ |s − t| ≤ 2p − 2.
The eigenvalue decomposition of Σcirc is given by
X
Σcirc =
λj uj ūTj
|j|≤p−1

with the eigenvectors
uj = √

T
1
1, e−2πij/(2p−1) , . . . , e−2πij(2p−2)/(2p−1) ,
2p − 1

|j| ≤ p − 1,

and the (non-negative) eigenvalues
λj =

p−1
X

2p−2
−2πijr/(2p−1)

σr e

+

=

σ2p−1−r e−2πijr/(2p−1)

r=p

r=0

p−1

X

X

−2πijr/(2p−1)

σr e

−1
X

+

r=0

r=−(p−1)
p−1

2πrj
= fΣ
σr cos
= σ0 + 2
2p − 1
r=1
X

σ−r e−2πijr/(2p−1)


2πj
2p − 1



,

|j| ≤ p − 1.

(15)

Let M · Σ̃n be our masked estimator with spectral density function fM ·Σ̃n , which may
possibly take negative values. Define f ∗ : [−π, π] → R as the non-negative part of fM ·Σ̃n ,
(
fM ·Σ̃n (x), if fM ·Σ̃n (x) ≥ 0,
f ∗ (x) =
0,
otherwise.
Set
Σ∗circ

=

X

|j|≤p−1

f

∗



8


2πj
uj ūTj .
2p − 1

Then Σ∗circ ∈ R(2p−1)×(2p−1) is circulant and positive semidefinite. As a new estimator Σ∗ we
take the restriction of Σ∗circ to its first p rows and p columns. It is clear that Σ∗ is Toeplitz
and positive semidefinite. But note that in the case of a sparse mask M, the estimator Σ∗
may in general fail to be sparse. Nevertheless, we have the following error bound.
Theorem 4. Let X1 , . . . , Xn be drawn from a distribution X ∈ Rp such that E X = 0,
Σ = E XX T is Toeplitz and X satisfies the convex concentration property with constant K.
Let M ∈ Rp×p be a Toeplitz mask with first row ω. Then the positive semidefinite estimator
Σ∗ obtained from M · Σ̃n by the procedure described above satisfies, for every t > 0,
!
!
r
t
kωk
t
1,∗
P kΣ∗ − Σk ≥ CK 2 kωk2,∗
+ 3kf − fM ·Σ k∞ ≤ Cpe−t ,
(16)
+
n
n
where f and fM ·Σ denote spectral density functions of Σ and M · Σ respectively. Moreover,
!
r
log(p)
log(p)
E kΣ∗ − Σk ≤ CK 2 kωk2,∗
+ 3kf − fM ·Σ k∞ ,
(17)
+ kωk1,∗
n
n
The term kf − fM ·Σ k∞ in (17) replaces the bias term in (2) and is in general an upper
bound for it. If the mask M is chosen in such a way that M · Σ is precisely Σ then the term
kf − fM ·Σ k∞ in the estimate above disappears.
In the situation of Toeplitz covariance matrices Σ from the class Fβ (L0 , L) from Section 1.4 we have for the tapering mask Mtap with parameter m, see also (12),
kf − fMtap ·Σ k∞ ≤ 12Lm−β .
Choosing m as in (13) and following the same steps leading to (14), we conclude that the
corresponding positive definite estimator Σ∗ satisfies
E kΣ∗ − Σk ≤ CL



log(p)
np

β
 2β+1

.

A corresponding tail estimate follows in the same way. This means that the original masked
estimator M · Σ̃n and the positive semidefinite estimator Σ∗ obey the same error estimates
on Fβ (L0 , L) (up to possibly constants).

Acknowledgements
Both authors acknowledge funding from the DFG through the project Compressive Covariance Sampling for Spectrum Sensing (CoCoSa). They thank Andreas Bollig and Arash
Behboodi for discussions on Toeplitz covariance estimation in the context of wireless communications.

9

2

Preliminaries

2.1

The convex concentration property

The Gaussian concentration inequality, see e.g. [14, 15], states that if f : Rp → R is a
Lipschitz function with Lipschitz constant kf kLip and X ∼ N(0, Σ), then
!
t2
P (|f (X) − E f (X)| ≥ t) ≤ 2 exp −
for all t ≥ 0.
(18)
2kΣkkf k2Lip
We are interested in distributions X ∈ Rp that behave similar to (18).
Definition 1 (Convex concentration property). Let X be a random vector in Rp . We
say that X has the convex concentration property (c.c.p.) with constant K if for every
1-Lipschitz convex function φ : Rp → R, we have E |φ(X)| < ∞ and for every t > 0,
P(|φ(X) − E φ(X)| ≥ t) ≤ 2 exp(−t2 /K 2 ).
The mean E φ(X) in (18) may be replaced by a median Mf after possibly adjusting the
constant K, see e.g. [2, Lemma 3.2].
This type of distributions is considered in [1, 2, 14, 24, 17]. We provide several examples
of distributions with possibly dependent entries satisfying the c.c.p.:
1. Clearly, a Gaussian random vector X ∼ N(0, Σ) satisfies the c.c.p. with K 2 = 2kΣk.
√
2. A random vector X that is uniformly distributed on the sphere pS p−1 satisfies the
c.c.p. with constant K = 2. This follows from [14, eq. (5.7)] combined with [14,
Theorem 5.3].
3. A random vector X ∈ Rp with a density proportional to e−u(x) , where the Hessian
satisfies D 2 u(x) ≥ γ Id for some c p
> 0 uniformly in x ∈ Rp , has the c.c.p. [14,
Proposition 2.18] with constant K = 2/γ. Such random vectors form an important
subclass of the logarithmically convex random vectors.
4. A random vector X = (X1 , . . . , Xp ) with independent components Xj taking values
in [−1, 1] satisfies the c.c.p. with absolute constant K = c [22]. (Of course, the Xj
taking values in some other bounded intervals works as well after possibly adjusting
the constant c.)
5. In generalization of the previous example, the c.c.p. also holds for certain random
vectors X = (X1 , . . . , Xp ) on [−1, 1]p with dependent entries. In [20] this is proven for
some classes of Markov chains and so-called Φ-mixing processes.
6. Let X ∈ Rp be a random vector with covariance matrix being the identity and that
satisfies the c.c.p. with constant K, for instance, a Rademacher vector, i.e., independent entries that take the value ±1 with equal probability (see Example 4). Now for
an arbitrary B ∈ Rq×p we define Y = BX ∈ Rq . Then Y has covariance matrix
10

ΣY = BB T and satisfies the c.c.p. Indeed, for a 1-Lipschitz and convex function
1
f : Rq → R, define φ : Rp → R as φ(X) = kBk
f (BX). Then φ is also 1-Lipschitz and
convex. Since X has the c.c.p., we have
E |f (Y )| = E |f (BX)| = kBk E |φ(X)| < ∞
and

P(|f (Y ) − E f (Y )| ≥ t) = P |φ(X) − E φ(X)| ≥

t
kBk



≤ 2 exp(−t2 /(KkBk)2 ),

which implies that Y satisfies the c.c.p. with constant KkΣY k1/2 . This example shows
in particular that any positive semidefinite matrix Σ may appear as covariance matrix
of a random vector satisfying the c.c.p. and not being Gaussian.
7. It follows from [18, Theorem 3.3] (a generalization of Talagrand’s convex distance inequality) that the c.c.p. holds for a random vector X = (X1 , . . . , Xp ) with possibly
dependent entries which satisfies a Dobrushin type condition. See [18] for details and
[21, Theorem 3] on how to deduce a concentration inequality from a convex distance
inequality. This examples applies in particular to random vectors generated via sampling from finite sets without replacement [18, Theorem 6.8].
8. Random vectors satisfying the logarithmic Sobolev inequality are c.c.p.: For some
positive measurable function f on Rp , the entropy is defined as
EntX (f ) = E[f (X) log(f (X))] − E[f (X)] log(E[f (X)]).
The random vector is said to satisfy a logarithmic Sobolev inequality if for all smooth
enough functions f on Rp it holds


EntX (f 2 ) ≤ K 2 E k∇f (X)k22 .

It follows from [14, Theorem 5.3] that X has the c.c.p. with constant K. Examples of
random vectors satisfying the logarithmic Sobolev inequality include Gaussian random
vectors X ∼ N(0, Σ) and more generally logarithmically concave random vectors as
in Example 3. above, the uniform distribution on the sphere [14, eq. (5.7)] and, more
generally, random vectors distributed according to the normalized Riemann measure
on a compact Riemannian manifold with Ricci curvature uniformly bounded from
below by a positive constant [14, eq. (5.5)].

The following generalization of the Hanson-Wright inequality for random vectors satisfying
the c.c.p. due to Adamczak [2] is crucial for the proof of Theorem 3.
Theorem 5. Let X ∈ Rp be random with E X = 0. If X satisfies the c.c.p. with constant
K, then for any A ∈ Rp×p and t > 0,



t
t2
1
.
,
P (|hAX, Xi − EhAX, Xi| ≥ t) ≤ 2 exp − min
C
2K 4 kAk2F K 2 kAk
11

2.2

Sub-gamma random variables

The proof of our main result uses the concept of sub-gamma random variables, see also
[5, Chapter 2.4]. A real-valued mean-zero random variable X is called sub-gamma with
variance factor ν and scale parameter c if, for all 0 < λ < 1/c,




λ2 ν
λ2 ν
E exp(λX) ≤ exp
and E exp(−λX) ≤ exp
(19)
2(1 − cλ)
2(1 − cλ)
The tail of a sub-gamma variable satisfies [5, Chapter 2.4]
√
√
P(|X| > 2νt + ct) ≤ 2 exp(−t).

(20)

Sub-gamma variables can be characterized via their moments [5, Theorem 2.3].
Theorem 6. If, for any integer q ≥ 1, a random variable X satisfies
E[X 2q ] ≤ q!Aq + (2q)!B 2q

(21)

then X is sub-gamma with variance factor ν = 4(A + B 2 ) and scale parameter c = 2B.
Conversely, if X is sub-gamma then (21) holds for some A and B.

3

Proof of main results

Proof of Theorem 3. As in [6] our results rely on the connection between the spectral norm
of the Toeplitz matrix and the L∞ norm of the corresponding spectral density function.
The spectral density function corresponding to a Toeplitz covariance matrix Σ defined
in (5) is given by
f (x) = fΣ (x) = σ0 + 2

p−1
X

σr cos rx =

r=1

p−1
X

r=−(p−1)

σ|r| cos rx,

x ∈ [−π, π].

It follows from [12, Chapter 5.2] that
kΣk ≤ kf k∞ := sup |f (x)| ≤ 2 max |f (xk )| ,
x∈[−π,π]

1≤k≤4p

with xk =

k − 2p
π,
4p

(22)

where the second inequality follows from the fact that f is a trigonometric polynomial of
order less than p together with Theorem 7.28 in [26, Chapter X].
Our masked estimator based on n observations X1 , . . . , Xn of X ∈ Rp is defined as


ω0 σ̃0
ω1 σ̃1 . . . ωp−1 σ̃p−1
..


.
ω0 σ̃0

 ω1 σ̃1
M · Σ̃n = 
,
.
.
..
..

ω1 σ̃1 
ωp−1 σ̃p−1 . . . ω1 σ̃1
ω0 σ̃0
12

with

n

p−r

1X 1 X
σ̃r =
Xij Xi(j+r) ,
n i=1 p − r j=1

r = 0, . . . , p − 1,

where Xij is the jth entry of the observation Xi . Then the corresponding spectral density
function is given by
fM ·Σ̃n (x) =

p−1
X

n

1X
ω|r| σ̃|r| cos rx =
n i=1

r=−(p−1)
p
n

p−1
X

r=−(p−1)

p

p−|r|
ω|r| X
Xij Xi(j+|r|) cos rx
p − |r| j=1
n

1 X X X ω|s−t|
1X
=
hM · V x Xi , Xi i,
Xis Xit cos(s − t)x =
n i=1 s=1 t=1 p − |s − t|
n i=1
where
x p
V x = [vst
]s,t=1 ,

x
x
vst
= v|s−t|
=

cos(s − t)x
,
p − |s − t|

(23)

x ∈ [−π, π].

Let Zik be the mean-zero random variable defined by
Zik = hM · V xk Xi , Xi i − EhM · V xk Xi , Xi i,

i = 1, . . . , n, k = 1, . . . , p.

Then (22) and (23) together with the notation above provide the following bound
!
n

1X k
t
P kfM ·Σ̃n − fM ·Σ k∞ ≥ t ≤ P max
Zi ≥
.
1≤k≤4p n
2
i=1

(24)

By the generalized Hanson-Wright inequality of Theorem 5, for each i = 1, . . . , n and k =
1, . . . , 4p,




t
t2
1
k
,
P Zi ≥ t ≤ 2 exp − min
,
C
2K 4 kM · V xk k2F K 2 kM · V xk k

which by integration implies that for every integer q ≥ 1,
q
2q
2q
E Zik ≤ 2q 2CK 4 kM · V xk k2F Γ(q) + 4q CK 2 kM · V xk k Γ(2q)
q
2q
≤ q! 4CK 4 kM · V xk k2F + (2q)! 2CK 2 kM · V xk k .

(25)

According to Theorem 6 it follows that Zik is a sub-gamma random variable with variance
factor

ν = 16K 4 CkM · V xk k2F + C 2 kM · V xk k2
and scale parameter

c = 2CK 2 kM · V xk k.

Hence, by (19) and independence, for all 0 < λ < 1/c,
!

n
n
Y
X

k
k
E exp λZi ≤ exp
Zi =
E exp λ
i=1

i=1

13


λ2 nν
,
2(1 − cλ)

(26)

and similarly for the

Zik

replaced by

−Zik .

This means that

n
X

Zik is a sub-gamma random

i=1

variable with variance factor νn and scale parameter c. By (20) this implies that for every
t > 0,
!
n
X
√
P
Zik > 2νnt + ct ≤ 2e−t .
i=1

Taking into account that the spectral norm of a matrix is bounded from above by its Frobenius norm we obtain
!
r
n
1X k
t
CK 2 kM · V xk kt
2
xk
P
Zi ≥ C1 K kM · V kF
≤ 2e−t for all t > 0,
+
n i=1
n
n
√
where C1 = 4 2C + 2C 2 . A direct calculation of kM · V xk kF yields
kM · V xk kF ≤

p−1
X
ωℓ2
2
p−ℓ
ℓ=0

!1/2

= 2kωk2,∗.

By the Gershgorin disc theorem [13, Chapter 6], kM · V xk k is bounded by
kM · V

xk

p−1
X
ωℓ
= 2kωk1,∗.
k≤2
p
−
ℓ
ℓ=0

Applying the union bound to (24) results in
P kfM ·Σ̃n − fM ·Σ k∞ ≥ C2 K 2

kωk2,∗

r

t
kωk1,∗t
+
n
n

!!

≤ 8pe−t

(27)

for some C2 only depending on C. Due to (22) the error of approximating M · Σ by M · Σ̃n
is bounded by
!!
r
kωk
t
t
1,∗
≤ 8pe−t .
P kM · Σ̃n − M · Σk ≥ C2 K 2 kωk2,∗
+
n
n
Integration yields
E kfM ·Σ̃n − fM ·Σ k∞ ≤ C3 K 2
E kM · Σ̃n − M · Σk ≤ C3 K 2

!
log(p)
log(p)
kωk2,∗
,
+ kωk1,∗
n
n
!
r
log(p)
log(p)
kωk2,∗
.
+ kωk1,∗
n
n
r

This concludes the proof.
14

(28)

Proof of Corollary 2. The Gaussian distribution satisfies the c.c.p with the constant K 2 =
2kΣk. Since the entries of either the banding or tapering mask M are bounded from above
by 1 and m ≤ p2 , we obtain
kωk2,∗ ≤
kωk1,∗ ≤ 2

2

m
X
ℓ=0

m
X
ℓ=0

1
p−ℓ

!1/2

≤



2(m + 1)
p−m

1/2

≤



4(m + 1)
p

1/2

,

2(m + 1)
4(m + 1)
1
≤
≤
.
p−ℓ
p−m
p

Theorem 3 yields the claim.
Proof of Theorem 4. By the triangle inequality,
kΣ∗ − Σk ≤ kΣ∗ − M · Σk + kM · Σ − Σk.

(29)

We bound the first term by expanding both matrices to a circulant matrix and taking into
account expression (15) for its eigenvalues,




2πj
2πj
∗
∗
∗
− fM ·Σ
kΣ − M · Σk ≤ kΣcirc − (M · Σ)circ k = max f
|j|≤p−1
2p − 1
2p − 1
∗
∗
≤ kf − fM ·Σ k∞ ≤ kf − f k∞ + kf − fM ·Σ k∞ .
(30)
Since f is non-negative and f ∗ is the positive part of fM ·Σ̃n ,
kf ∗ − f k∞ ≤ kfM ·Σ̃n − f k∞ ≤ kfM ·Σ̃n − fM ·Σ k∞ + kfM ·Σ − f k∞ .

(31)

Estimating the second term of (29) by the L∞ norm of the corresponding spectral density
function together with (30) and (31) leads to
kΣ∗ − Σk ≤ kfM ·Σ̃n − fM ·Σ k∞ + 3kf − fM ·Σ k∞ .
Taking expectations and applying estimate (28) shows the claimed estimate for the expectation of the approximation error, while a combination with (27) proves the probability
bound.

References
[1] R. Adamczak. Logarithmic Sobolev inequalities and concentration of measure for convex
functions and polynomial chaoses. Bull. Pol. Acad. Sci. Math., 53(2):221–238, 2005.
[2] R. Adamczak. A note on the Hanson-Wright inequality for random vectors with dependencies. Electron. Commun. Probab., 20(72):1–13, 2015.
[3] P. Bickel and E. Levina.
36(6):2577–2604, 2008.

Covariance regularization by thresholding.

15

Ann. Stat.,

[4] P. Bickel and E. Levina. Regularized estimation of large covariance matrices. Ann.
Stat., 36(1):199–227, 2008.
[5] S. Boucheron, G. Lugosi, and P. Massart. Concentration inequalities. A nonasymptotic
theory of independence. Oxford University Press, Oxford, 2013.
[6] T. Cai, Z. Ren, and H. Zhou. Optimal rates of convergence for estimating Toeplitz
covariance matrices. Probab. Theory Relat. Fields, 156(1-2):101–143, 2013.
[7] T. Cai and H. Zhou. Minimax estimation of large covariance matrices under ℓ1 -norm.
Stat. Sin., 22(4):1319–1349, 2012.
[8] S. Chaudhari, V. Koivunen, and H. V. Poor. Autocorrelation-based decentralized sequential detection of OFDM signals in cognitive radios. IEEE Trans. Signal Process.,
57(7):2690–2700, 2009.
[9] R. Chen, A. Gittens, and J. Tropp. The masked sample covariance estimator: an
analysis using matrix concentration inequalities. Inf. Inference, 1(1):2–20, 2012.
[10] N. El Karoui. Operator norm consistent estimation of large-dimensional sparse covariance matrices. Ann. Stat., 36(6):2717–2756, 2008.
[11] R. Furrer and T. Bengtsson. Estimation of high-dimensional prior and posterior covariance matrices in Kalman filter variants. J. Multivariate Anal., 98(2):227–255, 2007.
[12] U. Grenander and G. Szegö. Toeplitz forms and their applications. California Monographs in Mathematical Sciences. University of California Press, Berkeley-Los Angeles,
1958.
[13] R. Horn and C. Johnson. Matrix analysis. Cambridge University Press, Cambridge,
2013.
[14] M. Ledoux. The concentration of measure phenomenon, volume 89 of Mathematical
Surveys and Monographs. American Mathematical Society, Providence, RI, 2001.
[15] M. Ledoux and M. Talagrand. Probability in Banach spaces. Isoperimetry and processes.
Springer-Verlag, Berlin, 2011.
[16] E. Levina and R. Vershynin. Partial estimation of covariance matrices. Probab. Theory
Relat. Fields, 153(3-4):405–419, 2012.
[17] M. Meckes and S. Szarek. Concentration for noncommutative polynomials in random
matrices. Proc. Amer. Math. Soc., 140(5):1803–1813, 2012.
[18] D. Paulin. The convex distance inequality for dependent random variables, with applications to the stochastic travelling salesman and other problems. Electron. J. Probab.,
19(0):1–34, 2014.

16

[19] H. Rauhut and R. Ward. Interpolation via weighted ℓ1 -minimization. Appl. Computat.
Harmonic Anal., 40(2):321–351, 2016.
[20] P. Samson. Concentration of measure inequalities for Markov chains and Φ-mixing
processes. Ann. Prob., 28(1):416–461, 2000.
[21] M. Talagrand. An isoperimetric theorem on the cube and the Kintchine-Kahane inequalities. Proc. Am. Math. Soc., 104(3):905–909, 1988.
[22] M. Talagrand. Concentration of measure and isoperimetric inequalities in product
spaces. Inst. Hautes Études Sci. Publ. Math., (81):73–205, 1995.
[23] R. Vershynin. Introduction to the non-asymptotic analysis of random matrices. In
Compressed sensing, Theory and Applications, pages 210–268. Cambridge Univ. Press,
Cambridge, 2012.
[24] V. Vu and K. Wang. Random weighted projections, random quadratic forms and
random eigenvectors. Random Struct. Algor., 47(4):792–821, 2015.
[25] Y. Zeng and Y. C. Liang. Covariance based signal detections for cognitive radio. In 2007
2nd IEEE International Symposium on New Frontiers in Dynamic Spectrum Access
Networks, pages 202–207, April 2007.
[26] A. Zygmund. Trigonometric series. Cambridge Mathematical Library. Cambridge University Press, Cambridge, 2002.

17

