Proceedings of Machine Learning Research vol 75:1–15, 2018

Stable recovery of deep linear networks under sparsity constraints

arXiv:1706.00342v2 [math.OC] 20 Feb 2018

François Malgouyres

MALGOUYRES @ MATH . UNIV- TOULOUSE . FR

Institut de Mathématiques de Toulouse ; UMR5219
Université de Toulouse ; CNRS
UPS IMT F-31062 Toulouse Cedex 9, France Address 1
Joseph Landsberg
Department of Mathematics
Mailstop 3368
Texas A& M University

JML @ MATH . TAMU . EDU

Abstract
We study a deep linear network expressed under the form of a matrix factorization problem. It
takes as input a matrix X obtained by multiplying K matrices (called factors and corresponding
to the action of a layer). Each factor is obtained by applying a fixed linear operator to a vector of
parameters satisfying a sparsity constraint. In machine learning, the error between the product of
the estimated factors and X (i.e. the reconstruction error) relates to the statistical risk. The stable
recovery of the parameters defining the factors is required in order to interpret the factors and the
intermediate layers of the network.
In this paper, we provide sharp conditions on the network topology under which the error on the
parameters defining the factors (i.e. the stability of the recovered parameters) scales linearly with
the reconstruction error (i.e. the risk). Therefore, under these conditions on the network topology,
any successful learning tasks leads to robust and therefore interpretable layers.
The analysis is based on the recently proposed Tensorial Lifting. The particularity of this
paper is to consider a sparse prior. As an illustration, we detail the analysis and provide sharp
guarantees for the stable recovery of convolutional linear network under sparsity prior. As expected,
the condition are rather strong.
Keywords: Stable recovery, deep linear networks, convolutional linear networks, feature robustess.

1. Introduction
Let K ∈ N∗ , m1 . . . mK+1 ∈ N, write m1 = m, mK+1 = n. We impose the factors to be structured
matrices defined by a number S of unknown parameters. More precisely, for k = 1 . . . K, let
Mk : RS

−→ Rmk ×mk+1 ,

h 7−→ Mk (h)

be a linear map. We assume that we know the matrix X ∈ Rm×n which is provided by
X = M1 (h1 ) · · · MK (hK ) + e,

(1)

for an unknown error term e, such that kek ≤ δ, and parameters h = (hk )k=1..K ∈ RS×K .
Moreover, considering a family of possible supports M (e.g., all the supports of size S ′ , for a
c 2018 J. Landsberg.

given S ′ ≤ S), we assume that theh satisfy a sparsity constraint
of the form : there exists S =

(S k )k=1..K ∈ M such that supp h ⊂ S (i.e.: ∀k, supp hk ⊂ S k ).
This work investigates necessary and sufficient conditions imposed on the constituents of (1) for
which we can (up to obvious scale rearrangement) stably recover the parameters h from X. Beside
such that
these conditions, we assume that we have a way to find S ∗ ∈ M and h∗ ∈ RS×K
S∗
η = kM1 (h∗1 ) . . . MK (h∗K ) − Xk

, is small.

(2)

As we will discuss later, at the writing, the success of algorithms for constructing h∗ is mostly
supported by empirical evidence and lack theoretical justifications. These aspects of the problem
are out of the scope of the present paper. However, in machine learning problems, the reconstruction
error η represents the risk. There is therefore no point in analyzing the properties of h∗ , if η is large.
The established upper-bound on the recovery error of the parameters linearly depends on δ + η.
Therefore, when the learning algorithm is successful (i.e. the sum of the risk η and noise δ is
sufficiently small), if the deep linear network satisfies the conditions established in this paper the
estimation of the parameters is stable. The latter property is required if one wants to interpret the
features provided by the machine learning algorithm. That is the main interest of the proposed
analysis. Notice that we also establish that the conditions are sharp.
Also, the study considers deep linear networks instead of deep neural networks. As can be
deduced from Eldan and Shamir (2016), this significantly diminishes the expressiveness of the network. The main argument for studying deep linear networks (as is done in the present paper)
comes from a remark in Safran and Shamir (2016). For the rectified linear unit activation function
(ReLU)1 , between each layer every entry is multiplied by an element of the discrete set {0, 1}. As a
consequence, the parameter space RS×K can be partitioned into subsets such that, on every subset,
the action of the non-linear network is the same deep linear network (i.e. the activation function has
a constant action when h varies in the subset). Therefore, the objective function optimized in deep
learning is made of pieces and on every piece it is the objective function of a deep linear network.
As a consequence, properties of the objective function for deep neural networks generalize properties of the objective function for deep linear networks. Restricting the analysis to linear networks is
legitimate as a step towards the study of deep neural networks.
Notice, that the authors of Choromanska et al. (2015a,b); Kawaguchi (2016) use a different
argument but also end-up studying deep linear networks. The simplifying assumption assumes the
independence of the activation to the input. Taking the expectation then leads to linear networks
that the authors analyse. As explained by the same authors in Choromanska et al. (2015b), this is
however a moderatly convincing argument. We prefer to say clearly that we consider deep linear
networks.
Finally, S ∗ and h∗ are typically found by an algorithm (most often a heuristic) that tries to lower
kM1 (h1 ) . . . MK (hK ) − Xk2

