1

On the Restricted Isometry of the Columnwise
Khatri-Rao Product
Saurabh Khanna, Student Member, IEEE and Chandra R. Murthy, Senior Member, IEEE

arXiv:1709.05789v2 [] 10 Oct 2017

Dept. of ECE, Indian Institute of Science, Bangalore, India
{saurabh, cmurthy}@iisc.ac.in

Abstract—The columnwise Khatri-Rao product of two matrices
is an important matrix type, reprising its role as a structured
sensing matrix in many fundamental linear inverse problems.
Robust signal recovery in such inverse problems is often contingent on proving the restricted isometry property (RIP) of a
certain system matrix expressible as a Khatri-Rao product of
two matrices. In this work, we analyze the RIP of a generic
columnwise Khatri-Rao product by deriving two upper bounds
for its kth order Restricted Isometry Constant (k-RIC) for
different values of k. The first RIC bound is computed in terms
of the individual RICs of the input matrices participating in the
Khatri-Rao product. The second RIC bound is probabilistic in
nature, and is specified in terms of the input matrix dimensions.
We show that the Khatri-Rao product of a pair of m × n
sized random matrices comprising independent and identically
distributed subgaussian entries satisfies k-RIP
with arbitrarily
√
high probability, provided m exceeds O( k log3/2 n). This is
a substantially milder condition compared to O(k log n) rows
needed to guarantee k-RIP of the input subgaussian random
matrices participating in the Khatri-Rao product. Our results
confirm that the Khatri-Rao product exhibits stronger restricted
isometry compared to its constituent matrices for the same
RIP order. The proposed RIC bounds are potentially useful in
obtaining improved performance guarantees in several sparse
signal recovery and tensor decomposition problems.

examples include compressive sensing [4], [5], covariance
matrix estimation [6], [7], direction of arrival estimation [8]
and tensor decomposition [9]. In each of these examples,
the KR product A
B, for certain m × n sized system
matrices A and B, plays the role of the sensing matrix used to
generate linear measurements y of an unknown signal vector
x according to
y = (A B) x + w,
(2)

Index Terms—Khatri-Rao product, Kronecker product, compressive sensing, Restricted isometry property, covariance matrix
estimation, multiple measurement vectors, PARAFAC, CANDECOMP, tensor decomposition, direction of arrival estimation.

The smallest constant δk (Φ) for which (3) holds for all ksparse z is called the k th order restricted isometry constant or
the k-RIC of Φ. Matrices with small k-RICs are good encoders
for storing/sketching high dimensional vectors with k or fewer
nonzero entries [14]. For example, δk (A B) < 0.307 is a
sufficient condition for a unique k-sparse solution to (2) in the
noiseless case, and its perfect recovery via the `1 minimization
technique [15]. As pointed out earlier, in many structured
signal recovery problems, the main sensing matrix can be
expressed as a columnwise Khatri-Rao product between two
matrices. Thus, from a practitioner’s viewpoint, it is pertinent
to study the restricted isometry property of a columnwise
Khatri-Rao product matrix, which is the focus of this work.

I. I NTRODUCTION
The Khatri-Rao product, denoted by the symbol , is
a columnwise Kronecker product, which was originally introduced by Khatri and Rao in [1]. For any two matrices
A = [a1 , a2 . . . , ap ] and B = [b1 , b2 . . . , bp ] of sizes m × p
and n × p, respectively, the columnwise Khatri-Rao product
A B is a matrix of dimension mn × p defined as
A

B = [a1 ⊗ b1 a2 ⊗ b2

...

ap ⊗ bp ] ,

(1)

where a ⊗ b denotes the Kronecker product [2] between
vectors a and b. That is, each column of A
B is the
Kronecker product between the respective columns of the
two input matrices A and B. In this article, we shall refer
to the columnwise Khatri-Rao product as simply the KhatriRao product or the KR product. Since the Kronecker product
A⊗B comprises all pairwise Kronecker product combinations
of the columns of the input matrices, it can be shown that
A B = (A ⊗ B)J, where J is a p2 × p selection matrix
2
with columns as a subset of the standard basis in Rp [3].
Khatri-Rao product matrices are encountered in several
linear inverse problems of fundamental importance. Recent

where w represents the additive measurement noise. It is now
well established in the sparse signal recovery literature [10]–
[12] that, if the signal of interest, x, is a k-sparse1 vector in
Rn , it can be stably recovered from its noisy underdetermined
2
linear observations y ∈ Rm (m2 < n) in a computationally
efficient manner provided that the sensing matrix (here, A B)
satisfies the restricted isometry property defined next.
A matrix Φ ∈ Rm×n is said to satisfy the Restricted
Isometry Property (RIP) [13] of order k, if there exists a
constant δk (Φ) ∈ (0, 1), such that for all k-sparse vectors
z ∈ Rn ,
(1 − δk (Φ))||z||22 ≤ ||Φz||22 ≤ (1 + δk (Φ))||z||22 .

(3)

A. Applications involving Khatri-Rao matrices
We briefly describe some examples where it is required to
show the restricted isometry property of a KR product matrix.
1) Support recovery of joint sparse vectors from underdetermined linear measurements: Suppose x1 , x2 , . . . , xL are
unknown joint sparse signals in Rn with a common k-sized
support denoted by an index set S. A canonical problem in
multi-sensor signal processing is concerned with the recovery
of the common support S of the unknown signals from their
1A

vector is said to be k-sparse if at most k of its entries are nonzero.

2

noisy underdetermined linear measurements y1 , y2 , . . . , yL ∈
Rm generated according to
yj = Axj + wj ,

1 ≤ j ≤ L,

(4)

m×n

where A ∈ R
(m < n) is a known measurement matrix,
and wj ∈ Rn models the noise in the measurements. This
problem arises in many practical applications such as MIMO
channel estimation, cooperative wideband spectrum sensing in
cognitive radio networks, target localization, and direction of
arrival estimation. In [16], the support set S is recovered as
the support of γ̂, the solution to the Co-LASSO problem:
Co-LASSO: min vec(R̂yy ) − (A
γ0

2

A)γ

2

+λ ||γ||1 , (5)

PL
where R̂yy , L1 j=1 yj yjT . From compressive sensing
theory [11], the RIP of A A (also called the self Khatri-Rao
product of A) determines the stability of the sparse solution in
the Co-LASSO problem. In M-SBL [17], a different support
recovery algorithm, A A satisfying 2k-RIP can guarantee
exact recovery of S from multiple measurements [18].
2) Vandermonde decomposition of Toeplitz matrices:
According to a classical result by Carathéodory and Fejér [19],
any n×n positive semidefinite Toeplitz matrix T of rank r < n
admits the following decomposition
T = APAT ,

(6)

where P is an n × n positive semidefinite diagonal matrix
with an r-sparse diagonal, and A is an n × n Vandermonde
matrix with uniformly sampled complex sinusoids of different frequencies as its columns. This Toeplitz decomposition
underpins subspace based spectrum estimation methods such
as MUltiple SIgnal Classification (MuSiC) and EStimation
of Parameters by Rotationally Invariant Techniques (ESPRIT)
[20], [21]. By replacing T with a data covariance matrix,
the r-sparse support of diag(P) in (6) corresponds to the
r-dimensional signal subspace of the data. Estimation of
p , diag(P) is tantamount to finding an r-sparse solution
to the vectorized form of (6), i.e., vec(T) = (A A)p. Here
again, the recovery of a unique r-sparse solution for p can be
guaranteed if A A satisfies the RIP of order 2r.
3) PARAFAC model for low-rank three-way arrays:
Consider an I × J × K tensor X of rank r. We can
express
PrX as the sum of r rank-one three way arrays as
X = i=1 ai ◦ bi ◦ ci , where ai , bi , ci are loading vectors of
dimension I, J, K, respectively, and ◦ denotes the vector outer
product. The tensor X itself can be arranged into a matrix
as X = [vec(X1 ), vec(X2 ), . . . , vec(XK )]. In the parallel
factor analysis (PARAFAC) model [22], the matrix X can be
approximated as
X ≈ (A B)CT ,
(7)
where A, B and C are the loading matrices with columns
as the loading vectors ai , bi and ci , respectively. In many
problems such as direction of arrival estimation using a 2Dantenna array, the loading matrix C turns out to be rowsparse matrix [23]. In such cases, the uniqueness of the
PARAFAC model shown in (7) depends on the restricted
isometry property of the Khatri-Rao product A B.

Finding the exact kth order RIC of any matrix entails
searching for the smallest and largest eigenvalues among all
possible k-column submatrices of the matrix, which is, in
general, an NP hard task [24]. In this work, we follow an
alternative approach to analyzing the RIP of a KR product
matrix. We seek to derive tight upper bounds for its RICs.
B. Related Work
Perhaps the most straightforward way to analyze the RICs
of the KR product matrix is to use the eigenvalue interlacing
theorem [25], which relates the singular values of any kcolumn submatrix of the KR product to the singular values of
the Kronecker product. This is possible because any k columns
of the KR product can together be interpreted as a submatrix
of the Kronecker product. However, barring the maximum and
minimum singular values of the Kronecker product, there is
no explicit characterization of its non-extremal singular values
available, that can be used to obtain tight bounds the k-RIC of
the KR product. Bounding the RIC using the extreme singular
values of the Kronecker product matrix turns out to be too
loose to be useful. In this context, we note that an upper bound
for the k-RIC of the Kronecker product matrix is derived in
terms of the k-RICs of the input matrices in [4], [26]. However,
the k-RIC of the KR product matrix is yet to be analyzed.
Recently, [27], [28] gave probabilistic lower bounds for
the minimum singular value of the columnwise KR product
between two or more matrices. These bounds are limited to
randomly constructed input matrices, and are polynomial in
the matrix size. In [29], it is shown that for any two matrices
A and B, the Kruskal-rank2 of A B has a lower bound in
terms of K-rank(A) and K-rank(B). In fact, Krank(A B)
is at least as high as max (K-rank(A), K-rank(B)), thereby
suggesting that A B satisfies a stronger restricted isometry
property than both A and B. The RIC bounds presented in
this work ratify this fact.
A closely related yet weaker notion of restricted isometry
constant is the τ -robust K-rank, denoted by K-rankτ . For a
given matrix Φ, the K-rankτ (Φ) is defined as the largest k for
which every n × k submatrix of Φ has its smallest singular
value larger than 1/τ . In [27], it is shown that the τ -robust Krank is super-additive, implying that the K-rankτ of the KhatriRao product is strictly larger than individual K-rankτ s of the
input matrices. We show a similar result for the restricted
isometry constants of the KR product matrix.
Our work is perhaps closest to [7], which provides a
polynomially tight probabilistic upper bound for the k-RIC
(defined using `1 -norm in (3)) of the Khatri-Rao product
A B, when the input matrices A and B are the adjacency
matrices of two independent uniformly random δ-left regular
bipartite graphs. This work instead assumes A and B to be
random matrices with independent subgaussian elements.
C. Our Contributions
We derive two upper bounds on the k-RIC of the columnwise KR product of two m × n sized matrices A and B. The
2 The Kruskal rank of any matrix A is the largest integer r such that any
r columns of A are linearly independent.

