# Convergence of Slice-Based Block Coordinate Descent Algorithm for Convolutional Sparse Coding

Authors: Jing Li; Hui Yu; Xiao Wei; Jinjia Wang
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

Convolutional sparse coding (CSC) models are becoming increasingly popular in the signal and image processing communities in recent years. Several research studies have addressed the basis pursuit (BP) problem of the CSC model, including the recently proposed local block coordinate descent (LoBCoD) algorithm. This algorithm adopts slice-based local processing ideas and splits the global sparse vector into local vector needles that are locally computed in the original domain to obtain the encoding. However, a convergence theorem for the LoBCoD algorithm has not been given previously. This paper presents a convergence theorem for the LoBCoD algorithm which proves that the LoBCoD algorithm will converge to its global optimum at a rate ofO1/k. A slice-based multilayer local block coordinate descent (ML-LoBCoD) algorithm is proposed which is motivated by the multilayer basis pursuit (ML-BP) problem and the LoBCoD algorithm. We prove that the ML-LoBCoD algorithm is guaranteed to converge to the optimal solution at a rate O1/k. Preliminary numerical experiments demonstrate the better performance of the proposed ML-LoBCoD algorithm compared to the LoBCoD algorithm for the BP problem, and the loss function value is also lower for ML-LoBCoD than LoBCoD.


---

## Body

## 1. Introduction

Sparse representation models have been widely used in various image processing [1, 2] and computer vision [3, 4] applications. A sparse representation model assumes that signals X∈RN can be expressed as a linear combination of several columns, i.e., X=DΓ, where D is a matrix that forms the dictionary D∈RN×Nm, and Γ∈RNm is a sparse vector. If D is assumed to be fixed, it can be considered a basis pursuit (BP) problem to find the sparse vector Γ. However, the BP algorithms are only encoded in patches and ignore the relationship between neighboring patches, resulting in a high degree of redundancy in the encoding. The convolution sparse coding (CSC) model [5] has been proposed and extended in the last ten years, and it imposes constraints on the dictionary by using a banded circulant matrix. This model assumes that the signal can be represented as the superposition of a few local filters, convolved with a sparse vector. Several works have presented algorithms for solving the CSC problem [6, 7]. Contemporary BP algorithms for CSC often rely on the Alternating Direction Methods of Multipliers (ADMM) algorithm in the Fourier domain. It is known that algorithms encoded in the Fourier domain are often computationally infeasible. Additionally, algorithms based on the ADMM formula need to introduce auxiliary variables which increases the difficulty of optimization. A recent work proposed by Papyan et al. [8], adopted slice-based local processing ideas and split the global sparse vector Γ into local vector needles that are locally computed in the original domain rather than the Fourier domain to obtain the encoding. While this approach still relies on the ADMM algorithm, its convergence largely depends on the auxiliary variables that were introduced. The LoBCoD algorithm [9] is another algorithm that was proposed for the BP problem. The advantages of the LoBCoD algorithm are that it is not calculated on the Fourier domain and the calculation does not use the ADMM formula. More precisely, the LoBCoD algorithm optimizes needles of the CSC model in the original domain and operates without any auxiliary variables. Compared with global or local ADMM-based methods, the LoBCoD algorithm achieves better performance to solve the BP problem. However, the literature [9] does not provide convergence theorem for the LoBCoD algorithm. Thus, this paper will present a convergence theorem and proof of the LoBCoD algorithm.A multilayer convolution sparse coding (ML-CSC) model has been proposed in the last three years by Sulam et al. [10], which is a deep extension of the CSC model. The core assumption of the ML-CSC model is that a signal can be expressed by sparse representations at different layers in terms of nested convolutional filters. The traditional BP problem was recently extended to a multilayer setting, which was motivated by the ML-CSC model [11]. Several methods have been proposed to solve the ML-BP problem. The first method is a layered basis pursuit algorithm [12], which establishes a connection between convolutional neural networks and sparse modeling. However, layered basis pursuit algorithm does not provide a signal that satisfies the assumption of the multilayer model, and the signal reconstruction error increases as the network deepens. Subsequently, the multilayer iterative threshold algorithm (ML-ISTA) and its fast version (ML-FISTA) algorithm [11] were proposed, which only require matrix multiplications and entry-wise operations and will converge well to the global optimal. Unfortunately, both methods operate on patches only and do not utilize slice-based local processing idea. Therefore, the slice-based ML-LoBCoD algorithm is proposed for ML-BP problem. This algorithm employs slice-based local processing idea and the block coordinate descent (BCD) method. Based on the convergence theorem proof of the block coordinate descent algorithm [13], this paper provides a convergence theorem for the ML-LoBCoD algorithm and proves that the ML-LoBCoD algorithm converges to the global optimal value at a rate of O1/k.The rest of this paper is organized as follows. We begin by reviewing the slice-based CSC and slice-based LoBCoD algorithms in Section2. The convergence theorem and proof of the LoBCoD algorithm are given in Section 3. In Section 4, we propose a slice-based ML-CSC model and a slice-based ML-LoBCoD algorithm. The convergence theorem and proof of the slice-based ML-LoBCoD algorithm are given in Section 5. In Section 6, the experimental results of the signal reconstruction and classification accuracy of the two networks inspired by the two algorithms are given. Finally, we conclude this work in Section 7.