(3)

while avoiding overfit. A classical strategy is the dropout of Srivastava et al. (2014). This is perfectly compatible with the assumption (2). However, even if we ignore the overfit issue and restrict
the analysis to the minimization of (3), we see that it is non-convex. Again, we do not address this
minimization issue but there is significant empirical evidence suggesting that (3) can be minimized
efficiently in a surprisingly large number of situations. Despite an increasing theoretical activity
1. ReLU is the most common activation function.

2

S TABLE

RECOVERY OF DEEP LINEAR NETWORKS UNDER SPARSITY CONSTRAINTS

related to that question the theory explaining this phenomenon is still far from satisfactory when
K ≥ 3 (see Livni et al. (2014); Haeffele and Vidal (2015); Kawaguchi (2016); Choromanska et al.
(2015a,b); Safran and Shamir (2016) ).
The approach developed in this paper extends to K ≥ 3 existing results for K ≤ 2. In particular,
when K = 1, the considered problems boils down to a compressed sensing problem Elad (2010).
When K = 2 and when extended to other constraints on the parameters h, the statements apply
to already studied problems such as: low rank approximation Candes et al. (2013), Non-negative
matrix factorization Lee and Seung (1999); Donoho and Stodden (2003); Laurberg et al. (2008);
Arora et al. (2012), dictionary learning Jenatton et al. (2012), phase retrieval Candes et al. (2013),
blind deconvolution Ahmed et al. (2014); Choudhary and Mitra (2014); Li et al. (2016). Most of
these papers use the same lifting property we are using. They further propose to convexify the problem. A more general bilinear framework is considered in Choudhary and Mitra (2014). The only
existing statements when K ≥ 3 are very recent Malgouyres and Landsberg (2017). They are also
applied to deep linear networks but do not include sparsity constraint.
The present work describes an alternative analysis, specialized to sparsity constraints, of the
results exposed in Malgouyres and Landsberg (2017). Doing so, we obtain better bounds (defined
with an analogue of the lower-RIP) and weaker constraints on the model. Its application to sparse
convolutional linear networks leads to simple necessary and sufficient conditions of stable recovery,
for a large class of solvers. The stability inequality (see Theorem 5) only involves explicit and
simple ingredients of the problem. The condition on the network topology is rather strong but
takes an simple format. Implementing a test checking if the condition is met is easy and the test
only requires to apply the networks as many times as the network has leaves, for every couple of
supports.

2. Notations and preliminaries on Tensorial Lifting
= {h ∈ RS×K , ∀k = 1..K, khk k =
6 0}. Define an equivalence
Set NK = {1, . . . , K} and RS×K
∗
S×K
S×K
, h ∼ g if and only if there exists (λk )k=1..K ∈ RK such
relation in R∗ : for any h, g ∈ R
that
K
Y
λk = 1
and
∀k = 1..K, hk = λk gk .
k=1

Denote the equivalence class of h ∈ RS×K
by [h]. For any p ∈ [1,∞], we denote the usual ℓp norm
∗
S×K
by k.kp and define the mapping dp : (R∗ / ∼) × (RS×K
/ ∼) → R by
∗
dp ([h], [g]) =

inf

S×K
h′ ∈[h]∩Rdiag

kh′ − g′ kp

,
, ∀h, g ∈ RS×K
∗

(4)

S×K
g′ ∈[g]∩Rdiag

where
RS×K
= {h ∈ RS×K
, ∀k = 1..K, khk k∞ = kh1 k∞ }.
diag
∗

/ ∼.
It is proved in Malgouyres and Landsberg (2017) that dp is a metric on RS×K
∗
The real valued tensors of order K whose axes are of size S are denoted by T ∈ RS×...×S . The
K
K
space of tensors is abbreviated RS . We say that a tensor T ∈ RS is of rank 1 if and only if there
exists a collection of vectors h ∈ RS×K such that, for any i = (i1 , . . . , iK ) ∈ NK
S,
Ti = h1,i1 . . . hK,iK .
3

The set of all the tensors of rank 1 is denoted by Σ1 . Moreover, we parametrize Σ1 ⊂ RS
the Segre embedding

K

using

K

P : RS×K −→ Σ1 ⊂ RS
h 7−→ (h1,i1 h2,i2 . . . hK,iK )i∈NK

(5)

S

As stated in the two next theorems, we can control the distortion of the distance induced by P
and its inverse.
Theorem 1 Stability of [h] from P (h), see Malgouyres and Landsberg (2017)
Let h and g ∈ RS×K
be such that kP (g) − P (h)k∞ ≤ 21 max (kP (h)k∞ , kP (g)k∞ ). For all
∗
p, q ∈ [1, ∞],


1
1
1
−1
−1
K
K
, kP (g)k∞
kP (h) − P (g)kq .
(6)
dp ([h], [g]) ≤ 7(KS) p min kP (h)k∞
Theorem 2 Lipschitz continuity of P , see Malgouyres and Landsberg (2017)
We have for any q ∈ [1, ∞] and any h and g ∈ RS×K
,
∗


