Neurally Augmented ALISTA
Authors: Freya Behrens
Jonathan Sauder
Peter Jung
Venue: ICLR 2021 Poster (2021)
Keywords: compressed sensing
sparse reconstruction
unrolled algorithms
learned ISTA

Abstract:  It is well-established that many iterative sparse reconstruction algorithms can be unrolled to yield a learnable neural network for improved empirical performance. A prime example is learned ISTA (LISTA) where weights, step sizes and thresholds are learned from training data. Recently, Analytic LISTA (ALISTA) has been introduced, combining the strong empirical performance of a fully learned approach like LISTA, while retaining theoretical guarantees of classical compressed sensing algorithms and significantly reducing the number of parameters to learn. However, these parameters are trained to work in expectation, often leading to suboptimal reconstruction of individual targets.  In this work we therefore introduce Neurally Augmented ALISTA, in which an LSTM network is used to compute step sizes and thresholds individually for each target vector during reconstruction. This adaptive approach is theoretically motivated by revisiting the recovery guarantees of ALISTA. We show that our approach further improves empirical performance in sparse reconstruction, in particular outperforming existing algorithms by an increasing margin as the compression ratio becomes more challenging.

Published as a conference paper at ICLR 2021
NEURALLY AUGMENTED ALISTA
Freya Behrens' . Jonathan Sauder' Peter Jung 12.1
Communications and Information Theory Chair, Technical University Berlin', Data Science in Earth Observation, Technical University of Munich {f behrens,, sauder) | @campus. tu bberlin.de, peter. jungetunngneeeeee bertuuu-brlinccc
ABSTRACT
it well-established that many iterative sparse reconstruction algorithms can be unrolled to yield a learnable neural network for improved empirical performance. A prime example is learned ISTA (LISTA) where weights, step sizes and thresholds are learned from training data. Recently, Analytic LISTA (ALISTA) has been introduced, combining the strong empirical performance of fully learned approach like LISTA, while retaining theoretical guarantees of classical compressed sensing algorithms and significantly reducing the number of parameters to learn. However, these parameters are trained to work in expectation, often leading to suboptimal reconstruction of individual targets. In this work therefore introduce Neurally Augmented ALISTA, which an LSTM network is used to compute step sizes and thresholds individually for each target vector during reconstruction. This adaptive approach is theoretically motivated by revisiting the recovery guarantees ALISTA. We show that our approach further improves empirical performance in sparse reconstruction, in particular outperforming existing algorithms by an increasing margin as the compression ratio becomes more challenging.
INTRODUCTION AND RELATED WORK
Compressed sensing deals with the problem of recovering a sparse vector from very few compressive linear observations, far less than its ambient dimension. Fundamental works of Candes et al. (Candès) et al., 2006) and Donoho (Donoho) (006) show that this can be achieved in a robust and stable manner with computationally tractable algorithms given that the observation matrix fulfills certain conditions, for an overview see Foucart & Raubut (2017). Formally, consider the set of s-sparse vectors in R.N. i.e. Σ.N = x E T. |0 S 8) where the size of the support of x is denoted by || == [x = Ki I; + OH] Furthermore, let E RMM be the measurement matrix, with typically M < N. For given noiseless observation y Qx of unknown but s-sparse x" ΣN we therefore wish to solve:
argmin
|
s.t. 4x
(I)
In (Candès et al. 2006) it has been shown, that under certain assumptions on 4, the solution to the combinatorial problem in ( can be also obtained by a convex relaxation where one instead minimizes the L norm of z. The Lagrangian formalism yields then an unconstrained optimization problem also
known as LASSO (Tibshirani) 1996). which penalizes the 4 mnomr via the hyperparameter R:
argmmin Ily tr + X X||0=||a
A very popular approach for solving this problem is the iterative shrinkage thresholding algorithm (ISTA) (Daubechies et al. 2003), in which reconstruction (*)) is obtained after & iterations from initial ( 0 via the iteration:
(k+1) = 7 (2(0) + - - 2x))))
(3)
equul contribution
(BMBF) framewurk the internationa foture "AMEO Artifcial Ineellgmeee Finth Ohservsioo: Ressoning, Unncrttaistess, Fibics Reyond" (Grant mumber: 01D020001).
The work puriillly DPG grant
Ministry

---

