Student Member, IEEE Zheng Zhang

Member, IEEE Jian Yang

Fellow, IEEE Xuelong Li

Fellow, IEEE David Zhang

Yong Xu
email: yongxu@ymail.com

A survey of sparse representation: algorithms and applications

Keywords: Sparse representation, compressive sensing, greedy algorithm, constrained optimization, proximal algorithm, homotopy algorithm, dictionary learning

Sparse representation has attracted much attention from researchers in fields of signal processing, image processing, computer vision and pattern recognition. Sparse representation also has a good reputation in both theoretical research and practical applications. Many different algorithms have been proposed for sparse representation. The main purpose of this article is to provide a comprehensive study and an updated review on sparse representation and to supply a guidance for researchers. The taxonomy of sparse representation methods can be studied from various viewpoints. For example, in terms of different norm minimizations used in sparsity constraints, the methods can be roughly categorized into five groups: sparse representation with l0-norm minimization, sparse representation with lp-norm (0<p<1) minimization, sparse representation with l1-norm minimization and sparse representation with l2,1-norm minimization. In this paper, a comprehensive overview of sparse representation is provided. The available sparse representation algorithms can also be empirically categorized into four groups: greedy strategy approximation, constrained optimization, proximity algorithmbased optimization, and homotopy algorithm-based sparse representation. The rationales of different algorithms in each category are analyzed and a wide range of sparse representation applications are summarized, which could sufficiently reveal the potential nature of the sparse representation theory. Specifically, an experimentally comparative study of these sparse representation algorithms was presented.

I. INTRODUCTION

W ITH advancements in mathematics, linear represen- tation methods (LRBM) have been well studied and have recently received considerable attention [START_REF] Natarajan | Sparse approximate solutions to linear systems[END_REF][START_REF] Huang | Brain extraction based on locally linear representation-based classification[END_REF]. The sparse representation method is the most representative methodology of the LRBM and has also been proven to be an extraordinary powerful solution to a wide range of application fields, especially in signal processing, image processing, machine learning, and computer vision, such as image denoising, debluring, inpainting, image restoration, super-resolution, visual tracking, image classification and image segmentation [START_REF] Lu | Group sparse reconstruction for image segmentation[END_REF][START_REF] Elad | On the role of sparse and redundant representations in image processing[END_REF][START_REF] Mallat | A wavelet tour of signal processing: the sparse way[END_REF][START_REF] Starck | Sparse image and signal processing: wavelets, curvelets, morphological diversity[END_REF][START_REF] Elad | Sparse and redundant representations: from theory to applications in signal and image processing[END_REF][START_REF] Bruckstein | From sparse solutions of systems of equations to sparse modeling of signals and images[END_REF][START_REF] Xu | A two-phase test sample sparse representation method for use with face recognition[END_REF][START_REF] Wright | Sparse representation for computer vision and pattern recognition[END_REF].

Sparse representation has shown huge potential capabilities in handling these problems.

Sparse representation, from the viewpoint of its origin, is directly related to compressed sensing (CS) [START_REF] Donoho | Compressed sensing[END_REF][START_REF] Baraniuk | Compressive sensing[END_REF][START_REF] Candès | Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information[END_REF], which is one of the most popular topics in recent years. Donoho [START_REF] Donoho | Compressed sensing[END_REF] first proposed the original concept of compressed sensing. CS theory suggests that if a signal is sparse or compressive, the original signal can be reconstructed by exploiting a few measured values, which are much less than the ones suggested by previously used theories such as Shannon's sampling theorem (SST). Candes et al. [START_REF] Candès | Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information[END_REF], from the mathematical perspective, demonstrated the rationale of CS theory, i.e. the original signal could be precisely reconstructed by utilizing a small portion of Fourier transformation coefficients. Baraniuk [12] provided a concrete analysis of compressed sensing and presented a specific interpretation on some solutions of different signal reconstruction algorithms. All these literature [START_REF] Donoho | Compressed sensing[END_REF][START_REF] Baraniuk | Compressive sensing[END_REF][START_REF] Candès | Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information[END_REF][START_REF] Candes | An introduction to compressive sampling[END_REF][START_REF] Tsaig | Extensions of compressed sensing[END_REF][START_REF] Candes | Compressive sampling[END_REF][START_REF] Candes | Sparsity and incoherence in compressive sampling[END_REF] laid the foundation of CS theory and provided the theoretical basis for future research. Thus, a large number of algorithms based on CS theory have been proposed to address different problems in various fields. Moreover, CS theory always includes the three basic components: sparse representation, encoding measuring, and reconstructing algorithm. As an indispensable prerequisite of CS theory, the sparse representation theory [START_REF] Elad | On the role of sparse and redundant representations in image processing[END_REF][START_REF] Elad | Sparse and redundant representations: from theory to applications in signal and image processing[END_REF][START_REF] Bruckstein | From sparse solutions of systems of equations to sparse modeling of signals and images[END_REF][START_REF] Xu | A two-phase test sample sparse representation method for use with face recognition[END_REF][START_REF] Wright | Sparse representation for computer vision and pattern recognition[END_REF][START_REF] Candes | Sparsity and incoherence in compressive sampling[END_REF] is the most outstanding technique used to conquer difficulties that appear in many fields. For example, the methodology of sparse representation is a novel signal sampling method for the sparse or compressible signal and has been successfully applied to signal processing [START_REF] Elad | On the role of sparse and redundant representations in image processing[END_REF][START_REF] Mallat | A wavelet tour of signal processing: the sparse way[END_REF][START_REF] Starck | Sparse image and signal processing: wavelets, curvelets, morphological diversity[END_REF].

Sparse representation has attracted much attention in recent years and many examples in different fields can be found where sparse representation is definitely beneficial and favorable [START_REF] Lu | Manifold regularized sparse nmf for hyperspectral unmixing[END_REF][START_REF] Yuan | Binary sparse nonnegative matrix factorization[END_REF]. One example is image classification, where the basic goal is to classify the given test image into several predefined categories. It has been demonstrated that natural images can be sparsely represented from the perspective of the properties of visual neurons. The sparse representation based classification (SRC) method [START_REF] Wright | Robust face recognition via sparse representation[END_REF] first assumes that the test sample can be sufficiently represented by samples from the same subject. Specifically, SRC exploits the linear combination of training samples to represent the test sample and computes sparse representation coefficients of the linear representation system, and then calculates the reconstruction residuals of each class employing the sparse representation coefficients and training samples. The test sample will be classified as a member of the class, which leads to the minimum reconstruction residual. The literature [START_REF] Wright | Robust face recognition via sparse representation[END_REF] has also demonstrated that the SRC method has great superiorities when addressing the image classification issue on corrupted or disguised images. In such cases, each natural image can be sparsely represented and the sparse representation theory can be utilized to fulfill the image classification task.

For signal processing, one important task is to extract key components from a large number of clutter signals or groups of complex signals in coordination with different requirements. Before the appearance of sparse representation, SST and Nyquist sampling law (NSL) were the traditional methods for signal acquisition and the general procedures included sampling, coding compression, transmission, and decoding. Under the frameworks of SST and NSL, the greatest difficulty of signal processing lies in efficient sampling from mass data with sufficient memory-saving. In such a case, sparse representation theory can simultaneously break the bottleneck of conventional sampling rules, i.e. SST and NSL, so that it has a very wide application prospect. Sparse representation theory proposes to integrate the processes of signal sampling and coding compression. Especially, sparse representation theory employs a more efficient sampling rate to measure the original sample by abandoning the pristine measurements of SST and NSL, and then adopts an optimal reconstruction algorithm to reconstruct samples. In the context of compressed sensing, it is first assumed that all the signals are sparse or approximately sparse enough [START_REF] Elad | On the role of sparse and redundant representations in image processing[END_REF][START_REF] Starck | Sparse image and signal processing: wavelets, curvelets, morphological diversity[END_REF][START_REF] Elad | Sparse and redundant representations: from theory to applications in signal and image processing[END_REF]. Compared to the primary signal space, the size of the set of possible signals can be largely decreased under the constraint of sparsity. Thus, massive algorithms based on the sparse representation theory have been proposed to effectively tackle signal processing issues such as signal reconstruction and recovery. To this end, the sparse representation technique can save a significant amount of sampling time and sample storage space and it is favorable and advantageous.

A. Categorization of sparse representation techniques

Sparse representation theory can be categorized from different viewpoints. Because different methods have their individual motivations, ideas, and concerns, there are varieties of strategies to separate the existing sparse representation methods into different categories from the perspective of taxonomy. For example, from the viewpoint of "atoms", available sparse representation methods can be categorized into two general groups: naive sample based sparse representation and dictionary learning based sparse representation. However, on the basis of the availability of labels of "atoms", sparse representation and learning methods can be coarsely divided into three groups: supervised learning, semi-supervised learning, and unsupervised learning methods. Because of the sparse constraint, sparse representation methods can be divided into two communities: structure constraint based sparse representation and sparse constraint based sparse representation. Moreover, in the field of image classification, the representation based classification methods consist of two main categories in terms of the way of exploiting the "atoms": the holistic representation based method and local representation based method [START_REF] Zhang | Integrating globality and locality for robust representation based classification[END_REF]. More specifically, holistic representation based methods exploit training samples of all classes to represent the test sample, whereas local representation based methods only employ training samples (or atoms) of each class or several classes to represent the test sample. Most of the sparse representation methods are holistic representation based methods. A typical and representative local sparse representation methods is the two-phase test sample sparse representation (TPTSR) method [START_REF] Xu | A two-phase test sample sparse representation method for use with face recognition[END_REF]. In consideration of different methodologies, the sparse representation method can be grouped into two aspects: pure sparse representation and hybrid sparse representation, which improves the pre-existing sparse representation methods with the aid of other methods. The literature [START_REF] Cheng | Sparse representation and learning in visual recognition: Theory and applications[END_REF] suggests that sparse representation algorithms roughly fall into three classes: convex relaxation, greedy algorithms, and combinational methods. In the literature [START_REF] Tropp | Algorithms for simultaneous sparse approximation. part i: Greedy pursuit[END_REF][START_REF] Tropp | Algorithms for simultaneous sparse approximation. part ii: Convex relaxation[END_REF], from the perspective of sparse problem modeling and problem solving, sparse decomposition algorithms are generally divided into two sections: greedy algorithms and convex relaxation algorithms. On the other hand, if the viewpoint of optimization is taken into consideration, the problems of sparse representation can be divided into four optimization problems: the smooth convex problem, nonsmooth nonconvex problem, smooth nonconvex problem, and nonsmooth convex problem. Furthermore, Schmidt et al. [START_REF] Schmidt | Optimization methods for l 1 -regularization[END_REF] reviewed some optimization techniques for solving l 1norm regularization problems and roughly divided these approaches into three optimization strategies: sub-gradient methods, unconstrained approximation methods, and constrained optimization methods. The supplementary file attached with the paper also offers more useful information to make fully understandings of the 'taxonomy' of current sparse representation techniques in this paper.

In this paper, the available sparse representation methods are categorized into four groups, i.e. the greedy strategy approximation, constrained optimization strategy, proximity algorithm based optimization strategy, and homotopy algorithm based sparse representation, with respect to the analytical solution and optimization viewpoints.

(1) In the greedy strategy approximation for solving sparse representation problem, the target task is mainly to solve the sparse representation method with l 0 -norm minimization. Because of the fact that this problem is an NP-hard problem [START_REF] Amaldi | On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems[END_REF], the greedy strategy provides an approximate solution to alleviate this difficulty. The greedy strategy searches for the best local optimal solution in each iteration with the goal of achieving the optimal holistic solution [START_REF] Tropp | Greed is good: Algorithmic results for sparse approximation[END_REF]. For the sparse representation method, the greedy strategy approximation only chooses the most k appropriate samples, which are called ksparsity, to approximate the measurement vector.

(2) In the constrained optimization strategy, the core idea is to explore a suitable way to transform a non-differentiable optimization problem into a differentiable optimization problem by replacing the l 1 -norm minimization term, which is convex but nonsmooth, with a differentiable optimization term, which is convex and smooth. More specifically, the constrained optimization strategy substitutes the l 1 -norm minimization term Fig. 1: The structure of this paper. The main body of this paper mainly consists of four parts: basic concepts and frameworks in Section II-III, representative algorithms in Section IV-VII and extensive applications in Section VIII, massive experimental evaluations in Section IX. Conclusion is summarized in Section X.

with an equal constraint condition on the original unconstraint problem. If the original unconstraint problem is reformulated into a differentiable problem with constraint conditions, it will become an uncomplicated problem in the consideration of the fact that l 1 -norm minimization is global non-differentiable.

(3) Proximal algorithms can be treated as a powerful tool for solving nonsmooth, constrained, large-scale, or distributed versions of the optimization problem [START_REF] Parikh | Proximal algorithms[END_REF]. In the proximity algorithm based optimization strategy for sparse representation, the main task is to reformulate the original problem into the specific model of the corresponding proximal operator such as the soft thresholding operator, hard thresholding operator, and resolvent operator, and then exploits the proximity algorithms to address the original sparse optimization problem.

(4) The general framework of the homotopy algorithm is to iteratively trace the final desired solution starting from the initial point to the optimal point by successively adjusting the homotopy parameter [START_REF] Donoho | Fast solution of l 1 -norm minimization problems when the solution may be sparse[END_REF]. In homotopy algorithm based sparse representation, the homotopy algorithm is used to solve the l 1norm minimization problem with k-sparse property.

B. Motivation and objectives

In this paper, a survey on sparse representation and overview available sparse representation algorithms from viewpoints of the mathematical and theoretical optimization is provided. This paper is designed to provide foundations of the study on sparse representation and aims to give a good start to newcomers in computer vision and pattern recognition communities, who are interested in sparse representation methodology and its related fields. Extensive state-of-art sparse representation methods are summarized and the ideas, algorithms, and wide applications of sparse representation are comprehensively presented. Specifically, there is concentration on introducing an up-todate review of the existing literature and presenting some insights into the studies of the latest sparse representation methods. Moreover, the existing sparse representation methods are divided into different categories. Subsequently, corresponding typical algorithms in different categories are presented and their distinctness is explicitly shown. Finally, the wide applications of these sparse representation methods in different fields are introduced.

The remainder of this paper is mainly composed of four parts: basic concepts and frameworks are shown in Section II and Section III, representative algorithms are presented in Section IV-VII and extensive applications are illustrated in Section VIII, massive experimental evaluations are summarized in Section IX. More specifically, the fundamentals and preliminary mathematic concepts are presented in Section II, and then the general frameworks of the existing sparse representation with different norm regularizations are summarized in Section III. In Section IV, the greedy strategy approximation method is presented for obtaining a sparse representation solution, and in Section V, the constrained optimization strategy is introduced for solving the sparse representation issue. Furthermore, the proximity algorithm based optimization strategy and Homotopy strategy for addressing the sparse representation problem are outlined in Section VI and Section VII, respectively. Section VIII presents extensive applications of sparse represen- tation in widespread and prevalent fields including dictionary learning methods and real-world applications. Finally, Section IX offers massive experimental evaluations and conclusions are drawn and summarized in Section X. The structure of the this paper has been summarized in Fig. 1.

II. FUNDAMENTALS AND PRELIMINARY CONCEPTS

A. Notations

In this paper, vectors are denoted by lowercase letters with bold face, e.g. x. Matrices are denoted by uppercase letter, e.g. X and their elements are denoted with indexes such as X i . In this paper, all the data are only real-valued. Suppose that the sample is from space R d and thus all the samples are concatenated to form a matrix, denoted as D ∈ R d×n . If any sample can be approximately represented by a linear combination of dictionary D and the number of the samples is larger than the dimension of samples in D, i.e. n > d, dictionary D is referred to as an over-complete dictionary. A signal is said to be compressible if it is a sparse signal in the original or transformed domain when there is no information or energy loss during the process of transformation.

"sparse" or "sparsity" of a vector means that some elements of the vector are zero. We use a linear combination of a basis matrix A ∈ R N ×N to represent a signal x ∈ R N ×1 , i.e. x = As where s ∈ R N ×1 is the column vector of weighting coefficients. If only k (k ≪ N ) elements of s are nonzero and the rest elements in s are zero, we call the signal x is k-sparse.

B. Basic background

The standard inner product of two vectors, x and y from the set of real n dimensions, is defined as

x, y = x T y = x 1 y 1 + x 2 y 2 + • • • + x n y n (II.1)
The standard inner product of two matrixes, X ∈ R m×n and Y ∈ R m×n from the set of real m × n matrixes, is denoted as the following equation

X, Y = tr(X T Y ) = m i=1 n j=1 X ij Y ij (II.2)
where the operator tr(A) denotes the trace of the matrix A, i.e. the sum of its diagonal entries.

Suppose that v = [v 1 , v 2 , • • • , v n ] is an n dimensional vector in Euclidean space, thus v p = ( n i=1 |v i | p ) 1/p (II.3) is denoted as the p-norm or the l p -norm (1 ≤ p ≤ ∞) of vector v.
When p=1, it is called the l 1 -norm. It means the sum of absolute values of the elements in vector v , and its geometric interpretation is shown in Fig. 2b, which is a square with a forty-five degree rotation.

When p=2, it is called the l 2 -norm or Euclidean norm. It is defined as

v 2 = (v 2 1 + v 2 2 + • • • + v 2 n ) 1/2
, and its geometric interpretation in 2-D space is shown in Fig. 2c which is a circle.

In the literature, the sparsity of a vector v is always related to the so-called l 0 -norm, which means the number of the nonzero elements of vector v. Actually, the l 0 -norm is the limit as p → 0 of the l p -norms [START_REF] Bruckstein | From sparse solutions of systems of equations to sparse modeling of signals and images[END_REF] and the definition of the l 0 -norm is formulated as

v 0 = lim p→0 v p p = lim p→0 n i=1 |v i | p (II.4)
We can see that the notion of the l 0 -norm is very convenient and intuitive for defining the sparse representation problem. The property of the l 0 -norm can also be presented from the perspective of geometric interpretation in 2-D space, which is shown in Fig. 2a, and it is a crisscross. Furthermore, the geometric meaning of the l p -norm (0<p<1) is also presented, which is a form of similar recessed pentacle shown in Fig. 2d.

On the other hand, it is assumed that f (x) is the function of the l p -norm (p>0) on the parameter vector x, and then the following function is obtained:

f (x) = x p p = ( n i=1 |x i | p ) (II.5)
The relationships between different norms are summarized in Fig. 3. From the illustration in Fig. 3, the conclusions are as follows.

L 0 norm L 1/10 norm L 1/3 norm L 1/2 norm L 2/3 norm L 1 norm L 2 norm ( ) | | p i i f x x = i x
Fig. 3: Geometric interpretations of different norms in 1-D space [START_REF] Elad | Sparse and redundant representations: from theory to applications in signal and image processing[END_REF].

In order to more specifically elucidate the meaning and solutions of different norm minimizations, the geometry in 2-D space is used to explicitly illustrate the solutions of the l 0 -norm minimization in Fig. 4a, l 1 -norm minimization in Fig. 4b, and l 2 -norm minimization in Fig. 4c. Let S = {x * : Ax = y} denote the line in 2-D space and a hyperplane will be formulated in higher dimensions. All possible solution x * must lie on the line of S. In order to visualize how to obtain the solution of different norm-based minimization problems, we take the l 1 -norm minimization problem as an example to explicitly interpret. Suppose that we inflate the l 1ball from an original status until it hits the hyperplane S at some point. Thus, the solution of the l 1 -norm minimization problem is the aforementioned touched point. If the sparse solution of the linear system is localized on the coordinate axis, it will be sparse enough. From the perspective of Fig. 4, it can be seen that the solutions of both the l 0 -norm and l 1 -norm minimization are sparse, whereas for the l 2norm minimization, it is very difficult to rigidly satisfy the condition of sparsity. However, it has been demonstrated that the representation solution of the l 2 -norm minimization is not strictly sparse enough but "limitedly-sparse", which means it possesses the capability of discriminability [START_REF] Zhang | Noise modeling and representation based classification methods for face recognition[END_REF].

The Frobenius norm, L 1 -norm of matrix X ∈ R m×n , and l 2 -norm or spectral norm are respectively defined as

X F = ( n i=1 m j=1 X 2 j,i ) 1/2 , X L1 = max j=1,...,n m i=1 |x ij |, X 2 = δ max (X) = (λ max (X T X)) 1/2 (II.6)
where δ is the singular value operator and the l 2 -norm of X is its maximum singular value [START_REF] Boyd | Convex optimization[END_REF]. The l 2,1 -norm or R 1 -norm is defined on matrix term, that is

X 2,1 = n i=1 ( m j=1 X 2 j,i ) 1/2 (II.7)
As shown above, a norm can be viewed as a measure of the length of a vector v. The distance between two vectors x and y, or matrices X and Y , can be measured by the length of their differences, i.e.

dist(x, y) = x -y 2 2 , dist(X, Y ) = X -Y F (II.8
) which are denoted as the distance between x and y in the context of the l 2 -norm and the distance between X and Y in the context of the Frobenius norm, respectively.

Assume that X ∈ R m×n and the rank of X, i.e. rank(X) = r. The SVD of X is computed as

X = U ΛV T (II.9)
where U ∈ R m×r with U T U = I and V ∈ R n×r with V T V = I. The columns of U and V are called left and right singular vectors of X, respectively. Additionally, Λ is a diagonal matrix and its elements are composed of the singular values of X, i.e.

Λ = diag(λ 1 , λ 2 , • • • , λ r ) with λ 1 ≥ λ 2 ≥ • • • ≥ λ r > 0.
Furthermore, the singular value decomposition can be rewritten as

X = r i=1 λ i u i v i (II.10)
where λ i , u i and v i are the i-th singular value, the i-th column of U , and the i-th column of V , respectively [START_REF] Boyd | Convex optimization[END_REF].

III. SPARSE REPRESENTATION PROBLEM WITH DIFFERENT NORM REGULARIZATIONS

