Learning Cluster Structured Sparsity by Reweighting
Authors: Yulun Jiang
Lei Yu
Haijian Zhang
Zhou Liu
Venue:  (2020)
Keywords: Sparse Recovery
Sparse Representation
Structured Sparsity

Abstract: Recently, the paradigm of unfolding iterative algorithms into finite-length feed-forward neural networks has achieved a great success in the area of sparse recovery. Benefit from available training data, the learned networks have achieved state-of-the-art performance in respect of both speed and accuracy. However, the structure behind sparsity, imposing constraint on the support of sparse signals, is often an essential prior knowledge but seldom considered in the existing networks. In this paper, we aim at bridging this gap. Specifically, exploiting the iterative reweighted $\ell_1$ minimization (IRL1) algorithm, we propose to learn the cluster structured sparsity (CSS) by rewegihting adaptively. In particular, we first unfold the Reweighted Iterative Shrinkage Algorithm (RwISTA) into an end-to-end trainable deep architecture termed as RW-LISTA. Then instead of the element-wise reweighting, the global and local reweighting manner are proposed for the cluster structured sparse learning. Numerical experiments further show the superiority of our algorithm against both classical algorithms and learning-based networks on different tasks. 

Under review as a conference paper at ICLR 2020
LEARNING CLUSTER STRUCTURED SPARSITY BY REWEIGHTING
Anonymous authors Paper under double-blind review
ABSTRACT
Recently, the paradigm of unfolding iterative algorithms into finite-length feed- forward neural networks has achieved a great success in the area sparse re- covery. Benefit from available training data, the learned networks have achieved state-of-the-an performance in respect of both speed and accuracy. However, the structure behind sparsity, imposing constraint on the support of sparse signals, is often an essential prior knowledge but seldom considered in the existing networks. In this paper, we aim bridging this gap. Specifically, exploiting the iterative reweighted & minimization (IRL1) algorithm, we propose to learn the cluster structured sparsity (CSS) by rewegihting adaptively. In particular, we first unfold the Reweighted Iterative Shrinkage Algorithm (RwISTA) into an end-to-end train- able deep architecture termed as RW-LISTA. Then instead of the element-wiss reweighting, the global and local reweighting manner proposed for the cluster structured sparse learning. Numerical experiments further show the superiority our algorithm against both classical algorithms and learning-based networks on different tasks.
INTRODUCTION
Sparsity is an important inherent property that describes the low-dimensionality of signals. Learning the sparse representation of signals or data plays important role in many applications, such im- age restoration (Liu et al., 2018 2019b), classification (Wright et al. 2009), radar detection (Ahmad & Amin 2013). medical imaging (Lustig et al.) (007). black hole image in astronomy (Honma et al. (016). As fundamental, sparse recovery sparse representation (SR) has been substantially investigated in the last two decades due to the emergence of Compressive Sensing (CS) (Zhang &
Rao 2011 Yu et al., 20122; Needell & Tropp 2009 Yu et al., 20155 Daubechies et al. 2004).
Particularly, the objective of SR is to find concise representation of a signal using a few atoms from some specified (over-complete) dictionary
y Ax +
with y E R.M the observed measurements corrupted by some noises e, x E R. the sparse represen- tation with no more than S nonzero entries (S-sparsity) and A RMXN the dictionary (normally M < N). Consequently, the ill-posedness of ( prohibits a direct solution of x by inverting A. In the last two decades, such ill-posed inversion problem has been exhaustively investigated in the
community of signal processing (Becker et al. 2011 Daubechies et al. 2004, Needell & Tropp,
2009.. Many iterative algorithms such as ISTA (Daubechies al.] 2004), FISTA (Beck & Teboulle,
2009 Becker et al. 2011). ADMM (Chartrand & Wohlberg (013) and AMP (Donoho et al.) 2009)
have been proposed to solve it, which can be considered as unlearnable approaches since all the parameters are fixed instead of being learned from data.
Recently, inspired by the deep learning techniques, SR problem is instead turn to the data-driven approaches. The seminal work LISTA (Gregor & LeCun 2010 Sprechmann et al., 2013) Zhang & Ghanem 2018) and its consecutive variations (Zhou et al., 2018 Moreau & Bruna 2016 Ito et al.] 2019 Sun et al. 2016) have largely improved the SR performance by simply unfolding iterations of existing SR algorithms into limited number of neural network layers, and then training the net- work through back propagation with huge amount of data. Theoretically (Moreau & Bruna 2016)

---