1
1
K−1
1
1− K
1− K
1−
kP (h) − P (g)kq ≤ S q K q max kP (h)k∞ , kP (g)k∞
dq ([h], [g]).

(7)

The Tensorial Lifting (see Malgouyres and Landsberg (2017)) states that there exists a unique
linear map
K
A : RS −→ Rm×n ,
such that for all h ∈ RS×K

M1 (h1 )M2 (h2 ) . . . MK (hK ) = AP (h).

(8)

The intuition leading to this equality is that every entry in M1 (h1 )M2 (h2 ) . . . MK (hK ) is a multivariate polynomial whose variables are in h. Moreover, every monomial of the polynomials is
of the form ai P (h)i for i ∈ NK
S , where ai is a coefficient depending on M1 , . . . , MK . The great
property of the Tensorial Lifting is to express any deep linear network using the Segre Embedding
and a linear operator A. The Segre embedding is non-linear and might seem difficult to deal with at
the first sight, but it is always the same whatever the network topology, the sparsity pattern, the action of the ReLU activation function. . . These constituents of the problem only influence the lifting
linear operator A.
In the next section, we study what properties of A are required to obtain the stable recovery. In
Section 4, we study these properties when A corresponds to a sparse convolutional linear network.

3. General conditions for the stable recovery under sparsity constraint
From now on, the analysis differs from the one presented in Malgouyres and Landsberg (2017). It is
dedicated to models that enforce sparsity. In this particular situation, we can indeed have a different
view of the geometry of the problem. In order to describe it, we first establish some notation.

4

S TABLE

RECOVERY OF DEEP LINEAR NETWORKS UNDER SPARSITY CONSTRAINTS

We define a support by S = (Sk )k=1..K , with Sk ⊂ NS , and denote the set of all supports by
K
K
P(NK
S ) (the parts of NS ). For a given support S ∈ P(NS ), we denote
= {h ∈ RS×K | hk,i = 0, for all k = 1..K and i 6∈ Sk }
RS×K
S
(i.e., for all k, supp (hk ) ⊂ Sk ) and
RSS

K

K

= {T ∈ RS | Ti = 0, if ∃k = 1..K, such that ik 6∈ Sk }.
K

K

We also denote by PS the orthogonal projection from RS onto RSS . We trivially have for all
K
T ∈ RS and all i ∈ NK
S

Ti , if i ∈ S,
(PS T )i =
0 , otherwise.
As explained in the introduction, we assume that there exists a known family of admissible
S×K
supports M ⊂ P(NK
that we
S ), an unknown support S ∈ M and unknown parameters h ∈ RS
would like to estimate from the noisy matrix product
X = M1 (h1 ) . . . MK (hK ) + e.

(9)

We assume that there exists δ ≥ 0 such that the error satisfies
kek ≤ δ.

(10)

Also, we consider an inexact minimization and assume that we have a way to find S ∗ ∈ M and
h∗ ∈ RS×K
S∗
η = kM1 (h∗1 ) . . . MK (h∗K ) − Xk
is small.
We remind that, in machine learning problems, η represents the risk.
In the geometrical view described in the sequel, we consider different linear operators AS , with
S×K
S ∈ P(NK
S ), such that for all h ∈ RS
AS P (h) = M1 (h1 ) . . . MK (hK ).
In order to achieve that, considering (8), we simply define for any S ∈ P(NK
S)
AS = APS .

(11)

