With the development of technology, data collection and processing have become easier, and many areas involve high-dimensional data issues, such as information technology, economic finance, and data modeling. Faced with such huge data, many researchers have proposed different solutions, and compressed sensing and sparsity has become an effective algorithm, because sparsity reduces the dimensionality of data in a certain sense and alternates direction multiplier method (ADMM)  . It is a typical idea of using divide-and-conquer, which is to transform the original high-dimensional problem into two or more low-dimensional problem-solving algorithms, which is in line with the processing requirements of big data. However, the traditional ADMM is prone to the local best of the problem. The linear model has a simple structure, which is relatively basic, easy to handle, and widely used. There are many phenomena in real life that can be approximated by a linear model, for example, the relationship between per capita disposable income and consumer spending. Generally speaking, the higher the per capita disposable income X is, the higher the corresponding consumption expenditure Y is. The main advantage of the new algorithm is that it can make the sub-problem have a display solution and be easier to solve, which is of great significance in the application of many problems.
2. Introduction to the Method
The ADMM algorithm was first proposed by Gabay, Meicher and Glowinski in the mid-1970    . A similar idea originated in the mid-1950s. A large number of articles analyzed the nature of this method, but ADMM was used to solve the problem of partial differential equations. Now ADMM is mainly used to solve the optimization problem with separable variables, which solves the problem that the augmented Lagrangian algorithm with good properties can’t solve. It can be parallelized, which speeds up the solution. The convergence and convergence rate of ADMM for convex optimization problems with two separable variables. Although there is a mature theoretical analysis, the convergence problem of convex optimization problems extended to more than three separable variables has not been improved in a good solution. Then ADMM is also a public problem for non-convex optimization problems. There have been many applications showing the effectiveness of ADMM for non-convex problems. Can ADMM be applied to more optimization problems and more non-convex optimization problems? What is the effect? This article will introduce the application of ADMM in non-convex optimization problems.
First consider the convex optimization problem with equality constraints
where is a convex function.
Firstly, an optimization algorithm with good properties is introduced, which augments the Lagrangian multiplier method. The augmented Lagrangian function is defined as:
where is called the penalty parameter. when , is the Lagrangian function. The iterative steps of the augmented Lagrangian multiplier method are:
where is the Lagrangian multiplier, i.e. the dual variable.
The advantage of this algorithm is that the convergence of the iterative sequence can be guaranteed without too strong conditions. For example, for the penalty parameter, it is not required to increase to infinity in the iterative process, and a fixed value can be taken. But the disadvantage of this algorithm is that when the objective function is separable, the model becomes:
where g is also a convex function. In the x iteration step, the augmented Lagrangian function is inseparable, and the discrete variables cannot be solved in parallel for the x subproblem. This leads to the ADMM algorithm we will discuss in the next section. The Alternating Direction Method (ADMM) is mainly used to solve the optimization problem with separable variables like (4), where . Let’s assume that both f and g are convex functions, and then make other assumptions. Similar to the definition in the previous section, the augmented Lagrangian penalty function of (4) is:
The steps of the ADMM algorithm iteration are as follows:
where . The similarity between the algorithm and the augmented Lagrangian multiplier method is to iteratively solve the variables x and y and then iteratively solve the dual variables.
If the augmented Lagrangian multiplier method is used for iterative solution:
As mentioned in the previous section, you can see that the augmented Lagrangian multiplier method deals with two separate variables at the same time, and ADMM alternates the variables, which is the origin of the algorithm name. It can be considered that this is the use of Gauss-Seidel iterations on two variables. For details, please refer to. It is obvious from the algorithm framework that the ADMM algorithm is more suitable for solving the problem of having separate variables because the objective functions f and g are also separated.
To get a simpler form of ADMM, normalize the dual variable so that . Then the ADMM iteration becomes:
ADMM convergence: Regarding the convergence of ADMM, please refer to the literature.
3. Application of ADMM in Dictionary Learning
As we all know, the alternating direction method (ADMM) is one of the effective algorithms for solving large-scale sparse optimization problems. It is solved by splitting the problem into a number of low-dimensional sub-problems by augmented Lagrangian function construction. In recent years, a large number of working signals have pointed to the sparse expression of signals. Sparse expression refers to the use of a dictionary, the dictionary contains nSignal atoms . A signal can be expressed as a sparse linear representation of these signal atoms. In fact, the so-called sparse means that the number of non-zero coefficients is much smaller than that of n. Such a sparse representation may be a determined or an approximate representation with an error term . The vector is the signal y sparse expression coefficient. In practice, p often takes a value of 1, 2, or ∞.
If and the dictionary D is full rank, then the underdetermined system of the problem has an infinite number of solutions, and the solution using the least non-zero coefficient is one of them, and is the solution we hope to find. Sparse expression is expressed as a mathematical expression
where is ―module, which means that the corresponding vector takes a non-zero quantity.
Learn the dictionary based on the signal set. First given a data set , assuming that there is a dictionary D so that for a given signal can be represented as a sparse representation of the dictionary, i.e. for a given signal , the model Or can find the sparse coefficient . The question then is how to find such a dictionary D. Detailed reference can be found in the literature  .
The model of the problem can be written as:
where is the upper bound of the coefficient sparsity, is the ith column of the coefficient matrix X, and is the Frobenius norm of the matrix, i.e. the sum of the squares of the elements of the matrix.
Another model for dictionary learning is corresponding to the above model.
is a fixed error value.
Before applying ADMM, first make some transformations to the model, let , then the model becomes:
Then the augmented Lagrangian function of the problem is:
where is the Lagrange multiplier matrix and is the ith column of .
Using the ADMM algorithm in the above model, there is a X subproblem
The Z subproblem is
This sub-question has a solution.
D sub-problem is
But ADL (ADMM for Dictionary Learning) is prone to the local best of the problem. Using linearization techniques, we extended LADMM to solve the problem of ADL local straits and proved the convergence of the algorithm. Numerical experiments are used to illustrate the effectiveness of the proposed algorithm.
4. Application of Linearized ADMM in Dictionary Learning
In order to apply ADMM, we can rewrite (11) into the following form
Then the augmented Lagrangian function of the model (20) is
The iterative method of ADMM is:
Now, we solve the subproblem in (22). First we solve the X-sub problem.
Because of the non-identity of matrix D, this subproblem does not show a solution. Inspired by  , we linearize this quadratic term as
The parameter controls the degree of approximation of X and , then we solve the following problem and use the solution of this problem to approximate the solution of the subproblem generated by ADMM.
For the above problem, it is known from  medium (11)
Furthermore, for the Y subproblem, the Equation (10) in  shows that the display solution is
As can be seen from the above discussion, the LADMM iterative algorithm can be described by the following table.
In this section, we will demonstrate that the LADMM algorithm is convergent. is the unit matrix of . Let and , , . Solving the model is equivalent to finding that satisfies the KKT condition of the model, i.e.
Let us remember that the set of elements that satisfy the above formula in S is . The KKT condition of the above formula can be written as the form of variational inequality (VI) as:
In order to prove these conclusions, as well as the proof of convergence of LADMM, need to introduce some lemma. For details, please refer to the literature  .
5. Numerical Experiments
In this chapter, we will discuss the application of the algorithm in image deblur ring to prove the effectiveness of the algorithm. All experiments were carried out on a four-core notebook computer with Intel Intel(R) Core(TM) i5-7200UCPU @ 2.50 GHz and 4 GB memory. Procedures for this experiment, pictures are referenced  .
Figure 1 shows the application of ADMM algorithm in image deblurring, which has motion blur and Gaussian blur respectively. (“motion”, 35, 50), (“gaussian”, 20, 20).
The noise levels are delta = 0.256, 0.511 respectively. For comparison, we also include the results of FTVd v4.1 in  , which is the most advanced image deblurring algorithm. It can be seen from the pictures that our proposed algorithm and FTVd algorithm have the same quality as PSNR (Figure 2), and our algorithm does not need regularization operator.
MSE represents the average square error of each pixel.
In this paper, we propose a linearized alternating direction multiplier method
Figure 1. ADMM algorithm for deblurring.
Figure 2. LADMM algorithm for deblurring.
(LADMM) to solve the problem of rapid convergence of the dictionary model that is easy to fall into the local optimal solution. This model combines the advantages of linearization features to make sub-problems easier to solve. When the algorithm is applied to the problem of image reconstruction, we use the quadratic term of the linearized sub-problem to make the sub-problem easier to solve.
Moreover, in the case of similar PSNR, the algorithm does not need regularization operator.
In addition, we analyze the convergence of the LADMM algorithm. Our next step is to generalize the model to more non-convex problems (non-negative matrix factorization problems) and use practical problems.
 Boyd, S., Parikh, N., Chu, E., Peleato, B. and Eckstein, J. (2010) Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers. Foundations and Trends® in Machine Learning, 3, 1-122.
 Fu, X.L., He, B.H., Wang, X.F., et al. (2014) Block-Wise Alternating Direction Method of Multipliers with Gaussian Back Substitution for Multiple-Block Convex Programming. 1-37.
 Haubruge, S., Nguyen, V.H. and Strodiot, J.J. (1998) Convergence Analysis and Applications of the Glowinski—Le Tallec Splitting Method for Finding a Zero of the Sum of Two Maximal Monotone Operators. Journal of Optimization Theory and Applications, 97, 645-673.
 Glowinski, R. and Marroco, A. (1975) Sur l’approximation, par éléments finis d’ordre un, et la résolution, par Pénalisation-Dualité d’une classe de problèmes de Dirichlet non linéaires. Journal of Equine Veterinary Science, 2, 41-76.
 Jiao, Y.L., Jin, Q.N., Lu, X.L., et al. (2016) Alternating Direction Method of Multipliers for Linear Inverse Problems. SIAM Journal on Numerical Analysis, 54, 2114-2137.