In this section, sparse representation is summarized and grouped into different categories in terms of the norm regularizations used. The general framework of sparse representation is to exploit the linear combination of some samples or "atoms" to represent the probe sample, to calculate the representation solution, i.e. the representation coefficients of these samples or "atoms", and then to utilize the representation solution to reconstruct the desired results. The representation results in sparse representation, however, can be greatly dominated by the regularizer (or optimizer) imposed on the representation solution [START_REF] Chen | Theoretical results on sparse representations of multiple-measurement vectors[END_REF][START_REF] Pant | Unconstrained regularized l p -norm based algorithm for the reconstruction of sparse signals[END_REF][START_REF] Chartrand | Iteratively reweighted algorithms for compressive sensing[END_REF][START_REF] Yang | Beyond sparsity: The role of l 1 -optimizer in pattern classification[END_REF]. Thus, in terms of the different norms used in optimizers, the sparse representation methods can be roughly grouped into five general categories: sparse representation with the l 0 -norm minimization [START_REF] Tropp | Signal recovery from random measurements via orthogonal matching pursuit[END_REF][START_REF] Needell | Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit[END_REF], sparse representation with the l p -norm (0<p<1) minimization [START_REF] Saab | Stable sparse approximations via nonconvex optimization[END_REF][START_REF] Chartrand | Exact reconstruction of sparse signals via nonconvex minimization[END_REF][START_REF] Xu | Data modeling: Visual psychology approach and l 1/2 regularization theory[END_REF], sparse representation with the l 1 -norm minimization [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF][START_REF] Efron | Least angle regression[END_REF][START_REF] Yang | Alternating direction algorithms for l 1 -problems in compressive sensing[END_REF][START_REF] Schmidt | Fast optimization methods for l 1 regularization: A comparative study and two new approaches[END_REF], sparse representation with the l 2,1 -norm minimization [START_REF] Nie | Efficient and robust feature selection via joint l 2,1 -norms minimization[END_REF][START_REF] Yang | l 2,1 -norm regularized discriminative feature selection for unsupervised learning[END_REF][START_REF] Shi | Face recognition by sparse discriminant analysis via joint l 2,1 -norm minimization[END_REF][START_REF] Liu | Multi-task feature learning via efficient l 2,1 -norm minimization[END_REF][START_REF] Hou | Joint embedding learning and sparse regression: A framework for unsupervised feature selection[END_REF], sparse representation with the l 2 -norm minimization [START_REF] Xu | A two-phase test sample sparse representation method for use with face recognition[END_REF][START_REF] Naseem | Linear regression for face recognition[END_REF][START_REF] Zhang | Sparse representation or collaborative representation: Which helps face recognition?[END_REF].

A. Sparse representation with l 0 -norm minimization

Let x 1 , x 2 , • • • , x n ∈ R d be
all the n known samples and matrix X ∈ R d×n (d<n), which is constructed by known samples, is the measurement matrix or the basis dictionary and should also be an over-completed dictionary. Each column of X is one sample and the probe sample is y ∈ R d , which is a column vector. Thus, if all the known samples are used to approximately represent the probe sample, it should be expressed as:

y = x 1 α 1 + x 2 α 2 + • • • + x n α n (III.1)
where α i (i=1,2,• • • ,n) is the coefficient of x i and Eq. III.1 can be rewritten into the following equation for convenient description:

y = Xα (III.2) where matrix X=[x 1 , x 2 , • • • , x n ] and α=[α 1 , α 2 , • • • , α n ] T .
However, problem III.2 is an underdetermined linear system of equations and the main problem is how to solve it. From the viewpoint of linear algebra, if there is not any prior knowledge or any constraint imposed on the representation solution α, problem III.2 is an ill-posed problem and will never have a unique solution. That is, it is impossible to utilize equation III.2 to uniquely represent the probe sample y using the measurement matrix X. To alleviate this difficulty, it is feasible to impose an appropriate regularizer constraint or regularizer function on representation solution α. The sparse representation method demands that the obtained representation solution should be sparse. Hereafter, the meaning of 'sparse' or 'sparsity' refers to the condition that when the linear combination of measurement matrix is exploited to represent the probe sample, many of the coefficients should be zero or very close to zero and few of the entries in the representation solution are differentially large.

The sparsest representation solution can be acquired by solving the linear representation system III.2 with the l 0norm minimization constraint [START_REF] Donoho | Optimally sparse representation in general (nonorthogonal) dictionaries via l 1 minimization[END_REF]. Thus problem III.2 can be converted to the following optimization problem:

α = arg min α 0 s.t. y = Xα (III.3)
where • 0 refers to the number of nonzero elements in the vector and is also viewed as the measure of sparsity. Moreover, if just k (k < n) atoms from the measurement matrix X are utilized to represent the probe sample, problem III.3 will be equivalent to the following optimization problem:

y = Xα s.t. α 0 ≤ k (III.
α = L(α, λ) = arg min y -Xα 2 2 + λ α 0 (III.8)
where λ refers to the Lagrange multiplier associated with α 0 .

B. Sparse representation with l 1 -norm minimization

The l 1 -norm originates from the Lasso problem [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF][START_REF] Efron | Least angle regression[END_REF] and it has been extensively used to address issues in machine learning, pattern recognition, and statistics [START_REF] Liu | Realistic action recognition via sparsely-constructed gaussian processes[END_REF][START_REF] Patel | Sparse representations, compressive sensing and dictionaries for pattern recognition[END_REF][START_REF] Yuan | Learning hash functions using sparse reconstruction[END_REF]. Although the sparse representation method with l 0 -norm minimization can obtain the fundamental sparse solution of α over the matrix X, the problem is still a non-deterministic polynomial-time hard (NP-hard) problem and the solution is difficult to approximate [START_REF] Amaldi | On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems[END_REF]. Recent literature [START_REF] Wright | Robust face recognition via sparse representation[END_REF][START_REF] Donoho | For most large underdetermined systems of linear equations the minimal l 1 -norm solution is also the sparsest solution[END_REF][START_REF] Candes | Stable signal recovery from incomplete and inaccurate measurements[END_REF][START_REF] Candes | Near-optimal signal recovery from random projections: Universal encoding strategies?[END_REF] has demonstrated that when the representation solution obtained by using the l 1 -norm minimization constraint is also content with the condition of sparsity and the solution using l 1 -norm minimization with sufficient sparsity can be equivalent to the solution obtained by l 0 -norm minimization with full probability. Moreover, the l 1 -norm optimization problem has an analytical solution and can be solved in polynomial time. Thus, extensive sparse representation methods with the l 1 -norm minimization have been proposed to enrich the sparse representation theory. The applications of sparse representation with the l 1 -norm minimization are extraordinarily and remarkably widespread. Correspondingly, the main popular structures of sparse representation with the l 1 -norm minimization , similar to sparse representation with l 0 -norm minimization, are generally used to solve the following problems:

α = arg min α α 1 s.t. y = Xα (III.9) α = arg min α α 1 s.t. y -Xα 2 2 ≤ ε (III.10) or α = arg min α y -Xα 2 2 s.t. α 1 ≤ τ (III.11) α = L(α, λ) = arg min α 1 2 y -Xα 2 2 + λ α 1 (III.12)
where λ and τ are both small positive constants.

C. Sparse representation with l p -norm (0<p<1) minimization

The general sparse representation method is to solve a linear representation system with the l p -norm minimization problem. In addition to the l 0 -norm minimization and l 1 -norm minimization, some researchers are trying to solve the sparse representation problem with the l p -norm (0<p<1) minimization, especially p = 0.1, 1 2 , 1 3 , or 0.9 [START_REF] Qin | A comparison of typical l p minimization algorithms[END_REF][START_REF] Xu | l 1/2 regularization: A thresholding representation theory and a fast solver[END_REF][START_REF] Guo | Enhancing sparsity via l p (0<p<1) minimization for robust face recognition[END_REF]. That is, the sparse representation problem with the l p -norm (0<p<1) minimization is to solve the following problem:

α = arg min α α p p s.t. y -Xα 2 2 ≤ ε (III.13) or α = L(α, λ) = arg min α y -Xα 2 2 + λ α p p (III.14)
In spite of the fact that sparse representation methods with the l p -norm (0<p<1) minimization are not the mainstream methods to obtain the sparse representation solution, it tremendously influences the improvements of the sparse representation theory.

D. Sparse representation with l 2,1 -norm minimization

The representation solution obtained by the l 2 -norm minimization is not rigorously sparse. It can only obtain a 'limitedlysparse' representation solution, i.e. the solution has the property that it is discriminative and distinguishable but is not really sparse enough [START_REF] Zhang | Noise modeling and representation based classification methods for face recognition[END_REF]. The objective function of the sparse representation method with the l 2 -norm minimization is to solve the following problem:

α = arg min α α 2 2 s.t. y -Xα 2 2 ≤ ε (III.15) or α = L(α, λ) = arg min α y -Xα 2 2 + λ α 2 2 (III.16)
On the other hand, the l 2,1 -norm is also called the rotation invariant l 1 -norm, which is proposed to overcome the difficulty of robustness to outliers [START_REF] Ding | R1-pca: rotational invariant l 1 -norm principal component analysis for robust subspace factorization[END_REF]. The objective function of the sparse representation problem with the l 2,1 -norm minimization is to solve the following problem:

arg min A Y -XA 2,1 + µ A 2,1 (III.17)
where

Y = [y 1 , y 2 , • • • , y N ] refers to the matrix composed of samples, A = [a 1 , a 2 , • • • , a N ]
is the corresponding coefficient matrix of X, and µ is a small positive constant. Sparse representation with the l 2,1 -norm minimization can be implemented by exploiting the proposed algorithms in literature [START_REF] Nie | Efficient and robust feature selection via joint l 2,1 -norms minimization[END_REF][START_REF] Yang | l 2,1 -norm regularized discriminative feature selection for unsupervised learning[END_REF][START_REF] Shi | Face recognition by sparse discriminant analysis via joint l 2,1 -norm minimization[END_REF].

IV. GREEDY STRATEGY APPROXIMATION Greedy algorithms date back to the 1950s. The core idea of the greedy strategy [START_REF] Elad | Sparse and redundant representations: from theory to applications in signal and image processing[END_REF][START_REF] Tropp | Algorithms for simultaneous sparse approximation. part i: Greedy pursuit[END_REF] is to determine the position based on the relationship between the atom and probe sample, and then to use the least square to evaluate the amplitude value. Greedy algorithms can obtain the local optimized solution in each step in order to address the problem. However, the greedy algorithm can always produce the global optimal solution or an approximate overall solution [START_REF] Elad | Sparse and redundant representations: from theory to applications in signal and image processing[END_REF][START_REF] Tropp | Algorithms for simultaneous sparse approximation. part i: Greedy pursuit[END_REF]. Addressing sparse representation with l 0 -norm regularization, i.e. problem III.3, is an NP hard problem [START_REF] Wright | Robust face recognition via sparse representation[END_REF][START_REF] Donoho | For most large underdetermined systems of linear equations the minimal l 1 -norm solution is also the sparsest solution[END_REF]. The greedy strategy provides a special way to obtain an approximate sparse representation solution. The greedy strategy actually can not directly solve the optimization problem and it only seeks an approximate solution for problem III.3.

A. Matching pursuit algorithm

The matching pursuit (MP) algorithm [START_REF] Mallat | Matching pursuits with time-frequency dictionaries[END_REF] is the earliest and representative method of using the greedy strategy to approximate problem III.3 or III.4. The main idea of the MP is to iteratively choose the best atom from the dictionary based on a certain similarity measurement to approximately obtain the sparse solution. Taking as an example of the sparse decomposition with a vector sample y over the over-complete dictionary D, the detailed algorithm description is presented as follows:

Suppose that the initialized representation residual is

R 0 = y, D = [d 1 , d 2 , • • • , d N ] ∈ R d×N
and each sample in dictionary D is an l 2 -norm unity vector, i.e. d i = 1. To approximate y, MP first chooses the best matching atom from D and the selected atom should satisfy the following condition:

| R 0 , d l0 | = sup| R 0 , d i | (IV.1)
where l 0 is a label index from dictionary D. Thus y can be decomposed into the following equation:

y = y, d l0 d l0 + R 1 (IV.2)
So y = R 0 , d l0 d l0 + R 1 where R 0 , d l0 d l0 represents the orthogonal projection of y onto d l0 , and R 1 is the representation residual by using d l0 to represent y. Considering the fact that d l0 is orthogonal to R 1 , Eq. IV.2 can be rewritten as

y 2 = | y, d l0 | 2 + R 1 2 (IV.3)
To obtain the minimum representation residual, the MP algorithm iteratively figures out the best matching atom from the over-completed dictionary, and then utilizes the representation residual as the next approximation target until the termination condition of iteration is satisfied. For the t-th iteration, the best matching atom is d lt and the approximation result is found from the following equation:

R t = R t , d lt d lt + R t+1 (IV.4)
where the d lt satisfies the equation:

| R t , d lt | = sup| R t , d i | (IV.5)
Clearly, d lt is orthogonal to R k+1 , and then

R k 2 = | R t , d lt | 2 + R t+1 2 (IV.6)
For the n-th iteration, the representation residual R n 2 ≤ τ where τ is a very small constant and the probe sample y can be formulated as:

y = n-1 j=1 R j , d lj d lj + R n (IV.7)
If the representation residual is small enough, the probe sample y can approximately satisfy the following equation: y ≈ n-1 j=1 R j , d lj d lj where n ≪ N . Thus, the probe sample can be represented by a small number of elements from a large dictionary. In the context of the specific representation error, the termination condition of sparse representation is that the representation residual is smaller than the presupposed value. More detailed analysis on matching pursuit algorithms can be found in the literature [START_REF] Mallat | Matching pursuits with time-frequency dictionaries[END_REF].

B. Orthogonal matching pursuit algorithm

The orthogonal matching pursuit (OMP) algorithm [START_REF] Tropp | Signal recovery from random measurements via orthogonal matching pursuit[END_REF][START_REF] Pati | Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition[END_REF] is an improvement of the MP algorithm. The OMP employs the process of orthogonalization to guarantee the orthogonal direction of projection in each iteration. It has been verified that the OMP algorithm can be converged in limited iterations [START_REF] Tropp | Signal recovery from random measurements via orthogonal matching pursuit[END_REF]. The main steps of OMP algorithm have been summarized in Algorithm 1.

C. Series of matching pursuit algorithms

It is an excellent choice to employ the greedy strategy to approximate the solution of sparse representation with the l 0 -norm minimization. These algorithms are typical greedy iterative algorithms. The earliest algorithms were the matching pursuit (MP) and orthogonal matching pursuit (OMP). The basic idea of the MP algorithm is to select the best matching atom from the overcomplete dictionary to construct sparse approximation during each iteration, to compute the signal representation residual, and then to choose the best matching atom till the stopping criterion of iteration is satisfied. Many more greedy algorithms based on the MP and OMP algorithm such as the efficient orthogonal matching pursuit algorithm [START_REF] Vitaladevuni | Efficient orthogonal matching pursuit using sparse random projections for scene and video classification[END_REF] subsequently have been proposed to improve the pursuit algorithm. Needell et al. proposed an regularized version of orthogonal matching pursuit (ROMP) algorithm [START_REF] Needell | Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit[END_REF], which recovered all k sparse signals based on the Restricted Isometry Property of random frequency measurements, and then proposed another variant of OMP algorithm called compressive sampling matching pursuit (CoSaMP) algorithm [START_REF] Needell | Cosamp: Iterative signal recovery from incomplete and inaccurate samples[END_REF], which incorporated several existing ideas such as restricted isometry property (RIP) and pruning technique into a greedy iterative structure of OMP. Some other algorithms also had an impressive influence on future research on CS. For example, Donoho et al. proposed an extension of OMP, called stage-wise orthogonal matching pursuit (StOMP) algorithm [START_REF] Donoho | Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit[END_REF], which depicted an iterative algorithm with three main steps, i.e. threholding, selecting and projecting. Dai and Milenkovic proposed a new method for sparse signal reconstruction named subspace pursuit (SP) algorithm [START_REF] Dai | Subspace pursuit for compressive sensing signal reconstruction[END_REF], which sampled signals satisfying the constraints of the RIP with a constant parameter. Do et al. presented a sparsity adaptive matching pursuit (SAMP) algorithm [START_REF] Do | Sparsity adaptive matching pursuit algorithm for practical compressed sensing[END_REF], which borrowed the idea of the EM algorithm to alternatively estimate the sparsity and support set. Jost et al. proposed a tree-based matching pursuit (TMP) algorithm [START_REF] Jost | Tree-based pursuit: Algorithm and properties[END_REF], which constructed a tree structure and employed a structuring strategy to cluster similar signal atoms from a highly redundant dictionary as a new dictionary. Subsequently, La and Do proposed a new tree-based orthogonal matching pursuit (TBOMP) algorithm [START_REF] La | Tree-based orthogonal matching pursuit algorithm for signal reconstruction[END_REF], which treated the sparse tree representation as an additional prior knowledge for linear inverse systems by using a small number of samples. Recently, Karahanoglu and Erdogan conceived a forward-backward pursuit (FBP) method [START_REF] Karahanoglu | Compressed sensing signal recovery via forward-backward pursuit[END_REF] with two greedy stages, in which the forward stage enlarged the support estimation and the backward stage removed some unsatisfied atoms. More detailed treatments of the greedy pursuit for sparse representation can be found in the literature [START_REF] Tropp | Algorithms for simultaneous sparse approximation. part i: Greedy pursuit[END_REF].

V. CONSTRAINED OPTIMIZATION STRATEGY

Constrained optimization strategy is always utilized to obtain the solution of sparse representation with the l 1 -norm regularization. The methods that address the non-differentiable unconstrained problem will be presented by reformulating it as a smooth differentiable constrained optimization problem. These methods exploit the constrained optimization method with efficient convergence to obtain the sparse solution. What is more, the constrained optimization strategy emphasizes the equivalent transformation of α 1 in problem III.12 and employs the new reformulated constrained problem to obtain a sparse representation solution. Some typical methods that employ the constrained optimization strategy to solve the original unconstrained non-smooth problem are introduced in this section.

A. Gradient Projection Sparse Reconstruction

The core idea of the gradient projection sparse representation method is to find the sparse representation solution along with the gradient descent direction. The first key procedure of gradient projection sparse reconstruction (GPSR) [START_REF] Figueiredo | Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems[END_REF] provides a constrained formulation where each value of α can be split into its positive and negative parts. Vectors α + and α -are introduced to denote the positive and negative coefficients of α, respectively. The sparse representation solution α can be formulated as:

α = α + -α -, α + ≥ 0, α -≥ 0 (V.1)
where the operator (•) + denotes the positive-part operator, which is defined as (x) + =max{0, x}. Thus,

α 1 = 1 T d α + + 1 T d α -, where 1 d = [1, 1, • • • , 1 d
] T is a d-dimensional vector with d ones. Accordingly, problem III.12 can be reformulated as a constrained quadratic problem:

arg min L(α) = arg min 1 2 y -X[α + -α -] 2 2 + λ(1 T d α + + 1 T d α -) s.t. α + ≥ 0, α -≥ 0 (V.2) or arg min L(α) = arg min 1 2 y -[X + , X -][α + -α -] 2 2 +λ(1 T d α + + 1 T d α -) s.t. α + ≥ 0, α -≥ 0 (V.3)
Furthermore, problem V.3 can be rewritten as:

arg min G(z) = c T z + 1 2 z T Az s.t. z ≥ 0 (V.4) where z = [α + ; α -], c = λ1 2d + [-X T y; X T y], 1 2d = [1, • • • , 1 2d ] T , A = X T X -X T X -X T X X T X .
The GPSR algorithm employs the gradient descent and standard line-search method [START_REF] Boyd | Convex optimization[END_REF] to address problem V.4. The value of z can be iteratively obtained by utilizing

arg min z t+1 = z t -σ∇G(z t ) (V.5)
where the gradient of ∇G(z t ) = c + Az t and σ is the step size of the iteration. For step size σ, GPSR updates the step size by using

σ t = arg min σ G(z t -σg t ) (V.6)
where the function g t is pre-defined as

g t i = (∇G(z t )) i , if z t i > 0 or (∇G(z t )) i < 0 0, otherwise. (V.7)
Problem V.6 can be addressed with the close-form solution

σ t = (g t ) T (g t ) (g t ) T A(g t ) (V.8)
Furthermore, the basic GPSR algorithm employs the backtracking linear search method [START_REF] Boyd | Convex optimization[END_REF] to ensure that the step size of gradient descent, in each iteration, is a more proper value. The stop condition of the backtracking linear search should satisfy

G((z t -σ t ∇G(z t )) + ) > G(z t ) -β∇G(z t ) T (z t -(z t -σ t ∇G(z t )) + ) (V.9)
where β is a small constant. The main steps of GPSR are summarized in Algorithm 2. For more detailed information, one can refer to the literature [START_REF] Figueiredo | Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems[END_REF].

Algorithm 2. Gradient Projection Sparse Reconstruction (GPSR)

Task: To address the unconstraint problem: α = arg minα 1 2 y -Xα 2 2 + λ α 1 Input: Probe sample y, the measurement matrix X, small constant λ Initialization: t = 0, β ∈ (0, 0.5), γ ∈ (0, 1), given α so that z = [α + , α -].

While not converged do

Step 1: Compute σ t exploiting Eq. V.8 and σ t ← mid(σ min , σ t , σmax), where mid(•, •, •) denotes the middle value of the three parameters.

Step 2: While Eq. V.9 not satisfied do σ t ← γσ t end Step 3: z t+1 = (z t -σ t ∇G(z t )) + and t = t + 1. End Output: z t+1 , α

B. Interior-point method based sparse representation strategy

The Interior-point method [START_REF] Boyd | Convex optimization[END_REF] is not an iterative algorithm but a smooth mathematic model and it always incorporates the Newton method to efficiently solve unconstrained smooth problems of modest size [START_REF] Parikh | Proximal algorithms[END_REF]. When the Newton method is used to address the optimization issue, a complex Newton equation should be solved iteratively which is very timeconsuming. A method named the truncated Newton method can effectively and efficiently obtain the solution of the Newton equation. A prominent algorithm called the truncated Newton based interior-point method (TNIPM) exists, which can be utilized to solve the large-scale l 1 -regularized least squares (i.e. l 1 l s ) problem [START_REF] Kim | An interior-point method for largescale l 1 -regularized least squares[END_REF].

The original problem of l 1 l s is to solve problem III.12 and the core procedures of l 1 l s are shown below:

(1) Transform the original unconstrained non-smooth problem to a constrained smooth optimization problem.

(2) Apply the interior-point method to reformulate the constrained smooth optimization problem as a new unconstrained smooth optimization problem.

(3) Employ the truncated Newton method to solve this unconstrained smooth problem.

The main idea of the l 1 l s will be briefly described. For simplicity of presentation, the following one-dimensional problem is used as an example.

|α| = arg min -σ≤α≤σ σ (V.10)
where σ is a proper positive constant.

Thus, problem III.12 can be rewritten as

α = arg min 1 2 y -Xα 2 2 + λ α 1 = arg min 1 2 y -Xα 2 2 + λ N i=1 min -σi≤αi≤σi σ i = arg min 1 2 y -Xα 2 2 + λ min -σi≤αi≤σi N i=1 σ i = arg min -σi≤αi≤σi 1 2 y -Xα 2 2 + λ N i=1 σ i (V.11
) Thus problem III.12 is also equivalent to solve the following problem:

α = arg min α,σ∈R N 1 2 y-Xα 2 2 +λ N i=1 σ i s.t. -σ i ≤ α i ≤ σ i (V.12) or α = arg min α,σ∈R N 1 2 y -Xα 2 2 + λ N i=1 σ i s.t. σ i + α i ≥ 0, σ i -α i ≥ 0 (V.13)
The interior-point strategy can be used to transform problem V.13 into an unconstrained smooth problem

α = arg min α,σ∈R N G(α, σ) = v 2 y-Xα 2 2 +λv N i=1 σ i -B(α, σ) (V.14) where B(α, σ) = N i=1 log(σ i + α i ) + N i=1 log(σ i -α i
) is a barrier function, which forces the algorithm to be performed within the feasible region in the context of unconstrained condition.

Subsequently, l 1 l s utilizes the truncated Newton method to solve problem V.14. The main procedures of addressing problem V.14 are presented as follows: First, the Newton system is constructed

H △α △σ = -∇G(α, σ) ∈ R 2N (V.15)
where

H = -∇ 2 G(α, σ) ∈ R 2N ×2N
is the Hessian matrix, which is computed using the preconditioned conjugate gradient algorithm, and then the direction of linear search [△α, △σ] is obtained. Second, the Lagrange dual of problem III.12 is used to construct the dual feasible point and duality gap: a) The Lagrangian function and Lagrange dual of problem III.12 are constructed. The Lagrangian function is reformulated as