## 2. Background

### 2.1. Slice-Based Convolutional Sparse Coding

The CSC model assumes that a global signalX∈RN can be decomposed as X=DΓ=∑i=1mdi∗Γi, where D∈RN×Nm is a banded convolutional dictionary that consists of all shifted versions of a local dictionary DL∈Rn×m, di∈Rn are local filters that are extracted from DL, the global sparse vector Γ∈RNm contains the interlacing cascades of all the sparse representations Γi∈RN, and Γi is the corresponding sparse representation of local filter di. Using the above formula, the BP problem can be expressed as(1)minΓ12X−DΓ22+λΓ1.The global sparse vectorΓ can be decomposed into N nonoverlapping m-dimensional local sparse vectors, αii=1N, which are called needles [8], i.e., Γ=α1,…,αs,…,αN. Thus, the global signal X can be expressed as X=∑i=1NPiTDLαi, where PiT∈RN×n is the operator that places DLαi in the ith position and pads the remaining entries with zeros. Therefore, the BP problem (1) can be expressed as a local problem:(2)minαii=1N12X−∑i=1NPiTDLαi22+λ∑i=1Nαi1.Papyan et al. proposed the slice-based local processing idea and definedsi=DLαi as the ith slice. The global signal X can be rewritten as X=∑i=1NPiTsi. Then, the slice-based BP problem (2) can be expressed as(3)minαii=1N,sii=1N12X−∑i=1NPiTsi22+λ∑i=1Nαi1,s.t.si=DLαi.Papyan et al. tackled the BP problem (3) using the ADMM algorithm [8], which minimizes the following augmented Lagrangian problem:(4)minDL,αii=1N,sii=1N,uii=1N12X−∑i=1NPiTsi22+∑i=1Nλαi1+ρ2si−DLαi+ui22.Here,uii=1N denotes the dual variables of the ADMM formulation.


### 2.2. Slice-Based Local Block Coordinate Descent Algorithm

The CSC model parameters are represented by the local sparse vectorsαi and the local dictionary DL. Assuming DL is fixed, a slice-based local processing idea and block coordinate descent method are adopted to update the needles.fα1k,…,αs−1k,αs,αs+1k,…,αNk is objection function of equation (2). The BCD algorithm [14] will be briefly described below.Initialization: choose anyΓ0=α10,…,αN0, k=0Iteration: choose an indexs∈1,…,N and compute(5)Γsk+1∈argminαsfα1k,…,αs−1k,αs,αs+1k,…,αNk,αjk+1=αjk,∀j≠s,k=k+1,until the convergence condition is met.Output:Γk+1=α1k+1,…,αNk+1In this paper, each needleαi can be treated as a block of coordinates taken from the global vector which can be optimized separately with respect to each block in sequence.Consequently, the update rule for each needle can be written as(6)minαi12X−∑j=1Nj≠iPjTDLαj−PiTDLαi22+λαi1,i=1,…,N.Equation (6) can be decomposed into a local problem:(7)minαi12PiRi−DLαi22+λαi1,i=1,…,N,where Ri=X−∑j=1j≠iNPjTDLαj is global variable, representing the residual image without the contribution of needle αi, and Pi∈Rn×N is the transpose of PiT, representing the operator that extracts the ith n-dimensional patch from X.The LoBCoD algorithm is proposed to minimize equation (7) [9]. The function fαi=1/2PiRi−DLαi22 can be defined, which is a convex smooth function. The LoBCoD algorithm can be considered to be a generalized gradient algorithm that applies an update in the form αk+1←αk−∇fαk, where ∇fαi=DLTDLαi−PiRi. The update rule for each needle αi can be expressed as(8)αik+1=Sλαik+DLTPiRi−DLαik.


## 2.1. Slice-Based Convolutional Sparse Coding

The CSC model assumes that a global signalX∈RN can be decomposed as X=DΓ=∑i=1mdi∗Γi, where D∈RN×Nm is a banded convolutional dictionary that consists of all shifted versions of a local dictionary DL∈Rn×m, di∈Rn are local filters that are extracted from DL, the global sparse vector Γ∈RNm contains the interlacing cascades of all the sparse representations Γi∈RN, and Γi is the corresponding sparse representation of local filter di. Using the above formula, the BP problem can be expressed as(1)minΓ12X−DΓ22+λΓ1.The global sparse vectorΓ can be decomposed into N nonoverlapping m-dimensional local sparse vectors, αii=1N, which are called needles [8], i.e., Γ=α1,…,αs,…,αN. Thus, the global signal X can be expressed as X=∑i=1NPiTDLαi, where PiT∈RN×n is the operator that places DLαi in the ith position and pads the remaining entries with zeros. Therefore, the BP problem (1) can be expressed as a local problem:(2)minαii=1N12X−∑i=1NPiTDLαi22+λ∑i=1Nαi1.Papyan et al. proposed the slice-based local processing idea and definedsi=DLαi as the ith slice. The global signal X can be rewritten as X=∑i=1NPiTsi. Then, the slice-based BP problem (2) can be expressed as(3)minαii=1N,sii=1N12X−∑i=1NPiTsi22+λ∑i=1Nαi1,s.t.si=DLαi.Papyan et al. tackled the BP problem (3) using the ADMM algorithm [8], which minimizes the following augmented Lagrangian problem:(4)minDL,αii=1N,sii=1N,uii=1N12X−∑i=1NPiTsi22+∑i=1Nλαi1+ρ2si−DLαi+ui22.Here,uii=1N denotes the dual variables of the ADMM formulation.