Under review as a conference paper at ICLR 2020
and empirically (Gregor & LeCun 2010; sulted algorithms are with improved accuracy and efficiency comparing to their original counterparts [Gryyes et al. 2018).
Sprechmann et al. 2013 Zhang & Ghanem 2018), the
On the other hand, the structure behind sparsity, imposing constraint on the support of sparse signals, is an important prior knowledge that can be used to enhance the recovery performance (Wang al., 2014 Prasad et al.] 2013] Liu et al. 2018: Yu et al. 2012). Specifically, structures often exhibit as sharing of zero/nonzero pattern for grouped entries (dependent on each other) of sparse signals. And the cluster structured sparsity (CSS) is one of the most important cases, where the zero/nonzero entries appear in clusters. Since many natural sparse signals tend to have clustered sparse structure, this pattern has been widely exploited in many practical applications such as gene expression analy- sis (Tibshirani et al. 2005), and inverse synthetic aperture radar imaging (Lv et al. 2014). However, to the best of the authors' knowledge, few of the data-driven SR algorithms have been proposed for structured SR problems. Thus, there an urgent need for the study of a learnable approach to utilize the structure behind sparse signals.
In this paper, we try to bridge this gap with special attention on cluster structured sparse recovery. We aim at tackling this problem with neural networks which are explainable and fully trainable. As discussed above, LISTA provides an exemplar approach to bridge the connection between SR and NN in explainable manner. To further consider the clustered structure, we exploit the reweighted iterative soft-thresholding algorithm (RwISTA) (Fosson, 2018) as the prototype of our proposed network. Essentially, the weights in RwISTA act latent variable that controls the sparsity pattern of corresponding coefficients, Based on this observation, in addition to unfolding RwISTA as feed- forward network, we recast the reweighting process into a parameterized reweighting block that can inference the inherent dependencies between coefficients and thus promote structures. To this end, a one-layer fully connected reweighting block (RW-LISTA-fe) that exploits the global dependencies of all elements is first proposed. And empirically, the adjacency matrix of the FC layer after training with CSS signals reveals local dependence of elements for CSS signals. Consequently, two-layer convolutional reweighting block (RW-LISTA-Com) is then proposed to capture such dependencies, namely the connection of neighboring coefficients. Through exhaustive numerical experiments, the resulted network RW-LISTA is proven the superiority over existing methods in solving CSS recovery. Our high-level contribution can be concluded as follows:
We propose a novel supervised approach for cluster structured sparse recovery. Leverag- ing the iterative reweighting algorithm, we demonstrate that, we can learn the structured sparsity by reweighting adaptively. Furthermore, a deep architecture called RW-LISTA is proposed by unrolling the existing model into deep networks.
Instead of wise manner, we introduce a fully connected (FC) and a convolutional reweighting block in RW-LISTA promote the structures. Excitedly, the learned adja- cency matrix in FC layer reveals local dependency for coefficients of CSS signals, which is suitable to be captured by convolution. Although this work specially focuses on CSS, it gives further insights to other structured problems beyond SR.
We achieved state-of-the- performance on several tasks based on both synthesized and real-world data. In these cases, compare our algorithm with others in different settings. And the result further verifies the effectiveness and superiority of our proposed methods.
2 LEARNING CSS BY REWEIGHTING
2.1 REWEIGHTING THE & NORM ITERATIVELY
Sparse recovery is often cast into LASSO formulation, namely minimization problem with & norm constraint used to promote sparsity. To alleviate the penalty on nonzero coefficients, Candes et al. 2008) propose to reweight the l norm. Formally, consider the following problem:
min Iy Aa 1
wa |a:]|
where w, corresponds to the weight associated to ith entry of x. To reach a more "democratic" penalization among coefficients, Candes et al. (2008) assign the weight wi lolte with e > 0
2

---