L(α, z, u) = z T z + λ α 1 + u(Xα -y -z) (V.16)
where its corresponding Lagrange dual function is

α = arg max F (u) = - 1 4 u T u -u T y s.t. |(X T u) i | ≤ λ i (i = 1, 2, • • • , N ) (V.17) b) A dual feasible point is constructed u = 2s(y-Xα), s = min{λ/|2y i -2(X T Xα) i |}∀i (V.18)
where u is a dual feasible point and s is the step size of the linear search.

c) The duality gap is constructed, which is the gap between the primary problem and the dual problem:

g = y -Xα + λ α 1 -F (u) (V.19)
Third, the method of backtracking linear search is used to determine an optimal step size of the Newton linear search. The stopping condition of the backtracking linear search is

G(α+η t △α, σ+η t △σ) > G(α, σ)+ρη t ∇G(α, σ)[△α, △σ] (V.20
) where ρ ∈ (0, 0.5) and η t ∈ (0, 1) is the step size of the Newton linear search. Finally, the termination condition of the Newton linear search is set to

ζ = min{0.1, βg/ h 2 } (V.21)
where the function h = ∇G(α, σ), β is a small constant, and g is the duality gap. The main steps of algorithm l 1 l s are summarized in Algorithm 3. For further description and analyses, please refer to the literature [START_REF] Kim | An interior-point method for largescale l 1 -regularized least squares[END_REF].

Algorithm 3. Truncated Newton based interior-point method (TNIPM) for l 1 ls Task: To address the unconstraint problem:

α = arg minα 1 2 y -Xα 2 2 + λ α 1 Input: Probe sample y, the measurement matrix X, small constant λ Initialization: t = 1, v = 1 λ , ρ ∈ (0, 0.5), σ = 1 N
Step 1: Employ preconditioned conjugate gradient algorithm to obtain the approximation of H in Eq. V.15, and then obtain the descent direction of linear search [△α t , △σ t ].

Step 2: Exploit the algorithm of backtracking linear search to find the optimal step size of Newton linear search η t , which satisfies the Eq. V.20.

Step 3: Update the iteration point utilizing (α t+1 , σ t+1 ) = (α t , σ t )+ (△α t + △σ t ).

Step 4: Construct feasible point using eq. V.18 and duality gap in Eq. V.19, and compute the termination tolerance ζ in Eq. V.21.

Step 5: If the condition g/F (u) > ζ is satisfied, stop; Otherwise, return to step 1, update v in Eq. V.14 and t = t + 1.

Output: α

The truncated Newton based interior-point method (TNIPM) [START_REF] Portugal | A truncated primal-infeasible dual-feasible network interior point method[END_REF] is a very effective method to solve the l 1 -norm regularization problems. Koh et al. [START_REF] Koh | An interior-point method for large-scale l 1 -regularized logistic regression[END_REF] also utilized the TNIPM to solve large scale logistic regression problems, which employed a preconditioned conjugate gradient method to compute the search step size with warm-start techniques. Mehrotra proposed to exploit the interior-point method to address the primal-dual problem [START_REF] Mehrotra | On the implementation of a primal-dual interior point method[END_REF] and introduced the second-order derivation of Taylor polynomial to approximate a primal-dual trajectory. More analyses of interior-point method for sparse representation can be found in the literature [START_REF] Wright | Primal-dual interior-point methods[END_REF].

C. Alternating direction method (ADM) based sparse representation strategy

This section shows how the ADM [START_REF] Yang | Alternating direction algorithms for l 1 -problems in compressive sensing[END_REF] is used to solve primal and dual problems in III.12. First, an auxiliary variable is introduced to convert problem in III.12 into a constrained problem with the form of problem V.22. Subsequently, the alternative direction method is used to efficiently address the sub-problems of problem V. [START_REF] Cheng | Sparse representation and learning in visual recognition: Theory and applications[END_REF]. By introducing the auxiliary term s ∈ R d , problem III.12 is equivalent to a constrained problem

arg min α,s 1 2τ s 2 + α 1 s.t. s = y -Xα (V.22)
The optimization problem of the augmented Lagrangian function of problem V.22 is considered

arg min α,s,λ L(α, s, λ) = 1 2τ s 2 + α 1 -λ T (s+ Xα -y) + µ 2 s + Xα -y 2 2 (V.23)
where λ ∈ R d is a Lagrange multiplier vector and µ is a penalty parameter. The general framework of ADM is used to solve problem V.23 as follows:

   s t+1 = arg min L(s, α t , λ t ) (a) α t+1 = arg min L(s t+1 , α, λ t ) (b) λ t+1 = λ t -µ(s t+1 + Xα t+1 -y) (c) (V.24)
First, the first optimization problem V.24(a) is considered

arg min L(s, α t , λ t ) = 1 2τ s 2 + α t 1 -(λ t ) T (s + Xα t -y) + µ 2 s + Xα t -y 2 2 = 1 2τ s 2 -(λ t ) T s + µ 2 s + Xα t -y 2 2 + α t 1 -(λ t ) T (Xα t -y) (V.25)
Then, it is known that the solution of problem V.25 with respect to s is given by

s t+1 = τ 1 + µτ (λ t -µ(y -Xα t )) (V.26)
Second, the optimization problem V.24(b) is considered

arg min L(s t+1 , α, λ t ) = 1 2τ s t+1 2 + α 1 -(λ) T (s t+1 + Xα -y) + µ 2 s t+1 + Xα -y 2 2
which is equivalent to

arg min{ α 1 -(λ t ) T (s t+1 + Xα -y) + µ 2 s t+1 + Xα -y 2 2 } = α 1 + µ 2 s t+1 + Xα -y -λ t /µ 2 2 = α 1 + f (α) (V.27)
where

f (α) = µ 2 s t+1 +Xα-y-λ t /µ 2 2 .
If the second order Taylor expansion is used to approximate f (α), the problem V.27 can be approximately reformulated as

arg min{ α 1 + (α -α t ) T X T (s t+1 + Xα t -y -λ t /µ) + 1 2τ α -α t 2 2 } (V.28)
where τ is a proximal parameter. The solution of problem V.28 can be obtained by the soft thresholding operator

α t+1 = sof t{α t -τ X T (s t+1 +Xα t -y-λ t /µ), τ µ } (V.29)
where sof t(σ, η) = sign(σ) max{|σ| -η, 0}.

Finally, the Lagrange multiplier vector λ is updated by using Eq. V.24(c). The algorithm presented above utilizes the second order Taylor expansion to approximately solve the sub-problem V.27 and thus the algorithm is denoted as an inexact ADM or approximate ADM. The main procedures of the inexact ADM based sparse representation method are summarized in Algorithm 4. More specifically, the inexact ADM described above is to reformulate the unconstrained problem as a constrained problem, and then utilizes the alternative strategy to effectively address the corresponding sub-optimization problem. Moreover, ADM can also efficiently solve the dual problems of the primal problems III.9-III.12. For more information, please refer to the literature [START_REF] Yang | Alternating direction algorithms for l 1 -problems in compressive sensing[END_REF][START_REF] Boyd | Distributed optimization and statistical learning via the alternating direction method of multipliers[END_REF].

Algorithm 4. Alternating direction method (ADM) based sparse representation strategy

Task: To address the unconstraint problem: α = arg minα 1 2 y -Xα 2 2 + τ α 1 Input: Probe sample y, the measurement matrix X, small constant λ Initialization: t = 0, s 0 = 0, α 0 = 0, λ 0 = 0, τ = 1.01, µ is a small constant.

Step 1: Construct the constraint optimization problem of problem III.12 by introducing the auxiliary parameter and its augmented Lagrangian function, i.e. problem (V.22) and (V.23).

While not converged do

Step 2: Update the value of the s t+1 by using Eq. (V.25).

Step 2: Update the value of the α t+1 by using Eq. (V.29).

Step 3: Update the value of the λ t+1 by using Eq. (V.24(c)).

Step 4: µ t+1 = τ µ t and t = t + 1. End While Output: α t+1

VI. PROXIMITY ALGORITHM BASED OPTIMIZATION

STRATEGY

In this section, the methods that exploit the proximity algorithm to solve constrained convex optimization problems are discussed. The core idea of the proximity algorithm is to utilize the proximal operator to iteratively solve the sub-problem, which is much more computationally efficient than the original problem. The proximity algorithm is frequently employed to solve nonsmooth, constrained convex optimization problems [START_REF] Parikh | Proximal algorithms[END_REF]. Furthermore, the general problem of sparse representation with l 1 -norm regularization is a nonsmooth convex optimization problem, which can be effectively addressed by using the proximal algorithm.

Suppose a simple constrained optimization problem is

min{h(x)|x ∈ χ} (VI.1)
where χ ⊂ R n . The general framework of addressing the constrained convex optimization problem VI.1 using the proximal algorithm can be reformulated as

xt = arg min{h(x) + τ 2 x -x t 2 |x ∈ χ} (VI.2)
where τ and x t are given. For definiteness and without loss of generality, it is assumed that there is the following linear constrained convex optimization problem

arg min{F (x) + G(x)|x ∈ χ} (VI.3)
The solution of problem VI.3 obtained by employing the proximity algorithm is:

x t+1 = arg min{F (x) + ∇G(x t ), x -x t + 1 2τ x -x t 2 } = arg min{F (x) + 1 2τ x -θ t 2 } (VI.4)
where θ = x t -τ ∇G(x t ). More specifically, for the sparse representation problem with l 1 -norm regularization, the main problem can be reformulated as:

min P (α) = {λ α 1 | Aα = y} or min P (α) = {λ α 1 + Aα -y 2 2 | α ∈ R n } (VI.5)
which are considered as the constrained sparse representation of problem III.12.

A. Soft thresholding or shrinkage operator

First, a simple form of problem III.12 is introduced, which has a closed-form solution, and it is formulated as:

α * = min α h(α) =λ α 1 + 1 2 α -s 2 = N j=1 λ|α j | + N j=1 1 2 (α j -s j ) 2 (VI.6)
where α * is the optimal solution of problem VI.6, and then there are the following conclusions:

(1) if

α j > 0, then h(α) = λα + 1 2 α -s 2 and its derivative is h ′ (α j ) = λ + α * j -s j . Let h ′ (α j ) = 0 ⇒ α * j = s j -λ, where it indicates s j > λ; (2) if α j < 0, then h(α) = -λα+ 1 2 α-s 2 and its derivative is h ′ (α j ) = -λ + α * j -s j . Let h ′ (α j ) = 0 ⇒ α * j = s j + λ, where it indicates s j < -λ; (3) if -λ ≤ s j ≤ λ,
and then α * j = 0. So the solution of problem VI.6 is summarized as

α * j =    s j -λ, if s j > λ s j + λ, if s j < -λ 0, otherwise (VI.7)
The equivalent expression of the solution is α * = shrink(s, λ), where the j-th component of shrink(s, λ) is shrink(s, λ) j = sign(s j ) max{|s j | -λ, 0}. The operator shrink(•) can be regarded as a proximal operator.

B. Iterative shrinkage thresholding algorithm (ISTA)

The objective function of ISTA [START_REF] Figueiredo | A bound optimization approach to wavelet-based image deconvolution[END_REF] has the form of

arg min F (α) = 1 2 Xα -y 2 2 + λ α 1 = f (α) + λg(α) (VI.8
) and is usually difficult to solve. Problem VI.8 can be converted to the form of an easy problem VI.6 and the explicit procedures are presented as follows.

First, Taylor expansion is used to approximate f (α) = 1 2 Xαy 2 2 at a point of α t . The second order Taylor expansion is

f (α) = f (α t ) + (α -α t ) T ∇f (α t ) + 1 2 (α -α t ) T H f (α t )(α -α t ) + • • • (VI.9)
where H f (α t ) is the Hessian matrix of f (α) at α t . For the function f (α), ∇f (α) = X T (Xαy) and H f (α) = X T X can be obtained.

f (α) = 1 2 Xα t -y 2 2 + (α -α t ) T X T (Xα t -y)+ 1 2 (α -α t ) T X T X(α -α t ) (VI.10)
If the Hessian matrix H f (α) is replaced or approximated in the third term above by using a scalar 1 τ I, and then

f (α) ≈ 1 2 Xα t -y 2 2 + (α -α t ) T X T (Xα t -y) + 1 2τ (α -α t ) T (α -α t ) = Q t (α, α t ) (VI.11)
Thus problem VI.8 using the proximal algorithm can be successively addressed by

α t+1 = arg min Q t (α, α t ) + λ α 1 (VI.12)
Problem VI.12 is reformulated to a simple form of problem VI.6 by

Q t (α, α t ) = 1 2 Xα t -y 2 2 +(α -α t ) T X T (Xα t -y)+ 1 2τ α -α t 2 2 = 1 2 Xα t -y 2 2 + 1 2τ α-α t + τ X T (Xα t -y) 2 2 - τ 2 X T (Xα t -y) 2 2 = 1 2τ α -(α t -τ X T (Xα t -y)) 2 2 + B(α t ) (VI.13)
where the term

B(α t ) = 1 2 Xα t -y 2 2 -τ 2 X T (Xα t -y) 2 in problem VI.
12 is a constant with respect to variable α, and it can be omitted. As a result, problem VI.12 is equivalent to the following problem:

α t+1 = arg min 1 2τ α -θ(α t ) 2 2 + λ α 1 (VI.14)
where θ(α t ) = α t -τ X T (Xα ty).

The solution of the simple problem VI.6 is applied to solve problem VI.14 where the parameter t is replaced by the equation θ(α t ), and the solution of problem VI.14 is α t+1 = shrink(θ(α t ), λτ ). Thus, the solution of ISTA is reached. The techniques used here are called linearization or preconditioning and more detailed information can be found in the literature [START_REF] Figueiredo | A bound optimization approach to wavelet-based image deconvolution[END_REF][START_REF] Combettes | Proximal splitting methods in signal processing[END_REF].

C. Fast Iterative shrinkage thresholding algorithm (FISTA)

The fast iterative shrinkage thresholding algorithm (FISTA) is an improvement of ISTA. FISTA [START_REF] Beck | A fast iterative shrinkagethresholding algorithm for linear inverse problems[END_REF] not only preserves the efficiency of the original ISTA but also promotes the effectiveness of ISTA so that FISTA can obtain global convergence.

Considering that the Hessian matrix H f (α) is approximated by using a scalar 1 τ I for ISTA in Eq. VI.9, FISTA utilizes the minimum Lipschitz constant of the gradient ∇f (α) to approximate the Hessian matrix of f (α), i.e. L(f ) = 2λ max (X T X). Thus, the problem VI.8 can be converted to the problem below:

f (α) ≈ 1 2 Xα t -y 2 2 + (α -α t ) T X T (Xα t -y) + L 2 (α -α t ) T (α -α t ) = P t (α, α t ) (VI.15)
where the solution can be reformulated as

α t+1 = arg min L 2 α -θ(α t ) 2 2 + λ α 1 (VI.16)
where θ(α t ) = α t -1 L X T (Xα ty). Moreover, to accelerate the convergence of the algorithm, FISTA also improves the sequence of iteration points, instead of employing the previous point it utilizes a specific linear combinations of the previous two points {α t , α t-1 }, i.e.

α t = α t + µ t -1 µ t+1 (α t -α t-1 ) (VI.17)
where µ t is a positive sequence, which satisfies µ t ≥ (t+1)/2, and the main steps of FISTA are summarized in Algorithm 5.

The backtracking linear research strategy can also be utilized to explore a more feasible value of L and more detailed analyses on FISTA can be found in the literature [START_REF] Beck | A fast iterative shrinkagethresholding algorithm for linear inverse problems[END_REF][START_REF] Yang | Fast l 1 -minimization algorithms and an application in robust face recognition: A review[END_REF]. Input: Probe sample y, the measurement matrix X, small constant λ Initialization: t = 0, µ 0 = 1, L = 2Λmax(X T X), i.e. Lipschitz constant of ∇f .

While not converged do

Step 1: Exploit the shrinkage operator in equation VI.7 to solve problem VI.16.

Step 2: Update the value of µ using

µ t+1 = 1+ √ 1+4(µ t ) 2 2
.

Step 3: Update iteration sequence α t using equation VI.17. End Output: α

D. Sparse reconstruction by separable approximation (SpaRSA)

Sparse reconstruction by separable approximation (SpaRSA) [START_REF] Wright | Sparse reconstruction by separable approximation[END_REF] is another typical proximity algorithm based on sparse representation, which can be viewed as an accelerated version of ISTA. SpaRSA provides a general algorithmic framework for solving the sparse representation problem and here a simple specific SpaRSA with adaptive continuation on ISTA is introduced. The main contributions of SpaRSA are trying to optimize the parameter λ in problem VI.8 by using the worm-starting technique, i.e. continuation, and choosing a more reliable approximation of H f (α) in problem VI.9 using the Barzilai-Borwein (BB) spectral method [START_REF] Dai | The cyclic barzilai-borwein method for unconstrained optimization[END_REF]. The wormstarting technique and BB spectral approach are introduced as follows.

(

1) Utilizing the worm-starting technique to optimize λ

The values of λ in the sparse representation methods discussed above are always set to be a specific small constant. However, Hale et al. [START_REF] Hale | A fixed-point continuation method for l 1 -regularized minimization with applications to compressed sensing[END_REF] concluded that the technique that exploits a decreasing value of λ from a warm-starting point can more efficiently solve the sub-problem VI.14 than ISTA that is a fixed point iteration scheme. SpaRSA uses an adaptive continuation technique to update the value of λ so that it can lead to the fastest convergence. The procedure regenerates the value of λ using

λ = max{γ X T y ∞ , λ} (VI.18)
where γ is a small constant.

(2) Utilizing the BB spectral method to approximate H f (α) ISTA employs 1 τ I to approximate the matrix H f (α), which is the Hessian matrix of f (α) in problem VI.9 and FISTA exploits the Lipschitz constant of ∇f (α) to replace H f (α). However, SpaRSA utilizes the BB spectral method to choose the value of τ to mimic the Hessian matrix. The value of τ is required to satisfy the condition:

1 τ t+1 (α t+1 -α t ) ≈ ∇f (α t+1 ) -∇f (α t ) (VI.19)
which satisfies the minimization problem

1 τ t+1 = arg min 1 τ (α t+1 -α t ) -(∇f (α t+1 ) -∇f (α t )) 2 2 = (α t+1 -α t ) T (∇f (α t+1 ) -∇f (α t )) (α t+1 -α t ) T (α t+1 -α t ) (VI.20)
For problem VI.14, SpaRSA requires that the value of λ is a decreasing sequence using the Eq. VI.18 and the value of τ should meet the condition of Eq. VI.20. The sparse reconstruction by separable approximation (SpaRSA) is summarized in Algorithm 6 and more information can be found in the literature [START_REF] Wright | Sparse reconstruction by separable approximation[END_REF].

Algorithm 6. Sparse reconstruction by separable approximation (SpaRSA)

Task: To address the problem α = arg min F (α) = 1 2 Xαy 2 2 + λ α 1 Input: Probe sample y, the measurement matrix X, small constant λ

Initialization: t = 0, i = 0, y 0 = y, 1 τ 0 I ≈ H f (α) = X T X, tolerance ε = 10 -5 .
Step 1: λt = max{γ X T y t ∞, λ}.