## 2.2. Slice-Based Local Block Coordinate Descent Algorithm

The CSC model parameters are represented by the local sparse vectorsαi and the local dictionary DL. Assuming DL is fixed, a slice-based local processing idea and block coordinate descent method are adopted to update the needles.fα1k,…,αs−1k,αs,αs+1k,…,αNk is objection function of equation (2). The BCD algorithm [14] will be briefly described below.Initialization: choose anyΓ0=α10,…,αN0, k=0Iteration: choose an indexs∈1,…,N and compute(5)Γsk+1∈argminαsfα1k,…,αs−1k,αs,αs+1k,…,αNk,αjk+1=αjk,∀j≠s,k=k+1,until the convergence condition is met.Output:Γk+1=α1k+1,…,αNk+1In this paper, each needleαi can be treated as a block of coordinates taken from the global vector which can be optimized separately with respect to each block in sequence.Consequently, the update rule for each needle can be written as(6)minαi12X−∑j=1Nj≠iPjTDLαj−PiTDLαi22+λαi1,i=1,…,N.Equation (6) can be decomposed into a local problem:(7)minαi12PiRi−DLαi22+λαi1,i=1,…,N,where Ri=X−∑j=1j≠iNPjTDLαj is global variable, representing the residual image without the contribution of needle αi, and Pi∈Rn×N is the transpose of PiT, representing the operator that extracts the ith n-dimensional patch from X.The LoBCoD algorithm is proposed to minimize equation (7) [9]. The function fαi=1/2PiRi−DLαi22 can be defined, which is a convex smooth function. The LoBCoD algorithm can be considered to be a generalized gradient algorithm that applies an update in the form αk+1←αk−∇fαk, where ∇fαi=DLTDLαi−PiRi. The update rule for each needle αi can be expressed as(8)αik+1=Sλαik+DLTPiRi−DLαik.


## 3. Convergence of Slice-Based Local Block Coordinate Descent Algorithm

The convergence theorem will now be proposed and proof of LoBCoD algorithm will be given.Lemma 1.
(fundamental proximal gradient inequality).
Assume thatf is a convex smooth function, g is a convex function, and TLy=TLf,gy is proximal gradient operator. For any x∈Rm, y∈intdomf, L>0, satisfying(9)fTLy≤fy+∇fy,TLy−y+L2TLy−y2,it holds that(10)Fx−FTLy≥L2x−TLy2−L2x−y2+lfx,y,where(11)lfx,y=fx−fy−∇fy,x−y.Theorem 1.
(convergence of LoBCoD).
Given a signalX and local dictionary DL, the slice-based LoBCoD algorithm is guaranteed to converge to the optimal solution at a rate Ο1/k.Proof.
The optimization problem of CSC can be represented as a general minimization model as follows:(12)minαii=1NFαi≡fαi+gαi:αi∈Rm,where fαi=1/2PiRi−DLαi22 and gαi=λαi1 are convex functions. The gradient of fαi is Lipschitz continuous. αi∗ is defined to represent the nonempty optimal problem set of problem (12), and the optimal object function value is represented by Fαi∗. According to the proximal gradient method, the general update step of αi can be written in the following form:(13)αik+1=prox1/Lgαik+1LDLTPiRi−DLαik.
Due to the proximal gradient operatorTLf,gαi=prox1/Lgαi−1/L∇fαi, L is the Lipschitz constant of fαi. Therefore, the update step of each needle αi can be written in the following form:(14)αik+1=TLf,gαik.
Exploiting the fundamental proximal gradient inequality and makingx=αi∗,y=αin, we obtain(15)2LFαi∗−FTLf,gαin≥αi∗−αin+12−αi∗−αin2+2Llfαi∗,αin≥αi∗−αin+12−αi∗−αin2.
When all of the above inequalities are added together forn=0,…,k, the following result is obtained:(16)2L∑n=0k−1Fαi∗−Fαin+1≥∑n=0k−1αi∗−αin+12−αi∗−αin2.
The following result is obtained using the scaling method:(17)∑n=0k−1Fαin+1−Fαi∗≤L2αi∗−αi02−L2αi∗−αin2≤L2αi∗−αi02.
Thus, we obtain(18)kFαik−Fαi∗≤∑n=0k−1Fαin+1−Fαi∗≤L2αi∗−αi02.
Finally, we obtain(19)Fαik−Fαi∗≤L2kαi∗−αi02.
Since the sparse vectorΓ can be decomposed into nonoverlapping m-dimensional sparse vectors αii=1N and αi is convergent, we can obtain convergence of Γ and the convergence rate is constant with αi. Thus, the LoBCoD algorithm convergences to the global optimum at a rate of Ο1/k.


## 4. Slice-Based Multilayer Local Block Coordinate Descent Algorithm

### 4.1. Slice-Based Multilayer Convolutional Sparse Coding