3

bounds are listed below.
1) A deterministic upper bound for the k-RIC of A B in
terms of the k-RICs of the input matrices A and B. The
bound is valid for k ≤ m, and for input matrices with
unit `2 -norm columns.
2a) A probabilistic upper bound for the k-RIC of A B
in terms of k and the input matrix dimensions (m, n),
for A, B as random matrices with i.i.d. subgaussian
elements. The probabilistic bound is polynomially tight
with respect to the input matrix dimension n. The bound
is valid for k ≤ n.
2b) A probabilistic upper bound for the k-RIC of the self
KR product A A in terms of m, n, and k, for A as a
random matrix with i.i.d. subgaussian elements. Although
the RIC bounds for the self KR product and the general
KR product with distinct input matrices are of similar
form, the derivation of former RIC bound is slightly more
intricate as it involves showing sharp concentration for
functions of dependent random variables.
A key idea in the RIC analysis is to use the fact (stated
formally as Proposition 12) that for any two matrices A and
B, the Gram matrix of their KR product (A B)T (A B) can
be interpreted as the Hadamard product (element wise multiplication) between AT A and BT B. The Hadamard product
form is more analytically tractable than columnwise Kronecker
product form of the KR matrix.
Lately, in several machine learning problems, the necessary
and sufficient conditions for successful signal recovery have
been reported in terms of the RICs of a certain Khatri-Rao
product matrix serving as a pseudo sensing matrix [8], [16].
In light of this, our proposed RIC bounds are quite timely,
and pave the way towards obtaining order-wise tight sample
complexity bounds in several fundamental learning problems.
The rest of this article is organized as follows. In Secs. II
and III, we present our main results: deterministic and probabilistic RIC bounds, respectively, for a generic columnwise
KR product matrix. Sec. III also discusses about the RIP of the
self Khatri-Rao product of a matrix with itself, an important
matrix type encountered in the sparse diagonal covariance
matrix estimation problem. In Secs. IV and VI, we provide
some background concepts needed in proving the proposed
RIC bounds. Secs. V and VII provide the detailed proofs of
the deterministic and probabilistic RIC bounds, respectively.
Final conclusions are presented in Sec. VIII.
Notation: In this work, bold lowercase letters are used for
representing both scalar random variables as well as vectors.
Bold uppercase letters are reserved for matrices. The `2 -norm
of vector x is denoted by ||x||2 . For an m × n matrix A,
||Ax||
||A|| denotes its operator norm, ||A|| = supx∈Rn ,x6=0 ||x|| 2 .
2
The Hilbert-Schmidt
(or Frobenius) norm of A is defined
Pm P
n
2
as ||A||HS =
i=1
j=1 |Ai,j | . The symbol [n] denotes
the index set {1, 2, . . . , n}. For any index set S ⊆ [n],
AS denotes the submatrix compromising the columns of A
indexed by S. The matrices A ⊗ B, A ◦ B and A B denote
the Kronecker product, Hadamard product and columnwise
Khatri-Rao product of A and B, respectively. A ≤ B implies
that B − A is a positive semidefinite matrix. AT , AH , A−1 ,