Published as a conference paper at ICLR 2021
where 778 is the soft thresholding function given by (0(2) sign(z) max(0. |x|| 0) (applied coordinate-wist wise) and L is the Lipschitz constant (i.e. the largest eigenvalue) of x Φ. Famously, the computational graph of ISTA with K iterations can be unrolled to yield Learned ISTA (LISTA) (Grregor & LeCun 2010), a K-layer neural network in which all parameters involved can be trained (each layer & has individual threshold parameter and individual shared matrix weights) using backpropagation and gradient descent. LISTA achieves impressive empirical reconstruction per- formance for many sparse datasets but loses the theoretical guarantees of ISTA. Bridging the gap between LISTA's strong reconstruction quality and the theoretical guaranteess for ISTA, ALISTA (Liu jt al.
2019) was introduced. ALISTA, introduces a matrix W related to the measurement matrix ① in
which is computed by optimizing the generalized coherence:
(WW Ø)
inf max W W.. s.t. Vi {I......N) D.
(4)
WERMXN i
Then, contrary to LISTA, all matrices are excluded from learning in order to retain desirable properties such as low coherence. For each layer of ALISTA, only a scalar step size parameter 7(h) and a scalar threshold ((k) is learned from the data, yielding the iteration:
x (k+1)
a (8) (W (6x(1) v)
(5)
As in LISTA, the parameters for ALISTA are learned end-to-end using backpropagation and stochastic gradient descent by empirically minimizing the reconstruction error:
min
Ex
x 201
((0)
The authors rigorously upper- upper-bound the reconstruction error of ALISTA in the noiseless case and demonstrate strong empirical reconstruction quality even in the noisy case. The empirical performance similar to LISTA, the retained theoretical guarantees, and the reduction of number of parameters to train from either O(K M NM) in vanilla LISTA O(MNK) in the variant of LISTA-CPSS (Chen et al. 2018) to just O(K). make ALISTA an appealing algorithm to study and extend.
In (Ablin al. 2019). instead of directly focusing the reconstruction problem, where À is not known a priori, analytical conditions for optimal step sizes in ISTA are derived for LASSO, yielding Stepsize-ISTA ISTA. Stepsize-ISTA is variant of LISTA in which the measurement matrices are exempt from training like in ALISTA, outperforming existing approaches to directly solving LASSO. Thresholds that are adaptive to the current target vector have been explored in ALISTA-AT (Kim & 2020). Following the majorization cnniiiaaioonminnnizaaioon method, component-wiss wise thresholds are computed from previous iterations. In a particular case this yields 0%4) 1/(1 + 2 1/e) for some c > 0, known as iterative reweighted f fymiinimization. By unrolling this algorithm, the authors demonstrate superior recovery over ALISTA for a specific setting of M, and s. a related approach (Wu et al., (020) identify undershooting, meaning that reconstructed components are smaller than target components, as shorteoming of LISTA and propose Gated-LISTA to address these issues. The authors introduce gain and overshoot gates to LISTA, which can amplify the reconstruction after each iteration before and after thresholding, yielding an architecture resembling GRU cells (Cho et al. 2014). The authors demonstrate better sparse reconstruction than previous LISTA-variants and also show that adding their proposed gates to ALISTA, named AGLISTA, it is possible to improve its performance in the same setting of M, N and ALISTA-AT.
In this paper, motivated by essential proof steps of ALISTA's recovery guarantee, we propose an alternative method for adaptively choosing thresholds and step sizes during reconstruction. Our method directly extends ALISTA by using a recurrent neural network to predict thresholds and step sizes depending on an estimate of the fi-error between the reconstruction and the unknown target vector after each iteration. We refer to our method as Neurally Augmented ALISTA (NA-ALISTA), as the method falls into the general framework of neural augmentation of unrolled algorithms (Welling) et al. (017)). The rest of the paper is structured as follows: we provide theoretical motivation for NA-ALISTA in Section [2] before describing our method in detail in Section 3 In Section 4 we demonstrate experimentally that NA-ALISTA achieves state-of-the-art performance in all evaluated settings. To summarize, our main contributions are:
2020 Monga et al.]
1. We introduce Neurally Augmented ALISTA (NA-ALISTA), an algorithm which learns to adap- tively compute thresholds and step-sizes for individual target vectors during recovery. The number of parameters added does not scale with the problem size.
2

---

Published as a conference paper at ICLR 2021
2. We provide theoretical motivation inspired by guarantees for sparse reconstruction which show that NA-ALISTA can achieve arrive tighter error bounds depending on the target x²"
We find that NA-AI ALISTA empirically outperforms ALISTA and other cate-of-theear algorithms in synthetic setting well as in real-world application from wireless communications and that the gains increase with decreasing M/N.
2 THEORETICAL MOTIVATION
The thresholds g(k) in (5) play an important role in the analysis of ALISTA. While the authors of (Liu et al. 2019) prove that ((k) must be larger than certain value in order to guarantee no false positives the support of the reconstruction (k))), the thresholds ((k) also appear as an additive term in the reconstruction error upper bound.
Thus, to guarantee good reconstruction ((k) should be just slightly larger than the value it must surpass in order to both minimize the error and verify the assumption. this section, repeat key insights from ALISTA and motivate the choice of adaptive thresholds the key improvement in our proposed NA-ALISTA. More specifically, we repeat the conditions under which ALISTA guarantees no false positives and highlight an intermediate step in the error bound from (Liu et al. 2019), which tightens when the thresholds can adapt to specific instances of xx"
Assumption (adapted from Assumption 1 from (Liu et al. 2 Let x² E N be a fixed s-sparse larget vector. Let W be such that it atlains the infimum of the generalized coherence with & (as in (4) and denote this generalized coherence as ja (WW, ④). Let (1+ //2 Let 7(1) ,...,?? 7i) be any sequence of scalars taking values (0, 248- and ((1) (0.,..((K))) with:
((() 2 (/) Al| x1112
Because in ALISTA, the thresholds (1) (K) and stepsizes ((1), g()),..., ((() are optimized in expectation over the training data, the inequality in 7 holds only in the general case if the thresholds are larger than the worst case -errro committed by the algorithm over all training vectors x i.e.:
gk)) 2 200 jusp (1x x0111
(8)
This is needed in order fulfill the Assumption. Under these conditions it is guaranteed that false positives are in the support of the reconstruction:
No false positives (Lemma from (Liu et al. 2019))
Under the settings of the Assumption, it holds that:
(R) supp(x")
However, the threshold (1() also reappears in the error upper bound. Here we employ intermediate step of the error upper bound from (Liu et al. 2019):
Reconstruction error upper bound (Theorem from (Liu et al. 2019)
Under the settings of the Assumption, it holds that:
[|x(0++1) 11(+++)-2211) 222 < (k++1) x111 (s) - (H))s -+11-7 (1 - (10)
Where the first inequality holds for all real vectors and the second inequality is derived in detail in Appendix A of (Liu et al. 2019). According to (10) is therefore desirable that ((k) as small as
Note that in this work and in Liu et al. (2019) the noiseless case is considered simplify the theorems and proofs. For similar statements in the noisy case, refer the reader to Chen et al. (2018).
3

---

Published as a conference paper at ICLR 2021
possible, but such that it still satisfies 7 This means that ALISTA has to learn thresholds ((A) at least proportional to the largest possible committed l fi-error over all possible x in order to guarantee good reconstruction, for which it is in turn penalized in the error bound.
However, if an algorithm would have access to [|x:(A) - x= Il and were allowed to choose thresholds adaptively based on x², the more relaxed inequality (7) could be employed directly, without taking the supremum over all possible x² as in (8). Then, this algorithm could obtain tighter error bound for some individual targets x" than ALISTA since ((k) 2 0(1), Finding such algorithm is the aim of this paper.
3 NEURALLY AUGMENTED ALISTA
In order to tighten the error upper bound in (0O), we introduce Neurally Augmented ALISTA (NA- ALISTA), in which we adaptively predict thresholds ((k,a") depending on the current estimate for the -errro between (x)) and the unknown x". As can be observed from (7). such (kk,z") must be
proportional to ||z((4) - x= 111 1|1.
In theory, this true errorr could be recovered exactly. This is because there are no false positives in 2((k, making it s-sparse and for a < 1/(2s 121-1) the column-normalizer W 4 is restricted- invertible for any 28-sparse input (Foucart & Rauhut 2017) [Corollary 5.4, p. 113]. However, it is infeasible solve such an inverse problem at every iteration k. Furthermore, in practice the sparsity is often much larger than what is admissible via the coherence bound. For example, in the experiments
of (Gregor LeCun 2010 Liu et al. 2019 Wu et al. 2020; Kim & Park] (020), a sparsity of 50 is used with . = 250. N 500. This sparsity already exceeds maximum admitted sparsity of 11 derived from the minimum theoretical coherence of 0.0447 by the Welch Bound (Welch) 1974).
implying that such exact recovery is not possible in practice anyways.
NA-ALISTA thus largely concerned with learning for each iteration a good approximation of [|x2(0 x 111 For this, consider the fn-nrr of the residual:
(k) == [x)(
y/11 = [x (K) x²) x²)ll1
(11)
and the iterative update quantity in
u (A) = | (k) e)1l = II (x)))) I|
(12)
Both are known to the algorithm even though x² unknown. That (k) and (k) are useful quantities for approximating the true --erro stems from the fact that W & has low mutual coherence, thus being a restricted isometry for sparse vectors. This visualized in Figure Other useful quantities to approximate the true fi-error are given by []) x 11,,,,,.. [|2- xx" This is highlighted by Figure and suggests the use of recurrent neural network in NA-ALISTA. We therefore propose
to use an LSTM (Hochreiter & Schmidhuber 1997) which has two input neurons, receiving (k) and
300
[''"""1111 1/1
1710
300
430
1000
155
350
1300
382
1000
||at
|| 11
||="||
|| 1|
(a) |1"" 110
15
(b) u. [0" 110 15
(c) r. || Ilo 1000
(d) 0. |10
1000
Figure 1: Correlation between ||='|| and r |e="|| 1/1 u || 4 ||2. In (a) and (b) for sparse vectors with || 15. In (c) and (d) for non-sparse vectors a|~ Ilu N. The non-zero zero components of x are
drawn i.i.d. from (0, 1) with N 1000. One can see that for sparse x r and u are correlated with ||> (Spearman coefficients 0.91,0.92), whereas there is much weaker correlation for non con-sparse vectors (0.38,0.37).
4

---

Published as a conference paper at ICLR 2021
10
35
12.5
1:5
1xx00
20-
23
50 | (z)
300
W (a:"0) 11
)1la
[ ((2
11h
(a)
(b)
(d)
Figure Correlation between w and || =
||| in trained instance of NA-ALISTA from different iterations
(i.j). (a): (0, (0, (b): (5, 6). (c): (14, 15), (d): 8). The Spearman coefficients are 0.85,0.96.0.97 9609.7,0..) showing that the strong correlation, is even preserved across multiple iterations (d), suggesting the use of
recurrent neural network to predict g(t,==) Training was performed with 1000, 128 and K 16.
Algorithm I: Neurally Augmented ALISTA
Learnable Parameters: initial cell state eo IR initial hidden state ho E R
LSTM parameters, I-layer MLP parameters U1 # .U2 122 map states to outputs.
Input: y
x < 0;
< hu: c + Co K] do
for {1,
r
px - yll
W y)ll
e, h +- LSTM(C, h u])
0,7 (0ftsign(U((eLL((i))))
110 (I w - 8)
end
Return z:
((k) each iteration k. This is used to update the internal state and produce the outputs ((k,a") and g(k,z") which are used compute the next iteration, producing the update rule:
(k+1) =.) (Z(C)) - (k)a"=)) (4) - -v)
(13)
computational expression for NA-ALISTA is given Algorithm Note that the introduction of LSTM-cellls in NA-ALISTA does not significantly increase the required computing power in practice. fact, in Section 4 we show that small LSTM-cells suffice for best empirical performance, independently of the problem size. Let H be the size of the hidden layer of the LSTM-cells, then the computation for a single forward computation of the cell takes O(H2) computations. As a regular iteration of ALISTA takes O(MN) operations and computing the l 4-normm of the update takes additional O(N) operations, iteration of NA-ALISTA requires O(MN + N + H2) operations. For example, when M = 250. N = 2000, = 64 as in one of the experimental settings in Figure 5 then H²/MN 4096 550000 0.0081 008192, showing that the added computation is negligible in practice.
quantity (T (A)
4 EXPERIMENTS
In this section, we evaluate NA-ALISTA a sparse reconstruction task and compare it against
ALISTA (Liu al. 2019, ALISTA-AT (Kim & Park 2020). AGLISTA (Wu al. 2020). well as
the classical ISTA Daubechies et al. 2003) and FISTA (Beck & Teboulle] 22099. To emphasize
fair and reproducible comparison between the models, the code for all experiments listed is available
on GitHub
htttps:///ht thw.. com. http://eed////e/eeee htttt::://gtthbb...o//eeee////// lista
5

---

Published as a conference paper at ICLR 2021
4.1 EXPERIMENTAL SETUP
Following the same experimental setup as (Liu et al. 2019 Wu et al. 2020 Chen et al. 2018 Kim & Park 2020), the support of x² R is determined via i.i.d. Bernoulli random variables with parameter S/N, leading to an expected sparsity of S. The non-zero components of x are then sampled according A (0, 1). The entries of 4 are also sampled from (0, 1), before each column is normalized to unit f2-norm. W is then computed by minimizing the generalized coherence in (4) between W and via the Frobenius-Nonn Norm approximation using projected gradient descent. This procedure is identical to (Liu al.) 2019) Wu et al. 2020 Kim & Park 2020 The Adam optimizer (Kingma Ba 2015) is used to minimize the -2-error from (6) for all algorithms. A test set 10000 samples is fixed before training and recovery performance is measured with the normalized mean squared error (NMSE):
[kx( E,
x
NMSE = 10 log
x
2018) to speed up convergence and stabilize training and has been subsequently used extensively variants LISTA and ALISTA (Liu al.) 2019 Kim & Park 2020 Wu et al. (020). When support selection is used, a hyperparameter p = ..... ....ppp p(() is set such that for each layer, a certain percentage of the largest absolute values exempt from thresholding. iee.:
support selection trick was introduced in (Chen et al.
110 (10 (z);
Zi sign( (.)) max(0, |2/ -
if
| (p(k) /N] -larestt value of [ar] else
For a fair comparison, we employ support selection in all learned models compared in this paper similarly the literature (Liu al.) 2019 Chen al. 2018 Wu al. 2020 Kim & Park [2020). Our AGLISTA implementation follows the description in the paper (Wu et al.) 2020): we use exponential gain gates and inverse- prtpeeooooool--ooooeeeee based overshoot gains. The À parameter in ISTA and FISTA was tuned via grid search, we found that À = 0.4 led to the best performance in our tasks. NA-ALISTA by default uses both (k) and (*) as inputs to the LSTM iteration k:
When not otherwise indicated we the following settings for experiments and algorithms: M 250, N = 1000, S = 50, K = 16, H = 128, and oz* + with additive white Gaussian noise with signal noise ratio = E | /12)
40dB. We train all algorithms for 400 epochs, with each epoch containing 50,000 sparse vectors with a batch size of 512.
4.2 COMPARISON WITH COMPETITORS
As an established experimental setting to compare the performance of ISTA- methods the compressed sensing, previous work (Liu al.) 2019 Kim & Park 2020 Wu et al.) 2020) has focused on compression level of M/N = 0.5 with sparsity S=50 following (Chen et al. 201 8).. However, practical applications in communication and imaging favor even lower compression rates
-5
-15
-20
LMSE (dB)
-10
aMSE
-00
-15
-35
-20
44
ALISTA
AGLISTA
FISTA
-25
ALISTA
AGLISTA
FISTA
55
ALISTA AT
NA. ALISTA
ISTA
ALISTA AT
NA. ALISTA
ISTA
-00
0
10
12
14
16
18
10
14
16
20
22
24
26
Iterations
(K)
Iterations
(K)
(a) N=2000, SNR=400B
(b) N=2000, SNR=20dB
Figure 3: The reconstruction eror for ALISTA, AGLISTA, ALISTA-AT and NA-ALISTA over the number of iterations K for SNR=40dB (Ba) and SNR=20dB (3b). NA-ALISTA outperforms all competitors. Results for scttings with smaller found Appendix

---

50 Published as a conference paper at ICLR 2021
-5
ALISTA-AT AGLISTA NA-ALISTA
ALISTA-AT
-5
AGLISTA
HMSE (dB3)
-55
mMSE (di3)
NA-ALISTA
-10
20
-00
55
20
005
-25
N
N
SNR=40dB
(b) SNR=20dB
Figure 4: Reconstruction enror over different compression ratios. For constant expected sparsity
and M = 250 measurements and K = 26 iterations, the input size N varies. Both under a SNR of 10dB and 20dB NA-ALISTA increases its reconstruction margin to competitors as N increases and the compression ratio becomes more challenging.
25
3.5
N-500
Mean
Moou
30
N-2000
2.5
aMSE (db)
-35
2.0
-55
-50
16
32
64
128
256
3
11 12 13
16
LSTM Size (H)
Iterations (K)
Figure 5: Reconstruction error for varying settings of LSTM size NA-ALISTA. Larger N profit more from larger H. but in all settings exponential in- crease of the LSTM size only yields marginal im- provement once H 64 is surpassed.
Figure 6: Predicted step sizes and thresholds from a trained instance of NA-ALISTA (N 1000, M 250, S = 50, K 16), highlighting the adpativity of NA-ALISTA. Inference obtain these values performed on the test set.
like 1 which is why extend our analysis compression rates we keep the sparsity and measurements M constant while increasing N.
challenging rates. To achieve different
As shown in Figure 3 we first fix N 2000 and observe the reconstruction error for varying amount of iterations. Figure we then decrease the compression ratio while keeping the sparsity constant. We observe that NA-ALISTA outperforms state-of-the-arr adaptive methods in all evaluated scenarios. Whereas for the more established setting from the literature of ==500, the improvement of NA-ALISTA small, this margin increases the compression ratio becomes more challenging. In Figure 4a the reconstruction error achieved by ALISTA-AT and AGLISTA deteriorates to the performance of ALISTA, while our NA-ALISTA can sustain advantage over ALISTA even for compression rates up to 0.1 when N 2500. This suggests that our method is interesting to wider range of practical applications.
NA-ALISTA with: LSTM-r
LSTM-r,
LSTM-u
MLP-r, u
Vanilla RNN-r,
N 500
-42.00
-42.18
.42.03
-39.64
-42.11*
N 1000
-39.15
-39.12
-39.24
-35.64
-39.43
N 2000
-32.50
-32.49
-29.36
-28.47
-24.18*
Table 1: Reconstruction NMSE dB NA-ALISTA with varying inputs (r-(k) (R)) different neural network architectures with K = 16, SNR= 40. For the LSTM it does not seem to matter which quantities to estimate the Ei-error, since all perform equally well. The MI.P is outperformed by all recurrent architectures. Even though the Vanilla-RNN can perform on par with the LSTM, suffers from serious training instability with training resulting in NaNs for 500 and 2000 (*) even when trained significantly smaller learning rate. which lead us to use the stable LSTM in our experiments.

---

Published as conference paper at ICLR 2021
1.4
ALISTA ALISTA-AT
AGLASTA NA-ALISTA
1.2
HMSE -10
1.0
08
20
0.6
0.4
10
Training Epochs
Terasions (K)
Figure 7: Training curves for N = 1000, K = 16, =NR= 40 from the learned algorithms compare in this paper, showing that NA-ALISTA outperforms the competitors after only few epochs training. Each epoch consists of 50,000 random sparse vectors.
Figure Comparison of the ratio (()) /~(00 with the true E1-error ||== x x || at each iteration for NA- ALISTA for the mean of batch of randomly drawn test data {a*) } and standard deviation. Together these terms behave as desired, see Eq. 7
To verify that the added computation, determined by the size of the LSTM, is negligible in practice, we test different settings of H. In Figure we show that an exponential increase in hidden neurons yields only small error reduction for different N, suggesting that the size H 128 is a sufficient default value for several settings of N. This implies that neural augmentation only marginally affects the runtime. We tested NA-ALISTA using different inputs r((k), (*) and architectures in Table I. justifying the use of an LSTM, and concluding that the all approximations perform similarly and a single approximation of the fi-error is sufficient. However, we observe slight increase in convergence speed and training stability when using both inputs. For a direct comparison of wall clock times we refer the reader to the appendix.
We also evaluate whether the increased empirical performance NA-ALISTA is truly due to its adaptivity or simply due to its architecture, since the LSTM architecture could in principle enable a more stable optimization of the desired parameters due to more stable gradients. This would imply that when
test set, the learned step sizes would not vary depending the input. Figure shows that this not the case, since step sizes and thresholds vary within a margin on test set of 10,000 randomly sampled inputs. Also, the decreasing threshold g(A) corresponds to "warm start" behavior for ISTA to first go through a thresholding phase and then through fitting phase where the threshold becomes essentially zero, see exemplary (Loris) 2009). An additional strength of NA-ALISTA is that it is fast and stable to train, outperforming competitors after only few epochs, as shown in Figure 7
As empirical verification of Assumption 1 in 7 need check for every x², whether the ratio ((k,=)) 1/2 (k,rx"))) is proportional to the feerrorr ||x" x((1)|11 Since it is infeasible to check the assumption for the infinite set sparse vectors ΣyA we empirically verify (7) for a sample inputs from the training distribution. In Figure & the means of both values proportional to each other for such a test sample, suggesting that the reconstruction bound (10) holds for NA-ALISTA.
4.3 REAL DATA SETTING MULTIPATH CHANNEL ESTIMATION
In this section we evaluate NA-ALISTA for based multipath channel estimation for Orthogonal Frequency Division Multiplexing (OFDM) used in modern wireless networks like LTE and 5G and video broadcasting systems like DVB-T, T, see e.g. (T'se & Pramod, 2005). Within scenario-dependent coherence time, the communication channel is almost time-invariant and described by a circular con-
0.2
0.00
0.0
Re
0.00
-0.4
-0.05
150
250
800
(b) Pilots E C for M 50 and Nrrr 1024 Figure Pilot-based multipath channel estimation with compressed sensing. Here, CMXN subsampled DFT with NrFT 1024. A random realization the CIR and the pilot values y are shown.
(a) Sample CIR x" CN for delay spread N 256
8

---

Published as a conference paper at ICLR 2021
volution with the channel impulse response (CIR) when using cyclic prefix. Since this operation is di- agonalized by the discrete Fourier transform (DFT), i.c the information bearing data payload is multi- plexed in OFDM onto different frequencies (called subcarriers) and the channel operation in frequency space simplifies to simple multiplications with the DFT of the CIR. Hence, demodulation and decoding of the data message requires accurate knowledge of these instantaneous channel coefficients. In mobile scenarios, the channel is estimated from scattered pilots: on some pilot subcarriers known symbols are transmitted. Conventionally, an equidistant pilot pattern used as motivated by the Nyquist-criterion i.e. the maximum delay spread of the channel. Fortunately, the CIR is also often well well-approximated by sparse vectors since concentrates on only few clusters and paths. Due to longer propagation, more delayed components decrease in averaged power. A statistical model like in (Saleh & Valenzuela 1987) is often used for the power delay profile, i.e. the second order statistics of the random CIR.
From the viewpoint of compressed sensing with partial Fourier matrices (Foucart & Raubut 2017). it is known that pilot overhead can be reduced and channel estimation performance im-
M
DMSE (d13)
-9
proved when penalizing with respect to sparsity and using irregular random pilot locations (Tauböck & Hlawatsch] 2008) Jung et al. (2099).
-14
19
However, since the iterative compressed sensing algorithms are more complex than linear estima- tors it is important reach sufficient accuracy in only few iterations and to rely on fast Fourier transforms (FFT). Optimizing generalized co- herence for the algorithm via (4) is therefore not feasible since the resulting W can usually not be implemented via FFT.
-21
-20
ALISTA AGLISTA ALISTA-AT
FISTA
NA-ALISTA
ISTA
344
12 14 16
18
Iterations (K)
Figure 10: Channel estimation error vs. iterations K for an 10MHz LTE system at SNR=10dB Amount of pilots M = 100, as used in the standard but sampled randomly.
We evaluate NA-ALISTA for 10MHz LTE sys- tem with a FFT size NEFT 1024 with cyclic prefix of 256 samples ("long CP"), which is capable of dealing with channel delay spreads of up to N = 256 (Fig. 9h). A practical system uses M 100 equispaced pilots at distance of 6 in the allowed band of 600 subcarriers for conventional estima- tion. As motivated above, for compressed sensing we instead use random locations (Fig@b). is known that with high probability the partial DFT matrix will have good coherence and thus enable compressed sensing (Foucart & Rauhut 2017).
CN assume exponentially decaying power delay profile: for every E supp(x) the value I; is zero-mean complex-Gaussin distributed with variance p: E 12,21 12 ~ exp(().5i). The random support itself is uniformly distributed with given sparsity S = 8. In Figure 10 we observe that NA-ALISTA finds better solutions with fewer iterations than its competitors and the gain even improves when decreasing number of pilots to 75 (see Appendix).
As a statistical model for the CIR
CONCLUSION AND FUTURE WORK
In this paper, we propose Neurally Augmented ALISTA (NA-ALISTA), an extension of ALISTA in which the step sizes and thresholds are predicted adaptively to the target vector by neural network. Besides a theoretical motivation for NA-ALISTA, we experimentally demonstrate that it is able to outperform state-of-the of-the--rt algorithms such as ALISTA (Liu et al. 2019). AGLISTA (Wu et al. 2020), and ALISTA-AT (Kim & Park 2020) in sparse reconstruction in a variety of experimental settings. In particular, NA-ALISTA outperforms the existing algorithms by wide margin in settings with large compression.
While in this paper we restrict ourselves to the classical compressed sensing setting, neural augmenta- tion provides a flexible framework for incorporating additional knowledge into classical algorithms. Therefore, an interesting line of future work is to explore how neural augmentation can incorporate notions of structured sparsity other constraints into sparse reconstruction. There is a plethora of signal processing algorithms, going much beyond variants of compressed sensing and proximal gradient methods, which lend itself learned unrolling (Monga et al. 2019). Identifying algorithms which could benefit from neural augmentation in the way that ALISTA does is left as future work.
For thresholding the complex case the magnitude of x; E is changed and the phase remains the same.

---

Published as a conference paper at ICLR 2021
REFERENCES
Pierre Ablin, Thomas Moreau, Mathurin Massias, and Alexandre Gramfort, Learning step sizes for unfolded sparse coding. In Advances Neural Information Processing Systems 32. 2019.
Amir Beck and Mare Teboulle. A fast iterative shrinkage-threshooldnng algorithm for linear inverse problems. SIAM journal on imaging sciences, 2009.
Emmanuel J Candès, Justin Romberg, and Terence Tao. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on information theory, 2006.
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, 2018.
Kyunghyun Cho, Bart van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using RNN encoder-decoder for statistical machine translation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), 2014.
Ingrid Daubechies, Michel Defrise, and Christine De Mol. An iterative thresholding algorithm for linear inverse problems with sparsity constraint. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 2003.
Steven Diamond, Vincent Sitzmann, Felix Heide, and Gordon Wetzstein. Unrolled optimization with deep priors. arXiv preprint 1.Kiv:1705.0844 2017.
David L Donoho. Compressed sensing. IEEE Transactions on information theory, 2006.
Simon Foucart and Holger Rauhut. A mathematical introduction to compressive sensing. Bull. Am. Math, 2017.
Karol Gregor and Yann LeCun. Learning fast approximations of sparse coding. In Proceedings of the 27th international conference international conference machine learning, 2010.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 1997.
P. Jung, W. Schüle, and G. Wunder. Robust Path Detection for the LTE Downlink based on Com- pressed Sensing. 14th International OFDM- WWDDM-Wrr.shpp... Hamburg, 2009.
D. Kim and D. Park. Element-wise udaptive thresholds for learned iterative shrinkage thresholding algorithms. IEEE Access, 2020.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
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, 2019.
Ignace Loris. On the performance of algorithms for the minimization of Ei-penalized functionals. Inverse Problems, 2009.
Vishal Monga, Yuelong Li, and Yonina Eldar. Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing. arXiv preprini arXiv: 191. 2019.
A. A. M. Saleh and R. Valenzuela. A statistical model for indoor multipath propagation. JEEE Journal Selected Areas in Communications, 5(2):128-133 137, 1987. doi: 10.1109/SAAC.118.114555
Georg Tauböck and Franz Hlawatsch. A compressed sensing technique for OFDM channel estimation in mobile environments: Exploiting channel sparsity for reducing pilots. 2008 IEEE International Conference on Acoustics, Speech and Signal Processing, (3):2885-222) 2888, mar 2008. ISSN 1520- 6149. doi: 10.1 459//
10

---

Published as a conference paper at ICLR 2021
Robert Tibshirani. Society: Series B (Methodological), 1996.
Regression shrinkage and selection via the lasso. Journal of the Royal Statistical
David Tse and Viswanath Pramod. Fundamentals of wireless communication, volume 9780521845. 2005. ISBN 9780511807213 doi: 10.1017/CH0978051180777 1807211..
Lloyd Welch. Lower bounds on the maximum cross correlation of signals (corresp.). IEEE Transac- fions on Information theory, 1974.
Max Welling. Neural augmentation in wireless communication, Keynote at 2020 IEEE International Symposium on Information Theory, 2020.
Kailun Wu, Yiwen Guo, Ziang Li, and Changshui Zhang. Sparse coding with gated learned ista. In International Conference Learning Representations, 2020.

---

Published as a conference paper at ICLR 2021
A SUPPLEMENTARY EXPERIMENTS ON SYNTHETIC DATA
-5-
15
HMSE (dB)
HMSE (AB)
-10
-5
30
-15
-00
-20
50
AGLISTA NA-ALISTA
-5
AGLISTA NA-ALISTA
55
ALISTA-AT
ISTA
ALISTA-AT
ISTA
18
24
10
16
20
(K)
Herations
(K)
(a) N 500, SNR= 40
(b) N = 500, SNR= 20
0
10
15
uMSB (dB)
IMSE ((B)
-10
25
300
20
-00
-20
-45
-50
ALISTA
AGLISTA NA-ALISTA
ALISTA ALISTA-AT
AGLISTA
FISTA ISTA
55
ALISTA-AT
ISTA
NA-ALISTA
18
Iterations (K)
Iterations
(c) N 1000, SNR= 10
(d) 1000, SNR= 20
0-
10
-5
15
HMSE (dB)
IMSE (4B)
-10
25
-0
-35
-00
ALISTA ALISTA-AF AT
AGLISTA
FISTA ISTA
ALISTA
AGLISTA
FISTA ISTA
55
NA. ALISTA
ALISTA AT
NA ALISTA
Iterations (K)
Iterations
(0) . 2000, SNR- 40
(1) N 20000 SNR= 20
Figure 11: The reconstruction error for ALISTA, ALISTA-AT and NA-ALISTA over the number of iterations nun for different noise and N settings. In [aa] for the standard setting in the literature with N 500 and a noise level of 40dB NA-ALISTA performs on par with competitors after 16 iterations. For an increased ==1000 under the same noise level in TIc our algorithm outperforms the other methods clearly. For a noise level of 20dB all algorithms perform similarly for N 500 and N 1000 and NA-ALISTA outperforms the others N 2000.
12

---

Published as a conference paper at ICLR 2021
B COMPARISON OF WALL CLOCK RUNTIMES
In Figure comparison of the wall-clock time for one iteration NA-ALISTA and ALISTA at inference time for a single batch is shown. A batch size of 5000 instead of 512 is used because otherwise the kernel launch latency dominates the actual computation time for all algorithms when GPU used. The results show that NA-ALISTA is feasible to compute and in fact faster than AGLISTA.
NA-ALISTA M-260
ALISTA M=:00
2.5
NA-ALISTA (14)
ALISTA M-250
AGLISTA M1-50
M-250
M-500
Time (ms))
2.0
Time
1.5
1.0
0
0.0
300
1000
1500
2000
2500
3000
3500
2000
500
1000
1500
2000
2500
3000
3500
4000
N
(a) GPU
(b) CPU
Figure 12: Wall clock time for single iteration of NA-ALIST, AGLISTA and ALISTA with M=250 and 500 and N ranging from 750 4000 for single batch of size 5000, averaged over 100 batches. Computations
run system with NVIDIA Tesla P100 GPU and Intel(R) Xeon(R), with the GPU enabled (a) and CPU only (b).
C SUPPLEMENTARY EXPERIMENTS IN COMMUNICATION SETTING
n.MSE (dB3)
R.MSE: (dB)
-14
-14
-19
-19
-9
ALISTA
AGLISTA
FISTA ISTA
-29
ALISTA
AGLISTA
FISTA ISTA
ALISTA-A AT
NA ALISTA
ALISTA AT
NA. ALISTA
Iterations (K)
Iteration (K)
(a) 100
(b) 75
Figure 13: Channel estimation error vs. iterations K for an 10MHz LTE system at SNR=10dB, (a) amount of sampled pilots M 100, while (b) reduces this to 75, the reconstruction erro is still close to using M = 75.
13


Reviews:
[{"review_id": "SSzLNLZcG_B", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "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\n\nThe paper shows that augmenting analytic learned ISTA (ALISTA) with a small LSTM that predicts step sizes and thresholds improves empirical performance in terms of sparse reconstruction compared to comparable baselines, especially as the compression ratio increases (i.e. ratio of measurement dimension M to sparse vector dimension N).\n\nThe proposed method is also nicely motivated by an intermediate step in the ALISTA reconstruction error bounds, where predicting thresholds adaptively given knowledge of the L1 error between estimate at the $k$th step and true target $x^*$ can allow use of a tighter error bound.\n\n\n### Strong points\n\nS1: Clear explanation of the method in terms of its relation to prior work and theoretical motivation.\n\nS2: Nice empirical exploration of theoretical motivation (i.e. examining correlation between various quantities of interest in Figures 1 and 2)\n\nS3: The approach seems to achieve superior performance compared to comparable baselines.\n\n### Weak points\n\nW1: Only uses synthetic data for evaluation. This is fine to study the properties of the method, and sparse recovery is a general method, but I think the paper would be stronger if the authors also used the approach for some kind of real world task or application. Or at least used parameters for synthetic data that match a real world task, e.g. maybe something from communications. This would also help motivate the method's superior performance for higher compression ratios.\n\nW2: A bit more empirical validation of the theoretical arguments would strengthen the paper. In particular, Figure 8 shows that the ratio of threshold to step size versus iteration $k$ is roughly proportional to the true L1 error, but looking at the bound in equation (7), I wonder if there's a stronger empirical validation, e.g. would it be possible to compute the coherence $\\tilde{\\mu}$ and check that the ratio is bounded below by coherence times L1 error?\n\n### Recommendation\n\nI think this is a good paper and I recommend acceptance. I would be inclined to increase my score if the weak points I mentioned above were addressed, and depending on answers to my questions below.\nThe paper is clearly written, the method well-motivated both theoretically and empirically, and achieves superior performance compared to competitive and comparable baselines.\n\n### Questions\n\nQ1: how important is the LSTM architecture? Have you tried other types of RNNs, e.g. vanilla RNN or GRU?\n\nQ2: I was a little confused about the LSTM notation. Does c, h \\leftarrow LSTM(c, h, [r, u]) mean that the output is split into these two vectors? A bit more explanation of this notation would be helpful.\n\nQ3: relating to a weak point I mentioned above: is there some motivation for the choice of synthetic data parameters M, N, S, K, H?\n\nQ4: is Figure 3 the mean reconstruction error over the 10k-example test set? Would it make sense to report std devs across examples for each method?\n\n### Other comments:\n\nC1: I found the Figure 1 caption to be a little hard to understand and there's a typo. Adding some punctuation could help: \"=15, (a) and (b), and non sparse vectors .., (c) and (d)\"\n\nC2: Caption of figure 1 says \"whereas there is no obvious correlation for non-sparse vectors.\". I wouldn't say there's no obvious correlation just from looking at the scatter plots. For figures 1 and 2, how about measuring and reporting correlation measures, like Pearson and/or Spearman? I suggest Spearman b/c the correlation doesn't seem entirely linear in the Figure 2 plots. Adding these measures would quantify the degree of correlation.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "O7Y0rs7tt47", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "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 extends the framework of ALISTA, a variant of learned ISTA called Neurally Augmented ALISTA (AG-ALISTA), which significantly reduces the number parameters in the model (down to 2 scalars per layer, one for step size and the other for the threshold in soft-thresholding function). Specifically, the authors use a LSTM to generate these two parameters in each layer along iterations, taking reconstruction error related signals as input. This method is based on (1) the previous previous finding of the relation of the step size and threshold with the $\\ell_1$ signal recovery error; and (2) the empirical observation of the correlation between the $\\ell_1$ signal recovery error and reconstruction error. Experiments in synthetic setting show the superiority of AG-ALISTA over ALISTA and other variants that follow it, especially in settings where the compression ratios are challenging, which is claimed to be more realistic in real-world settings.\n\nPros:\nThe most interesting and novel part of this paper is the use of LSTM for the generation of the step size and threshold parameters. The authors use two types of signals related to reconstruction error as the input to the LSTM, which is based on the restricted isometry due to sparsity and observed to be reasonable. And the observation of \"not weak\" correlation between the $\\ell_1$ recovery error and previous reconstruction error also makes it reasonable to use a LSTM structure. These are all interesting observations. Also, the synthetic experimental results do corroborate the effectiveness of the AG-ALISTA model.\n\nCons:\n- Firstly, it is kind of a pity that the authors do not provide some real-world experiments, e.g. compressive sensing, where the compression ratios are challenging indeed. I think this paper would be strong with taht kind of experiments.\n- I think eqn (11) and (12) hold when the measurements are noiseless; otherwise they are not exactly accurate. However, noiseless experiments are not presented, nor is there discussion about the noisy/noiseless cases.\n- Another concern is that baseline performance of ALISTA with 40dB noises when N=500 seems to be worse than that reported in the previous works. Is it because of the training strategy used? According to the description in this paper, I guess the authors do not use the layerwise training but end-to-end training? This is not clearly stated in the paper.\n\nOthers:\n- In the last paragraph of page 3, \"However, the thresholds that make the error bound tighter vary depending on...\" Either \"tighter\" or \"vary\" should be deleted.\n\nOverall I think this is an interesting paper. I am willing to further raise my score if the authors address my concerns/questions.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "NoXShSbFsSr", "reviewer": "AnonReviewer2", "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": "This paper adds LSTM to adjust the step size and threshold for LISTA, an optimization algorithm of sparse regression problems.\n\nUsing LSTM to dynamically determine those optimization parameters seems to be reasonable.\nStill, I found the experiments to be a bit insufficient to convince me of its improvement over LISTA or even most vanilla solvers: Figure 3,4,5 all showing MSE to some iterations when only one optimizer reaches its optimality, or even not one reaching optimality. I also think the other algorithms, with the step size tuned better, could be reaching faster convergence, however, the paper fails to mention how the parameters are tuned for those methods. On top of this, no mentions of the actual running time of the optimizer as LSTM could be really slow.\n\nsmall questions:\n\nWhat is the point of the study showed in figure 1&2 as by definition,  as $W$ is already supposed to be an isometric mapping?", "extra_scores": {}, "extra_text": {}}, {"review_id": "4MQehGnqXvC", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "SUMMARY:\nThe paper at hand introduces Neurally augmented ALISTA (NA-ALISTA) which is an extension to the previously proposed analytical learned iterative shrinkage threshold algorithm (ALISTA). Both algorithms belong to the class of learned optimization algorithms for solving the compressed sensing problem, i.e., methods that have parameters which are learned via backpropagating through multiple iterations of the algorithm. The key novelty of the NA-LISTA is the LSTM network used to predict thresholds and stepsized used by the algorithm. The experiments show that this adaptive approach improves the performance of ALISTA.\n\nSTRENGTHS:\n1. After reading the paper I have the impression that the proposed method is thouroughly evaluated. The experimental setup is clear and well-described. Interestingly, the performance of their approach does not depend on wether u^(k) or r^(k) is fed into the LSTM-cell.\n2. The results look very promising and the proposed NA-LISTA algorithm seems to consistently outperform the other discussed ISTA variants.\n3. The method is well motivated.\n4. The paper is very clearly written and well positioned in previously existing literature. All notation is introduced beforehand and it is easy to follow.\n\nWEAKNESSES:\n1. The authors claim that the computational time per iteration is not strongly influenced by the forward pass through the LSTM, because of its relatively small architecture. However, I would have liked to see wall-clock time comparison for the different ISTA variants.\n2. No completely novel theoretical insights. The lemma and the threorem are adapted from Liu et al. (2019).\n3. I find the formulations \"An algorithm which approximates such thresholds, resulting in a tighter error bound, is the aim of this paper.\" somewhat misleading, since there is not tighter bound explicitly stated within the paper.\n\nCONCLUSION:\nOverall, I would recommend to accept this submission. The method is solidly justified and the experiments are convincing. I would like to see wall-clock time comparisons in the final manuscript or in the supplemental material, but this is not a major issue in my opinion.\n\nMINOR REMARKS:\n- At some points throughout the paper the definition of variables, e.g., N=500, is not written in math mode.\n- Also some citations are not correctly formatted, e.g. \"Candes, Romberg, Tao and Donoho (Candès et al., 2006; Donoho, 2006)\" should be \"Candes et al. (2006) and Donoho (2006)\".\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers and AC liked the basic idea of how this paper improves on ALISTA, and the initial scores were high. Because the contributions rely quite a lot on empirical demonstrations, the reviewers asked for more experiments, changes to experiments, and timing results. The revision and rebuttal addressed most of these requests.  The multipath channel estimation problem was interesting though outside the scope of the AC and reviewer's expertise, so it is hard to evaluate how helpful the method is in that particular setting.
Decision: Accept (Poster)