1

Identifiability of Kronecker-structured Dictionaries
for Tensor Data

arXiv:1712.03471v1 [stat.ML] 10 Dec 2017

Zahra Shakeri, Anand D. Sarwate, and Waheed U. Bajwa

Abstract—This paper derives sufficient conditions for reliable
recovery of coordinate dictionaries comprising a Kroneckerstructured dictionary that is used for representing Kth-order
tensor data. Tensor observations are generated by a Kroneckerstructured dictionary and sparse coefficient tensors that follow
the separable sparsity model. This work provides sufficient
conditions on the underlying coordinate dictionaries, coefficient
and noise distributions, and number of samples that guarantee
recovery of the individual coordinate dictionaries up to a specified
error with high probability. In particular, the sample complexity
to recover K coordinate dictionaries with dimensions mk × pk
up to estimation error rk is shown to be maxk∈[K] O(mk p3k rk−2 ).
Index Terms—Dictionary identification, dictionary learning,
Kronecker-structured dictionary, sample complexity, tensor data.

I. I NTRODUCTION
With rapid advances in sensing and data acquisition technologies in recent years, individual data samples or signals increasingly are structured by multiple modes. Examples include
hyperspectral video (four modes; two spatial, one temporal,
and one spectral), colored depth video (five modes; two
spatial, one temporal, one spectral, and one depth), and fourdimensional tomography (four modes; three spatial and one
temporal). Such data form multiway arrays and are called
tensor data [2], [3].
Previous approaches to handling tensor data collapse or
vectorize the tensor into a long one-dimensional vector and
apply existing processing methods. This approach ignores the
structure and inter-mode correlations in tensor data. More
recently, several works instead assume a structure on the tensor
of interest through tensor decompositions such as the CANDECOMP/PARAFAC (CP) decomposition [4], Tucker decomposition [5], and PARATUCK decomposition [3]. Because
these decompositions involve fewer parameters, or degrees
of freedom, in the model, inference algorithms that exploit
the decomposition perform better than those for unstructured
tensors. Moreover, decompositions are more efficient in terms
of storage and computational cost: the cost of storing the
This work is supported in part by the National Science Foundation under
awards CCF-1525276 and CCF-1453073, and by the Army Research Office
under award W911NF-17-1-0546. Some of the results reported here are presented at the 2017 IEEE International Workshop on Computational Advances
in Multi-Sensor Adaptive Processing [1].
The authors are with the Department of Electrical and
Computer Engineering, Rutgers, The State University of New
Jersey, 94 Brett Road, Piscataway, NJ 08854, USA. (Emails:
zahra.shakeri@rutgers.edu, anand.sarwate@rutgers.edu,
and waheed.bajwa@rutgers.edu,)

decomposition can be substantially lower, and numerical methods can exploit the structure by solving simpler subproblems.
In this work, we focus on the problem of finding sparse
representations of tensors which have a Tucker decomposition.
More specifically, we analyze the dictionary learning (DL)
problem for tensors, where the goal is to construct an overcomplete basis (dictionary) such that each data sample can be
represented by only a few columns (atoms) of that basis [6]. To
account for the Tucker structure of tensor data, we require that
the dictionary underlying the vectorized versions of tensor data
points be Kronecker-structured (KS). That is, it is comprised
of coordinate dictionaries that transform various modes of the
tensor data. Such dictionaries have successfully been used for
tensor data representation in application such as hyperspecral
imaging, video acquisition, and distributed sensing [7]. This
gives rise to the fundamental question: what are the theoretical
limits on the learning of KS dictionaries underlying Kth-order
tensor data? To answer this question, we examine the KS-DL
objective function and find sufficient conditions on the number
of samples (or sample complexity) for successful identification
of coordinate dictionaries underlying the KS dictionary. To the
best of our knowledge, this is the first work presenting such
identification results for the KS-DL problem.
A. Our Contributions
We derive sufficient conditions on the true coordinate dictionaries, coefficient and noise distributions, regularization parameter, and the number of data samples such that the KS-DL
objective function has a local minimum within a small neighborhood of the true coordinate dictionaries with high probability. Specifically, suppose the observations are generated from
a true dictionary D0 ∈ Rm×p consisting of the Kronecker
product of K coordinate dictionaries, D0k ∈ Rmk ×pk , k ∈
QK
QK
{1, . . . , K}, where m = k=1 mk and p = k=1 pk . Our
results imply that that N = maxk∈[K] Ω(mk p3k rk−2 ) samples
are sufficient (with high probability) to recover the underlying
coordinate dictionaries D0k up to the given estimation error
rk , k ∈ {1, . . . , K}.
B. Relationship to Prior Work
Among existing works on structured DL that have focused
exclusively on the Tucker model for tensor data, [8]–[12] have
empirically established the superiority of KS-DL problem in
various settings for 2nd and 3rd-order tensor data.
In terms of analytical results for dictionary identification,
there are several works in the literature that study the unstructured dictionary identifiability problem [13]–[20]. These
results cannot be trivially translated for the KS-DL problem

2

and differ from each other in terms of the distance metric used
for identification guarantees. In this work, we focus on the
Frobenius norm as the distance metric. Among the cited works,
[19] and [20] also consider this metric. In [20], minimax
lower bounds for dictionary reconstruction error are provided.
These bounds show that the number of samples for reliable
reconstruction (up to a prescribed mean squared error r) of
an m × p dictionary within its local neighborhood is on the
order of N = Ω(mp2 r−2 ). A competing upper bound for
the sample complexity of the DL problem is obtained in [19],
where it is shown that N = Ω(mp3 r−2 ) samples are sufficient
to guarantee (with high probability) the existence of a local
minimum of the DL cost function within the r neighborhood of
the true dictionary. In our previous works, we have obtained
lower bounds on the minimax risk of KS-DL for 2nd-order
[21] and Kth-order tensors [22], [23], and have shown that the
number of samples necessary for reconstruction of the true KS
dictionary within its local neighborhood up to a given estimation error scales with the sum of the product P
of the dimensions
K
of the coordinate dictionaries, i.e., N = Ω(p k=1 mk pk r−2 ).
Compared to this sample complexity lower bound, our upper
bound is larger by a factor maxk p2k .
Analytically, while our proof techniques are inspired by
the approach in [19] for the DL problem for vectorized
data, we recover the true coordinate dictionaries (up to a
specified error), and not just the true KS dictionary. In
particular, the following assumptions distinguish this work
from [19]: (i) the true dictionary and the recovered dictionary
belong to the class of KS dictionaries, and (ii) dictionary
coefficient tensors follow the separable sparsity model that
requires nonzero coefficients to be grouped in blocks [23],
[24]. Translating the results in [19] to the case of tensor data
requires overcoming the following challenges: (i) expanding
the asymptotic objective function into a summation in which
individual terms depend on coordinate dictionary recovery
errors, (ii) translating identification conditions on the KS
dictionary to conditions on its coordinate dictionaries, and (iii)
connecting the asymptotic objective function to the empirical
objective function using concentration of measure arguments
that use the coordinate-wise Lipschitz continuity property of
the KS-DL objective function with respect to the coordinate
dictionaries.
C. Notational Convention and Preliminaries
Underlined bold upper-case, bold upper-case and lowercase letters are used to denote tensors, matrices and vectors,
respectively. Lower-case letters denote scalars. For a tensor
X, its (i1 , . . . , iK )-th element is denoted as xi1 ...iK . The i-th
element of v is denoted by vi and the ij-th element of X is
denoted as xij . The elements of the sign vector of v, denoted
as sign(v), are equal to sign(vi ) = vi /|vi |. The k-th column
of X is denoted by xk and XI denotes the matrix consisting of
the columns of X with indices I. We use |I| for the cardinality
of the set I. Sometimes we use matrices indexed by numbers,
such as X1 , in which case the second index denotes the column
index. We use vec(X) to denote the vectorized version of
matrix X, which is a column vector obtained by stacking the
columns of X on top of one another. We use diag (X) to

denote the vector comprised of the diagonal elements of X
and Diag (v) to denote the diagonal matrix, where its diagonal
elements are comprised of elements of v. We also use sin(v)
to denote the vector with elements sin(vi ) (used similarly for
other trigonometry functions). Norms are given by subscripts,
so kvk0 , kvk1 , and kvk2 are the ℓ0 , ℓ1 , and ℓ2 norms of v,
while kXk2 and kXkF are the spectral and Frobenius norms
of X, respectively. We use [K] to denote {1, 2, . . . , K} and
X1:K to denote {Xk }K
k=1 . For matrices X1 and X2 , we define
their distance to be d(X, Y) = kX − YkF . For X0 belonging
to the set X , we define

Sr (X0 ) , X ∈ X : kX − X0 kF = r ,

Br (X0 ) , X ∈ X : kX − X0 kF < r ,

B̄r (X0 ) , X ∈ X : kX − X0 kF ≤ r .
(1)

Note that while Sr (X0 ) represents the surface of a sphere,
we use the term “sphere” for simplicity. We use the standard
“big-O” notation for asymptotic scaling.
In the body, we sometimes use ∆f (X; Y) , f (X) −
f (Y). We define HX , (X⊤ X)−1 , X+ , HX X⊤ , and
PX , XX+ for full rank matrix X. We write X ⊗ Y
for the Kronecker product of two matrices X ∈ Rm×n and
Y ∈ Rp×q , where the result is an mp × nq matrix and
we have kX ⊗ YkF = kXkF kYkF [25]. We also use
N
k∈K Xk = X1 ⊗ · · · ⊗ XK .
1) Tensor Operations and Tucker Decomposition for Tensors: A tensor is a multidimensional array where the order of
the tensor is defined as the number of components in the array.
A tensor X ∈ Rp1 ×p2 ×···×pK of order K can be expressed as
a matrix by reordering its elements to form a matrix. This
reordering is called unfolding:
the mode-k unfolding matrix
Q
of a tensor is a pk × i6=k pi matrix, which we denote by
X(k) . Each column of X(k) consists of the vector formed
by fixing all indices of X except the one in the kth-order.
The k-rank of a tensor X is defined by rank(X(k) ); trivially,
rank(X(k) ) ≤ pk . The mode-k matrix product of the tensor X
and a matrix A ∈ Rmk ×pk , denoted by X ×k A, is a tensor of
size p1 × . . . pk−1 × mk × pk+1P
· · · × pK whose elements are
pk
(X ×k A)i1 ...ik−1 jik+1 ...iK =
ik =1 xi1 ...ik−1 ik ik+1 ...iK ajik .
The mode-k matrix product of X and A and the matrix
multiplication of X(k) and A are related [3]:
Y = X ×k A ⇔ Y(k) = AX(k) .

