Sparse Coding with Gated Learned ISTA
Authors: Kailun Wu
Yiwen Guo
Ziang Li
Changshui Zhang
Venue:  (2020)
Keywords: Sparse coding
deep learning
learned ISTA
convergence analysis

Abstract: In this paper, we study the learned iterative shrinkage thresholding algorithm (LISTA) for solving sparse coding problems.  Following assumptions made by prior works, we first discover that the code components in its estimations may be lower than expected, i.e., require gains, and to address this problem, a gated mechanism amenable to theoretical analysis is then introduced. Specific design of the gates is inspired by convergence analyses of the mechanism and hence its effectiveness can be formally guaranteed. In addition to the gain gates, we further introduce overshoot gates for compensating insufficient step size in LISTA. Extensive empirical results confirm our theoretical findings and verify the effectiveness of our method.

Published as a conference paper at ICLR 2020
SPARSE CODING WITH GATED LEARNED ISTA
Kailun Wu of
Yiwen Guo Bytedance Lab Beijing, P.R.China guoyiwen ai aiibytedance.comm com
Department of Automation, Tsinghua University
Beijing, P.R.C. China
wukl140n 1ak1140mali wtw.slsssssinaaaaeeeeeoo.o.. on &kailun www.iluneal
com
Ziang Li
Changshui Zhang
Department of Automation, Tsinghua University Beijing, P.R.Chine China
Department of Automation,
Tsinghua University
Beijing, P.R.Chini zcs@mas ts testttnnniii innhungha.... edu. cn
1 aazal 1 90ma 1 s. tsinnhua. edu.cn
ABSTRACT
In this paper, we study the learned iterative shrinkage thresholding algorithm (LISTA) for solving sparse coding problems. Following assumptions made by prior works, we first discover that the code components in its estimations may be lower than expected, i.e., require gains, and to address this problem, a gated mechanism amenable to theoretical analysis is then introduced. Specific design of the gates is inspired by convergence analyses of the mechanism and hence its effectiveness can be formally guaranteed. In addition to the gain gates, further introduce overshoot gates for compensating insufficient step size in LISTA. Extensive empirical results confirm our theoretical findings and verify the effectiveness of our method.
INTRODUCTION
Sparse coding serves as the foundation of many machine learning applications, e.g., the direction-of- arrival estimation (Xu et al. 2012), signal denoising (Elad & Aharon 2006), and super resolution imaging (Yang et al. 2010). In general, aims recover an inherently sparse vector Vs E IR. from an observation y E R. corrupted by noise vector Rmm. That is,
y Ax. + E,
(1)
in which A E x is over-complete basis matrix. The problem of recovering T.. however, is a challenging task, in which the main difficulties are to incorporate the sparse constraint which is nonconvex and to further determine the indices of its non-zero elements, i.e., the support of the vector. reasonable solution to the problem is to use convex functions as surrogates to relax the constraint of sparsity, among which the most classical one probably is the (-oor penalty. Such a problem is carefully studied in Lasso (Tibshirani) 1996), and it can be solved via least angle regression (Efron al. 2004), the iterative shrinkage and thresholding algorithm (ISTA) (Daubechies et al. 2004). etc.
Despite the simplicity, these conventional solvers suffer from critical shortcomings. Taking ISTA as an example, we know that converges very slowly with only a sublinear rate (Beck & Teboulle 2009). 2) the correlation between each of the two columns of A should be relatively low. In recent years, deep learning [LeCun al. 2015) methods have achieved remarkable successes. Deep neural
"Kailun Wu and Yiwen Guo contribute equally to the paper.
"Kallun Wu, Ziang Li, and Changshui Zhang with the Institute for Artificial Intelligence (THUAI), the State Key Lab of Intelligent Technologies and Systems, the Beijing National Research Center for Information Science and Technology (BNRist), and the Department of Automation, Tsinghua University. Kailun Wu did his work when he was Ph.D. student at Tsinghua Unversity, and now he works at Alibaba Group. This work is (jointly or partly) funded by the NSFC (Grant No. 61 61876095) and Beijing Academy of Artificial Intelligence (BAAD).

---

