1.

INTRODUCTION

As it is crucial to minimize the sample size required in estimation problems, compressive sensing (CS) plays an indispensable role in the field of signal processing^1-3. Many existing problems can be formulated in terms of compressed sensing (CS), including sparse channel estimation⁴, beam pattern synthesis⁵, direction-of-arrival (DOA) estimation^6,7, and range-Doppler estimation⁸. The recovery is completed by finding a sparse representation of the time-domain signal over a dictionary matrix, which is always a row-sampled discrete Fourier transform (DFT) matrix.

Since this kind of problem is ill-posed, various methods have been proposed. One of the well-known ℓ1-norm regularization techniques is the iterative shrinkage thresholding algorithm (ISTA)⁹, which is often used in a wide range of applications^10,11. Since ISTA is solving a convex optimization problem, it is guaranteed to converge to a solution under the correct circumstances. As an iterative solver, it often costs too much time for ISTA to converge, thus difficult to apply in various real-time applications. Some pre-defined optimization parameters such as the step size and regularization parameter are also required to be set carefully based on prior knowledge, which may become quite challenging in some cases¹².

To address this problem, Gregor and LeCun¹³ have proposed a recurrent neural network (RNN) to solve sparse coding problems, named learned ISTA (LISTA). Based on the iterative structure of ISTA, the authors free the traditional parameters in ISTA to data-driven variables and unfold ISTA algorithms into a RNN structure. LISTA networks show improved performance in terms of convergence speed in both theoretical analysis and empirical results^14-16. Many works have modified LISTA to increase its adaptability by embedding the dictionary in the network architecture. Reference¹⁷ couples the learned matrices in LISTA by embedding the dictionary matrix into the network structure. Based on the work of Reference¹⁷, robust- ALISTA is proposed in Reference¹⁸, which explicitly calculates the learned matrices by solving a coherence minimization problem. Another adaptive variation of LISTA, named Adaptive-LISTA (AdaLISTA)¹⁹, generalizes the application of robust-ALISTA to various model scenarios. Beyond enjoying accelerated convergence speed, AdaLISTA can serve different dictionaries using the same weight matrix without retraining the whole network.

However, all these LISTA-type networks are sensitive to the signal sparsity level. While increasing the number of nonzero elements in the sparse signal of interest, LISTA and its variants will suffer decreased signal recovery accuracy. In practical applications, the recovered signal may not be sufficiently sparse, such as block-sparse problems which recover an unknown, block-sparse signal, where the nonzero elements are distributed in blocks. Based on AdaLISTA, a block-sparse reconstruction network, named Ada-BlockLISTA, has been proposed in Reference²⁰, which makes good use of the natural structure of a block-sparse signal and can recover its nonzero blocks correctly, while original AdaLISTA fails, especially with many nonzero blocks.

In this paper, we formulate the signal model with block structure and introduce relevant iterative algorithms for solving the block-sparse recovery problem in Section 2. By exploring the block structure of the signal model, we introduce Ada-BlockLISTA network in Section 3, and further analyze its convergency rate as well as support recovery guarantee. In numerical simulations, we demonstrate its convergence acceleration and a significant advantage in recovery performance.

2.

SYSTEM MODEL AND TRADITIONAL ALGORITHMS

In this section, we introduce the signal model with block-sparsity and review traditional algorithms such as ISTA and LISTA, which leverage the assumption of sparsity in the ground truth signal.

2.1

System model

We aim to recover an unknown, sparse signal from noisy observations taken from a known, under-determined dictionary Φ ∈ ℂ^N×M, with N < M. In this ill-conditioned problem, noisy observation y ∈ ℂ^N can be formulated as

where x* is the ground truth, and w is additive random noise present in the system. Next, we define block sparsity according to Reference²¹. Suppose that a block-sparse signal x* is divided into Q blocks of length P. If there are at most K nonzero blocks (K ≪ Q) in x*, it is called K-block-sparse. Sharing the same structure with x*, the dictionary matrix Φ is also divided into Q blocks. A visualization of the block-sparse model is shown in Figure 1.

Figure 1.

A visualization of the block-sparse signal model where each color in Φ and x corresponds to a different block. White corresponds to zero entries in x.

2.2

Brief review of traditional algorithms

This subsection briefly reviews traditional algorithms such as ISTA and LISTA, designed to solve sparse problems. In the framework of CS, the ℓ1-regularized regression is a well-known technique to harness prior knowledge of sparsity. Standard ISTA solves the ℓ1-regularized optimization problem by iteratively performing Lipschitz gradient descent with respect to the measurement error^9,22.

While the signal of interest x possesses a block-sparse structure, many researchers have designed specialized algorithms in principle to utilize the block-sparse structure, such as Block ISTA²⁰, block-OMP²³, block-based CoSaMP²⁴ and block-sparse Bayesian learning²⁵. To compute an estimate which maintains a block-sparse structure, the original ℓ1-norm optimization problem turns into the following mixed-norm optimization problem as follows,

where is the estimated signal, and λ is a regularization parameter controlling the sparsity penalty characterized by minimizing the ℓ2,1 norm.