(2)

The Tucker decomposition decomposes a tensor into a core
tensor multiplied by a matrix along each mode [3], [5]. We
take advantage of the Tucker model since we can relate
the Tucker decomposition to the Kronecker representation of
tensors [24]. For a tensor Y ∈ Rm1 ×m2 ×···×mK of order K,
if rank(Y(k) ) ≤ pk holds for all k ∈ [K] then, according to
the Tucker model, Y can be decomposed into:
Y = X ×1 D1 ×2 D2 ×3 · · · ×K DK ,

(3)

where X ∈ Rp1 ×p2 ×···×pK denotes the core tensor and
Dk ∈ Rmk ×pk are factor matrices. The following is implied
by (3) [3]:
Y(k) = Dk X(k) (DK ⊗ · · · ⊗ Dk+1 ⊗ Dk−1 ⊗ · · · ⊗ D1 )⊤ .

3

Since the Kronecker product satisfies vec(BXA⊤ ) = (A ⊗
B) vec(X), (3) is equivalent to

vec(Y) = DK ⊗ DK−1 ⊗ · · · ⊗ D1 vec(X),
(4)

where vec(Y) , vec(Y(1) ) and vec(X) , vec(X(1) ) [3].
2) Definitions for Matrices: We use the following definitions for a matrix D with unit-norm columns: δs (D) denotes
the restricted isometry property (RIP) constant of order s
for D [26]. We define the worst-case coherence of D as
µ1 (D) = max i,j d⊤
i dj . We also define the order s cui6=j

mulative coherence of D as
µs (D) , max max kD⊤
J dj k 1 .
|J |≤s j6∈J

(5)

Note that for s = 1, the cumulative coherence is equivalent to
the
N worst-case coherence and µs (D) ≤ sµ1 (D) [19]. For D =
k∈[K] Dk , where Dk ’s have unit-norm columns, µ1 (D) =
maxk∈[K] µ1 (Dk ) [27, Corollary 3.6] and it can be shown that
 Y

µs (D) ≤ max µsk (Dk )
(1 + µsi −1 (Di )) . (6)
k∈[K]

i∈[K],
i6=k

The rest of the paper is organized as follows. We formulate the KS dictionary learning problem in Section II. In
Section III, we provide analysis for asymptotic recovery of
coordinate dictionaries composing the KS dictionary and in
Section IV, we present sample complexity results for identification of coordinate dictionaries that are based on the results
of Section III. Finally, we conclude the paper in Section V.
In order to keep the main exposition simple, proofs of the
lemmas and propositions are relegated to appendices.
II. S YSTEM M ODEL
We assume the observations are Kth-order tensors Y ∈
Rm1 ×m2 ×···×mK . Given generating coordinate dictionaries
D0k ∈ Rmk ×pk , coefficient tensor X ∈ Rp1 ×p2 ×···×pK , and
noise tensor W, we can write y , vec(Y) using (4) as1

 O
D0k x + w, kxk0 ≤ s,
(7)
y=

from [pk ], k ∈ [K]. Then, the random support of x is
{J ⊆ [p], |J | = s} that is associated with
{J1 × J2 × · · · × JK : Jk ⊆ [pk ], |Jk | = sk , k ∈ [K]}
Q
via lexicographic indexing, s = k∈[K] sk , and the support
of x1:N ’s are assumed to be independent and identically distributed (i.i.d.). We make the same assumptions as assumptions
A and B in [19] for the distribution of x. These include: (i)
nonzero
elements of x are zero-mean and uncorrelated, i.e.,

2
E xJ x⊤
Is , (ii) x and its sign, σ = sign(x),
J |J = E x 
are uncorrelated, i.e., E xJ σ ⊤
= E{|x|} Is , (iii) eleJ |J
ments of sign(x) are uncorrelated, i.e., E σ J σ ⊤
= Is ,
J |J
(iv) magnitude of x is bounded, i.e., kxk2 ≤ Mx , and
(v) nonzero entries of x have a minimum magnitude, i.e.,
E {|x|}
minj∈J |xj | ≥ xmin . We define κx , p
as a measure
E {x2 }
of the flatness of x (κx ≤ 1, with κx = 1 when all nonzero
coefficients are equal [19]).
Noise distribution: We make following assumptions on
the distribution of noise, which is i.i.d. across data samples:
 (i) elements
 of w are zero-mean and uncorrelated, i.e.,
E ww⊤ = E w2 Im
 , (ii) w is uncorrelated with x and σ,
i.e., E wx⊤ |J = E wσ ⊤ |J = 0, and (iii) magnitude
of w is bounded, i.e., kwk2 ≤ Mw .
Our goal is to recover the underlying coordinate dictionaries, D0k , from N noisy realizations of tensor data. To solve this
problem, we take the empirical risk minimization approach and
define



O
2
1
y−
Dk x′ + λkx′ k1 , and
fy (D1:K ) , ′inf p
x ∈R
2
2
N
1 X
(8)
fy (D1:K ) ,
FY (D1:K ) ,
N n=1 n

where λ is a regularization parameter. We can recover the
coordinate dictionaries by solving the following regularized
optimization program:
min FY (D1:K ) .

k∈[K]

where x = vec(X) ∈ Rp denotes
generatN 0 the sparse
ing coefficient vector, D0 =
Dk ∈ Rm×p denotes
the underlying KS dictionary, and w = vec(W) ∈ Rm
denotes the underlying noise vector. Here, D0k ∈ Dk =
mk ×pk
{D
, kdk,j kQ
k = [K],
2 = 1, ∀j ∈ [pk ]} for N
N p =
Q k∈R
2
for
k∈[K]
k∈[K] mk . We use
k∈[K] pk and m =
throughout the paper for simplicity of notation. We assume
we have N noisy observations, stacked in Y = [y1 , . . . , yN ].
To state the problem formally, we first make the following
assumptions on distributions of x and w for each observation.
Coefficient distribution: We assume the coefficient tensor X
follows the “separable sparsity” model. That is, x = vec(X)
is sparse and the support of nonzero entries of x is random.
Specifically, we sample sk elements uniformly at random
1 We

have reindexed Dk ’s in (4) for ease of notation.
that the Dk ’s are compact sets on their respective oblique manifolds
of matrices with unit-norm columns [19].
2 Note

(9)

Dk ∈Dk
k∈[K]

K

More specifically, given desired errors {rk }k=1 , we want
a local minimum of (9) to be attained by coordinate dicb k ∈ Br (D0 ), k ∈ [K]. That is, for any set
tionaries D
k
k

