{'fraction_non_alphanumeric': 0.05486959392538791, 'fraction_numerical': 0.015450643776824034, 'mean_word_length': 4.226363008971704, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Onsager-corrected deep learning for sparse linear inverse problems

Deep learning has gained great popularity due to its widespread success on many inference problems. We consider the application of deep learning to the sparse linear inverse problem encountered in compressive sensing, where one seeks to recover a sparse signal from a small number of noisy linear measurements. In this paper, we propose a novel neural-network architecture that decouples prediction errors across layers in the same way that the approximate message passing (AMP) algorithm decouples them across iterations: through Onsager correction. Numerical experiments suggest that our"learned AMP"network significantly improves upon Gregor and LeCun's"learned ISTA"network in both accuracy and complexity.


INTRODUCTION
We consider the problem of recovering a signal s ∈ C N from a noisy linear measurement where Φ ∈ C M ×N represents a linear measurement operator and n ∈ C M a noise vector. In many cases of interest, M ≪ N . We will assume that the signal vector s has a sparse representation in a known orthonormal basis Ψ ∈ C N×N , i.e., that s = Ψx for some sparse vector x ∈ C N . Thus we define A ΦΨ ∈ C M ×N , write (1) as and seek to recover an sparse x from y. In the sequel, we will refer to this problem as the "sparse linear inverse" problem. Note that the resulting estimate x of x can be easily converted into an estimate s of s via s = Ψ x. The sparse linear inverse problem has received enormous attention over the last few years, in part because it is central to compressive sensing [1] and sparse coding [2]. Many methods have been developed to solve this problem. Most of the existing methods involve a reconstruction algorithm that inputs a pair (y, A) and produces an sparse estimate x. A myriad of such algorithms have been proposed, including both sequential (e.g., greedy) and iterative varieties. Some relevant algorithms will be reviewed in Section Section 2.1.
Recently, a different approach to solving this problem has emerged from the field of "deep learning," whereby a neural network with many layers is trained using a set of D examples 2 {(y (d) , x (d) )} D d=1 . Once trained, the network can be used to predict the sparse x that corresponds to a given input y. Note that knowledge of the operator A is not necessary here. Previous work (e.g., [3][4][5][6]) has shown that the deep-learning approach to solving sparse linear inverse problems has the potential to offer significant improvements, in both accuracy and complexity, over the traditional algorithmic approach.
Relation to prior work: In this paper, we show how recent advances in iterative reconstruction algorithms suggest modifications to traditional neural-network architectures that yield improved accuracy and complexity when solving sparse linear inverse problems. In particular, we show how "Onsager correction," which lies at the heart of the approximate message passing (AMP) algorithm [7], can be employed to construct deep networks with increased accuracy and computational efficiency (i.e., fewer layers needed to produce an accurate estimate). To our knowledge, the application of Onsager correction to deep neural networks is novel.

Iterative Algorithms
One of the best known algorithmic approaches to solving the sparse linear inverse problem is through solving the convex optimization problem [8,9] x = arg min where λ > 0 is a tunable parameter that controls the tradeoff between sparsity and measurement fidelity in x. The convexity of (3) leads to provably convergent algorithms and bounds on the performance of the estimate x (see, e.g., [10]).

FISTA
Although ISTA is guaranteed to converge under β ∈ (0, 1/ A 2 2 ) [12], it converges somewhat slowly and so many modifications have been proposed to speed it up. Among the most famous is "fast ISTA" (FISTA) [13], which converges in roughly an order-of-magnitude fewer iterations than ISTA (see Fig. 1).

AMP
Recently, the approximate message passing (AMP) algorithm [7,14] was applied to (3), giving for x0 = 0, v−1 = 0, t = 0, 1, 2, . . . , and Here, α is a tuning parameter that has a one-to-one correspondence with λ in (3) [14]. Comparing AMP to ISTA, we see two major differences: i) AMP's residual vt in (7a) includes the "Onsager correction" term btvt−1, and ii) AMP's denoising threshold λt in (7b) takes the prescribed, t-dependent value (9). We now describe the rationale behind these differences. When A is a typical realization of a large i.i.d. (sub)Gaussian random matrix with entries of variance M −1 , the Onsager correction decouples the AMP iterations in the sense that the input to the denoiser, rt xt + A H vt, can be modeled as 3 In other words, the Onsager correction ensures that the denoiser input is an additive white Gaussian noise (AWGN) corrupted version of the true signal x with known AWGN variance σ 2 t . (See Fig. 5.) The resulting problem, known as "denoising," is well understood. For example, for an independent known prior p(x) = N j=1 pj(xj), the mean-squared error (MSE)-optimal denoiser 4 is simply the posterior mean estimator (i.e., xt+1,j = E{xj |rt,j; σt}), which can be computed in closed form for many pj(·). In the more realistic case that pj(·) are unknown, we may be more interested in the minimax denoiser, i.e., minimizer of the maximum MSE over an assumed family of priors. Remarkably, for sparse priors, i.e., pj(xj) = (1−γ)δ(xj)+γ pj(xj) with γ ∈ (0, 1) and arbitrary unknown pj(·), soft-thresholding (5) with a threshold proportional to the AWGN standard deviation (i.e., λt = ασt as in (9)) is nearly minimax optimal [14]. Thus, we can interpret the AMP algorithm (7) as a nearly minimax approach to the sparse linear inverse problem. 3 The AMP model (10) is provably accurate in the large-system limit (i.e., M, N → ∞ with M/N converging to a fixed positive constant) [15]. 4 AMP with MSE-optimal denoising was first described in [16].