and A† denote the transpose, conjugate-transpose, inverse and
generalized matrix inverse operations, respectively.
II. D ETERMINISTIC k-RIC B OUND
In this section, we present our first upper bound on the kRIC of a generic columnwise KR product A B, for any two
similar sized matrices A and B with normalized columns. The
bound is given in terms of the k-RICs of A and B.
Theorem 1. Let A and B be m × n sized real-valued
matrices with unit `2 -norm columns and satisfying the k th
order restricted isometry property with constants δkA and
δkB , respectively. Then, their columnwise Khatri-Rao product
A B satisfies the restricted isometry
property with k-RIC at

most δ 2 , where δ , max δkA , δkB , i.e.,
(1 − δ 2 )||z||22 ≤ ||(A

B)z||22 ≤ (1 + δ 2 )||z||22

(8)

n

holds for all k-sparse vectors z ∈ R .
Proof. The proof is provided in Section V.
Remark 1: The RIC bound for A B in Theorem 1 is
relevant only when δk (A) and δk (B) lie in (0, 1), which
is true only for k ≤ m. In other words, the above k-RIC
characterization for A B requires the input matrices A and
B to be k-RIP compliant.
Remark 2: Since the input matrices A and B satisfy kRIP with δk (A), δk (B) ∈ (0, 1), it follows from Theorem 1
that δk (A B) is strictly smaller than max (δk (A), δk (B)).
If B = A, the special case of self Khatri-Rao product A A
arises, for which
δk (A

A) < δk2 (A).

(9)

Above implies that the self Khatri-Rao product A A is a better restricted isometry compared to A itself. This observation
is in alignment with the expanding Kruskal rank and shrinking
mutual coherence of the self Khatri-Rao product reported in
[16]. In fact, for k = 2, the 2-RIC bound (9) exactly matches
the mutual coherence bound shown in [16].
For k ∈ (m, m2 ], using ( [30], Theorem 1), one can
√
show that δk (A
B) ≤
k + 1 δ√k , where δ√k =

max δ√k (A), δ√k (B) . This bound, however, loses its tightness and quickly becomes unattractive for larger values of k.
Finding a tighter k-RIC upper bound for the k > m case
remains an open problem.
To gauge the tightness of the proposed k-RIC bound for
A
B, we present its simulation-based quantification for
the case when the input matrices A and B are random
Gaussian matrices with i.i.d. N (0, 1/m) entries. Fig. 1 plots
δk (A), δk (B), δk (A B) and the upper bound δk (A B) =
2
(max (δk (A), δk (B))) for a range of input matrix dimension
m. The aspect ratio m/n of the input matrices is fixed to
0.5.3 For computational tractability, we restrict our analysis
to the cases k = 2 and 3. The RICs: δk (A), δk (B) and
3 While the m×n matrices A and B may represent highly underdetermined
linear systems (when m  n), their m2 ×n sized Khatri-Rao product A B
can become an overdetermined system. In fact, many covariance matching
based sparse support recovery algorithms [16], [17], [31] exploit this fact to
offer significantly better support reconstruction performance.

4

The minimum such K1 is called the subgaussian or ψ2 norm
of the random variable x, i.e.,

1
δ2A
δ2B
δ2A⊙B

0.8

p

Bound for δ2A⊙Bin Theorem-1

(11)

p≥1

Given a pair of random input matrices with i.i.d. subgaussian entries, Theorem 2 presents a new upper bound on the
k-RIC of their columnwise KR product.

δ2

0.6

0.4

0.2

0
100

1

||x||ψ2 = sup p−1/2 (E |x| ) p .

300

500

700

900

n
1.2
1

Theorem 2. Suppose A and B are m × n random matrices
with real i.i.d. subgaussian entries, such that EAij = 0 and
EA2ij = 1, and ||Aij ||ψ2 ≤ K, and similarly for B. Let Ko ,
max (K, 1). Then, the k th order restricted isometry constant
of √Am √Bm , denoted by δk , satisfies δk ≤ δ with probability
at least 1 − 8en−2(c2 γ−1) for all γ > 1/c2 , and c2 a universal
positive constant, provided that
!
√
16 2πγ 3/2 Ko2 √
3/2
k (log n) .
m≥
δ

δ3

0.8
0.6
0.4
0.2
0
50

100

150

200

250

300

n
Fig. 1: Variation of k-RICs of A, B, A B and the proposed upper bound
with increasing input matrix dimensions. The top and the bottom plots are
for k = 2 and 3, respectively. Each data point is averaged over 10 trials.

δk (A B) are computed by exhaustively searching for the
worst conditioned submatrix comprising k columns of A, B
and A B, respectively. From Fig. 1, we observe that the
proposed k-RIC upper bound becomes tighter as the input
matrices grow in size.
III. P ROBABILISTIC k-RIC B OUND
The deterministic RIC bound for the columnwise KR product discussed in the previous section is only applicable when
k ≤ m. It also fails to explain the empirical observation that
the KR product A B often satisfies k-RIP in spite of the
input matrices A and B failing to do so. These concerns are
addressed by our second RIC bound for the columnwise KR
product. This second RIC bound is probabilistic in nature and
is applicable to the KR product of random input matrices
with i.i.d. subgaussian entries. Below, we define a subgaussian
random variable and state some of its properties.
Definition 1. (Subgaussian Random Variable): A random variable x is called subgaussian, if its tail probability is dominated
by that of a Gaussian random variable. In other words, there
2
2
exists a constant K > 0 such that P(|x| ≥ t) ≤ e−t /K .
Gaussian, Bernoulli and all bounded random variables are
subgaussian random variables. For a subgaussian random
variable, its pth order moment grows only as fast as O(pp/2 )
[32]. In other words, there exists K1 > 0 such that
√
p 1
(E |x| ) p ≤ K1 p, p ≥ 1.
(10)

Proof. The proof is provided in Section VII.
√
The normalization constant m used while computing
√B
the KR product √Am
ensures that the columns of
m
A
B
√
√
the input matrices m , m have unit average energy, i.e.
√
√
E ||ai / m||2 = E ||bi / m||2 = 1 for 1 ≤ i ≤ n. Column
normalization is a key assumption towards correct modelling
of the isotropic, norm-preserving nature of the effective sens1
ing matrix m
(A B), an attribute found in most sensing
matrices employed in practice.
Theorem 2 implies that
!
√


3/2
√
A
B
k (log n)
3/2 2
√
δk √
≤ 16 2πγ Ko
m
m
m
(12)
with probability exceeding 1 − 8en−2(c2 γ−1) . Thus, the above
k-RIC bound decreases as m increases, which is intuitively
appealing. Interestingly, for fixed k and n, the above k√B decays as O( 1 ). This is
RIC upper bound for √Am
m
m
a significant improvement over the O( √1m ) decay rate [11]
already known for the individual k-RICs of the input subgaussian matrices √Am and √Bm . Thus, for any m, the Khatri√B exhibits stronger restricted isometry
Rao product √Am
m
property, with significantly smaller k-RICs in comparison to
the k-RICs for the input matrices.
In some applications, the effective sensing matrix can be
1
(A A) of a
expressed as the self-Khatri Rao product m
A
certain column normalized system matrix √m with itself [16].
In Theorem 3 below, we present the k-RIC bound for the
special case of self-Khatri-Rao product matrices.
Theorem 3. Let A be an m × n random matrix with real
i.i.d. subgaussian entries, such that EAij = 0 and EA2ij = 1,
and ||Aij ||ψ2 ≤ K. Then, the k th order restricted isometry
constant of the column normalized self Khatri-Rao product
1
A) satisfies δk ≤ δ with probability at least 1 −
m (A
4en−2(c2 γ−1) for any γ ≥ 1/c2 , provided
!
√
16 2πγ 3/2 Ko2 √
3/2
m≥
k (log n) .
δ

5

Here, Ko , max (K, 1) and c2 > 0 is a universal constant.
Proof. A proof sketch is provided in Appendix F.
Theorem 3 implies that


√
A
A
√
≤ 16 2πγ 3/2 Ko2
δk √
m
m

√

3/2

k (log n)
m

!

(13)
with probability exceeding 1−4en
. The above k-RIC
bound for the self Khatri-Rao product scales with m, n, and
k in a similar fashion as the asymmetric Khatri-Rao product.
Remark 3: From [11], for an mq× n matrix A with i.i.d.
2Ck log(eN/k)
with high
subgaussian entries, δk ( √Am ) ≤
m
probability. Now, even though the columns of A do not exactly
have unit norm, directly using this in Theorem 1 for the sake of
2Ck log(eN/k)
√A ) ≤
, when
comparison results in δk ( √Am
m
m
k ≤ m. Our probabilistic bound in (13) is therefore tighter
than the deterministic
bound in Theorem 1 by a multiplicative
√
factor of O( k). Note that, the deterministic bound is valid
for any pair of input matrices with normalized columns, while
the probabilistic bound holds when the input matrices have
i.i.d. subgaussian entries.
Remark 4: In covariance matching based signal support
recovery algorithms like Co-LASSO [16] and M-SBL [17],
given a system matrix √Am , δ2k ( √Am √Am ) ≤ 1 is one of the
sufficient conditions for exact recovery of the true k-sparse
support of the unknown signal of interest [18]. This sufficiency
condition is met with arbitrarily high probability according
to Theorem
√ 3, when the
 subgaussian matrix A has at least
m = O
k log3/2 n rows. This is a significantly milder
condition when compared with O(k log n) rows required for
exact k-sparse support recovery by conventional compressive
sensing algorithms such as SOMP [33]. In fact, to the best
of our knowledge, our k-RIC bound for the self Khatri-Rao
product provides the first ever theoretical confirmation for
the empirically observed performance of covariance matching
based sparse support recovery algorithms, i.e.,
√ the number of
measurements m need to scale as only O( k) rather than
O(k) in the case of conventional support recovery algorithms.
−2(c2 γ−1)

IV. P RELIMINARIES FOR D ETERMINISTIC k-RIC B OUND
In this section, we present some preliminary concepts and
results which are necessary for the derivation of the deterministic k-RIC bound in Theorem 1. For the sake of brevity, we
provide proofs only for claims that have not been explicitly
shown in their cited sources.
A. Properties of the Kronecker and Hadamard product
For any two matrices A and B of dimensions m × n and
p × q, the kronecker product A ⊗ B is the mp × nq matrix


a11 B a12 B · · · a1n B
 a21 B a22 B · · · a2n B 


A⊗B= .
(14)
..
..  .
.
.
.
 .
.
.
. 
am1 B am2 B · · ·

amn B

The following Proposition relates the spectral properties of
the Kronecker product and its constituent matrices.

Proposition 4 (7.1.10 in [2]). Let A ∈ Rn×n and B ∈ Rp×p
admit eigenvalue decompositions UA ΛA UTA and UB ΛB UTB ,
respectively. Then,
(UA ⊗ UB )(ΛA ⊗ ΛB )(UA ⊗ UB )T
yields the eigenvalue decomposition for A ⊗ B.
For any two matrices of matching dimensions, say m × n,
their Hadamard product A ◦ B is obtained by elementwise
multiplication of the entries of the input matrices, i.e.,
[A ◦ B]i,j = aij bij

for i ∈ [m], j ∈ [n].

(15)

The Hadamard product A ◦ B is a principal submatrix of the
Kronecker product A ⊗ B [3], [34]. For n × n sized square
matrices A and B, one can write,
A ◦ B = JT (A ⊗ B)J,

(16)

where J is an n2 ×n sized selection matrix constructed entirely
from 0’s and 1’s which satisfies JT J = In .
In Proposition 5, we present an upper bound on the spectral
radius of a generic Hadamard product.
Proposition 5. For every A, B ∈ Rm×n , we have
σmax (A ◦ B) ≤ rmax (A)cmax (B)

(17)

where σmax (·), rmax (·) and cmax (·) are the largest singular
value, the largest row norm and the largest column norm of
the input matrix, respectively.
Proof. See Theorem 5.5.3 in [35].
We now state an important result about the Hadamard
product of two positive semidefinite matrices.
Proposition 6 (Mond and Pec̆arić [36]). Let A and B be
positive semidefinite n × n Hermitian matrices and let r and
s be two nonzero integers such that s > r. Then,
1/s

(As ◦ Bs )

1/r

≥ (Ar ◦ Br )

.

(18)

In Propositions 7 and 8, we state some spectral properties of
correlation matrices and their Hadamard products. Correlation
matrices are symmetric positive semidefinite matrices with
diagonal entries equal to one. Later on, we will exploit the
fact that the singular values of the columnwise KR product
are related to the singular values of the Hadamard product of
certain correlation matrices.
Proposition 7. If A is an n×n correlation matrix, then A1/2 ◦
A1/2 is a doubly stochastic matrix.
Proof. See Appendix A.
Proposition 8 (Werner [37]). For any correlation matrices A
and B of the same size, we have A1/2 ◦ B1/2 ≤ I, where
A1/2 and B1/2 are the positive square roots of A and B,
respectively.
Proof. Since A is a correlation matrix, from Proposition 7,
it follows that A1/2 ◦ A1/2 is doubly stochastic. Since the
rows and columns of A1/2 ◦ A1/2 sum to unity, we have
rmax (A1/2 ) = cmax (A1/2 ) = 1. Similarly, rmax (B1/2 ) =
cmax (B1/2 ) = 1. Then, from Proposition 5, it follows that
the largest eigenvalue of A1/2 ◦ B1/2 is at most unity.

6

B. Matrix Kantorovich Inequalities
Matrix Kantorovich inequalities relate positive definite matrices by inequalities in the sense of the Löwner partial order.4
These inequalities can be used to extend the Löwner partial
order to the Hadamard product of positive definite matrices.
Our proposed RIC bound relies on the tightness of these
Kantorovich inequalities and their extensions.
A matrix version of the Kantorovich inequality was first
proposed by Marshall and Olkin in [38]. It is stated below as
Proposition 9.
Proposition 9 (Marshall and Olkin [38]). Let A be an n × n
positive definite matrix. Let A admit the Schur decomposition
A = UΛUT with unitary U and Λ = diag(λ1 , λ2 , . . . , λn )
such that λi ∈ [m, M ]. Then, we have
A2 ≤ (M + m)A − mM In .

(19)

The above inequality (19) is the starting point for obtaining
a variety of forward and reverse Kantorovich-type matrix
inequalities for positive definite matrices. In Propositions 10
and 11, we state specific forward and reverse inequalities,
respectively, which are relevant to us.
Proposition 10 (Liu and Neudecker [39]). Let A be an n × n
positive definite Hermitian matrix, with eigenvalues in [m, M ].
Let V be an n × n matrix such that VT V = I. Then,
2
1
(20)
VT A2 V − VT A2 V ≤ (M − m)2 I.
4
Proposition 11 (Liu and Neudecker [40]). Let A and B be
n×n positive definite matrices. Let m and M be the minimum
and maximum eigenvalues of B1/2 A−1 B1/2 . Let X be an
n × p matrix with rank q (n > p ≥ q). Then, we have
4mM
(XT BX)(XT AX)† (XT BX) ≥
XT BA−1 BX.
(M + m)2
(21)
Proposition 10 can be proved using (19) by pre- and
post-multiplying by VT and V, respectively, followed by
completion of squares for the right hand side terms. The proof
of Proposition 11 is given in [40].
C. Kantorovich Matrix Inequalities for the Hadamard Products of Positive Definite Matrices
Lemmas 1 and 2 stated below extend the Kantorovich inequalities from the previous subsection to Hadamard products.
Lemma 1 (Liu and Neudecker [39]). Let A and B be
n × n positive definite matrices, with m and M denoting the
minimum and maximum eigenvalues of A ⊗ B. Then, we have
1
A2 ◦ B2 ≤ (A ◦ B)2 + (M − m)2 In .
(22)
4
Proof. Let J be the selection matrix such that JT J = I and
A ◦ B = JT (A ⊗ B)J. Then, by applying Proposition 10 with
A replaced with A ⊗ B, and V replaced with J, we obtain
1
JT (A ⊗ B)2 J − (JT (A ⊗ B)J)2 ≤ (M − m)2 I.
4
4 The Löwner partial order here refers to the relation “≤”. For positive
definite matrices A and B, A ≤ B if and only if B − A is a positive
semi-definite matrix.

Using Fact 8.21.29 in [2], i.e., (A ⊗ B)2 = A2 ⊗ B2 , we get
JT (A2 ⊗ B2 )J − (A ◦ B)2 ≤

1
(M − m)2 I,
4

Finally, by observing that JT (A2 ⊗ B2 )J = A2 ◦ B2 , we
obtain the desired result.
Lemma 2 (Liu [41]). Let A, B be n × n positive definite
correlation matrices. Then,
A1/2 ◦ B1/2 ≥

2cd
In
+ d2

c2

(23)

where the eigenvalues of A1/2 and B1/2 lie inside [c, d].
Lemma 2 follows from Proposition 11, by replacing A with
In ⊗ B, B with A1/2 ⊗ B1/2 , and X with J, where J is
the n2 × n binary selection matrix such that JT J = I and
A ◦ B = JT (A ⊗ B)J.
V. P ROOF OF THE D ETERMINISTIC k-RIC B OUND
(T HEOREM 1)
The key idea used in bounding the k-RIC of the columnwise
KR product A B is the observation that the Gram matrix
of A B can be interpreted as a Hadamard product between
the two correlation matrices AT A and BT B, as mentioned
in the following Proposition.
Proposition 12 (Rao and Rao [42]). For A, B ∈ Rm×n ,
(A

B)T (A

B) = (AT A) ◦ (BT B)

(24)

Proof. See Proposition 6.4.2 in [42].
Then, by using the forward and reverse Kantorovich matrix
inequalities, we obtain the proposed upper bound for k-RIC
of A B as explained in the following arguments.
Without loss of generality, let S ⊂ [n] be an arbitrary index
set representing the nonzero support of z in (8), with |S| ≤ k.
Let AS denote the m × |S| submatrix of A, constituting |S|
columns of A indexed by the set S. Let BS be constructed
similarly. Since δk (A), δk (B) < 1, both AS , BS have full
rank, and consequently the associated Gram matrices ATS AS ,
BTS BS are positive definite. Further, since A and B have
unit norm columns, both ATS AS and BTS BS are correlation
matrices with unit diagonal entries. Using Proposition 12, we
can write
(AS

BS )T (AS

BS ) = ATS AS ◦ BTS BS .

(25)

Next, for k ≤ m, by applying Lemma 1 to the positive
definite matrices (ATS AS )1/2 and (BTS BS )1/2 , we get,

 1
1
1 2
ATS AS ◦ BTS BS ≤ (ATS AS ) 2 ◦(BTS BS ) 2 + (M −m)2 Ik
4
1
2
≤ Ik + (M − m) Ik ,
(26)
4
where the second inequality is a consequence of the unity
bound on the spectral radius of the Hadamard product between
correlation matrices, shown in Proposition 8. In (26), M and
m are upper and lower bounds for the maximum and minimum
eigenvalues of (ATS AS )1/2 ⊗ (BTS BS )1/2 , respectively. From
the restricted isometry of A and B, and by application of

7

Proposition 4, the minimum and maximum eigenvalues of
T
1/2
(A
⊗ (BTS BS )1/2qare lower and upper bounded by
q S AS )

almost surely. Then, for all t > 0,

By introducing δ , max(δkA , δkB ), it is easy to check that
the eigenvalues of (ATS AS )1/2 ⊗ (BTS BS )1/2 also lie inside
the interval [1 − δ, 1 + δ]. Plugging m = 1 − δ and M = 1 + δ
in (26), and by using (25), we get

(AS BS )T (AS BS ) ≤ 1 + δ 2 Ik .
(27)

Proof. See Theorem 6.7 in [45].

(1 −

δkA )(1

−

δkB )

(1 +

and

δkA )(1

+

δkB ),

respectively.

Similarly,
by applying√Lemma 2 to ATS AS and BTS BS with
√
c = 1 − δ and d = 1 + δ, we obtain

p
1 − δ 2 Ik .
(ATS AS )1/2 ◦ (BTS BS )1/2 ≥
ATS AS

BTS BS

From Proposition 6, we have
◦
2
(ATS AS )1/2 ◦ (BTS BS )1/2 . Therefore, we can write

ATS AS ◦ BTS BS ≥ 1 − δ 2 Ik .

≥

(AS

BS ) (AS

BS ) ≥ 1 − δ

2



Ik .

2

/2ν

.

Theorem 14 can be used to show a subgaussian tail for the
maximal linear combination of bounded nonnegative random
variables, stated below.
Lemma 3. Let x1 , x2 , . . . , xn be i.i.d. nonnegative, bounded
random variables
Pn satisfying xi ≤ b. Then, y ,
supz∈Rn ,||z||2 ≤1 i=1 zi xi is a nonnegative random variable
which satisfies the following tail inequality:
P (y − Ey ≥ t) ≤ e−t

2

/2b2

.

Proof. See Appendix B.
The following proposition bounds the expectation of a
nonnegative subgaussian random variable.

Further, using (25), we get
T

P (z − Ez ≥ t) ≤ e−t

(28)

Finally, Theorem 1’s statement follows from (27) and (28).
VI. P RELIMINARIES FOR P ROBABILISTIC k-RIC B OUND

Proposition 15. Let x be a nonnegative random variable with
a subgaussian tail, i.e., for t ≥ 0,
P(z − Ez ≥ t) ≤ e−t
√
for some ν > 0. Then, Ez ≤ 2πν.

2

/2ν

In this section, we briefly discuss some concentration results
on certain functions of subgaussian random variables which
will appear in the proofs of Theorems 2 and 3.

Proof. See Appendix C.

A. A Tail Probability for Subgaussian Vectors

The proof of Theorem
2 starts
 with a variational definition

of the k-RIC, δk √Am √Bm given below.

The Theorem below presents the Hanson-Wright inequality
[43], [44], a tail probability for a quadratic form constructed
using independent subgaussian random variables.
Theorem 13 (Rudelson and Vershynin [44]). Let x =
(x1 , x2 , . . . , xn ) ∈ Rn be a random vector with independent
components xi satisfying Exi = 0 and ||xi ||ψ2 ≤ K. Let A
be an n × n matrix. Then, for every t ≥ 0,

P xT Ax − ExT Ax > t
"
!#
t2
t
≤ 2 exp −c min
2 ,
K 4 ||A||HS K 2 ||A||
where c is a universal positive constant.
B. Concentration of Supremum of Linear Combination of
Bounded, Nonnegative Independent Random Variables
The following theorem bounds the subgaussian tail of a
function of several independent random variables satisfying
a relaxed bounded difference property.
Theorem 14. Consider a general real-valued function of n
independent random variables z = f (x1 , x2 , . . . , xn ) and
zi denotes an xi -measurable random variable defined by
zi = inf x0i f (x1 , x2 , . . . , x0i , . . . , xn ). Assume that the random
variable z is such that there exists a constant ν > 0, for which,
n
X
i=1

2

(z − zi ) ≤ ν

VII. P ROOF OF THE P ROBABILISTIC k-RIC B OUND
(T HEOREM 2)


δk

A
√
m

B
√
m




=

sup

z∈Rn ,
||z||2 =1,||z||0 ≤k

A
√
m

B
√
m

2



−1 .

z
2

(29)
In order to find a probabilistic upper bound for δk , we intend
to find a constant δ ∈ (0, 1) such that P(δk √Am √Bm ≥ δ)
is arbitrarily close to zero. We therefore consider the tail event





 2


B
A
√
√
E,
sup
z −1 ≥δ ,


m
m
z∈Rn ,


2
||z||2 =1,||z||0 ≤k

(30)
and show that for m sufficiently large, P(E) can be driven
arbitrarily close to zero. In other words,
 δ serves
 the constant
B
A
√
√
.
as a probabilistic upper bound for δk
m
m
Let Uk be the set of all k or less sparse unit norm vectors
in Rn . Then, using Proposition 12, the tail event in (30) can
be rewritten as


T
P(E) = P sup zT (A B) (A B) z − m2 ≥ δm2
z∈U
 k


= P sup zT AT A ◦ BT B z − m2 ≥ δm2
z∈U
 k

n X
n
X


= P sup
zi zj aTi aj bTi bj − m2 ≥ δm2
z∈Uk i=1 j=1

8

where ai and bi denote the ith column of A and B, respectively. Further, by applying the triangle inequality and the
union bound, we get
!
n
X
2
2
2
2
2
P(E) ≤ P sup
zi ||ai ||2 ||bi ||2 − m ≥ αδm +
z∈Uk i=1





n
n
X
X

zi zj aTi aj bTi bj
z∈Uk i=1
j=1,j6=i

P  sup

≥ (1 − α)δm2  . (31)

In the above, α ∈ (0, 1) is a variational union bound parameter
which can be optimized at a later stage. We now proceed to
find separate upper bounds for each of the two probability
terms in (31).
The first probability term in (31) admits the following
sequence of relaxations.
!
n
X
2
2
2
2
2
P sup
zi ||ai ||2 ||bi ||2 − m ≥ αδm

In step (d), β ∈ (0, 1) is a variational union bound parameter.
Step (g) is once again the union bound and exploits the i.i.d.
nature of the columns of A and B. Step (h) is obtained
by setting β = αδ/4. Lastly, step (i) is the Hanson-Wright
inequality (Theorem 13) applied to the subgaussian vector a1 .
Next, we turn our attention to the second probability term
in (31). It can be upper bounded as follows:
sup

n
n
X
X

z∈Uk i=1
j=1,j6=i

≤ sup

≤

n
X

z∈Uk i=1



(b)

≤

sup

P

≤

P

2

2

(c)

=

P

(d)

n
X

[ n

2

2

||ai ||2 ||bi ||2 − m2


P



2

2



i=1
(e)

=

(f )

≤

(g)

≤

(h)

≤

(i)

≤

nP





2
2
||a1 ||2 ||b1 ||2 − m2 ≥ αδm2 .
2

2

||a1 ||2 − m ||b1 ||2 − m ≥ αβδm2


α(1 − β)δm
2
+2nP ||a1 ||2 − m ≥
2


p
2
2nP ||a1 ||2 − m ≥ αβδm


α(1 − β)δm
2
+2nP ||a1 ||2 − m ≥
.
2



αδm
αδ
2
4nP ||a1 ||2 − m ≥
1−
2
4
nP

4ne

2 2
−cm α4Kδ4
o



.

|zj | |uij vij |

!
|zi | ||ai ||2 ||bi ||2
n
X


|zj0 | |uij vij | ,

(33)

j=1,j6=i

z∈Uk i=1
j=1,j6=i


≤ P  max sup

1≤i≤n z∈Uk

n
X



√

zj uij vij ≥ 4 2πKo2 (γ log n)3/2 

j=1,j6=i

n
X

(1 − α)δm2
|zi | ||ai ||2 ||bi ||2 ≥ √
+ P sup
4 2πKo2 (γ log n)3/2
z∈Uk i=1

!
(.34)

The following Lemmas provide upper bounds for the two tail
probability terms in (34).

2

(1−αδ/4)



where uij , h ||aaii|| , aj i and vij , h ||bbii|| , bj i. From
2
2
the approximate rotational invariance of subgaussian random
variables [32], it can be shown that the inner products uij and
vij are also subgaussian with ||uij ||ψ2 = ||vij ||ψ2 ≤ c3 K,
with c3 > 0 being a universal numerical constant.
Using (33), and by applying the union bound, the second
probability term in (31) can be written as the sum of following
two tail probabilities.


n
n
X
X
zi zj aTi aj bTi bj ≥ (1 − α)δm2 
P  sup


o
≥ αδm2 

||ai ||2 ||bi ||2 − m2 ≥ αδm2

n
X

sup

n
X

j=1,j6=i

1≤i≤n z0 ∈Uk

1≤i≤n

≤

|zi | ||ai ||2 ||bi ||2 

 max sup

1≤i≤n







2

zi2 ||ai ||2 ||bi ||2 − m2 ≥ αδm2

max ||ai ||2 ||bi ||2 − m2 ≥ αδm2

n
X

z∈Uk i=1

!
2

zi zj aTi aj bTi bj

z∈Uk i=1

z∈Uk i=1

(a)

2

2

+m ||a||2 − m + m ||b||2 − m .

(32)

In the above, step (a) follows from the triangle inequality
combined with the fact that zi2 ’s sum to one. The inequality
in step (b) is a consequence of the fact that any nonnegative
convex combination of n arbitrary numbers is at most the
maximum among the n numbers. Step (c) is obtained by
simply rewriting the tail event for the maximum of n random
variables as the union of tail events for the individual random
variables. Step (d) is obtained by using the union bound over
values of index i ∈ [n]. Step (e) follows because the columns
of A and B are i.i.d.. Step (f ) is the union bound combined
with the fact that for any two vectors a, b ∈ Rm , the following
triangle inequality holds:



2
2
2
2
||a||2 ||b||2 − m2 ≤
||a||2 − m ||b||2 − m

Lemma 4. Let A and B be m × n random matrices as
specified in Theorem 2. Let uij , h ||aaii|| , aj i and vij ,
2
h ||bbii|| , bj i, where ai and bi denote the ith column of A and
2
B, respectively. Then,


n
X
√
P  max sup
|zj ||uij vij | ≥ 4 2πKo2 (γ log n)3/2 
1≤i≤n z∈Uk

j=1,j6=i

≤

2e
n2(c2 γ−1)

,

(35)

where Ko , max(K, 1) and c2 > 0 is a universal constant.
Proof. See Appendix D.

9

Lemma 5. Let A and B be m × n random matrices with independent zero mean, unit variance, i.i.d. subgaussian entries
satisfying ||Aij ||ψ2 = ||Bij ||ψ2 ≤ K. Then,
!
n
X
(1 − α)δm2
P sup
|zi | ||ai ||2 ||bi ||2 ≥ √
4 2πKo2 (γ log n)3/2
z∈Uk i=1
≤ 2ne

cm
−K
4
o

,

(36)

√
8 2πKo2 γ 3/2 √
k log3/2
(1−α)δ

n. Here, Ko = max (K, 1)
provided m ≥
and c > 0 is a universal constant.
Proof. See Appendix E.
By using Lemmas 4 and 5 together in (34), we get


n
n
X
X
P  sup
zi zj aTi aj bTi bj ≥ (1 − α)δm2 
z∈Uk i=1
j=1,j6=i

≤

2e

cm
−K
4

to the dimensions of the input matrices, we had to resort to the
randomness in their entries. Removing this randomness aspect
of our results could be an interesting direction for future work.
A PPENDIX
A. Proof of Proposition 7
Proof. Since A is a correlation matrix, it admits the Schur
decomposition, A = UΛUT , with unitary U and eigenvalue
matrix Λ = diag(λ1 , λ2 , . . . , λn ). Since A is positive semidefinite, its nonnegative square-root exists and is given by
A1/2 = UΛ1/2 UT . Consider
n
n
X
X
1/2
1/2
A1/2 ◦ A1/2 =
λi ui uTi ◦
λj uj uTj
i=1

=

4e

+ 2ne o ≤ 2(c γ−1) ,
(37)
n2(c2 γ−1)
n 2
 √

3
8 2πKo2 γ 3/2 √
(2c2 γ−1)Ko4 log n
2 n,
provided m ≥ max
k
log
.
(1−α)δ
c
Using (32) and (37) together in (31), we get

=

n X
n
X
i=1 j=1
n X
n
X

j=1
1/2 1/2

λi λj

1/2 1/2

λi λj



ui uTi ◦ uj uTj
T

(ui ◦ uj ) (ui ◦ uj ) .(39)

i=1 j=1

Above, the second equality follows from the distributive
property of the Hadamard product and the last step follows
4e
8e
4
[2]. Using (39), we can show that the rows
 +
≤ 2(c γ−1) , (38) from Fact 7.6.2 in 1/2
P(E) ≤  2 2
2(c2 γ−1)
2
cα δ (1−αδ/4)2 m
n
n
and
columns
of
A
◦ A1/2 sum to one, as follows:
−1
4
4Ko log n
n
n X
n
X
 √

1/2 1/2
T
1/2
1/2
3
8 2πKo2 γ 3/2 √
(2c2 γ−1)ξKo4 log n
(A
◦
A
)1
=
λi λj (ui ◦ uj ) (ui ◦ uj ) 1
2
provided m ≥ max
k log n,
,
(1−α)δ
c


i=1 j=1
4
n X
n
where ξ = max 1, α2 δ2 (1−αδ/4)
.
2
X
1/2 1/2
T
=
λi λj (ui ◦ uj ) (ui ◦ 1) uj
Lastly, by choosing α = 1/2, we get P(δk ≥ δ) = P(E) ≤
i=1 j=1
8en−2(c2 γ−1) , provided that
n
n X
!
X
√
1/2 1/2
2 3/2√
4
3
λi λj (ui ◦ uj ) uTi uj
=
(2c2 γ −1)ξKo
16 2πKo γ
k log 2 n,
m ≥ max
log n ,
i=1 j=1
δ
c
n
X


λi (ui ◦ ui ) = d (say).
=
16
where ξ = max 1, γδ2 (1−δ/8)2 . Note that, in terms of k and
i=1
√
n, the first term in the inequality for m scales as k log3/2 n;
The above arguments follow from the orthonormality of
it dominates the second term, which scales as log n. This ends
the columns of U, and repeated application
in
Pn of Fact 7.6.1
our proof.
2
[2]. Note that for k ∈ [n], d(k) =
λ(i)
(u
(k))
=
i
i=1
[UΛUT ]kk = Akk = 1. Thus, we have shown that (A1/2 ◦
VIII. C ONCLUSIONS
A1/2 )1 = 1. Likewise, it can be shown that 1T (A1/2 ◦
In this work, we have analyzed the restricted isometry A1/2 ) = 1T . Thus, A1/2 ◦ A1/2 is doubly stochastic.
property of the columnwise Khatri-Rao product matrix in
terms of its restricted isometry constants. We gave two upper B. Proof of Lemma 3
bounds for the k-RIC of a generic columnwise Khatri-Rao
Define y(i) , inf0 sup (z1 x1 + · · · + zi x0i + · · · + zn xn ).
product matrix. The first k-RIC bound, a deterministic bound,
xi z∈Rn
||z||≤1
is valid for the Khatri-Rao product of an arbitrary pair of
Pn
∗
sup
input matrices of the same size with normalized columns. Further, let z , arg
j=1 zj xj . Since xi are nonn
z∈R ,||z||2 ≤1
It is conveniently computed in terms of the k-RICs of the negative, clearly z∗ is a nonnegative,
unit norm vector. Then,
input matrices. We also gave a probabilistic RIC bound for for i ∈ [n],
the columnwise KR product of a pair of random matrices with


i.i.d. subgaussian entries. The probabilistic RIC bound is one
n
n
X
X 0

of the key components needed for computing tight sample y − y(i) = sup
zj xj − inf0 sup 
zj xj + zi0 x0i 


xi z0 ∈Rn ,
complexity bounds for several machine learning algorithms.
z∈Rn , j=1
j=1,
0
||z||2 ≤1
||z ||2 ≤1 j6=i
The analysis of the RIP of Khatri-Rao product matrices in


this article can be extended in multiple ways. The current RIC
n
n
X
X
bounds can be extended to the Khatri-Rao product of three or
≤
zj∗ xj − inf0 
zj∗ xj + zi∗ x0i 
xi
more matrices. More importantly, in order to relate the RICs
j=1
j=1,j6=i

10



= zi∗ xi − inf0 x0i = zi∗ xi .

a,b
m×n
× Rm×n : x1 = a, y1 = b}
(40) Let E2 , E2 ∩{(X, Y) ∈ R
denote the set of matrix tuples (X, Y) with their first columns

Pn
fixed as a and b ∈ Rm , respectively. Then, conditioned
∗
(i) 2
Since
≤
i ≤ b and ||z ||2 ≤ 1, we have
i=1 y − y
Pn x∗2
on E2a,b , the random variables |u1j v1j |, 2 ≤ j ≤ n are
2
2
z
b
≤
b
.
Finally,
by
invoking
Theorem
14
with
ν
=
i=1 i
i.i.d., bounded and nonnegative random variables. By applying
b2 , we obtain the desired tail bound for y.
Lemma 3, it follows that


n
n
X
X
C. Proof of Proposition 15
P  sup
|zj ||uij vij | − E sup
|zj ||u1j v1j | ≥ t E2a,b 
z∈Uk j=2
z∈Uk j=2
The said upper bound for Ez can be derived as shown below.
Z ∞
Z ∞
2
4 2
2
≤ e−t /8K γ log n . (43)
P(z ≥ r + Ez)dr
P(z ≥ t)dt =
Ez =
Z −Ez
Z0 ∞
It is to be noted here that the above tail bound in the RHS
∞
2
√
2
− r2ν
−r /2ν
does not depend on a and b. This leads to an interesting
e
e
dr ≤
≤
dr ≤ 2πν.
−∞
−Ez
consequence explained in the following discourse.
a,b
Let T be an event such that P(T
≤ η, where η is
S |E2 ) a,b
independent of a, b. Since E2 = a,b∈Rn E2 , we have


D. Proof of Lemma 4
a,b
n (T ∩ E
P
∪
a,b∈R
2
P(T ∩ E2 )
=
P(T |E2 ) =
Let Q ⊆ (Rm×n × Rm×n ) be the collection of matrix
P(E
)
P(E
)
2
2
tuples (X, Y) satisfying |uij vij | < 2K 2 γ log n for all 1 ≤
R
R
a,b
a,b
a,b
xT
P(T
∩
E
P(T
|E
)
i xj
2
2 )P(E2 )
a,b
a,b
i, j ≤ n, j 6= i, where uij and vij are evaluated as h ||xi || i and
=
=
2
P(E2 )
P(E2 )
yT y
h ||yi i ||j i, respectively. Then, for subgaussian random matrices
R
a,b
2
P(E2 )
P(E2 )
A, B as defined in Lemma 4,
a,b
=η
= η.
(44)
≤η


P(E2 )
P(E2 )

 [ 
Coming back to our proof, using similar arguments as
|uij vij | ≥ 2K 2 γ log n 
P ((A, B) ∈
/ Q) = P 
 above5 and on account of the tail bound in the RHS in (43)

1≤i,j≤n
being independent of a and b, it follows that
j6=i


X
(a)

n
n
X
X
≤
P |uij vij | ≥ 2K 2 γ log n
|zj ||u1j v1j | ≥ t E2 
|zj ||uij vij | − E sup
P  sup
xi

(b)

≤

1≤i,j≤n
j6=i
2


n
P |u12 v12 | ≥ 2K 2 γ log n
2


√ p
n2 P |u12 | ≥ 2K γ log n

z∈Uk j=2

z∈Uk j=2

2

≤ e−t

/8K 4 γ 2 log2 n

. (45)

Further, using Proposition 15, the probability term in the
LHS of the inequality in (45) can be replaced by a smaller
≤
probability term as shown below.
(d)
e


2 −2c1 γ log n
≤ en e
= 2(c γ−1) .
(41)
n
X
√
n 1
|zj ||u1j v1j | ≥ t + 2 2πK 2 γ log n E2 
P  sup
In the above, steps (a), (b), and (c) are obtain by applying
z∈Uk j=2
the union bound over n2 combinations of distinct (i, j) pairs
2
2 2
2
≤ e−t /8K γ log n .
and exploiting the identical subgaussian tails of the random
variables uij and vij , i 6= j. Step (d) is simply the standard
Setting t = 4K(γ log n)3/2 , we get
subgaussian tail bound, with c1 > 0 a universal constant. Thus,


n
for γ > 1/c1 , the random variable |uij vij |, i 6= j, is uniformly
X
√
3
1
Psup
|zj ||u1j v1j | ≥ 4 2πKo2 (γ log n) 2 E2  ≤ 2γ .
bounded by 2K 2 γ log n with arbitrarily high probability, for
n
z∈Uk j=2
sufficiently large n.
(46)
Let E2 denote the event that the matrix tuple (A, B) ∈ Q.
Finally,
by
combining
(41),
(42)
and
(46),
we
obtain
the
Then, by the law of total probability, we have
desired tail bound:




n
X
n
X
√
P  max sup
|zj ||uij vij | ≥ t
P  max sup
|zj ||uij vij | ≥ 4 2πKo2 (γ log n)3/2 
1≤i≤n z∈Uk
j=1,j6=i
1≤i≤n z∈Uk
j=1,j6=i


n
X
1
e
2e
≤ 2γ−1 + 2(c γ−1) ≤ 2(c γ−1) ,
(47)
≤ P  max sup
|zj ||uij vij | ≥ t E2  + P(E2c )
1
n
n
n 2
1≤i≤n z∈Uk
j=1,j6=i


where c2 = min (c1 , 1) is a universal positive constant.
n
X
5 The tail bound in (45) can also be obtained by using the law of total
≤ nP  sup
|zj ||u1j v1j | ≥ t E2  + P(E2c ).
(42)
(c)

z∈Uk j=2

probability extended to conditional probabilities.

11

E. Proof of Lemma 5
Consider the tail event
)
(
n
X
(1 − α)δm2
.
E3 = sup
|zi | ||ai ||2 ||bi ||2 ≥ √
4 2πKo2 (γ log n)3/2
z∈Uk i=1
(48)
While bounding the tail probability P(E3 ), the supremum with
respect to z can be circumvented as shown below.
!
n
X
(1 − α)δm2
|zi |
√ ||ai ||2 ||bi ||2 ≥ √
P(E3 ) = P sup
3
4 2πkKo2 (γ log n) 2
z∈Uk i=1 k


(1 − α)δm2
. (49)
≤ P max ||ai ||2 ||bi ||2 ≥ √
1≤i≤n
4 2πkKo2 (γ log n)3/2
The above inequality is obtained by observing that
since z has unit P`2 -norm, by Cauchy-Schwarz inequaln
ity, we have √1k i=1 |zi | ≤ 1. Consequently, the linPn
zi
√
||ai ||2 ||bi ||2 can be at most
ear combination
i=1
k
max1≤i≤n ||ai ||2 ||bi ||2 , a quantity independent of z.
Since ai and bi , the column vectors of A and B, respectively, are i.i.d., the following series of union bounds apply.