Under review as a conference paper at ICLR 2020
small value. And thus, 1 Wt [ can be seen smooth approximation of tu norm. Through reweighting, different entries are penalized differently. Large weights will discourage nonzero en- tries in the recovered signal while small weights tend to encourage nonzero entries. Consequently, to improve the estimation, the weights should be determined properly according to the true location of nonzero entries.
In the original paper, Candes et al. (2088) adopts an iterative algorithm (IRL1) that alternates be- tween reconstruction and redefining the weights, which falls into general form of majorization- minimization algorithm (a generalization of EM algorithm (Dempster et al. 1977)). Later, Fosson 2018) proposed simple variant algorithm called Reweighted Iterative Soft Threshold Algorithm (RwISTA), which can be formulated as:
w < +p (1216)) (x++1)) +- (x)) + A A)xx(A)) w)(k)
where ((.,-) is an element- wise soft offtthhresholding function defined as [T 0)] = max [|=:| -0, 0). (1:)( for i 1, 1,2, N. L is often taken as the largest eigenvalue of A, |- applies element- wisely and (p) is the reweighting function that takes the magnitude of signal as input. Generally, the reweighting function is usually defined wlesey
[p(=)]] = g'xx,, i = 1.,
(4)
where g(-) is a concave, non-decreasing function called merit function. Obviously, if we define g(x) - I, then (px)) 13 (3) will be reduced to normal ISTA. However, a popular choice is g(ø) log(z + c) with e > 0 pre-defined parameter. In this case, the weights are determined inversely proportional the magnitudes of the corresponding coefficients as w; in + Consequently,
any coefficient o (x+1) becomes larger, the corresponding weight becomes smaller, and in the next iteration weaker penalty will be applied. Since nonzero entries are more likely to be identified with greater magnitude, iterative reweighting algorithm introduces a positive feedback that prevents the overshrinkage of nonzero entries while suppressing the magnitude of zero coefficients.
2.2 LEARNED ITERATIVE
ALGORITHM WITH REWEIGHTING BLOCK
Although quite successful, there are some reasons that make RwISTA unsuitable for our prob- lem, namely learning recover cluster structured sparsity (CSS). First and most importantly, the reweighting function is often defined element-wisele which ignores the structures behind sparsity. In CSS signals, for example, images of MNIST digits, nonzero entries tend to appear in clusters that the sparsity pattern of the neighboring coefficients statistically dependent. But such lationship cannot be captured by the blement-wise reweighting manner. Besides, RwISTA can be viewed recurrent structure with pre-fixed parameters. However, according recent successful applications of deep learning in sparse representation, learnable parameters that benefit from huge amount of training data will behave significantly better with respect to both convergence speed and recovery accuracy.
(())
((1
C(K-1)
(()
X (1)
22)
(K-1)
((0)
B
B(K-1)
p (0) (0)
w(1)
(K w(M-
(1)
Figure 1: Architecture of our proposed model RW-LISTA.
To address the issues mentioned above, we propose RW-LISTA as shown in Figure which unfolds RwISTA (3) into finite-length deep neural network. Formally, the forward pass of RW-LISTA can be formulated as:
w (k) (k) + (k) (12060)). (k+1) +
(k) (k) + ((k) g00) to
(5)
3

---

Under review as a conference paper at ICLR 2020
where ((A) RNXN C(A) NNM and (.) denotes the paratermized reweighting block in the hth layer. The model's architecture is illustrated Fig. [ In RwISTA we fix ((k)
I I "ATA A, C(k) A" and g( = À for all layers. However, now all the parameters in I
RW-LISTA (including the parameters of the reweighting block (o(+) are optimized by minimizing the reconstruction error || - x=12 through paok-propagation to fix the distribution of the data.
Since weights are able to control the sparsity pattern of the coefficients, what we need to do is to determine the weight properly so that they have small values in nonzero locations and significantly greater values elsewhere. the only clue that can be utilized. The dependencies between coefficients should also be carefully considered. Existing works including Yu et al. (2015) 2012) and Fang et al. (2014 2016) exploit the neighboring dependencies to tackle the problem of CSS recovery, where if the neighbors of one coefficient appears to be nonzero with great magnitude, then the current coefficient more likely to be nonzero and thus should be reweighted less. It inspires us to build the reweighting block to with respect to the amplitude of coefficients æ. And the objective is to output weights with small values if the corresponding coefficients belong to some clustered blocks, while with large values if the corresponding coefficients are isolated or small in magnitude. The details of reweighting block construction will be discussed in the next section. And Figure 2 iillustrates an example of the output of the proposed reweighting block (after training).
turns out that for structured sparsity, the magnitude of the entry is not
0.8
0.8
Magnituo
Magnitude
0.4
-2
0.2
Input Signal Corresponding Weights
II III I
III In
III
40
100
120
140
Index of Entries
Figure 2: An example of input signal and output of the proposed reweighting block yo (after training).
2.3 BUILDING THE REWEIGHTING BLOCK
In this section, we discuss the construction of reweighting block. Empirically, we use reversed sigmoid function o--2)= I+e= the activation since it's also the derivative of concave non- decreasing merit function. Traditionally, reweighting is achieved in an clement-wise manner: each coefficient will be passed into a derivative of merit function to determine its own weight. This manner introduces self-dependence between coefficients, and the corresponding reweighting block can be expressed as:
(k) + a (-t1()
(x)))))
(6)
with (1)) a temperature parameter. Based on previous analysis, the element-wise manner doesn't 't capture the dependence between elements. Instead, it utilizes the coefficient's 's self-magni the only clue for reweighting.
To inference the sparsity pattern of CSS signals, exploit a global dependencies among coef- ficients of the signal, illustrated at Figure 3 (c). Namely, we build the reweighting block with a full-connection (FC) layer:
w -
(2 (x1
(7)
where the adjacency matrix G E R Different from (6), the FC layer gives the reweighting
block global visual field. Each coefficient is connected all other elements of the signal. Since
each coefficient will pass its influence to other elements through the FC layer and the extent of influence or dependence is measured by the adjacency matrix of FC layer, the learned (k)) in (7) indicates the general sparsity pattern structure of the signals.
We visualized the matrix G learned on synthesized CSS signals recovery in Fig (c) (refer the details of the experiment in Section 3.1). The leamed matrix is notably great in the diagonal areas,
4

---

Under review as a conference paper at ICLR 2020
which means each coefficient is highly dependent its neighbors, but less related to coefficients in a long distance. Generally, it reveals the local dependence coefficients in CSS signals and is illustrated in Figure (b). (b). Consequently, we further introduce convolutional reweighting block to capture such relationship. In this paper we consider a two-layer convolution:
w (k) - (-12 (R)
CC ReLU
U1
1)))))
(8)
(k) denote the convolution kernels with the same size and ReLU denotes the recti- where v/ and 02 fied linear unit defined as max(x, 0) (Nair Hinton 2010). Zero-padding is added to keep the size unchanged. Since the operation of convolution is local receptive and shift-invariant, its naturally suitable for clustered structure sparsity. Moreover, different kernel sizes will give different visual field for the reweighting block. For example, when the kernel size equals 1, it will be reduced to element wise connection manner. Finally, stacked convolutional layers will expand the receptive field and also include more non-linearity in our architecture.
X
X142
(a) Self-Dependence
(b) Local Dependence
(c) Global Dependence
Figure (a) Self-dependence introduced the reweighting block, which corresponds to the element-wise manner. (b) Local dependence introduced in the reweighting block, which is achieved by convolution (illustrated by 3 convolution). (c) Global dependence introduced in the reweighting block, which is conducted by fully connected layers.
NUMERICAL EXPERIMENTS
In this section, the results of Monte Carlo simulation experiments on both synthetic and real data reported for corroborating the above theoretical analysis of the RW-LISTA algorithm. Our periments contain four parts. The first three parts are based on synthetic data, in which we compare RW-LISTA with both learning-based algorithms and classical CSS solvers to verify the effectiveness of our algorithm. In the final part we consider a real-world application of RW-LISTA: recovery of MNIST digit images.
If not specifically mentioned, the depth of all architecture is set to 12. The sensing matrix A in (1) randomly generated with each entry independently drawn from zero-mean Gaussian distribution (O, 1/M), and each column is normalized to have unit l norm. Additive white Gaussian noise (AWGN) is considered and denoted by e, and the signal-to- noise ratio (SNR) in the system is defined as
E|| Ax
SNR
The following average normalized mean square error (NMSE) is defined to evaluate the RW-LISTA and compare with existing cluster structured sparse (CSS) recovery algorithms
x
NMSE 10 E.
(10)
|x|
where || || is the Frobenius norm, and denotes the recovered CSS vector. Our codes are imple-
mented with Python and MATLAB. Models are built on PyTorch (Paszke al. 2017) and trained