Step 2: Exploit shrinkage operator to solve problem VI.14, i.e.

α i+1 = shrink(α i -τ i X T (X T α t -y), λtτ i ).
Step 3: Update the value of 1 τ i+1 using the Eq. VI.20.

Step 4: If

α i+1 -α i α i
≤ ε, go to step 5; Otherwise, return to step 2 and i = i + 1.

Step 5: y t+1 = y -Xα t+1 .

Step 6: If λt = λ, stop; Otherwise, return to step 1 and t = t + 1. Output:

α i E. l 1/2 -

norm regularization based sparse representation

Sparse representation with the l p -norm (0<p<1) regularization leads to a nonconvex, nonsmooth, and non-Lipschitz optimization problem and its general forms are described as problems III.13 and III.14. The l p -norm (0<p<1) regularization problem is always difficult to be efficiently addressed and it has also attracted wide interests from large numbers of research groups. However, the research group led by Zongben Xu summarizes the conclusion that the most impressive and representative algorithm of the l p -norm (0<p<1) regularization is sparse representation with the l 1/2 -norm regularization [START_REF] Zeng | Accelerated l 1/2 regularization based sar imaging via bcr and reduced newton skills[END_REF]. Moreover, they have proposed some effective methods to solve the l 1/2norm regularization problem [START_REF] Xu | l 1/2 regularization: A thresholding representation theory and a fast solver[END_REF][START_REF] Zeng | l 1/2 regularization: convergence of iterative half thresholding algorithm[END_REF].

In this section, a half proximal algorithm is introduced to solve the l 1/2 -norm regularization problem [START_REF] Xu | l 1/2 regularization: A thresholding representation theory and a fast solver[END_REF], which matches the iterative shrinkage thresholding algorithm for the l 1 -norm regularization discussed above and the iterative hard thresholding algorithm for the l 0 -norm regularization. Sparse representation with the l 1/2 -norm regularization is explicitly to solve the problem as follows:

α = arg min{F (α) = Xα -y 2 2 + λ α 1/2
1/2 } (VI.21) where the first-order optimality condition of F (α) on α can be formulated as

∇F (α) = X T (Xα -y) + λ 2 ∇( α 1/2 1/2 ) = 0 (VI.22)
which admits the following equation:

X T (y -Xα) = λ 2 ∇( α 1/2 1/2 ) (VI.23)
where ∇( α

1/2 1/2
) denotes the gradient of the regularization term α 1/2 1/2 . Subsequently, an equivalent transformation of Eq. VI.23 is made by multiplying a positive constant τ and adding a parameter α to both sides. That is,

α + τ X T (y -Xα) = α + τ λ 2 ∇( α 1/2 1/2 ) (VI.24)
To this end, the resolvent operator [START_REF] Xu | l 1/2 regularization: A thresholding representation theory and a fast solver[END_REF] is introduced to compute the resolvent solution of the right part of Eq. VI.24, and the resolvent operator is defined as

R λ, 1 2 (•) = I + λτ 2 ∇( • 1/2 1/2 ) -1 (VI.25)
which is very similar to the inverse function of the right part of Eq. VI.24. The resolvent operator is always satisfied no matter whether the resolvent solution of ∇( • 1/2 1/2 ) exists or not [START_REF] Xu | l 1/2 regularization: A thresholding representation theory and a fast solver[END_REF]. Applying the resolvent operator to solve problem VI.24

α = (I + λτ 2 ∇( • 1/2 1/2 )) -1 (α + τ X t (y -Xα)) = R λ,1/2 (α + τ X T (y -Xα)) (VI.26)
can be obtained which is well-defined. θ(α) = α + τ X T (y -Xα) is denoted and the resolvent operator can be explicitly expressed as:

R λ, 1 2 (x) = (f λ, 1 2 (x 1 ), f λ, 1 2 (x 2 ), • • • , f λ, 1 2 (x N )) T (VI.27)
where