(1 − α)δm2
√
P(E3 ) ≤ nP ||a1 ||2 ||b1 ||2 ≥
4 2πkKo2 (γ log n)3/2
s
!
(1 − α)δm2
√
≤ 2nP ||a1 ||2 ≥
4 2πkKo2 (γ log n)3/2



(1 − α)δm
2
≤ 2nP ||a1 ||2 −m ≥ m √
−1 .(50)
4 2πkKo2 (γ log n)3/2

≤ P



(1−α)δm
√
√
2 γ 3/2 k(log n)3/2
4 2πKo


−1

+P  sup

o

and show that for sufficiently large m, P(E1 ) can be driven
arbitrarily close to zero, thereby√implying√that δ is a probabilistic upper bound for δk ((A/ m A/ m)). Now, P(E1 )
admits the following union bound:


T
P(E1 ) = P sup zT (A A) (A A) z − m2 ≥ δm2
z∈U
 k


= P sup zT AT A ◦ AT A z − m2 ≥ δm2
z∈U
 k

n X
n
X

2
= P  sup
zi zj aTi aj − m2 ≥ δm2 
z∈Uk i=1 j=1

2
||ai ||4

2

2

≥ αδm

−m



n
n
X
X

aTi aj

2

≥ (1 − α)δm2  .(53)

