Learned ISTA with Error-based Thresholding for Adaptive Sparse Coding
Authors: Li Ziang
Wu Kailun
Yiwen Guo
Changshui Zhang
Venue:  (2021)
Keywords: Sparse coding
Learned ISTA
Convergence Analysis

Abstract: The learned iterative shrinkage thresholding algorithm (LISTA) introduces deep unfolding models with learnable thresholds in the shrinkage function for sparse coding. Drawing on some theoretical insights, we advocate an error-based thresholding (EBT) mechanism for LISTA, which leverages a function of the layer-wise reconstruction error to suggest an appropriate threshold value for each observation on each layer. We show that the EBT mechanism well-disentangles the learnable parameters in the shrinkage functions from the reconstruction errors, making them more adaptive to the various observations. With rigorous theoretical analyses, we show that the proposed EBT can lead to faster convergence on the basis of LISTA and its variants, in addition to its higher adaptivity. Extensive experimental results confirm our theoretical analyses and verify the effectiveness of our methods.

Under review as a conference paper at ICLR 2021
LEARNED ISTA WITH ERROR-BASED THRESHOLDING FOR ADAPTIVE SPARSE CODING
Anonymous authors Paper under double-blind review
ABSTRACT
The learned iterative shrinkage thresholding algorithm (LISTA) introduces deep unfolding models with learnable thresholds in the shrinkage function for sparse coding. Drawing some theoretical insights, we advocate an error-based thresh- olding (EBT) mechanism for LISTA, which leverages a function of the layer-wise reconstruction error suggest an appropriate threshold value for each observation on each layer. We show that the EBT mechanism well-disentangles the learnable parameters in the shrinkage functions from the reconstruction errors, making them more adaptive to the various observations. With rigorous theoretical analyses, we show that the proposed EBT can lead to faster convergence on the basis of LISTA and its variants, in addition to its higher adaptivity. Extensive experimental results confirm our theoretical analyses and verify the effectiveness of our methods.
INTRODUCTION
Sparse coding is widely used in many machine learning applications (Xu et al. 2012 Dabov et al. et al., 2010 Ikehata et al. (012)). and its core problem is to deduce the figh-dimensional sparse code from the obtained low-dimensional observation, for example, under the assumption of y Ax, + 6, where y RT is the observation corrupted by the inevitable noise E IRm 2, T is the sparse code to be estimated, and A E TR is an over-complete dictionary matrix. To recover T, purely from y called sparse linear inverse problem (SLIP). The main challenge for solving SLIP is its ill-posed nature because of the over-complet modeling, i.c., m < n. A possible solution SLIP can be obtained via solving a LASSO problem using the regularization:
min ly AxI12 + A||z||1-
Possible solutions for Eq. 11) are iterative shrinking thresholding algorithm (ISTA) (Daubechies) ct al. 2004) and its variants, e.g., fast ISTA (FISTA) (Beck & Teboulle 2009). Despite their sim- plicity, these traditional optimization algorithm suffer Trom slow convergence speed in large scale problems. Therefore, Gregor & LeCun (2010) proposed the learned ISTA (LISTA) which was a deep neural network (DNN) whose architecture followed the iterative process of ISTA. The thresholding mechanism was modified into shrinkage functions in the DNNs together with learnable thresholds. LISTA achieved superior performance in sparse coding, and many theoretical analyses have been proposed to modify LISTA to further improve its performance (Chen et al., 2018 Liu et al. 2019
Zhou et al. 2018 Ablin al. 2019 Wu al. 2020).
Yet, LISTA and many other deep networks based on it suffer from two issues. (a) Though the thresholds of the shrinkage functions in LISTA were learnable, their values were shared among all training samples and thus lack adaptability to the variety of training samples and robustness to outliers. According to prior work (Chen al.) 2018 Liu et al. 2019). the thresholds should be proportional to the upper bound of the norm of the current estimation enror to guarantee fast convergence in LISTA. However, outliers with drastically higher estimation errors will affect the thresholds more, making the Iearned thresholds less suitable to other (training) samples. (b) For the same reason, it may also lead to poor generalization to test data with different distribution (or sparsity (Chen et al.) 2018)) from the training data. For instance, in practice, we may only be given some synthetic sparse codes but not the real ones for training, and current LISTA models may fail to generalize under such cireumstances.
In this paper, we propose an error-based thresholding (EBT) mechanism to address the aforemen- tioned issues of biste-based models to improve their performance. Drawing on theoretical insights,

---