---

Under review as a conference paper at ICLR 2020
Pel
(a) Recovered Signals.
(b) Different Reweighting Blocks.
(c) Adjacency Matrix G.
Figure 4: (a) Visualization of recovered signals by LISTA and RW-LSITA. (b) The results of dif- ferent reweighting blocks on synthetic CSS signals, where RwISTA and LISTA are considered for comparison. (c) Visualization of the matrix of one learned reweighting FC layer.
by Adam Optimizer (Kingma& & Ba 2014 All the experiments are performed on a laptop with Intel
Core 17-8750H clocked 2.20 GHz CPU and a NVIDIA GeForce GTX 1060 GPU.
3.1 DIFFERENT REWEIGHTING BLOCKS
In this section, we test different reweighting blocks described in Section 2.3 lution and full-connection. For convolution we consider three kernel sizes, and 7. By setting N 200 and M 100, synthetic CSS signals with non-zero elements are generated following standard Gaussian distribution.
element-wise, convo-
An example of recovered signal by LISTA and RW-LISTA is illustrated in Figure (a), and the re- sults of recovery NMSEs versus different SNR levels after layers/iterations are shown in Figure (b), where RwISTA and LISTA are used for comparison. It is noted that the proposed RW-LISTA achieves significant performance gain with much lower NMSEs, compared to RwISTA and LISTA. In particular, reweighting with 1 convolution achieves the best performance. Furthermore, the superiority of RW-LISTA can be further enlarged as the SNR level increases. get better sense of the pattern learned through the reweighting blocks, the learned weight matrix G in equation (7) from one layer the reweighting blocks is visualized, as shown in Figure 4 (c). The weight is noticeably great in the diagonal area, i.e., each coefficient is highly connected its neighbors. This indicates that the RW-LISTA has successfully learned the clustered structure sparsity. Since such learned matrix assembles the operation of convolution, in the following choose use 1 convolution for the RW-LISTA considering computational cost and recovery performance.
3.2 EFFECTIVENESS OF REWEIGHTING BLOCK
The next experiment will focus verifying the effectiveness of the proposed reweighting block. To achieve this goal, we integrate the reweighting block into LISTA and its successors, i.e., LISTA- CP (Chen et al.) 22188. TIED-LISTA as well as ALISTA (Liu al. 2019a)), and obtain their reweighted versions: RW-ALISTA-CP RW-TIED-LISTA, and RW-ALISTA, We also include the result of LISTAs with support selection proposed in Chen et al. (2018) for comparison (termed as LISTA-SS, LISTA-CPSS, TIED-LISTA-SS, and ALISTA-SS). As before, we generate synthetic CSS signals with non-zero elements following Gaussian Distribution under N 200 and M 100. The results of NMSE comparison between RW-LISTAs and LISTAs in the case of different noisy conditions are presented in Figure (a)-(d) where the curves are depicted by running 10000 Monte Carlo trials.
is clearly observed that the proposed RW-LISTAs with reweighting block achieve significant per- formance improvement compared to LISTA and its variants, especially under relatively high SNR conditions. This implies that the performance of CSS signal recovery has been certainly improved by adaptively reweighting the coefficients in the thresholding operation of ISTA. It is worthwhile noticing that the role the reweighting block becomes more obvious when the level of SNR in- creases.