In the above, the second identity follows from Proposition 12.
The last inequality uses the triangle inequality followed by the
union bound, with α ∈ (0, 1) being a variational parameter to
be optimized later. Similar to the proof of Theorem 2, we now
derive separate upper bounds for each of the two probability
terms in (53).
The first term in (53) admits the following series of relaxations.
!
n
X
4
2
2
2
P sup
zi ||ai ||2 − m ≥ αδm
z∈Uk i=1

(a)

≤

sup

P

n
X

z∈Uk i=1

!
4

zi2 ||ai ||2 − m2 ≥ αδm2



(b)

4
max ||ai ||2
1≤i≤n

2



P

(c)


4
||a1 ||2 − m2 ≥ αδm2 .


2
2
2
nP ||a1 ||2 − m ≥ αβδm


α(1 − β)δm
2
+2nP ||a1 ||2 − m ≥
2


p
2
nP ||a1 ||2 − m ≥ αβδm


α(1 − β)δm
2
+2nP ||a1 ||2 − m ≥
.
2



αδm
αδ
2
3nP ||a1 ||2 − m ≥
1−
2
4

(d)

≤

(e)

≤

(f )

≤

(g)

≤

nP

−m

2

≤

≤

4

F. Proof Sketch for Theorem 3
The proof of Theorem 3 is along similar lines as that of
Theorem 2; the sketch here focuses on the differences in the
steps. We consider the tail event
(
)
 2