Under review as a conference paper at ICLR 2021
EBT introduces function of the evolving estimation error to provide each threshold in the shrink- age functions. It has no extra parameter to learn compared with original LISTA- models yet shows significantly better performance. The main contributions of our paper are listed follows:
The EBT mechanism can be readily incorporated into popular sparse coding DNNs (e.g.- LISTA (Gregor & LeCun 2010) and LISTA with support selection (Chen al. 2018 to speed up the convergence with no extra parameters.
We give a rigorous analysis to prove that the estimation error of EBT-LISTA (i.c., a com- bination of our EBT and LISTA) and EBT-LISTA with support selection (i.e., combina- tion of our EBT and LISTA with support selection) is theoretically lower than the original LISTA Grreorr& LeCun 2010) and LISTA with support selection (Chen respectively. In addition, the introduced parameters in our EBT are well-disentangled from the reconstruction errors and need only be correlated with the dictionary matrix to ensure convergence. These results guarantee the superiority of our EBT in theory.
2018),
We demonstrate the effectiveness of our EBT the original LISTA and several of its vari- ants in simulation experiments. We also show that it can be applied to practical applications (e.g., photometric stereo analysis) and achieve superior performance as well.
we will review some preliminary knowledge of our study. In Section 3 we will introduce basic form of our EBT and several of its improved versions. Section provides a theoretical study of the convergence EBT-LISTA. Exper- imental results in Section valid the effectiveness of our method in practice. Section 6 summarizes this paper.
The organization of this paper is structured as follows. In Section 2
BACKGROUND AND PRELIMINARY KNOWLEDGE
As mentioned in Section
I ISTA is iterative algorithm for solving LASSO in Eq. ① Its update
rule is: ((( and
(1-1) = (1-
+ y/7). 14 2 0,
where sha (z) = (1<= b)+ is a shrinkage fuucction with a threshold 6 2 0 and (-)+ max }. is positive constant scalar greater than or equal to the maximal eigenvalue of the symmetric matrix A A. LISTA kept the update rule of ISTA but learned parameters via end-to-end training. Its inference process can formulated as (0) and
b)+
(1+1) shao (w) + y)) t=.....d
set of learnable parameters, and, specifically, b(t) is the layer-wise threshold which is learnable but shared among all samples. LISTA achieved lower recon- struction error between its output and the ground-truth v, compared with ISTA, and is proved to convergence linearly (Chen al. 2018) with (tt) (((()) A holds for any layer Thus, Eq. can be written as.
where [W(9), (tt), ()(()) ((t)) t
(++1) shyc ((1 (1) ()x (1()) v), t= O......d d.
(4)
Chen et al. 2018 further proposed support selection for LISTA, which introduced shp (x) whose elements are defined as
sign(x:) - b). if |z,| > b, Sp if | b, Sp
(shp (htp((t),)))x)) (x));
De, 0.
(5)
otherwise
substitute the original shrinking function shace (I), where Sp is the set of the index of the largest p% elements (in absolute value) in vector x. Formally, the update rule of LISTA with support selection is formulated as (0) and
(++1) shp pr ((T (A) v(0)). t= -=
where ((*) is a parametr and increases from early layers to later layers. LISTA with support selection can achieve faster convergence compared with LISTA (Chen al. 2018).
2

---

Under review as a conference paper at ICLR 2021
Theoretical studies (Chen et al. and its variants should satisfy the equality
2018 Liu et al. 2019) also demonstrate that the threshold of LISTA
( (²A) sup |xx(0 W. l|p
2.ES
to ensure fast convergence in the noiseless case (i.e., e 0), where S is the training set and j((A) is the general mutual coherence coefficient of the dictionary matrix A. Note that ((A) is a crucial term in this paper, here we formally give its definition together with the definition of ((A) follows.
Definition 1 For A Rmxx its generalized coherence coefficient is defined as p(A) inf infwer"x" W., =1 maxi3j ((,), and we say W E EW(A) max44 A..) A..)) = p(A).
3 METHODS
In LISTA and its variants, the threshold 6(4) is commonly treated as a learnable parameter. As demonstrated in Eq. (7). g60) should be proportional to the upper bound of the estimation error of the t-th layer in the noiseless case to ensure fast convergence. Thus, some outliers or extreme training samples largely influence the value of 6(t), making the obtained threshold not fit the majority of the data. To be specific, we know that the suggested value of b(() is ((()) p(A)sup:: I..............llll _lll
Il for a set { 1i.0.......m and normal training of LISTA leads to it in theory (Chen et al. 2018). Yet, if new training sample Is,-1 with higher reconstruction error is introduced, the expected ((0) shall change to p p(A)]l=
(e) Is,, Ilr- which is probably undesirable for the other samples. Similar problems occur if there exists a large variety in the value of reconstruction errors.
In order solve this problem, learnable part of the threshold and introduce adaptive thresholds for LISTA and related networks. We attempt to rewrite the threshold at the i-th layer something like
propose to disentangle the reconstruction error term from the
((t) 11x zallp-
(8)
where p(t) is a layer-specific learnable parameter. However, the ground-truth x, is actually unknown for the inference process in SLIP. Therefore, we need to find an alternative formulation. Notice that in the noiseless case, it holds that (r(!) y A(z(t) IZ), thus we further rewrite Eq. (8 into
(0) = p ((0((A) - llp:
where Q RR is compensation matrix introduced to let Eq. approximate Eq. 8 better, i.e., a matrix that makes QA approaches the identity matrix is more desired. However, note that although QA is low-rank matrix and can never be identity matrix, we can encourage its diagonal elements to be 1 and the non-diagonal elements to be nearly zero This can be directly achieved by letting Q W(A). where W(A) defined in Definition [ According to some prior works (Liu al., 2019 Wu et al. 2020 Chen et al. 2018), we also know that (1t) W(A) to guarantee linear convergence, thus ( can probably be reasonable option for the matrix Q in our method, making it layer-specific well. Therefore, our EBT-LISTA is formulated as (9) 0 and
(++1) = shao ((1 (1) + ('))), 810 = 100 v) lp-
t= d,
(10)
Note that only (()) and (t)) are learnable parameters in the above formulation, thus our EBT-LISTA actually introduces no extra parameters compared with the original LISTA. The architecture of LISTA and EBT-LISTA are shown in Figure [] We can also apply our EBT mechanism on LISTA with support selection (Chen et al., 2018). is straightforward to keep the support set selection operation and replace the fixed threshold with our EBT, and such combination can be similarly formulated as =0()= 0 and
(++1) shp(ae) (()))(((1) ((I- ((1) A)z(0 + ())y), t= O....,d d,
(II)
((t) = (1000 8)1lp-
3

---

Under review as a conference paper at ICLR 2021
x
A
u
x(r11)
x
U
44
x(++1)
y
|1-11p
b(5)
p(
(a) LISTA Figure 1: The t-th layer of LISTA and EBT-LISTA.
(b) EBT-LISTA
Our former analysis is based the noiseless case. For noise case, there is A(x(t) 22) ==)==Al y + E. Since the noise is generally unknown in practical problems, we may add an extra learnable parameter the threshold to compensate the noise, i.e.,
t (()) 117 (Ax y)lb, + aa)
(12)
where a is the learnable parameter for the observation noise.
THEORETICAL ANALYSIS
In this section, provide convergence analyses for LISTA and LISTA with support selection. We focus on the noiseless case and the main results are obtained under a mild assumption of the ground-truth sparse code. To be more specific, sampled from the distribution 7(B, 8), i.e., the number of its nonzero elements follows a uniform distribution (100,s) s) and the magnitude of its nonzero elements follows arbitrary distribution in [-B, B). Compared with the assumptions made in some recent work (Chen et al. [0188] Liu et al. 2019 Wu al. 2020), i.e., XB s) [ llo s, || S B). our assumption here provides more detailed yet also stricter description of the distribution of 2s, especially for the sparsity of r. In fact, it can be easily derived that our assumption can also be rewritten the form of some prior assumptions, In particular, for Vz, E >BB s), there exist 2, ( s) == {a=Ill<=,loo s 8; ||> S B} (Wu et al. 2020). We will mention the condition that 8 is sufficiently small error-based thresholding, which means ((A)s < specifically.
assume that the ground-truie -rruh sparse vector 2, is
4.1 FRROR-BASED THRESSIOLDING ON LISTA
Let us first discuss the convergence of LISTA and how our EBT improves LISTA accelerating convergence. Proof of all theoretical results be found in Appendix A.2 To get started, would like to recall the theoretical guarantee of the convergence of LISTA, which was given in the work of Chen et al. 2218)'s.
Lemma Chen et al. 2018 For LISTA formulated in Eq. 4 if is sampled from 7 7B, 8) and is small such that p1 ((A)(22s1) < 1, with U(() E W(A), assume that b(() (((A sup,,, ||x((t) xx ll achieved guarantee the "no false positive" property (i.e. supp(x C supp(s.)), then the estimation (1)) at the t-th layer of LISIA satisfies
[x(00) xzl12 S sB exp (cot),
where co = log((o2 - L))(A)) < 0.
The above lemma shows that the reconstruction error of LISTA decreases reconstruction eттor bound is also related to and B. With Lemma [ we further show in the following theorem that the convergence of EBT-LISTA similarly bounded from above.
of co and the
Theorem (Convergence of EBT-LISTA) For EBT-LISTA formulated in Eq. 10,, for r(A) I, is sampled from (B, s) and is sufficiently small, with U W(A),, assume (()) I--(AAs is achieved to guarantee the "no false positive" property, then the estimation x! at the 1-th layer satisfies
if
xella S go exp (cit), where qo < BB and Ca Co hold with the probability of ((A)s.
(|
4

---

Under review as a conference paper at ICLR 2021
From Theorem we know that EBT-LISTA converges similarly with rate of of, which is probably faster than that of the original LISTA. In addition, we show that its reconstruction error at each layer with index t is also probably lower than that of the original LISTA, with 9o < sB. Since μ((A) is generally small in practical and is assumed to be sufficiently small such that ju( ({A)) < 1, the probability of achieving the superiority is very high in theory. We will further show experiments that even if is not that small (i.c., the sparsity is not that high), our EBT can still achieve favorable improvement on the basis of LISTA. Moreover, unlike the desired threshold the original LISTA (i.e., (((A) supz, || x=||1)
(I) which depends specific training samples, the desired threshold in EBT-LISTA is disentangled with the reconstruction error.
4.2 ERROR-BASED BASED THRESHOLD ON LISTA WITH SUPPORT SELECTION
Effective prior work from Chen et al. (2018) proposed improve the performance of LISTA with the operation of support set selection, and it helps to achieve lower error bound when compared with the original LISTA. We first give a detailed discussion on the convergence of LISTA combined with support selection before we delve deeper into the theoretical study of how combining our EBT with them further improves the performance.
Lemma 2 (Convergence of LISTA with support selection) For LISTA with support selection as formulated in Eq. ( if xr sampled 7 (B,,) and is sufficiently small, with U E W(A), assume that ((2) (o(A)sup, ||x(()) =.ll1 is achieved and pl) is sufficiently large, there actually
exist two convergence phases.
In the first phase, i.e., lo, the 1-th layer estimation x! satisfies
|| x2112 I sB exp (c2t), ())( In the second phase, i.e., > la, the estimation () satisfies
where cn S 10g((2)1))(AA))
|xx00 22ll2 S Cl((x(t-1) xz x2l12.
where S 8P((A)
Lemma 2 shows that when powered with support selection, LISTA shows two different convergence phases. The earlier phase generally slower and the later phase is faster. On the basis of the theoretical results in Lemma [ we further show in the following theorem that the convergence of EBT-LISTA with support selection is similarly bounded and also has two phases.
Theorem (Convergence of EBT-LISTA with support selection) For EBT-LISTA with support selection and 1, if x.s sampled from (B, 8) and is sufficiently small, with U E W(A), m(A) is achieved and o is sufficiently large, there exist two convergence phases. assume p(t) 1-p(A)s
In the first phase, i.e., t tú, the t-th layer estimation (t)) satisfies
||x(*) æzllı S 91 exp (egt):
where ca < C2 q1 sB and t1 < to hold with a probability of - u(A)s. A)s. In the second phase, i.e., I l1, the estimation (º()) satisfies
|1x(0) - S C1 - xxl122 -20l)
where C' < sp(A).
The above theorem shows that further incorporated with EBT, the model shall also show two dif- ferent phases of convergences. In addition, it processes the same rate of convergence in the second phase, comparing with the results of the original LISTA with support selection Lemma while in the first phase, our EBT leads to faster convergence and faster enter the second phase, which shows effectiveness of our EBT in LISTA with support selection theory.
EXPERIMENTS
We conduct extensive experiments both synthetic data and real data to validate theorem and testify the effectiveness of our methods. The network architectures and training strategies in our ex- periments most follow those of prior works (Chen et al. 2018 Wu et al. 2020). To be more specific,
5

---

Under review as a conference paper at ICLR 2021
all the compared networks have d 16 layers and their learnable parameters W U p b(t) without out EBT) are not shared between layers. The training batch size is 64, and we use the pop- ular Adam optimizer (Kingma & Bal 2014) for training with its default nyper-parameters 81 0.9, 82 = 0.999. The training is performed from layer to layer in a progressive way, i.e., if the validation loss of the current layer does not decrease for 4000 iterations, the training will move the next layer. When training each layer, the learning rate is first initialized to be 0.0005 and it will then decrease 0.0001 and finally decrease to 0.00001, if the validation loss does not decrease for 4000 iterations. Specifically, in our proposed methods, we impose the constraint between W(t)) and U(()) and make sure it holds that W(( = I (7(+) A, Vt, ie.. the coupled constraints are introduced for all the evaluated models. For models empowered with support selection, we will append "SS" to their name for clarity, i.e., LISTA with support selection is renamed "LISTA-SS" in the following discussions. The value of (( is initialized to be 0.02.
5.1 SIMULATION EXPERIMENTS
Basic settings. In simulation experiments, we set m = 250, n = 500, and we generate the dictionary matrix A by using the standard Gaussian distribution. The indices of the non-zero entries in v, are determined by a Bernoulli distribution letting its sparsity (i.e., the probability of any of its entry be zero) be Pb. while the magnitudes of the non-zero entries are also sampled from the standard Gaussian distribution. The noise is sampled from a Gaussian distribution where the standard deviation is determined by the noise level. With y = Ar, E& can randomly synthesize in-stream Ia and get a corresponding set of observations for training. Similarly, we also synthesize two sets for validation and test, respectively, each contains 1000 samples. The sparse coding performance of different models is evaluated by the normalized mean squared error (NMSE) in decibels (dB):
|| xx112 |
NMSE( x.) = 10 1og
(13)
Disentanglement. First we would like to compare the learned parameters (i.e., 6(t) and p(t)) for thresholds in both LISTA and our EBT-LISTA. Figure 2(a) shows how the learned parameters (in logarithmic coordinate) vary with the index of layers in LISTA and EBT-LISTA. Note that the mean values are removed to align the range of the parameters of different models on the same y- axis. It can be seen that the obtained values for the parameter in EBT-LISTA do not change much from lower layers to higher layers, while the reconstruction errors in fact decrease. By contrast, the obtained threshold values in LISTA vary a lot across layers. Such results imply that the optimal thresholds in EBT-LISTA are indeed independent to (or say disentangled from) the reconstruction error, which confirms the theoretical result in Theorem []] Similar observation can also be made on LISTA-SS (i.e., LISTA with support selection) and our EBT-LISTA-S: (i.e., EBT-LISTA with support selection), as shown in Figure 2(b)
logtz imcante))
log(=Pimeamta)
0
-1
-2
3
LISTA EBT-LISTA
LIST
2
4
6
10 12 14
6
8
10
12
14
Index of layers
Index layers
(a) LISTA
(b) LISTA-SS
Figure/ 2: Disentanglement of the reconstruction emror and learnable parameters in our EBT, 2(()
here indicates p!t) and ((t) for networks with or without EBT, respectively.
We analyze the obtained threshold values in EBT-LLITA and EBT-LISTA-SS, i.c., b09
p(t)) (Ax(() =)Ipp (with p = 2), and we compare them with the thresholds values obtained in LISTA and LISTA-SS. Note that the threshold values in our EBT-based models differ from sam- ple to sample, we show the results in Figure 3 It can be seen that the learned thresholds in our EBT-based methods and the original LISTA and LISTA-SS are similar, which indicates that the in- troduced EBT mechanism does not modify the training dynamics of the original methods, and our EBT works by disentangling the reconstruction error and learnable parameters.

---

Under review as a conference paper at ICLR 2021
logie (mmannte)))
log(e (ememma)))))))
-2
-6
LISTA EDT-LISTA
-8
1917 LINTAA
0
2
10
12
14
-10
8 100
12
14
Index of layers
Indox of layers
(a) LISTA
(b) LISTA-SS
Figure 3: Thresholds obtained from different methods across layers.
Validation of Theorem 2 Figure 4(a) shows how the NMSE of EBT-LISTA-SS varies with the
index of layers. Besides the 1 norm (i.e., b(*) =p(0 (()) y)]l1 concerned in the theorem, we also test EBT-LISTA-SS with the le norm (i.c.. letting b(*) = o ( (Ax(t) y)ll2). It can be seen that, with both the 1 and 12 norms, EBT-LISTA-SS leads to consistently faster convergence than LISTA. Also, it is clear that there exist two convergence phases for EBT-LISTA-S and LISTA- SS, and the later phase indeed faster. With faster convergence, EBT-LISTA-S. finally achieves superior performance. The experiment is performed in the noiseless case with pt 0.95. Similar observations can be made on the basis of other variants LISTA (e.g., ALISTA, see Figure 4(b).
NMSE (dB)
-20
-20
-40
NMSE
-40
-60
-60
LISTA-SS
ALISTA
BB1-L1STA-3541
-80
-80
FRT INT-LISTASS.
2
8
10
12
16
2
8 10
14
16
Index of layers
Index of layers
(a) LISTA-SS
(b) ALISTA
Figure 4: Validation of Theorem 2 there exist two convergence phases and our EBT accelerates the convergence of LISTA-SS, in particular the first phase.
Adaptivity to unknown sparsity. As have been mentioned, in some practical scenarios, there may exist a gap between the training and test data distribution, or we may not know the distribution real test data and will have to train synthesized data based the guess of the test distribution. Under such circumstances, it importance to consider the model (trained on specific data distribution or with a specific sparsity) test data sampled from different distributions with different sparsity. We conduct an experiment to test in such a scenario, in which we let the test sparsity be different from the training sparsity. Figure 5 shows the results in three different settings. The black curves represent the optimal model when LISTA is trained on exactly the same sparsity as that of the test data. It can seen that our EBT has huge advantages in such practical scenario where the adaptivity to un-trained sparsity is required, and the performance gain of LISTA is larger when the distribution shift between training and test is larger (ef. purple line
of the sparse coding
and yellow line in Figure 5(a) and 5(b)..
-20
NMSE (18)
NMSE (11))
NMSE (d))
440
LESTARE
ALIEAA
40
LETAAS ALRCE
-20
LISTAGE
LISTA
ESTAUSTA
-80
PRILECTIRR
60
ESTLISTARE
2
10
12
14
3.6
80
10 Indes of layer
14 12
40
10 12 Index of layers
6 8
Indox of lagers
(a) ps changes from 0.8 to 0.99
(b) Ps changes from 0.8 0.9
(c) Ps changes from 0.9 to 0.8
Figure 5: NMSE of different methods when the test sparsity is different from the training sparsity. We use "Origin" to indicate the optimal scenario where the LISTA models are trained on exactly the same sparsity as that of the test data.
Comparison with competitors. Here compare EBT-LISTA-SS. EBT-LISTA, and EBT-ALISTA with other methods comprehensively. In addition to LISTA-SS, LISTA, and ALISTA, we also com- pare with leamed AMP (LAMP) (Borgerding al. 2017) here. The performance of different net-
7

---

Under review as a conference paper at ICLR 2021
works under different noise levels shown in Figure 6 It can be that when combined with LISTA and its variants, our EBT achieves better or similar performance. Figure 6(a) demonstrates that the combination of ALISTA and EBT performs the best in the noiseless case (i.e., SNR=oo), yet
is inferior to the other networks when noise presents. The figures also show that the performance of our EBT is more promising in the noiseless low noise cases (i.e., SNR=oo and SNR=40dB), while in very noisy scenarios it provides little help.
LAMP
-10
-10
NMSE (if)
-20
NMSE (d8)
ALETA
-30
-60
USTA45
EDT-LISTA
-50
AUITA
ALECTA
-60
-50
-70
-60
-20
-80g
14
16
-70
2
8
10
12
14
16
Indox lyyy
Index of layers
Index liyers
(a) SNR=0o
(h) SNR=40dB
(c) SNR=20dB
Figure 6: NMSE of different sparse coding methods under different noise levels. It can be seen that our EBT performs favorably well under SNR=oo and SNR=40dB.
We further test different networks under different sparsity and different condition numbers. Note that for the methods with support selection (i.e., EBT-ALISTA, EBT-LISTA-SS, ALISTA, and LISTA- SS), p and Pmaz are set as 0.6 and 6.5 when Ps 0.95, and are set as 1.2 and 13.0 when pb, 0.9. Figure 7 demonstrates some of the results in different settings, while more results can be found in Appendix I In all settings, we can see that our EBT leads to significantly faster convergence. In addition, the superiority of our CBT-basee models is more significant with larger Pa for which the assumption of a sufficiently small s is more likely to hold (comparing Figure ((a)
(a) and (b)).
We also tried training with ps 0.99, yet found that some classical models failed converge such a setting so the results are now shown here.
AMSSE (08))
-30
-2
1873 NMSE (L.B)
-10
-0
NMSE (4D))
-10
-20
-40
LSTA
-30
-50
-60
LITAAS
AUSTA
40
AUIEA
-40
ALITA
EDUAIISTA
60
-60
EST
2
6
8
10
12
14
10
12 14
16
6
8
10
12
14
16
Index of lyyer
Index of lyyer
Index of lnyers
(a) pb50.95
(b) condition number=3
(c) condition number=100
Figure 7: NMSE of different sparse coding methods in different settings where different sparsity and different condition numbers are considered. When we vary the condition numbers, we fix pb=0.99
5.2 PHOTOMETRIC STEREO ANALYSIS
We also consider a practical sparse coding task: photometric stereo analysis (Ikehata et al. 2012). The task solves the problem of estimating the normal direction of Lambertian surface, given observations under different light directions. can be formulated as
pTn + 6,
(14)
where o E R& the observation, n E R33 represents the normal direction of the Lambertian surface which is to be estimated, T, E R represents the normalized light directions, e is the noise vector, and p is the diffuse albedo scalar. Although the normal vector n is unconstrained in Eq. [4], the noise vector is found to be generally sparse (Wu et al.) 2010 Ikehata et al., 2012). Therefore, we may estimate the noise e first. We introduce the orthogonal complement of L, denoted by L to rewrite Eq. [44 as
(15) On the basis of the above equation, the estimation of e is basically a sparse coding problem in the noiseless case, where I is the dictionary matrix A, is the sparse code x, be estimated in the
L'o Ln Ln + L'f Lie.
8

---

Under review as a conference paper at ICLR 2021
reformulated problem, and Lio is the observation y. Once we have achieved a reasonable estimation of e, we can further obtain n by using the equation n ( e).
In this experiment, we mainly follow the settings in Xin et al. 2016's and Wu et al. 2020]s work. We use the same bunny picture for evaluation and is also randomly selected from the hemispherical surface. We set the number of observations q to be 15, 25, and 35 and let the training sparsity of be Pr = 0.8. The final performance evaluated by calculating the average angle between the estimated normal vector and the ground-truth normal vector (in degree). Since the distribution of the noise is generally unknown in practice, the adaptivity is of great importance for this task. We use two test settings for evaluating different models, in which the sparsity of the noise in test data (i.e., Pe) is set as 0.8 and 0.9, We compare EBT-LISTA-SS LISTA-SS, and two conventional methods including using the least squares (codenamed: 1,) and least 1-norm (codenamed: 41) in Table [ Also, we build the reconstruction 3D error maps for LISTA-SS and EBT-LISTA-S
shown in Figure X in the
appendix. The results show that EBT-LISTA. -SS outperforms all the competitors in all the concerned settings, note that the advantage is remarkable when Pe 0.9, which means our EBT-based network has better adaptivity and can be more effective in this practical tasks.
Table 1: Mean error (in degree) with different number of observations and different test sparsity
Pe
4
h
LISTA-SS
EBT-LISTA-SS
15
3,41
0.678
5.50
10-
1.09 x 10-
0.8
25
3.05
0.408
7.48 x 10
3.17 x 10 3
35
2.78
0.336
1.89 10
5.95 x 10"4
15
1.94
0.232
6.67 x 10-3
2.57 x 10-3
0.9
25
0.145
2.03
1.33 10
1.64 x 10-4
35
1.61
0.088
2.93 x 10
4.91 x 10
CONCLUSION
In this paper, we have studied the thresholds in the shrinkage functions of LISTA. We have proposed novel EBT mechanism that well-disentangles the learnable parameter in the shrinkage function on each layer of LISTA from its layer-wise reconstruction error. We have proved theoretically that, in combination with LISTA and its variants, EBT mechanism leads to faster convergence and achieves superior final sparse coding performance. Also, we have shown that the EBT mechanisms endow deep unfolding models higher adaptivity different observations with a variety of sparsity. Our experiments on both synesthetic data and real data have testified the effectiveness of our EBT, especially when the distribution of the test data is different from that of the train data. We hope to extend our EBT mechanism to more complex tasks in future work.
REFERENCES
Pierre Ablin, Thomas Moreau, Mathurin Massias, and Alexandre Gramfort. Learning step sizes for unfolded sparse coding. In Advances in Neural Information Processing Systems, pp. 13100- 10, 2019.
Amir Beck and Mare Teboulle. A fast iterative shrinnagg-threshhollnng algorithm for linear inverse problems. SIAM journal on imaging sciences, 2(1):183-2022 2022, 2009.
Mark Borgerding, Philip Schniter, and Sundeep Rangan. Amp-inspired deep networks for sparse linear inverse problems. IEEE Transactions on Signal Processing, 65(16):4293445 4308, 2017.
Xiaohan Chen, Jialin Liu, Zhangyang Wang. and Wotao Yin. Theoretical linear convergence of un- folded ista and its practical weights and thresholds. In Advances in Neural Information Processing Systems, pp. 9061-9071, 2018.
K Dabov, A Foi, V Katkovnik, and K Egiazarian. Image denoising by sparse 3-d transform- domain collaborative filtering. IEEE Transactions on Image processing, 16(8):2080-209) 2007.

---

Under review as a conference paper at ICLR 2021
Ingrid Daubechies, Michel Defrise, and Christine De Mol. An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 57(11):1413- 1457, 2004.
Karol Gregor and Yann LeCun. Learning fast approximations of sparse coding. In Proceedings of the 27th International Conference on International Conference on Machine Learning, pp. 399-406, Omnipress, 2010.
Satoshi Ikehata, David Wipf, Yasuyuki Matsushita, and Kiyoharu Aizawa. Robust photometric stere- using sparse regression. In 2012 IEEE Conference on Computer Vision and Pattern Recognition. pp. 318-325. IEEE, 2012.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.69080 2014.
Jialin Liu, Xiaohan Chen, Zhangyang Wang, and Wotao Yin. Alista: Analytic weights are as good as learned weights in lista. In International Conference on Learning Representations (ICLR), 2019.
Kailun Wu, Yiwen Guo, Ziang Li, and Changshui Zhang. Sparse coding with gated learned ista. In Proceedings of the International Conference Learning Representations, 2020.
Lun Wu, Arvind Ganesh, Boxin Shi, Yasuyuki Matsushita, Yongtian Wang, and Yi Ma. Robust pho- tometric stereo via low-rank matrix completion and recovery. Asian Conference on Computer Vision, pp. 703-717. Springer, 2010.
Bo Xin, Yizhou Wang, Wen Gao, David Wipf, and Baoyuan Wang. Maximal sparsity with deep networks? In Advances in Neural Information Processing Systems, pp. 4340-4348, 2016.
Xu Xu, Xiaohan Wei, and Zhongfu Ye. Doa estimation based on sparse signal recovery utilizing weighted ll 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):281122873 2010.
Joey Tianyi Zhou, Kai Di, Jiawei Du. Xi Peng, Hao Yang. Sinno Jialin Pan, Ivor W Tsang, Yong Liu, Zheng Qin, and Rick Siow Mong Goh. Sc2net: Sparse Istms for sparse coding, In Seirty-Second AAAI Conference on Artificial Intelligence, 2018.
10

---

Under review as a conference paper at ICLR 2021
A
APPENDIX
(a) pb=0.8, LISTA-SS (=0.055
(b) Pb=0.8, EBT--ISTA-SS (=0.041
(c) p.=0.9, LISTA-SS: (=0.0067
(d) Pt=0.99 EBT-LISTA-SS: (=0.0026
Figure 8: Reconstruction 3D error maps of different methods in different settings. ( here is the mean estimation error in degree. Note that the maximal error is 1 and 0.03 in theory when ps = 0.8 and ps 0.9, respectively.
A.1 ADDITIONAL SIMULATION RESULTS
Comparison with competitors. More experiment results than those in Figure 7 are given here. Figure shows the results of our methods with EBT (i.e. EBT-LISTA, EBT-LISTA-SS, and EBT- ALISTA) and other competitors in settings including Pg=0.9, P6=0.8 (i.e. the sparsity is 0.9 and 0.8), and when condition number is set as (with Ps = 0.9). For those concerned methods with support selection (EBT-ALISTA, EBT-LISTA-CPSS, ALISTA, and LISTA-CPSS), and Pmaon set as 1.2(1.5) and 13(16.25) when p = 0.9(0.8). From Figure we can find that our EBT leads to better performance as shown in the results in the main paper.
-10
(8))
NMSE (13)
AMSE (D))
-20
-30
-10
-AU
LSTA-S5
AUSTA
LSTA--0
ALISTA
-40
LISTA55
ALETA
-60
ESTURTA
-20
SAVARIAA
ENTAISTA
-70
-80
10
12
14
16
8 10 12 Indox of layers
Inder
layer
Index
layers
P.=0.9
(b) Pb=0.8
(c) condition number=30
Figure 9: NMSE of different sparse coding methods in different settings where different sparsity and different condition numbers considered.
Random sparsity. We also consider the scenario where the sparsity of the data follows a certain distribution. We test with two distributions of sparsity (i.e., pæ): Ps U (0.9, 1) (uniform distribu- tion) and ps ~ NO.955, 0.025) E [0.9, 1] (truncated normal distribution). The comparison results in such settings shown in Figure 10 Our EBT lead to huge advantages in all the methods and setting, indicating that the conclusion in Theorem can be extended to broader distributions of the data sparsity.

---

Under review as a conference paper at ICLR 2021
0
-10
10
NMSE (B
-20
NMSE (di))
20
330
30
40
LISTA
40
LISTA
550
LISTA-SS
50
LISTA-SS
60
ALISTA
60
ALISTA
-70
880
EBT-LISTA-SS
EBT-ALISTA
EBT-LISTA
80
70
LIS--ISSA-SS
EBT-ALISTA
EBT-LISTA
0
2
6
8
10
12
14
16
0
2
4
6
8
10
12 14 16
Index of layers
Index of layers
(a) Uniform distribution
(b) Truncated normal distribution
Figure 10: NMSE of different sparse coding methods when the sparsity of the data follows a certain distribution.
EBT mechanism (F)ISAA We further conduct our proposed EBT mechanism standard ISTA and FISTA. Note that ISTA and FISTA are nonlineared convergence. We set the scalar y (in Eq. 2 constant and the regularization coefficients À (in Eq. D and Eq. as 0.1 and 0.2. In our proposed methods, we set A|| (l) ylll 1/y as the thresholds, comparaed with X/7 in (F)ITA.. From the experiment results shown in Figure [I] we can find that our EBT mechanism leads to faster convergence. However the fast convergence have negative influence on the final performances. That because the convergence speed of ISTA and FISTA are lineaine,,,d, while our EBT mechanism proposed for linear convergence methods. Therefore, EBT (F)ITA might convergence too fast to reach a better performance.
A.2 PROOF OF THEOREMS
We first give some important notations before delve into the proofs. The support set is defined as the index set of non-zero values of x and it is written as supp(z). We define S as the support set of the vector 2. and we further let [S] denote the element number of S. We denote (r); as i-th element of the vector æ and denote (M) as the element from the i-th row and j-th column of the matrix M.
A.2.1 PROOF OF THEOREM
Assume & S, ic., (I2); = 0. If (x((t1))) * 0, note that = Ax.. there is,
((t) 00 ((( .)|l
(((x((+)))
< I[([ ((t) A)x U00 Axoll
I[(T 7(1) A) - -x,) + xale
S [[(I (10) A) -x2)ll + +xxx)a
=I[(T ( (7))))(()) - =2)1.l
Σ ( ()is(a -xx0)p)
(16)
Σ [(T -U( (z) xx)i
$ Σ [(A)](=(0) - -x0ss
S ((A))l=()) - xzll1-
From above, we also have [[I ((0 A)(x(() x,),, S ((A))l=((1) =x.l1. therefore we have ||
(1)) (z((() - zz)ll1 < [S1m(A)]la((1) - xell1. Since (1) A(z(t) - -xa)lli = [1(x(t) - -xx) (1
(x(()) - -1.)ll2. we have
(1 [5]m(A))]( - sulli (1 A(x x.. || s (1 + [S]n(( (1)((1)))2=01) - (17)
12

---

Under review as a conference paper at ICLR 2021
ISTA
ISTA EBTISTAA
EBT-ISIA FISTA LOT-PISTA
NMSE (dl3)
NMSE: (dB3)
-
EUT-PISTA
-10
-15
-20
0
10
20
30
40
50
60
70
80
90
100
-15
10
20
30
40
50
60
70
80
90
100
Iterations
Iterations
(a) A=0.1
(b) X=0.2
Figure 11: NMSE of different sparse coding methods where different regularization coefficients are considered.
Since p(+)
m(4)
((A) T- A there is
T-p(Ajs
10 A(x -x,)li 2 (<A)(2()) - -rall1-
(18)
Eq. 16 and 18 are conflicted, which means (x((+1))), = 0 if (x.); (i.e supp(x((t1) c S),
which means our EBT-LISTA is also "no false positive".
From Eq. (10). we have
x (b+
I. = sbaco (1I ( A)x + +1((00 y) Is
=(T TT-U0 (() A)a((0) ( Ar. Is - -b() o h(x(+11)
(19)
= (1 - A)(z 2.) - 600) о ((x(1+1)),
where h(x) 1f > h(x) 1 and h(x) E |-1, if O. For the i-th element of
((++1) 22. have
(1x xs)h = 1(T t A)(x)) xx);, 110 @ >(a)-11)
(20)
1 - (1())))) (z - -x,)1l= + 1.
Since (1+1() C C, we have ||x((+1) rzl11 (xx1((+1))) x.)al. Thus we have
s
(1+1+) x I 2 (1 ((() (() xz)El + +bb())
s
Σ [1 T(( A))((((0) -x,)g + +
ΣΣ
([ - ( ((1)()) xz)5a + +1S|b601
(21)
$ (IS) - 1)m(A)ll(()) xell1 + \S) A(z xz)111
< (S1) ()m(A))((()) xmll1 |(A)|S] |1 A(x10 - xx)1l1-
((()s
< (IS) + 5 1 ((A)s
((A)s ())(()))(( -
The final step holds because LISTA can be calculated as
[S] Σ and Eq 17 hold. The la error bound of t-th output of EBT-
(zx 23l12
- (1) xzlli
1 + m(A)s
- ((|S) + |S||
- -x,)l1
(22)
1- m(A)s
< go exp(cit),
13

---

Under review as a conference paper at ICLR 2021
where 9u | and c1 log((1S) + |S| [+((A)s 1)x(A)). Compare e with co. have
((Ass i-A()s
[S]
exp(co) - exp(ci) = 2x(A) - (-A))))
>
(23)
hold when |S| < s(1 ((()ss) Under this circumstance,
have
40 = ||ا|||| || S | B < s(1 - p(())) S sB.
(24)
Note that v, is sampled from ((B, s). Eq. 23 and 24 hold with the probability with of 1 - 1) where
|S|
1
(25)
p(A)s.
A.2.2 PROOF OF LEMMA 2
For LISTA with support selection formulated as (G. there is x (f+1) xs chp(ot)),po)) ((T ((+) A)x + (()ly)) - Js
(I U70) A)x(!) U Ar, - I, -b() o g(x((+1))
(26)
= (1 - (1( A)(x())) - xx.) -b() o g(
where
0,i xp #0
1 Sp, H, >
9(x)
(27)
1, $ Sp. < 0.
1,,11
For the i-th element of x(+1))
3. we have
(xx xs)ss (T 0()) A) - xz); -b @ g(a((tt)
(28)
S (T ( A)(x - xx)il + ( o g( ((tt))))
Since ((() = na( (4) sup,, |2x(10 - x. x.lli- same as the standard LISTA, LISTA with support selection also "no false positive". Therefore, supp(z((+1)) c S and [x( xall1 E. (z(++1) xz)i-
Similar to (1. we have
s (1(I (()) A)(z - xo)el + 1600) @ ((1;;+1))))
||x æol11 - Σ
8
s
Σ
Σ (I T A))y(o)) xz)Ea + 16 م6ا=! (-
(29)
8
S
Σ
Σ
I(T ((()) A)ss((() -xs);| + Σ (bt)) o g(x; (1)
8 324
$ (IS) ()m(A)](zo(0) - 22 + Σ (60 o g(x(((+1))
a; From Eq. (7). we have (( < and ((a((())) only if E Sp and (t+1) + 0. We let
S411 denote the number of non-zero entries in (1++1), Also, P++1 denotes the number of the largest ((++1)% elements (in absolute value) in (((+1), Therefore the number of zero entries in (xx(++1) is min(S1+1. P.t1). Then 29) can be calculated as
[|x(++)) - =x s ((S) ())(4))(2(0) - -xall + Σ (4) o g(x:((
s (SS) 1))(4))(22(1) -xxll1 + (|S) min(S1+) P (b41))
= (S1) - ())( - -salli + ([S) minn(S++ Pe+ ()) sup |x xxl11.
(30)
14

---

Under review as a conference paper at ICLR 2021
Then, take the supremum of Eq. there is
sup [ rell1 S (2s 1 min(S P(t1))u(( (())))(()))))))) sup ||x:(0) x2ll1-
(31)
Note that | I sB and assume & = arg min; Pt), the l2 upper bound of t-th output can be calculated
||x(0) x:ll2 S ||x - xxll1 I sup ||x100 - rrll1
2,
(2s 1 min(S, Pi))a(A) sup ||x 22/11 1=1
(32)
8,
< ((2s - 1 min(Sk, Px))
1 sB &Bexxpees exp(e2t),
where 02 = loogoo(ss 1-mmmn(k (kk, S Pt))
Apparently, we have e2 S =000=0(((22 (
From 32). we have ||x(() x=|lı I sB exp(c2t), which means I error bound can approaches to 0. Thus, there exists a 1", when > 1*, ||-(00 ..,11 S minses (1ta;: Note that (1) (cc.) S
||x(()) xell1. if E S, i.., (x,); * 0, there exists 2 * O, which means S supp(x!")) Recall the "no false positive" property, i.e., supp(x(0) C we can conclude that supp(x(()) S.
Recall P. increases layerwise and ( is sufficiently large, there exists t' statisfies Pt. > s, let
max(!", ('), if > lo. there exists P. |S| and supp(>(()) S. Under this circumstance, i E S, we have oi jf 0 and E Sp,, which means every element in S will be selected as support. Therefore, have
(++1) (x,); shp pro) (r0) (((I(((())))))))) A)x())))) ( Ax.))) (xx))
((1-0()) - ()) (1 ArI); (x+);
(33)
((I A)((((() x.));:
We let as E R denote the vector that keeps the elements with indices of x in S and remove the others. Similarly, we let (S, E (R(S] x S) denote the submatrix of matrix M which keeps the row and column if the index belongs to S. Then, we have
(++1) 22112 ||2 (1(x((++1 - -x,)sll2
II((1 (1)) xx))s
I1(T - ()(S))( ((())))(())) - xs)ss12
(34)
I1(1 - ()( -z,)s|2
())( xx)ll2,
where C = A) Further we have C S |1(--00) A)(AA)) S) S VISPu(A) < (p(()).
A.2.3 PROOF OF THEOREM 2
For the EBT-LISTA with support selection formulated in Eq. [II). similar to Eq. (26) and (8). have
(xx(+ - xx)a |[I ( ()(x() - xz); ((0) o g(r; ((+1)))
(35)
(T T()) ()((())) xz)aa (1) g( (1+1)))
where ((1) (+) 17 (Ax v)|l m(d)
イ- (1 A(xlt) - x.>) Same the origin EBT- LISTA, EBT-LISTA with support selection also "no false positive" and Eq. (77 hold either. There- fore [100) (t) x1)l (1 + (8]x()))]laa x.ll1 (1 sp({))]l sslli. Similar to
15

---

Under review as a conference paper at ICLR 2021
Eq. 29
and (30)
there is
(c((+1))xx)))
(1(I (((A)){'')) - + 16 +16(0 ((xx(+1)))
8
8
Σ
Σ (1 (10 - + 1 o g(o:+t))
=
S
$ ΣΣ
111 -4-UP (1- A))((())( xz))]l + Σ 10 g(x, (
jti
< (18) 1))(A))l2(1)) -x,111 + (1S) -min(S Pe+1 1)]b((
min(SS+1; P2+1 / (A) 1 1((A)s
< (S8 1)) (1)(()) -xal11 + (IS)
[[x!10 xx2)
((A)s
2
1 ++
81
P.+1) 1 1)x(A))((z()) - xz)]111
((A)s
1 ((AAs)
(36)
Similar to Eq. 32 the l2 error bound can be calculated
[zx(1) 12 ||x(()
2
1 u(A)s
|S|
min P.) ())(A)) [1x ((=(0) xz)1l1
p(A)s
1 -((Ass
(37)
2
1 1+ m(A)s
<
|8|
(Sn, Pk) 1))(())))) |sal|1
(A)s
1 (A))s
< exp(cal),
where @1 = =||a/]] and cg log(( [-M(A)a|S)
I+u(A)s I-M(A)e min(S Px) - 1))(
Compare c3 with e2, we have
2u(AA) exp(c2) exp(es) 2n((A)(s 1- (A(A)s (u(A)s
|S|
minn Pk))
(38)
|S|
2u(A)(s 1- m(A)s > 0
hold when |S| < s(1 - [(A)s). Under this circumstance, we have
q1 ||0./|| S |S] B s(1 - ((A)s) sB. Note that v, is sampled from >(B, s). Eq. where
(39)
388 and 39
hold with the probability with of 1 1,.
S
(40)
# (())s.
Similar to LISTA with support selection, there exists a t"" when > t"t, ||x(0) x. < minies (x,);. Therefore, supp(z(")) = S. Recall that C3 < C2 holds with the probability of 1 - 7). we have t** < t' hold with the probability of as LISTA-SS, we have same t' satisfying Pe s. Let = max(t*", t'), we have f S ty with the probability of 1 When t > t1, we have x * 0 and i E Sp. Same as Eq. 33 and (34). there
When we use the same settings for p(t)
(++1) xxl12 < (1((x!!) x22)12, where C = || UV A)(S,) S) 11 < - A) ViST2(AA)= & sp(A).
(41)
16


Reviews:
[{"review_id": "tT8GftLKBU1", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "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": "In the paper, authors propose a new error-based thresholding mechanism for LISTA which introduces a function of the evolving estimation error to provide each threshold in the shrinkage functions. They provided the theoretical analysis for EBT-LISTA and EBT-LISTA with support selection and proved that the  estimation error of the proposed algorithm is theoretically lower than compared methods. The authors also evaluated the proposed method on multiple synthetic or real tasks. Experimental results show that the proposed method achieves a better estimation error and  higher adaptivity to different observations with a variety of sparsity.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "dOelrnEa4Kc", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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:\nThe authors propose an automatic threshold selection for LISTA-style neural nets. The threshold introduces negligible number of parameters (either 0, or one per layer). This choice is shown theoretically and empirically to have faster convergence than methods without it and popular alternatives.\n\nClarity:\nThe clarity of your idea would be improved using a graphic: for example showing the LISTA architecture, and what sort of computations are performed in a \"feed in\" direction toward the shrinkage operator. Just a thought, not a criticism. The information in Table 1 might be more succinctly reported using exponential notation, or speedup as a percentage (I count 39 extraneous 0's)\n\nQuality:\nThe quality would be improved if you applied this adaptive thresholding idea to classic (F)ISTA, i.e. updating (F)ISTA's thresholds via the parameterless form of EBT. How would this impact standard (F)ISTA convergence, i.e., compared to using a fixed threshold run on a whole test set? (is ebt-threshold selection better than say, doing a parameter search for fixed threshold \"b\", over a training set on (F)ISTA?)\n\nThe experiment variety is of good quality: experiments across condition numbers and sparsities, validation of theorems, etc.\n\nOriginality: \nI am not familiar with other works like this, and I like the idea. I wish we were given insight to how it affects nonlearned (F)ISTA algorithms, which are still widely used in practice.\n\nSignificance:\nThe result is significant in the specific application of LISTA.", "extra_scores": {}, "extra_text": {}}, {"review_id": "dESHMouLwP2", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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 disentangles the threshold parameters in LISTA-type models from the reconstruction errors, proposing the Error-Based Threholding (EBT) mechanism which mainly follows a theoretical results in (Chen et al., 2019; Liu et al., 2018), where the threshold at one layer is proportional to the recovery error of current iterate. The benefits brought by the proposed EBT method are faster convergence and better adaptivity to a wider range of samples. To bypass the requirement of ground truth sparse signals, EBT uses the reconstruction error following a learned linear transform, which in theory has good coherence property with the dictionary and therefore can approximate the recovery error well. The authors theoretically show that the proposed EBT mechanism enjoys faster convergence in both cases with and without the support selection technique. Emprirical experiments on standard synthetic setting and cross-sparsity setting are shown to support the efficacy of EBT. The authors also do real-world photometric stereo analysis to show the superiority of EBT.\n\nPros:\n- This paper is a successful extention of basic LISTA-type models by disentangling the learnable threshold parameters.\n- Theoretical analysis of the benefits of EBT is provided and looks correct to me.\n- The empirical experiments are solid enough to show the superiority of EBT.\n\nCons:\n- My main concern is about that this paper is a little bit incremental, as it seems to be a very direct extension based on previous theoretical results.\n\nOther comments:\n- In Figure 1, it can be observed that the thresholds learned LISTA-SS have a bumpy curve, which is also observed in previous works. In contrast, the $\\rho^{(t)}$ parameters look much stabilized. It might be better to also show the curves of reconstruction error term, i.e. the $\\ell_p$ term in eqn (12) to see how they look like. This would help to understand if the new parameterization used in EBT changes the training dynamics or not.\n- In the basic settings part, the numbers of validation and testing samples are provided. How many samples are used for training?\n- In eqn (15), is the term about $\\rho n$ omitted on purpose, or mistakenly?\n\nIn summary, I think this is a good extension paper but I have a little concern about its incremental contribution. Overall I think it is slightly above the threshold. I am open to more opinions from other reviewers.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "LeFq8XDkxgW", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "### Strengh\n\n- The idea makes sense to adapt the thresholding mechanism to an input distribution with various reconstruction error. It might bring a much better empirical performance compared to thresholds fixed globally and it seems to be adapted in a denoising setting.\n\n\n### Weakness\n\n- The motivation for this work is not sufficiently furnished. The authors claim that it is useful when there is a discrepancy between train/test distribution but do not provide reference to realistic situation where such a problem arise.\n- Also, this method cannot really be used for real sparse coding problems as the network needs to be trained with the ground truth which is often not known in practice.\n- The theoretical contribution is marginal as it is almost straightforwardly adapted from Chen et al. (2018) and Liu et al. (2019).\n- The theoretical results are not precise enough (`s small enough`) while this assumption might very well render all the results only applicable to toyish case. Moreover, these assumptions are stronger than the one in `Chen et al. (2018)` and `Liu et al. (2019)` for $x_s$ realizing the sup in the expression of $b^t$ (Eq.7).\n- Almost all the experiments use the same setting as previous work, failing to highlight the advantage of the proposed method.\n- The performance advantage over LISTA seems to be minor from Figure.2.\n\n\n## Extra remarks\n\n\n- The proposed goal is to adapt LISTA in a setting where the input training distribution is *different* from the testing one. However, in this setting, using an algorithm like LISTA does not make sense as the learned weights have no reason to be adapted to the new distribution if the distribution do not overlap at all. There might be some degree to which it is possible to adapt but this should be made more explicit and better discussed. In particular, what type of distribution shift are considered and would make sense -- sparsity is mentionned but it is unclear.\n\n- p.3: `normal training of LISTA leads to it.` I don't think there is any results showing that SGD over LISTA achieves such threshold in theory and I haven't seen any proper empirical validation. If it exists, a proper citation is needed. Else, the statement should be updated.\n\n- p.3: `According to some prior works, we also know that U(t)∈ W(A)`: in the three cited papers, there seems to be no results showing that the learned `U(t)` verifies this. The statement is once again too strong.\n\n- Eq.(8): Would it be interesting to evaluate the usage of $\\rho^{(t)} = \\mu(A)$?\n\n- p.4: `the main results are obtained under a mild assumption of the ground-truth sparse code` -> The assumption is not mild. For instance, it seems to never be verified in any of the experiments. The statement $\\mu(A)s \\ll 1$ seems not backed by any experimental evidence and I don't think this is true.\n\n- p.4: `the above assumption gives a more detailed description of the distribution for $x_s$` while it is true that it sets a distribution on the space $\\mathcal X$, it is not more precise as in the assumptions by `Chen et al. (2018)`, I believe no distribution is mentionned. so overall it constrains the type of distribution while it is not required in `Chen et al. (2018)`\n\n\n## Minor comments, nitpicks and typos\n\n- citations in () could use `citealt` to remove the extra parenthesis.\n- p.1: Lasso can also be solved using CD algorithms, which are typically state of the art.\n- p.1: In Gregor&LeCun (2010), the thresholding is not modified compared to ISTA.\n- p.2: `with W(t)=I−U(t)A holds for any layer` -> `in the case where W(t)=I−U(t)A holds for any layer`.\n- Eq.(7):\n- `Liu et al. (2018)`: The proper citation is `Liu, J., Chen, X., Wang, Z. & Yin, W. ALISTA: Analytic Weights are as good as Learned weigths in LISTA. in International Conference on Learning Representation (ICLR) 1113–1117 (2019).`\n- p.4: `a truncated distribution` -> I assume the authors mean `truncated gaussian distribution`?\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper received mixed reviews, with one review voting for acceptance, one strongly opposed, and two borderline ones. The discussion essentially involved R1 and R2, who gave the most informative reviews. After discussion, they did not update their score, even though they appreciated the work and effort done by the authors during the rebuttal. 

In short, the paper has some merit, but several concerns were raised, which the area chair agrees with, leading to a rejection recommendation. The innovation was found to be limited and the discussion between practice and theory (meaning assumptions made in this work) are not discussed in a convincing manner, and these concerns remained after the rebuttal. The experiments were also subject to improvements.

It is however likely that with a major revision, this work may become publishable to a another venue.
Decision: Reject