Comparison of ISTA, FISTA, and AMP
We now compare the average per-iteration behavior of ISTA, FISTA, and AMP for an A drawn i.i.d. N (0, M −1 ). In our experiment, all quantities were real-valued, the problem dimensions were N = 500 and M = 250, the elements of x were drawn i.i.d. N (0, 1) with probability γ = 0.1 and were otherwise set to zero, and the noise n was drawn i.i.d. N (0, v) with v set to yield a signal-to-noise ratio (SNR) of 40 dB. Recall that ISTA, FISTA, and AMP all estimate x by iteratively minimizing (3) for a chosen value of λ (selected via α in the case of AMP). We chose the minimax optimal value of α for AMP (which is 1.1402 since γ = 0.1 [14]) and used the corresponding λ for ISTA and FISTA. Figure 1 shows the average normalized MSE (NMSE) versus iteration t, where NMSE xt − x 2 2 / x 2 2 and 1000 realizations of (x, n) were averaged. We see that AMP requires roughly an order-of-magnitude fewer iterations than FISTA, which requires roughly an order-of-magnitude fewer iterations than ISTA.

Deep Learning
In deep learning [17], training data {(y (d) , x (d) )} D d=1 composed of (feature,label) pairs are used to train the parameters of a deep neural network with the goal of accurately predicting the label x of a test feature y. The deep network accepts y and subjects it to many layers of processing, where each layer consists of a linear transformation followed by a non-linearity.
Typically, the label space is discrete (e.g., y is an image and x is its class in {cat, dog,. . . , tree}). In our sparse linear inverse problem, however, the "labels" x are continuous and high-dimensional (e.g., C N or R N ). Remarkably, Gregor and LeCun demonstrated in [3] that a well-constructed deep network can accurately predict even labels such as ours.
The neural network architecture proposed in [3] is closely related to the ISTA algorithm discussed in Section 2.1.1. To understand the relation, we rewrite the ISTA iteration (4) as and "unfold" iterations t = 1...T , resulting in the T -layer feedforward neural network shown in Fig. 2. Whereas ISTA uses the values of S and B prescribed in (11) and a common value of λ at all layers, Gregor and LeCun [3] proposed to use layer-dependent thresholds λ [λ1, λ2, . . . , λT ] and "learn" both the thresholds λ and the matrices B, S from the training data {(y (d) , x (d) )} D d=1 by minimizing the quadratic loss Here, Θ = [B, S, λ] denotes the set of learnable parameters and xT (y (d) ; Θ) the output of the T -layer network with input y (d) and parameters Θ. The resulting approach was coined "learned ISTA" (LISTA). Relative to existing algorithms for the sparse linear inverse problem with optimally tuned regularization parameters (e.g., λ or α), LISTA generates estimates of comparable MSE with significantly fewer matrix-vector multiplications. As an example, for the problem described in Section 2.1.4, LISTA took only 16 layers to reach an NMSE of −35 dB, whereas AMP took 25 iterations. (More details will be given in Section 4.) Other authors have also applied ideas from deep learning to the sparse linear inverse problem. For example, [4] extended the approach from [3] to handle structured sparsity and dictionary learning (when the training data are {y (d) } D d=1 and A is unknown). More recently, [6] extended [3] from the ℓ2 + ℓ1 objective of (3) to the ℓ2 +ℓ0 objective, and [5] proposed to learn the MSE-optimal scalar denoising function η by learning the parameters of a B-spline. The idea of "unfolding" an iterative algorithm and learning its parameters via training data has also been used to recover non-sparse signals. For example, it has been applied to speech enhancement [18], image deblurring [19], image super resolution [20], compressive imaging [21,22], and video compressive sensing [23].

LEARNED AMP
Recall that LISTA involves learning the matrix S IN − BA, where B ∈ C N×M and A ∈ C M ×N . As noted in [3], when M < N/2, it is advantageous to leverage the IN − BA structure of S, leading to network layers of the form shown in Fig. 3, with firstlayer inputs x0 = 0 and v0 = y. Although not considered in [3], the network in Fig. 3 allows both A and B to vary with the layer t, allowing for modest improvement (as will be demonstrated in Section 4).