A
A
√
√
E1 , sup
z −1 ≥δ ,
(52)
m
m
z∈Uk
2

!
zi2

zi zj
z∈Uk i=1
j=1,j6=i

≤ 2ne−cm/Ko .
(51)

 √
8 2πKo2 γ 3/2 √
3/2
k(log n) , and with c > 0
provided m ≥
(1−α)δ
being a universal constant.
P(E3 ) ≤ 2ne

z∈Uk i=1



Since a1 is a subgaussian vector with independent entries, by
the Hanson-Wright concentration inequality in Theorem 13,
the desired tail probability can be obtained as follows:
cm
−K
4

sup

n
X

≥ αδm



2 2

−cm α4Kδ4 (1−αδ/4)2

3ne

o

.

(54)

In the above, step (a) is the triangle inequality. The inequality
in step (b) follows from the fact that nonnegative convex
combination of n arbitrary numbers is at most the maximum
among the n numbers. Step (c) is a union bound. Step (d)
is also a union bounding argument with β ∈ (0, 1) as a
variational parameter, combined with the fact that for any vec4

2

tor a, the triangle inequality ||a||2 − m2 ≤ ||a||2 − m
2
||a||2

2

+

2m
− m is always true. Step (f ) is obtained by choosing the union bound parameter β = αδ/4. Finally, step (g)
is the Hanson-Wright inequality (Theorem 13) applied to the
subgaussian vector a1 .
We now derive an upper bound for the second probability
term in (53). Note that
sup