---

Under review as a conference paper at ICLR 2020
NM48 (18)
Layees
Taperr
(a) SNR 15dB.
(b) SNR 20dB.
SNR 30dB.
(d) SNR 40dB.
Figure 5: Comparisons of reweighted LISTAS with LISTAs at different SNR levels.
Sonhh
DVT
(a) Sparsity.
(b) SNR Level.
(c) Number of Block.
(d) Measurement.
Figure 6: Comparisons of RW-LISTA with state-of-the-art CSS solvers.
3.3 COMPARISON RW-LISTA TO CLASSICAL CSS SOLVERS
Signal recovery techniques for CSS are various and can be roughly classified into two main cate- gories depending on whether the deep learning is involved. In order to demonstrate the advantage of parameter learning based techniques, synthetic CSS data generated for evaluating the RW- LISTA comparison with classical CSS recovery algorithms, including CluSS (Yu et al.) 2012), MBCSLBP YYu et al., 2015), PCSBL (Fang al. 2014), and EBSBL (Zhang & Rao 2013). Sup- pose the sparsity of a x 1 CSS signal is S, i.e., there are S non-zero elements, which consist of T blocks with random sizes and locations. The results are averaged over 500 independents runs.
The effectiveness and robustness of the RW-LISTA are demonstrated in Figure 6 in terms of the following four aspects: i) Sparsity: Note that from Figure 6 (a) the RW-LISTA outperforms the others by large margin, which verifies the theoretical analysis in section 2. The reason lies in that the reweighting block is embedded to improve recovery accuracy while maintaining acceptable computational complexity. ii) Noise level: The RW-LISTA is noise-robust and can achieve higher recovery accuracy than those using classical CSS solvers especially low SNR levels, as shown in Figure 6 (b). Note that the efficient learning via the reweighting block is the key achieve the desired performance. iii) Number of blocks: The number blocks changes when keeping the sparsity unchanged. It is seen in Figure 6 (c) that the NMSE curve of RW-LISTA slightly fluctu- ates as the number blocks increases, and there is a significant performance improvement when compared with existing algorithms. The results in Figure 6 (a) and (c) indicate that the performance degradation mainly results from the change of sparsity rather than the number of blocks. iv) Num- ber of measurements: The effectiveness of the RW-LISTA in coping with different numbers of measurements is likewise demonstrated in Figure (d). It is noted that the RW-LISTA gives rise to substantial gain in the NMSE performance for the reason outlined above. Moreover, find that the curve of the RW-LISTA does not monotonously change with the number of measurements.
As result, the above features of the RW-LISTA strongly relax the constraints on the sparsity, noise level, blocks and measurements of the CSS signals. The reweighting block is therefore regarded as a unit which is well-matched for LISTA architecture.
3.4 EXPERIMENTS ON MNIST DIGITS RECOVERY
To give additional insight of the proposed RW-LISTA into the signals encountered in real-life see- narios, the experiments are carried out on the MNIST dataset. wherein the monochrome images of hand-written numerals and labels exhibit cluster-sparse structure in spatial domain and most of

---