Published as a conference paper at ICLR 2020
networks (DNNs) have been proven both effective and efficient in dealing with many tasks, including
image classification (He et al. 2016). object detection (Girshick 2013), speech recognition (Hinton
2012), and also sparse coding (Gregor & LeCun [ Wang et al., [2166] BBrgerding et al. 2017 He et al. 2017 ZZhang & Ghanem 2018) Chen et al. [018 Liu et al. 2019] |ulam et al. 2019). The core idea behind deep learning-based sparse coding
et al.
train DNNs approximate the optimal sparse code. For instance, an initial work of Gregor and LeCun's 's (2010) takes the inspiration from ISTA and develops an approximator named learned ISTA (LISTA), which is structurally similar to recurrent neural network (RNN).
has been demonstrated both empirically and theoretically that LISTA is superior to ISTA (Wang et al. 2016; Moreau & Bruna 2017 Giryes et al.] [2018] Chen et al. 2018). Nevertheless, it is also In this paper; we delve deeply into the foundation of (L)ISTA and discover possible weaknesses of LISTA. First and foremost, we know from prior arts (Chen al. 2018 Liu et al. 2019) that LISTA tends to learn large enough biases to achieve no "false positive" in the support of generated codes and further ensure linear convergence, and we prove that this tendency, however, also makes the magnitude of the code components being lower than that of the ground-truth. That said, there probably exists requirement of gains in the code estimations. Second, regarding the optimization procedure of ISTA as to minimize an upper bound of its objective function each step, we conjecture that the element-wise update of (L)ISTA normally "lags behind" the optimal solution, which suggests that it requires overshoots to reach the optimum, just like what has been suggested in fast ISTA (FISTA) (Beck & Teboulle 2009) and learned FISTA (LFISTA) (Moreau & Bruna 2017).
uncontroversial that there exists much room for further enhancing
In this paper, our main contributions are summarized as follows:
We discover weaknesses of LISTA by theoretically analyzing its optimization procedure, for mitigating which we introduce gain gates and overshoot gates. akin to update gate and reset gate mechanisms in the gated recurrent unit (GRU) Cho et al. (2014).
We provide convergence analyses for LISTA (with or without gates), which further give rise to conditions on which the performance of our method with gain gates can be guaranteed. A practical case is considered, where the assumption of no "false positive" is relaxed.
Insightful expressions for the gates are presented. In comparison with state-of-the-art sparse coding networks (not limited to previous extensions to LISTA), our method achieves superior performance. also applies variants of LISTA, e.g., LFSITA (Moreau & Bruna 2017)
and ALISTA (Liu et al. 2019).
Notations: In this paper, unless otherwise clarified, vectors and matrices are denoted by lowercase and uppercase characters, respectively. For vectors/matrices originally introduced without any subscript, adding subscript (e.g.. i) indicates its clement/column at the corresponding position. For instance, for x E R", Iy represents the i-th element of the vector, and W., and Wt. denote the i-th column and row of matrix W respectively. While for vectors introduced with subscripts already, e.g., Z.. use (x.);; to denote its i-th element. The operator @ is used to indicate element- dement-wise multiplication of vectors. The support of a vector is denoted as supp(æ:) == (ilxa * 0). We use sup,, the simplified form of sup, (B,,))))) see Assumption 1 for the definition of X (B, 8,,8800 O)..
BACKGROUND
In general, sparse coding solves the problem that can be formulated as
min f(x, v) + Ar(x),
(2)
in which fæ, y) calculates the residual of approximating using a linear combination of column-wise features in A. The function f(x, y) is convex with respect to x in general. In particular, & is a Gaussian vector, then it should be f(x, u) = || 211.. The term Xr(x) serves as regularizer for sparsity and we have r(æ)= = ||a:|| in Lasso. As mentioned, a variety of algorithms can be applied to solve the problem and our focus in the paper is (L)ISTA. We first revisit the optimization procedure of ISTA, which is the foundation of LISTA as well. Given y. let us introduce a scalar y > 0 that fulfills T V2 (a > 0, Va, then it can be considered optimizing an upper bound of the objective
2

---

Published as a conference paper at ICLR 2020
function obtained via Taylor expansion. To be more specific, for any presumed 21),, we have 10 -
f(z y) + Ar(x)= S f(x(") y) + (x - x ='")V=f(x")) + - -
Ar(x)).
(3)
2
By substituting r(æ) with ||al| and optimizing the bound in an element-wise manner, we can easily get the one-step update rule that zeros the gradient based on s((), It is, x:()) = 0 and
(1++)) (x/)(((( vzl(x())//
VI 2 O,
(4)
in which sx)) = signí (z) (1z) - b)+ a shrinking function and (-)+ is rectified linear unit (ReLU) calculating max (0, -.. For Gaussian noises, the formulation reduces to
x ((+1) 8x/7 ((r
A A
AT
x
(5)
Y
The update as shown in Eq. and (5) can be performed iteratively until convergence. However, the convergence of ISTA (along with some other conventional solvers) is known to be slow, and it has been shown that DNNs can be utilized to accelerate the procedure. Many researchers have explored the idea since the initial work of Gregor and LeCun's 's (i.e., LISTA). For LISTA, they design deep architectures following the main procedure ISTA yet to learn parameters an end-to-end manner from data (Gregor& & LeCun 2010 Hershey et al. 2014). The inference process of LISTA is similar
to that of an RNN and can be formulated as x (0) 0 and
x (1+1) Sp00) (W(1)) (0) + u))
t= ,,
where è = (000)
W b(t) Jt= is learnable parameters set. Some works (Xin et al. 2016
Chen et al. 2018 have proved that W(t) and (+(t) should satisfy the constraint W = U
such that
x (++1) 8p00 (2 + (')))(('' (Ax!") y)), 1= 1-0,...,-11
The parameters in O are normally learned from set of training samples by minimizing the difference between the final code estimations and ground-truth. In this paper, our main assumption for theoretical analyses follows those of prior works (Chen al. 2018 Liu al. 2019) in a noiseless case, and noisy cases will be considered the experiments.
Assumption 1. The sparse vector v. and noise vector are sampled from set X(B, 8, 0) fulfilling:
X(B, == [a|1|=/|00 & B, = 0, |=||o s}.
SPARSE CODING WITH GAIN GATES AND OVERSHOOT GATES
In this section, we will introduce the advocated gain gates and overshoot gates. Along with thorough discussions for the motivations, their formulations are provided in Section and
and 3.2] respectively. Figure T the inference process of the standard LISTA and two evolved versions with our gates incorporated. Proofs of all our theoretical results are deferred to the appendix.
stuges
stages
stages
(LF1)
(t
10
(411)
wil
NP
LISTA Figure 1: The inference process of the standard LISTA and evolved versions with our gates
LISTA with the overshoot gates
LISTA with the gain gates
3.1 SPARSE CODING WITH GAIN GATES
Recent works have shown linear convergence of LISTA (Chen al., 2018 Liu et al. 2019). order to guarantee the convergence, it is also demonstrated that the value of bias terms should be large enough to eliminate all "false positive" in the support of the generated codes. However, this may lead to an issue that the magnitude of the generated code components in LISTA must be smaller than at most equal to those of the ground-truth. Our result in Proposition I makes this formal. For clarity of the result, would like to introduce the following definition first.
3

---

Published as a conference paper at ICLR 2020
Definition 1.
(Liu et al. 2019) Given matrix A Rmxx its generalized mutual coherence is:
(AA) =
inf
{ Liji
max
W...A.s.
(8)
W BeeixxmwWWW.a.a A1,M
We let (A) denote set of all matrices that can achieve the generalized mutual coherence μ(A)), which means:
W(A) = W|]
max Wi.A... = ((A), W., (1, 1,
(9)
Proposition 1. (Requirement of gains). With ( E W(A) and W = I - A, if b(t)
= p(A) supx, [|x(()) - 1sll1 is achieved in LISTA to guarantee no "false positive" (i.e., supp(x!!))
supp(æ.)) and further linear convergence (i.e., [xx(1) rell2 S sB exp(ct). in which log((22
1))( then we have for the estimation |=; I (xx)); and x. (xx); 2 0, Vi E supp(a.).
Provided Proposition [ as the evidence of a potential weakness of LISTA, we believe that if the code components can be enlarged appropriately, then the estimation at each step would be closer to T., and the convergence of LISTA will be further improved, which inspires us design gate to enlarge the generated code components. Such gate is named as gain gate and it acts on the input to the current estimation, akin to a reset gate GRU (Cho al. 2014). which is
(1++1) Syc0
ylAf1) @ xl1) + U))
(10)
in which the gate function (A, outputs n-dimensions vector, and A is the set of its learnable parameters. In the original implementation of LISTA, the output of each layer is obtained by calculating Eq. 4 iteratively. has been proven that the estimation (1)) ultimately converges to the ground-truth Is (as -> 20), only if the condition of (W() - (T U A)) - 0 holds. That said, suggested that (7(3) and (( are entangled to the end. Yet, with our gated mechanism, the update rule in neural networks has been modified into Eq. (10), making it unclear whether the convergence guaranteed similarly or not. To figure out, we perform theoretical analyses in depth, which will further provide guidance for the gate design. We are going to explore: whether the learnable matrices are still entangled as in LISTA, and to encourage fast convergence, what properties should the gate function satisfy? Theorem and 2 give some answers to these questions and they are based on the same assumptions as for Proposition [
Theorem 1. If the s-th principal minor of W()) have full rank, then for the gate function bounded from both above and below, have x,, the fixed point of Eq. (70) only if
diag(g(( (e)()))))))))))))) D and ((t) D (I- (()) + 0,
as t + co,
(11)
in which D is an constant diagonal matrix and the function diag(.) creates diagonal matrix with the elements of its input on the main diagonal.
-I- From Theorem we can equivalently have (W7( - ('0 - 0 by defining V7 = (()) D.
which means the learnable matrices are similarly entangled as in the standard LISTA. Besides, we know that as the number of layers increases, each introduced gain gate should ultimately converge to a constant (diagonal) matrix to guarantee performance. Then W(t) function converges to identical mapping as + co, and vice versa. This inspires us to "split" the gate function into an identical one and residual one, and we thus advocate, for each index of the vector, the i-th element of gain gate is
( A, the gain gate
(t( bl vllA()) = 1 + (x)()) (vl(())))))))))))) vlA and (x(x ,llA 2 0.
(12)
in which Ke (*)) y/ y 0; is the i-th element of (x))))) ylA,"), and it should decrease as t increases, in order guarantee convergence in Eq. M Let us further study the convergence rate of "LISTA" equipped with such gain gates. For clarity, we introduce another condition for the function before moving to more details;
(0) ,vlA))) 26th 1/12
(13)
We present theoretical results as follows on the basis of Proposition 1 i.e., we still have ( W(A).
W 1 - TT(1) A and Assumption 1 but the requirement for ((0) is different.
4

---

Published as a conference paper at ICLR 2020
Theorem 2. 1f(()) μ(A) sup,, Ir,, rule in Eq. (10, if the conditions in Eq. 12
xl0 ge(a(()
y ) is achieved, following the update hold for the gate function, there will be
and 13
||-(() -zal2 2 S sB expl
G c++c),
(14)
which log((2s ())( a = ccfi Nog ||=, ) log( (2a- 1 iyw(a))) ). and G; < otherwise.
Theorem presents an upper bound of ||-((0) 22-12 for LISTA with gain gates, and it shows that so long as the gates satisfying conditions Eq. (12) and (13) are introduced, the "convergence factor" c+ Σ of our gated LISTA would be smaller in comparison with that of the standard LISTA (which ct, see Proposition
T and Chen et al.'s work 201k).
By consolidating all these theoretical cues, we further give principled expressions for the gate function. One may expect to endow the gates some learning capacities, thus we let
go (x)(t) y
(x(()) .y v/)
+ p,b(t- fx (x((00)))
(15)
which ft E R is a parameter to learned, (((-1) is the threshold parameter of the (t - -h layer, and ft(x(*|pp) p4) is a newly introduced function constrained not to be greater than 2/(xx')). We are
going to evaluate different choices for the function f(((() in experiments, c.g.,
the piece-wist wise linear function: (p,) ReL.U(1 (eLU((,)a=!))))
the inverse proportional function: fi(x(01p4) =
(16)
the exponential function: (((x"))))) exp(-vn)z>))),
in which PI E R is a parameter to be learned, and is tiny positive scalar introduced to avoid zero being divided. All the learnable parameters in a gain gate are thus collected as Ag {Me, ).
3.1.1 No FALSE POSITIVE?
Our previous theoretical results show that the performance of LISTA can be improved by using gain gate, as long the gate function satisfies conditions in Eq. (22 and (33). and no "false positive" is encountered. However, it is not always true in practice. Our experimental results also show that when the inverse proportional function is adopted gain gates in lower layer for LISTA, the performance of our gated LISTA may even degrade. We conjecture that such contradiction to the theoretical results may be owing impractical assumptions. In this subsection, we try relax the assumption about no "false positive", and we further found that tighter bound can be achieved with more reasonable assumption instead. Through theoretical analyses as follows, we also demonstrate that the inverse proportional gain function should better be only adopted in higher layers. For clarity of the results, we would like introduce the following definition first.
Definition 2. Given a model with O in which b(t) = ['((A) supæ, ||x((0) O ge y/A!") - x #all1. introduce We41 (k()) to characterize its relationship with the false positive rate, which is r,
We+1 (k++1
sup
Va., sup((at 1) ()Ummpp(a,)) Slmpp..)sssmm SImpp(a.)) +++k
in which ((++1) == Spce (W(+) (x(() O (e(x(()) (lle(t)v)l (vAA - IZ)), and k 2 O is the desired maximal number of "false positive" of (t++))
The above definition applies to both the standard LISTA and LISTA with gain gates (we can let the gate function an identity function to achieve a standard LISTA). We first analyze the convergence of LISTA without gates. We present theoretical results follows the basis of similar assumptions
(including Assumption I ttt) E W(A), and W(O I- - (tt) A), but with a different requirement
for ((0) from Proposition 1
Theorem 3. (() Wh+1 (ke+1 (O))(A) (K)+)))))(()))))))))))))))))( sups, ||x(()) æelli is achieved, and 30 (1) < such
that (k) (0) - 1/(s - 1 then there exists "false positive" with 0 < kt < and
|x(01 - xal12 S sB exp
in which og 12g((2s ()).
5

---

Published as a conference paper at ICLR 2020
It can be seen that when we relax the assumption about no "false positive" and further reduce the value of the threshold ((0), the error bound of LISTA becomes even lower. Obviously, the previous bound of LISTA with gain gates in Theorem 2 is not necessarily lower than the tighter bound of a standard LISTA in Theorem [ which well explains the contradiction of theoretical and empirical results. Here we re-deduce the error bound our gated LISTA with the inverse proportional function in the following theorem. Note that we still have (1(() W(A),, W
U A and Assumption
Theorem 4. Suppose that mupsgsupp(z.) ((xg) )
2 > 0, ifbl = wh+1 (ke41 (A) sup,,, 1
ge ge(1 2/ - w. |1 is achieved and 30 k(t)
< such that wi (x. (0) - 1/(s =b)). then
|1,( Nz S 8B expl
4 + c));
1=1
///ll/(//// (28- (28-1)p A) ) if the scating ps of the gate has μ4 for S to, < k; < s. then de c, and if w, (s] < p4 for > to. k; = 0, then d; < c.
in which ct < log((2s - ()). 360 - [log( =2
We can conclude from Theorem 4 that, a) a gain gate expressed by the inverse proportional function should be applied to deeper layers in LISTA, rather than lower layers, b) when using the function, there indeed exists no "false positive" (i.e., k;- = 0) in deeper layer. We follow such guidelines in the implementation of our gated LISTA. In addition, we observe that unlike the inverse proportional function, other considered functions show consistent performance gains on both lower and higher layers, hence attempt utilize them on lower layers in alliance with the inverse proportional function powered gain gates on the other layers. In practice, we choose the ReLU-based piece- wise linear fuucciin, and it is uniformly applied to the first 10 layers. We will empirically compare different choices between the gain gate functions in Section 4.1
3.2 SPARSE CODING WITH OVERSHOOT GATES
Unlike the gain gates that are incorporated before performing estimation each step, the overshoot gates act more like adjustments to the outputs, which can be viewed as Icarnable boosts:
(((+1) Spen (W() (0) + (
(17)
(++1) (1 )) @ (((+1) + (1 (1- (1-0, (((4")))AAA))) O 19)
The gate function oz( ( (R" RT + R" outputs n-dimensional vector and A collects all the trainable parameters in the function, akin to a dedicated update GRU gate (Cho et al. 2014).
Our motivation comes from analyses of ISTA, whose update can be viewed as 2:(t) + 1)(2 in which 7 1 is constant step size. We argue that
may not be the most suitable choice and the following proposition makes this formal. We have to theoretically analyze the update rule of ISTA and 17" := arg min, f ((((((+1)) x(t)) + (t() yy + (1(n(=((-1) (0)) + (f(
Proposition 2. (Requirement of overshoots) For min f(x. y) + A||=112, in which f(z, y) is convex with respect to x and I V2.((x) > 0 holds for all x. if the update rule in Eq. (4) is adopted, then
we have 17" 2 1. In addition, if (t))( c supp(x
then we further have 17" > 1.
See also Figure for an illustration of the issue with 7) = 1 as concerned. Since the optimization procedure of ISTA inspires the network architecture in LISTA, the theoretical result in Proposition] 2 that requires a boost in 17 for superior performance also inspires to design specific overshoot gates for LISTA. Having noticed that an essential principle we have obtained is to let 2 1 (or > 1), we may expect the output of the gate function to be greater than or at least equal to 1. To achieve the goal, we can try different expressions for it, e.g..
the sigmoid-har based function: (x (9) ) = 1 + a (Wow + Uny)
Σ yi
the inverse- proportoooot based function: (x y/A = 1+ [ - [+)) +
ao
(18)

---

Published as a conference paper at ICLR 2020
with (-) being the sigmoid function, Ao {a.: Wa, Un} and Ao {a.} for the two types of functions respectively, and e being a tiny positive constant introduced to avoid zero being divided. The principle of our overshoot gate is similar to that of some momentum-basee methods, e.g.. FISTA (Beck & Teboulle| 2209) and LFISTA (Moreau & Bruna 2017). The fundamental difference between these methods and ours is that, (L)FISTA considers that the scaling factor in a momentum term should be independent of the current inputs (including the previous estimation and y), i.e., being time or at least input invariant, while the output of the overshoot gate is a function of both the previous estimation and y, hence being time-and-ing -inuud-atttttttgnggg.. The design of our overshoot gate may endow the sparse coding network higher capability to learn from its inputs. Experimental comparisons in Section 7 in the Appendix confirm the superiority of our method.
We also note that our convergence analyses in Section 3.1 generalize to 1J > cases with a constant 77, i.c., linear convergence can still be guaranteed, but the asymptotic behavior with learnable and adaptive overshoots should be further explored in future studies.
70x
/
Offe 5) (o)(())
6ftra) x/6)
O
p(++)
wirl--l gilly 1 1110111))
The derivative function (illustrated in blue) of f(x, y) + Ar(x), in which r(x) = ||<||| 1, is monotonic owing to the convexity of [(x, y) and r(x),, and its output should be consistently smaller than the derivative (illustrated in orange) of the upper bound in absolute value. Let æx be the optimal solution to the problem, then we know from the figure that the estimation with standard ISTA update (i.c., 17 = 1) normally 'lags behind".
Figure 2:
4 EXPERIMENTS
In this section, we perform experiments to confirm our theoretical results and evaluate the performance of our gated sparse coding networks. Validations of theoretical results performed synthetic data, and the performance of our method in sparse coding is tested on both synthetic and real data. We set m 250, n 500, and sample the elements of the dictionary matrix A randomly from standard Gaussian distribution in simulations. The position of non-zero elements of the sparse vector T, determined by a Bernoulli sampling with a probability 0.1 (which means approximately 90% of the elements are set to be zero). Different noise levels and condition numbers are considered in the sparse coding simulations. We randomly synthesize in-stream v. and & to obtain y for training, and we let two extra sets consisting of 1000 samples each the validation and test sets, just like in prior works
(Chen et al. 2018 Liu et al. 2019; Borgerding et al. 2017).
For the proposed gated LISTA and other deep learning based methods, we set d = 16 and let (602) not be shared between different layers under all circumstances. The weight matrices (W(0, U01 are not shared either in our method and the coupled constraints W((1) / ( A, Vt, are imposed. For all gates, 1/2 is initialized as 1.0, and then we let the initial value of μı in the inverse proportional function powered gain gate be 1.0 too, since Eq. (12 and [33 indicate 0 S μ4 < 2. Other learnable parameters in our gates are uniformly initialized as 5.0 according to their suggested range of the gates. The training batch size is 64. We use Adam (Cho et al. 2014) and let 91 0.9 and f32 = 0.999. The tuned on the validation set and fixed for all our experiments in the sequel. Our training follows it of Chen et al. 's (2018). That said, the sparse coding network is trained progressively to update more layers, and we cut the learning rate for currently optimized layers when no decrease in the validation loss can be observed for 4000 iterations, with a base learning rate of 0.0005. Training on current layers stops when the validation loss does not decrease any more with the learning rate being cut to 0.00001. More details are explained in Section i in the appendix.
basedd
hyper-paramette
Our training objective for a network with d intermediate update steps is
min (() x.1.2
(19)
'The core codes of this paper could he find in github https::/ggthubb.cmmm

---

Published as a conference paper at ICLR 2020
LIST LISTA OLISTA
Datl of SHNCE CITEOIIII
06-
LOTANS
D4
LISTAAR LISTA GLISTA
02-
-90
10
14
Layone
Namberof Tayer
(a) FPR vs index layers
(b) Ratio lower components
(c) NMSE of layers
Figure 3: Average results confirming our Proposition Darasitioonnnn and Theorem 2 in which intermediate outputs of single network over five runs are reported in (a) and (b) while networks with varying depth are evaluated in (c), over five runs as well. It is plotted from layer indices of in (a) and (b), since the two metries (i.e., false positive rate and ratio of generated non-zero code components that require gains) do not make much sense with initial code estimation (i.e., 0).
1.4
12
12
10
34
Layers
(a)
(b)
Figure 4: Average results over the whole test set confirm our Theorem 1 in which intermediate outputs of a single network is reported. It can be seen that: (a) the gate output converges to 1, and (b) LISTA with our gain gates converges expected. It is plotted from layer index in (a) since gain imposed on the initial code estimation (i.e., 0.)
is the set of all learnable parameters in the sparse coding network that generates (a4) given y. Note that in comparison with the parameter set in a standard LISTA, it also contains the parameters in gate functions. In practice, we are given a
in which θ = (W(*), (OO, ((0,6")) ) U ( U... A (d-1)
set of training samples and opt to minimize empirical loss instead of the one in Eq. (19)
Our evaluation metric for sparse coding is the normalized MSE (NMSE) (Chen et al. 2018):
NMSE(2, xx)) 10 log1o ( x, 1/// 112))
(20)
4.1 SIMULATION EXPERIMENTS
4.1.1 VALIDATION OF THEORETICAL RESULTS
Validation of Proposition T We first confirm Proposition |
In order to ensure that LISTA fulfills the assumption about no "false positive", we introduce an auxiliary loss into the learning object as:
Σ Σ
(21)
jæsupp(r.)
We formally introduce the false positive rate (FPR) as FPR Ssupp Juup((z [2.)) and try to
[supp (3)
approach no "false positive" (i.e., LISTA--fP))) by setting À 5.0 in the experiment, Check Figure
for an illustrative comparison between different models, we see LISTA-nfP achieves almost no "false
positive" in practice in Figure [a) but its convergence slower as demonstrated in Figure 33() which is consistent with our result in Theorem In addition, we also see in Figure (bb) that without "false positive", the code components LISTA estimations are almost always less than those of the ground-truth, which confirms our Proposition
We aim to calculate 1 (+() (t)t)))l using gated LISTA with Validation of Theorem! 1
Fl To accomplish this task, we need to first evaluate the output of our gate function, which is expect to converge to 1 as shown in the theorem. We show such a trend indeed exists Figure 4(a) Consequently, the matrix is supposed
the introduced ReL-u- piece-wise linear gain gate function
The FPR is slightly different from the general false positive rate hy calculating only in the obtained non-zero code components.
*Otee functions he adopted and the same results he obtained.
8

---

Published as a conference paper at ICLR 2020
CLSS's mordoc custve
-20
-10
NNSSE: (485)
NASSEE (489)
NNSS2 -20
-20
-20
Nurther of Bgger
Namiie of
Nurther of Byrer
(a)
(b)
(c)
Figure 5: Comparison of different (a) overshoot gate functions, (b) gain gate functions, and (c) their
combination over five runs. The experiment is performed with SNR=40dB.
to be an identity matrix in the end and we can calculate || - (7 - U A)ll2 as a surrogate. In Figure 4(b) converges to zero in the end and the results confirm the theorem.
Validation of Theorem 2 We apply three kinds of gated LISTA with an alliance of gain gate functions (i.e., what has been introduced in Section [.I.J]. the exponential function, and the inverse proportional function respectively to verify our theoretical results. They were named as GLISTA (which is the abbreviation of gated LISTA), GLISTA-exp, GLISTA-inv, respectively. From FigureBi(c) we see that when the models with such gain gates has no "false positive", all of them are superior to the standard LISTA without "false positive" as well, which is consistent with the conclusion of Theorem 2 In addition, from Figure 3[a) we can also that there actually exist "false positives" in lower layers of GLISTA, but even without the auxiliary loss term, the evaluated FPR of our GLISTA
and it variants approach zero in higher layers, which is in good agreement with Theorem 4
4.1.2 COMPARISON WITH COMPETITORS
Empirical analyses for the gate functions: should be interesting to compare the performance of our gates with different expressions. We test LISTA with different overshoot gate functions introduced in Section 3.2 in Figure 5(a) Both of them are incorporated with their Icarnable parameters being shared among layers. It can be seen from Figure (aa) that the accelerations in convergence and gain in final performance are obvious, just as expected. For LISTA with gain gates, one can check Figure [(b) It can be seen that the performance degrades a lot if either the bias term the μ4 term is removed. We also try different f+(-) functions, including the ReLU-based piece-wise linear one and some possibly more nonlinear ones as mentioned in Section 3.1 We confirm that gate functions whose outputs are relatively closer to the boundary condition may perform better. Yet, it is worth noting that when the outputs of inverse proportional function reach that boundary condition and being applied uniformly to all layers, the performance degrades (see LISTA-inV-e in Figure 5(b).. These results suggest an alliance of gain gate functions practice. We further test combination of gain gates and overshoot gates, despite the mechanism with solely gain gates is already good enough. See Figure 5(c) when overshoots are further incorporated, the convergence on lower layers becomes faster while the overall convergence is not affected much, leading to similar final performance when the model is very deep and superior performance when the model is relatively shallow.
Compared with other state-of-the-art methods: We consider four state-of-ther tthe-arts:: LISTA with support selections (namely LISTA-C-S and LISTA-S, with and without the coupled constraint) (Chen) et al. 2018), analytic LISTA with support selections (ALISTA-S) (Liu et al. 2019), and learned AMP (LAMP) (Borgerding et al. 2017) for comparison, and their official imple emmeettttti are directly used. The syper-parametert are following the papers (Borgerding et al. 2017 Chen et al., 2018). We compare our GLISTA with these competitive methods under different levels of noises (including the signal-to-noise ratios (SNRs) being equal to 40dB, 20dB, and 10dB) and different condition numbers (including 3, 30, and 100, with SNR=40dB). See Figure oor comparisons between LISTA, LAMP, LISTA-S, LISTA-C-S. ALISTA-S, and our GLISTA in some of the settings. Obviously, the introduced gates facilitate LISTA significantly, and the concerned NMSE diminishes the fastest using GLISTA. See our Appendix for comparisons of final performance after multiple runs and the results in other settings (i.c.. SNR: 20dB, 40dB, and condition number: 3). We know from these results that using the gain gates solely can already outperforms existing overshoot gates additionally may further boost the performance, as testified.
while incorporating the
We also try adopting the introduced gates into some variants of LISTA to verify their "generalization ability". Specifically, incorporate the gain gates to LFISTA (Moeau & Brunal 2017) and ALISTA (Liu et al., 2019) to obtain GFLISTA and AGLISTA, respectively. Since ALISTA is suggested to be implemented with support set selection in the original
Applying our method to variants of LISTA:

---

Published as a conference paper at ICLR 2020
LANE
LANE
NNSS (18))
LST14 0U3TA
NNSSE (88)
USTA4
NASSE
GUSTA
-20
20
-10
-30
Numbher of Bipers
Nambeer of
Nurther of Byees
(a) SNR=10dB
(b) condition number=30
(c) condition number=100
Figure 6: Comparison of sparse coding methods in different settings over five runs. Our GLISTA consistently outperforms the competitors in almost all test cases with different numbers of layers.
paper, i.e. ALISTA-S, we also compare with it. The experiment is performed under different levels of noises (40dB, 20dB, and 10dB). As can be seen in Table in which average results along with their standard deviations calculated over five runs are reported, models with our gain gates perform significantly better, which verifies that our method generalizes well.
Table 1: Comparison of LISTA and its variants (with and without gates) under different noise levels.
SNR
LISTA
GLISTA
LFISTA
GLFISTA
ALISTA
AGLISTA
ALISTA-S
40
-38.72.10.09
45.22.10.02
-37,84 37..8410.32
-38.3011..10
-37.86.10.35
-42.30110.13
41.86:10,04
20
0..665:0.099
-2.008:10.03
-20.90:2..02
-22.00=10.07
-17.38:+0.05
-2..13-10.03
-20.00::0.05
10
-9,4210.08
-10.41.0.022
-10.67
-11.2011.00
-8.3910.04
.9.13.10.02
-9.0410.02
4.2
PHOTOMETRIC STEREO ANALYSIS
We now test on more practical task, i.e., photometric stereo analysis, using sparse coding. For a 3D object with Lambertian surface, there are q different light conditions, a camera or some other kinds of sensors can obtain different observations, all with noises caused by shadows and specularities. The observations can be represented as a vector o E R for estimating the norm vector v E I at any position on the surface. It is generally formulated as normalized light directions (q directions), E E R2 is a noise which is often sparse, p E R represents the albedo reflectivity. Our task is to obtain v from and L which is also known. The estimation of e can be considered as a sparse coding problem, and one can use L e) to recover e given the estimation. More detailed descriptions of the task can be found in Xin al.'s paper (2016).
pLu + e, which L E R represents the
In the sparse coding problem, we have Q E Raa33)xq (the orthogonal complement of L) as the dictionary matrix (i.c., A in Eq. (L), E as the sparse code to be estimated, and Qo as the observation (i.e., y in Eq. (T). We mainly follow settings in Xin et al.'s work, e.g. the vectors of T. are randomly selected from the hemispherical surface, except that we test with = 15, 25, 35, and let 40% of the elements of e be non-zero. We use GLISTA here to estimate and the final result for e calculated as (o - e*) e*), where L E paxx is the pseudo-inverse of L and e* is the estimation. Our method is compared with LISTA and two traditional methods where no explicit training is introduced, i.e. the original least square (LS) and least LI, in Table Our evaluation metric is the mean (#: standard deviation) error degree and it is calculated using the bunny picture (Xin et al.) (0166).
Table 2: Mean (= standard derivation) error in degree with different number of observations over five runs.
9
LS
L1
LISTA
GLISTA
35
5.37
1.39
0.0237-0.0022
0.00210110.0000
5.60
2.03
0.0429-0.0065
0.0052410.00044
15
6.09
4.25
0.371=0.046
0.0255:000054
5 CONCLUSION
In this paper, we study LISTA for solving sparse coding problems. We discover its potential weak- nesses and introduce gated mechanisms to address them accordingly. In particular, we theoretically prove that LISTA with gain gates can achieve faster convergence than the standard LISTA. We also discover that LISTA (with or without gates) can obtain lower reconstruction errors under weaker assumption of "fase positive" in its code estimations. It helps us improve the convergence analyses to achieve more solid theoretical results, which have been perfectly confirmed in simulation experiments. The effectiveness of our introduced gates is verified in variety of sparse coding experiments and the sfate-of-the-a performance is achieved. In the future, we aim to extend the method to convolutional neural networks to deal with more complex tasks.
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Amir Beck and Mare Teboulle. A fast iterative Seainkag--hreesolddin algorithm for linear inverse problems. SIAM journal on imaging sciences, 2(1):183-2022 2009.
Mark Borgerding. Philip Schniter, and Sundeep Rangan. Amp- inop-indeeedd deep networks for sparse linear inverse problems. IEEE Transactions on Signal Processing, 65(16):4293 4308, 2017.
Xiaohan Chen, Jialin Liu, Zhangyang Wang. and Wotao Yin. Theoretical linear convergence of unfolded ista and its practical weights and thresholds. In Advances in Neural Information Processing Systems, pp. 9061-9071, 2018.
Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using rmn encoder-decoder for statistical machine translation. In EMNLP, 2014.
Ingrid Daubechies, Michel Defrise, and Christine De Mol. An iterative thresholding algorithm for lincar inverse problems with sparsity constraint. Communications Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 57(11):141311557 2004.
Bradley Efron, Trevor Hastie, Iain Johnstone, Robert Tibshirani, al. Least angle regression. The Annals of statistics, 32(2):407-499, 2004.
Michael Elad Michal Aharon. Image denoising via sparse and redundant representations over learned dictionaries. IEEE Transactions on Image processing, 15(12):3736-3755, 2006.
Ross Girshick. Fast r-cnn. In Proceedings of the IEEE international conference on computer vision, pp- 1440-1448 2015,
Raja Giryes, Yonina C Eldar, Alex M Bronstein, and Guillermo Sapiro. Tradeoff's between convergence speed
and reconstruction accuracy in inverse problems. IEEE Transactions on Signal Processing, 66(7):1676-1690. 2018.
Karol Gregor and Yann LeCun, Learning fast approximations sparse coding. In Proceedings of 27th International Conference on International Conference on Machine Learning, pp. 996. Omnipress, 2010.
Hao He, Bo Xin, Satoshi Ikehata, and David Wipf. From bayesian sparsity to gated recurrent nets. In Advances in Neural Information Processing Systems, pp. 3554-5564, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 770-778, 2016.
John R Hershey, Jonathan Le Roux, and Felix Weninger. Deep unfolding: Model-based inspiration of novel deep architectures. arXiv preprint arXiv: 1409.2574, 2574, 2014.
Geoffrey Hinton, Deng, Dong Yu, George Dahl, Abdel-rahman Mohamed, Navdeep Jaitly, Andrew Senior, Vincent Vanhoucke, Patrick Nguyen, Brian Kingsbury, et al. Deep neural networks for acoustic modeling in speech recognition. IEEE Signal processing magazine, 29, 2012.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521 2015.
Jialin Liu, Xiaohan Chen, Zhangyang Wang, and Wotao Yin. Alista: Analytic weights are as good as learned weights in lista. In Proceedings the International Conference Learning Representations, 2019.
Thomas Moreau and Joan Bruna. Understanding trainable sparse coding via factorization. In Proceedings of the International Conference on Learning Representations, 2017.
Jeremias Sulam, Aviad Aberdam, Amir Bock, and Michael Elad, On multi-layer basis pursuit, efficient algorithms and convolutional neural networks. IEEE transactions on pattern analysis and machine intelligence, 2019.
Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267-288 1996.
Zhangyang Wang, Qing Ling, and Thomas S Huang. Learning deep 10 encoders. In Thirtieth AAAI Conference on Artificial Intelligence, 2016.
Bo Xin, Yizhou Wang, Wen Gao, David Wipf, and Baoyuan Wang. Maximal sparsity with deep networks? In Advonces Neural Information Processing Systems, pp. 4340-4348, 2016.
11

---

Published as a conference paper at ICLR 2020
Xu Xu. Xiaohan Wei, and Zhongfu Ye. Doa estimation based on sparse signal recovery utilizing weighted 11-norm penalty, IEEE signal processing letters, 19(3):155- 158, 2012.
Jianchao Yang. John Wright, Thomas S Huang. and Ma. Image super reportteooution via sparse representation. IEEE transactions on image processing, 19(11):2861222) -8733, 2010.
Jian Zhang and Bernard Ghanem. Ista-net: Interpretable optimization-inspired deep network for image com- pressive sensing. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1828-1837, 2018
APPENDIX
PROOF OF THEOREMS AND PROPOSITIONS
Before we delve deeply into the proof, we first give some importance notations. We define S as the support of the vector Tg, i.e. S supp(æ,)). and let |8| denote the number of elements in the set S. For vector that shares the same size with 2; say 2, we denote by 2s E R| vector that keeps the elements with indices of = in S and removes the others. If the vectors have been introduced with subscripts already, e-g. Vs.
(2s))s to denote vectors obtained in such manner. For square matrix with the same number of row and column as the size of x., say M. M (S, S) is its principal minor with the index formed by removing rows and columns whose indices are not in S. Assume a vector æ with no zero elements, sign(-) is defined as (sign(z)); = z, | i.e. (sign(r)); = 1 when r; > 0, and (sign(x)); = when 2;- < O.
6.1 PROOF OF PROPOSITION 1
Recall that the update rule of LISTA is (0) and
x (1+1) 8800 (w)) (W())(()) + y))y)), t= 1,
(22)
Proof. Recall the definition of S is S = supp(z.). For the shrinking function (x) (ign(x)((a) b(0)+ - b())) where h(2) = 1ff 0, h(2) 1 if < 0, and
h(2) E 11,
We use Mathematical Induction to prove supp(x(0)) c S, = 0. We assume supp(x((0) C S. From the calculation of x; (++1) as W(t) = 1 U A there is
((+1) Syce) ((W()) (1) + g)))
Sp19s ((W(02())) + (z,)),
(23)
Sp00 ((11 - ((1 (1) () - xz)); + (xa)i)
((-
A) (z - xz)); + (x.); (((0 1(x ((+1))).
For Vi of S, (rx). 4 0. Let's assume x (I+1) # 0, then hao (++1) = sign(1) sign(x((+1)) ((+1)), Multiply the two
sides of the Eq. (3 by (zgn(z((+1)) the ((t) ((A) sup,, ||x(() xx there will be
a (++ 1
((I (1()) A) () x.)) sign (-/( 1111) ((())
-(U-U()) U(+) A){=))(((( -x.)) (1-11) mm(A) sup || xx|li 2,
(24)
$ ((A))la(()) 2all1 ((A) (())sup/) ||x - 22 00
z
the inequality holds for ã- 5 < || |0 11] and || (0) S ((A) (because of (tt) E ((A)).
From Eq. 24). we know |z! [++1) 1)
< 0 actually is (e,((++)) 0 which is in conflict with a; ((+1) $ 0.
Therefore, the z. (++1) 0. when é & S, i.c., supp(x c S. As (0) = 0 C S, the supp(x(()) C
S, VL. The no "false positive" property has been proved.
12

---

Published as a conference paper at ICLR 2020
According to Eq.
23
support set of xs and (:(1) are the subsets of S, there is
2; (1+1)
(x=); - (11 - U A) - xz)); 6 h(x (1
Σ (T U ((15)))(((33 A)1s(r)) - -(xa))) -bt0 ((0)((((t)))
(25)
jES
1x; - (xa))i S Σ ( (a) - (xa)))) + +b4
jES
As supp(x((+()) C S, accumulate all |z, (1+1) - (1 in Eq. 25 with i S, there is
[|x(0+11] xslli S Σ ΣE( (((g) A)is(a (1x))) + +S
iES JES
$ Σ Σ
[11- (00) }
10 (xx) + (S
(26)
iES jES,
$ (15)-1))d - ()((()) xx111 + 1516
The second equation is because of UIO W(A), so that [W S m(A) when i * j and
|W, when i j. Substitute 8(() u(A) sup,, ||x(() - xelli into Eq. 26). and take the supremum of Eq. 26 As [S] S s there is
sup I (++1) æ=111 1 S (s 1))((A A) sup [ox(() =2111 + sH((A) sup || x2111 ll1 Zx
Tha
s (2s 1)p(A) sup ||x(1) xzll1
(27)
$ ((2s - 1)M(A))( e+ sup ||z - x2l11.
Let c = log((2s - 1)H(A)), the 12 error bound of t-th layer in LISTA should be calculated as
(1x xzll2 s ||x((t) æalli s sup ||x xzl11
S ((2s - ())( sup -x,l))
x,
(28)
exp(ct) sup ||= xzl11 s sB exp(ct),
where the last inequality is deduced since (xx); < B, and I S s. The linear convergence has been proved.
Refer to the Eq. 25 as xt ((+1) = when $ S, 1 n((+11) < ((x)) and ((+1)) 2 0 hold
certainly. We only concentrate on i S
x (t+1) (It);: = ((I - ((1) A)x - -xa)); ((0) ((z((+11))
(29)
(r+1) ((+ = 0, there must be | ((+1)] = (Ix)i, and x: ((+1) (xx)); (xx)) = O.
If a
If 2; (t+1) 0, the according to Eq. 29). 24 (t+1) (xs); = ((I - (()) A) - xz)): - b(t)
(1--0() -xx)):=-((a sup,, [xx(1) -sal1 5 i.,,, 0 < x (1+1) < (xa)is |z (++1) S (x.)al.
and and (f((+1) (xx); > O.
If x; (t+1) < 0, the according to Eq. (2). ((+1)
(Ix); = ((1 - (((() A)(2(1) - xz)); + 6(t) =
x;
((-U0 (z))
supr, [1x x2sl11 2 0, i.e. > x (1+1) > (rx);, |zا ((+++)) S ((r.))l
and x; ((+1) (I=);= 0.
In conclusion, we can obtain | (1+1) < (xx.)x and (x++)) 2 0 for all the situations.
13

---

Published as a conference paper at ICLR 2020
6.2 PROOF OF THEOREM
Recall that the update rule of LISTA with gain gates is x0() - 0 and
(1+1) Syco (W (o((x ylAg") @ x1()) + 17())) y).
(30)
Proof. We assume that ((0) is vector, i.e., b(t) E R", in our proof to make it more general.
According to definition of the shrinking function 8yc0 (+) and y = Azg. Eq. 10p is
x(+11) Sbce) (W (9c(x(") ylAAa) @ x0) + U()
W 0c(x 2 @ (1) + U y b(t) @ h(x(t++))
(31)
diagl (x 3 21A4)))) + -U(0 b00 o h(x((+1))
Widd (2 ( (r(()) + ((t) Ar, - b00 ④ ((x((+1))
Concentrate on the situation of co. Define gu (x,) ge (2., y Ag (2)
when + co. In the main
body of Theorem
| I. ( diag(an (3ra) )r + ( Ar, (()) o h(r.).
Vx, satisfying 12,1lo S 8 is the fixed point of Eq. 10) when + co. Eq. 31 is
(32)
The equation group of the indices in S in Eq.
32) is
(xx)s (((W( diag(gx(x))) ( A)xx)s 6 o h((2))s)
(33)
(w ()diig(ggg(((..)))) Let (Ia)s + O but (z.)s # 0 so that h((z)))) sign( (z, )s) As W U A and (x(x)))
(U A)(S, ())(2a) bi o h((as)s)
gr (z u|Agg) ) are bounded, the right hand side Eq. 33 is also tend to 0, which
6 0, t oc. As the S can be selected arbitrarily as long as |S|
(34)
S b(t)
also satisfies
8 O,
tー oc.
(35)
Substitute the ( of Eq. 34 into Eq. 33 (xr)s is
) (S,) (iiigg(g
(U A)(S,
(36)
where the ((0 defined at start of this section. Eq. 36
(I (1-U% (14) AS, (1,,)s (S ( ((s)
(1 - (() (0- A)SS, (xa.s = (S
(37)
((x)s) diag(((z))s) ( diag(((r.)s) (M. gx((5))s)
where M (W) (S, 8)) 111 (11) A),
The i-th row and j-th column element in M is
denoted as maj. From Eq. 37 (I,()))) is
((x,)s)
m11
M22
m||
((xx)s)²
(9x(x)))s=
M22
17122
m2
(II))))
M|
S|ssssss
(xx))))
((x))s)2
((x,)s){s)
1 (s)ss (1))s)
1 (m))))
(a,)s)a
(z)sss (s.)s)111
14

---

Published as a conference paper at ICLR 2020
where this equation should hold for all 2e in Assumption bounded, we can conclude that maj = 0, if + j. From Eq. formulated as
1
Assume (rg)s - 0, for gr. (x,) is 38 the final form gu (xx())))) is
gn (xx()))) =
m122
(38)
m| S)
From Eq. 38 we can conclude that gre (xt,); a constant if S, as the could arbitrary subset of {1, n as long [S] S We could deduce that gx (xt2); is constant vi {I, n) and 9u (T,) must be constant vector, i.c.
diag(on(<.)) = D,
(39)
where is an n constant diagonal matrix. The first part of conclusion of Theorem has been proved. Substitute 8(0) in Eq. 34 and (x.g)()((x)))) in Eq. (39 into Eq. 32
Eq. 332 is.
Is = (W()) D + U A)
(40)
Hg Zu
where Z W00 (1) [21, Zz.....
Znd] and the Z, is the i-th column of Z.
Give a -, satisfying only the i-th element of aa is non-zero and all the other elements are equal to zero, i.e., Fg [0, ............ 0)" we,, in which e, basis vector with only the i-th element being and w O. Substitute the x, = we, into Eq. 40 there is
Fs Z3.::
we; 12,,72..... ....... 7,] 10.0......44 .,, ........
(41)
wei whi;
w(e Z,) O.
As the Eq. 41 should hold for Ve * O, we can deduce that Z, As the i is selected arbitrarily,
Z = ( D + (tt) = 12,, Z2 Zn] = (e1,e,,.... ..... en] 1. Thus we have completed the
proof and get
w D (I (1() A) as oc.
6.3 PROOF OF THEOREM? 2
Recall that the update rule LISTA with gain gates (0)) = 0 and
((+1) 8800 (g( y/A @ ,0()) + (7(1)) y).
(43)
Proof. We simplify the (*)) y/A as (x("))), and (x(x ) as Ki (x(1)). According to the definition of gain gate in Eq. (43), we have
((+1)
spmn (Will @ (x() + ((())
(W o (x()) +1(1) Ar,)
(44)
- () o g(x(()) - xx) + x.)) (I - (U(())) A)(((t) o ((x(())
(I
xs) + (()) h(x(t+1))
(t) For the i-th equation in Eq. 44 and $ S, give the value of ((0) ((A) sup,, 1|xx(1) g(x(0)) x. w.lli. there is
Simplify the (1()) @ ((x(1))
F, A gt)l))
((+1) = ((I (()() (
((0)(a((t1)) (e-1))
x
(45)
= ((I - (1()) (x ((A) sup || 2,,(00 (11((l1((tt())))
15

---

Published as a conference paper at ICLR 2020
With almost the same proof process in Proposition
1 could deduce that supp(a!
Fe.
(46)
which is the no "false poistive" property.
Recall the Eq. (44 and substitute the + ki++1 (z:((+1)) = 14-1 (z)(+t)) into it:
(((+1) = -((T-
(1T-U66 [((1) ()) )z)l)))) - (x(((t))())) + Tz.
(1 Net1 (x((+))))= = - -I-- () (A (0)
b(*) ((x((+1))
(47)
+ + ((+22) 2 rip (x)11)))
Agx((+1) (I -U(()) ()
blt) ((z(+()) + x(1+1) o (((((()))).
We shall calculate the non-zero | ب | with the index i. The i could be seperated to two parts.
One is i S but i & supp(x((++)) another part is i S and i supp(z((+ Two kinds of i are discussed respectively.
For E S but i & stpp((((++)) there must be 2r (L+1) 0 and -1 S h(x, < 1. Select the i-th equation Eq. (47). there is
A A (++1) 1)
- 1(11-(())) ()(A xx A)
6l0
S ((A) Σ A + 16600)
(48)
jESJNi
For i E S aadd i E supp(z i-th equation in Eq. (47). there
there must be ((++1) * and ((x(++1)) = =igg(x((+t))), Select the
A (++1)
((I (
(W (M - ((0)((z((t)) (2tt)) + H2 ((+1)
Re (z/
S ((A)
Σ 1 (11 signn) 1)
JESJZ
(49)
+ sign(x! M1x (++1) 16441 (1( (
= =(A)
Σ 1
11) + (1z) (1+1)
1 (2 (2(t+1)) - sign(() ((+1))
K8e
JES
According to the condition in Eq. 12 and 13 the < <x(()) |x|| < 2)) Then, (z)
B(t-1)| b(t-1), there must E7 < 1, so that (x(x) O |z|| - -b(t-)) S mb((t-1) b(( 1) Substituting
it to Eq. 49 there is
A (1 S ((A))
Σ
Agae
(0) + (1a (la((t2)) (a,(tt)))) - 6(0) )sign(..(+t))
jES
$ ((A)
Σ
Agxx11) 11et00t (c((t))) - 6(0)
(50)
jESijti
S ((A)
A 1 (6)
jESijii
Accumulate all the Ag (1+1) (12) with all i E S, and define (()) = |supp(2(()) as the number of
non-zeros elements in (t) there is
$ Σ ((A)
Σ
A0 (1) + (s(l+)), (1S) s(++1)))6(1)
iES
JES,j=i
< Σ u(A)
Σ
A Ague (1) + (s(t+1),, + (18) =(++1)))6(0)
(51)
jES
< (18) 1))((A)) Ag) |||
+ (1((+1) + (15) - s((+1) ))
sup sup | ||1.
x,
16

---

Published as a conference paper at ICLR 2020
Take the supremum of Eq. (51). let (1) denote the infimum of (0) with all of the x, (B, s.)).
and C = log((2s
1 - s. (1 (a)) there is
sup |و ||2 - (s 1)p( (A) sup ||ا
+ +(s!+t) 1) (8 s. (((+1))) pu{ A) sup || و - ||I
< (2s 1 + s/4
(1+1) (1 nj) sup | 2
(52)
< exp(c441) sup | الا(وو11
++1 11 S exp c)sB.
S exp(
c
Eq. 52
gives the upper bound of sups, || (t=1))1)1 111- next we shall deduce the relationship between
| 2alli and it. For the last layer (I-th layer), from Eq. (44), we have
((+1) ((I (0 A)(A x. )) ((A) sup | A (1)
11((1; ((tt) + (xx))..
2i
[t+1) (xz); = ((I - (4 x )); (())((r))))) sup || z
(53)
| (++1) - (x.)dl & 1((I - - A) 1)d + (()) sup || Aو 11
zx
Using almost the same process in Eq. 26 and Eq. 27 we could deduce Eq. (33 that
[|x - -xall S (2s 1)u A)) sup A I|1,
(1x xxll1 < (2s ())(A) sup A x (t-1) 1|1
(54)
< (2s ())(A) exp
c)sB
= exxp
C. + c)sB
where the third inequality sign holds because of Eq. log((2s ())(
52 and the last equation holds because of
As least G: e satisfies, there will be supz, ||x(() xılli I explel)sB. Set to
*B [log( | ) log( (2=-1) When i > to. sup,, ||x(0) - xxal1 I exp(ci)sB < |
(|~((0) - 2.111 111 < |1r/11. then the s (s)p > O, -log(2 1 + 5 ()))((A) < (2g((2s 1))(
In conclusion, from Eq. (54), there is
[|x(()) x=l12 5 110000 -111- < exp Σ c: + c)sB,
(55)
where c 1og((2s 1))(AA),, c, = = when i S to. and a < c when i to.
6.4 PROOF OF THEOREM 3
Proof. For the t-th layer of the LISTA, according to the Eq. 23 we have
((+1) ((I (-(())))) () - IZ)) + (xz); ((0) 1(x ((41))
(56)
x
17

---

Published as a conference paper at ICLR 2020
As we have remove the false positive assumption, supp(x(") I 8. Define 8t Vi E 8() satisfies i E supp(a(!)) but i & S. In order to calculate all of non-zero n. (t+1) (xx); with index i, we divide the i into two kinds, i E S and i E s(++))
If i S, from Eq. (66). we can deduce the same formulation as Eq. (5):
| [t+1] - (x.)sls
Σ JEsupp(e())
(I-U0)
((() A)ss(a) - (Ix)z) + (())
(57)
Σ (I--Ul) (1, (I:))))
b
jesupp(a(t)
If i E s(+1), then the (Ir,); 0 but ui (1+1) then h[*, ((1(t(111))- = sign(r? sign(a((+1)). From Eq. 56 there is
z ((+1) = ((T - A) - -x))); (()((x)()))
(58)
((I - (7(1) (z((() xx,);; sign (z((t
Multiply sign(æ; (1+2) on Eq. (8). we have
|r, | ((1 (-(()) (xx(" x. si)gg (2((t1)) -b(0,
6(0,
| [++1)
+ ((0) -(II ([I-UP) ([I-U() A)(()) x.)) si)ggg) (e+1))
(59)
(Ix + ((() ssign( (xx(+))) = ((T - -U(1) (xx()) - r.));:
which means ((I - ((t)) A) xx))); have the same sign with sign(a; (+1 because (2 ((+1))
and 6(t) 0, i.e.
((I A2(()))))))))))))))) xZ)); I(II U (()=)()))((())))-))) =ss)ss==))
(60)
From the Eq. (58 substitute Eq. 60 into Eq. (58). there is
(1+1) - (x.); (++1)
= sign i
(141)
Σ
(1- (--((t))))(11 (x.);))
jEsupp(z(0)
B(()),
((+1) (xx)xl = -10
= x (++1)
sign( x (1+11)
(61)
Σ
(I- ((- -xx)))) (==0))))(of[-(()))--- 600
jEsupp(a(t)
Σ
[[1- (0() ())(() (2x)))) (())
jEsupp(a(0)
Accumulate all the |x. (2.(+ -(x)) with i E supp(x((+1)) supp((z.) = =((+1) + S, there is
[|x xzlli S
Σ iES + jEsupp(a(O)
Σ
(1 (() (a) (x.))il
(62)
+ (18) (8((+)))))00)
< (18(+1)) + (S)) - xx 11 + ((S) - ()
Substitute the b(0) = we+1 (k++1 (A) sup.., ||-(() - -xall into Eq. 62). and take its supremum of right part:
[2((++]) xxal1 5 ((8(++1) (A) sup [zx(()) -xall1
-1((+))
|w2+ (ks 1 (A)(()) sup ||x - relli
(63)
(1 + |S| + (18) (1Sss(((()))ser (ke+ (0))
(u) (|]( 2z 1.
18

---

Published as a conference paper at ICLR 2020
Take the supremum of left part of (3)). there is
sup [| xzll1 S exp(c(+2 sup |x - xx|11,
(64)
where c++1 supa, log(((((t+i))
S + ([S) 1stt+1))) (k++1 (b-t: According to the definition of wr).), 800) = w (+)) supz, || - Ig xa so that the number of false positive is less or equal than 1 i.e. [8(++1] < k4+1. According to the previous proof, when ((0) = (a(A) sup,, ||x(() - 1, the number of false positive satisfies he+1 = 0. That means that (010) s 1 and (k:O) < 1 when k > The c should be
4+ = sup logllll(sslllo (og(((((((()) + |S| + (1S) - (066
(65)
= log((( + ka+1 + (s kz (u-11wat11 (k++
As assumption of (-+1(-10), 3htt s.t. < 1ot1 < 8, and wi+1 (0) < 1/(s 1.t1).
Select the value of ((4) so that hi+1 = kot1, we substitute to Eq. (65). there will be
4+1 = log((s + ke+11 + (s hio ( (kic+ (0))u(A)
< log((s + k4+1 + (s - --i--))1111 - s- kk+1
(){(
(66)
log((2s 1)p(
Recall the Eq.
64
we have
sup
| (++2) - xxall1 1 S (xp((c41)ssm sup (|x((t) - xzll1
S exp(
sup |1x x
(67)
H+1
S expl
ss
The la error bound of the 1-th layer of LISTA
||x((0) xxa122 I (1x
xxal1 I sup ||x - xxll1 S sB expl
(68)
x,
where of < <log((2s - 1))x(A))
6.5 PROOF OF THEOREM 4
Proof. For the t-th layer given in Eq. (0 according to Eq. (47
x((+1) = ((I U0 A)(Axz())) ((() 112 + x..
(69)
and
(yx((t1== = (I- (1- (0) - ((0) (zx(1())) + (1++1) o (=((((+1))
(70)
As the no false positive is not fit for (1)), (1)) o S. We still define ((t) as Vi E sio satisfies
i supp(z:") (0) but & S and define S(t) as Vi E g(t) satisfies i e S and i (f)) In order
to calculate the non-zero Agx((()) (++1) we divide the into three situations: i E g(++1), & S(++1) but
i E S, and i E S(++1)
'According to the definition of wes we must be a monotonic decreasing function and w. (k(e) when
k 0.
19

---

Published as a conference paper at ICLR 2020
For i g(+1), there must be xi of Eq. (70)
(t+1) 0, and (2r,); + O. Substitute the form of Ki into i-th equation
A (1+1) = ((T - U0, A)
gz (0) - 100h sign(x((+1) + 1 ((1 U AA (0)), (1 Mb+11)6 (i+z)66ssggn(((( (+g
sign(a?
(71)
Agu (1+1)
< [((1 ((DAA(( gz ))s+ (1 -1+++160
we have assume 14: 1
For i & g(++) but i S, x [1+1] 0, and (zx); # O. The i-th equation of Eq. 70p is
A 1 (1+1) ((I ( A) ()); 60 sign(z)) (1)))),)))))
(72)
A 3 ((+1) S 1((1 - ( (0); 164)
For i E S(42), (I.)); =
A0 (1+1)
2i ge (z (z((+))) (1I-
[1
() ([)0U((((()),))
- (1--
14+1)6 (lgg sign(z((+1)),,
(73)
As gi (x ) 2 the sign of (1+1)
x; (x (t) is the same as that of x (++1) Multiply sign(r;) (tttt)
on Eq.
73 there is
I (t-1) (e (++)) = -II-U U0 ()(A))(())))))) ( ((igg - (1 1c+1)6(1)
(74)
: 1) (
((+ 11 (1 - (1+1)6(0) ((I ((I- (1I-0())))) A(A (ig)) sign(()((11)
|x]
which means the (1) A) (0)) should have the same sign with sign (z((+1)), i..,).. i.c
()((((() (tsn(n((++))(((((-CC () "0 - 1(1 Ag S 1((T vl A)(Agx()))) (1 11+1))((1)
A t ((+1) = sign(s (++
me+ me+1 11(00,
(75)
Accumulate all the | ( with i E (upp(x((++)) Usupp(xs), there is
|| [1ggo(++1)))
Σ (
g (+t2))
Σ
- ))al ((8)ttt)) -M++1)
(2
(76)
((S) - 13(4+1) 1)6(()
< ((8) + (8 (u(A)\AA (1) + ||(t(++)](((tt)) (1+4411)
+ ((S) - ())
Substitute the ((0) w/+ (k 10) A) sup... | into Eq. 76). Take the supremum of the
right part of Eq. 76
|
(++1) 1)
11a S ((S) + 18 (s((+1) sup 25ا0011 + + (s(++)) - (441) (SS)
Te
(kut) sup 110,z00011
(77)
S (SS) + (1(+881 ((18((+1) - (5(C+) - me+1)
(Sl) (((tt)) (1 (k ())) sup - (1) |||.
Let
4+1 sup + | + + ([(((++1]- - -1 -m41)
(78)
+ ([S) (6
20

---

Published as a conference paper at ICLR 2020
Take the supremum of the left part of Eq.
77 the supz, | (1+ || satisfies
sup || A A
exp(c(+1) (is4)ssss))) sup A A
||1
++1
I expl
sup || ,
(79)
H+1
S exp(
Σ 4 B
After the upper bound of |A ||2 is deduced, we shall consider about the relationship between a((+1) - 3g and Agz(1)
if 8(+1)), (2ss); O, and x.
[t+1) # 0. The i-th equation in Eq. (69 is
z a((+11)
(z,); -
6(0) sign (1((t))) ((I - 1 -00,)
(80)
According the similar malyses in previous, the sign of ((1 U ()()))((A (A (o() is the same as
sign(x; (++1)) ) 2t l)+1) (xx); satisfies
2 (++1) - (x:.); 2((+11) (I((1 U((A)) 2 - 69 siggnn(())
(81)
|a (t+1) (x.)sl = | 1((T - - A) gr ))s - -80
i 8, the s;
((+1) (ara); satisfies
|r] (n((t11) - (x.))il S ((( Ul) ())))=11)) + b(0
(82)
Accumulate all the |0 (I+1) (xE) with i E supp(r((++)) U (s,) there is
[|x((++1) xxll1 S
Σ 1((I ((1 A) y ))&l + (IS) 1)(++)))1(011
iEsupp(r(t=D)
(83)
s (15) + ()(+))))(()))))))))))))))))>)))) (
||: + (IS) - ()
Substitute the 6(0) (1+1(4+110)pp44 sup.. 1aa.11111 ااممو || into Eq. 83 take the supremum of (1 ||x(0++]) - 21,l1 S ([8) + + (8t++ (u((A) sup |Agx(1)) ||2
sup
+ (81) (1 (010)))0111111 (k) sup ||امo
(84)
$ (sl) + 1| + (|S) - s DW1++ (ke (k)+1 sup ,0
2,
Let c²* be
= log (|S) + [(() + (IS) - | (t)
(85)
Substitute Eq.
79h and 85 into Eq. (84) the l2 emror bound of LISTA with gain gate should be
(1) 2. 21 I (ta) ==al1 I explc"")
sup | | (t-1) l|2
(86)
expl Σ c + d' )sB.
Then we shall discuss the value of e, and c²". Let to flog( (BB / log( (25-1)m(a))1 )1
When i I tu. μ4 0, which means the gain gate does not exist, there is
& = sup log(((()) + | + (IS) -
(K)11))))(())
x²
(87)
= log((s + ki+1 + (s- ki+1)wi+ (k++ (k)+1)))))((A))
21

---

Published as a conference paper at ICLR 2020
3kj, s.t. < kb < and wi (k)](( 1 - 1/(s - kj). According to main process in the proof Theorem let K; = kg. h; < s, and C = cj < log (A))
When i > to. sup,, |r,(0 - xxIlı < sB exp(ci) 5 o v minpesppp(..)) (( As the minimal absolute value of æ, is less or equal than a, g() = S. Select the 6(() so that K₂ = O, (k,kk s 1. Recall the form Eq. 78). As sup,, |S|| k 0. and of is
4 sup log + |8() + (IS) - (us
2e
(88)
x log((s + s(1 - p:))
As - wi(s/0) < 1
log((s + s(1 - (4) 14)) A))
< log((s + mmm (s]))))
(89)
log((s + sk)(k) ()) (A)
log((s K/ (s ww, (k(1)))u(A)) =
i.., of < <... As wx(+)) is the monotone decreasing function, the second "<" in Eq. 89 holds since kj < and the last "<" holds since kg > 0.
|S] S 8, and | < 4t 1/(s- A.)). Select ((() to let K2 Kg- According to the similar derivation in Theorem 3 d' in Eq. (5) should satisfies e'" < log((s + ke (s he (k))(((())))(() < +log((2s ())x(A))
According to the assumption of wx(- 3kj. s.t. < kg < s and
(kg O
All of the conclusions in Theorem 4 have been proven.
6.6 PROOF OF PROPOSITION 2
Recall that the update rule of ISTA is x (0) = 0 and
x ((+1) = s2/ (x - V V=((x(())/>)
(90)
We have the following theorem which analyzes the update rule of ISTA and
17 == arg min f(n(x(0+1) - (0) + x()) + Al[n(a - x(1)) + x 111
(91)
Proof. According to the analysis in Section in the main paper, x (1+1) is the solution of minimizing the upper bound Uxx),
U(x) = f(x(") v) + (z vz) + 7 211z= -|0=-x(0)
+ Ar(x).
(92)
The sub-uuudeee gradient of U(x) is
0,U(x) (z)( + 7( - 211) 10xr(x).
(93)
As the (t--1) is the optimal solution to minimizing Eq. 992 2 O,U((((tt)) satisfies
0 E a (z(((()))))
(=
+ (zx (1) + (0
(94)
where r(x)= = |||||1- According to the definition of the sub looo-gradentt,, (dur(z)) E [-1,1] when when 2; O, and (0.r(z)); when x, 0.
z; 0. (Orr(z)),
From the Eq. 944. there must exists r1 E r(x) such that
vxf(x()) + (z - (1)) + \r 0,
(95)
where (r1); = if x;
(t+1) > 0, (r1); = -1 if x ((+1) < O. and - 1 (r1); S 1ff (ff < 0.
((+1)
According to the definition of 17" in Eq. 91 we define new function 0(m) as
((1) ((1(x (1)) + (() v) (e-m(2((e11) - 200) (0) |11
(96)
22

---

Published as a conference paper at ICLR 2020
Notice that {()) is the line search function of f(r 3) A||z||1- According the law of convex optimization, as f(x; y) + +|| is a convex function, the ((1) must be also a convex function about 77. The sub-gradient of ((n) is
0,0(1) (x(1+1) - ( V
- x1)) + x(t))+
(97)
A(x - (0 ( (((11))))))))))))))))))))) x(1)) x()")
The 17" actually is the value to minimize (1) in Eq. 96 There must be
0 e 0,0(1²))
(98)
From Eq. 197 the sub-gradient function of ((n) when v 1 is
010(1)
-xx(1+1) - , (V (Vef(xl(tt)) (0g((zl(t11))
(99)
(x(((11) - - (V - +zl(((()) =(x(11) - (V2 (V2 x00) + vof(x(()) + -)0r(z((++1)),,
(0,r(z((+1))
where the last equation holds for Lagrange's mean value theorem and ( E R Substitute v=I(x! in Eq. 95 into Eq. (99). the 0,,(1) is
0,0(1)
(cx((+1) x
x(0) - ((x((11) - -x(0) Ar1 + 10gr(z((t1))
=(x((+1)- 2(0 - -7T](x(t+1) =1(0) + -(0r)(((+2))-- 11))
(100)
-(2(0+1) - -x0)(--)))) x10)+
A (1(t1)1) 2(0 -(1r))))
where the sub-gradient (t(x()+1)) is set. For all r* Or(x(tt1),,
(z(1+) - (V) - -1)(2((11) -1(1))
(++ (a(tt)=2())0 xz') - (ri)i) E 0,0(1).
(101)
We prove 17" 2 according to the counter-evidence. According to the properties of convex function and the sub-gradient, assume 17" < 1, s.t. e 0n"(""), Vra E (,0(1), there will be
re 0.
However, T1 Or(x((+1)), substitute = Ör (x(((+)))) into Eq. 100 The corresponding element in sub-gradient when ri is
(()+ (V (+) -(())) E 0,0(1). According to given condition 7/ (²f(x) > 0, < O. which is in contrast re O. Therefore, the conclusion 1)* Z 1 is obtained.
Moreover, consider about the last term of Eq. 100 i.e.
E (++1)
(1) ((00((
(102)
If (1) c supp(x((+1), there are two situations about index i. 1) supp( there will be x! ((-1) 4 0 and (Or(2()+))), (ri), sign(a (tt() 2) i & supp(x((++)) and & (!)) there will be x! (t+1) x.!1 O. Both conditions will make the term (a! (f+1) (((())))(((((((((((e(((( ((O(((()))))))))))) (r1))) in Eq. (102) be O. Therefore, Eq. 102
Eaa!
(++ x ((Or(a (ri))) 0.
(103)
According to the given condition 71 - V+f(x) > 0, 0,,(1) should be a number but not set and (11(1)= = (x((++1) - (V? - (z)())))) (1)) 0. As the ((1) convex function, there must be 17" because of 0 0,0(1"). The conclusion 1)* is derived.
23

---

Published as a conference paper at ICLR 2020
ISTA with overshoot (A 0.01)
ISTA ( = 0.01)
ISTA with ovenshoot (1 0.025)
NMSE (dB3)
-10
ISTA (1 - 0.025)
-2
-30
40
200
400
600
800
Number of iterations
Figure 7: Experimental results validating our Proposition ISTA "lags behind"..
It can be observed that the update of
USEA
-10
-10
NMSE (ci))
(MI1:
-20
-20
LINT
10
Namber of layser
Number layers
(a)
(b)
Figure 8: Comparison of overshoot and gain gate with similar methods five
LSSA ALSTAS
LOTA A.RIS
AUSI4A
200
N0USE (I))
LERINE
LoTAch-o)
N06SE
-40
-00
30
36
-50
6.7
-00
30
Ripers
(a) SNR=20dB
(b) SNR=40dB
(c) condition number=3
Figure 9: Comparison of sparse coding methods under different settings over five runs. Our GLISTA consistently outperforms the competitors in almost all test cases with different numbers of layers.
7 MORE SIMULATION EXPERIMENTS
Validation of Proposition 2. Some experimental results are given here due to the length limit of the main body of our paper. One might also be interested in our Proposition] [ hence we first conduct an experiment confirm it. We adopt ISTA with an adaptive overshoot and compare it with the standard ISTA for sparse coding. The adaptation is obtained via enlarging the step size from 1.0 through backtracking line search (see section 7 for more details). Figure 7 demonstrates that our overshoot mechanism facilitates ISTA optimization, and such a result confirms Proposition 2
Comparison with similar methods: As mentioned in the main body of the paper, the overshoot gates is proposed do address insufficient step size, which is similar to the motivation of (L)FISTA. LIHT and support select can also be considered as special cases of our gain gates (by letting 14 = in the inverse proportional function). We compare these similar methods with our overshoot and gain gates Figure It can be seen that when compared with LISTA, LFISTA converges faster in lower layers, and our overshoot gates also show such advantage. When applying to deeper layers, LFISTA converges quite slow while the overshoot gates still perform well, which indicates that the time-varying property is beneficial in practice. LISTA with our gain gates is obviously better than LIHT as shown in Figure 8(b) and sufficient experimental results in the paper also prove that the gain gate outperforms support select (e.g., in LISTA-C-S and LISTA-S).
24

---

Published as a conference paper at ICLR 2020
Comparison under less challenging settings: Now also give sparse coding results under the described less challenging settings on the noise level and the condition number in Figure 9 Com- pared with LISTA-CP, LAMP, LISTA-SS, and LISTA-CP-SS, remarkably better with less ill-posed dictionary matrices and less noises. Table [ and 4 report the statistical means and standard deviations of five runs using different methods. It can be seen that the improvement achieved by our GLISTA is significant.
gated LISTA (GLISTA) performs
Table 3: Comparison of the final NMSEs under different noise levels with d = 16. The condition number the dictionary is not specifically constrained.
SNR
LJSTA
LAMP
LISTA-S
LISTA-C-S
ALISTA-S
GLJSTA (ours)
40
-38. 0..
-36.7710..0
41.99110.99
-44.8510.02
41.8610.04
-45.22 0.002
20
-18.654.009
-18.66:10.09
-20.6410.066
-22.8410.022
-20.00-0.055
-23.08.10.03
-..42=0.08
-9.66
-9.84+0.02
-11.06++0001
-9.04=0.02
-11.41++0.02
Table 4: Comparison the final NMSEs under different condition numbers with d = 16. The noise level chosen SNR=40dB for all the tested condition numbers.
Con. num.
LISTA
LAMP
LISTA-S
LISTA-C-S
ALISTA-S
GLISTA (ours)
3
-39.03=10.54
-37.26:20113
43.122+0.06
-44.90+0.03
-33.88:0.26
-45.33=:0.04
30
-29.65.10.89
-28.4410.31
-32.30.10.17
-38.36.1.55
-31.50.10.15
-3.661.10.44
-21.39110.75
-22.2310.18
-27.0810.57
-27.9410.34
-27.1010.02
-3..07:10.64
PROGRESSIVE TRAINING AND ADAPTIVE OVERSHOOT
Our training mostly follows it of Chen et al.'s (2018), and some key steps are listed here: 1) The model is trained progressively to include more layers during the training phase. At the very beginning. only learnable parameters in the first layer is considered, and parameters in the second layer is only included once training on the first update converges, so as the third and higher layers. 2) Training after including the t-th layer is split into three stages, with an initial learning rate of 0.0005 to optimize its own learnable parameters first, and learning rates of 0.0001 and 0.00001 to jointly optimize all learnable parameters from the 0-th t-th layers in the second and third stages, respectively. We move to the next stage once no performance gain is observed on the validation set for 4000 iterations. 3) With the three stages done the t-th layer, training moves to include the (t + 1)-th and the same three stages of training are performed.
We perform adaptive overshoot in the experiment confirm Proposition 2. The algorithm is summarized Algorithm [ Most of input variables are introduced in the main body of our paper and F is given as the step size for performing line search. The whole algorithm procedure is very similar to the famous backtracking line search. The step size for sparse coding is updated by r until the objective function fz. 3) Ar(x) does not decrease any more.
Algorithm ISTA with adaptive overshoot.
Input: The dictionary matrix A, observation y. initial step size n/o 1.0 for sparse coding, step size 7 = 1.05 for line search, and a maximal number of iteration. Output: output result
1: [0) 0:
2: for 0, ,.. 1
3:
=(() = =8x/((1 - A A/ A/7)x((-11 y///));
4:
Ip =z(t), . 100;;
5:
I, =T(((t) -(())- r!t)
6:
while fo(#p, y) 2 lo (o 1 do
7:
Jp Fcs 1) T4];
8:
F. = n (1) (1) (t) 11);
9:
(1) = xpi
10:
return z: (1))
25

---

Published as a conference paper at ICLR 2020
REFERENCES
Amir Beck and Mare Teboulle. A fast iterative Seainkag--hreesooddin algorithm for linear inverse problems. SIAM journal on imaging sciences, 2(1):183-2022 2009.
Mark Borgerding. Philip Schniter, and Sundeep Rangan. Amp- inpp-indeeedd deep networks for sparse linear inverse problems. IEEE Transactions on Signal Processing, 65(16):4293 4308, 2017.
Xiaohan Chen, Jialin Liu, Zhangyang Wang. and Wotao Yin. Theoretical linear convergence of unfolded ista and its practical weights and thresholds. In Advances in Neural Information Processing Systems, pp. 9061-9071, 2018.
Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using rmn encoder-decoder for statistical machine translation. In EMNLP, 2014.
Ingrid Daubechies, Michel Defrise, and Christine De Mol. An iterative thresholding algorithm for lincar inverse problems with sparsity constraint. Communications Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 57(11):1413-1557 2004.
Bradley Efron, Trevor Hastie, Iain Johnstone, Robert Tibshirani, al. Least angle regression. The Annals of statistics, 32(2):407-499, 2004.
Michael Elad Michal Aharon. Image denoising via sparse and redundant representations over learned dictionaries. IEEE Transactions on Image processing, 15(12)33736-3755, 2006.
Ross Girshick. Fast r-cnn. In Proceedings of the IEEE international conference on computer vision, pp- 1440-1448 2015.
Raja Giryes, Yonina C Eldar, Alex M Bronstein, and Guillermo Sapiro. Tradeoff's between convergence speed
and reconstruction accuracy in inverse problems. IEEE Transactions on Signal Processing, 66(7):1676-1690. 2018.
Karol Gregor and Yann LeCun, Learning fast approximations sparse coding. In Proceedings of 27th International Conference on International Conference on Machine Learning, pp. 996. Omnipress, 2010.
Hao He, Bo Xin, Satoshi Ikehata, and David Wipf. From bayesian sparsity to gated recurrent nets. In Advances in Neural Information Processing Systems, pp. 3554-5564, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 778.778, 2016.
John R Hershey, Jonathan Le Roux, and Felix Weninger. Deep unfolding: Model-based inspiration of novel deep architectures. arXiv preprint arXiv: 1409.2574, 2574, 2014.
Geoffrey Hinton, Deng, Dong Yu, George Dahl, Abdel-rahman Mohamed, Navdeep Jaitly, Andrew Senior, Vincent Vanhoucke, Patrick Nguyen, Brian Kingsbury, et al. Deep neural networks for acoustic modeling in speech recognition. IEEE Signal processing magazine, 29, 2012.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521 2015.
Jialin Liu, Xiaohan Chen, Zhangyang Wang, and Wotao Yin. Alista: Analytic weights are as good as learned weights in lista. In Proceedings the International Conference Learning Representations, 2019.
Thomas Moreau and Joan Bruna. Understanding trainable sparse coding via factorization. In Proceedings of the International Conference on Learning Representations, 2017.
Jeremias Sulam, Aviad Aberdam, Amir Bock, and Michacl Elad, On multi-layer basis pursuit, efficient algorithms and convolutional neural networks. IEEE transactions on pattern analysis and machine intelligence, 2019.
Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267-288 1996.
Zhangyang Wang, Qing Ling, and Thomas S Huang. Learning deep 10 encoders. In Thirtieth AAAI Conference on Artificial Intelligence, 2016.
Bo Xin, Yizhou Wang, Wen Gao, David Wipf, and Baoyuan Wang. Maximal sparsity with deep networks? In Advonces Neural Information Processing Systems, pp. 4340-4348, 2016.
26

---

Published as a conference paper at ICLR 2020
Xu Xu. Xiaohan Wei, and Zhongfu Ye. Doa estimation based sparse signal recovery utilizing weighted I1-norm penalty, IEEE signal processing letters, 19(3):155- 158, 2012.
Jianchao Yang. John Wright, Thomas S Huang. and Yi Ma. Image super-resolution via sparse representation. IEEE transactions on image processing, 19(11):2861-22
2010.
Jian Zhang and Bernard Ghanem. Ista-net: Interpretable optimization-inspired deep network for image pressive sensing. Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, pp. 1828 1837, 2018.
27


Reviews:
[{"review_id": "SJlzRVohKH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "1. Summary\nThe authors propose extensions to LISTA with the goal of addressing underestimation (by introducing “gain gates”) and including momentum (by introducing “overshoot gates”). The authors provide theoretical analysis for each step of their LISTA augmentations, showing that it improves convergence rate. Their theoretical statements are empirically validated and then a numerical comparison is performed between the most interesting LISTA variants. Their proposed GLISTA performs favorably, especially for networks of depth greater than 10.\n2. Decision and arguments\nThe theory given is quite comprehensive and seems solid. Moreover it’s motivated by and helps real problems, namely L1’s well-known underestimation and LISTA’s lack of momentum. On top of that, the numerical results not only show your GLISTA outperforming others, but that by adding gates to other LISTA variants you can get better results. On the other hand (see details in the Questions section), there is some critical information missing from the empirical section which makes the results non-repeatable. \nTraining is not described, i.e. hyperparameter searches and stopping criteria. A couple of the plots validating theory are difficult to understand. The datasets used are synthesized and tiny, only 1000 samples (training/testing/validation sets are not described) and 250x500 dimensions. That means your network has many more parameters than data samples unless I am mistaken.\nSo I have given weak reject because the paper has strong theory but weak experiments making it hard to trust the conclusions. I really want to hear back about the questions raised below.\n3. Questions \na) Just before eqn 12 you say that gains greater than 1 can be more appropriate. Am I understanding this correctly: *before* shrinkage you want to apply a gain on code elements that are “truly” nonzero, in order to cancel out the imminent L1 penalization? And you will learn to predict those code elements via parameters Lambda?\nb) Just before Section 4, you describe the difference between yours and Moreau & Bruna’s momentum taps. If I understand correctly they have a matrix called W_m^(k) which is multiplied onto the previous iterate—but for each layer / time unit (k), the matrix may vary by learning (note that in the main body of their paper they don’t explicitly use ^(k) notation, but it is explained to be the same as the other LISTA parameter matrices which vary with time, and is made explicit in the appendix). So I think their momentum is in fact time-varying. Moreover it is certainly dependent on the previous iterate, using the function f(z^(k-1)) = W_m^(k) * z^(k-1). Did you mean something else by that? In what sense do you have a higher capacity—do you have more parameters?\nc) If I understand correctly, in Figure 5a, 5b, for each point you have trained independently an N-layer GLISTA. Then you observe properties of your learned parameters.\nFor 5a: how do you compute the “output” of the gain gates? What is the input that gives this output?\nFor 5b: which ‘t’ is used to calculate ||W(t)D-I+U(t)A||? Or did you just train a single 15-layer GLISTA, and the x-axis is just ‘t’?\nd) Could you tell us more about the hyperparameter tests for every method? How do we know it was a fair comparison? There are no error bars, but from experience I know that training LISTA type networks can be a pain. What algorithms did you use? Stopping criteria? Some plots start at zero layers (4c, 5b, 6a-c) and some start at 1 layer… \ne) Interesting that in your real-data example, the sparse vector e has more non-zeros than zeros, is that really sparse? What dictionary A did you use, then? By your own description this task does not fit the sparse coding model you have analyzed…. Am I misunderstanding?\n4. Additional feedback/ minor comments\na) Add reference for DOA estimation application\nb) You should put something like “we prove this in the supplement” for props and theorems. Otherwise to readers less familiar with the literature it will seem like you forgot to put a reference.\nc) It seems unnecessary to put ||epsilon||<= 0 , instead of epsilon=0.\nd) Basically I think you should explain what your gate is before providing proofs about it. It would be useful to see a plot of the function g and/or kappa so provide some intuition about what you are doing to the architecture (nonlinear? Linear? Threshold? Etc.). Capital “Lambda” is not defined until after theorems are provided about the functions g, kappa, f. In fact it seems like kappa is only useful for the sake of proofs. The first time through, I over-read the statement “All the learnable parameters are thus collected as Lambda…” just before Section 3.1.1 because I was thinking “Why isn’t Lambda in the definitions of f/g/kappa??”. Anyway it makes perfect sense when you define it clearly as after Eqn 18.\ne) At the beginning of Section 3.2 you have a clause “the over-shoot gates act more like on the output”, which doesn’t make sense.\nf) Figures should be approximately self-explanatory—but “Ratio of lower components” is not explained in the caption of Fig 4b. Although I greatly appreciate that you have made the actual plot lines/markers very easy to see! Should these results be averaged over many training attempts with error bars?\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "S1eZe6Sa9H", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposed two novel gates to improve the convergence speed of the learned ISTA (LISTA) algorithm for sparse coding. The first gate is designed to address the problem that the output of the LISTA algorithm usually has a lower magnitude compared against the ground-truth. To address this, the paper proposed a gain gate to increase the magnitude of a layer in the LISTA algorithm. The second gate is designed to further improve the convergence with a technique similar to the momentum but with a time-varying coefficient. \n\nThis paper provides rigorous theoretical justifications for the observations that motivate the two gates in two propositions. It also provides theoretical guarantees for the first gain gate under practical assumptions. \n\nThorough synthetic experiments are conducted to empirically validate the proposals as well as the theorems. The effectiveness of the gates is also proved in a real-world computer vision task, photometric stereo. \n\nGiven the thoroughness of the theoretical and experimental justifications, I strongly recommend the acceptance of the paper.\n\nDespite the strength of the paper, I have the following suggestions and questions regarding the two gates proposed by the paper:\n\n1. The second proposed gate, the overshoot gate, lacks theoretical justification and is not as well studied as the gain gate. The experiments for this gate are not included in the main text but got placed in the appendix. I suggest squeezing some of them into the main text to show a complete picture about the overshoot gate. If there are more theoretical results about the behavior of the overshoot gate, the author should include it in the paper; otherwise, the author should clearly states this limitation in the main text of the paper.\n\n2. The author proposed two gates to address two different issues of the original LISTA algorithm. However, the two gates are only applied seperately to modify the LISTA algorithm; they have not been integrated into a single concise algorithm. It would strengthen the paper if the author could provide a further discussion on how the two gates can be combined to address the two issues in one algorithm.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}, {"review_id": "BkeidSdTFr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis paper is focused on solving sparse coding problems using LISTA-type\nnetworks. It discusses the weakness of the ``no false positive'' assumption in\nprevious works and the weakness results in underestimated code components. The\nauthors propose a ``gain gating function'' to mitigate the weakness. Moreover,\nthe paper incorporates another ``overshoot'' gating function inspired by\nmomentum-based methods. Both contributions are supported with theoretical and\nempirical results. Numerical experiments show that the proposed model is\nsuperior to previous works especially in cases with high measurement noises or\nill-composed basis matrix. The paper is well written and easy to follow, and the\nempirical results are impressive.\n\nI really like the relaxation of ``no false positive'' assumption as in real world\napplication, learning-based algorithms may find it difficult to keep satisfying\nthe assumption while maintaining good empirical performance. And this relaxation\ncontributes to guarantee the convergence in a more real scenario.\n\nI think in (Chen et al., 2018), the support selection technique serves to\nmitigate the problem of underestimated code components as it bypasses the\nthresholding function for codes with large magnitudes. The empirical results\nalso show that in many cases LISTA with support selection has comparable\nperformance. I don't know if LISTA with support selection also suffers from\nthis underestimation problem severely.\n\nQuestions:\n\n1. The theorems in Section 3.1 hold without overshooting mechanism, i.e. eta==1.\nProp. 2 says that for one step of iteration, the optimal updates requires\novershoot. When the gain and overshoot mechanisms are combined, however, will\nthe theoretical convergence still hold?\n\n2. I don't have a very good understanding of why GLISTA performs so well given\nill-composed basis matrix compared to previous works. Could there be some\n(intuitive) explanation as to this based on the theoretical results?\n\n3. More details about the training process should be included. For example, I\ncan guess the loss function used for the training. But it is confusing not\nmentioning it at all in the paper. Some might think the objective funciton in\neqn (2) but the convergence analysis is with respect to the ground truth sparse\nvector. Also, the training scheme and some hyperparameter selection should also\nbe stated at least in Appendix.\n\n\nOverall I hold very positive attitude towards this paper due to its theoretical\ncontributions and good empirical results.\n\n================================\nUpdate: the authors addressed my questions well and I will keep my positive decision on this paper.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper extends LISTA by introducing gain gates and overshoot gates, which respectively address underestimation of code components and compensation of small step size of LISTA. The authors theoretically analyze these extensions and backup the effectiveness of their proposed algorithm with encouraging empirical results. All reviewers are highly positive on the contributions of this paper, and appreciate the rigorous theory which is further supported by convincing experiments. All three reviewers recommended accept.

Decision: Accept (Spotlight)