The ML-CSC model is a deep extension of the CSC model, since the ML-CSC model assumes that the signal can be represented by a sparse representation of the nested convolution filter on different layers. The ML-CSC model assumes that forD1∈RN×Nm1, Γ1 is the corresponding sparse representation and a global signal X can be expressed as X=D1Γ1. This model can be cascaded by imposing a similar assumption Γ1, i.e., Γ1=D2Γ2, for a convolutional dictionary D2∈RNm1×Nm2 and corresponding sparse representations Γ2. The model can be cascaded to J layers and the final global signal X can be expressed as X=D1,JΓJ, where D1,J=D1D2,…,DJ. Applying the slice-based local processing idea to the ML-CSC model, the slice-based ML-CSC model is proposed. The definition of the slice-based ML-CSC model will now be given. For a set of local convolution dictionaries DL,jj=1J of appropriate dimensions and a global signal X∈RN, the slice-based ML-CSC model can be expressed as(20)X=D1Γ1=∑i=1NP1,iTDL,1α1,i,∑i=1Nα1,i0,∞≤λ1,Γ1=D2Γ2=∑i=1NP2,iTDL,2α2,i,∑i=1Nα2,i0,∞≤λ2,⋮ΓJ−1=DJΓJ=∑i=1NPJ,iTDL,JαJ,i,∑i=1NαJ,i0,∞≤λJ,where the l0,∞ norm is defined the maximal number of nonzeros in vector [10], Γj is the sparse representation of the jth layer, Pj,iT is the operator that extracts the ith n-dimensional patch from the jth layer sparse representation Γj, DL,j is jth layer local dictionary, αj,i is αi of the jth layer, and λj is a superparameter. The proposed slice-based multilayer basis pursuit (ML-BP) problem can be expressed as(21)minαj,ii=1Nj=1J12X−∑i=1NPj,iTDL1,Ljαj,i22+∑j=1Jλj∑i=1Nαj,i1.Thejth layer of the BP problem can be expressed as(22)minαj,ii=1Nj=1J12Γj−1−∑i=1NPj,iTDL1,Ljαj,i22+λj∑i=1Nαj,i1.


### 4.2. Slice-Based Multilayer Local Block Coordinate Descent Algorithm

Based on the LoBCoD algorithm, this paper extends the LoBCoD algorithm to a multilayer algorithm to solve the ML-BP problem of equation (21). ML-LoBCoD uses slice-based local processing idea to update the needles. However, rather than optimizing with respect to all needles at the same time, we can treat each needle αj,i as a coordinate block and optimize with respect to each block separately in sequence. Therefore, the jth layer of the BP problem can be expressed as(23)minαj,ij=1J12Γj−1−∑m=1Nm≠iPj,mTDL,jαj,m−Pj,iTDL,iαj,i22+λαj,i1,i=1,…,N.By definingRj,i=Γj−1−∑m=1m≠iNPj,mTDL,jαj,m as the residual image of the jth layer without the contribution of the needles αj,i, the jth layer of the ML-BP problem of equation (23) can be rewritten as(24)minαj,ij=1J12Rj,i−Pj,iTDL,jαj,i22+λjαj,i1,i=1,…,N.Thejth layer of the ML-BP problem of equation (24) becomes equivalent to solving the following minimization problem:(25)minαj,ij=1J12Pj,iRj,i−DL,jαj,i22+λjαj,i1,i=1,…,N.We definefα=1/2Pj,iRj,i−DL,jαj,i22, which is a convex function. The gradient of fα is ∇fαj,i=−DL,jTPj,iRj,i−DL,jαj,i. The ML-LoBCoD algorithm can also be considered to be a generalized gradient algorithm that applies an update of the form αj,ik+1←αj,ik−∇fαj,ik. The update rule of each needle αj,i can be expressed as(26)αj,ik+1=Sλαj,ik+DL,jTPj,iRj,i−DL,jαj,ik.The process of the ML-LoBCoD algorithm is shown as Algorithm1. The input is the global signal X, the convolution dictionary DL,jj=1J, and the initial needles αj,i0i=1N. The initial parameter values are Γ0=X and R0=Γ0. The outputs are the needles αj,iki=1Nj=1J. For the iterative process, we take the jth layer as an example, and select a direction needle αj,i. The steps of ML-LoBCoD algorithm are as follows. (1) The residuals and needles of the previous iteration are used to calculate the residual Rj,i. (2) The needles αj,i are updated. (3) The other needles are fixed to update αj,i+1. All needles of the jth layer are updated. (4) The convolutional sparse code Γj=αj,ii=1N of the jth layer is obtained by accumulating each of the updated needles in turn. (5) All needles of all layers are updated and the layer residual Rjk is updated. (6) This process is repeated k times until convergence occurs.Algorithm 1: Multilayer LoBCoD.
Input: signal X, dictionary DL,jj=1J, initial needles αj,i0i=1Nj=1JOutput: needles αj,iki=1Nj=1JInitialization: Γ0=X,R0=Γ0,X^=0,k=0while not converged dok = k + 1forj=1:Jdofori=1:NdoCompute the local residual:Rj,ik=Rjk−1+Pj,iTDL,jαj,ik−1Find the local sparse code:αj,ik+1=Sλαj,ik+DL,jTPj,iRj,i−DL,jαj,ikUpdate the convolutional sparse code:Γj=Γj−1+∑i=LjPj,iTDL,jαj,ik−αj,ik−1Update the layer residual:Rjk=Γj−1k−ΓjendendendThe natural question that arises is whether the slice-based ML-LoBCoD algorithm is guaranteed to converge to the global minimum of the ML-BP problem, and the answer is positive as will be discussed in Section5.