n
n
X
X

z∈Uk i=1
j=1,j6=i

≤ sup

n
X

z∈Uk i=1

zi zj aTi aj

2

|zi | ||ai ||2 

2

n
X
j=1,j6=i


|zj |u2ij 

12

≤

n
X

sup

z∈Uk i=1

!

n
X

2
|zi | ||ai ||2  max sup
1≤i≤n

z0 ∈U

k


|zj0 |u2ij ,(55)

j=1, j6=i

where uij , h ||aaii|| , aj i. The inner product uij is a subgaus2
sian random variable satisfying ||uij ||ψ2 ≤ c4 K, where c4 is
a universal numerical constant.
Using (55) in (53) yields the following union bound.


n
n
X
X

2
≥ (1 − α)δm2 
P  sup
zi zj aTi aj
z∈Uk i=1
j=1,j6=i


≤




P
 max sup

1≤i≤n z0 ∈Uk

+P

sup

n
X

z∈Uk i=1

n
X
j=1
j6=i

√

|zj0 |u2ij ≥ 4 2πKo2 (γ log n)3/2 


2
|zi | ||ai ||2

(1 − α)δm2
≥ √
4 2πKo2 (γ log n)3/2

!
. (56)

The following Lemmas 6 and 7 provide upper bounds for the
two tail probability terms occurring in the RHS of (56).

provided m ≥ max

where ξ = max 1,

Proof. See Appendix G.
Lemma 7. Let A be an m×n random matrix with zero mean,
unit variance, i.i.d. subgaussian entries satisfying ||Aij ||ψ2 ≤
K. Then,
!
n
X
(1 − α)δm2
− cm
2
|zi | ||ai ||2 ≥ √
P sup
≤ ne Ko4 ,
2
3/2
4 2πKo (γ log n)
z∈Uk i=1
(57)
√
8 2πKo2 γ 3/2 √
3/2
provided m ≥
k
log
n.
Here,
c
>
0
is
a
(1−α)δ
universal constant.
Proof. The proof is similar to that of Lemma 5, which is given
in Appendix E.
By using the tail probability bounds in Lemmas 6 and 7
together in (56), we obtain the following upper bound.


n
n
X
X

2
P  sup
zi zj aTi aj
≥ (1 − α)δm2 
z∈Uk i=1
j=1,j6=i

e

≤

e

−cm/Ko4

1

+ ne
= 2(c γ−1) + ( cm −1)
n2(c2 γ−1)
n 2
n Ko4 log n
2e
≤
.
(58)
n2(c2 γ−1)
The  √
above
inequality
is
true
for
m
≥

3
8 2πKo2 γ 3/2 √
(2c2 γ−1)Ko4 log n
2
max
k log n,
. By combining
(1−α)δ
c
(54), (56) and (58), we obtain the following tail bound.
P(E) ≤

3


n



cα2 δ 2 (1−αδ/4)2 m
−1
4 log n
4Ko

+

4
α2 δ 2 (1−αδ/4)2

(2c2 γ−1)ξKo4
log n
c



n,

,

. Finally, by choosing

−2(c2 γ−1)

α = 1/2, we have
P(E) ≤ 4en
, provided that

√
16 2πKo2 γ 3/2 √
(2c2 γ−1)ξKo4
3/2
m ≥ max
k
log
n,
log
n
,
δ
c


16
with ξ = max 1, δ2 (1−δ/8)2 . Note that, in terms of k and
√
n, the first term in the inequality for m scales as k log3/2 n;
it dominates the second term, which scales as log n.
G. Proof of Lemma 6
Let W ⊆ Rm×n be the collection of all m × n sized
matrices X with columns xi , i ∈ [n], and satisfying |uij | ,
√
|xT
i xj |
||xi ||2 < K 2γ log n for all 1 ≤ i, j ≤ n, j 6= i. Then, for a
subgaussian random matrix A,