K
b 1:K ) ≤ FY (D1:K ). To address
Dk ∈ Brk (D0k ) k=1 , FY (D
this problem, we first minimize the statistical risk:
min fP (D1:K ) , min Ey {fy (D1:K )} .

Dk ∈Dk
k∈[K]

Dk ∈Dk
k∈[K]

(10)

Then, we connect FY (D1:K ) to fP (D1:K ) using concentration of measure arguments and obtain the number of samples
sufficient for recovery of the coordinate dictionaries. This
ensures that any algorithm minimizing the objective function
in (9) is guaranteed to find a local minimum attained by
coordinate dictionaries close to the generating coordinate
dictionaries (as opposed to the generating KS dictionary in
the vectorized case [19]).

4

III. A SYMPOTOTIC I DENTIFIABILITY R ESULTS
In this section, we provide an identifiability result for the
KS-DL objective function in (10). The implications of this
theorem are discussed in Section V.
Theorem 1. Suppose the observations are generated according to (7) and the dictionary coefficients follow the separable
sparsity model of Section II. Further, assume the following
conditions are satisfied:

pk
1
0
(11)
sk ≤
2 , max µsk (Dk ) ≤ ,
0
4
k∈[K]
8 kD k + 1
k 2

and


E x2
72K2K−1
>
Mx E {|x|}
(1 − 2µs (D0 ))

sk
⊤
max
D0k D0k − I
k∈[K] pk

F

D0k 2

+1

Define

B. Proof Outline
.

K−1  
sk
2
⊤
√
κ2x D0k D0k − I
pk
1.5

D0k 2 + 1 , and
E {|x|}
1
(1 − 2µs (D0 )).
=
3K(1.5)K/2 Mx

Ck,min = 24

Cmax






(12)

F

(13)

Then,N
the map D1:K 7→ fP (D1:K ) admits a local minimum
0
b
b
b =
D
k∈[K] Dk such that Dk ∈ Brk (Dk ), k ∈ [K], for any
rk > 0 as long as
xmin
λ≤
,
(14)
8(1.5)(K−1)/2

and





s
1
1
.
=
O
= O
0 2
kD0 k22
kD01 k22 kD√
p
2 k2
√
√
Using the fact that D0 2 ≥ kD0 kF / m = p/ m, this
translates into sparsity order s = O (m). This scaling is similar
to the scaling of the sparsity level in [19]. Next, the left
hand side of the condition in (12) is less than 1. Moreover,
from properties of the Frobenius norm, it is easy to show
p
⊤
pk (pk − mk )/mk . The fact that
that D0k D0k − I
≥
√F
√
0
Dk 2 ≥ pk / mk and the assumption µsk (D0k ) ≤ 1/4
imply
right hand side of (12) is lower bounded by
 that the
p
Ω maxk sk (pk − mk )/m2k . Therefore, Theorem 1 applies
to coordinate dictionaries with dimensions pk ≤ m2k and
subsequently, KS-dictionary with p ≤ m2 . This is in line with
the scaling results in [19] for vectorized data.
Therefore, we have

λCmax
λCk,min
< rk <
, k ∈ [K],
E {|x|}
E {|x|}

(15)


X 
Mw
K/2 λKCmax
rk .
< 3(1.5)
−
Mx
E {|x|}

(16)

k∈[K]

A. Discussion
Our result captures the dependence of existence of a local
minimum on various properties of the coordinate dictionaries and demonstrates that there exists a local minimum of
fP (D1:K ) that is in local neighborhoods of the coordinate
dictionaries. This ensures asymptotic recovery of coordinate
dictionaries within some local neighborhood of the true coordinate dictionaries, as opposed to KS dictionary recovery for
vectorized observations [19, Theorem 1].
We now explicitly compare conditions in Theorem 1 with
the corresponding ones for vectorized observations [19, Theorem 1]. Given that the coefficients are drawn from the separable sparsity model, the sparsity constraints for the coordinate
dictionaries in (11) translate into
Y sk
1
s
≤
=
(17)
2 .
Q
0
K
p
pk
8
k∈[K]
k kDk k2 + 1

√
For given radii 0 < rk ≤ 2 pk , k ∈ [K], the spheres
Srk (D0k ) are non-empty. This follows from the construction
of dictionary classes, Dk ’s. Moreover, the mapping D1:K 7→
fP (D1:K ) is continuous with respect to the Frobenius norm
kDk − D′k kF on all Dk , D′k ∈ Rmk ×pk , k ∈ [K] [28]. Hence,
it is also continuous on compact constraint sets Dk ’s. We
derive conditions on the coefficients, underlying coordinate
dictionaries, Mw , regularization parameter, and rk ’s such that

∆fP (r1:K ) ,
inf 0 ∆fP D1:K ; D01:K > 0. (18)
Dk ∈Srk (Dk )

This along with the compactness of closed balls B̄rk (D0k ) and
the continuity of the mapping D1:K 7→ fP (D1:K ) imply the
b 1:K in open balls, Br (D0 )’s,
existence of local minima D
k
k
k ∈ [K].
To find conditions that ensure ∆fP (r1:K ) > 0, we take the
following steps: given coefficients that follow the separable
sparsity model, we can decompose any DJ , |J | = s, as
O
DJ =
Dk,Jk ,
(19)

where |Jk | = sk for k ∈ [K].3 Given a generating σ =
b by solving fy (D1:K ) with respect to x′ ,
sign(x), we obtain x
b = σ, hence eliminatconditioned on the fact that sign(b
x) = σ
ing the dependency of fy (D1:K ) on inf x′ by finding a closedb = σ, which we denote
form expression for fy (D1:K ) given σ
as φy (D1:K |σ). Denoting E {φy (D1:K |σ)} = φP (D1:K |σ),
we expand ∆φP D1:K ; D01:K |σ using (19) and separate the
terms that depend on each radius rk = kDk − D0k kF to obtain
conditions for sparsity levels sk , k ∈ [K],
 and coordinate
dictionaries such that ∆φP D1:K ; D01:K |σ > 0. Finally, we
derive conditions on Mw , coordinate dictionary coherences

b = σ and ∆fP D1:K ; D01:K =
and rk ’s that ensure σ
∆φP D1:K ; D01:K |σ .
Remark 1. The key assumption in the proof of Theorem 1 is
expanding DJ according to (19). This is a consequence of
the separable sparsity model for dictionary coefficients. For a
detailed discussion on the differences between the separable
sparsity model and the random sparsity model for tensors, we
refer the readers to our earlier work [21].
3 The separable sparsity distribution model implies sampling without replacement from columns of Dk .

5

Remark 2. Although some of the forthcoming lemmas needed
of Theorem 1 impose conditions on Dk ’s as well as true coordinate dictionaries D0k ’s, we later translate these conditions
exclusively in terms of D0k ’s and rk ’s.
The proof of Theorem 1 relies on the following propositions
and lemmas. The proofs of these are provided in Appendix A.
Proposition 1. Suppose the following inequalities hold for
k ∈ [K]:

pk
1
sk ≤
and max δsk (D0k ) ≤ . (20)
0
2
k∈[K]
8(kDk k2 + 1)
4
Then, for

λ̄ ,

1
λ
≤
,
E {|x|}
8(1.5)(K−1)/2

(21)

any collection of {rk : rk ≤ 0.15, k ∈ [K]}, and for all Dk ∈
Srk (D0k ), we have :

 sE{x2 } X rk
rk − rk,min (λ̄) ,
∆φP D1:K ; D01:K |σ ≥
8
pk
k∈[K]

(22)

where
rk,min (λ̄) ,

 K−1

2
√
1.5 2 + 2(K+1) λ̄ λ̄Ck,min .
3(2/ 1.5)K−1

In addition, if

λ̄ ≤

0.15
,
maxk∈[K] Ck,min

(23)


then rk,min < 0.15. Thus, ∆φP D1:K ; D01:K |σ > 0 for all
rk ∈ (rk,min (λ̄), 0.15], k ∈ [K].
The proof of Proposition 1 relies on the following lemmas
as well as Lemmas 4–7,15, and 16 in [19].
N
Lemma 1. Let D =
Dk where δs (Dk ) < 1 for k ∈ [K],
and J be a support set generated by the separable sparsity
model. Then any DJ , |J | = s, can be decomposed as DJ =
N
Dk,Jk , where |Jk | = sk and rank(Dk,Jk ) = sk , for
k ∈ [K]. Also, the following relations hold for this model:4
O
O
O
+
=
HDk,Jk ,
PDk,Jk , D+
=
D
,
H
PDJ =
D
J
J
k,Jk
(24)
where P and H are defined in section I-C.
Lemma 2. Given D1:K and D01:K , the difference
O
O
Dk −
D0k
X

e k,K , (25)
e k,1 ⊗ · · · ⊗ Dk − D0 ⊗ · · · ⊗ D
D
=
k
k∈[K]

e k,i is equal to either
where without loss of generality, each D
0
Dk or Dk .

e k,i for ease of notation
We drop the k index from D
throughout the rest of the paper.
4 The

equations follow from basic properties of the Kronecker product [25].

Lemma 3. Let σ ∈ {−1, 0, 1}p be an arbitrary sign vector
and J = J (σ) be its support. Define5
 2
O
1
y−
Dk x + λσ ⊤ x.
φy (D1:K |σ) =
inf p
2
x∈R
2
supp(x)⊂J

(26)

b minimizes
If D⊤
k,Jk Dk,Jk is invertible for k ∈ [K], then x
φy (D1:K |σ), where
O

O
−1 
bJ =
σJ ,
x
D+
D⊤
k,Jk Dk,Jk
k,Jk y − λ
(27)

bJ c = 0. Thus, φy (D1:K |σ) can be expressed in closed
and x
form:

O
1
1
φy (D1:K |σ) = kyk22 − y⊤
PDk,Jk y
2
2
O


O
λ2
+
⊤
+ λσ J
Dk,Jk y − σ ⊤
H
Dk,Jk σ J . (28)
2 J

Lemma 4. Assume max δsk (D0k ), δsk (Dk ) < 1 for k ∈
e be equal to either D0 or Dk . For
[K] and let D
k
φP (D1:K |σ) , Ey {φy (D1:K |σ)} ,

(29)

we have

∆φP D1:K ; D01:K σ
io
n h ⊤
E{x2 } X
0
=
...
EJ1 Tr D01 PD
e 1,J D1
1
2
k∈[K]
io
n h ⊤
EJk Tr D0k (Imk − PDk,Jk )D0k
n h
io
⊤
0
. . . EJK Tr D0K PD
e K,J DK
K
n h
io
X
+
0
e
EJ1 Tr D1,J1 D1 . . .
− λE{|x|}
k∈[K]

io
n h
io
n h
+
0
0
e
Tr
.
.
.
E
D
D
D
EJk Tr Isk − D+
J
K
K,JK K
k,Jk k
io
n h
λ2 X
+
...
EJ1 Tr HD
e 1 ,J1
2
k∈[K]
n h
io
io
n h
.
EJk Tr HD0k,J − HDk,Jk . . . EJK Tr HD
e K,J
K
k
(30)

Lemma 5. For any Dk ∈ Dk satisfying RIP of order sk , given
Jk ⊂ [pk ] and |Jk | = sk , the following relations hold:
p
kDk,Jk k2 = Dk,Jk ⊤ ≤ 1 + δsk (Dk ),
(31)
2

δsk (Dk ) ≤ µsk −1 (Dk ).

(32)

Lemma 6 ([19, Lemma 4]). Let Dk ’s be coordinate dictionaries such that δsk (Dk ) < 1. Then for any Jk ⊂ pk , |Jk | =
sk , HDk,Jk exists and
HDk,Jk

2

≤

1
,
1 − δsk (Dk )

D+
k,Jk

2

1
,
≤p
1 − δsk (Dk )
(33)

5 φ (D
y
1:K |σ) is not equal to φy (D1:K ) conditioned on σ and the
expression is only used for notation.

6

and for any D′k such that kDk − D′k kF ≤ rk <
p
1 − δsk (Dk ):
p
(34)
1 − δsk (D′k ) ≥ ( 1 − δsk (Dk ) − rk )2 , 1 − δk .

Lemma 7 ([19, Lemma 5]). For any δk < 1, Dk , D′k such
that max(δsk (Dk ), δsk (D′k )) ≤ δk , and Jk ⊂ pk , |Jk | = sk ,
we have
′
−1/2
kI − D+
kDk − D′k kF ,
k,Jk Dk,Jk k2 ≤ (1 − δk )
−3/2

kHDk,Jk − HD′k,J k2 ≤ 2(1 − δk )
k

kD+
k,Jk −

+
D′ k,Jk k2

kDk −

D′k kF ,

≤ 2(1 − δk )−1 kDk − D′k kF , and

k

1
2
Lemma 8 ([19, Lemma 6]). Given any
 k ∈ Dk ,
 Dk , D
⊤
there exist Vk ∈ Rmk ×pk with diag D1k Vk = 0 and

diag Vk⊤ Vk = Ipk and a vector θk = θk (D1k , D2k ) ∈
[0, π]pk , such that

(36)

where Ck (θk ) , Diag (cos(θk )) and Sk (θk ) ,
Diag (sin(θk )). Moreover,


2
θk,j
2
1
≤ θk,j , and
θk,j ≤ kdk,j − dk,j k2 = 2 sin
π
2
2
kθk k2 ≤ kD2k − D1k kF ≤ kθk k2 .
(37)
π
′
1
2
Similarly, there exists V
 k such that Dk = Dk Ck (θk ) +
′
2⊤ ′
Vk Sk (θ k ), where diag Dk Vk = 0.

Lemma 9. Fix D1:K and D01:K , and suppose
{Ak } , {Bk } , {δk } satisfy the following:
o
n
0⊤ 0
Ak ≥ max kD⊤
k Dk − Ipk kF , kDk Dk − Ipk kF ,

Bk ≥ max kDk k2 , kD0k k2 , and

δk ≥ max δsk (Dk ), δsk (D0k ) .
(38)

Then for all kθ k k2 ≥ kDk − D0k kF , k ∈ [K], we have

∆φP D1:K ; D01:K |σ



sE{x2 } X kθk k2
sk Bk2
2
≥
kθk k2 1 −
− λ̄κx δ−k
2
pk
p k 1 − δk
k∈[K]



Y
1
2 sk 2Ak Bk
,
(39)
λ̄κx
− δ−k + 2λ̄
1 − δi
p k 1 − δk
i∈[K]

where δ−k =

Q

i∈[K]
i6=k

r

1
.
2
xmin
λ
Suppose λ̄ ≤
, where λ̄ =
and
2E {|x|}
E {|x|}

max {rk } ≤ min λ̄Cmax , 0.15 .
max{µsk (D0k )} <
k

k∈[K]

If the following is satisfied:

X 
Mw
K/2
rk ,
< 3(1.5)
λ̄KCmax −
Mx

(40)

(41)

(42)

k∈[K]

kPDk,Jk − PD′k,J k2 ≤ 2(1 − δk )−1/2 kDk − D′k kF . (35)

D2k = D1k Ck (θ k ) + Vk Sk (θ k ),

{D0k ∈ Dk } satisfy:

1 + δi
.
1 − δi


Proposition 1 shows ∆φP D1:K ; D01:K |σ ≥ 0. However,
b, the solution of φy (D1:K |σ), σ
b = sign (b
given x
x) is not
necessarily equal to the sign of the generating σ. We derive
b is almost surely the unique minimizer
conditions that ensure x
b = σ. We introduce the following
of fy (D1:K ) and σ
proposition for this purpose.
Proposition 2. Let the generating coordinate dictionaries

then for any D1:K such that Dk ∈ Srk (D0k ), for k ∈
b is
[K], x
the minimizer of the map x′  7→
N almost′ surely
2
1
′
ky
−
(
D
)
x
k
+
λkx
k1 and ∆φP D1:K ; D01:K |σ =
k
2
2
∆fP D1:K ; D01:K .

The proof of Proposition 2 relies on the following lemmas
and [19, Lemmas 10–13].
1
Lemma 10 ([19, Lemma 13]). Assume µs (D) < . If
2
min x′j ≥ 2λ, and ky − Dx′ k2 < λ(1 − 2µs (D))
j∈J

(43)

b N
hold, then x
defined in (27) is the unique solution of
minx′ 21 ky − ( Dk ) x′ k2 + λkx′ k1 .
N 0
N
Lemma 11. For any D0 =
Dk and D =
Dk such
that Dk ∈ B̄rk (D0k ), for k ∈ [K], suppose the following
inequalities are satisfied:
max {µsk −1 (D0k )} ≤

k∈[K]

1
,
2

and

max rk ≤ 0.15.

k∈[K]

Then, we have
0

K/2 √

µs (D) ≤ µs (D ) + 2(1.5)

s

 X

k∈[K]


rk .

(44)

(45)

Proof of Theorem 1: The assumptions in (11) ensure that the conditions in (20) and (40) are satisfied for
Proposition 1 and Proposition 2, respectively. Assumptions
(12) and (14) ensure that the condition in (23) is satisxmin
fied for Proposition 1, λ̄ ≤
holds for Proposi2E {|x|}
tion 2, and maxk∈[K] {Ck,min } < Cmax
 . Hence, according
to Proposition 1, ∆φP D1:K ; D01:K |σ > 0 for all rk ∈
(λ̄Ck,min , 0.15], k ∈ [K]. Finally, according to Proposition
 2,
the assumption in (16) implies ∆φP D1:K ; D01:K |σ =
∆fP D1:K ; D01:K for all rk ≤ λ̄Cmax , k ∈ [K]. Furthermore, the assumption in (14) implies Cmax λ̄ ≤ 0.15. Consequently, for any {rk > 0, k ∈ [K]} satisfying the conditions
in
b = ND
bk
(15), D1:K → fP (D1:K ) admits a local minimum D
b k ∈ Br (D0 ), k ∈ [K].
such that D
k
k
IV. F INITE S AMPLE I DENTIFIABILITY R ESULTS

We now focus on solving (9) to derive finite-sample bounds
for KS dictionary identifiability. Compared to Gribonval et
al. [19] that uses Lipschitz continuity with respect to the KS
dictionary, our analysis is based on the “coordinate-wise Lipschitz continuity” with respect to the coordinate dictionaries.

7

Theorem 2. Suppose the observations are generated according to (7) and the dictionary coefficients follow the separable
sparsity model of Section II such that (11) to (16) are satisfied.
Then, for any number of observations satisfying
 2
pk (ε + mk pk )
N ≥ max Ω
k∈[K]
(rk − rk,min (λ̄))2
 K
2 

2 (1 + λ̄2 )Mx2
Mn
, (46)
+
s2 E{x2 }2
sE{x2 }

with probability at leastN
1 − e−ε , D1:K 7→ FY (D1:K ) admits
b k such that D
b k ∈ Br (D0 ), k ∈
b
D
a local minimum D =
k
k
[K].

Let us make some remarks about implications of Theorem 2.
First, sample complexity has an inverse relationship with
signal to noise ratio (SNR),6 which we define as SNR ,
sE{x2 }
E{kxk2 }
on the right hand
E{kwk2 } = mE{w 2 } . Looking at the terms
 2
side of (46) in Theorem 2, Mx /(sE x ) is related to the
deviation of kxk2 from its mean, E {kxk2 }, and depends on
the coefficient distribution and Mn /(sE x2 ) is related to
1/ SNR and depends on the noise and coefficient distributions.
Second, we notice dependency of sample complexity on the
recovery error of coordinate dictionaries. We can interpret rk
as the recovery error for D0k . Then, the sample complexity
scaling in (46) is proportional to maxk rk−2 . We note that
the sample complexity results obtained in [19] that are independent of r , D − D0 F only hold for the noiseless
setting and the dependency on r−2 is inevitable for noisy
observations [19]. Furthermore, given the condition on the
range of rk ’s in (15), rk ’s cannot be arbitrarily small, and
will not cause N to grow arbitrarily large.
Third, we observe a linear dependence between the sample complexity scaling in (46) and coordinate dictionaries’
dimensions, i.e., maxk O(mk p3k ). Comparing this to the scaling Q
in the unstructured
DL problem [19], i.e., O(mp3 ) =

3
O
k mk pk , the sample complexity in the KS-DL problem
scales with the dimensions of the largest coordinate dictionary,
as opposed to the dimensions of the KS dictionary.
We also compare this sample complexity upper bound
scaling to the sample complexity lower bound scaling in
our previous
1], where we obtained