## 4.1. Slice-Based Multilayer Convolutional Sparse Coding

The ML-CSC model is a deep extension of the CSC model, since the ML-CSC model assumes that the signal can be represented by a sparse representation of the nested convolution filter on different layers. The ML-CSC model assumes that forD1∈RN×Nm1, Γ1 is the corresponding sparse representation and a global signal X can be expressed as X=D1Γ1. This model can be cascaded by imposing a similar assumption Γ1, i.e., Γ1=D2Γ2, for a convolutional dictionary D2∈RNm1×Nm2 and corresponding sparse representations Γ2. The model can be cascaded to J layers and the final global signal X can be expressed as X=D1,JΓJ, where D1,J=D1D2,…,DJ. Applying the slice-based local processing idea to the ML-CSC model, the slice-based ML-CSC model is proposed. The definition of the slice-based ML-CSC model will now be given. For a set of local convolution dictionaries DL,jj=1J of appropriate dimensions and a global signal X∈RN, the slice-based ML-CSC model can be expressed as(20)X=D1Γ1=∑i=1NP1,iTDL,1α1,i,∑i=1Nα1,i0,∞≤λ1,Γ1=D2Γ2=∑i=1NP2,iTDL,2α2,i,∑i=1Nα2,i0,∞≤λ2,⋮ΓJ−1=DJΓJ=∑i=1NPJ,iTDL,JαJ,i,∑i=1NαJ,i0,∞≤λJ,where the l0,∞ norm is defined the maximal number of nonzeros in vector [10], Γj is the sparse representation of the jth layer, Pj,iT is the operator that extracts the ith n-dimensional patch from the jth layer sparse representation Γj, DL,j is jth layer local dictionary, αj,i is αi of the jth layer, and λj is a superparameter. The proposed slice-based multilayer basis pursuit (ML-BP) problem can be expressed as(21)minαj,ii=1Nj=1J12X−∑i=1NPj,iTDL1,Ljαj,i22+∑j=1Jλj∑i=1Nαj,i1.Thejth layer of the BP problem can be expressed as(22)minαj,ii=1Nj=1J12Γj−1−∑i=1NPj,iTDL1,Ljαj,i22+λj∑i=1Nαj,i1.


## 4.2. Slice-Based Multilayer Local Block Coordinate Descent Algorithm

Based on the LoBCoD algorithm, this paper extends the LoBCoD algorithm to a multilayer algorithm to solve the ML-BP problem of equation (21). ML-LoBCoD uses slice-based local processing idea to update the needles. However, rather than optimizing with respect to all needles at the same time, we can treat each needle αj,i as a coordinate block and optimize with respect to each block separately in sequence. Therefore, the jth layer of the BP problem can be expressed as(23)minαj,ij=1J12Γj−1−∑m=1Nm≠iPj,mTDL,jαj,m−Pj,iTDL,iαj,i22+λαj,i1,i=1,…,N.By definingRj,i=Γj−1−∑m=1m≠iNPj,mTDL,jαj,m as the residual image of the jth layer without the contribution of the needles αj,i, the jth layer of the ML-BP problem of equation (23) can be rewritten as(24)minαj,ij=1J12Rj,i−Pj,iTDL,jαj,i22+λjαj,i1,i=1,…,N.Thejth layer of the ML-BP problem of equation (24) becomes equivalent to solving the following minimization problem:(25)minαj,ij=1J12Pj,iRj,i−DL,jαj,i22+λjαj,i1,i=1,…,N.We definefα=1/2Pj,iRj,i−DL,jαj,i22, which is a convex function. The gradient of fα is ∇fαj,i=−DL,jTPj,iRj,i−DL,jαj,i. The ML-LoBCoD algorithm can also be considered to be a generalized gradient algorithm that applies an update of the form αj,ik+1←αj,ik−∇fαj,ik. The update rule of each needle αj,i can be expressed as(26)αj,ik+1=Sλαj,ik+DL,jTPj,iRj,i−DL,jαj,ik.The process of the ML-LoBCoD algorithm is shown as Algorithm1. The input is the global signal X, the convolution dictionary DL,jj=1J, and the initial needles αj,i0i=1N. The initial parameter values are Γ0=X and R0=Γ0. The outputs are the needles αj,iki=1Nj=1J. For the iterative process, we take the jth layer as an example, and select a direction needle αj,i. The steps of ML-LoBCoD algorithm are as follows. (1) The residuals and needles of the previous iteration are used to calculate the residual Rj,i. (2) The needles αj,i are updated. (3) The other needles are fixed to update αj,i+1. All needles of the jth layer are updated. (4) The convolutional sparse code Γj=αj,ii=1N of the jth layer is obtained by accumulating each of the updated needles in turn. (5) All needles of all layers are updated and the layer residual Rjk is updated. (6) This process is repeated k times until convergence occurs.Algorithm 1: Multilayer LoBCoD.
Input: signal X, dictionary DL,jj=1J, initial needles αj,i0i=1Nj=1JOutput: needles αj,iki=1Nj=1JInitialization: Γ0=X,R0=Γ0,X^=0,k=0while not converged dok = k + 1forj=1:Jdofori=1:NdoCompute the local residual:Rj,ik=Rjk−1+Pj,iTDL,jαj,ik−1Find the local sparse code:αj,ik+1=Sλαj,ik+DL,jTPj,iRj,i−DL,jαj,ikUpdate the convolutional sparse code:Γj=Γj−1+∑i=LjPj,iTDL,jαj,ik−αj,ik−1Update the layer residual:Rjk=Γj−1k−ΓjendendendThe natural question that arises is whether the slice-based ML-LoBCoD algorithm is guaranteed to converge to the global minimum of the ML-BP problem, and the answer is positive as will be discussed in Section5.