f λ, 1 2 (x i ) = 2 3 x i (1 + cos( 2π 3 - 2 3 g λ (x i )), g λ (x i ) = arg cos( λ 8 ( |x i | 3 ) -3 2 ) (VI.28)
which have been demonstrated in the literature [START_REF] Xu | l 1/2 regularization: A thresholding representation theory and a fast solver[END_REF]. Thus the half proximal thresholding function for the l 1/2norm regularization is defined as below:

h λτ, 1 2 (x i ) = f λτ, 1 2 (x i ), if |x i | > 3 √ 54
4 (λτ )

2 3 0, otherwise (VI.29)
where the threshold

3 √ 54
4 (λτ )

2 3
has been conceived and demonstrated in the literature [START_REF] Xu | l 1/2 regularization: A thresholding representation theory and a fast solver[END_REF].

Therefore, if Eq. VI.29 is applied to Eq. VI.27, the half proximal thresholding function, instead of the resolvent operator, for the l 1/2 -norm regularization problem VI.25 can be explicitly reformulated as:

α = H λτ, 1 2 (θ(α)) (VI.30)
where the half proximal thresholding operator H [START_REF] Xu | l 1/2 regularization: A thresholding representation theory and a fast solver[END_REF] is deductively constituted by Eq. VI.29.

Up to now, the half proximal thresholding algorithm has been completely structured by Eq. VI.30. However, the options of the regularization parameter λ in Eq. VI.24 can seriously dominate the quality of the representation solution in problem VI. [START_REF] Zhang | Integrating globality and locality for robust representation based classification[END_REF], and the values of λ and τ can be specifically fixed by

τ = 1 -ε X 2 and λ = √ 96 9τ |[θ(α)] k+1 | 3 2 (VI.31)
where ε is a very small constant, which is very close to zero, the k denotes the limit of sparsity (i.e. k-sparsity), and

F (α) = Xα -y 2 2 + λ α 1/2 1/2
Input: Probe sample y, the measurement matrix X

Initialization: t = 0, ε = 0.01, τ = 1-ε X 2 . While not converged do Step 1: Compute θ(α t ) = α t + τ X T (y -Xα t ). Step 2: Compute λt = √ 96 9τ |[θ(α t )] k+1 | (θ(α t )).
Step 4: t = t + 1. End Output: α

F. Augmented Lagrange Multiplier based optimization strategy

The Lagrange multiplier is a widely used tool to eliminate the equality constrained problem and convert it to address the unconstrained problem with an appropriate penalty function.

Specifically, the sparse representation problem III.9 can be viewed as an equality constrained problem and the equivalent problem III.12 is an unconstrained problem, which augments the objective function of problem III.9 with a weighted constraint function. In this section, the augmented Lagrangian method (ALM) is introduced to solve the sparse representation problem III.9.

First, the augmented Lagrangian function of problem III.9 is conceived by introducing an additional equality constrained function, which is enforced on the Lagrange function in problem III.12. That is,

L(α, λ) = α 1 + λ 2 y-Xα 2 2 s.t. y-Xα = 0 (VI.32)
Then, a new optimization problem VI.32 with the form of the Lagrangain function is reformulated as

arg min L λ (α, z) = α 1 + λ 2 y -Xα 2 2 + z T (y -Xα) (VI.33
) where z ∈ R d is called the Lagrange multiplier vector or dual variable and L λ (α, z) is denoted as the augmented Lagrangian function of problem III.9. The optimization problem VI.33 is a joint optimization problem of the sparse representation coefficient α and the Lagrange multiplier vector z. Problem VI.33 is solved by optimizing α and z alternatively as follows:

α t+1 = arg minL λ (α, z t ) = arg min( α 1 + λ 2 y -Xα 2 2 + (z t ) T Xα) (VI.34) z t+1 = z t + λ(y -Xα t+1 ) (VI.35)
where problem VI.34 can be solved by exploiting the FISTA algorithm. Problem VI.34 is iteratively solved and the parameter z is updated using Eq. VI.35 until the termination condition is satisfied. Furthermore, if the method of employing ALM to solve problem VI.33 is denoted as the primal augmented Lagrangian method (PALM) [START_REF] Yang | Fast l 1 -minimization algorithms for robust face recognition[END_REF], the dual function of problem III.9 can also be addressed by the ALM algorithm, which is denoted as the dual augmented Lagrangian method (DALM) [START_REF] Yang | Fast l 1 -minimization algorithms for robust face recognition[END_REF]. Subsequently, the dual optimization problem III.9 is discussed and the ALM algorithm is utilized to solve it. First, consider the following equation:

α 1 = max θ ∞≤1 θ, α (VI.36)
which can be rewritten as

α 1 = max{ θ, α -I B 1 ∞ } or α 1 = sup{ θ, α -I B 1 ∞ } (VI.37)
where

B λ p = {x ∈ R N | x p ≤ λ} and I Ω (x) is a indicator function, which is defined as I Ω (x) = 0 , x ∈ Ω ∞ , x ∈ Ω .
Hence,

α 1 = max{ θ, α : θ ∈ B 1 ∞ } (VI.38)
Second, consider the Lagrange dual problem of problem III.9 and its dual function is [START_REF] Chartrand | Exact reconstruction of sparse signals via nonconvex minimization[END_REF] where λ ∈ R d is a Lagrangian multiplier. If the definition of conjugate function is applied to Eq. VI.37, it can be verified that the conjugate function of I B 1 ∞ (θ) is α 1 . Thus Eq. VI.39 can be equivalently reformulated as

g(λ) = inf α { α 1 +λ T (y-Xα)} = λ T y-sup α {λ T Xα-α 1 } (VI.
g(λ) = λ T y -I B 1 ∞ (X T λ) (VI.40)
The Lagrange dual problem, which is associated with the primal problem III.9, is an optimization problem:

max λ λ T y s.t. (X T λ) ∈ B 1 ∞ (VI.41)
Accordingly,

min λ,z -λ T y s.t. z -X T λ = 0, z ∈ B 1 ∞ (VI.42)
Then, the optimization problem VI.42 can be reconstructed as

arg min λ,z,µ L(λ, z, µ) = -λ T y -µ T (z -X T λ) + τ 2 z -X T λ 2 2 s.t. z ∈ B 1 ∞ (VI.43)
where µ ∈ R d is a Lagrangian multiplier and τ is a penalty parameter.

Finally, the dual optimization problem VI.43 is solved and a similar alternating minimization idea of PALM can also be applied to problem VI.43, that is,

z t+1 = arg min z∈B 1 ∞ L τ (λ t , z, µ t ) = arg min z∈B 1 ∞ {-µ T (z -X T λ t ) + τ 2 z -X T λ t 2 2 } = arg min z∈B 1 ∞ { τ 2 z -(X T λ t + 2 τ µ T ) 2 2 } = P B 1 ∞ (X T λ t + 1 τ µ T ) (VI.44)
where

P B 1 ∞ (u) is a projection, or called a proximal operator, onto B 1
∞ and it is also called group-wise soft-thresholding. For example, let

x = P B 1 ∞ (u), then the i-th component of solution x satisfies x i = sign(u i ) min{|u i |, 1} λ t+1 = arg min λ L τ (λ, z t+1 , µ t ) = arg min λ {-λ T y + (µ t ) T X T λ + τ 2 z t+1 -X T λ 2 2 } = Q(λ) (VI.45)
Take the derivative of Q(λ) with respect to λ and obtain

λ t+1 = (τ XX T ) -1 (τ Xz t+1 + y -Xµ t ) (VI.46) µ t+1 = µ t -τ (z t+1 -X T λ t+1 ) (VI.47)
The DALM for sparse representation with l 1 -norm regularization mainly exploits the augmented Lagrange method to address the dual optimization problem of problem III.9 and a proximal operator, the projection operator, is utilized to efficiently solve the subproblem. The algorithm of DALM is summarized in Algorithm 8. For more detailed description, please refer to the literature [START_REF] Yang | Fast l 1 -minimization algorithms for robust face recognition[END_REF]. Input: Probe sample y, the measurement matrix X, a small constant λ 0 .

Initialization: t = 0, ε = 0.01, τ = 1-ε X 2 , µ 0 = 0. While not converged do
Step 1: Apply the projection operator to compute

z t+1 = P B 1 ∞ (X T λ t + 1 τ µ T ).
Step 2: Update the value of λ t+1 = (τ XX T ) -1 (τ Xz t+1 +y-Xµ t ).

Step 3: Update the value of µ t+1 = µ t -τ (z t+1 -X T λ t+1 ).

Step 4:

t = t + 1. End While Output: α = µ[1 : N ]

G. Other proximity algorithm based optimization methods

The theoretical basis of the proximity algorithm is to first construct a proximal operator, and then utilize the proximal operator to solve the convex optimization problem. Massive proximity algorithms have followed up with improved techniques to improve the effectiveness and efficiency of proximity algorithm based optimization methods. For example, Elad et al. proposed an iterative method named parallel coordinate descent algorithm (PCDA) [START_REF] Elad | Coordinate and subspace optimization methods for linear least squares with non-quadratic regularization[END_REF] by introducing the elementwise optimization algorithm to solve the regularized linear least squares with non-quadratic regularization problem.

Inspired by belief propagation in graphical models, Donoho et al. developed a modified version of the iterative thresholding method, called approximate message passing (AMP) method [START_REF] Donoho | Messagepassing algorithms for compressed sensing[END_REF], to satisfy the requirement that the sparsity undersampling tradeoff of the new algorithm is equivalent to the corresponding convex optimization approach. Based on the development of the first-order method called Nesterov's smoothing framework in convex optimization, Becker et al. proposed a generalized Nesterov's algorithm (NESTA) [START_REF] Becker | Nesta: a fast and accurate first-order method for sparse recovery[END_REF] by employing the continuation-like scheme to accelerate the efficiency and flexibility. Subsequently, Becker et al. [START_REF] Becker | Templates for convex cone problems with applications to sparse signal recovery[END_REF] further constructed a general framework, i.e. templates for convex cone solvers (TFOCS), for solving massive certain types of compressed sensing reconstruction problems by employing the optimal first-order method to solve the smoothed dual problem of the equivalent conic formulation of the original optimization problem. Further detailed analyses and inference information related to proximity algorithms can be found in the literature [START_REF] Parikh | Proximal algorithms[END_REF][START_REF] Yang | Fast l 1 -minimization algorithms and an application in robust face recognition: A review[END_REF].

VII. HOMOTOPY ALGORITHM BASED SPARSE

REPRESENTATION

The concept of homotopy derives from topology and the homotopy technique is mainly applied to address a nonlinear system of equations problem. The homotopy method was originally proposed to solve the least square problem with the l 1 -penalty [START_REF] Osborne | A new approach to variable selection in least squares problems[END_REF]. The main idea of homotopy is to solve the original optimization problems by tracing a continuous parameterized path of solutions along with varying parameters. Having a highly intimate relationship with the conventional sparse representation method such as least angle regression (LAR) [START_REF] Efron | Least angle regression[END_REF], OMP [START_REF] Pati | Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition[END_REF] and polytope faces pursuit (PFP) [START_REF] Plumbley | Recovery of sparse representations by polytope faces pursuit[END_REF], the homotopy algorithm has been successfully employed to solve the l 1 -norm minimization problems. In contrast to LAR and OMP, the homotopy method is more favorable for sequentially updating the sparse solution by adding or removing elements from the active set. Some representative methods that exploit the homotopy-based strategy to solve the sparse representation problem with the l 1 -norm regularization are explicitly presented in the following parts of this section.

A. LASSO homotopy

Because of the significance of parameters in l 1 -norm minimization, the well-known LASSO homotopy algorithm is proposed to solve the LASSO problem in III.9 by tracing the whole homotopy solution path in a range of decreasing values of parameter λ. It is demonstrated that problem III.12 with an appropriate parameter value is equivalent to problem III.9 [START_REF] Donoho | Fast solution of l 1 -norm minimization problems when the solution may be sparse[END_REF]. Moreover, it is apparent that as we change λ from a very large value to zero, the solution of problem III.12 is converging to the solution of problem III.9 [START_REF] Donoho | Fast solution of l 1 -norm minimization problems when the solution may be sparse[END_REF]. The set of varying value λ conceives the solution path and any point on the solution path is the optimality condition of problem III.12. More specifically, the LASSO homotopy algorithm starts at an large initial value of parameter λ and terminates at a point of λ, which approximates zero, along the homotopy solution path so that the optimal solution converges to the solution of problem III.9. The fundamental of the homotopy algorithm is that the homotopy solution path is a piecewise linear path with a discrete number of operations while the value of the homotopy parameter changes, and the direction of each segment and the step size are absolutely determined by the sign sequence and the support of the solution on the corresponding segment, respectively [START_REF] Asif | Fast and accurate algorithms for re-weighted l 1 -norm minimization[END_REF].

Based on the basic ideas in a convex optimization problem, it is a necessary condition that the zero vector should be a solution of the subgradient of the objective function of problem III.12. Thus, we can obtain the subgradiential of the objective function with respect to α for any given value of λ, that is,

∂L ∂α = -X T (y -Xα) + λ∂ α 1 (VII.1)
where the first term r = X T (y -Xα) is called the vector of residual correlations, and ∂ α 1 is the subgradient obtained by

∂ α 1 = θ ∈ R N θ i = sgn(α i ), α i = 0 θ i ∈ [-1, 1],
α i = 0 Let Λ and u denote the support of α and the sign sequence of α on its support Λ, respectively. X Λ denotes that the indices of all the samples in X Λ are all included in the support set Λ. If we analyze the KKT optimality condition for problem III.12, we can obtain the following two equivalent conditions of problem VII.1, i.e.

X Λ (y -Xα) = λu; X T Λ c (y -Xα) ∞ ≤ λ (VII.2)
where Λ c denotes the complementary set of the set Λ. Thus, the optimality conditions in VII.2 can be divided into N constraints and the homotopy algorithm maintains both of the conditions along the optimal homotopy solution path for any λ ≥ 0. As we decrease the value of λ to λ -τ , for a small value of τ , the following conditions should be satisfied

X T Λ (y -Xα) + τ X T Λ Xδ = (λ -τ )u (a) p + τ q ∞ ≤ λ -τ (b) (VII.3)
where p = X T (y -Xα), q = X T Xδ and δ is the update direction.

Generally, the homotopy algorithm is implemented iteratively and it follows the homotopy solution path by updating the support set by decreasing parameter λ from a large value to the desired value. The support set of the solution will be updated and changed only at a critical point of λ, where either an existing nonzero element shrinks to zero or a new nonzero element will be added into the support set. The two most important parameters are the step size τ and the update direction δ. At the l-th stage (if (X T Λ X Λ ) -1 exists), the homotopy algorithm first calculates the update direction, which can be obtained by solving

X T Λ X Λ δ l = u (VII.4)
Thus, the solution of problem VII.4 can be written as

δ l = (X T Λ X Λ ) -1 u, on Λ 0, otherwise (VII.5)
Subsequently, the homotopy algorithm computes the step size τ to the next critical point by tracing the homotopy solution path. i.e. the homotopy algorithm moves along the update direction until one of constraints in VII.3 is not satisfied. At this critical point, a new nonzero element must enter the support Λ, or one of the nonzero elements in α will be shrink to zero, i.e. this element must be removed from the support set Λ. Two typical cases may lead to a new critical point, where either condition of VII.3 is violated. The minimum step size which leads to a critical point can be easily obtained by computing τ * l = min(τ + l , τ - l ), and τ + l and τ - l are computed by

τ + l = min i∈Λ c λ -p i 1 -x T i X Λ δ l , λ + p i 1 + x T i X Λ δ l + (VII.6) τ - l = min i∈Λ -α i l δ i l + (VII.7)
where p i = x T i (yx i α i l ) and min(•) + denotes that the minimum is operated over only positive arguments. τ + l is the minimum step size that turns an inactive element at the index i + in to an active element, i.e. the index i + should be added into the support set. τ - l is the minimum step size that shrinks the value of a nonzero active element to zero at the index i - and the index i -should be removed from the support set. The solution is updated by α l+1 = α l + τ * l δ, and its support and sign sequence are renewed correspondingly.

The homotopy algorithm iteratively computes the step size and the update direction, and updates the homotopy solution and its corresponding support and sign sequence till the condition p ∞ = 0 is satisfied so that the solution of problem III.9 is reached. The principal steps of the LASSO homotopy algorithm have been summarized in Algorithm 9. For further description and analyses, please refer to the literature [START_REF] Donoho | Fast solution of l 1 -norm minimization problems when the solution may be sparse[END_REF][START_REF] Asif | Fast and accurate algorithms for re-weighted l 1 -norm minimization[END_REF].

Algorithm 9. Lasso homotopy algorithm

Task: To addrss the Lasso problem: α = arg minα y -Xα 2 2 s.t. α 1 ≤ ε Input: Probe sample y, measurement matrix X. Initialization: l = 1, initial solution α l and its support set Λ l . Repeat:

Step 1: Compute update direction δ l by using Eq. (VII.5).

Step 2: Compute τ + l and τ - l by using Eq. (VII.6) and Eq. (VII.7).

Step 3: Compute the optimal minimum step size τ * l by using

τ * l = min{τ + l , τ - l }.
Step 4: Update the solution α l+1 by using α l+1 = α l + τ * l δ l .

Step 5: Update the support set:

If τ + l == τ - l then Remove the i -from the support set, i.e. Λ l+1 = Λ l \i -. else Add the i + into the support set, i.e.

Λ l+1 = Λ l i + End if Step 6: l = l + 1. Until X T (y -Xα) ∞ = 0 Output: α l+1

B. BPDN homotopy

Problem III.11, which is called basis pursuit denoising (BPDN) in signal processing, is the unconstrained Lagrangian function of the LASSO problem III.9, which is an unconstrained problem. The BPDN homotopy algorithm is very similar to the LASSO homotopy algorithm. If we consider the KKT optimality condition for problem III.12, the following condition should be satisfied for the solution α

X T (y -Xα) ∞ ≤ λ (VII.8)
As for any given value of λ and the support set Λ, the following two conditions also need to be satisfied

X T Λ (y -Xα) = λu; X T Λ c (y -Xα) ∞ ≤ λ (VII.9)
The BPDN homotopy algorithm directly computes the homotopy solution by

α = (X T Λ X Λ ) -1 (X T Λ y -λu), on Λ 0, otherwise (VII.10)
which is somewhat similar to the soft-thresholding operator.

The value of the homotopy parameter λ is initialized with a large value, which satisfies λ 0 > X T y ∞ . As the value of the homotopy parameter λ decreases, the BPDN homotopy algorithm traces the solution in the direction of (X T Λ X Λ ) -1 u till the critical point is obtained. Each critical point is reached when either an inactive element is transferred into an active element, i.e. its corresponding index should be added into the support set, or an nonzero active element value in α shrinks to zero, i.e. its corresponding index should be removed from the support set. Thus, at each critical point, only one element is updated, i.e. one element being either removed from or added into the active set, and each operation is very computationally efficient. The algorithm is terminated when the value of the homotopy parameter is lower than its desired value. The BPDN homotopy algorithm has been summarized in Algorithm 10. For further detail description and analyses, please refer to the literature [START_REF] Efron | Least angle regression[END_REF].

Algorithm 10. BPDN homotopy algorithm

Task: To address the Lasso problem: α = arg minα y -Xα 2 2 + λ α 1 Input: Probe sample y, measurement matrix X. Initialization: l = 0, initial solution α 0 and its support set Λ 0 , a large value λ 0 , step size τ , tolerance ε. Repeat:

Step 1: Compute update direction δ l+1 by using

δ l+1 = (X T Λ X Λ ) -1 u l .
Step 2: Update the solution α l+1 by using Eq. (VII.10).

Step 3: Update the support set and the sign sequence set.

Step 6:

λ l+1 = λ l -τ , l = l + 1. Until λ ≤ ε Output: α l+1

C. Iterative Reweighting l 1 -norm minimization via homotopy

Based on the homotopy algorithm, Asif and Romberg [START_REF] Asif | Fast and accurate algorithms for re-weighted l 1 -norm minimization[END_REF] presented a enhanced sparse representation objective function, a weighted l 1 -norm minimization, and then provided two fast and accurate solutions, i.e. the iterative reweighting algorithm, which updated the weights with a new ones, and the adaptive reweighting algorithm, which adaptively selected the weights in each iteration. Here the iterative reweighting algorithm via homotopy is introduced. The objective function of the weighted l 1 -norm minimization is formulated as

argmin 1 2 Xα -y 2 2 + W α 1 (VII.11)
where

W = diag[w 1 , w 2 , • • • , w N ]
is the weight of the l 1 -norm and also is a diagonal matrix. For more explicit description, problem VII.11 can be rewritten as

argmin 1 2 Xα -y 2 2 + N i=1 w i |α i | (VII.12)
A common method [START_REF] Efron | Least angle regression[END_REF][START_REF] Figueiredo | Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems[END_REF] to update the weight W is achieved by exploiting the solution of problem VII.12, i.e. α, at the previous iteration, and for the i-th element of the weight w i is updated by

w i = λ |α i | + σ (VII.13)
where parameters λ and σ are both small constants. In order to efficiently update the solution of problem (7-9), the homotopy algorithm introduces a new weight of the l 1 -norm and a new homotopy based reweighting minimization problem is reformulated as

argmin 1 2 Xα -y 2 2 + N i=1 ((1 -σ) ŵi + σ ŵi )|α i | (VII.14)
where ŵi denotes the new obtained weight by the homotopy algorithm, parameter τ is denoted as the homotopy parameter varying from 0 to 1. Apparently, problem VII.14 can be evolved to problem VII.12 with the increasing value of the homotopy parameter by tracing the homotopy solution path. Similar to the LASSO homotopy algorithm, problem VII.14 is also piecewise linear along the homotopy path, and for any value of σ, the following conditions should be satisfied

x T i (Xα -y) = -((1 -σ)w i + σ ŵi )u i f or i ∈ Λ (a) |x T i (Xα -y)| < (1 -σ)w i + σ ŵi f or i ∈ Λ c (b) (VII.15
) where x i is the i-th column of the measurement X, w i and ŵi are the given weight and new obtained weight, respectively. Moreover, for the optimal step size σ, when the homotopy parameter changes from σ to σ + τ in the update direction δ, the following optimality conditions also should be satisfied

X T Λ (Xα -y) + τ X T Λ Xδ = -((1 -σ)W + σ Ŵ )u + τ (W -Ŵ )u (a) |p -τ q| ≤ r + τ s (b) (VII.16)
where u is the sign sequence of α on its support Λ, p i = x T i (Xαy), q i = x T i Xδ, r i = (1 -σ)w i + σ ŵi and s i = ŵi -w i . Thus, at the l-th stage (if (X T i X i ) -1 exists), the update direction of the homotopy algorithm can be computed by

δ l = (X T Λ X Λ ) -1 (W -Ŵ )u, on Λ 0, otherwise (VII.17)
The step size which can lead to a critical point can be computed by τ * l = min(τ + l , τ - l ), and τ + l and τ - l are computed by

τ + l = min i∈Λ c r i -p i q i -s i , -r i -p i q i + s i + (VII.18) τ - l = min i∈Λ -α i l δ i l + (VII.19)
where τ + l is the minimum step size so that the index i + should be added into the support set and τ - l is the minimum step size that shrinks the value of a nonzero active element to zero at the index i -. The solution and homotopy parameter are updated by α l+1 = α l + τ * l δ, and σ l+1 = σ l + τ * l , respectively. The homotopy algorithm updates its support set and sign sequence accordingly until the new critical point of the homotopy parameter σ l+1 = 1. The main steps of this algorithm are summarized in Algorithm 11 and more information can be found in literature [START_REF] Asif | Fast and accurate algorithms for re-weighted l 1 -norm minimization[END_REF].

D. Other homotopy algorithms for sparse representation

The general principle of the homotopy method is to reach the optimal solution along with the homotopy solution path by evolving the homotopy parameter from a known initial value to the final expected value. There are extensive hotomopy algorithms, which are related to the sparse representation with the l 1 -norm regularization. Malioutov et al. first exploited the homotopy method to choose a suitable parameter for l 1 -norm regularization with a noisy term in an underdetermined system and employed the homotopy continuation-based method to solve BPDN for sparse signal processing [START_REF] Malioutov | Homotopy continuation for sparse signal representation[END_REF]. Garrigues and Ghaoui [START_REF] Garrigues | An homotopy algorithm for the lasso with online observations[END_REF] proposed a modified homotopy algorithm to solve the Lasso problem with online observations by optimizing the Algorithm 11. Iterative reweighting homotopy algorithm for weighted l 1norm minimization Task: To addrss the weighted l 1 -norm minimization: α = arg min 1 2 Xαy 2 2 + W α 1 Input: Probe sample y, measurement matrix X. Initialization: l = 1, initial solution α l and its support set Λ l , σ 1 = 0. Repeat:

Step 1: Compute update direction δ l by using Eq. (VII.17).

Step 2: Compute p, q, r and s by using Eq. (VII.16).

Step 2: Compute τ + l and τ - l by using Eq. (VII.18) and Eq. (VII.19).

Step 3: Compute the step size τ * l by using τ * l = min{τ + l , τ - l }.

Step 4: Update the solution α l+1 by using α l+1 = α l + τ * l δ l .

Step 5: Update the support set:

If τ + l == τ - l then Shrink the value to zero at the index i -and remove i -, i.e. Λ l+1 = Λ l \i -. else Add the i + into the support set, i.e. Λ l+1 = Λ l i + End if

Step 6: σ l+1 = σ l + τ l and l = l + 1. Until σ l+1 = 1 Output: α l+1 homotopy parameter from the current solution to the solution after obtaining the next new data point. Efron et al. [START_REF] Efron | Least angle regression[END_REF] proposed a basic pursuit denoising (BPDN) homotopy algorithm, which shrinked the parameter to a final value with series of efficient optimization steps. Similar to BPDN homotopy, Asif [START_REF] Asif | Primal dual pursuit: A homotopy based algorithm for the dantzig selector[END_REF] presented a homotopy algorithm for the Dantzing selector (DS) under the consideration of primal and dual solution. Asif and Romberg [START_REF] Asif | Dynamic updating for l 1 minimization[END_REF] proposed a framework of dynamic updating solutions for solving l 1 -norm minimization programs based on homotopy algorithm and demonstrated its effectiveness in addressing the decoding issue. More recent literature related to homotopy algorithms can be found in the streaming recovery framework [START_REF]Sparse recovery of streaming signals using l 1homotopy[END_REF] and a summary [START_REF] Asif | Dynamic compressive sensing: Sparse recovery algorithms for streaming signals and video[END_REF].

VIII. THE APPLICATIONS OF THE SPARSE REPRESENTATION METHOD

Sparse representation technique has been successfully implemented to numerous applications, especially in the fields of computer vision, image processing, pattern recognition and machine learning. More specifically, sparse representation has also been successfully applied to extensive real-world applications, such as image denoising, deblurring, inpainting, super-resolution, restoration, quality assessment, classification, segmentation, signal processing, object tracking, texture classification, image retrieval, bioinformatics, biometrics and other artificial intelligence systems. Moreover, dictionary learning is one of the most typical representative examples of sparse representation for realizing the sparse representation of a signal. In this paper, we only concentrate on the three applications of sparse representation, i.e. sparse representation in dictionary learning, image processing, image classification and visual tracking.

A. Sparse representation in dictionary learning

The history of modeling dictionary could be traced back to 1960s, such as the fast Fourier transform (FFT) [START_REF] Cooley | An algorithm for the machine calculation of complex fourier series[END_REF]. An over-complete dictionary that can lead to sparse representation is usually achieved by exploiting pre-specified set of transformation functions, i.e. transform domain method [START_REF] Mallat | A wavelet tour of signal processing: the sparse way[END_REF], or is devised based on learning, i.e. dictionary learning methods [START_REF] Rubinstein | Dictionaries for sparse representation modeling[END_REF]. Both of the transform domain and dictionary learning based methods transform image samples into other domains and the similarity of transformation coefficients are exploited [START_REF] Shao | From heuristic optimization to dictionary learning: a review and comprehensive comparison of image denoising algorithms[END_REF]. The difference between them is that the transform domain methods usually utilize a group of fixed transformation functions to represent the image samples, whereas the dictionary learning methods apply sparse representations on a over-complete dictionary with redundant information. Moreover, exploiting the pre-specified transform matrix in transform domain methods is attractive because of its fast and simplicity. Specifically, the transform domain methods usually represent the image patches by using the orthonormal basis such as over-complete wavelets transform [START_REF] Simoncelli | Noise removal via bayesian wavelet coring[END_REF], super-wavelet transform [START_REF] He | Automatic fault feature extraction of mechanical anomaly on induction motor bearing using ensemble super-wavelet transform[END_REF], bandelets [START_REF] Pennec | Sparse geometric image representations with bandelets[END_REF], curvelets transform [START_REF] Starck | The curvelet transform for image denoising[END_REF], contourlets transform [START_REF] Do | The contourlet transform: an efficient directional multiresolution image representa-tion[END_REF] and steerable wavelet filters [START_REF] Simoncelli | Shiftable multiscale transforms[END_REF]. However, the dictionary learning methods exploiting sparse representation have the potential capabilities of outperforming the pre-determined dictionaries based on transformation functions. Thus, in this subsection we only focus on the modern over-complete dictionary learning methods.

An effective dictionary can lead to excellent reconstruction results and satisfactory applications, and the choice of dictionary is also significant to the success of sparse representation technique. Different tasks have different dictionary learning rules. For example, image classification requires that the dictionary contains discriminative information such that the solution of sparse representation possesses the capability of distinctiveness. The purpose of dictionary learning is motivated from sparse representation and aims to learn a faithful and effective dictionary to largely approximate or simulate the specific data. In this section, some parameters are defined as matrix

Y = [y 1 , y 2 , • • • , y N ], matrix X = [x 1 , x 2 , • • • , x t ] T , and dictionary D = [d 1 , d 2 , • • • , d M ].
From the notations of the literature [START_REF] Cheng | Sparse representation and learning in visual recognition: Theory and applications[END_REF][START_REF] Shi | A nonconvex relaxation approach to sparse dictionary learning[END_REF], the framework of dictionary learning can be generally formulated as an optimization problem arg min

D∈Ω,xi 1 N N i=1 ( 1 2 y i -Dx i 2 2 + λP (x i )) (VIII.1)
where

Ω = {D = [d 1 , d 2 , • • • , d M ] : d T i d i = 1, i = 1, 2, • • • , M } (M
here may not be equal to N ), N denotes the number of the known data set (eg. training samples in image classification), y i is the i-th sample vector from a known set, D is the learned dictionary and x i is the sparsity vector. P (x i ) and λ are the penalty or regularization term and a tuning parameter, respectively. The regularization term of problem VIII.1 controls the degree of sparsity. That is, different kinds of the regularization terms can immensely dominate the dictionary learning results.

One spontaneous idea of defining the penalty term P (x i ) is to introduce the l 0 -norm regularization, which leads to the sparsest solution of problem VIII.1. As a result, the theory of sparse representation can be applied to dictionary learning. The most representative dictionary learning based on the l 0 -norm penalty is the K-SVD algorithm [START_REF] Bruckstein | From sparse solutions of systems of equations to sparse modeling of signals and images[END_REF], which is widely used in image denoising. Because the solution of l 0 -norm regularization is usually a NP-hard problem, utilizing a convex relaxation strategy to replace l 0 -norm regularization is an advisable choice for dictionary learning. As a convex relaxation method of l 0 -norm regularization, the l 1 -norm regularization based dictionary learning has been proposed in large numbers of dictionary learning schemes. In the stage of convex relaxation methods, there are three optimal forms for updating a dictionary: the one by one atom updating method, group atoms updating method, and all atoms updating method [START_REF] Shi | A nonconvex relaxation approach to sparse dictionary learning[END_REF]. Furthermore, because of over-penalization in l 1norm regularization, non-convex relaxation strategies also have been employed to address dictionary learning problems. For example, Fan and Li proposed a smoothly clipped absolution deviation (SCAD) penalty [START_REF] Fan | Variable selection via nonconcave penalized likelihood and its oracle properties[END_REF], which employed an iterative approximate Newton-Raphson method for penalizing least sequences and exploited the penalized likelihood approaches for variable selection in linear regression models. Zhang introduced and studied the non-convex minimax concave (MC) family [START_REF] Zhang | Nearly unbiased variable selection under minimax concave penalty[END_REF] of non-convex piecewise quadratic penalties to make unbiased variable selection for the estimation of regression coefficients, which was demonstrated its effectiveness by employing an oracle inequality. Friedman proposed to use the logarithmic penalty for a model selection [START_REF] Friedman | Fast sparse regression and classification[END_REF] and used it to solve the minimization problems with non-convex regularization terms. From the viewpoint of updating strategy, most of the dictionary learning methods always iteratively update the sparse approximation or representation solution and the dictionary alternatively, and more dictionary learning theoretical results and analyses can be found in the literature [START_REF] Rubinstein | Dictionaries for sparse representation modeling[END_REF][START_REF] Tosic | Dictionary learning[END_REF].

Recently, varieties of dictionary learning methods have been proposed and researchers have attempted to exploit different strategies for implementing dictionary learning tasks based on sparse representation. There are several means to categorize these dictionary learning algorithms into various groups. For example, dictionary learning methods can be divided into three groups in the context of different norms utilized in the penalty term, that is, l 0 -norm regularization based methods, convex relaxation methods and non-convex relaxation methods [START_REF] Bao | l 0 norm based dictionary learning by proximal methods with global convergence[END_REF]. Moreover, dictionary learning algorithms can also be divided into three other categories in the presence of different structures. The first category is dictionary learning under the probabilistic framework such as maximum likelihood methods [START_REF] Olshausen | Sparse coding with an overcomplete basis set: A strategy employed by v1?[END_REF], the method of optimal directions (MOD) [START_REF] Engan | Multi-frame compression: Theory and design[END_REF], and the maximum a posteriori probability method [START_REF] Kreutz-Delgado | Dictionary learning algorithms for sparse representation[END_REF]. The second category is clustering based dictionary learning approaches such as KSVD [START_REF] Aharon | k-svd: An algorithm for designing overcomplete dictionaries for sparse representation[END_REF], which can be viewed as a generalization of K-means. The third category is dictionary learning with certain structures, which are grouped into two significative aspects, i.e. directly modeling the relationship between each atom and structuring the corrections between each atom with purposive sparsity penalty functions. There are two typical models for these kinds of dictionary learning algorithms, sparse and shift-invariant representation of dictionary learning and structure sparse regularization based dictionary learning, such as hierarchical sparse dictionary learning [START_REF] Jenatton | Proximal methods for sparse hierarchical dictionary learning[END_REF] and group or block sparse dictionary learning [START_REF] Bengio | Group sparse coding[END_REF]. Recently, some researchers [START_REF] Cheng | Sparse representation and learning in visual recognition: Theory and applications[END_REF] categorized the latest methods of dictionary learning into four groups, online dictionary learning [START_REF] Zhao | Online detection of unusual events in videos via dynamic sparse coding[END_REF], joint dictionary learning [START_REF] Zhang | Robust visual tracking via multi-task sparse learning[END_REF], discriminative dictionary learning [START_REF] Zhang | Discriminative k-svd for dictionary learning in face recognition[END_REF], and supervised dictionary learning [START_REF] Yang | Tag localization with spatial correlations and joint group sparsity[END_REF].

Although there are extensive strategies to divide the available sparse representation based dictionary learning methods into different categories, the strategy used here is to categorize the current prevailing dictionary learning approaches into two main classes: supervised dictionary learning and unsupervised dictionary learning, and then specific representative algorithms are explicitly introduced.

1) Unsupervised dictionary learning: From the viewpoint of theoretical basis, the main difference of unsupervised and supervised dictionary learning relies on whether the class label is exploited in the process of learning for obtaining the dictionary. Unsupervised dictionary learning methods have been widely implemented to solve image processing problems, such as image compression, and feature coding of image representation [START_REF] Bryt | Compression of facial images using the k-svd algorithm[END_REF][START_REF] Wang | Locality-constrained linear coding for image classification[END_REF].

(1) KSVD for unsupervised dictionary learning One of the most representative unsupervised dictionary learning algorithms is the KSVD method [START_REF] Aharon | k-svd: An algorithm for designing overcomplete dictionaries for sparse representation[END_REF], which is a modification or an extension of method of directions (MOD) algorithm. The objective function of KSVD is

arg min D,X { Y -DX 2 F } s.t. x i 0 ≤ k, i = 1, 2, • • • , N (VIII.
2) where Y ∈ R d×N is the matrix composed of all the known examples, D ∈ R d×N is the learned dictionary, X ∈ R N ×N is the matrix of coefficients, k is the limit of sparsity and x i denotes the i-th row vector of the matrix X. Problem VIII.2 is a joint optimization problem with respect to D and X, and the natural method is to alternatively optimize the D and X iteratively.

Algorithm 12. The K-SVD algorithm for dictionary learning Task: Learning a dictionary D:

arg min D,X Y -DX 2 F s.t. x i 0 ≤ k, i = 1, 2, • • • , N Input: The matrix composed of given samples Y = [y 1 , y 2 , • • • , ym].
Initialization: Set the initial dictionary D to the l 2 -norm unit matrix, i = 1.

While not converged do

Step 1: For each given example y i , employing the classical sparse representation with l 0 -norm regularization to solve problem VIII.3 for further estimating X i ,set l = 1. While l is not equal to k do

Step 2: Compute the overall representation residual E l = Yj =l d j x T j .

Step 3: Extract the column items of E l which corresponds to the nonzero elements of x T l and obtain E P l .

Step 4: SVD decomposes E P l into E P l = U ΛV T . Step 5: Update d l to the first column of U and update corresponding coefficients in x T l by Λ(1, 1) times the first column of V .

Step 6: l = l + 1.

End While

Step 7: i = i + 1.

End While

Output: dictionary D More specifically, when fixing dictionary D, problem VIII.2 is converted to

arg min X Y -DX 2 F s.t. x i 0 ≤ k, i = 1, 2, • • • , N (VIII.
3) which is called sparse coding and k is the limit of sparsity. Then, its subproblem is considered as follows:

arg min xi y i -Dx i 2 2 s.t. x i 0 ≤ k, i = 1, 2, • • • , N
where we can iteratively resort to the classical sparse representation with l 0 -norm regularization such as MP and OMP, for estimating x i . When fixing X, problem VIII.3 becomes a simple regression model for obtaining D, that is

D = arg min D Y -DX 2 F (VIII.4)
where D = Y X † = Y X T (XX T ) -1 and the method is called MOD. Considering that the computational complexity of the inverse problem in solving problem VIII.4 is O(n 3 ), it is favorable, for further improvement, to update dictionary D by fixing the other variables. The strategy of the KSVD algorithm rewrites the problem VIII.4 into

D = arg min D Y -DX 2 F = arg min D Y - N j=1 d j x T j 2 F = arg min D (Y - j =l d j x T j ) -d l x T l 2 F (VIII.5)
where x j is the j-th row vector of the matrix X. First the overall representation residual E l = Yj =l d j x T j is computed, and then d l and x l are updated. In order to maintain the sparsity of x T l in this step, only the nonzero elements of x T l should be preserved and only the nonzero items of E l should be reserved, i.e. E P l , from d l x T l . Then, SVD decomposes E P l into E P l = U ΛV T , and then updates dictionary d l . The specific KSVD algorithm for dictionary learning is summarized to Algorithm 12 and more information can be found in the literature [START_REF] Aharon | k-svd: An algorithm for designing overcomplete dictionaries for sparse representation[END_REF].

(2) Locality constrained linear coding for unsupervised dictionary learning

The locality constrained linear coding (LLC) algorithm [START_REF] Wang | Locality-constrained linear coding for image classification[END_REF] is an efficient local coordinate linear coding method, which projects each descriptor into a local constraint system to obtain an effective codebook or dictionary. It has been demonstrated that the property of locality is more essential than sparsity, because the locality must lead to sparsity but not vice-versa, that is, a necessary condition of sparsity is locality, but not the reverse [START_REF] Wang | Locality-constrained linear coding for image classification[END_REF].

Assume that

Y = [y 1 , y 2 , • • • , y N ] ∈ R d×N
y i -Dx i 2 2 + µ b ⊙ x i 2 2 s.t. 1 T x i = 1, i = 1, 2, • • • , N (VIII.6)
where µ is a small constant as a regularization parameter for adjusting the weighting decay speed, ⊙ is the operator of the element-wise multiplication, x i is the code for y i , 1 ∈ R N ×1 is defined as a vector with all elements as 1 and vector b is the locality adaptor, which is, more specifically, set as

x i = xi / 1 T xi (VIII.9)
where the operator a\b denotes a -1 b, and

C i = (D T - 1y T i )(D T -1y T i )
T is the covariance matrix with respect to y i . This is called the LLC algorithm. Furthermore, the incremental codebook optimization algorithm has also been proposed to obtain a more effective and optimal codebook, and the objective function is reformulated as

arg min xi,D N i=1 y i -Dx i 2 2 + µ b ⊙ x i 2 2 s.t. 1 T x i = 1, ∀i; d j 2 2 ≤ 1, ∀j (VIII.10)
Actually, the problem VIII.10 is a process of feature extraction and the property of 'locality' is achieved by constructing a local coordinate system by exploiting the local bases for each descriptor, and the local bases in the algorithm are simply obtained by using the K nearest neighbors of y i . The incremental codebook optimization algorithm in problem VIII.10 is a joint optimization problem with respect to D and x i , and it can be solved by iteratively optimizing one when fixing the other alternatively. The main steps of the incremental codebook optimization algorithm are summarized in Algorithm 13 and more information can be found in the literature [START_REF] Wang | Locality-constrained linear coding for image classification[END_REF].

(3) Other unsupervised dictionary learning methods A large number of different unsupervised dictionary learning methods have been proposed. The KSVD algorithm and LLC algorithm are only two typical unsupervised dictionary learning algorithms based on sparse representation. Additionally, Jenatton et al. [START_REF] Jenatton | Proximal methods for sparse hierarchical dictionary learning[END_REF] proposed a tree-structured dictionary learning problem, which exploited tree-structured sparse regularization to model the relationship between each atom and defined a proximal operator to solve the primaldual problem. Zhou et al. [START_REF] Zhou | Nonparametric bayesian dictionary learning for analysis of noisy and incomplete images[END_REF] developed a nonparametric Bayesian dictionary learning algorithm, which utilized hierarchical Bayesian to model parameters and employed the truncated beta-Bernoulli process to learn the dictionary. Ramirez and Shapiro [START_REF] Ramirez | An mdl framework for sparse coding and dictionary learning[END_REF] employed minimum description length to

i -D i x i 2 2 s.t. 1 T x i = 1.
Step 7: Update dictionary D using a classical gradient descent method with respect to problem VIII.6. Step 8: i = i + 1.

End While

Output: dictionary D model an effective framework of sparse representation and dictionary learning, and this framework could conveniently incorporate prior information into the process of sparse representation and dictionary learning. Some other unsupervised dictionary learning algorithms also have been validated. Mairal et al. proposed an online dictionary learning [START_REF] Mairal | Online learning for matrix factorization and sparse coding[END_REF] algorithm based on stochastic approximations, which treated the dictionary learning problem as the optimization of a smooth convex problem over a convex set and employed an iterative online algorithm at each step to solve the subproblems. Yang and Zhang proposed a sparse variation dictionary learning (SVDL) algorithm [START_REF] Yang | Sparse variation dictionary learning for face recognition with a single sample per person[END_REF] for face recognition with a single training sample, in which a joint learning framework of adaptive projection and a sparse variation dictionary with sparse bases were simultaneously constructed from the gallery image set to the generic image set. Shi et al. proposed a minimax concave penalty based sparse dictionary learning (MCPSDL) [START_REF] Shi | A nonconvex relaxation approach to sparse dictionary learning[END_REF] algorithm, which employed a non-convex relaxation online scheme, i.e. a minimax concave penalty, instead of using regular convex relaxation approaches as approximation of l 0norm penalty in sparse representation problem, and designed a coordinate descend algorithm to optimize it. Bao et al. proposed a dictionary learning by proximal algorithm (DLPM) [START_REF] Bao | l 0 norm based dictionary learning by proximal methods with global convergence[END_REF], which provided an efficient alternating proximal algorithm for solving the l 0 -norm minimization based dictionary learning problem and demonstrated its global convergence property.

2) Supervised dictionary learning: Unsupervised dictionary learning just considers that the examples can be sparsely represented by the learned dictionary and leaves out the label information of the examples. Thus, unsupervised dictionary learning can perform very well in data reconstruction, such as image denoising and image compressing, but is not beneficial to perform classification. On the contrary, supervised dictionary learning embeds the class label into the process of sparse representation and dictionary learning so that this leads to the learned dictionary with discriminative information for effective classification.