P work [21, Corollary
N = Ω p k mk pk r−2 /K .7 In terms
 of overall error r, our
result translates into N = maxk Ω 2K Kp(mk p3k )r−2 . The
lower bound depended
P on the average dimension of the coordinate dictionaries, k mk pk /K, whereas, we observe here
a dependence on the dimensions of the coordinate dictionary
in terms of the maximum dimension, maxk mk pk . We also
observe an increase of order maxk p2k in the sample complexity
6 Sufficient

conditioning
have the following
X  Y
r≤
k∈[K]

B. Proof Outline
We follow a similar approach used in [19, Theorem 2] for
vectorized data. We show that, with high probability,

∆FY (r1:K ) ,
inf 0 ∆FY D1:K ; D01:K
(47)
Dk ∈Srk (Dk )

converges uniformly to its expectation,
∆fP (r1:K ) ,

inf

Dk ∈Srk (D0k )


∆fP D1:K ; D01:K .

i∈[K]
i6=k

on N implies O-scaling for sample complexity.
relation between r and rk ’s:

√ X
ek
rk .
Dk − D0k F ≤ p
D
F

k∈[K]

Assuming all rk ’s are equal, this then implies rk2 ≥ r 2 /(Kp).

(48)

In other words, with high probability,

|∆FY (r1:K ) − ∆fP (r1:K )| ≤ ηN ,

A. Discussion

7 We

upper bound scaling. This gap suggests that tighter bounds can
be obtained for lower and/or upper bounds.

(49)

where ηN is a parameter that depends on the probability and
other parameters in the problem. This implies ∆FY (r1:K ) ≥
∆fP (r1:K ) − 2ηN . In Theorem 1, we obtained conditions
that ensure ∆fP (r1:K ) > 0. Thus, if 2ηN < ∆fP (r1:K ) is
satisfied, this implies ∆FY (r1:K ) > 0, and using arguments
similar to the proof of Theorem N
1, D1:K 7→ FY (D1:K )
b k , such that D
bk ∈
b =
D
admits a local minimum D
0
bound deviaBrk (Dk ), k ∈ [K]. To find ηN , we uniformly

tions of D1:K 7→ ∆φY D1:K ; D01:K |σ from its expectation

K
on Srk (D0k ) k=1 . Our analysis is based on the coordinate-
wise Lipschitz continuity property of ∆φY D1:K ; D01:K |σ
with respect to coordinate dictionaries. Then, using (22),
we obtain the sufficient number of samples based on each
coordinate dictionary dimension and recovery error.
The proof of Theorem 2 relies on the following definition
and lemmas. The proofs of these are provided in Appendix B.
Definition 1 (Coordinate-wise Lipschitz continuity). A function f : D1 × · · · × DK → R is coordinate-wise Lipschitz
continuous with constants (L1 , . . . , LK ) if there exist real
K
K
constants {Lk ≥ 0}k=1 , such that for {Dk , D′k ∈ Dk }k=1 :
X
(50)
Lk kDk − D′k kF .
|f (D1:K ) − f (D′1:K )| ≤
k∈[K]

Lemma 12 (Rademacher averages [19]). Consider F to be a
set of measurable functions on measurable set X and N i.i.d.
random variables X1 , . . . , XN ∈ X . Assuming all functions
are bounded by B, i.e., |f (X)| ≤ B, almost surely, with
probability at least 1 − e−ε :


1 X
sup
f (Xn ) − EX {f (X)}
N
f ∈F
n∈[N ]
r
r



1 X
π
2ε
βn f (Xn )
+B
EX,β1:N sup
,
≤2
2
N
N
f ∈F
n∈[N ]

(51)

where β1:N ’s are independent standard Gaussian random
variables.
Lemma 13. Let H be a set of real-valued functions on
Dk ∈ B rk (D0k ), k ∈ [K], that are bounded by B almost
everywhere and are coordinate-wise Lipschitz continuous with
constants (L1 , . . . , LK ) . Let h1 , h2 , . . . , hN be independent

8

realizations from H with uniform Haar measure on H. Then,
with probability greater than 1 − e−ε :
1 X
sup
hn (D1:K ) − E {h(D1:K )}
2
Dk ∈Br (D0 ) N
n∈[N ]

k

k

k∈[K]

≤4

r

π
2N

 X

k∈[K]

p
Lk rk Kmk pk



+B

r

2ε
. (52)
N

0
Lemma
p 14. Consider Dk ∈ Dk and rk ’s √such that
0
1 − δsk (Dk ), for k ∈ [K] and define 1 − δk ,
rp
k <
1 − δsk (D0k ) − rk . The function ∆φY D1:K ; D01:K |σ is

K
almost surely coordinate-wise Lipschitz on Brk (D0k ) k=1
with Lipschitz constants
  Y q

Lk , (1 − δk )−1/2 Mx
1 + δsk (D0k ) + Mw
k∈[K]

√
+λ s

Y

k∈[K]

(1 − δk )−1/2

2

,

(53)


and ∆φY D1:K ; D01:K |σ is almost surely bounded on

P
K
Brk (D0k ) k=1 by k∈[K] Lk rk .

Proof of Theorem 2: From Lemmas 13 and 14, we have
that with probability at least 1 − e−ε :

sup
∆φY D1:K ; D01:K |σ
Dk ∈B(D0k ,rk )
k∈[K]

∆φP D1:K ; D01:K |σ

≤

−
r



√ 
2 X
√
Lk rk 2 πmk pk + ε ,
N

(54)

k∈[K]

where Lk is defined
 obtain
 in (53). From (54), we
∆φY D1:K ; D01:K |σ q > ∆φP D1:K ; D01:K |σ − 2ηN
√ 
√
2 P
ε .
where ηN
=
k∈[K] Lk rk 2 πmk pk +
N
In
Theorem
1,
we
derived
conditions  that
and
ensure ∆FX (r1:K )
=
∆φY D1:K ; D01:K |σ
0
=
∆fP (r1:K ).
Therefore,
∆φP D1:K ; D1:K |σ
∆FX (r1:K ) > ∆fP (r1:K ) − 2ηN , and the existence of
a local minimum of FX (D1:K ) within radii rk around
D0k , k ∈ [K], is guaranteed with probability at least
1 − e−ε as soon as 2ηN < ∆fP (r1:K ). According to

sE{x2 } P
rk
(78), ∆fP (r1:K ) ≥
rk − rk,min (λ̄) ;
k∈[K]
8
pk
therefore, it is sufficient to have for all k ∈ [K]:
r

√  sE{x2 }rk rk − rk,min (λ̄)
√
8
,
Lk rk 2 πmk pk + ε <
N
8pk
which translates into N ≥ maxk∈[K] Nk , where
2

2
√
√
24.5 Lk pk
Nk =
ε + 2 πmk pk
.
sE{x2 }(rk − rk,min (λ̄))
(55)
Furthermore, we can upper bound Lk by


(a) √
√ 2
Lk ≤ 2 1.25K/2 Mx + Mw + 2K/2 λ s

(b)

≤

√
2C1





1.25K + 2K λ̄2 Mx2 + Mw2 ,

(56)

where (a) follows from the fact that given the assumption
1
in (20), δk ≥
satisfies (34) for any rk ≤ 0.15 and (b)
2
follows from the following inequality:
1
1
1
λ̄E {kxk1 } ≤ √ λ̄E {kxk2 } ≤ √ λ̄Mx .
s
s
s
2
√
√
ε + 2 πmk pk
Substituting (56) in (55) and using
≤
C0 (ε + mk pk ), we get



2K (1 + λ̄2 )Mx2 + Mw2
2
Nk = Ω pk (ε + mk pk ) 2
s E{x2 }2 (rk − rk,min (λ̄))2
 2
 K

pk (ε + mk pk )
2 (1 + λ̄2 )Mx2
Mw2
=Ω
.
+ 2
s2 E{x2 }2
s E{x2 }2
(rk − rk,min (λ̄))2
λ = λ̄E {|x|} =

and N ≥ maxk∈[K] Nk .

Remark 3. To bound deviations of ∆φY D1:K ; D01:K |σ
from its mean, we can also use the bound provided in [28,
Theorem 1] that prove uniform convergence results using
covering number argumentsr
forP
various classes of dictionaries.
( k mk pk + ε) log N
In this case, we get ηN ≤ c
for some
N
√
constant c, where an extra log N term appears compared to
(52). Therefore, Lemma 13 provides a tighter upper bound.
V. C ONCLUSION
In this paper, we focused on recovery of coordinate dictionaries comprising a Kronecker-structured dictionary used to
represent Kth-order tensor data. We derived a sample complexity upper bound for coordinate dictionary identification
up to a specified error by expanding the objective function
with respect to individual coordinate dictionaries and using the
coordinate-wise Lipschitz continuity property. Our results hold
for dictionary coefficients generated according to the separable
sparsity model. This model has some limitations compared
to the random sparsity model and we leave the analysis for
the random sparsity model for future work. Future work also
includes providing practical KS-DL algorithms that achieve
the sample complexity scaling of Theorem 2.
A PPENDIX A
Proof of Lemma 2: The proof follows from mathematical
induction and is omitted here due to space constraints.
Proof of Lemma 3: The proof follows from [19, Definition 1]. Taking the derivative of φy (D1:K |σ) with respect to
b.
x and setting it to zero, we get the expression in (27) for x
b in (26), we get
Substituting x

O

⊤
1
D⊤
φy (D1:K |σ) =
kyk22 −
y
−
λσ
J
k,Jk
2

O
 O

⊤
−1
⊤
(Dk,Jk Dk,Jk )
Dk,Jk y − λσ J


O
1
(a) 1
PDk,Jk y
= kyk22 − y⊤
2
2
O


O
λ2
+
⊤
+ λσ J
Dk,Jk y − σ ⊤
HDk,Jk σ J ,
J
2

9



where (a) follows from (24).

Proof of Lemma 4:
We use N
the expression
N for
φy (D1:K |σ) from (28). For any D =
Dk , D′ =
D′k ,
′
Dk , Dk ∈ Dk , we have

∆φy (D1:K ; D′1:K |σ) = φy (D1:K |σ) − φy (D′1:K |σ)

O
O
1
PD′k,J −
PDk,Jk y
= y⊤
k
2
O

O
′+
⊤
D k,Jk −
D+
− λσ J
k,Jk y


O
O
λ2
′
+ σ⊤
(57)
H
−
H
Dk,Jk σ J .
Dk,J
k
2 J
N

N 0
We substitute y =
Dk x + w =
D0k,Jk xJ + w
and break up the sum in (57) into 6 terms:
X
∆φi (D1:K ; D′1:K |σ) , (58)
∆φy (D1:K ; D′1:K |σ) =
i∈[6]

where
⊤
O
1
∆φ1 (D1:K ; D′1:K |σ) = x⊤
D0k
2

 O
O
O
D0k x
PD′k,J −
PDk,Jk
k

  X
(a) 1 ⊤ O 0 ⊤
= x
PD
Dk
e 1,J ⊗ · · · ⊗
1
2
k∈[K]
 O



D0k x
PD′k,J − PDk,Jk ⊗ · · · ⊗ PD
e K,J
k
K


1 ⊤ X  0⊤
0
D1 PD
= x
e 1,J D1 ⊗ · · · ⊗
1
2
k∈[K]

 ⊤
0
Dk (PD′k,J − PDk,Jk )D0k ⊗ · · · ⊗
k


0 ⊤
0
x,
DK PD
D
e K,J
K
K
 X 

0
D
PD
∆φ2 (D1:K ; D′1:K |σ) = w⊤
e 1,J
1 ⊗ ···⊗
1

k∈[K]





0
(PD′k,J − PDk,Jk )D0k ⊗ · · · ⊗ PD
D
x,
e K,J
K
k
K
 X
1
∆φ3 (D1:K ; D′1:K |σ) = w⊤
PD
e 1,J ⊗ · · · ⊗
1
2
k∈[K]



w,
PD′k,J − PDk,Jk ⊗ · · · ⊗ PD
e K,J
K
k
 X 

e + D0 ⊗ · · · ⊗
D
∆φ4 (D1:K ; D′1:K |σ) = −λσ ⊤
1
J
1,J1
k∈[K]





+
+
′+
0
0
e
(D k,Jk − Dk,Jk )Dk ⊗ · · · ⊗ DK,JK DK
x,
 X
e+ ⊗ ···⊗
D
∆φ5 (D1:K ; D′1:K |σ) = −λσ ⊤
J
1,J1
k∈[K]




+
+
′+
e
D k,Jk − Dk,Jk ⊗ · · · ⊗ DK,JK w, and

λ2 ⊤ X
′
∆φ6 (D1:K ; D1:K |σ) =
HD
σ
e 1,J ⊗ · · · ⊗
1
2 J
k∈[K]



σJ ,
HD′k,J − HDk,Jk ⊗ · · · ⊗ HD
e K,J
k

(59)

K

where (a) follows from Lemma 2 and analysis for deriva6
tion of {∆φi (D1:K ; D′1:K |σ)}i=2 are omitted due to space
′
constraints. Now, we set D = D0 and take the expectation
of ∆φy D1:K ; {D0k }|σ with respect to x and w. Since the
coefficient and noise vectors are uncorrelated,




E ∆φ2 D1:K ; D01:K |σ = E ∆φ5 D1:K ; D01:K |σ = 0.
We can restate the other terms as:

∆φ1 D1:K ; D01:K |σ


X  ⊤
(b) 1
0
0
= Tr xJ x⊤
D
D
P
e 1,J
1 ⊗ ···⊗
1
J
D
1
2
k∈[K]



 ⊤
⊤
0
,
D
D0k (Imk − PDk,Jk )D0k ⊗ · · · ⊗ D0K PD
e K,J
K
K

∆φ3 D1:K ; D01:K |σ
 X



1
PD
= Tr ww⊤
e 1,J ⊗ · · · ⊗ PD0k,J − PDk,Jk
1
k
2
k∈[K]

⊗ · · · ⊗ PD
,
e K,J
K

∆φ4 D1:K ; D01:K |σ

 X 

(c)
⊤
e + D01 ⊗ · · · ⊗
D
= −λ Tr xJ σ J
1,J1


k∈[K]

Isk −

0
D+
k,Jk Dk







0
e+
⊗ ···⊗ D
K,JK DK

 

, and

∆φ6 D1:K ; D01:K |σ
 X

λ2
=
HD
Tr σ J σ ⊤
e 1,J ⊗ · · · ⊗
J
1
2
k∈[K]



,
HD0k,J − HDk,Jk ⊗ · · · ⊗ HD
e K,J

(60)

K

k

where (b) and (c) follow from the facts that PD0k,J D0k = D0k
k

+

and D0 k,Jk D0k = Isk , respectively. Taking the expectation of
the terms in (60), we get


E ∆φ1 D1:K ; D01:K |σ
 X
i
h ⊤
2
(d) E{x }
0
Tr D01 PD
EJ
=
e 1,J D1 . . .
1
2
k∈[K]
h ⊤
i
h
i
0
0
0 ⊤
0
Tr Dk (Imk − PDk,Jk )Dk . . . Tr DK PD
e K,J DK
K

io
n h ⊤
E{x } X
0
=
...
EJ1 Tr D01 PD
e 1,J D1
1
2
k∈[K]
io
n h ⊤
EJk Tr D0k (Imk − PDk,Jk )D0k . . .
n h
io
⊤
0
EJK Tr D0K PD
D
,
e K,J
K
K

E{∆φ3 D1:K ; D01:K |σ }
  X
E{w2 }
=
PD
EJ Tr
e 1,J ⊗ · · · ⊗
1
2
2

k∈[K]

10




PD0k,J − PDk,Jk ⊗ · · · ⊗ PD
e K,J
K
k
 X
i
i
h
h
2
E{w }
=
. . . Tr PD0k,J − PDk,Jk
Tr PD
EJ
e 1,J
1
k
2
k∈[K]
h
i  (e)
. . . Tr PD
= 0,
e K,J
K


E ∆φ4 D1:K ; D01:K |σ
io
n h
X
e + D0 . . .
EJ1 Tr D
= −λE{|x|}
1,J1 1
k∈[K]

io
n h
n h
io
0
0
e+
,
EJk Tr Isk − D+
. . . EJK Tr D
K,JK DK
k,Jk Dk


E ∆φ6 D1:K ; D01:K |σ
io
n h
λ2 X
=
...
EJ1 Tr HD
e 1,J
1
2
k∈[K]
n h
io
io
n h
.
EJk Tr HD0k,J − HDk,Jk . . . EJK Tr HD
e K,J
K
k
(61)
where (d) follows from the relation Tr(A⊗B) = Tr[A] Tr[B]
[25] and (e) follows from the fact that PDk,Jk ’s are orthogonal
projections ionto subspaces of dimension sk and
h
Tr PD0k,J − PDk,Jk = sk − sk = 0. Adding the terms
k
in (61), we obtain the expression in (30).
Proof of Lemma 5: Equation (31) follows from RIP and
(32) follows from Gershgorin’s disk theorem [29].
Proof
of
Lemma
9:
To
lower
bound

∆φP D1:K ; D01:K |σ , we bound each term in (30) separately.
For the first term E ∆φ1 D1:K ; D01:K |σ , we have


io
n h ⊤
2
0
0
PD
.
= EJk
EJk Tr D0k PD
e k,J Dk,Jk
e k,J Dk
F

k

k

(62)

e k = D0 , then
If D
k

PD0k,J D0k,Jk
EJk
k

2
F



(a)

=

sk
D0k
pk

2
F

= sk ,

(63)

F

=

sk
Dk C−1
k
pk

2 (d)
=
F

≥



sk Bk2
sk
,
kθk k22 1 −
pk
p k 1 − δk

pk
(e) s
1
sk X
k
≥
p k = sk ,
2
pk j=1 cos (θ(k,j) )
pk

where (b) is a direct consequence of Lemma 8; we can
write D0k = Dk C−1
k − Vk Tk where Ck = Diag (cos(θ k )),
Tk = Diag (tan(θk )), and PDk,Jk D0k,Jk = [Dk C−1
k ]Jk and
θk,j denotes the angle between dk,j and d0k,j . Moreover, (c)
follows from [19, Lemma 15], (d) follows from the fact that
kdk,j k2 = 1, and (e) follows from the fact that cos(θk,j ) < 1.
Similarly, we have
io
n h ⊤
EJk Tr D0k (Imk − PDk,Jk )D0k


2
(Imk − PDk,Jk )D0k,Jk
= EJk
F

(64)

where (f) follows from similar arguments as in Gribonval et
al. [19, Equation (72)]. Putting it all together, we have


E ∆φ1 D1:K ; D01:K |σ

 Y 

E{x2 } X
sk Bk2
sk
≥
si
kθk k22 1 −
2
pk
p k 1 − δk
k∈[K]

=

sE{x2 } X
2

i∈[K]
i6=k
kθk k22

k∈[K]

pk



sk Bk2
1−
.
p k 1 − δk

(65)



Next, to lower bound E ∆φ4 D1:K ; D01:K |σ , we upper


e k = D0 , we have
bound E ∆φ4 D1:K ; D01:K |σ . If D
k
n h +
io
= EJk {Tr [Isk ]} = sk , (66)
EJk Tr D0 k,Jk D0k,Jk
e k = Dk , we get
otherwise, if D

 
EJk Tr Dk,Jk + D0k
n
o
(g)
0
D+
≤ sk EJk
k,Jk Dk,Jk
2
o
n
+
0
≤ sk EJk kDk,Jk k2 kDk,Jk k2
!

q
(h)
1
0
≤ sk p
1 + δsk (Dk )
1 − δsk (Dk )
r
(i)
1 + δk
,
(67)
≤ sk
1 − δk

where (g) follows from the fact that for a square matrix A ∈
Rq×q , Tr [A] ≤ qkAk2 , (h) follows from (31) and (33) and
(i) follows from (38). Similar to [19, equation (73)], we also
have
n 
o
0
EJk Tr Isk − D+
k,Jk Dk
sk kθk k22
s2 Ak Bk
kθk k2 .
+ k2
pk 2
p k 1 − δk
r
Q
1 + δi
Thus, defining δ−k , i∈[K]
, we have
1 − δi
i6=k


E ∆φ4 D1:K ; D01:K |σ
 Y 
X
si
δ−k
≥ −λE{|x|}
≤

e k = Dk , then
where (a) follows from [19, Lemma 15]. If D


n
o
2
(b)
2
PDk,Jk D0k,Jk
[Dk C−1
EJk
= EJk
k ]Jk F
(c)

(f )

k∈[K]

(68)

i∈[K]
i6=k


sk kθk k22
s2 Ak Bk
kθk k2
+ k2
pk 2
p k 1 − δk

X δ−k  kθk k2
sk Ak Bk
2
= −λsE{|x|}
kθk k2 .
+
pk
2
p k 1 − δk


k∈[K]

(69)



e k , we
To lower bound E ∆φ6 D1:K ; D01:K |σ , for any D
have
o (j) s
n
io
n h
k
≤
≤ EJk sk HD
EJk Tr HD
,
e k,J
e k,J
k 2
k
1 − δk
(70)

11

where (j) follows from (33) and (38). Similar to Gribonval et
al. [19, equation (74)], we also have
io
n h
s2 4Ak Bk
≤ k2
EJk Tr HD0k,J − HDk,Jk
kθk k2 .
k
pk (1 − δk )2
Thus, we get


E{∆φ6 D1:K ; D01:K |σ }

 Y
 2
si
sk 4Ak Bk
λ2 X
kθ
k
≥−
k 2
2
1 − δi
p2k (1 − δk )2
i∈[K]
i6=k

k∈[K]

=−


 Y

λ2 s X 1
1
sk 4Ak Bk
kθk k2 .
2
pk
1 − δi
p k 1 − δk
k∈[K]

i∈[K]

(71)

Adding (65), (69), and (71), we get (39).
Proof of Proposition
1:
To ensure that

∆φP D1:K ; D01:K |σ > 0, we show that the right hand side
of (39) is positive. First, we ensure the conditions in (34) and
(38) hold for Lemma 6 and Lemma 9, respectively. We set
1
1
1
and δsk (D0k ) = , for k ∈ [K]. For
δk = , δsk (Dk ) =
2
2
4
rk ≤ 0.15, this ensures:
q
p
1 − δsk (D0k ) ≥ 1 − δsk (Dk ) − rk

max δsk (D0k ), δsk (Dk ) ≤ δk ,
(72)

and implies δk < 1 (condition for Lemmas 4 and 7). First, we
find conditions that guarantee:
 (K−1)/2
3
2Bk2 sk
1
sk Bk2
2
2
+ λ̄κx δ−k =
+ λ̄κx
≤ .
p k 1 − δk
pk
2
2
(73)
1
sk
1
≤
and λ̄κ2x ≤
, (73) is
2
(K−1)/2
pk
8Bk
8(1.5)
satisfied.8 Consequently, we have

 sE{x2 } X kθk k2
∆φP D1:K ; D01:K |σ ≥
kθk k2
4
pk
k∈[K]


  (K−1)/2
sk
3
+ 2(K+1) λ̄ λ̄κ2x Ak Bk . (74)
−8
2
pk

If we take

From [19, proposition 2 proof], we use the following relations:
Bk ≤ Bk0 + rk ≤ Bk0 + 1,

Ak ≤ A0k + 2Bk rk ,

⊤

where A0k , D0k D0k − Ipk

F

and Bk0 , D0k

k ∈ [K],
(75)
2

and (75)

follows
from matrix norminequalities [19]. Defining γk ,

B 2 sk
16 1.5(K−1)/2 + 2(K+1) λ̄ λ̄κ2x k
for k ∈ [K] and using
pk
κ2x ≤ 1, we have


  (K−1)/2
2(K+1)
1
3
+
γk ≤ 2
2
8(1.5)(K−1)/2
8(1.5)(K−1)/2


1
8
1
≤2
+
(76)
≤ .
8 64
2
8 These

numbers are chosen for a simplified proof and can be modified.

Furthermore, for Dk ∈ Srk (D0k ), k ∈ [K], we get

∆φP D1:K ; D01:K |σ


(a) sE{x2 } X r
γk Ak
k
rk −
≥
4
pk
2 Bk
k∈[K]


(b) sE{x2 } X r
γk A0k + 2Bk rk
k
≥
rk −
4
pk
2
Bk
k∈[K]


sE{x2 } X rk
γk A0k
≥
rk (1 − γk ) −
4
pk
2 Bk
k∈[K]


(c) sE{x2 } X r
A0
k
rk − γk k ,
(77)
≥
8
pk
Bk
k∈[K]

where (a) follows from (37), (b) follows from (75), and (c)
follows from (76). Hence, we can write

 sE{x2 } X rk
rk − rk,min (λ̄) ,
∆φP D1:K ; D01:K |σ ≥
8
pk
k∈[K]

(78)

where we define
A0
rk,min (λ̄) , γk k
Bk


sk
(K−1)/2
(K+1)
= 16 1.5
+2
λ̄ λ̄κ2x A0k Bk
pk


2
(K−1)/2
(K+1)
√
1.5
+2
λ̄ λ̄Ck,min , (79)
=
3(2/ 1.5)K−1
and Ck,min is defined in (13). The lower bound in (78)
holds for any rk ≤ 0.15 and Dk ∈ Srk (D0k ), k ∈ [K].
K−1

2
3
√
,
Finally, since 1.5(K−1)/2 + 2(K+1) λ̄ ≤
2
1.5
the assumption λ̄ ≤ 0.15/(maxk∈[K] Ck,min ) implies
that

rk,min (λ̄) ≤ 0.15. Therefore, ∆φP D1:K ; D01:K |σ > 0 for
all rk ∈ (rk,min (λ̄), 0.15], k ∈ [K].
Proof of Lemma 11: Considering j 6∈ J , associated with
(j1 , . . . , jk ) 6∈ (J1 × · · · × JK ), we have

kD⊤
J dj k 1
(a)

⊤

⊤

≤ kD0J d0j k1 + kD0J (dj − d0j )k1 + k(DJ − D0J )⊤ dj k1
i
√ h
⊤
≤ µs (D0 ) + s kD0J (dj − d0j )k2 + k(DJ − D0J )⊤ dj k2
 O
O

√
⊤
0
dk,Jk − d0k,Jk
≤ µs (D ) + s
D0k,Jk
2
2

O
O
+
Dk,Jk −
D0k,Jk kdj k2
2
 Y q

(b)
√
≤ µs (D0 ) + s
1 + δsk (D0k )
 X

k∈[K]

+

X

k∈[K]

k∈[K]

e 1,j
d
1

e 1,J
D
1

. . . dk,Jk −

d0k,Jk 2

. . . Dk,Jk −

D0k,Jk 2

2

2

...
...

e k,J
d
k

e k,J
D
k

2



2



12

(c)

≤ µs (D0 ) +
+

√
s

 Y q
 X 
rk
1 + µsk −1 (D0k )

X  Y

k∈[K]

i∈[K]
i6=k

k∈[K]

e i,Ji
D

2

k∈[K]

 
rk

APPENDIX

 X 
0
K/2 √
≤ µs (D ) + 2(1.5)
rk ,
s

(d)

N
b is almost
ky − ( Dk ) x′ k2 . Thus, according to LemmaN
10, x
1
′
ky
−
(
D
surely the unique solution of min
k ) xk2 +
x
2

0
0
′
λkx k1 and ∆φP D1:K , D1:K |σ = ∆fP D1:K , D1:K .

(80)

k∈[K]

where (a) follows from the triangle inequality, (b) follows from
(25) and the definition of RIP, (c) follows from (32), and, (d)
follows from substituting the value from (44) for µsi −1 (D0i ).
e i = Di , according to (75), we have kDi,Ji k ≤
For D
2
q
p
D0i,Ji 2 + ri ≤ 1 + µsi −1 (D0i ) + ri ≤ 32 + 0.15 < 1.5.
Proof of Proposition 2: We follow a similar approach to
Gibonval et al. [19]. To ensure the conditions in (43) hold for
Lemma 10, we have

O
y−
Dk x′
2

O
O
≤
D0k,Jk −
Dk,Jk x′J + kwk2
2
X

e 1,J ⊗ · · · ⊗ D0
D
≤ Mx
1
k,Jk − Dk,Jk ⊗ · · · ⊗
k∈[K]

e K,J
D
+ Mw
K
X 2
e 1,J1 . . . D0
D
≤ Mx
k,Jk − Dk,Jk
k∈[K]

+ Mw
X  Y
≤ Mx
k∈[K]

(a)

2

2

i∈[K]
i6=k

≤ (1.5)(K−1)/2 Mx

e i,Ji
D

X

2



e K,JK
... D

rk + Mw

rk + Mw ,

(81)

k∈[K]

where (a) follows from (40) and the fact that
D0i,Ji

2

+ ri < 1.5. Hence, we get

O
λ(1 − 2µs (D)) − y −
Dk x′
2

(K−1)/2

≥ λ(1 − 2µs (D)) − (1.5)

e i,Ji
D

2

k∈[K]

rk − Mw

k∈[K]

≥ λ(1 − 2µs (D0 )) − 3(1.5)K/2 Mx
K/2

= 3(1.5)

1 X
hn (D1:K ) − hn (D′1:K )
N2
n∈[N ]
2
 X
(a) 1
Lk kDk − D′k kF
≤
N

X

k∈[K]

rk − Mw


X 
rk − Mw ,
Mx K λ̄Cmax −

(82)

k∈[K]

where
from (45) and (c) follows from (43)
√ (b) follows
√
(2λ s ≤ xmin s ≤ Mx ) and (45). If rk < Cmax λ̄, k ∈ [K],
the assumption on the noise level in (42) implies that the righthand side of (82) is greater than zero and λ(1 − 2µs (D)) >

2

=

k∈[K]

K X 2
Lk kDk − D′k k2F
≤
N
k∈[K]
o
n
2
,
= E CD1:K − CD′1:K

(b)

(83)

where (a) follows from coordinate Lipschitz continuity of
h and (b) follows from Cauchy-Schwartz inequality. Hence,
using Slepian’s Lemma [30], we get




sup
AD1:K ≤ E
CD1:K
E
sup
Dk ∈Brk (D0k )
k∈[K]

≤

 √

≥ λ(1 − 2µs (D0 )) − (1.5)K/2 4λ s + (1.5)−1/2 Mx
X
rk − Mw

(c)

[pk ]’s are independent standard Gaussian vectors. We have
o
n
2
E AD1:K − AD′1:K

=

2

Mx

(b)

Proof
of
Lemma
13:
According
to
Lemma
12,
we
have
to
upper
bound
o
n
P
E supDk ∈Br (D0 ),k∈[K] N1 n∈[N ] βn hn (D1:K ) .
k
k
Conditioned on the draw of functions P
h1 , . . . , hN , consider
the Gaussian processes AD1:K = N1 n∈[N ] βn hn (D1:K )

q P
P
P
K
k
and CD1:K =
i∈[mk ]
j∈[pk ] ζij (Dk −
k∈[K] Lk
N

 k
D0k )ij , where {βn }N
n=1 ’s and ζij , k ∈ [K], i ∈ [mk ], j ∈

=
X

B

(

r

r

Dk ∈Brk (D0k )
k∈[K]

K
N

 X

k∈[K]


K X
N

k∈[K]

supDk ∈Br (D0k ) N1
k
k∈[K]

Thus, we obtain E
q P
√
≤2 K
k∈[K] Lk rk mk pk .
N


Lk rk E kζ k kF


√
Lk rk mk pk .



(84)

P

n∈[N ]

βn hn (D1:K )

)


Proof of Lemma 14: We expand ∆φy D1:K ; D01:K |σ
according to (59) and bound each term separately. Looking at
the first term

 (a) 1 ⊤ 0 ⊤ X
0
∆φ1 D1:K ; D1:K |σ = x D
PD
e 1,J ⊗ · · · ⊗
1
2
k∈[K]



D0 x
PD′k,J − PDk,Jk ⊗ · · · ⊗ PD
e K,J
K
k
 X
 Y
(b) 1
2
2
0
PD0k,J − PDk,Jk
Dk,Jk 2
≤ kxk2
k
2
2
k∈[K]

k∈[K]

13

 Y

PD
e i,J

2

i

i∈[K]
i6=k

(c)

≤ Mx2

 Y

k∈[K]

 X

k∈[K]




1 + δsk (D0k )
−1/2

(1 − δk )



kDk −

D0k kF


,

(85)

where (a) follows from (59), (b) follows from the fact that
Q
D0J 2 = k∈[K] D0k,Jk , and (d) follows from the defi2
nition of RIP and equation (35). Following a similar approach
and expanding the rest of the terms, we get
 Y

 12
 (d)
0
0
1 + δsk (Dk )
∆φ2 D1:K ; D1:K |σ ≤ 2Mw Mx
 X

k∈[K]

k∈[K]


−1/2
0
(1 − δk )
kDk − Dk kF ,


∆φ3 D1:K ; D01:K |σ
X

2
−1/2
0
≤ Mw
(1 − δk )
kDk − Dk kF ,
k

∆φ4 D1:K ; D01:K |σ

 Y
(e)
1/2
√
≤ 2λ sMx
1 + δsk (D0k )

 X

k∈[K]

k∈[K]

(1 − δk )−1


Y

i∈K
i6=k



(1 − δi )−1/2 kDk − D0k kF ,

√
∆φ5 D1:K ; D01:K |σ ≤ 2λ sMw
Y


 X
−1
0
−1/2
(1 − δk )
kDk − Dk kF ,
(1 − δi )
k∈[K]



i∈K
i6=k

∆φ6 D1:K ; D01:K |σ
Y


 X
(f )
(1 − δk )−3/2
≤ λ2 s
(1 − δi )−1 kDk − D0k kF ,
i∈K
i6=k

k∈[K]

where (e) and (f) follow from (33) and (35). Adding all the
terms together, we get
X

Lk kDk − D0k kF . (86)
∆φy D1:K ; D01:K |σ ≤
k∈[K]

where Lk is defined in (53).

R EFERENCES
[1] Z. Shakeri, A. D. Sarwate, and W. U. Bajwa, “Identification of
Kronecker-structured dictionaries: An asymptotic analysis,” in Proc.7th
Intl. Workshop Computational Advances in Multi-Sensor Adaptive Processing, December 2017.
[2] A. Smilde, R. Bro, and P. Geladi, Multi-way analysis: Applications in
the chemical sciences. John Wiley & Sons, 2005.
[3] T. G. Kolda and B. W. Bader, “Tensor decompositions and applications,”
SIAM Review, vol. 51, no. 3, pp. 455–500, 2009.
[4] R. A. Harshman, “Foundations of the PARAFAC procedure: Models
and conditions for an explanatory multi-modal factor analysis,” UCLA
Working Papers in Phonetics, vol. 16, pp. 1–84, December 1970.
[5] L. R. Tucker, “Implications of factor analysis of three-way matrices for
measurement of change,” Problems in Measuring Change, pp. 122–137,
1963.

[6] M. Aharon, M. Elad, and A. Bruckstein, “K-SVD: An algorithm for
designing overcomplete dictionaries for sparse representation,” IEEE
Trans. Signal Process., vol. 54, no. 11, pp. 4311–4322, November 2006.
[7] M. F. Duarte and R. G. Baraniuk, “Kronecker compressive sensing,”
IEEE Trans. Image Process., vol. 21, no. 2, pp. 494–504, Febuary 2012.
[8] S. Hawe, M. Seibert, and M. Kleinsteuber, “Separable dictionary learning,” in Proc. IEEE Conf. Comput. Vision and Pattern Recognition
(CVPR), June 2013, pp. 438–445.
[9] S. Zubair and W. Wang, “Tensor dictionary learning with sparse Tucker
decomposition,” in Proc. IEEE 18th Int. Conf. Digital Signal Process.
(DSP), July 2013, pp. 1–6.
[10] F. Roemer, G. Del Galdo, and M. Haardt, “Tensor-based algorithms for
learning multidimensional separable dictionaries,” in Proc. IEEE Int.
Conf. Acoustics, Speech and Signal Process., May 2014, pp. 3963–3967.
[11] C. F. Dantas, M. N. da Costa, and R. da Rocha Lopes, “Learning
dictionaries as a sum of Kronecker products,” IEEE Signal Processing
Letters, vol. 24, no. 5, pp. 559–563, March 2017.
[12] M. Ghassemi, Z. Shakeri, A. D. Sarwate, and W. U. Bajwa, “STARK:
Structured dictionary learning through rank-one tensor recovery,” in
Proc. 7th Intl. Workshop Computational Advances in Multi-Sensor
Adaptive Processing, December 2017.
[13] M. Aharon, M. Elad, and A. M. Bruckstein, “On the uniqueness of
overcomplete dictionaries, and a practical way to retrieve them,” Linear
Algebra and its Applicat., vol. 416, no. 1, pp. 48–67, July 2006.
[14] A. Agarwal, A. Anandkumar, P. Jain, P. Netrapalli, and R. Tandon,
“Learning sparsely used overcomplete dictionaries,” in Proc. 27th Annu.
Conf. Learning Theory, ser. JMLR: Workshop and Conf. Proc., vol. 35,
no. 1, 2014, pp. 1–15.
[15] A. Agarwal, A. Anandkumar, and P. Netrapalli, “A clustering approach
to learn sparsely-used overcomplete dictionaries,” IEEE Trans. Inf.
Theory, vol. 63, no. 1, pp. 575–592, January 2017.
[16] S. Arora, R. Ge, and A. Moitra, “New algorithms for learning incoherent
and overcomplete dictionaries,” in Proc. 25th Annu. Conf. Learning
Theory, ser. JMLR: Workshop and Conf. Proc., vol. 35, 2014, pp. 1–28.
[17] K. Schnass, “On the identifiability of overcomplete dictionaries via the
minimisation principle underlying K-SVD,” Appl. and Computational
Harmonic Anal., vol. 37, no. 3, pp. 464–491, November 2014.
[18] ——, “Local identification of overcomplete dictionaries,” J. Machine
Learning Research, vol. 16, pp. 1211–1242, June 2015.
[19] R. Gribonval, R. Jenatton, and F. Bach, “Sparse and spurious: Dictionary
learning with noise and outliers,” IEEE Trans. Inf. Theory, vol. 61,
no. 11, pp. 6298–6319, November 2015.
[20] A. Jung, Y. C. Eldar, and N. Görtz, “On the minimax risk of dictionary
learning,” IEEE Trans. Inf. Theory, vol. 62, no. 3, pp. 1501–1515, March
2015.
[21] Z. Shakeri, W. U. Bajwa, and A. D. Sarwate, “Minimax lower bounds
for Kronecker-structured dictionary learning,” in Proc. 2016 IEEE Int.
Symp. Inf. Theory, July 2016, pp. 1148–1152.
[22] ——, “Sample complexity bounds for dictionary learning of tensor data,”
in IEEE Int. Conf. Acoustics, Speech and Signal Process., March 2017,
pp. 4501–4505.
[23] ——, “Minimax lower bounds on dictionary learning for tensor data,”
arXiv preprint arXiv:1608.02792, August 2016.
[24] C. F. Caiafa and A. Cichocki, “Computing sparse representations of
multidimensional signals using Kronecker bases,” Neural Computation,
vol. 25, no. 1, pp. 186–220, January 2013.
[25] R. A. Horn and C. R. Johnson, Topics in matrix analysis. Cambridge
University Press, 1991.
[26] E. J. Candes, “The restricted isometry property and its implications for
compressed sensing,” Comptes Rendus Mathematique, vol. 346, no. 910, pp. 589–592, 2008.
[27] S. Jokar and V. Mehrmann, “Sparse solutions to underdetermined
Kronecker product systems,” Linear Algebra and its Applicat., vol. 431,
no. 12, pp. 2437–2447, December 2009.
[28] R. Gribonval, R. Jenatton, F. Bach, M. Kleinsteuber, and M. Seibert,
“Sample complexity of dictionary learning and other matrix factorizations,” IEEE Trans. Inf. Theory, vol. 61, no. 6, pp. 3469–3486, June
2015.
[29] G. H. Golub and C. F. Van Loan, Matrix computations. JHU Press,
2012, vol. 3.
[30] P. Massart, Concentration inequalities and model selection. Springer,
2007, vol. 6.