Under review as a conference paper at ICLR 2020
Original
5
6
9
-15.01
-14.59 dB
12.31 dB
02:35 dB
-15.47 dB
-25.82 68
14.09 dB
3.4.5 dB
11..2
.1..00 dB
RW-LISTA
6
-13.03
-11.8 dB
-10.73 de
-11.16 dB
-12:51 de
ds
-11.32 dB
-12.88 d8
-12.40 d8
-14.55 dB
LISTA
CluSS
0.68 d8
6.51 d8
3.25
1.66 6B
2.82 de
1.52 dB
4.27 4B
3.74 4h
0.62 d8
1.19 48
EBS8L
7.64
3.05
4.64
3.12
MBCSLAP
0.97
6.79
2.08
1.09 dB
3.25 dB
4.05 dll
4.45
1.53 dB
2.52 dB
PCSBL
Figure 7:
Reconstructed 20 x 20 digit images on MNIST dataset using different recovery algorithms with N 400, M 200 and SNR 5 dB (Rows from up to down: original images, recovered images by RW-LISTA, LISTA, CluSS, EBSBL, MBCSLBP, and PCSBL)
image pixels are zero. Extension of one-dimensional signal recovery two-dimensional image re- covery is straightforward since the two-dimensional image can be transformed into one-dimensional block-sparse signal. In the experiment, We resize the images in MNIST into 20 20 and normal- ize the pixel value to (0, 1]. Then each image is rasterized into a 400-dimensional vector. We set N 400, M 200 and corrupt the observation with SNR dB. All the 60000 images in the training set have been used to train RW-LISTA.
illustrative example of image signal recovery on MNIST dataset given in Figure 7 with SNR of 5 dB, where the NMSE of each recovered image is annotated for quantitative comparison. The state-of-the-an CluSS, EBSBL, MBCSLBP, PCSBL, and LISTA algorithms are taken as reference for performance comparison with the proposed RW-LISTA. is observed that the results in Figure are in accordance with those in Figure 7 i... the RW-LISTA substantially outperforms the others in preserving the cluster property for different image patterns (We choose the numeral images with distinct sparsity and number of blocks). We also note that the reconstructed images by RW- LISTA are very close the original ones, and this phenomenon of the use of the reweighting block, which is able to well learn the spatial pattern of hand-writte numerals. In contrast, most of state-of-the-un algorithms have the difficulty in recovering the images with real-world spatial structures in such noisy cases largely due to unknown sparse and cluster prior of CSS signals, e.g., cluster locations and the number of clusters.
be regarded
consequence
4 CONCLUSION
In this paper, we explore reweighted deep architecture for the recovery of CSS signals. In the proposed reweighting block, we introduce local dependence of coefficients by convolutional layers, and global dependence by FC layers. Moreover, we choose RwISTA and LISTA as the incarna- tion of our idea and get novel architecture termed RW-LISTA. In light of the above analysis of experimental results, the conclusion reached that the proposed algorithm successfully utilizes the clustered structure of signals and outperforms existing algorithms different tasks. Besides it also gives further insights into the recovery of other types of structured sparsity based on the reweighting mechanism, which pending in the future work.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Fauzia Ahmad and Moeness G Amin. Through-the-wall human motion indication using sparsity- driven change detection. IEEE Transactions on Geoscience and Remote Sensing, 51(2):881-890, 2013.
Amir Beck and Mare Teboulle. fast iterative shrinkage-thresholddng algorithm for linear inverse problems. SIAM journal on imaging sciences, 2(1):183-202, 2009.
Stephen Becker, Jérôme Bobin, and Emmanuel J Candès. Nesta: A fast and accurate first-order method for sparse recovery. SIAM Journal on Imaging Sciences, 4(1):1-39, 2011.
Emmanuel J Candes, Michael B Wakin, and Stephen P Boyd. Enhancing sparsity by reweighted & minimization. Journal of Fourier analysis and applications, 14(5-6):877-905, 2008.
Rick Chartrand and Brendt Wohlberg. A nonconvex admm algorithm for group sparsity with sparse groups. In 2013 IEEE international conference on acoustics, speech and signal processing, pp- 6009-6013. IEEE, 2013.
Xiaohan Chen, Jialin Liu, Zhangyang Wang, and Wotao Yin. Theoretical linear convergence of unfolded ista and its practical weights and thresholds. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances Neural Information Processing Systems 3/, pp. 9061-9071 Curran Associates, Inc., 2018.
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.
Arthur P Dempster, Nan M Laird, and Donald B Rubin. Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statistical Society: Series B (Methodological), 39(1): 1-22, 1977.
David Donoho, Arian Maleki, and Andrea Montanari. Message-passing algorithms for com- pressed sensing, Proceedings of the National Academy of Sciences, 106(45):18114-1891 2009.
Jun Fang, Yanning Shen, Hongbin Li, and Pu Wang. Pattern-coupled sparse bayesian learning for recovery of block-sparse signals. IEEE Transactions on Signal Processing, 63(2):360-372, 2014.
Jun Fang, Lizao Zhang, and Hongbin Li. Two-dimensional pattern-coupled sparse Bayesian learning via generalized approximate message passing. IEEE Transactions on Image Processing, 25(6): 2920-2930, 2016.
Sophie M Fosson. A biconvex analysis for lasso &, reweighting. IEEE Signal Processing Letters, 25(52):195511799 2018.
Raja Giryes, Yonina Eldar, Alex M Bronstein, and Guillermo Sapiro. Tradeoff's between con- vergence speed and reconstruction accuracy in inverse problems. IEEE Transactions Signal Processing, 66(7):1676-1690, 2018
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.
Mareki Honma, Kazunori Akiyama, Fumie Tazaki, Kazuki Kuramochi. Shiro Ikeda, Kazuhiro Hada, and Makoto Uemura. Imaging black holes with sparse modeling. In Journal of Physics: Confer- ence Series, volume 699, pp. 01 2006. IOP Publishing, 2016.
Daisuke Ito, Satoshi Takabe, and Tadashi Wadayama. Trainable ista for sparse signal recovery. IEEE Transactions on Signal Processing. 67(12):111331222 2019.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412 69800, 2014.