(1) Discriminative KSVD for dictionary learning Discriminative KSVD (DKSVD) [START_REF] Zhang | Discriminative k-svd for dictionary learning in face recognition[END_REF] was designed to solve image classification problems. Considering the priorities of supervised learning theory in classification, DKSVD incorporates the dictionary learning with discriminative information and classifier parameters into the objective function and employs the KSVD algorithm to obtain the global optimal solution for all parameters. The objective function of the DKSVD algorithm is formulated as

D, C, X = arg min D,C,X Y -DX 2 F + µ H -CX 2 F +η C 2 F s.t. x i 0 ≤ k (VIII.11)
where Y is the given input samples, D is the learned dictionary, X is the coefficient term, H is the matrix composed of label information corresponding to Y , C is the parameter term for classifier, and η and µ are the weights. With a view to the framework of KSVD, problem VIII.11 can be rewritten as

D, C, X = arg min D,C,X Y √ µH - D √ µC X 2 F +η C 2 F s.t. x i 0 ≤ k (VIII.12)
In consideration of the KSVD algorithm, each column of the dictionary will be normalized to l 2 -norm unit vector and D √ µC will also be normalized, and then the penalty term C 2 F will be dropped out and problem VIII.12 will be reformulated as

Z, X = arg min Z,X W -ZX 2 F s.t. x i 0 ≤ k (VIII.13) where W = Y √ µH , Z = D √ µC
and apparently the formulation VIII.13 is the same as the framework of KSVD [START_REF] Aharon | k-svd: An algorithm for designing overcomplete dictionaries for sparse representation[END_REF] in Eq. VIII.2 and it can be efficiently solved by the KSVD algorithm. More specifically, the DKSVD algorithm contains two main phases: the training phase and classification phase. For the training phase, Y is the matrix composed of the training samples and the objective is to learn a discriminative dictionary D and the classifier parameter C. DKSVD updates Z column by column and for each column vector z i , DKSVD employs the KSVD algorithm to obtain z i and its corresponding weight. Then, the DKSVD algorithm normalizes the dictionary D and classifier parameter C by where the label is the final predicted label vector. The class label of y i is the determined class index of label.