## 5. Convergence of Slice-Based ML-LoBCoD

In this section, we will propose the convergence theorem and provide proof of convergence of the slice-based ML-LoBCoD algorithm.Theorem 2.
(convergence of ML-LoBCoD).
Given signalX and local dictionary DL,jj=1J, the slice-based ML-LoBCoD algorithm will converge with convergence rate O1/k.Proof.
The definition of nonexpansive operators [15] is employed, which are guaranteed to converge to their fixed point. Firstly, the definition of internal operators and external operators is given as follows:(27)Tinαj,i=proxμgjαj,i−μDL,jTDL,jαj,i−Pj,iRj,i,Toutαj+1,i=proxtgj+1αj+1,i−tμDL,j+1TDL,j+1αj+1,i−TinDL,j+1αj+1,i.
An operatorT is nonexpansive if it is Lipschitz continuous with constant 1, i.e., if Tα−Tβ2≤α−β. In addition, if an operator is firmly nonexpansive, then it must be nonexpansive. A firmly nonexpansion operator needs to satisfy the following conditions:(28)Tα−Tβ22≤Tα−TβTα−β.
The proximal operator is firmly nonexpansive. The internal operator will now be analyzed as follows:(29)Tinαj,i−Tinβj,i22≤Tinαj,i−Tinβj,iTαj,i−μDL,jTDL,jαj,i−Pj,iRj,i−βj,i−μDL,jTDL,jβj,i−Pj,iRj,i=Tinαj,i−Tinβj,iTI−μDL,jTDL,jαj,i−βj,i≤Tinαj,i−Tinβj,iTαj,i−βj,i,where s is chosen such that s<λmaxD1TD1. Thus, Tin is firmly nonexpansive.
Similarly, it can be proved thatTout is also a nonexpansive operator. Let t/μ be a positive constant and satisfies t/μ<λmaxD2TD2. We obtain(30)Toutαj+1,i−Toutβj+1,i22≤Toutαj+1,i−Toutβj+1,iTαj+1,i−tμDL,j+1TDL,j+1αj+1,i−TinDL,j+1αj+1,i−βj+1,i−tμDL,j+1TDL,j+1βj+1,i−TinDL,j+1βj+1,i=Toutαj+1,i−Toutβj+1,iTI−tμDL,j+1TI−TinDL,j+1αj+1,i−βj+1,i≤Toutα−ToutβTαj+1,i−βj+1,i.
Therefore, the ML-LoBCoD algorithm is a nonexpansive operator and it converges to a fixed point.
Next, we analyze the fixed point which is defined asαj+1∗=Toutαj+1∗ for ML-LoBCoD algorithm. Using the second proximal theorem [16], we obtain(31)−tμDL,j+1TDL,j+1αj+1,i∗−TinDL,j+1αj+1,i∗∈t∂gj+1αj+1∗.
Assuming that there iswj+1∈∂gαj+1∗, the above expression can be rewritten as(32)−tμDL,j+1TDL,j+1αj+1,i∗−TinDL,j+1αj+1,i∗+wj+1=0.
Using the second proximal theorem, we obtainwj∈∂gjTinDL,j+1αj+1∗ and(33)DL,j+1αj+1∗−μ∇fDL,j+1αj+1∗−TinDL,j+1αj+1∗=μwj.
Combining these equations together, we obtain(34)DL,j+1T1μDL,j+1αj+1∗−DL,j+1αj+1∗−μ∇fDL,j+1αj+1∗+μwj+wj+1=0.
The fixed point satisfies the optimization condition of the convex function, so the algorithm will converge to a fixed point.
Next, the nonexpansive operatorTout is used to analyze the convergence rate of this algorithm:(35)αjk+1−αjk=αjk+1−αj∗−αjk−αj∗22=αjk+1−αj∗22+αjk−αj∗22−2αjk+1−αj∗Tαjk−αj∗=αjk+1−αj∗22+αjk−αj∗22−2Toutαjk−Toutαj∗Tαjk−αj∗≤αjk−αj∗22−αjk+1−αj∗22.
Summing all the inequalities above fromi=1,…,k−1, we can obtain(36)∑i=0k−1αji+1−αji22≤∑i=0k−1αji−αj∗22−αji+1−αj∗22=αj0−αj∗22−αjk−αj∗22.
Therefore, we obtain(37)kαjk−αj∗22≤∑i=0k−1αji+1−αji22≤αj0−αj∗22−αjk−αj∗22.
Finally, the results are obtained:(38)αjk−αj∗22≤1k+1αj0−αj∗22.
Thejth needles αj is convergent, i.e., Γj converges. Since the convolution sparse code Γ is an interleaved cascade of all Γj, thus Γ will also converge, and the convergence rate is constant with αi. Thus, ML-LoBCoD algorithm converges to the global optimum solution at a rate O1/k.