n
o
[
p
P (A ∈
/ W) = P 
|uij | ≥ K 2γ log n 
1≤i,j≤n, j6=i



p
P |uij | ≥ K 2γ log n

X

≤

Lemma 6. Let A be an m × n random matrix as specified in
Theorem 3. Let uij , h ||aaii|| , aj i. Then,
2


n
X
√
3
e
Pmax sup
|zj |u2ij ≥ 4 2πKo2 (γ log n) 2≤ 2(c γ−1) ,
1≤i≤n z∈Uk
n 2
j=1,j6=i
where Ko , max (K, 1) and c2 > 0 is a universal constant.

√
3
8 2πKo2 γ 3/2√
k log 2
 (1−α)δ




1≤i,j≤n, j6=i
2 


p
n
P |u12 | ≥ K 2γ log n
2
en2 −2c1 γ log n
e
e
= 2(c γ−1) ,
2
2n 1

≤
≤

(60)

where c1 > 0 is a universal constant. In the above, the first
and second inequalities are due to the union bound and the
identically distributed nature of uij , j 6= i. The last inequality
is simply the subgaussian tail
√ bound. Thus, for γ ≥ 1/c1 , and
for sufficiently large n, K 2γ log n acts as a uniform upper
bound for the random variables |uij |, j 6= i with arbitrarily
high probability.
Let E3 denote the event that the matrix A ∈ W. Then, by
law of total probability,


n
X
P  max sup
|zj ||uij |2 ≥ t
1≤i≤n z∈Uk

j=1,j6=i


≤ P  max sup

1≤i≤n z∈Uk


≤ nP  sup

n
X

z∈Uk j=2

n
X


|zj ||uij |2 ≥ t E3  + P(E3c )

j=1,j6=i


|zj ||u1j |2 ≥ t E3  + P(E3c ).

(61)

Conditioned on event E3 and the column a1 assuming
some fixed value, the random variables |u1j |2 are bounded,
nonnegative and i.i.d. random variables. By Lemma 3, it
follows that


n
n
X
X
P  sup
|zj ||u1j |2 − E sup
|zj ||u1j |2 ≥ t E3 , a1 
z∈Uk j=2

z∈Uk j=2

2

≤ e−t

/8K 4 γ 2 log2 n

. (62)

2e
4e
≤ 2(c γ−1) , (59) Since the above tail probability bound is independent of
n2(c2 γ−1)
n 2
a1 , it remains unchanged after marginalizing the conditional

13

probability in the LHS over all values of a1 , i.e.,


n
n
X
X
P  sup
|zj ||u1j |2 − E sup
|zj ||u1j |2 ≥ t E3 
z∈Uk j=2

z∈Uk j=2

≤ e−t

2

/8K 4 γ 2 log2 n

.

(63)

Further, using Proposition 15, the probability term in the LHS
of the inequality in (63) can be replaced by a smaller tail
probability as shown below.


n
X
√
P  sup
|zj ||uij |2 ≥ t + 2 2πK 2 γ log n E3 
z∈Uk j=2

2

≤ e−t

/8K 2 γ 2 log2 n

.

3/2

Setting t = 4K(γ log n) , we get


n
X
√
1
P sup
|zj ||u1j |2 ≥ 4 2πKo2 (γ log n)3/2 E3 ≤ 2γ .
n
z∈Uk j=2
(64)
Finally, by combining (60), (61) and (64), we obtain the
desired tail bound.


n
X
√
P  max sup
|zj ||uij |2 ≥ 4 2πKo2 (γ log n)3/2 
1≤i≤n z∈Uk

j=1,j6=i

1
e
e
+ 2(c γ−1) ≤ 2(c γ−1) ,
n2γ−1
2n 1
n 2
where c2 = min (1, c1 ) is a universal positive constant.
≤

R EFERENCES
[1] C. G. Khatri and C. R. Rao, “Solutions to some functional equations
and their applications to characterization of probability distributions,”
Sankhya: The Indian Journal of Statistics, Series A (1961-2002), vol. 30,
no. 2, pp. 167–180, 1968.
[2] D. S. Bernstein, Matrix Mathematics: Theory, Facts, and Formulas
(Second Edition). Princeton University Press, 2009.
[3] S. Liu and G. Trenkler, “Hadamard, Khatri-Rao, Kronecker and other
matrix products,” International Journal of Information and System
Sciences, vol. 4, no. 1, pp. 160–177, 2007.
[4] M. F. Duarte and R. G. Baraniuk, “Kronecker compressive sensing,”
IEEE Trans. Image Process., vol. 21, no. 2, pp. 494–504, Feb. 2012.
[5] A. Koochakzadeh and P. Pal, “Sparse source localization in presence of
co-array perturbations,” in International Conference on Sampling Theory
and Applications (SampTA), May 2015, pp. 563–567.
[6] D. Romero, D. D. Ariananda, Z. Tian, and G. Leus, “Compressive covariance sensing: Structure-based compressive sensing beyond sparsity,”
IEEE Signal Process. Mag., vol. 33, no. 1, pp. 78–93, Jan. 2016.
[7] G. Dasarathy, P. Shah, B. N. Bhaskar, and R. D. Nowak, “Sketching
sparse matrices, covariances, and graphs via tensor products,” IEEE
Trans. Inf. Theory, vol. 61, no. 3, pp. 1373–1388, Mar. 2015.
[8] W. K. Ma, T. H. Hsieh, and C. Y. Chi, “DOA estimation of quasistationary signals with less sensors than sources and unknown spatial
noise covariance: A Khatri-Rao subspace approach,” IEEE Trans. Signal
Process., vol. 58, no. 4, pp. 2168–2180, Apr. 2010.
[9] N. D. Sidiropoulos and A. Kyrillidis, “Multi-way compressed sensing
for sparse low-rank tensors,” IEEE Signal Process. Lett., vol. 19, no. 11,
pp. 757–760, Nov. 2012.
[10] D. L. Donoho, M. Elad, and V. N. Temlyakov, “Stable recovery of sparse
overcomplete representations in the presence of noise,” IEEE Trans. Inf.
Theory, vol. 52, no. 1, pp. 6–18, Jan. 2006.
[11] S. Foucart and H. Rauhut, A Mathematical Introduction to Compressive
Sensing. Birkhäuser Basel, 2013.
[12] E. J. Candès, J. K. Romberg, and T. Tao, “Stable signal recovery from
incomplete and inaccurate measurements,” Communications on Pure and
Applied Mathematics, vol. 59, no. 8, pp. 1207–1223, 2006.

[13] E. J. Candes and T. Tao, “Decoding by linear programming,” IEEE
Trans. Inf. Theory, vol. 51, no. 12, pp. 4203–4215, Dec 2005.
[14] R. Baraniuk, M. Davenport, R. DeVore, and M. Wakin, “A simple proof
of the restricted isometry property for random matrices,” Constructive
Approximation, vol. 28, no. 3, pp. 253–263, 2008.
[15] T. T. Cai, L. Wang, and G. Xu, “New bounds for restricted isometry
constants,” IEEE Trans. Inf. Theory, vol. 56, no. 9, pp. 4388–4394, Sept
2010.
[16] P. Pal and P. P. Vaidyanathan, “Pushing the limits of sparse support
recovery using correlation information,” IEEE Trans. Signal Process.,
vol. 63, no. 3, pp. 711–726, Feb. 2015.
[17] D. P. Wipf and B. D. Rao, “An empirical Bayesian strategy for solving
the simultaneous sparse approximation problem,” IEEE Transactions on
Signal Processing, vol. 55, no. 7, pp. 3704–3716, Jul. 2007.
[18] S. Khanna and C. R. Murthy, “On the support recovery of jointly
sparse Gaussian sources using sparse Bayesian learning,” CoRR, vol.
abs/1703.04930. [Online]. Available: http://arxiv.org/abs/1703.04930
[19] C. Carathéodory and L. Fejér, “Uber den zusammenhang der extremen
von harmonischen funktionen mit ihren koeffizienten un uber den picardlandauschen satz,” Rendiconti del Circolo Matematico di Palermo,
vol. 32, no. 1, pp. 218–239, 1911.
[20] P. Stoica and R. Moses, Spectral Analysis of Signals. Pearson Prentice
Hall, 2005.
[21] Z. Yang, L. Xie, and P. Stoica, “Vandermonde decomposition of multilevel Toeplitz matrices with application to multidimensional superresolution,” IEEE Trans. Inf. Theory, vol. 62, no. 6, pp. 3685–3701,
Jun. 2016.
[22] N. D. Sidiropoulos and A. Kyrillidis, “Multi-way compressed sensing
for sparse low-rank tensors,” IEEE Signal Processing Letters, vol. 19,
no. 11, pp. 757–760, Nov. 2012.
[23] D. Nion and N. D. Sidiropoulos, “A PARAFAC-based technique for
detection and localization of multiple targets in a MIMO radar system,”
in Proc. ICASSP, 2009, pp. 2077–2080.
[24] A. M. Tillmann and M. E. Pfetsch, “The computational complexity of the
restricted isometry property, the nullspace property, and related concepts
in compressed sensing,” IEEE Trans. Inf. Theory, vol. 60, no. 2, pp.
1248–1259, Feb. 2014.
[25] R. A. Horn and C. R. Johnson, Eds., Matrix Analysis. Cambridge
University Press, 1986.
[26] S. Jokar, “Sparse recovery and Kronecker products,” in 44th Annual
Conference on Information Sciences and Systems, Mar. 2010, pp. 1–4.
[27] A. Bhaskara, M. Charikar, A. Moitra, and A. Vijayaraghavan, “Smoothed
analysis of tensor decompositions,” in Proceedings of the 46th Annual
ACM Symposium on Theory of Computing, 2014, pp. 594–603.
[28] J. Anderson, M. Belkin, N. Goyal, L. Rademacher, and J. R. Voss, “The
more, the merrier: the blessing of dimensionality for learning large
Gaussian mixtures,” in 27th Annual Conference on Learning Theory,
Jun. 2014, pp. 1135–1164.
[29] N. D. Sidiropoulos and R. Bro, “On the uniqueness of multilinear
decomposition of N-way arrays,” Journal of Chemometrics, vol. 14,
no. 3, pp. 229–239, 2000.
[30] P. Koiran and A. Zouzias, “Hidden cliques and the certification of the
restricted isometry property,” IEEE Trans. Inf. Theory, vol. 60, no. 8,
pp. 4999–5006, Aug. 2014.
[31] S. Khanna and C. R. Murthy, “Rényi divergence based covariance
matching pursuit of joint sparse support,” in Sig. Process. Advances
in Wireless Commun. (SPAWC), Jul. 2017, pp. 1 – 5.
[32] R. Vershynin, “Introduction to the non-asymptotic analysis of random
matrices,” 2010.
[33] J. A. Tropp, “Greed is good: algorithmic results for sparse approximation,” IEEE Trans. Inf. Theory, vol. 50, no. 10, pp. 2231–2242, Oct.
2004.
[34] G. Visick, “A quantitative version of the observation that the Hadamard
product is a principal submatrix of the Kronecker product,” Linear
Algebra and its Applications, vol. 304, no. 13, pp. 45 – 68, 2000.
[35] R. A. Horn and C. R. Johnson, Topics in Matrix Analysis. Cambridge;
New York: Cambridge University Press, 1994.
[36] B. Mond and J. E. Pec̆arić, “Inequalities for the Hadamard product of
matrices,” SIAM J. Matrix Anal. Appl., vol. 19, no. 1, pp. 66–70, Jan.
1998.
[37] H. J. Werner, “Hadamard product of square roots of correlation matrices,” Image, vol. 26, pp. 1–32, Apr. 2001.
[38] A. W. Marshall and I. Olkin, “Reversal of the Lyapunov, Hölder,
and Minkowski inequalities and other extensions of the Kantorovich
inequality,” Journal of Mathematical Analysis and Applications, vol. 8,
no. 3, pp. 503 – 514, 1964.

14

[39] S. Liu and H. Neudecker, “Several matrix Kantorovich-type inequalities,” Journal of Mathematical Analysis and Applications, vol. 197, no. 1,
pp. 23 – 26, 1996.
[40] ——, “Kantorovich inequalities and efficiency comparisons for several
classes of estimators in linear models,” Statistica Neerlandica, vol. 51,
no. 3, pp. 345–355, 1997.
[41] S. Liu, “On the Hadamard product of square roots of correlation
matrices,” Econometric Theory, vol. 18, no. 4, p. 1007, Aug. 2002.
[42] C. R. Rao and M. B. Rao, Matrix Algebra and Its Applications to
Statistics and Econometrics. Singapore: World Scientific, 1998.

[43] R. Adamczak, “A note on the Hanson-Wright inequality for random
vectors with dependencies,” Electron. Commun. Probab., vol. 20, pp.
72–84, 2015.
[44] M. Rudelson and R. Vershynin, “Hanson-Wright inequality and subgaussian concentration,” Electron. Commun. Probab., vol. 18, pp. 82–91,
2013.
[45] S. Boucheron, G. Lugosi, and P. Massart, Concentration Inequalities:
A Nonasymptotic Theory of Independence. Oxford University Press,
2013.