---

Under review as a conference paper at ICLR 2020
Jialin Liu, Xiaohan Chen, Zhangyang Wang, and Wotao Yin. ALISTA: Analytic weights are good as learned weights in LISTA. In International Conference on Learning Representations, 2019a.
Zhou Liu, Lei Yu, and Hong Sun. Image restoration via Bayesian dictionary learning with nonlocal structured beta process. Journal of Visual Communication and Image Representation, 52:159- 169, February 2018.
Zhou Liu, Lei Yu, and Hong Sun. Image denoising via nonlocal low rank approximation with local structure preserving. IEEE Access, 7:7117-7132, 2019b.
Michael Lustig, David Donoho, and John M Pauly. Sparse MRI: The application of compressed sensing for rapid MR imaging. Magnetic Resonance in Medicine: An Official Journal of the International Society for Magnetic Resonance in Medicine, 5866) 2007.
Jieqin Lv, Huang Lei, Yunmei Shi, and Xiongjun Fu. Inverse synthetic aperture radar imaging via modified smoothed norm. IEEE Antennas Wireless Propagation Letters, 1365):1235-123) 2014.
Thomas Moreau and Joan Bruna. Understanding trainable sparse coding via matrix factorization. arXiv preprint 1rXi: 160900028, 2016.
Vinod Nair and Geoffrey E Hinton. Rectified linear units improve restricted boltzmann machines. In Proceedings of the 27th international conference machine learning (ICML-10), pp. 807-814, 2010.
Deanna Needell and Joel A Tropp. Cosamp: Iterative signal recovery from incomplete and inaceu- rate samples. Applied and computational harmonic analysis, 26(3):301-33) 2009.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang. Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Ranjitha Prasad, Chandra R Murthy, and Bhaskar D Rao. Joint channel estimation and data detection in MIMO-OFDM systems: A sparse Bayesian learning approach. IEEE Transactions on signal processing, 63(20):5369-3382 2015.
Pablo Sprechmann, Alex Bronstein, Michael Bronstein, and Guillermo Sapiro. Learnable low rank sparse models for speech denoising. In 2013 JEEE International Conference on Acoustics, Speech and Signal Processing, pp. 146-140. IEEE, 2013.
Jian Sun, Huibin Li, Zongben Xu, et al. Deep ADMM-Net for Compressive Sensing MRI. In Advances in neural information processing systems, pp- 10-18. 2016.
Robert Tibshirani, Michael Saunders, Saharon Rosset, Zhu, and Keith Knight. Sparsity and smoothness via the fused LASSO. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 67(1)911-108 2005.
Lu Wang, Lifan Zhao, Guoan Bi, and Chunru Wan. Sparse representation-basee ISAR imaging using Markov random fields. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 8(8):3941-3953, 2014.
J Wright, A Y Yang, Ganesh, S S Sastry, and Yi Ma. Robust Face Recognition via Sparse Representation. IEEE Transaction on Pattern Analysis and Machine Intelligence, 31(2):210-277, 2009.
Lei Yu, Hong Sun. Jean-Pierre Barbot, and Gang Zheng. Bayesian Compressive Sensing for Cluster Structured Sparse Signals. Signal Processing, 22(19:25993)) 2699, January 2012.
Lei Yu, Hong Sun, Gang Zheng, and Jean Pierre Barbot. Model based Bayesian compressive sensing via Local Beta Process. Signal Processing, 1089C))259-271, March 2015.
Jian Zhang and Beraard Ghanem. ISTA-Net: Interpretable Optimization-insiiee inssiieed Deep Network for Image Compressive Sensing. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1828-1837, 2018
10

---

Under review as a conference paper at ICLR 2020
Zhilin Zhang and Bhaskar D Rao. Sparse Signal Recovery with Temporally Correlated Source Vectors using Sparse Bayesian Learning. IEEE Journal of Selected Topics in Signal Processing, 5(5):912-95)) 926, 2011.
Zhilin Zhang and Bhaskar Rao. Extension of SBL Algorithms for the Recovery of Block Sparse Signals with Intra-block Correlation. IEEE Transactions on Signal Processing, 68()::2009s,055 2013.
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 LSTMs for sparse coding. In Thirty-Secone AAAI Conference on Artificial Intelligence, 2018.