ISTA demonstrates considerable accuracy in recovering sparse signals but takes too much time to converge²⁶. As an unfolded version of ISTA iterations, LISTA is a RNN containing only T layers, where each layer corresponds to an ISTA iteration¹³. To build a more generalized network for various dictionary choices, AdaLISTA, a variant of LISTA, has been proposed to increase the adaptability of the deep unfolding network¹⁹. One layer of AdaLISTA is defined as,

where x^(k) is the output signal of the k-th layer, W ∈ ℂ^N×N is the learned weight shared across different layers, while θ^(k), γ^(k) are the learned soft threshold and step size of the k-th layer in AdaLISTA.

3.

BLOCK-SPARSE RECOVERY NETWORK AND CONVERGENCE ANALYSIS

Motivated by ℓ2,1 minimization methods such as Block-ISTA, we explore the block structure of the signal model and propose our Ada-BlockLISTA network, which is derived from AdaLISTA.

As Φ and x* share the same block structure, i.e., and Φ=[Φ₁ Φ₂ ⋯ Φ_Q], we learn an individual weight matrix {W_q}_1≤q≤Q for each block and encourage block sparsity for the nonlinear shrinkage function by applying soft thresholding to each block individually. At the k-th layer of Ada-BlockLISTA, the update rule of the q-th block in the block-sparse signal is formulated as,

where is the q-th block of after block-wise gradient descent, and is the q-th block of the output signal x^(k+1) after block-wise soft thresholding. In Ada-BlockLISTA, we need to learn the individual weight W_q for the q-th block, as well as the learned soft threshold θ^(k) and the learned step size γ^(k).

As shown above, Ada-BlockLISTA consists of two main steps.

Figure 2.

The Block diagram of AdaLISTA architecture in one layer.

Figure 3.

The Block diagram of Ada-BlockLISTA architecture in one layer.

Comparing Figures 2 and 3, we can see that Ada-BlockLISTA updates each block in x independently, while AdaLISTA uses the same weight across different blocks. Furthermore, AdaLISTA and Ada-BlockLISTA use the soft threshold parameters {θ^(k)}_1≤k≤T in different ways. In AdaLISTA, we perform element-wise soft thresholding and set each element in x^(k) with an absolute value less than θ^(k) to 0. On the other hand, we use θ^(k) as a block-wise threshold in Ada-BlockLISTA, which is compared with the ℓ2 norm of every single block rather than the absolute value of elements.

Then we show some main theoretical results, i.e., the linear convergence rate and support recovery guarantee of Ada-BlockLISTA. We generalize the two basic definitions of coherence²¹, i.e., the mutual coherence within a block, also referred to as sub-coherence, and block-coherence of the dictionary, which describe its local and global properties, respectively.

Here we illustrate the linear convergence rate of our Ada-BlockLISTA in the following theorem (More details on the convergence analysis of Ada-BlockLISTA can be found in the arXiv article: https://arxiv.org/abs/2111.09801). The proof of Theorem 1 mimics the corresponding proof steps in References^18,19 and can be viewed as an extension to the block-sparse case.

Theorem 1 (Convergence rate of Ada-BlockLISTA).

We first consider the three quantities,

Suppose x* to be sufficiently small such that , and the soft thresholds are set as where σ is the standard deviation of noise, then Ada-BlockLISTA converges linearly, i.e., its recovered error decreases exponentially with the number of layers.

The above theorem can be interpreted in two aspects:

4.

NUMERICAL RESULTS

We simulate various experiments with different signal dimensions and the number of nonzero blocks. In our simulation, we set P = 16 and Q = 64, respectively. We generate observed signals according to Reference²⁷. In Figures 4 and 5, we compared the convergence speed and recovered the 2D block-sparse signal plane of four methods (ISTA, Block-ISTA, AdaLISTA and our Ada-BlockLISTA) when the block sparsity K is 2.

Figure 4.

The NMSE of four methods in each iteration/layer.

Figure 5.

The reconstructed block sparse signal, which has two nonzero blocks.

The results show that Block ISTA and Ada-BlockLISTA successfully reconstruct two blocks, while ISTA and AdaLISTA fail. It demonstrates that block sparse recovery methods can recover a larger number of blocks than their non-block counterparts, which is also proved in Theorem 1.

5.

CONCLUSION

In this work, we considered the block-sparse signal recovery problem, where nonzero entries of recovered signals occur in clusters. A block-sparse reconstruction network, Ada-BlockLISTA, explores the block structure in the signal model. We prove that the unrolled block-sparse reconstruction network enjoys a linear convergence rate and provides a sufficient condition on block-sparsity to guarantee the successful recovery of block-sparse signals. We performed extensive simulations to verify the recovery performance of the proposed network. The numerical results show that Ada-BlockLISTA yields better reconstruction properties than the original AdaLISTA network, especially with a large number of nonzero blocks. We demonstrate that explicit use of block-sparsity in unfolded deep learning networks improves block-sparse recovery performance by conducting theoretical and experimental analyses.