## 6. Experiment and Discussion

### 6.1. Methods

In this section, the LoBCoD algorithm and ML-LoBCoD algorithm for image reconstruction are described. They are inspired by the ML-ISTA [11, 17]. We constructed a one-layer CSC model. The LoBCoD algorithm is iterative unfolded into a layer of convolutional recurrent neural networks. We constructed a three-layer CSC model. The ML-LoBCoD algorithm is iterative unfolded into a multilayer convolutional recurrent neural network. ML-LoBCoD-NET iterates 3 times to form a convolutional recurrent structure because the algorithm requires multiple iterations to obtain the optimal performance. The forward process of ML-LoBCoD is that the images are inputted to the ML-LoBCoD network to obtain the coding, then which is classified by the classification layer. The backward process of ML-LoBCoD is minimizing the total loss of function to update the convolutional dictionary by the backpropagation algorithm. The loss function is the negative log likelihood function that represents the loss of a classification error between the ground truth labels and the predicted labels by the network.


### 6.2. Experimental Results

In this section, we perform experiments on the MINIST dataset using both the LoBCoD and ML-LoBCoD model for image reconstruction. We constructed a one-layer CSC model and a three-layer CSC model. The one-layer CSC model contains 64 local filters of size 6 × 6. In the three-layer CSC model, the first convolutional layer includes 64 local filters of size 6 × 6, the second convolutional layer contains 128 filters of size 6 × 6, and the third convolutional layer contains 512 filters of size 4 × 4. Its parameters are the same as a traditional CNN, and thus the network parameters remain unchanged.The cause of selecting the MNIST datasets that this dataset is the most popular and the most frequently used image datasets and are also the entry-level benchmark datasets in deep learning community.Experiments on MNIST using the proposed networks are run on Pytorch platform and Linux system using a single computer with a Nvidia Geforce 1080Ti GPU. The code used to support the findings of this paper inspired by the ML-ISTA [11] in GitHub website and are available from the corresponding author upon request.The loss function values of LoBCoD and ML-LoBCoD with the number of iterations in the MNIST dataset are shown in Figure1. It is obvious that the loss function values of the ML-LoBCoD are lower than that of the LoBCoD.Figure 1
Loss function of LoBCoD and ML-LoBCoD with the number of iterations.The results of the original test image and the reconstructed image using the LoBCoD method and the ML-LoBCoD method after 100 iterations are shown in Figures2 and 3, respectively. It can be clearly seen that the reconstruction quality of the ML-LoBCoD is better than that of LoBCoD.Figure 2
The test image and the reconstructed image of the LoBCoD after 100 iterations.Figure 3
The test image and the reconstructed image of the ML-LoBCoD after 100 iterations.The loss function value, the training time, and the peak signal-to-noise ratio (PSNR) value of the two networks after 100 iterations are shown in Table1. It can be observed that the loss function and PSNR values of the ML-LoBCoD network is smaller than the LoBCoD network. The PSNR value of the LoBCoD network is lower than that of the ML-LoBCoD network. The loss function value of the ML-LoBCoD network is 3.03 × 10−6. The PSNR value of the ML-LoBCoD network is 20.15 dB. However, the ML-LoBCoD network has longer training time than LoBCoD network.Table 1
Loss function value, training time, and PSNR of both networks after 100 iterations.
LoBCoDML-LoBCoDLoss function3.64 × 10−53.03 ×  10−6Training1 h 08 m1 h 47 mPSNR17.51 dB20.15 dBThe ML-LoBCoD network has more model parameters than the LoBCoD network. The model parameters of the two networks are shown in Table2. The model parameters and of the ML-ISTA and corresponding CNN are given in [11]. It can be observed that the ML-ISTA, ML-LoBCoD, and corresponding CNN have the similar parameters, more than the LoBCoD network.Table 2
Model parameters of ML-LoBCoD and LoBCoD networks.
LoBCoDML-LoBCoD1st layer6 × 6 × 1 × 64 + 646 × 6 × 1 × 64 + 642st layer06 × 6 × 64 × 128 + 1283st layer04 × 4 × 128 × 512 + 512Classifiction layer64 × 10 + 10512×10+10Total30181753818The classification accuracy results of the four model are shown in Table3. It can be observed that ML-LoBCoD has the highest accuracy rate, far superior to the LoBCoD. These experimental results demonstrate the superiority of our proposed method.Table 3
Average Classification results for MNIST of Four networks.
Feedforward (%)ML-ISTA (%)LoBCoD (%)ML-LoBCoD(%)98.6499.2495.3799.28


## 6.1. Methods