The LAMP Network
We propose to construct a neural network from unfolded AMP (7) with tunable parameters {At, Bt, αt} T −1 t=0 learned from training data. The hope is that a "learned AMP" (LAMP) will require fewer layers than LISTA, just as AMP typically requires many fewer iterations than ISTA to converge. Figure 4 shows one layer of the LAMP network. Comparing Fig. 4 to Fig. 3, we see two main differences: 1. LAMP includes a feed-forward path from vt to vt−1 that is not present in LISTA. This path implements an "Onsager correction" whose goal is to decouple the layers of the network, just as it decoupled the iterations of the AMP algorithm (recall Section 2.1.3). 2. LAMP's denoiser threshold λt = αt vt 2/ √ M varies with the realization vt, whereas LISTA's is constant. Note that LAMP is built on a generalization of the AMP algorithm (7) wherein the matrices (A, A H ) manifest as (At, Bt) at iteration t. An important question is whether this generalization preserves the independent-Gaussian nature (10) of the denoiser input error-the key feature of AMP. It can be shown that the desired behavior does occur when i) At = βtA with scalar βt and ii) Bt = A H Ct with appropriately scaled Ct. Thus, for LAMP, we impose 5 At = βtA and learn only βt, and we initialize Bt appropriately before learning.
From Fig. 4, we see that the βt scaling within At can be moved to the denoiser η(·; ·) under a suitable re-definition of xt, and we take this approach in LAMP. Thus, the tth layer of LAMP can be summarized as with first-layer inputs x0 = 0 and v0 = y. Figure 5(c) shows the QQplot of LAMP's denoiser input error xt + Btvt − x. The shape of the plot confirms that the error is Gaussian.

Learning The LAMP Parameters
Our proposed learning procedure is described below, where it is assumed that A is known. But if A was unknown, it could be estimated using a least-squares fit to the training data. Empirically, we find that there is essentially no difference in final test MSE between LAMP networks where i) A is known, ii) A is estimated via leastsquares, or iii) A is learned using back-propagation to minimize the loss LT from (12).

Untied {Bt}
In the "untied" case, Bt is allowed to vary across layers t. We propose the same learning procedure as above, but with one exception: when initializing the parameters for each new layer, we initialize Bt at the regularized pseudo-inverse (14) rather than the learned value Bt−1.

Structured Bt
Motivated by the M < N case, we recommend constraining Bt = A H Ct and learning only Ct ∈ C M ×M , which reduces the number of free parameters in Bt from M N to M 2 . After these Bt are learned, there is no need to represent them in factored form, although doing so may be advantageous if A has a fast implementation (e.g., FFT). Empirically, we find that there is essentially no difference in final test MSE between LAMP networks where i) Bt is unconstrained and ii) Bt = A H Ct. However, the learning procedure is more efficient in the latter case.

NUMERICAL RESULTS
We now evaluate the performance of LISTA and LAMP on the sparse linear inverse problem described in Section 2.1.4. The data were generated as described in Section 2.1.4, with training mini-batches of size D = 1000 and a single testing mini-batch of size 1000 (drawn independently of the training data). The training and testing methods were implemented in Python using TensorFlow [24] with the ADAM optimizer [25]. For LAMP, we performed the learning as described in Section 3.2. For LISTA, we used the same approach to learn "untied" B0, S0, {λt} T −1 t=0 and "tied" {Bt, St, λt} T −1 t=0 , with no constraints on St or Bt (because we found that adding constraints degraded performance).  Figure 6 shows average test NMSE xt − x 2 2 / x 2 versus layer t for the same i.i.d. Gaussian A and test data used to create Fig. 1, allowing a direct comparison. The figure shows LAMP significantly outperforming LISTA and AMP in convergence time and final NMSE. For example, to reach −34 dB NMSE, tied-LAMP took only 7 layers, tied-LISTA took 15, and AMP took 23. Figure 7 shows the results of a similar experiment, but where the singular values of A were replaced by a geometric sequence that yielded A 2 F = N and a condition-number of 15. For this A, AMP diverged but LAMP did not, due in part to the "preconditioning" effect of (14).
The figures also show that the untied versions of LAMP and LISTA yielded small improvements over the tied versions, but at the cost of a T -fold increase in parameter storage plus significantly increased training time.

CONCLUSION
We considered the application of deep learning to the sparse linear inverse problem. Motivated by the AMP algorithm, we proposed the use of Onsager correction in deep neural networks, for the purpose of decoupling and Gaussianizing errors across layers. Empirical results demonstrated improved accuracy and efficiency over Gregor and LeCun's LISTA [3].