D ′ = [d ′ 1 , d ′ 2 , • • • , d ′ M ] = [ d1 d1 , d2 d2 , • • • , dM dM ] C ′ = [c ′ 1 , c ′ 2 , • • • , c ′ M ] = [ c1 d1 , c2 d2 , • • • , cM dM ] x ′ i = x i × d i (VIII.
The main highlight of DKSVD is that it employs the framework of KSVD to simultaneously learn a discriminative dictionary and classifier parameter, and then utilizes the efficient OMP algorithm to obtain a sparse representation solution and finally integrate the sparse solution and learned classifier for ultimate effective classification.

(2) Label consistent KSVD for discriminative dictionary learning Because of the classification term, a competent dictionary can lead to effectively classification results. The original sparse representation for face recognition [START_REF] Wright | Robust face recognition via sparse representation[END_REF] regards the raw data as the dictionary, and then reports its promising classification results. In this section, a label consistent KSVD (LC-KSVD) [START_REF] Jiang | Learning a discriminative dictionary for sparse coding via label consistent k-svd[END_REF][START_REF] Jiang | Label consistent k-svd: learning a discriminative dictionary for recognition[END_REF] is introduced to learn an effective discriminative dictionary for image classification. As an extension of D-KSVD, LC-KSVD exploits the supervised information to learn the dictionary and integrates the process of constructing the dictionary and optimal linear classifier into a mixed reconstructive and discriminative objective function, and then jointly obtains the learned dictionary and an effective classifier. The objective function of LC-KSVD is formulated as

D, A, C, X = arg min D,A,C,X Y -DX 2 F + µ L -AX 2 F +η H -CX 2 F s.t. x i 0 ≤ k (VIII.17)
where the first term denotes the reconstruction error, the second term denotes the discriminative sparse-code error, and the final term denotes the classification error. Y is the matrix composed of all the input data, D is the learned dictionary, X is the sparse code term, µ and η are the weights of the corresponding contribution items, A is a linear transformation matrix, H is the matrix composed of label information corresponding to Y , C is the parameter term for classifier and L is a joint label matrix for labels of Y and D. For example, providing that Y = [y 1 . . . where

T =   Y √ µL √ ηH   , Z =   D √ µA √ ηC   .
The learning process of the LC-KSVD algorithm, as is DKSVD, can be separated into two sections, the training term and the classification term. In the training section, since problem VIII.18 completely satisfies the framework of KSVD, the KSVD algorithm is applied to update Z atom by atom and compute X. Thus Z and X can be obtained. Then, the LC-KSVD algorithm normalizes dictionary D, transform matrix A, and the classifier parameter C by

D ′ = [d ′ 1 , d ′ 2 , • • • , d ′ M ] = [ d1 d1 , d2 d2 , • • • , dM dM ] A ′ = [a ′ 1 , a ′ 2 , • • • , a ′ M ] = [ a1 d1 , a2 d2 , • • • , aM dM ] C ′ = [c ′ 1 , c ′ 2 , • • • , c ′ M ] = [ c1 d1 , c2 d2 , • • • , cM dM ]
(VIII.19) In the classification section, Y is the matrix composed of the test samples. On the basis of the obtained dictionary D ′ , the sparse coefficient xi can be obtained for each test sample y i by exploiting the OMP algorithm, which is to solve

xi = arg min y i -D ′ x ′ i 2 2 s.t. x ′ i 0 ≤ k (VIII.

20) The final classification is based on a simple linear predictive function

l = arg max f {f = C ′ × xi } (VIII.21)
where f is the final predicting label vector and the test sample y i is classified as a member of the l-th class.

The main contribution of LC-KSVD is to jointly incorporate the discriminative sparse coding term and classifier parameter term into the objective function for learning a discriminative dictionary and classifier parameter. The LC-KSVD demonstrates that the obtained solution, compared to other methods, can prevent learning a suboptimal or local optimal solution in the process of learning a dictionary [START_REF] Jiang | Learning a discriminative dictionary for sparse coding via label consistent k-svd[END_REF].

(3) Fisher discrimination dictionary learning for sparse representation Fisher discrimination dictionary learning (FDDL) [START_REF] Yang | Fisher discrimination dictionary learning for sparse representation[END_REF] incorporates the supervised information (class label information) and the Fisher discrimination message into the objective function for learning a structured discriminative dictionary, which is used for pattern classification. The general model of FDDL is formulated as

J(D, X) = arg min D,X {f (Y, D, X) + µ X 1 + ηg(X)} (VIII.22)
where Y is the matrix composed of input data, D is the learned dictionary, X is the sparse solution, and µ and η are two constants for tradeoff contributions. The first component is the discriminative fidelity term, the second component is the sparse regularization term, and the third component is the discriminative coefficient term, such as Fisher discrimination criterion in Eq. (VIII.23).

Considering the importance of the supervised information, i.e. label information, in classification, FDDL respectively updates the dictionary and computes the sparse representation solution class by class. Assume that Y i denotes the matrix of i-th class of input data, vector X i denotes the sparse representation coefficient of the learned dictionary D over Y i and X i j denotes the matrix composed of the sparse representation solutions, which correspond to the j-th class coefficients from X i . D i is denoted as the learned dictionary corresponding to the i-th class. Thus, the objective function of FDDL is

J(D, X) = arg min D,X ( c i=1 f (Y i , D, X i ) + µ X 1 + η(tr(S W (X) -S B (X)) + λ X 2 F )) (VIII.23)
where

f (Y i , D, X i ) = Y i -DX i 2 F + Y i -D i X i i 2 F + j =i D j X i j 2
F and S W (X) and S B (X) are the within-class scatter of X and between-class scatter of X, respectively. c is the number of the classes. To solve problem VIII.23, a natural idea of optimization is to alternatively optimize D and X class by class, and then the process of optimization is briefly introduced.

When fixing D, problem VIII.23 can be solved by computing X i class by class, and its sub-problem is formulated as

J(X i ) = arg min X i f (Y i , D, X i ) + µ X i 1 + ηg(X i ) (VIII.24) where g(X i ) = X i -M i 2 F - c t=1 M t -M 2 F + λ X i 2 F
and M j and M denote the mean matrices corresponding to the j-th class of X i and X i , respectively. Problem VIII.23 can be solved by the iterative projection method in the literature [START_REF] Rosasco | Iterative projection methods for structured sparsity regularization[END_REF].

When fixing α, problem VIII.23 can be rewritten as

J(D) = arg min D ( Y i -D i X i - j =i D j X j 2 F + Y i -D i X i i 2 F + j =i D i X i j 2 F ) (VIII.25)
where X i here denotes the sparse representation of Y over D i . In this section, each column of the learned dictionary is normalized to a unit vector with l 2 -norm. The optimization of problem VIII.25 computes the dictionary class by class and it can be solved by exploiting the algorithm in the literature [START_REF] Yang | Metaface learning for sparse representation based face recogni-tion[END_REF].

The main contribution of the FDDL algorithm lies in combining the Fisher discrimination criterion into the process of dictionary learning. The discriminative power comes from the method of constructing the discriminative dictionary using the function f in problem VIII.22 and simultaneously formulates the discriminative sparse representation coefficients by exploiting the function g in problem VIII.22. (4) Other supervised dictionary learning for sparse representation Unlike unsupervised dictionary learning, supervised dictionary learning emphasizes the significance of the class label information and incorporates it into the learning process to enforce the discrimination of the learned dictionary. Recently, massive supervised dictionary learning algorithms have been proposed. For example, Yang et al. [START_REF] Yang | Metaface learning for sparse representation based face recogni-tion[END_REF] presented a metaface dictionary learning method, which is motivated by 'metagenes' in gene expression data analysis. Rodriguez and Sapiro [START_REF] Ramirez | Classification and clustering via dictionary learning with structured incoherence and shared features[END_REF] produced a discriminative non-parametric dictionary learning (DNDL) framework based on the OMP algorithm for image classification. Kong et al. [START_REF] Kong | A dictionary learning approach for classification: separating the particularity and the commonality[END_REF] introduced a learned dictionary with commonalty and particularity, called DL-COPAR, which integrated an incoherence penalty term into the objective function for obtaining the class-specific sub-dictionary. Gao et al. [START_REF] Gao | Learning categoryspecific dictionary and shared dictionary for finegrained image categorization[END_REF] learned a hybrid dictionary, i.e. category-specific dictionary and shared dictionary, which incorporated a crossdictionary incoherence penalty and self-dictionary incoherence penalty into the objective function for learning a discriminative dictionary. Jafari and Plumbley [START_REF] Jafari | Fast dictionary learning for sparse representations of speech signals[END_REF] presented a greedy adaptive dictionary learning method, which updated the learned dictionary with a minimum sparsity index. Some other supervised dictionary learning methods are also competent in image classification, such as supervised dictionary learning in [START_REF] Mairal | Supervised dictionary learning[END_REF]. Zhou et al. [START_REF] Zhou | Learning inter-related visual dictionary for object recognition[END_REF] developed a joint dictionary learning algorithm for object categorization, which jointly learned a commonly shared dictionary and multiply category-specific dictionaries for correlated object classes and incorporated the Fisher discriminant fidelity term into the process of dictionary learning. Ramirez et al. proposed a method of dictionary learning with structured incoherence (DLSI) [START_REF] Ramirez | Classification and clustering via dictionary learning with structured incoherence and shared features[END_REF], which unified the dictionary learning and sparse decomposition into a sparse dictionary learning framework for image classification and data clustering. Ma et al. presented a discriminative lowrank dictionary learning for sparse representation (DLRD SR) [START_REF] Ma | Sparse representation for face recognition based on discriminative low-rank dictionary learning[END_REF], in which the sparsity and the low-rank properties were integrated into one dictionary learning scheme where subdictionary with discriminative power was required to be lowrank. Lu et al. developed a simultaneous feature and dictionary learning [START_REF] Lu | Simultaneous feature and dictionary learning for image set based face recognition[END_REF] method for face recognition, which jointly learned the feature projection matrix for subspace learning and the discriminative structured dictionary. Yang et al. introduced a latent dictionary learning (LDL) [START_REF] Yang | Latent dictionary learning for sparse representation based classification[END_REF] method for sparse representation based image classification, which simultaneously learned a discriminative dictionary and a latent representation model based on the correlations between label information and dictionary atoms. Jiang et al. presented a submodular dictionary learning (SDL) [START_REF] Jiang | Submodular dictionary learning for sparse coding[END_REF] method, which integrated the entropy rate of a random walk on a graph and a discriminative term into a unified objective function and devised a greedybased approach to optimize it. Si et al. developed a support vector guided dictionary learning (SVGDL) [START_REF] Cai | Support vector guided dictionary learning[END_REF] method, which constructed a discriminative term by using adaptively weighted summation of the squared distances for all pairwise of the sparse representation solutions.

B. Sparse representation in image processing

Recently, sparse representation methods have been extensively applied to numerous real-world applications [START_REF] Qin | A new sparse featurebased patch for dense correspondence[END_REF][START_REF] He | Sparse representation for blind image quality assessment[END_REF]. The techniques of sparse representation have been gradually ex-tended and introduced to image processing, such as superresolution image processing, image denoising and image restoration.

First, the general framework of image processing using sparse representation especially for image reconstruction should be introduced:

Step 1: Partition the degraded image into overlapped patches or blocks.

Step 2: Construct a dictionary, denoted as D, and assume that the following sparse representation formulation should be satisfied for each patch or block x of the image: α = arg min α p s.t.

x -HDα 2 2 ≤ ε where H is a degradation matrix and 0 ≤ p ≤ 1.

Step 3: Reconstruct each patch or block by exploiting x = D α.

Step 4: Put the reconstructed patch to the image at the corresponding location and average each overlapped patches to make the reconstructed image more consistent and natural.

Step 5: Repeat step 1 to 4 several times till a termination condition is satisfied.

The following part of this subsection is to explicitly introduce some image processing techniques using sparse representation.

The main task of super-resolution image processing is to extract the high super-resolution image from its low resolution counterpart and this challenging problem has attracted much attention. The most representative work was proposed to exploit the sparse representation theory to generate a superresolution (SRSR) image from a single low-resolution image in literature [START_REF] Yang | Image super-resolution as sparse representation of raw image patches[END_REF].

SRSR is mainly performed on two compact learned dictionaries D l and D h , which are denoted as dictionaries of low-resolution image patches and its corresponding highresolution image patches, respectively. D l is directly employed to recover high-resolution images from dictionary D h . Let X and Y denote the high-resolution and its corresponding lowresolution images, respectively. x and y are a high-resolution image patch and its corresponding low-resolution image patch, respectively. Thus, x = P y and P is the projection matrix. Moreover, if the low resolution image Y is produced by downsampling and blurring from the high resolution image X, the following reconstruction constraint should be satisfied

Y = SBX (VIII.26)
where S and B are a downsampling operator and a blurring filter, respectively. However, the solution of problem VIII.26 is ill-posed because infinite solutions can be achieved for a given low-resolution input image Y . To this end, SRSR [START_REF] Yang | Image super-resolution as sparse representation of raw image patches[END_REF] provides a prior knowledge assumption, which is formulated as

x = D h α s.t. α 0 ≤ k (VIII.27)
where k is a small constant. This assumption gives a prior knowledge condition that any image patch x can be approximately represented by a linear combination of a few training samples from dictionary D h . As presented in Subsection III-B, problem VIII.27 is an NP-hard problem and sparse representation with l 1 -norm regularization is introduced. If the desired representation solution α is sufficiently sparse, problem VIII.27 can be converted into the following problem:

arg min α 1 s.t. x -D h α 2 2 ≤ ε (VIII.28) or arg min x -D h α 2 2 + λ α 1 (VIII.29)
where ε is a small constant and λ is the Lagrange multiplier.

The solution of problem VIII.28 can be achieved by two main phases, i.e. local model based sparse representation (LMBSR) and enhanced global reconstruction constraint. The first phase of SRSR, i.e. LMBSR, is operated on each image patch, and for each low-resolution image patch y, the following equation is satisfied

arg min F y -F D l α 2 2 + λ α 1 (VIII.30)
where F is a feature extraction operator. One-pass algorithm similar to that of [START_REF] Freeman | Example-based super-resolution[END_REF] is introduced to enhance the compatibility between adjacent patches. Furthermore, a modified optimization problem is proposed to guarantee that the superresolution reconstruction coincides with the previously obtained adjacent high-resolution patches, and the problem is reformulated as [START_REF] Boyd | Convex optimization[END_REF] where v is the previously obtained high-resolution image on the overlap region, and L refers to the region of overlap between the current patch and previously obtained highresolution image. Thus problem VIII.31 can be rewritten as

arg min α 1 s.t. F y -F D l α 2 2 ≤ ε 1 ; v -LD h α 2 2 ≤ ε 2 (VIII.
arg min ŷ -Dα 2 2 + λ α 1 (VIII.32)
where ŷ = F y v and D = F D l LD h . Problem VIII.32 can be simply solved by previously introduced solution of the sparse representation with l 1 -norm minimization. Assume that the optimal solution of problem VIII.32, i.e. α * , is achieved, the high-resolution patch can be easily reconstructed by x = D h α * . The second phase of SRSR enforces the global reconstruction constraint to eliminate possible unconformity or noise from the first phase and make the obtained image more consistent and compatible. Suppose that the high-resolution image obtained by the first phase is denoted as matrix X 0 , we project X 0 onto the solution space of the reconstruction constraint VIII.26 and the problem is formulated as follows

X * = arg min X -X 0 2 2 s.t. Y = SBX (VIII.33)
Problem VIII.33 can be solved by the back-projection method in [START_REF] Irani | Motion analysis for image enhancement: Resolution, occlusion, and transparency[END_REF] and the obtained image X * is regarded as the final optimal high-resolution image. The entire super-resolution via sparse representation is summarized in algorithm 14 and more information can be found in the literature [START_REF] Yang | Image super-resolution as sparse representation of raw image patches[END_REF]. Furthermore, extensive other methods based on sparse representation have been proposed to solve the super-resolution image processing problem. For example, Yang et al. presented a modified version called joint dictionary learning via sparse representation (JDLSR) [START_REF] Yang | Image super-resolution via sparse representation[END_REF], which jointly learned For each overlapped 3 × 3 patches y of Y using one-pass algorithm, from left to right and top to bottom

Step 1: Compute optimal sparse representation coefficients α * in problem (VIII.32).

Step 2: Compute the high-resolution patch by x = D h α * .

Step 3: Put the patch x into a high-resolution image X 0 in corresponding location.

End

Step 4: Compute the final super-resolution image X * in problem (VIII.33). Output: X * two dictionaries that enforced the similarity of sparse representation for low-resolution and high-resolution images. Tang et al. [START_REF] Tang | Greedy regression in sparse coding space for single-image superresolution[END_REF] first explicitly analyzed the rationales of the sparse representation theory in performing the super-resolution task, and proposed to exploit the L 2 -Boosting strategy to learn coupled dictionaries, which were employed to construct sparse coding space. Zhang et al. [START_REF] Zhang | Image super-resolution via dual-dictionary learning and sparse representation[END_REF] presented an image super-resolution reconstruction scheme by employing the dualdictionary learning and sparse representation method for image super-resolution reconstruction and Gao et al. [START_REF] Gao | Image superresolution with sparse neighbor embedding[END_REF] proposed a sparse neighbor embedding method, which incorporated the sparse neighbor search and HoG clustering method into the process of image super-resolution reconstruction. Fernandez-Granda and Candes [START_REF] Fernandez-Granda | Superresolution via transform-invariant group-sparse regularization[END_REF] designed a transform-invariant group sparse regularizer by implementing a data-driven nonparametric regularizers with learned domain transform on group sparse representation for high image super-resolution. Lu et al. [START_REF] Lu | Geometry constrained sparse coding for single image superresolution[END_REF] proposed a geometry constrained sparse representation method for single image super-resolution by jointly obtaining an optimal sparse solution and learning a discriminative and reconstructive dictionary. Dong et al. [START_REF] Dong | Superresolution with nonlocal regularized sparse representation[END_REF] proposed to harness an adaptive sparse optimization with nonlocal regularization based on adaptive principal component analysis enhanced by nonlocal similar patch grouping and nonlocal self-similarity quadratic constraint to solve the image high super-resolution problem. Dong et al. [START_REF] Dong | Image deblurring and super-resolution by adaptive sparse domain selection and adaptive regularization[END_REF] proposed to integrate an adaptive sparse domain selection and an adaptive regularization based on piecewise autoregressive models into the sparse representations framework for single image superresolution reconstruction. Mallat and Yu [START_REF] Mallat | Super-resolution with sparse mixing estimators[END_REF] proposed a sparse mixing estimator for image super-resolution, which introduced an adaptive estimator models by combining a group of linear inverse estimators based on different prior knowledge for sparse representation.

Noise in an image is unavoidable in the process of image acquisition. The need for sparse representation may arise when noise exists in image data. In such a case, the image with noise may lead to missing information or distortion such that this results in a decrease of the precision and accuracy of image processing. Eliminating such noise is greatly beneficial to many applications. The main goal of image denoising is to distinguish the actual signal and noise signal so that we can remove the noise and reconstruct the genuine image. In the presence of image sparsity and redundancy representation [START_REF] Elad | On the role of sparse and redundant representations in image processing[END_REF][START_REF] Elad | Sparse and redundant representations: from theory to applications in signal and image processing[END_REF], sparse representation for image denoising first extracts the sparse image components, which are regarded as useful information, and then abandons the representation residual, which is treated as the image noise term, and finally reconstructs the image exploiting the pre-obtained sparse components, i.e. noise-free image. Extensive research articles for image denoising based on sparse representation have been published. For example, Donoho [START_REF] Bruckstein | From sparse solutions of systems of equations to sparse modeling of signals and images[END_REF][START_REF] Donoho | Fast solution of l 1 -norm minimization problems when the solution may be sparse[END_REF][START_REF] Donoho | De-noising by soft-thresholding[END_REF] first discovered the connection between the compressed sensing and image denoising. Subsequently, the most representative work of using sparse representation to make image denoising was proposed in literature [START_REF] Elad | Image denoising via sparse and redundant representations over learned dictionaries[END_REF], in which a global sparse representation model over learned dictionaries (SRMLD) was used for image denoising. The following prior assumption should be satisfied: every image block of image x, denoted as z, can be sparsely represented over a dictionary D, i.e. the solution of the following problem is sufficiently sparse: If we take the above prior knowledge into full consideration, the objective function of SRMLD based on Bayesian treatment is formulated as

arg min D,αi,x δ x -y 2 2 + M i=1 Dα i -P i x 2 2 + M i=1 λ i α i 0
(VIII.36) where x is the finally denoised image, y the measured image with white and additive Gaussian white noise, P i is a projection operator that extracts the i-th block from image x, M is the number of the overlapping blocks, D is the learned dictionary, α i is the coefficients vector, δ is the weight of the first term and λ i is the Lagrange multiplier. The first term in VIII.36 is the log-likelihood global constraint such that the obtained noise-free image x is sufficiently similar to the original image y. The second and third terms are the prior knowledge of the Bayesian treatment, which is presented in problem VIII. [START_REF] Yang | Beyond sparsity: The role of l 1 -optimizer in pattern classification[END_REF] Step 1: For each image patch P i x, employ the KSVD algorithm to update the values of sparse representation solution α i and corresponding dictionary D.

Step 2: t = t + 1 End While

Step 3: Compute the value of x by using Eq.(VIII.38). Output: denoised image x Moreover, extensive modified sparse representation based image denoising algorithms have been proposed. For example, Dabov et al. [START_REF] Dabov | Image denoising by sparse 3-d transform-domain col-laborative filtering[END_REF] proposed an enhanced sparse representation with a block-matching 3-D (BM3D) transform-domain filter based on self-similarities and an enhanced sparse representation by clustering similar 2-D image patches into 3-D data spaces and an iterative collaborative filtering procedure for image denoising. Mariral et al. [START_REF] Mairal | Sparse representation for color image restoration[END_REF] proposed the use of extending the KSVD-based grayscale algorithm and a generalized weighted average algorithm for color image denoising. Protter and Elad [START_REF] Protter | Image sequence denoising via sparse and redundant representations[END_REF] extended the techniques of sparse and redundant representations for image sequence denoising by exploiting spatio-temporal atoms, dictionary propagation over time and dictionary learning. Dong et al. [START_REF] Dong | Sparsity-based image denoising via dictionary learning and structural clustering[END_REF] designed a clustering based sparse representation algorithm, which was formulated by a double-header sparse optimization problem built upon dictionary learning and structural clustering. Recently, Jiang et al. [START_REF] Jiang | Mixed noise removal by weighted encoding with sparse nonlocal regularization[END_REF] proposed a variational encoding framework with a weighted sparse nonlocal constraint, which was constructed by integrating image sparsity prior and nonlocal self-similarity prior into a unified regularization term to overcome the mixed noise removal problem. Gu et al. [START_REF] Gu | Weighted nuclear norm minimization with application to image denoising[END_REF] studied a weighted nuclear norm minimization (WNNM) method with F -norm fidelity under different weighting rules optimized by non-local self-similarity for image denoising. Ji et al. [START_REF] Ji | Robust video denoising using low rank matrix completion[END_REF] proposed a patch-based video denoising algorithm by stacking similar patches in both spatial and temporal domain to formulate a low-rank matrix problem with the nuclear norm. Cheng et al. [START_REF] Cheng | Image denoising via group sparse representation over learned dictionary[END_REF] proposed an impressive image denoising method based on an extension of the KSVD algorithm via group sparse representation.

The primary purpose of image restoration is to recover the original image from the degraded or blurred image. The sparse representation theory has been extensively applied to image restoration. For example, Bioucas-Dias and Figueirdo [START_REF] Bioucas-Dias | A new twist: two-step iterative shrinkage/thresholding algorithms for image restoration[END_REF] introduced a two-step iterative shrinkage/thresholding (TwIST) algorithm for image restoration, which is more efficient and can be viewed as an extension of the IST method. Mairal et al. [START_REF] Mairal | Learning multiscale sparse representations for image and video restoration[END_REF] presented a multiscale sparse image representation framework based on the KSVD dictionary learning algorithm and shift-invariant sparsity prior knowledge for restoration of color images and video image sequence. Recently, Mairal et al. [START_REF] Mairal | Non-local sparse models for image restoration[END_REF] proposed a learned simultaneous sparse coding (LSSC) model, which integrated sparse dictionary learning and nonlocal self-similarities of natural images into a unified framework for image restoration. Zoran and Weiss [START_REF] Zoran | From learning models of natural image patches to whole image restoration[END_REF] proposed an expected patch log likelihood (EPLL) optimization model, which restored the image from patch to the whole image based on the learned prior knowledge of any patch acquired by Maximum A-Posteriori estimation instead of using simple patch averaging. Bao et al. [START_REF] Bao | Fast sparsity-based orthogonal dictionary learning for image restoration[END_REF] proposed a fast orthogonal dictionary learning algorithm, in which a sparse image representation based orthogonal dictionary was learned in image restoration. Zhang et al. [START_REF] Zhang | Group-based sparse representation for image restoration[END_REF] proposed a groupbased sparse representation, which combined characteristics from local sparsity and nonlocal self-similarity of natural images to the domain of the group. Dong et al. [START_REF] Dong | Centralized sparse representation for image restoration[END_REF][START_REF] Dong | Nonlocally centralized sparse representation for image restoration[END_REF] proposed a centralized sparse representation (CSR) model, which combined the local and nonlocal sparsity and redundancy properties for variational problem optimization by introducing a concept of sparse coding noise term.

Here we mainly introduce a recently proposed simple but effective image restoration algorithm CSR model [START_REF] Dong | Centralized sparse representation for image restoration[END_REF]. For a degraded image y, the problem of image restoration can be formulated as

y = Hx + v (VIII.41)
where H is a degradation operator, x is the original highquality image and v is the Gaussian white noise. Suppose that the following two sparse optimization problems are satisfied

α x = arg min α 1 s.t. x -Dα 2 2 ≤ ε (VIII.42) α y = arg min α 1 s.t. x -HDα 2 2 ≤ ε (VIII.43)
where y and x respectively denote the degraded image and original high-quality image, and ε is a small constant. A new concept called sparse coding noise (SCN) is defined

v α = α y -α x (VIII.44)
Given a dictionary D, minimizing SCN can make the image better reconstructed and improve the quality of the image restoration because x * = xx = Dα y -Dα x = Dv α .

Thus, the objective function is reformulated as

α y = arg min α y -HDα 2 2 + λ α 1 + µ α -α x 1
(VIII.45) where λ and µ are both constants. However, the value of α x is difficult to directly evaluate. Because many nonlocal similar patches are associated with the given image patch i, clustering these patches via block matching is advisable and the sparse code of searching similar patch l to patch i in cluster Ω i , denoted by α il , can be computed. Moreover, the unbiased estimation of α x , denoted by E[α x ], empirically can be approximate to α x under some prior knowledge [START_REF] Dong | Centralized sparse representation for image restoration[END_REF], and then SCN algorithm employs the nonlocal means estimation method [START_REF] Buades | A non-local algorithm for image denoising[END_REF] to evaluate the unbiased estimation of α x , that is, using the weighted average of all α il to approach E[α x ], i.e.

θ i = l∈Ωi w il α il (VIII.46)
where

w il = exp -x i -x il 2
2 /h /N , x i = Dα i , x il = Dα il , N is a normalization parameter and h is a constant. Thus, the objective function VIII.45 can be rewritten as

α y = arg min α y -HDα 2 2 + λ α 1 + µ M i=1 α i -θ i 1
(VIII.47) where M is the number of the separated patches. In the j-th iteration, the solution of problem VIII.47 is iteratively performed by

α j+1 y = arg min α y -HDα 2 2 + λ α 1 + µ M i=1 α i -θ j i 1
(VIII.48) It is obvious that problem VIII.47 can be optimized by the augmented Lagrange multiplier method [START_REF] Nedic | Convex analysis and optimization[END_REF] or the iterative shrinkage algorithm in [START_REF] Daubechies | An iterative thresholding algorithm for linear inverse problems with a sparsity constraint[END_REF]. According to the maximum average posterior principle and the distribution of the sparse coefficients, the regularization parameter λ and constant µ can be adaptively determined by λ = 2

√ 2ρ 2 σi and µ = 2 √ 2ρ 2
ηi , where ρ, σ i and η i are the standard deviations of the additive Gaussian noise, α i and the SCN signal, respectively. Moreover, in the process of image patches clustering for each given image patch, a local PCA dictionary is learned and employed to code each patch within its corresponding cluster. The main procedures of the CSR algorithm are summarized in Algorithm 16 and readers may refer to literature [START_REF] Dong | Centralized sparse representation for image restoration[END_REF] for more details.

C. Sparse representation in image classification and visual tracking

In addition to these effective applications in image processing, several other fields for sparse representation have been proposed and extensively studied in image classification and visual tracking. Since Wright et al. [START_REF] Wright | Robust face recognition via sparse representation[END_REF] proposed to employ sparse representation to perform robust face recognition, more and more researchers have been applying the sparse representation theory to the fields of computer vision and pattern recognition, especially in image classification and object tracking. Step 5: For a given θ t+1 i , compute the sparse representation solution, i.e. α t+1 y , in problem (VIII.48) by using the extended iterative shrinkage algorithm in literature [START_REF] Daubechies | An iterative thresholding algorithm for linear inverse problems with a sparsity constraint[END_REF].

Step 6: t = t + 1 End While Output: Restored image x = Dα t+1 y Experimental results have suggested that the sparse representation based classification method can somewhat overcome the challenging issues from illumination changes, random pixel corruption, large block occlusion or disguise.

As face recognition is a representative component of pattern recognition and computer vision applications, the applications of sparse representation in face recognition can sufficiently reveal the potential nature of sparse representation. The most representative sparse representation for face recognition has been presented in literature [START_REF] Lu | Manifold regularized sparse nmf for hyperspectral unmixing[END_REF] and the general scheme of sparse representation based classification method is summarized in Algorithm 17. Suppose that there are n training samples, X = [x 1 , x 2 , • • • , x n ] from c classes. Let X i denote the samples from the i-th class and the testing sample is y.

Algorithm 17. The scheme of sparse representation based classification method

Step 1: Normalize all the samples to have unit l 2 -norm.

Step 2: Exploit the linear combination of all the training samples to represent the test sample and the following l 1 -norm minimization problem is satisfied α * = arg min α 1 s.t. y -Xα 2 2 ≤ ε.

Step 3: Compute the representation residual for each class r

i = y -X i α * i 2 2
where α * i here denotes the representation coefficients vector associated with the i-th class.

Step 4: Output the identity of the test sample y by judging label(y) = arg min i (r i ).

Numerous sparse representation based classification methods have been proposed to improve the robustness, effectiveness and efficiency of face recognition. For example, Xu et al. [START_REF] Xu | A two-phase test sample sparse representation method for use with face recognition[END_REF] proposed a two-phase sparse representation based classification method, which exploited the l 2 -norm regularization rather than the l 1 -norm regularization to perform a coarse to fine sparse representation based classification, which was very efficient in comparison with the conventional l 1norm regularization based sparse representation. Deng et al. [START_REF] Deng | Extended src: Undersampled face recognition via intraclass variant dictionary[END_REF] proposed an extended sparse representation method (ESRM) for improving the robustness of SRC by eliminating the variations in face recognition, such as disguise, occlusion, expression and illumination. Deng et al. [START_REF]In defense of sparsity based face recognition[END_REF] also proposed a framework of superposed sparse representation based classification, which emphasized the prototype and vari-ation components from uncontrolled images. He et al. [START_REF] He | Maximum correntropy criterion for robust face recognition[END_REF] proposed utilizing the maximum correntropy criterion named CESR embedding non-negative constraint and half-quadratic optimization to present a robust face recognition algorithm. Yang et al. [START_REF] Yang | Robust sparse coding for face recognition[END_REF] developed a new robust sparse coding (RSC) algorithm, which first obtained a sparsity-constrained regression model based on maximum likelihood estimation and exploited an iteratively reweighted regularized robust coding algorithm to solve the pre-proposed model. Some other sparse representation based image classification methods also have been developed. For example, Yang et al. [START_REF] Yang | Linear spatial pyramid matching using sparse coding for image classification[END_REF] introduced an extension of the spatial pyramid matching (SPM) algorithm called ScSPM, which incorporated SIFT sparse representation into the spatial pyramid matching algorithm. Subsequently, Gao et al. [START_REF] Gao | Kernel sparse representation for image classification and face recognition[END_REF] developed a kernel sparse representation with the SPM algorithm called KSRSPM, and then proposed another version of an improvement of the SPM called LSc-SPM [START_REF] Gao | Local features are not lonely-laplacian sparse coding for image classification[END_REF], which integrated the Laplacian matrix with local features into the objective function of the sparse representation method. Kulkarni and Li [START_REF] Kulkarni | Discriminative affine sparse codes for image classification[END_REF] proposed a discriminative affine sparse codes method (DASC) on a learned affineinvariant feature dictionary from input images and exploited the AdaBoost-based classifier to perform image classification. Zhang et al. [START_REF] Zhang | Image classification by non-negative sparse coding, low-rank and sparse decomposition[END_REF] proposed integrating the non-negative sparse coding, low-rank and sparse matrix decomposition (LR-Sc + SPM) method, which exploited non-negative sparse coding and SPM for achieving local features representation and employed low-rank and sparse matrix decomposition for sparse representation, for image classification. Recently, Zhang et al. [START_REF] Zhang | Low-rank sparse coding for image classification[END_REF] presented a low-rank sparse representation (LRSR) learning method, which preserved the sparsity and spatial consistency in each procedure of feature representation and jointly exploited local features from the same spatial proximal regions for image classification. Zhang et al. [START_REF] Zhang | Learning structured low-rank representations for image classification[END_REF] developed a structured low-rank sparse representation (SLRSR) method for image classification, which constructed a discriminative dictionary in training terms and exploited low-rank matrix reconstruction for obtaining discriminative representations. Tao et al. [START_REF] Tao | Rank preserving sparse learning for kinect based scene classification[END_REF] proposed a novel dimension reduction method based on the framework of rank preserving sparse learning, and then exploited the projected samples to make effective Kinect-based scene classification. Zhang et al. [START_REF] Zhang | Discriminative tensor sparse coding for image classification[END_REF] proposed a discriminative tensor sparse coding (RTSC) method for robust image classification. Recently, low-rank based sparse representation became a popular topic such as non-negative low-rank and sparse graph [START_REF] Zhuang | Constructing a non-negative low rank and sparse graph with data-adaptive features[END_REF]. Some sparse representation methods in face recognition can be found in a review [START_REF] Yang | Fast l 1 -minimization algorithms and an application in robust face recognition: A review[END_REF] and other more image classification methods can be found in a more recent review [START_REF] Rigamonti | On the relevance of sparsity for image classification[END_REF].

Mei et al. employed the idea of sparse representation to visual tracking [START_REF] Mei | Robust visual tracking using l 1 minimization[END_REF] and vehicle classification [START_REF]Robust visual tracking and vehicle classification via sparse representation[END_REF], which introduced nonnegative sparse constraints and dynamic template updating strategy. It, in the context of the particle filter framework, exploited the sparse technique to guarantee that each target candidate could be sparsely represented using the linear combinations of fewest targets and particle templates. It also demonstrated that sparse representation can be propagated to address object tracking problems. Extensive sparse representation methods have been proposed to address the visual tracking problem. In order to design an accelerated algorithm for l 1 tracker, Li et al. [START_REF] Li | Real-time visual tracking using compressive sensing[END_REF] proposed two realtime compressive sensing visual tracking algorithms based on sparse representation, which adopted dimension reduction and the OMP algorithm to improve the efficiency of recovery procedure in tracking, and also developed a modified version of fusing background templates into the tracking procedure for robust object tracking. Zhang et al. [START_REF] Zhang | Robust object tracking based on sparse representation[END_REF] directly treated object tracking as a pattern recognition problem by regarding all the targets as training samples, and then employed the sparse representation classification method to do effective object tracking. Zhang et al. [START_REF] Zhang | Robust visual tracking via multi-task sparse learning[END_REF] employed the concept of sparse representation based on a particle filter framework to construct a multi-task sparse learning method denoted as multi-task tracking for robust visual tracking. Additionally, because of the discriminative sparse representation between the target and the background, Jia et al. [START_REF] Jia | Visual tracking via adaptive structural local sparse appearance model[END_REF] conceived a structural local sparse appearance model for robust object tracking by integrating the partial and spatial information from the target based on an alignment-pooling algorithm. Liu et al. [START_REF] Liu | Robust and fast collaborative tracking with two stage sparse optimization[END_REF] proposed constructing a two-stage sparse optimization based online visual tracking method, which jointly minimized the objective reconstruction error and maximized the discriminative capability by choosing distinguishable features. Liu et al. [START_REF] Liu | Robust tracking using local sparse appearance model and kselection[END_REF] introduced a local sparse appearance model (SPT) with a static sparse dictionary learned from k-selection and dynamic updated basis distribution to eliminate potential drifting problems in the process of visual tracking. Bao et al. [START_REF] Bao | Real time robust l 1 tracker using accelerated proximal gradient approach[END_REF] developed a fast real time l 1 -tracker called the APG-l 1 tracker, which exploited the accelerated proximal gradient algorithm to improve the l 1 -tracker solver in [START_REF] Mei | Robust visual tracking using l 1 minimization[END_REF]. Zhong et al. [START_REF] Zhong | Robust object tracking via sparsity-based collaborative model[END_REF] addressed the object tracking problem by developing a sparsitybased collaborative model, which combined a sparsity-based classifier learned from holistic templates and a sparsity-based template model generated from local representations. Zhang et al. [START_REF] Zhang | Fast compressive tracking[END_REF] proposed to formulate a sparse feature measurement matrix based on an appearance model by exploiting nonadaptive random projections, and employed a coarse-to-fine strategy to accelerate the computational efficiency of tracking task. Lu et al. [START_REF] Lu | Robust visual tracking with discriminative sparse learning[END_REF] proposed to employ both non-local selfsimilarity and sparse representation to develop a non-local selfsimilarity regularized sparse representation method based on geometrical structure information of the target template data set. Wang et al. [START_REF] Wang | Online robust non-negative dictionary learning for visual tracking[END_REF] proposed a sparse representation based online two-stage tracking algorithm, which learned a linear classifier based on local sparse representation on favorable image patches. More detailed visual tracking algorithms can be found in the recent reviews [START_REF] Zhang | Sparse coding based visual tracking: Review and experimental comparison[END_REF][START_REF] Smeulders | Visual tracking: An experimental survey[END_REF].

IX. EXPERIMENTAL EVALUATION

In this section, we take the object categorization problem as an example to evaluate the performance of different sparse representation based classification methods. We analyze and compare the performance of sparse representation with the most typical algorithms: OMP [START_REF] Tropp | Signal recovery from random measurements via orthogonal matching pursuit[END_REF], l 1 l s [START_REF] Koh | An interior-point method for large-scale l 1 -regularized logistic regression[END_REF], PALM [START_REF] Yang | Fast l 1 -minimization algorithms for robust face recognition[END_REF], FISTA [START_REF] Beck | A fast iterative shrinkagethresholding algorithm for linear inverse problems[END_REF], DALM [START_REF] Yang | Fast l 1 -minimization algorithms for robust face recognition[END_REF], homotopy [START_REF] Asif | Primal dual pursuit: A homotopy based algorithm for the dantzig selector[END_REF] and TPTSR [START_REF] Xu | A two-phase test sample sparse representation method for use with face recognition[END_REF]. Plenties of data sets have been collected for object categorization, especially for image classification. Several image data sets are used in our experimental evaluations.

ORL:

The ORL database includes 400 face images taken from 40 subjects each providing 10 face images [START_REF] Samaria | Parameterisation of a stochastic model for human face identification[END_REF]. For some subjects, the images were taken at different times, with varying lighting, facial expressions, and facial details. All the images were taken against a dark homogeneous background with the subjects in an upright, frontal position (with tolerance for some side movement). Each image was resized to a 56×46 image matrix by using the down-sampling algorithm.

LFW face dataset:

The Labeled Faces in the Wild (LFW) face database is designed for the study of unconstrained identity verification and face recognition [START_REF] Huang | Labeled faces in the wild: A database for studying face recognition in unconstrained environments[END_REF]. It contains more than 13,000 images of faces collected from the web under the unconstrained conditions. Each face has been labeled with the name of the people pictured. 1680 of the people pictured have two or more distinct photos in the database.

In our experiments, we chose 1251 images from 86 peoples and each subject has 10-20 images [START_REF] Wang | Sparse tensor discriminant color space for face verification[END_REF]. Each image was manually cropped and was resized to 32×32 pixels.

Extended YaleB face dataset: The extended YaleB database contains 2432 front face images of 38 individuals and each subject having around 64 near frontal images under different illuminations [START_REF] Georghiades | From few to many: Illumination cone models for face recognition under variable lighting and pose[END_REF]. The main challenge of this database is to overcome varying illumination conditions and expressions. The facial portion of each original image was cropped to a 192×168 image. All images in this data set for our experiments simply resized these face images to 32×32 pixels. COIL20 dataset: Columbia Object Image Library (COIL-20) database consists of 1,440 size normalized gray-scale images of 20 objects [START_REF] Nene | Columbia object image library (coil-20)[END_REF]. Different object images are captured at every angle in a 360 rotation. Images of the objects were taken from varying angles at pose intervals of five degrees and each object has 72 images.

Fifteen scene dataset: This dataset contains 4485 images under 15 natural scene categories presented in literature [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF] and each category includes 210 to 410 images. The 15 scenes categories are office, kitchen, living room, bedroom, store, industrial, tall building, inside cite, street, highway, coast, open country, mountain, forest and suburb. A wide range of outdoor and indoor scenes are included in this dataset. The average image size is around 250×300 pixels and the spatial pyramid matching features are used in our experiments.

A. Parameter selection

Parameter selection, especially selection of the regularization parameter λ in different minimization problems, plays an important role in sparse representation. In order to make fair comparisons with different sparse representation algorithms, performing the optimal parameter selection for different sparse representation algorithms on different datasets is advisable and indispensable. In this subsection, we perform extensive experiments for selecting the best value of the regularization parameter λ with a wide range of options. Specifically, we implement the l 1 l s , FISTA, DALM, homotopy and TPTSR algorithms on different databases to analyze the importance of the regularization parameter. Fig. 5 summarizes the classification accuracies of exploiting different sparse representation based classification methods with varying values of regularization parameter λ on the two face datasets, i.e. ORL and LFW face datasets, and two object datasets, i.e. COIL20 and Fifteen scene datasets. On the ORL and LFW face datasets, we respectively selected the first five and eight face images of each subject as training samples and the rest of image samples for testing. As for the experiments on the COIL20 and fifteen scene datasets, we respectively treated the first ten images of each subject in both datasets as training samples and used all the remaining images as test samples. Moreover, from Fig. 5, one can see that the value of regularization parameter λ can significantly dominate the classification results, and the values of λ for achieving the best classification results on different datasets are distinctly different. An interesting scenario is that the performance of the TPTSR algorithm is almost not influenced by the variation of regularization parameter λ in the experiments on fifteen scene dataset, as shown in Fig. 5(d). However, the best classification accuracy can be always obtained within the range of 0.0001 to 1. Thus, the value of the regularization parameter is set within the range from 0.0001 to 1.

B. Experimental results

In order to test the performance of different kinds of sparse representation methods, an empirical study of experimental results is conducted in this subsection and seven typical sparse representation based classification methods are selected for performance evaluation followed with extensive experimental results. For all datasets, following most previous published work, we randomly choose several samples of every class as training samples and used the rest as test samples and the experiments are repeated 10 times with the optimal parameter obtained using the cross validation approach. The gray-level features of all images in these data sets are used to perform classification. For the sake of computational efficiency, principle component analysis algorithm is used as a preprocessing step to preserve 98% energy of all the data sets. The classification results and computational time have been summarized in Table I. From the experimental results on different databases, we can conclude that there still does not exist one extraordinary algorithm that can achieve the best classification accuracy on all databases. However, some algorithms are noteworthy to be paid much more attention. For example, the l 1 l s algorithm in most cases can achieve better classification results than the other algorithms on the ORL database, and when the number of training samples of each class is five, the l 1 l s algorithm can obtain the highest classification result of 95.90%. The TPTSR algorithm is very computationally efficient in comparison with other sparse representation with l 1 -norm minimization algorithms and the classification accuracies obtained by the TPTSR algorithm are very similar and sometimes even better than the other sparse representation based classification algorithms.

The computational time is another indicator for measuring the performance of one specific algorithm. As shown in Table I, the average computational time of each algorithm is shown at the bottom of the table for one specific number of training samples. Note that the computational time of OMP and TPTSR algorithms are drastically lower than that of other sparse representation with l 1 -norm minimization algorithms. This is mainly because the sparse representation with l 1norm minimization algorithms always iteratively solve the l 1norm minimization problem. However, the OMP and TPTSR algorithms both exploit the fast and efficient least squares technique, which guarantees that the computational time is significantly less than other l 1 -norm based sparse representation algorithms.

C. Discussion

Lots of sparse representation methods have been available in past decades and this paper introduces various sparse representation methods from some viewpoints, including their motivations, mathematical representations and the main algorithms. Based on the experimental results summarized in Section IX, we have the following observations. First, a challenging task of choosing a suitable regularization parameter for sparse representation should make further extensive studies. We can see that the value of the regularization parameter can remarkably influence the performance of the sparse representation algorithms and adjusting the parameters in sparse representation algorithms requires expensive labor. Moreover, adaptive parameter selection based sparse representation methods is preferable and very few methods have been proposed to solve this critical issue.

Second, although sparse representation algorithms have achieved distinctly promising performance on some real-world databases, many efforts should be made in promoting the accuracy of sparse representation based classification, and the robustness of sparse representation should be further enhanced.

In terms of the recognition accuracy, the algorithms of l 1 l s , homotopy and TPTSR achieve the best overall performance. Considering the experimental results of exploiting the seven algorithms on the five databases, the l 1 l s algorithm has eight highest classification accuracies, followed by homotopy and TPTSR, in comparison with other algorithms. One can see that the sparse representation based classification methods still can not obtain satisfactory results on some challenge databases. For example, all these representative algorithms can achieve relatively inferior experimental results on the LFW dataset shown in Subsection IX-B, because the LFW dataset is designed for studying the problem of unconstrained face recognition [START_REF] Huang | Labeled faces in the wild: A database for studying face recognition in unconstrained environments[END_REF] and most of the face images are captured under complex environments. One can see that the PALM algorithm has the worst classification accuracy on the LFW dataset and the classification accuracy even decreases mostly with the increase of the number of the training samples. Thus, devising more robust sparse representation algorithm is an urgent issue.

Third, enough attention should be paid on the computational inefficiency of sparse representation with l 1 -norm minimization. One can see that high computational complexity is one of the most major drawbacks of the current sparse representation methods and also hampers its applications in real-time processing scenarios. In terms of speed, PALM, FISTA and DALM take much longer time to converge than the other methods. The average computational time of OMP and TPTSR is the two lowest algorithms. Moreover, compared with the l 1 -regularized sparse representation based classification methods, the TPTSR has very competitive classification accuracy but significantly low complexity. Efficient and effective sparse representation methods are urgently needed by real-time applications. Thus, developing more efficient and effective methods is essential for future study on sparse representation.

Finally, the extensive experimental results have demonstrated that there is no absolute winner that can achieve the best performance for all datasets in terms of classification accuracy and computational efficiency. However, l 1 l s , TPTSR and homotopy algorithms as a whole outperform the other algorithms. As a compromising approach, the OMP algorithm can achieve distinct efficiency without sacrificing much recognition rate in comparison with other algorithms and it also has been extensively applied to some complex learning algorithms as a function.

X. CONCLUSION

Sparse representation has been extensively studied in recent years. This paper summarizes and presents various available sparse representation methods and discusses their motivations, mathematical representations and extensive applications. More specifically, we have analyzed their relations in theory and empirically introduced the applications including dictionary learning based on sparse representation and real-world applications such as image processing, image classification, and visual tracking.

Sparse representation has become a fundamental tool, which has been embedded into various learning systems and also has received dramatic improvements and unprecedented achievements. Furthermore, dictionary learning is an extremely popular topic and is closely connected with sparse representation. Currently, efficient sparse representation, robust sparse representation, and dictionary learning based on sparse representation seem to be the main streams of research on sparse representation methods. The low-rank representation technique has also recently aroused intensive research interests and sparse representation has been integrated into low-rank representation for constructing more reliable representation models. However, the mathematical justification of low-rank representation seems not to be elegant as sparse representation. Because employing the ideas of sparse representation as a prior can lead to state-of-the-art results, incorporating sparse representation with low-rank representation is worth further research. Moreover, subspace learning also has been becoming one of the most prevailing techniques in pattern recognition and computer vision. It is necessary to further study the relationship between sparse representation and subspace learning, and constructing more compact models for sparse subspace learning becomes one of the popular topics in various research fields. The transfer learning technique has emerged as a new learning framework for classification, regression and clustering problems in data mining and machine learning. However, sparse representation research still has been not fully applied to the transfer learning framework and it is significant to unify the sparse representation and low-rank representation techniques into the transfer learning framework to solve domain adaption, multitask learning, sample selection bias and covariate shift problems. Furthermore, researches on deep learning seems to become an overwhelming trend in the computer vision field. However, dramatically expensive training effort is the main limitation of current deep learning technique and how to fully introduce current sparse representation methods into the framework of deep learning is valuable and unsolved.

The application scope of sparse representation has emerged and has been widely extended to machine learning and computer vision fields. Nevertheless, the effectiveness and efficiency of sparse representation methods cannot perfectly meet the need for real-world applications. Especially, the complexities of sparse representation have greatly affected the applicability, especially the applicability to large scale problems. Enhancing the robustness of sparse representation is considered as another indispensable problem when researchers design algorithms. For image classification, the robustness should be seriously considered, such as the robustness to random corruptions, varying illuminations, outliers, occlusion and complex backgrounds. Thus, developing an efficient and robust sparse representation method for sparse representation is still the main challenge and to design a more effective dictionary is being expected and is beneficial to the performance improvement.

Sparse representation still has wide potential for various possible applications, such as event detection, scene reconstruction, video tracking, object recognition, object pose estimation, medical image processing, genetic expression and natural language processing. For example, the study of sparse representation in visual tracking is an important direction and more depth studies are essential to future further improvements of visual tracking research. In addition, most sparse representation and dictionary learning algorithms focus on employing the l 0 -norm or l 1 -norm regularization to obtain a sparse solution. However, there are still only a few studies on l 2,1 -norm regularization based sparse representation and dictionary learning algorithms. Moreover, other extended studies of sparse representation may be fruitful. In summary, the recent prevalence of sparse representation has extensively influenced different fields. It is our hope that the review and analysis presented in this paper can help and motivate more researchers to propose perfect sparse representation methods.

Fig. 2 :

 2 Fig. 2: Geometric interpretations of different norms in 2-D space [7]. (a), (b), (c), (d) are the unit ball of the l 0 -norm, l 1 -norm, l 2 -norm, l p -norm (0<p<1) in 2-D space, respectively. The two axes of the above coordinate systems are x 1 and x 2 .

Fig. 4 :

 4 Fig. 4: The geometry of the solutions of different norm regularization in 2-D space [7]. (a), (b) and (c) are the geometry of the solutions of the l 0 -norm, l 1 -norm, l 2 -norm minimization, respectively.

Algorithm 5 .

 5 Fast Iterative shrinkage thresholding algorithm (FISTA) Task: To address the problem α = arg min F (α) = 1 2 Xαy 2 2 + λ α 1

Algorithm 8 .

 8 Dual augmented Lagrangian method for l 1 -norm regularization Task: To address the dual problem of α = arg minα α 1 s.t. y = Xα

  is a matrix composed of local descriptors extracted from examples and the objective dictionary D = [d 1 , d 2 , • • • , d N ] ∈ R d×N . The objective function of LLC is formulated as arg min xi,D N i=1

  dist(y i , D) = [dist(y i , d 1 ), • • • , dist(y i , d N )] and dist(y i , d j ) denotes the distance between y i and d j with different distance metrics, such as Euclidean distance and Chebyshev distance. Specifically, the i-th value of vector b is defined as b i = exp dist(yi,di) σ . The K-Means clustering algorithm is applied to generate the codebook D, and then the solution of LLC can be deduced as: xi = (C i + µ diag 2 (b))\1 (VIII.8)

Algorithm 13 .+µ b⊙ x i 2 2 2 2Step 3 :

 13223 The incremental codebook optimization algorithm Task: Learning a dictionary D: arg minx i ,D N i=1 y i -Dx i 2 2 s.t. 1 T x i = 1, ∀i; d j ≤ 1, ∀j Input: The matrix composed of given samples Y = [y 1 , y 2 , • • • , y N ]. Initialization: i = 1, ε = 0.01, D initialized by K-Means clustering algorithm. While i is not equal to N doStep 1: Initialize b with 1 × N zero vector.Step 2: Update locality constraint parameter b with b j = exp -dist(y i ,d j ) σ for ∀j. Normalize b using the equation b = b-b min bmax-b min . Step 4: Exploit the LLC coding algorithm to obtain x i . Step 5: Keep the set of D i , whose corresponding entries of the code x i are greater than ε, and drop out other elements, i.e. index ← {j | abs{x i (j)} > ε} ∀j and D i ← D(:, index). Step 6: Update x i exploiting arg max y

y 4 ]T -ZX 2 2 s

 42 and D = [d 1 . . . d 4 ] where y 1 , y 2 , d 1 and d 2 are from the first class, and y 3 , y 4 , d 3 and d 4 are from the second class, and then the joint label matrixL can be defined as L = to the DKSVD algorithm, the objective function VIII.17 can also be reformulated as Z, X = arg min Z,X .t.x i 0 ≤ k (VIII.18)

Algorithm 14 .

 14 Super-resolution via sparse representation Input: Training image patches dictionaries D l and D h , a low-resolution image Y .

  arg min α α 0 s.t. Dα = z (VIII.34) And an equivalent problem can be reformulated for a proper value of λ, i.e. arg min α Dαz 2 2 + λ α 0 (VIII.35)

Algorithm 16 . 2 √ 2ρ 2 σt and µ = 2 √ 2ρ 2 ηt . Step 4 :

 162224 Centralized sparse representation for image restorationInitialization: Set x = y, initialize regularization parameter λ and µ, the number of training iteration T , t = 0, θ 0 = 0.Step 1: Partition the degraded image into M overlapped patches. While t ≤ T do Step 2: For each image patch, update the corresponding dictionary for each cluster via k-means and PCA.Step 3: Update the regularization parameters λ and µ by using λ = Compute the nonlocal means estimation of the unbiased estimation of αx, i.e. θ t+1 i , by using Eq. (VIII.46) for each image patch.

Fig. 5 :

 5 Fig. 5: Classification accuracies of using different sparse representation based classification methods versus varying values of the regularization parameter λ on the (a) ORL (b) LFW (c) Coil20 and (d) Fifteen scene datasets.

  [START_REF] Candes | An introduction to compressive sampling[END_REF] For the classification phase, Y is the matrix composed of the test samples. Based on the obtained learning results D ′ and C ′ , the sparse coefficient matrix xi can be obtained for each test sample y i by exploiting the OMP algorithm, which is to solve xi = arg min y i -D ′ x ′

	i	2 2	s.t.	x ′ i 0 ≤ k (VIII.15)
	On the basis of the corresponding sparse coefficient xi , the
	final classification, for each test sample y i , can be performed by judging the label result by multiplying xi by classifier C ′ ,
	that is,
	label = C ′ × xi	(VIII.16)

  . The optimization of problem VIII.35 is a joint optimization problem with respect to D, α i and x. It can be solved by alternatively optimizing one variable when fixing the others. The process of optimization is briefly introduced below.When dictionary D and the solution of sparse representation α i are fixed, problem VIII.36 can be rewritten as P i x and τ is small constant. One can see that the sub-problem VIII.39 is the same as problem VIII.2 and it can be solved by the KSVD algorithm previously presented in Subsection VIII-A2. The algorithm of image denoising exploiting sparse and redundant representation over learned dictionary is summarized in Algorithm 15, and more information can be found in literature[START_REF] Elad | Image denoising via sparse and redundant representations over learned dictionaries[END_REF]. To denoise a measured image y from white and additional Gaussian white noise:arg min D,α i ,x δ xy 2 2 + M i=1 Dα i -P i x 2 2 + M i=1 λ i α i0 Input: Measured image sample y, the number of training iteration T . Initialization: t = 1, set x = y, D initialized by an overcomplete DCT dictionary. While t ≤ T do

	When x is given, problem (VIII.36) can be written as
		M			M
	arg min D,αi	i=1	Dα i -P i x 2 2 +	i=1	λ i α i 0	(VIII.39)
	where the problem can be divided into M sub-problems and
	the i-th sub-problem can be reformulated as the following
	dictionary learning problem:
	arg min D,αi	Dα i -z 2 2 s.t. α i 0 ≤ τ	(VIII.40)
	where z = Algorithm 15. Image denoising via sparse and redundant representation
	over learned dictionary
	Task:
								M
							arg min x	δ x -y 2 2 +	i=1	Dα i -z 2 2	(VIII.37)
							where z = P i x. Apparently, problem VIII.37 is a simple
							convex optimization problem and has a closed-form solution,
							which is given by
							x =	M	P T i P i + δI	-1	M	i Dα i + δy P T	-1
								i=1	i=1	(VIII.38)

TABLE I :

 I Classification accuracies (mean classification error rates ± standard deviation %) of different sparse representation algorithms with different numbers of training samples. The bold numbers are the lowest error rates and the least time cost of different algorithms.

in Eq. VI.31.Step

3: Apply the half proximal thresholding operator to obtain the representation solution α t+1 = H λtτ, 1

ACKNOWLEDGMENT

This work was supported in part by the National Natural Science Foundation of China under Grant 61370163, Grant 61233011, and Grant 61332011, and in part by the Shenzhen Municipal Science and Technology Innovation Council under Grant JCYJ20130329151843309, Grant JCYJ20130329151843309, Grant JCYJ20140417172417174, Grant CXZZ20140904154910774, the China Postdoctoral Science Foundation funded project, No. 2014M560264 and the Shaanxi Key Innovation Team of Science and Technology (Grant no.: 2012KCT-04).

We would like to thank Jian Wu for many inspiring discussions and he is ultimately responsible for many of the ideas in the algorithm and analysis. We would also like to thank Dr. Zhihui Lai, Dr. Jinxing Liu and Xiaozhao Fang for constructive suggestions. Moreover, we thank the editor, an associate editor, and referees for helpful comments and suggestions which greatly improved this paper.