In this section, the LoBCoD algorithm and ML-LoBCoD algorithm for image reconstruction are described. They are inspired by the ML-ISTA [11, 17]. We constructed a one-layer CSC model. The LoBCoD algorithm is iterative unfolded into a layer of convolutional recurrent neural networks. We constructed a three-layer CSC model. The ML-LoBCoD algorithm is iterative unfolded into a multilayer convolutional recurrent neural network. ML-LoBCoD-NET iterates 3 times to form a convolutional recurrent structure because the algorithm requires multiple iterations to obtain the optimal performance. The forward process of ML-LoBCoD is that the images are inputted to the ML-LoBCoD network to obtain the coding, then which is classified by the classification layer. The backward process of ML-LoBCoD is minimizing the total loss of function to update the convolutional dictionary by the backpropagation algorithm. The loss function is the negative log likelihood function that represents the loss of a classification error between the ground truth labels and the predicted labels by the network.


## 6.2. Experimental Results

In this section, we perform experiments on the MINIST dataset using both the LoBCoD and ML-LoBCoD model for image reconstruction. We constructed a one-layer CSC model and a three-layer CSC model. The one-layer CSC model contains 64 local filters of size 6 × 6. In the three-layer CSC model, the first convolutional layer includes 64 local filters of size 6 × 6, the second convolutional layer contains 128 filters of size 6 × 6, and the third convolutional layer contains 512 filters of size 4 × 4. Its parameters are the same as a traditional CNN, and thus the network parameters remain unchanged.The cause of selecting the MNIST datasets that this dataset is the most popular and the most frequently used image datasets and are also the entry-level benchmark datasets in deep learning community.Experiments on MNIST using the proposed networks are run on Pytorch platform and Linux system using a single computer with a Nvidia Geforce 1080Ti GPU. The code used to support the findings of this paper inspired by the ML-ISTA [11] in GitHub website and are available from the corresponding author upon request.The loss function values of LoBCoD and ML-LoBCoD with the number of iterations in the MNIST dataset are shown in Figure1. It is obvious that the loss function values of the ML-LoBCoD are lower than that of the LoBCoD.Figure 1
Loss function of LoBCoD and ML-LoBCoD with the number of iterations.The results of the original test image and the reconstructed image using the LoBCoD method and the ML-LoBCoD method after 100 iterations are shown in Figures2 and 3, respectively. It can be clearly seen that the reconstruction quality of the ML-LoBCoD is better than that of LoBCoD.Figure 2
The test image and the reconstructed image of the LoBCoD after 100 iterations.Figure 3
The test image and the reconstructed image of the ML-LoBCoD after 100 iterations.The loss function value, the training time, and the peak signal-to-noise ratio (PSNR) value of the two networks after 100 iterations are shown in Table1. It can be observed that the loss function and PSNR values of the ML-LoBCoD network is smaller than the LoBCoD network. The PSNR value of the LoBCoD network is lower than that of the ML-LoBCoD network. The loss function value of the ML-LoBCoD network is 3.03 × 10−6. The PSNR value of the ML-LoBCoD network is 20.15 dB. However, the ML-LoBCoD network has longer training time than LoBCoD network.Table 1
Loss function value, training time, and PSNR of both networks after 100 iterations.
LoBCoDML-LoBCoDLoss function3.64 × 10−53.03 ×  10−6Training1 h 08 m1 h 47 mPSNR17.51 dB20.15 dBThe ML-LoBCoD network has more model parameters than the LoBCoD network. The model parameters of the two networks are shown in Table2. The model parameters and of the ML-ISTA and corresponding CNN are given in [11]. It can be observed that the ML-ISTA, ML-LoBCoD, and corresponding CNN have the similar parameters, more than the LoBCoD network.Table 2
Model parameters of ML-LoBCoD and LoBCoD networks.
LoBCoDML-LoBCoD1st layer6 × 6 × 1 × 64 + 646 × 6 × 1 × 64 + 642st layer06 × 6 × 64 × 128 + 1283st layer04 × 4 × 128 × 512 + 512Classifiction layer64 × 10 + 10512×10+10Total30181753818The classification accuracy results of the four model are shown in Table3. It can be observed that ML-LoBCoD has the highest accuracy rate, far superior to the LoBCoD. These experimental results demonstrate the superiority of our proposed method.Table 3
Average Classification results for MNIST of Four networks.
Feedforward (%)ML-ISTA (%)LoBCoD (%)ML-LoBCoD(%)98.6499.2495.3799.28


## 7. Conclusion

In this paper, the convergence theorem of LoBCoD algorithm was proposed and it was proved that this method converges to the global optimum at a rateO1/k. Inspired by ML-CSC and slice-based local processing idea, a slice-based ML-CSC model was proposed. Motivated by ML-ISTA and the LoBCoD algorithm, an ML-LoBCoD algorithm was proposed and it was established that this method is guaranteed to converge to the global optimum of ML-BP at a rate of O1/k. The experiment compares the loss function value, training time, and PSNR of the two networks. The experiment shows that the reconstruction quality of the ML-LoBCoD network is better than that of LoBCoD network. However, this paper only studies the pursuit problem of ML-CSC. The dictionary learning problem of CSC needs further study. This paper is a preliminary study of ML-LoBCoD network, and further study is needed to obtain a more complete analysis, which will likely contribute to the further understanding of deep learning based on driven optimization algorithms.



---

*Source: 4367515-2020-07-30.xml*