The following property will turn out to be necessary and sufficient to guarantee the stable recovery property.
Definition 1 Deep-M-Null Space Property
Let γ ≥ 1 and ρ > 0, we say that A satisfies the deep-M-Null Space Property (deep-M-NSP )
)+P (RS×K
) satisfying
with constants (γ, ρ) if and only if for all S and S ′ ∈ M, any T ∈ P (RS×K
S
S′
′
kAS∪S ′ T k ≤ ρ and any T ∈ Ker (AS∪S ′ ), we have
kT k ≤ γkT − PS∪S ′ T ′ k.

5

(12)

)+
Geometrically, the deep-M-NSP does not hold when PS∪S ′ Ker (AS∪S ′ ) intersects P (RS×K
S
P (RS×K
)
away
from
the
origin
or
tangentially
at
0.
It
holds
when
the
two
sets
intersect
”transverS′
sally” at 0. Despite an apparent abstract nature, we will be able to characterize precisely when
the lifting operator corresponding to a convolutional linear network satisfies the deep-M-NSP (see
Section 4). We will also be able to calculate the constants (γ, ρ).
Proposition 1 Sufficient condition for deep-M-NSP
K
If Ker (A) ∩ RSS∪S ′ = {0}, for all S and S ′ ∈ M, then A satisfies the deep-M-NSP with
constants (γ, ρ) = (1, +∞).
Proof In order to prove the proposition, let us consider S and S ′ ∈ M, T ′ ∈ Ker (AS∪S ′ ). We have
K
APS∪S ′ T ′ = 0 and therefore PS∪S ′ T ′ ∈ Ker (A). Moreover, by definition, PS∪S ′ T ′ ∈ RSS∪S ′ .
Therefore, applying the hypothesis of the proposition, we obtain PS∪S ′ T ′ = 0 and (12) holds for
any T , when γ = 1. Therefore, A satisfies the deep-M-NSP with constants (γ, ρ) = (1, +∞).
If NK
S ∈ M, the condition becomes Ker (A) = {0}, which is sufficient but obviously not necessary
for the deep-M-NSP to hold. However, when M truly imposes sparsity, the condition Ker (A) ∩
K
RSS∪S ′ = {0} says that the elements of Ker (A) shall not be sparse in some (tensorial) way. This
nicely generalizes the case K = 1.
Definition 2 Deep-lower-RIP constant
There exists a constant σM > 0 such that for any S and S ′ ∈ M and any T in the orthogonal
complement of Ker (AS∪S ′ )
(13)
σM kPS∪S ′ T k ≤ kAS∪S ′ T k.
We call σM Deep-lower-RIP constant of A with regard to M.

Proof The existence of σM is a straightforward consequence of the fact that the restriction of AS∪S ′
on the orthogonal complement of Ker (AS∪S ′ ) is injective. We therefore have for all T in the
orthogonal complement of Ker (AS∪S ′ )
kAS∪S ′ T k ≥ σS∪S ′ kT k ≥ σS∪S ′ kPS∪S ′ T k,
where σS∪S ′ > 0 is the smallest non-zero singular value of AS∪S ′ . We obtain the existence of σM
by taking the minimum of the constants σS∪S ′ over the finite family of S and S ′ ∈ M.
Theorem 3 Sufficient condition for stable recovery
Assume A satisfies the deep-M-NSP with the constants γ ≥ 1, ρ > 0. For any S ∗ ∈ M and
∗
as in (2) with η + δ ≤ ρ, we have
h ∈ RS×K
S∗
kP (h∗ ) − P (h)k ≤

γ
(δ + η),
σM

where σM is the Deep-lower-RIP constant of A with regard to M.
Moreover, if σγM (δ + η) ≤ 12 max kP (h∗ )k∞ , kP (h)k∞ , then


1
1
1
γ
−1
∗
∗ K −1
K
p
dp ([h ], [h]) ≤ 7(KS) min kP (h)k∞ , kP (h )k∞
(δ + η).
σM
6

S TABLE

RECOVERY OF DEEP LINEAR NETWORKS UNDER SPARSITY CONSTRAINTS

Proof We have
kAS ∗ ∪S (P (h∗ ) − P (h))k = kAS ∗ ∪S P (h∗ ) − AS ∗ ∪S P (h)k
= kAP (h∗ ) − AP (h)k

≤ kAP (h∗ ) − Xk + kAP (h) − Xk
≤ δ+η

If we further decompose (the decomposition is unique)
where T ′ ∈ Ker AS ∗ ∪S



P (h∗ ) − P (h) = T + T ′ ,

and T is orthogonal to Ker AS ∗ ∪S , we have

kAS ∗ ∪S (P (h∗ ) − P (h))k = kAS ∗ ∪S T k ≥ σM kPS ∗ ∪S T k,

where σM is the Deep-lower-RIP constant of A with regard to M. We finally obtain, since
PS ∗ ∪S P (h∗ ) = P (h∗ ) and PS ∗ ∪S P (h) = P (h),
kP (h∗ ) − P (h) − PS ∗ ∪S T ′ k = kPS ∗ ∪S T k ≤

δ+η
.
σM

Since A satisfies the deep-M-NSP with constants (γ, ρ) and δ + η ≤ ρ, we have

kP (h∗ ) − P (h)k ≤ γkP (h∗ ) − P (h) − PS ∗ ∪S T ′ k
δ+η
≤ γ
σM
When δ + η satisfy the condition in the theorem, we can apply Theorem 1 and obtain the last inequality.
Theorem 3 differs from the analogous theorem in Malgouyres and Landsberg (2017). In particular, it is dedicated to sparsity constraint with much weaker hypotheses on A. The constant of the
upper bound is also different.
One might again ask whether the condition “A satisfies the deep-M-NSP ” is sharp or not. As
stated in the following proposition, the answer is affirmative.
Theorem 4 Necessary condition for stable recovery
Assume the stable recovery property holds: There exists M, C and δ > 0 such that for any
, any X = AP (h) + e, with kek ≤ δ, and any S ∗ ∈ M and
S ∈ M and any h ∈ RS×K
S
S×K
∗
h ∈ RS ∗ such that
kAP (h∗ ) − Xk ≤ kek
we have

∗



1
−1
K

d2 ([h ], [h]) ≤ C min kP (h)k∞
Then, A satisfies the deep-M-NSP with constants
K−1 √
K σmax
γ = CS 2

∗

1
−1
K

, kP (h )k∞

and



kek.

ρ = δ,

where σmax is the spectral radius of A.
The proof is very similar to the proof of the Theorem 6, in Malgouyres and Landsberg (2017) and
the proof of the analogous converse statement in Cohen et al. (2009). It is provided in Appendix A.
7

edges of depth 3

2

1

RN
RN
RN root r

leaves
RN
RN

Figure 1: Example of the considered convolutional linear network. To every edge/neuron is attached a convolution kernel. The network does not involve non-linearities or sampling.

4. Application to convolutional linear network under sparsity prior
We consider a sparse convolutional linear network as depicted in Figure 1. The network typically
aims at performing a linear analysis or synthesis of a signal living in RN . The considered convolutional linear network is defined from a rooted directed acyclic graph G(E, N ) composed of nodes
N and edges E. Each edge connects two nodes. The root of the graph is denoted by r and the set
containing all its leaves is denoted by F. We denote by Pa the set of all paths connecting the leaves
and the root. We assume, without loss of generality, that the length of any path between any leaf
and the root is independent of the considered leaf and equal to some constant K ≥ 0. We also
assume that, for any edge e ∈ E, the number of edges separating e and the root is the same for all
paths between e and r. This length is called the depth of e. For any k = 1..K, we denote the set
containing all the edges of depth k, by E(k). For e ∈ E(k), we also say that e belongs to the layer
k.
Moreover, to any edge e is attached
Pa convolution kernel of maximal support Se ⊂ NN . We assume (without loss of generality) that e∈E(k) |Se | is independent of k (|Se | denotes the cardinality
of Se ). We take
X
S=
|Se |.
e∈E(1)

For any edge e, we consider the mapping Te : RS −→ RN that maps any h ∈ RS into the convolution kernel he , attached to the edge e, whose support is Se . It simply writes at the right location
(i.e. those in Se ) the entries of h defining the kernel on the edge e. As in the previous section, we
assume a sparsity constraint and will only consider a family M of possible supports S ⊂ NK
S.
At each layer k, the convolutional linear network computes, for all e ∈ E(k), the convolution
between the signal at the origin of e; then, it attaches to any ending node the sum of all the convolutions arriving at that node. Examples of such convolutional linear networks includes wavelets,
wavelet packets Mallat (1998) or the fast transforms optimized in Chabiron et al. (2014, 2016). It
is similar to the usual convolutional neural network except that the linear network does not involve
any non-linearity and the supports are not fixed. It is clear that the operation performed at any layer
depends linearly on the parameters h ∈ RS and that its results serves as inputs for the next layer.
8

S TABLE

RECOVERY OF DEEP LINEAR NETWORKS UNDER SPARSITY CONSTRAINTS

The convolutional linear network therefore depends on parameters h ∈ RS×K and takes the form
X = M1 (h1 ) . . . MK (hK ),
where the operators Mk satisfy the hypothesis of the present paper.
This section applies the results of the preceding section
 in order to identify conditions such that
any unknown parameters h ∈ RS×K satisfying supp h ⊂ S, for a given S ∈ M, can be stably
recovered from X = M1 (h1 ) . . . MK (hK ) (possibly corrupted by an error).
In order to do so, let us define a few notations. Notice first that, we apply the convolutional
linear network to an input x ∈ RN |F | , where x is the concatenation of the signals xf ∈ RN for
f ∈ F. Therefore, X is the (horizontal) concatenation of |F| matrices X f ∈ RN ×N such that
X
Xx =
X f xf
, for all x ∈ RN |F | .
f ∈F

Let us consider the convolutional linear network defined by h ∈ RS×K as well as f ∈ F and
n = 1..N . The column of X corresponding to the entry n in the leaf f is the translation by n of
X
T p (h)
(14)
p∈Pa (f )

where Pa (f ) contains all the paths of Pa starting from the leaf f and
T p (h) = Te1 (h1 ) ∗ . . . ∗ TeK (hK )

, where p = (e1 , . . . , eK ).

Moreover, we define for any k = 1..K the mapping ek : NS −→ E(k) which provides for any
i = 1..S the unique edge of E(k) such that the ith entry of h ∈ RS contributes to Tek (i) (h). Also,
for any i ∈ NK
S , we denote pi = (e1 (i1 ), . . . , eK (iK )) and, for any S ∈ M,

IS = i ∈ NK
S |i ∈ S and pi ∈ Pa .
The latter contains all the indices of S corresponding to a valid path in the network. For any set of
parameters h ∈ RS×K and any path p ∈ Pa , we also denote by hp the restriction of h to its indices
i
S×K by
contributing to the kernels on the path p. We also define, for any i ∈ NK
S,h ∈R

1 , if j = ik
i
hk,j =
, for all k = 1..K and j = 1..S.
(15)
0 otherwise

We can deduce from (14) that, when i ∈ IS , AP (hi ) simply convolves the entries at one leaf with a
dirac delta function. Thefore, all the entries of AP (hi ) are in {0, 1} and we denote Di = {(i, j) ∈
NN × NN |F | |AP (hi )i,j = 1}.
We also denote 1 ∈ RS a vector of size S with all its entries equal to 1. For any edge e ∈ E,
1e ∈ RS consists of zeroes except for the entries corresponding to the edge e which are equal to 1.
For any S ⊂ NS , we define 1S ∈ RS which consists of zeroes except for the entries corresponding
to the indexes in S. For any p = (e1 , . . . , eK ) ∈ Pa , the support of M1 (1e1 ) . . . MK (1eK ) is
denoted by D p .
Finally, we remind that because of (8), there exists a unique mapping
A : RS

K

−→ RN ×N |F |
9

such that
, for all h ∈ RS×K ,

AP (h) = M1 (h1 ) . . . MK (hK )
where P is the Segre embedding defined in (5).

Proposition 2 Necessary condition of identifiability of a sparse network
′
′
Either RS×K is not identifiable or, for any S and S ′ ∈ M, all the entries of M1 (1S∪S ) . . . MK (1S∪S )
belong to {0, 1}. When the latter holds :
′

1. For any distinct p and p′ ∈ Pa , we have D p ∩ D p = ∅.
K

2. Ker (AS∪S ′ ) = {T ∈ RS |∀i ∈ IS∪S ′ , Ti = 0}.
Proof
′
′
Let us assume that: There exist S and S ′ ∈ M and an entry of M1 (1S∪S ) . . . MK (1S∪S )
that does not belong to {0, 1}.
Using (14), we know that there is f ∈ F and n = 1..N such that
X
T p (1) n ≥ 2.
p∈Pa (f )

As a consequence, there is i and j ∈ S ∪ S ′ with i 6= j and
T pi (hi ) n = T pj (hj ) n = 1.
Therefore,
AP (hi ) = AP (hj )
and the network is not identifiable. This proves the first statement.
′
′
Let us assume that: For any S and S ′ ∈ M, all the entries of M1 (1S∪S ) . . . MK (1S∪S )
belong to {0, 1}.
We immediately observe that (14) leads to the item 1 of the Proposition.
To prove the second item, we can easily check that (P (hi ))i6∈IS∪S ′ forms a basis of {T ∈
K
RS |∀i ∈ IS∪S ′ , Ti = 0}. We can also easily check using (14) and (11) that, for any i 6∈ IS∪S ′ ,

0
, if i 6∈ S ∪ S ′
i
AS∪S ′ P (h ) =
M1 (hi1 ) . . . MK (hiK ) = 0 , if i ∈ S ∪ S ′ and pi 6∈ Pa
K

As a consequence, {T ∈ RS |∀i ∈ IS∪S ′ , Ti = 0} ⊂ Ker (AS∪S ′ ).
To prove the converse inclusion, we observe that for any distinct i and j ∈ IS∪S ′ , we have
Di ∩ Dj = ∅. This implies that
K

rk (AS∪S ′ ) ≥ |IS∪S ′ | = S K − dim({T ∈ RS |∀i ∈ IS∪S ′ , Ti = 0}).
K

Finally, we deduce that dim(Ker (AS∪S ′ )) ≤ dim({T ∈ RS |∀i ∈ IS∪S ′ , Ti = 0}) and therefore
K

Ker (AS∪S ′ ) = {T ∈ RS |∀i ∈ IS∪S ′ , Ti = 0}.

10

S TABLE

RECOVERY OF DEEP LINEAR NETWORKS UNDER SPARSITY CONSTRAINTS

Proposition 2 extends Proposition 8 of Malgouyres and Landsberg (2017) by considering several
possible supports. Said differently, Proposition 8 of Malgouyres and Landsberg (2017) corresponds
to Proposition 2 when M = {NK
S }.
The interest of the condition in Proposition 2 is that it can easily be computed by applying the network to dirac delta functions, when |M| is not too large. Notice that, beside the
known examples in blind-deconvolution (i.e. when K = 2 and |Pa | = 1) Ahmed et al. (2014);
Bahmani and Romberg (2015), there are known convolutional linear networks (with K ≥ 2) that
satisfy the condition of the first statement of Proposition 2. For instance, the convolutional linear
network corresponding to the un-decimated Haar wavelet2 transform is a tree and for any of its
leaves f ∈ F, |Pa (f )| = 1. Moreover, the support of the kernel living on the edge e, of depth
k, on this path is {0, 2k }. It is not difficult to check that the first condition of Proposition 2 holds.
Otherwise, it is clear that the necessary condition will be rarely satisfied.
Proposition 3 If |Pa | = 1 and if, for any S and S ′ ∈ M, all the entries of M1 (1S∪S ) . . . MK (1S∪S )
K
belong to {0, 1}, then Ker (AS∪S ′ ) is the orthogonal complement of RSS∪S ′ and A satisfies the deepM-NSP√with constants (γ, ρ) = (1, +∞). Moreover, the deep-lower-RIP of A with regard to M is
σM = N .
′

K

′

Proof The fact that, Ker (AS∪S ′ ) is the orthogonal complement of RSS∪S ′ is a direct consequence
of Proposition 2 and the fact that, when |Pa | = 1, IS∪S ′ = S ∪ S ′ . We then trivialy deduce that,
for any T ′ ∈ Ker (AS∪S ′ ), PS∪S ′ T ′ = 0. A straightforward consequence is that A satisfies the
deep-M-NSP with constants (γ, ρ) = (1, +∞).
To calculate σM , let us considerP
S, S ′ ∈ M and T in the orthogonal complement of Ker (AS∪S ′ ).
We express T under the form T = i∈I ′ Ti P (hi ), where hi is defined (15). Let us also remind
S∪S
that, applying Proposition 2, the supports of AP (hi ) and AP (hj ) are disjoint, when i 6= j. Let us
finally add that, since AP (hj ) is the matrix of a convolution with a Dirac mass, we have |Dj | = N .
We finally have
X
kAT k2 = k
Ti AP (hi )k2 ,
i∈I

= N

X
i∈I

Ti2 = N kT k2 ,

from which we deduce the value of σM .
In the sequel, we establish stability results for a convolutional linear network estimator. In order
to do so, we consider a convolutional linear network of known structure G(E, N ), (Se )e∈E and
M. The convolutional
linear network is defined by unknown parameters h ∈ RS×K satisfying a

constraint supp h ⊂ S for an unknown support S ∈ M. We consider the noisy situation where
X = M1 (h1 ) . . . MK (hK ) + e,
2. Un-decimated means computed with the ”Algorithme à trous”, Mallat (1998), Section 5.5.2 and 6.3.2. The Haar
wavelet is described in Mallat (1998), Section 7.2.2, p. 247 and Example 7.7, p. 235

11

with kek ≤ δ and an estimate h∗ ∈ RS×K such that
kM1 (h∗1 ) . . . MK (h∗K ) − Xk ≤ η.
The equivalence relationship ∼ does not suffise to group parameters leading to the same network
action. Indeed, with networks, we can rescale the kernels on different path differently. Therefore,
we say that two networks sharing the same topology and defined by the parameters h and g ∈ RS×K
are equivalent if and only if
Y
∀p ∈ Pa , ∃(λe )e∈p ∈ Rp , such that
λe = 1 and ∀e ∈ p, Te (g) = λe Te (h).
e∈p

We trivially observe that applying the networks defined by equivalent parameters lead to the same
result. The equivalence class of h ∈ RS×K is denoted by {h}. For any p ∈ [1, +∞], we define


δp ({h}, {g}) = 

1

p

X

p p

p

dp ([h ], [g ])

p∈Pa

,

where we remind that hp (resp gp ) denotes the restriction of h (resp g) to the path p and dp is
defined in (4). Since dp is a metric, we easily prove that δp is a metric between network classes.
Theorem 5 If for any S and S ′ ∈ M, all the entries of M1 (1S∪S ) . . . MK (1S∪S ) belong to
{0, 1} and if there exists ε > 0 such that for all e ∈ E, kTe (h)k∞ ≥ ε then
′

′

1

(KS) p
δp ({h }, {h}) ≤ 7 √
(δ + η).
N εK−1
∗

Proof Let us consider a path p ∈ Pa , using (14), since all the entries of M1 (1S∪S ) . . . MK (1S∪S )
belong to {0, 1}, the restriction of the network to p satisfy the same property. Therefore, we can
apply Proposition 3 and Theorem 3 to the restriction of the convolutional linear network to p and
obtain for any p ∈ [1, ∞]
′

1

(KS) p 1−K p
dp ([(h ) ], [h ]) ≤ 7 √
ε
(δ + η p ),
N
∗ p

p

where δp and η p are the restrictions of the errors on D p . Finally, using item 1 of Proposition 2


1
p

1

p

(KS) 1−K 
δp ({h }, {h}) ≤ 7 √
ε
(δp + η p )p  ,
N
p∈Pa
∗

1

X

(KS) p
≤ 7√
(δ + η).
N εK−1

12

′

S TABLE

RECOVERY OF DEEP LINEAR NETWORKS UNDER SPARSITY CONSTRAINTS

Acknowledgments
Joseph Landsberg is supported by NSF DMS-1405348.

References
Arif Ahmed, Benjamin Recht, and Justin Romberg. Blind deconvolution using convex programming. IEEE Transactions on Information Theory, 60(3):1711–1732, 2014.
Sanjeev Arora, Rong Ge, Ravindran Kannan, and Ankur Moitra. Computing a nonnegative matrix
factorization–provably. In Proceedings of the forty-fourth annual ACM symposium on Theory of
computing, pages 145–162. ACM, 2012.
Sohail Bahmani and Justin Romberg. Lifting for blind deconvolution in random mask imaging:
Identifiability and convex relaxation. SIAM Journal on Imaging Sciences, 8(4):2203–2238, 2015.
Emmanuel J Candes, Thomas Strohmer, and Vladislav Voroninski. Phaselift: Exact and stable
signal recovery from magnitude measurements via convex programming. Communications on
Pure and Applied Mathematics, 66(8):1241–1274, 2013.
Olivier Chabiron, François Malgouyres, Jean-Yves Tourneret, and Nicolas Dobigeon. Toward fast
transform learning. International Journal of Computer Vision, pages 1–22, 2014.
Olivier Chabiron, François Malgouyres, Herwig Wendt, and Jean-Yves Tourneret. Optimization of
a fast transform structured as a convolutional tree. preprint HAL, (hal-01258514), 2016.
Anna Choromanska, Mikael Henaff, Michael Mathieu, Gérard Ben Arous, and Yann LeCun. The
loss surfaces of multilayer networks. In Artificial Intelligence and Statistics, pages 192–204,
2015a.
Anna Choromanska, Yann LeCun, and Gérard Ben Arous. Open problem: The landscape of the loss
surfaces of multilayer networks. In Conference on Learning Theory, pages 1756–1760, 2015b.
Sunav Choudhary and Urbashi Mitra. Identifiability scaling laws in bilinear inverse problems. arXiv
preprint arXiv:1402.2637, 2014.
Albert Cohen, Wolfgang Dahmen, and Ronald DeVore. Compressed sensing and best -term approximation. Journal of the American mathematical society, 22(1):211–231, 2009.
David L Donoho and Victoria Stodden. When does non-negative matrix factorization give a correct
decomposition into parts? 2003.
Michael Elad. Sparse and Redundant Representations: From Theory to Applications in Signal and
Image Processing. Springer, 2010.
Ronen Eldan and Ohad Shamir. The power of depth for feedforward neural networks. In Conference
on Learning Theory, pages 907–940, 2016.
Benjamin D Haeffele and René Vidal. Global optimality in tensor factorization, deep learning, and
beyond. arXiv preprint arXiv:1506.07540, 2015.
13

Rodolphe Jenatton, Rémi Gribonval, and Francis Bach. Local stability and robustness of sparse
dictionary learning in the presence of noise. arxiv, 2012.
Kenji Kawaguchi. Deep learning without poor local minima. In Advances in Neural Information
Processing Systems, pages 586–594, 2016.
Hans Laurberg, Mads Græsbøll Christensen, Mark D Plumbley, Lars Kai Hansen, and Søren Holdt
Jensen. Theorems on positive data: On the uniqueness of nmf. Computational intelligence and
neuroscience, 2008, 2008.
Daniel D Lee and H Sebastian Seung. Learning the parts of objects by non-negative matrix factorization. Nature, 401(6755):788–791, 1999.
Xiaodong Li, Shuyang Ling, Thomas Strohmer, and Ke Wei. Rapid, robust, and reliable
blind deconvolution via nonconvex optimization. CoRR, abs/1606.04933, 2016. URL
http://arxiv.org/abs/1606.04933.
Roi Livni, Shai Shalev-Shwartz, and Ohad Shamir. On the computational efficiency of training
neural networks. In Advances in Neural Information Processing Systems, pages 855–863, 2014.
François Malgouyres and Joseph Landsberg. Stable recovery of the factors from a deep matrix
product and application to convolutional network. arXiv preprint arXiv:1703.08044, 2017.
Stéphane Mallat. A Wavelet Tour of Signal Processing. Academic Press, Boston, 1998.
Itay Safran and Ohad Shamir. On the quality of the initial basin in overspecified neural networks.
In International Conference on Machine Learning, pages 774–782, 2016.
Nitish Srivastava, Geoffrey E Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov.
Dropout: a simple way to prevent neural networks from overfitting. Journal of machine learning
research, 15(1):1929–1958, 2014.

Appendix A. Proof of Theorem 4


′
′
S×K
and
Proof Let S and S ′ ∈ M. Let h ∈ RS×K
h
∈
R
be
such
that
kA
P
(h)
−
P
(h
)
k≤
′
S
S

δ. Throughout the proof, we also consider T ′ ∈ Ker (AS∪S ′ ). We assume that kP (h)k∞ ≤
′
′
kP (h )k∞ . If it is not the case, we simply switch the role of h and h in the definition of X and e,
below. We denote
′
X = AP (h)
and
e = AP (h) − AP (h ).
′

We have X = AP (h ) + e with kek ≤ δ. Moreover, when S and h play the role of S ∗ and h∗ in
the hypothesis, since h ∈ RS×K
and kek ≤ δ, we have
S
′

′

1

K
d2 ([h ], [h]) ≤ CkP (h )k∞

14

−1

kek.

S TABLE

RECOVERY OF DEEP LINEAR NETWORKS UNDER SPARSITY CONSTRAINTS

′

Using the fact that e = AS∪S ′ (P (h) − P (h )), for any T ′ ∈ Ker (AS∪S ′ )
′

kek = kAS∪S ′ (P (h) − P (h ) − T ′ )k,
′

≤ σmax kPS∪S ′ (P (h) − P (h ) − T ′ )k,
′

= σmax kP (h) − P (h ) − PS∪S ′ T ′ k,
where σmax is the spectral radius of A. Therefore,
′

′

1

K
d2 ([h ], [h]) ≤ CkP (h )k∞

−1

′

σmax kP (h) − P (h ) − PS∪S ′ T ′ k,
′

Finally, using Theorem 2 and the fact that kP (h)k∞ ≤ kP (h )k∞ , we obtain
′

K−1
2

′

1

1−

1

′

K 1− 2 kP (h )k∞ K d2 ([h ], [h])
K−1 √
′
≤ CS 2
K σmax kP (h) − P (h ) − PS∪S ′ T ′ k

kP (h ) − P (h)k ≤ S

′

= γkP (h) − P (h ) − PS∪S ′ T ′ k

K−1 √
for γ = CS 2
K σmax .
Summarizing, we conclude that under the hypothesis of the theorem: For any S and S ′ ∈ M
) + P (RS×K
) such that kAT k = kAS∪S ′ T k ≤ δ, we have for any T ′ ∈
and any T ∈ P (RS×K
S
S′
Ker (AS∪S ′ )
kT k ≤ γkT − PS∪S ′ T ′ k.

In words, A satisfies the deep-M-NSP with the constants of Theorem 4.

15