Reviews:
[{"review_id": "rylJ1Qhx9H", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper combines deep learning and compressed sensing. Specifically the RW-LISTA algorithm is proposed for cluster-structured sparse recovery, building upon two existing methods: the Reweighted Iterative Shrinkage Algorithm and the LISTA algorithm. The reweighing process is employed to infer the dependencies between coefficients and encourage cluster structure. Strategies for local and global dependence are presented. The approach is evaluated on synthetic and real datasets.\n\nThe paper considers and important topic. However the proposed approach is too incremental and the empirical evaluation could also be improved. In addition the presentation needs more work.  Specifically:\n- the use of unsupervised vs supervised is misleading. Traditional CS approaches are in fact supervised as they map to a regression problem when both input sensing matrix and response vector are available. The distinction has more to do with the ability (or lack of ability) to learn representations.\n- the proposed approach is a straightforward combination of LISTA and RwISTA and the section of global/local dependence regarding cluster-sparse structures is unsurprising.\n- Even though signals may exhibit cluster-sparsity, the size of such cluster might vary widely and it is therefore questionable if such patterns can be best captured via connections in the proposed reweighing blocks. Indeed for some blocks wider or lower neighborhoods might be needed to capture various radii of dependence.  \n- As an alternative to adopting RwISTA it might be pertinent to compare against a counterpart using fused lasso penalty (Tibshirani et al 2005).\n- Experiments are limited: a wider variety of block structure with more or less variability in block size etc should be considered. In addition it would be important to compare against vanilla  Rw-ISTA, as one of the classical CSS solvers.\n- It is somewhat disappointing that the proposed approach should be better the higher the SNR, where other approaches can do well enough. Ideally we are looking to improve in less favorable conditions of low SNR.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "SyxMwM1B5B", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Paper extends LISTA by introducing learned re-weighting for the problem of sparse signal recovery. Paper combines the insights from RW-ISTA (a re-weighted iterative algorithm with fixed parameters and LISTA, a learned iterative algorithm without re-weighting. \n\nResults show that: \n(a) On synthetic data, performance of Rw-LISTA is superior to many variants of LISTA for various SNRs\n(b) On synthetic data, Rw-LIST is better than classical approaches when SNR, Sparsity and other factors are varied. Why is LISTA not compared under all these different variations? \n(c) On MNIST, Rw-LISTA is much better than non-learned approaches, but seems very close to LISTA. \n\nIt strikes me that authors make all evaluations based on NMSE. However, motivation for CSS is that there is structure in the recovered signal — however no comparison of the recovered structure is made. While it is true, that is the signal is perfectly recovered, it would follow the structure from this data was obtained, however no such guarantees can be made for non-zero errors. \n\nI would also like to see what happens whens a pure learning based approach (such as denoting auto-encoders) is used to recover the signal. Do they perform worse than Rw-LISTA? \n\nAt present, I think the paper doesnot meet the standard of ICLR submissions. However, if authors address my concerns, I am happy to change the rating. \n\nMinor Comments:\n“considered as unsupervised approaches since all the paramters are fixed instead of learning from data.” — this is incorrect. A significant human intuition went into design of these systems. While one can argue that even NNet architecture design requires human intuition, the trend is towards using less domain-specific architectures. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "N/A", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "HyxE0iR-cS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "An approach is proposed to learn sparse representations while preserving some structures in the data.\n\nThe idea seems quite nice where we want to learn the structure that induces sparsity instead of simply sparse representations. The idea is to extend a recent algorithm RwISTA by adding reweighting block. The reweighing block changes weights to encode whether coefficients in the model learned by the network are similar or dissimilar to each other. To build the reweighing block convolutional layers are used.\n\nThe paper is slightly hard to read due to many typos, and hard-to-read sentences. Also, I think a more intuitive explanation of how the reweighting helps preserve structure is needed. Right now it is very difficult to understand (except maybe for experts working on similar problems?) Regarding the experiments, most of them are run with synthetic cases. It seems like the approach is compared with several recent approaches though showing good results. On the MNIST data, results are shown where the images are recovered from the sparse representation. I did not really see any substantial improvements in performance as compared to say LISTA. Maybe I am misunderstanding what is being evaluated in Figure 7. Also I am not sure how it shows that the sparse representation is learning the underlying structure? Maybe some re-writing is needed to make this clearer.\n\nI think the paper is interesting but needs some polishing to make it easier to read and perhaps some improved experiments in real datasets.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper is proposed a rejection based on majority reviews.
Decision: Reject