Title: SUPPORT REGULARIZED SPARSE CODING AND ITS FAST ENCODER

Abstract: Sparse coding represents a signal by a linear combination of only a few atoms of a learned over-complete dictionary. While sparse coding exhibits compelling performance for various machine learning tasks, the process of obtaining sparse code with fixed dictionary is independent for each data point without considering the geometric information and manifold structure of the entire data. We propose Support Regularized Sparse Coding (SRSC) which produces sparse codes that account for the manifold structure of the data by encouraging nearby data in the manifold to choose similar dictionary atoms. In this way, the obtained support regularized sparse codes capture the locally linear structure of the data manifold and enjoy robustness to data noise. We present the optimization algorithm of SRSC with theoretical guarantee for the optimization over the sparse codes. We also propose a feed-forward neural network termed Deep Support Regularized Sparse Coding (Deep-SRSC) as a fast encoder to approximate the sparse codes generated by SRSC. Extensive experimental results demonstrate the effectiveness of SRSC and Deep-SRSC.

1. INTRODUCTION:

The aim of sparse coding is to represent an input vector by a linear combination of a few atoms of a learned dictionary which is usually over-complete, and the coefficients for the atoms are called sparse code. Sparse coding is widely applied in machine learning and signal processing, and sparse code is extensively used as a discriminative and robust feature representation with convincing performance for classification and clustering (Yang et al., 2009; Cheng et al., 2013; Zhang et al., 2013) . Suppose the data X = [x 1 , x 2 , . . . , x n ] ∈ IR d×n lie in the d-dimensional Euclidean space IR d , and the dictionary matrix is D = [D 1 , D 2 , . . . , D p ] ∈ IR d×p with each D k ∈ IR d (k = 1, . . . , p) being an atom of the dictionary, sparse coding method seeks for the linear sparse representation with respect to the dictionary D for each vector x ∈ X by solving the following convex optimization problem:

min D,Z n i=1 1 2 xi -DZ i 2 2 + λ Z i 1 s.t. D k 2 ≤ c0, k = 1, . . . , p

where λ is a weighting parameter for the 1 -norm of z, and c 0 is a positive constant that bounds the 2 -norm of each dictionary atom. In (Gregor & LeCun, 2010) , a feed-forward neural network named Learned Iterative Shrinkage and Thresholding Algorithm (LISTA) is proposed to produce the approximation for sparse coding (1). The architecture of LISTA is illustrated in Figure 1 . The LISTA network involves an finite number of stages wherein each stage performs the following operation on the intermediate sparse code: where h θ is an element-wise shrinkage function defined as

EQUATION

EQUATION

and (•) + = max{•, 0} is the positive part of a number. Let f indicate the LISTA network and it generates the approximate sparse code z = f (x, Θ), where Θ = (W, S, θ) collectively denotes the parameters of the LISTA network. Suppose the optimal sparse codes for the training data x 1 , . . . , x m are Z * 1 , . . . , Z * m , then the parameters Θ are learned by minimizing the cost function which measures the distance between the predicted approximate sparse codes and the optimal sparse codes:

L(Θ) = 1 m m i=1 Z * i -f (x i , Θ) 2 2 .

The optimization is performed by stochastic gradient descent and back-propagation. Inspired by LISTA, a series of previous works have designed neural networks to simulate different forms of linear coding and achieve end-to-end training for different tasks such as image super-resolution (Liu et al., 2016) and hashing (Wang et al., 2016) .

Sparse coding is widely used to model high-dimensional data. Based on the formulation of sparse coding (1), it can be observed that the sparse code of each data point is obtained independently when the dictionary is fixed, which ignores the geometric information and manifold structure of the high-dimensional data. In order to obtain the sparse codes that account for the geometric information and manifold structure of the data, many regularized sparse coding methods, such as (Liu et al., 2010; He et al., 2011; Zheng et al., 2011; Gao et al., 2013) , employ manifold assumption (Belkin et al., 2006) . Manifold assumption in these methods imposes local smoothness on the sparse codes of nearby data, namely nearby data are encouraged to have similar sparse codes in the sense of 2 -distance, and they are termed 2 -Regularized Sparse Coding ( 2 -RSC). In this paper, we propose Support Regularized Sparse Coding (SRSC). Compared to 2 -RSC, SRSC captures the locally linear structure of the data manifold by encouraging nearby data to share dictionary atoms. In addition, SRSC enjoys robustness to data noise and preserves freedom in the spare representation of data without constraints on the magnitude of the sparse codes.

The remaining parts of the paper are organized as follows. SRSC and its optimization algorithm, together with 2 -RSC are introduced in the next section. The theoretical properties of the optimization of SRSC are shown in Section 3, with theoretical guarantee on the obtained sub-optimal solution for each step of the coordinate descent for obtaining the support regularized sparse codes: convergence to the critical point of the objective function and being close to the globally optimal solution. We then show the performance of the SRSC on data clustering, and conclude the paper. We use bold letters for matrices and vectors, and regular lower letter for scalars throughout this paper. The bold letter with superscript indicates the corresponding column of a matrix, and the bold letter with subscript indicates the corresponding element of a matrix or vector. In this section, we introduce Support Regularized Sparse Coding (SRSC) which is designed to capture the locally linear structure of the data manifold for sparse coding. One of the most important properties of manifold is that it is locally Euclidean, and each data point in the manifold has a neighbourhood that is homeomorphic to a Euclidean space. The success of several manifold learning methods, including LLE (Roweis & Saul, 2000) , SMCE (Elhamifar & Vidal, 2011) and Locally Linear Hashing (Irie et al., 2014) , is built on exploiting the locally linear structure of manifold. In these methods, the locally linear structure associated with each data point is a linear representation of

i x j x  k x t x 1  2  Figure 2:

Illustration of capturing the locally linear structure of the data manifold by Support Regularized Sparse Coding. Nearby data are encouraged to share dictionary atoms. In this example, x i and x j choose three common dictionary atoms so they lie on or close to the local subspace S 1 spanned by the common atoms, and it is the similar case for x t and x k with local subspace S 2 . Due to the smoothness of the support of the sparse codes, neighboring local subspaces, such as S 1 and S 2 , can share dictionary atoms. In this example, the two local subspaces share two dictionary atoms marked in red.

that point by a set of its nearest neighbors in a nonparametric manner, from which the low-dimensional embedding complying to the manifold structure of the original data is obtained and used for various learning tasks. In the context of sparse coding, the data lie on or close to the subspaces spanned by the dictionary atoms specified by the nonzero elements of the corresponding sparse codes. Inspired by this observation, we propose to capture the locally linear structure of the data manifold for sparse coding by encouraging nearby data to share the atoms of the dictionary, so that nearby data are on or close to the local subspace spanned by the common dictionary atoms (see Figure 2 ).

In order to obtain the sparse codes with locally similar support so as to capture the locally linear structure of the data manifold, we propose Support Regularized Sparse Coding (SRSC), which uses support distance to measure the distance between the sparse codes of nearby data. Given a proper symmetric similarity matrix A, the sparse codes Z that capture the locally linear structure of the manifold minimizes the following support regularization term:

EQUATION

A is usually the adjacency matrix of K-Nearest-Neighbor (KNN) graph, i.e. A ij = 1 if and only if x i is among the K nearest neighbors of x j or x j is among the K nearest neighbors of x i . Note that KNN is extensively used in the manifold learning literature, such as Locally Linear Embedding (LLE) (Roweis & Saul, 2000) , Laplacian Eigenmaps (Belkin & Niyogi, 2003) and Sparse Manifold Clustering and Embedding (SMCE) (Elhamifar & Vidal, 2011) , to establish the local neighborhood in the manifold. d indicates the support distance. For two vectors u, v of the same size, their support distance is defined below:

d(u, v) = |u| t=1 (1I u t =0,v t =0 + 1I u t =0,v t =0 ) (4)

where 1I is the indicator function. When the support distance between Z i and Z j is small for nonzero A ij , x i and x j choose similar atoms of the dictionary for sparse representation. Therefore, SRSC captures the locally linear structure of the data manifold by encouraging nearby data to share dictionary atoms, wherein the common atoms shared by nearby data serve as the basis of the local subspace.

The optimization problem of SRSC is presented below:

EQUATION

where γ > 0 is the weighting parameter for the support regularization term. Similar to (Lee et al., 2006) , problem ( 5) is optimized alternatingly with respect to the dictionary D and the sparse codes Z respectively with the other variable fixed.

2.1.1. OPTIMIZING WITH RESPECT TO D WITH FIXED Z:

The optimization with respect to D with fixed Z is a quadratic programming problem:

EQUATION

which can be solved using Lagrangian dual (Lee et al., 2006) .

2.1.2 OPTIMIZING WITH RESPECT TO Z WITH FIXED D

We use coordinate descent to optimize (5) with respect to Z with fixed D:

EQUATION

In each step of coordinate descent, the optimization is performed over the i-th column of Z, while fixing all the other sparse codes {Z j } j =i . For each 1 ≤ i ≤ n, the optimization problem for Z i is below:

min Z i F (Z i ) = 1 2 xi -DZ i 2 2 + λ Z i 1 + γR A (Z i ) (8) where R A (Z i ) = n j=1 A ij d(Z i , Z j ).

Inspired by recent advances in solving non-convex optimization problems by proximal linearized method (Bolte et al., 2014) , proximal gradient descent method (PGD) is used to optimize the nonconvex problem (8). Although the proximal mapping is typically associated with a lower semicontinuous function (Bolte et al., 2014) and it can be verified that R A is not always lower semicontinuous, we can still derive a PGD-styple iterative method to optimize (8).

Define

G A ∈ IR p×n as G A ki = n j=1 A ij 1I Z kj =0 - n j=1 A ij 1I Z kj =0

where 1I is the indicator function, then G A ki indicates the degree to which Z ki is discouraged to be nonzero and it can be verified that1 

EQUATION

Since each indicator function 1I Z ki =0 is lower semicontinuous, R A is lower semicontinuous if G A ki ≥ 0 for k = 1, . . . , p. In the following text, we let Q(

Z i ) = 1 2 x i -DZ i 2 2 .

The superscript with bracket indicates the iteration number of PGD or the iteration number of the coordinate descent without confusion. The PGD-style iterative method for optimizing (8) is as follows:

EQUATION

for k = 1, . . . , p and ε is any real number such that ε = 0 and

H k (ε) ≤ H k (Z (t-1) ki

). H k and u are defined below:

EQUATION

for v ∈ IR and each 1 ≤ k ≤ p, and

EQUATION

where • means element-wise multiplication.

Proposition 1 shows that the PGD-style iterative method decreases the value of the objective function in each iteration.

Proposition 1. Let the sequence {Z i (t) } t be generated by the PGD-style iterative method with (10) and ( 11), then the sequence of the objective {F (Z i (t) )} t decreases, and the following inequality holds for t ≥ 1:

F (Z i (t) ) ≤ F (Z i (t-1) ) - (τ -1)s 2 Z i (t) -Z i (t-1) 2 2 (14)

And it follows that the sequence {F (Z i (t) )} t converges. Remark 1. (10) and ( 11) in each iteration of the proposed PGD-style iterative method resemble that of the ordinary PGD. (10) performs gradient descent on the differential part, and (11) can be viewed as an approximate solution to the proximal mapping

min v∈IR p H(v) = τ s 2 v -Zi (t) 2 2 + λ v 1 + γR A (v). Since R A (Z i

) is not always lower semicontinuous, arg min v∈IR p H(v) is not guaranteed to exist. One can see a simple example where this happens when u k = 0 and G A ki < 0 for some k = 1, . . . , p, and in this case

inf v∈IR H k (v) = τ s 2 ( Z(t) ki ) 2 + γG A

ki but this infinitum can not be achieved.

In (10), τ > 1 is a constant and s is the Lipschitz constant for the gradient of function Q(•), namely

EQUATION

The PGD-style iterative method starts from t = 1 and continues until the sequence {F (Z i (t) )} converges or maximum iteration number is achieved. When the iterative method converges or terminates for each Z i , the step of coordinate descent for Z i is finished and the optimization algorithm proceeds to optimize other sparse codes.

Algorithm 1 Support Regularized Sparse Coding

Input::

The data set X = {xi} n i=1 , the parameter λ, γ, maximum iteration number M for the alternating method over D and Z, and maximum iteration number Mz for coordinate descent on Z, maximum iteration number Mp for the PGD-style iterative method on each Z i (i = 1,. . . ,n). and stopping threshold ε. 1: m = 1 2: while m ≤ M do 3:

Perform coordinate descent to optimize (7) and obtain Z (m) with fixed D (m-1) . In i-th (1 ≤ i ≤ n) step of each iteration of coordinate descent, solve (8) using the PGD-style iterative method (10) and (11) to update Z i in each iteration of the PGD-style iterative method. 4: Optimize (6) using Lagrangian dual and obtain D (m) with fixed Z (m) . 5:

if |L(D (m) , Z (m) ) -L(D (m-1) , Z (m-1) )| < ε then 6: break 7: else 8: m = m + 1. 9:

end if 10: end while Output: the support regularized sparse codes Ẑ when the above iterations converge or maximum iteration number is achieved.

TIME COMPLEXITY:

Algorithm 1 describes the algorithm of SRSC. We solve the ordinary sparse coding problem (1) by the online dictionary learning method (Mairal et al., 2009) and use the dictionary and the sparse codes as the initialization D (0) and Z (0) for the alternating method in Algorithm 1. In Algorithm 1, the time complexity of optimization over the sparse codes is O(M M z M p ndp 2 ), and time complexity of optimization over the dictionary using Newton's method to solve the Lagrangian dual problem is O M np 2 + T newton (3p 2.807 + 2dp 2 + dnp) , where T newton is the maximum iteration number for Newton's method. Therefore, the overall time complexity of Algorithm

1 is O M M z M p ndp 2 + np 2 + T newton (3p 2.807 + 2dp 2 + dnp) .

It should be emphasized that the optimization over the dictionary for SRSC has the same efficiency as the efficient sparse coding method (Lee et al., 2006) , and the optimization over the sparse code of each data point by the PGD-style iterative method ( 10) and ( 11) is almost as efficient as the widely used Iterative Shrinkage and Thresholding Algorithm (ISTA) (Daubechies et al., 2004; Beck & Teboulle, 2009) . Note that step (10) and ( 13) are required by both our method and ISTA; compared to ISTA, the extra operations incurred by our PGD-style iterative method ( 10) and ( 11) are only the arithmetic operations with time complexity 20p for evaluating the function H k (•) defined in ( 12) for k = 1, . . . , p. More specifically, evaluating the value of function H k (v) takes 10 arithmetic operations and two evaluations at v = u k and v = 0 are needed. Since a compact dictionary is preferred by the extensive study of the sparse coding and dictionary learning literature and the dictionary size p ≤ 500 is adopted throughout our experiments, our PGD-style iterative method only incurs extra operations of constant time complexity compared to ISTA while learning supported regularized sparse codes. In Section 4, we propose Deep-SRSC as a fast approximation of SRSC with considerable speedup for obtaining the sparse codes of the new data or the test data (see more details in Section 4.1). Furthermore, we conduct the empirical study and show that the parallel coordinate descent method, which updates the codes of a group of P data points in parallel and provides P times speedup over the coordinate descent method used in Section 2.1.2 and Algorithm 1, exhibits almost the same performance as the coordinate descent method for the clustering task on the test set of the CIFAR-10 data. Please refer to the details in the subsection "Deep-SRSC with the Second Test Setting (Referring to the Training Data)" in the Appendix.

2.2. RELATED WORK::

2 REGULARIZED SPARSE CODING ( 2 -RSC)

The manifold assumption (Belkin et al., 2006) is usually employed by existing regularized sparse coding methods (Liu et al., 2010; He et al., 2011; Zheng et al., 2011; Gao et al., 2013) to obtain the sparse code according to the manifold structure of the data. Interpreting the sparse code of a data point as its embedding, the manifold assumption in the case of sparse coding for most existing methods requires that if two points x i and x j are close in the intrinsic geometry of the submanifold, their corresponding sparse codes Z i and Z j are also expected to be similar to each other in the sense of 2 -distance (Zheng et al., 2011; Gao et al., 2013) . In other words, z varies smoothly along the geodesics in the intrinsic geometry. Based on the spectral graph theory (Chung, 1997) , extensive literature uses graph Laplacian to impose local smoothness of the embedding and preserve the local manifold structure (Belkin et al., 2006; Zheng et al., 2011; Gao et al., 2013) .

The sparse code Z that captures the local geometric structure of the data in accordance with the manifold assumption by graph Laplacian minimizes the following 2 regularization term, or the Laplacian regularization term:

R ( 2 ) A (Z) = 1 2 n i=1 n j=1 Aij Z i -Z j 2 2 (16)

where the 2 -norm is used to measure the distance between sparse codes, and A is the same as that in Section 2.1. L A = D A -A is the graph Laplacian associated with the similarity matrix A, the degree matrix D A is a diagonal matrix with each diagonal element being the sum of the elements in the corresponding row of A, namely

(D A ) ii = n j=1

A ij . To the best of our knowledge, such 2 regularization is employed by most methods that use graph regularization for sparse coding.

Incorporating the 2 regularization term into the optimization problem of sparse coding (1), the formulation of 2 Regularized Sparse Coding ( 2 -RSC) is presented below

EQUATION

ADVANTAGE OF SRSC OVER 2 -RSC Although 2 -RSC imposes the local smoothness on the sparse codes, it does not capture the locally linear structure of the data manifold. By promoting the smoothness on the support of the sparse codes rather than their 2 -distance, SRSC encodes the locally linear structure of the manifold in the sparse codes while reserving freedom in the sparse representation of the data with no constraints on the magnitude of the sparse codes. Moreover, as pointed out by (Wang et al., 2015) , support regularization offers robustness to noise for sparse coding. In SRSC, all the data consult their neighbors for choosing the dictionary atoms rather than choosing the atoms on their own, and the sparse codes of the noisy data are suppressed since they are forced to choose similar or the same atoms as the nearby clean data instead of choosing the atoms in the interests of representing themselves.

3. THEORETICAL ANALYSIS:

It can be observed that optimization by coordinate descent over the sparse code in Section 2.1.2 is important for the overall optimization of SRSC, and each step of the coordinate descent ( 8) is a difficult nonconvex problem and crucial for obtaining the support regularized sparse code, where the nonconvexity comes from the support regularization term R A (Z i ) (9). Therefore, the optimization of ( 8) plays an important role in the overall optimization of SRSC. In the previous section, a PGDstyle iterative method is proposed to decrease the value of the objective in each iteration. In this section, we provide further theoretical analysis on the optimization of problem (8) when G A ki ≥ 0 for k = 1, . . . , p. This condition is equivalent to the condition that the support regularization function

EQUATION

is lower semicontinuous, where c ∈ IR p is the coefficients and c k = G A ki . Under this condition, we prove that the sequence {Z i (t) } t produced by the PGD-style iterative method converges to the suboptimal solution which is a critical point of the objective (8). By connecting the support regularized function to the capped-1 norm and the nonconvexity analysis of the support regularization term, we present the bound for 2 -distance between the sub-optimal solution and the globally optimal solution to (8) in Theorem 1. Note that our analysis is valid for all 1 ≤ i ≤ n.

We first have the following result that the support regularization function ( 18) is lower semicontinuous if and only if all the coefficients c are nonnegative. Proposition 2. The support regularization function ( 18) is lower semicontinuous if and only if all the coefficients c are nonnegative.

Therefore, if G A:

ki ≥ 0 for k = 1, . . . , p, the support regularization term R A (Z i ) is lower semicontinuous with respect to Z i in (9). In this case, the PGD-style iterative method proposed in Section 2.1.2 for each iteration t ≥ 1 becomes

EQUATION

which is equivalent to the updates rules in the ordinary proximal gradient descent method. It is worthwhile to mention the meaning of the condition that G A ki ≥ 0 for k = 1, . . . , p. For a data point x i , if the number of its neighbors with zero k-th element of the sparse codes is larger than that with nonzero k-th element of the sparse codes, which indicates that the neighbors of x i suggest that a zero k-th element of the sparse code of x i is preferable, then G A ki ≥ 0 and G A ki quantitatively represents the penalty if the sparse code element Z i k is nonzero while the neighbors of x i suggest that Z i k = 0 is preferable. Intuitively, this situation happens when there is conflict between choosing the support of the code solely by the data point itself and the suggestion of its neighbors; if the point is an outlier or suffering from noise, the optimization can help that point make a sensible choice by considering the suggestion of its neighbors. We observe that G A ki ≥ 0 for k = 1, . . . , p happens in all the data sets used in this paper.

In the following lemma, we show that the sequence {Z i (t) } t generated by ( 19) and ( 20) converges to a critical point of F (Z i ), denoted by Ẑi . Denote by Z i * the globally optimal solution to the original optimization problem (8). The following lemma also shows that both Ẑi and Z i * are local solutions to the capped-1 regularized problem (21). Before stating the lemma, the following definitions are introduced which are essential for our analysis.

Definition 1. (Critical points) Given the non-convex function f : IR n → R ∪ {+∞} which is a proper and lower semi-continuous function.

• for a given x ∈ domf , its Frechet subdifferential of f at x, denoted by ∂f (x), is the set of all vectors u ∈ IR n which satisfy lim sup

y =x,y→x f (y) -f (x) -u, y -x y -x ≥ 0

• The limiting-subdifferential of f at x ∈ IR n , denoted by written ∂f (x), is defined by

∂f (x) = {u ∈ IR n : ∃x k → x, f (x k ) → f (x), ũk ∈ ∂f (x k ) → u} The point x is a critical point of f if 0 ∈ ∂f (x).

Also, we are considering the following capped-1 regularized problem, which replaces the indicator function in the support regularization term R A (Z i ) with the continuous capped-1 regularization term T:

EQUATION

where Note that θ(t, κ) = 0 for convex function P .

T(β; b) = p k=1 T k (β k ; b), T k (t; b) = γG A ki min{|t|,

Let Ŝi = supp( Ẑi ) where supp(•) indicates the support of a vector, i.e. the indices of its nonzero elements. Denote by Z i * the globally optimal solution to (8), and S * i = supp(Z i * ), then we have Lemma 1. For any 1 ≤ i ≤ n, if G A ki ≥ 0 for k = 1, . . . , p, then the sequence {Z i (t) } t generated by ( 10) and ( 11) converges to a critical point of F (Z i ), which is denoted by Ẑi . Moreover, if

EQUATION

(if the denominator is 0, • 0 is defined to be +∞ in the above inequality), then both Ẑi and Z i * are local solutions to the capped-1 regularized problem (21).

Using the degree of nonconvexity of the regularizer P, we have the following theorem showing that the sub-optimal solution Ẑi obtained by our PGD-style iterative method can be close to the globally optimal solution to the original problem (8), i.e. Z i * . In the following text, B I indicates a submatrix of B whose columns correspond to the nonzero elements of I, and σ min (•) indicates the smallest singular value of a matrix. Theorem 1. (Sub-optimal solution is close to the globally optimal solution) For any

1 ≤ i ≤ n, let E i = Ŝi ∪ S * i . Suppose G A ki ≥ 0 for k = 1, . . . , p, D Ei is not singular with κ 0 σ min (D Ei ) > 0, κ 2 0 > κ > 0,

and b is chosen according to (23) as in Lemma 1. Let Si = ( Ŝi \ S * i ) ∪ (S * i \ Ŝi ) be the symmetric difference between Ŝi and S * i , then

Z i * -Ẑi 2 ≤ 1 κ 2 0 -κ k∈ Si ∩ Ŝi (max{0, γG A ki b -κ| Ẑki -b|}) 2 + k∈ Si \ Ŝi (max{0, γG A ki b -κb}) 2 1 2 + t 2 (24)

where

t ∈ IR p , t k = 2λ1I Z i k * Ẑi k <0 + 01I Z i k * Ẑi k >0 for k ∈ Ŝi ∩ S *

i , and t k = 0 for all other k. Remark 2. Note that the bound for distance between the sub-optimal solution and the globally optimal solution presented in Theorem 1 does not require typical Restricted Isometry Property (RIP) conditions, e.g. Cands (2008) . Also, when -κb are no greater than 0 and Z i * and Ẑi has the same sign in the intersection of their support, the sub-optimal solution Ẑi is equal to the globally optimal solution. When Inspired by the PGD-style iterative method (10) and ( 11) for SRSC and the LISTA network, we propose Deep Support Regularized Sparse Coding (Deep-SRSC) illustrated in Figure 3 , which is a neural network that produces the approximate support regularized sparse codes for SRSC. The goal of Deep-SRSC is to approximate the sparse codes of the input data in a fast way by feeding the data through the Deep-SRSC network, instead of running the iterative optimization algorithm for SRSC in Section 2.1. To achieve this goal, the Deep-SRSC network is trained on the training data by minimizing the squared distance between the predicted codes of the training data by the network and their ground truth codes. The network design of Deep-SRSC is in accordance with the proposed PGD-style iterative method. When W = 1 L D , S = I -1 L D D where L = τ s, then each stage in the recurrent structure of Deep-SRSC implements one iteration of PGD-style iterative method, i.e. ( 10) and ( 11). In Deep-SRSC, W, S and L are to be learned by the network rather than computed from a pre-computed dictionary D, and S is shared over different layers. The min-pooling neuron in Deep-SRSC outputs the result of arg min

v∈{u k ,0}

H k (v) or ε, according to the update rule (11). Figure 3 illustrates Deep-SRSC with 2 layers. Denote the training data by x 1 , . . . , x m , and let Z sr be the ground truth support regularized sparse codes of the training data which are obtained by the optimization method introduced in Section 2.1. Let f sr be the Deep-SRSC encoder which produces the approximate support regularized sparse code z = f sr (x, Θ sr ), where Θ sr = (W, S, L) denotes the parameters of Deep-SRSC. Then the parameters of Deep-SRSC are learned by minimizing the cost function which measures the distance between the predicted approximate support regularized sparse codes and the ground truth ones:

1 m m i=1 Z i sr -f sr (x i , Θ sr ) 2 2 .

Similar to the LISTA network, the optimization is performed by stochastic gradient descent and back-propagation. The batch size is set to 1 so as to simulate the coordinate descent method for optimization over the sparse codes in Section 2.1.2. The adjacency matrix of the KNN graph over the training data is required as input for training the network.

The approximate codes of the new data, or the test data, are obtained by feeding the new data through the Deep-SRSC network learned on the training data. We provide two test settings below, depending on whether training data are referred to in the test process.

1) In the first setting where the training data are not referred to, the test data are a group of data points. The test data and the KNN graph over them are fed into the Deep-SRSC network to obtain the approximate codes of the test data. The locally linear manifold structure of the test data is encoded in the KNN graph over the test data. This setting is potentially more suitable for the situation of limited storage where the training data and their codes do not need to be stored in the test process. This setting may not be suitable for the test data that do not reliably reflect the locally linear manifold structure (e.g. in the case of a very small amount of test data), and in this case the second setting below is a better choice.

2) In the second setting where training data are referred to, the approximate code of each data point is obtained by feeding that point and the KNN graph over that point and the training data into the Deep-SRSC network. The code of each test point is reliably obtained by referring to its nearest neighbors in the training data and this process is independent of the factor that whether the test data reflect the locally linear manifold structure.

4.1. DEEP-SRSC AS FAST ENCODER:

It should be emphasized that Deep-SRSC is a fast encoder for SRSC when obtaining the codes of the new data (or test data). Each layer of Deep-SRSC resembles one iteration of the PGD-style iterative method ( 10) and ( 11), and the computational cost of feeding forward a data point through one layer is the same as that of executing one iteration of the PGD-style iterative method for that point. Therefore, the feed-forward process of obtaining the sparse codes of the new data using -layer Deep-SRSC is around Mp times faster than the PGD-style iterative method used in Algorithm 1, where M p is the maximum iteration number for the PGD-style iterative method. In the experimental results shown in the next section, Deep-SRSC with different number of layers are employed to produce the approximate support regularized sparse codes, and 6-layer Deep-SRSC achieves minimum prediction error. With M p = 50 throughout our experiments, Deep-SRSC is around 50 6 ≈ 8.3 times faster than the PGD-style iterative method. Our analysis in this subsection holds for both test settings. 

5. EXPERIMENTAL RESULTS:



5.1. CLUSTERING PERFORMANCE:

In this subsection, the superiority of SRSC is demonstrated by its performance in data clustering on various data sets, e.g. USPS handwritten digits data set, COIL-20, COIL-100 and UCI Gesture Phase Segmentation data set. Two measures are used to evaluate the performance of the clustering methods, i.e. the Accuracy (AC) and the Normalized Mutual Information (NMI) (Zheng et al., 2004) . SRSC is compared to K-means (KM), Spectral Clustering (SC), Sparse Coding and 2 -RSC in Section 2.2. Throughout all the experiments, we set K = 3 for building the adjacency matrix A of KNN graph, dictionary size p = 300 and λ = 0.1 for both 2 -RSC and SRSC. We also set γ ( 2 ) = 1 which is the suggested default value in (Zheng et al., 2011) , and M = M z = 5 and M p = 50 in Algorithm 1. The default value of the weight for support regularization term of SRSC is γ = 0.5. SRSC is implemented by both MATLAB and CUDA C++ with extreme efficiency, and the code is published on GitHub: https://github.com/yingzhenyang/SRSC.

The USPS handwritten digits data set is comprised of n = 9298 handwritten images of ten digits from 0 to 9, and each image is of size 16 × 16 and represented by a 256-dimensional vector. The whole data set is divided into training set of 7291 images and test set of 2007 images. We run Algorithm 1 to obtain the support regularized sparse code Ẑ, then build a n × n similarity matrix Y over all the data. Two similarity measure are employed: the first similarity is the positive part of the inner product of their corresponding sparse codes, namely Y ij = max{0, Ẑi Ẑj }, the second one is Y ij = A ij q Ẑi q Ẑj where q v is a binary vector of the same size as v with element 1 at the indices of nonzero elements of v. The second similarity measure is name the support similarity and it considers the number of common dictionary atoms chosen by the sparse codes. Spectral clustering is performed on the similarity matrix Y to obtain the clustering result of SRSC, and the best performance among the two similarity measures is reported. The same procedure is performed by all the other sparse coding based methods to obtain clustering results. The clustering results of various methods are shown in Table 1 .

COIL-20 Database has 1440 images of resolution 32 × 32 for 20 objects, and the background is removed in all images. The dimension of this data is 1024. Its enlarged version, COIL-100 Database, contains 100 objects with 72 images of resolution 32 × 32 for each object. The images of each object were taken 5 degrees apart when each object was rotated on a turntable. The UCI Gesture Phase Segmentation data set contains the gesture information of three users when they told stories of some comic strips in front of the Microsoft Kinect sensor. We use the processed file provided by the original data consisting of 9873 frames, and the gesture information in each frame is the vectorial velocity and acceleration of left hand, right hand, left wrist, and right wrist, represented by a 32-dimensional vector. The clustering results on these three data sets are shown in Table 2 . It can be observed from Table 1 and Table 2 that SRSC always produces better clustering accuracy than other competing methods, due to its capability of capturing the locally linear manifold structure of the data and robustness to noies. In the appendix, we further show the performance of different sparse coding based methods with different dictionary size on COIL-100 data set in Table 5 , and investigate the parameter sensitive of SRSC by demonstrating its performance with varying γ and K in Table 6 .

5.2. APPROXIMATION BY DEEP-SRSC:

In this subsection, Deep-SRSC is employed as a fast encoder to approximate the support regularized sparse codes of SRSC on the USPS data set. Throughout this subsection, we show results using the first test setting introduced in Section 4, i.e. test without referring to the training data. Additional experimental results on the performance of Deep-SRSC with the second test setting, including the application to semi-supervised learning by label propagation (Zhu et al., 2003) , are shown in the appendix.

The Deep-SRSC network is trained on the training set of the USPS data comprising 7291 images. We adopt three depth settings wherein Deep-SRSC has 1 layer, 2 layers, and 6 layers respectively. We first run SRSC on the training set of USPS data to obtain the dictionary D sr and the support regularized sparse codes Z sr of the training data. Then the optimization problem ( 7) is solved by the PGD-style iterative method in Section 2.1.2, where X is the test data, A is the adjacency matrix of the KNN graph over the test data, to obtain the support regularized sparse codes Z sr,test of the test data with dictionary D sr . Z sr is used as the ground truth support regularized sparse codes to train Deep-SRSC, and Z sr,test serves as the ground truth codes of the test data. The approximate codes of the test data of the USPS data are obtained by feeding forward them into the Deep-SRSC network together with the KNN graph over the test data, and the prediction error of Deep-SRSC is the average of the squared error between the predicted codes and Z sr,test . Figure 4 Table 3 shows the prediction error of Deep-SRSC for different dictionary size p and different number of layers. It can be observed that Deep-SRSC with more layers demonstrates smaller prediction error for the same dictionary size due to its better representation capability, and smaller dictionary size leads to less prediction error for the same number of layers due to the reduced difficulty of representation. Moreover, the codes predicted by 6-layer Deep-SRSC are used to perform clustering on the test data because of its minimum prediction error, with comparison to the performance of sparse coding and 2 -RSC shown in Table 4 with respect to different dictionary size. For either sparse coding or 2 -RSC, the dictionary is firstly learned on the training data, then the sparse codes of the test data obtained with respect to that dictionary are used to perform clustering on the test set of USPS data. We can see that SRSC together with its approximation, 6-layer Deep-SRSC, achieve the highest accuracy and NMI. In addition, a reasonably large dictionary benefits SRSC, e.g. increasing p from 100 to 300 boosts its accuracy, since the dictionary atoms serve as the basis for the locally linear structures (local subspaces) of the data manifold and a sufficiently large dictionary size is favorable for modeling all such locally linear structures. On the other hand, a too large dictionary (such as p = 500) imposes much difficulty on the optimization which can even hurt the performance of SRSC, 2 -RSC and regular sparse coding.

6. CONCLUSION:

We propose Support Regularized Sparse Coding (SRSC) which captures the locally linear manifold structure of the high-dimensional data for sparse coding and enjoys robustness to noise. SRSC achieves this goal by encouraging nearby data in the manifold to share dictionary atoms. The optimization algorithm of SRSC is presented with theoretical guarantee for the optimization over the sparse codes. In addition, we propose Deep-SRSC, a feed-forward neural network, as a fast encoder to approximate the support regularized sparse codes produce by SRSC. Experimental results demonstrate the effectiveness of SRSC by its application to data clustering, and show that Deep-SRSC renders approximate codes for SRSC with low prediction error. The approximate codes generated by 6-layer Deep-SRSC also deliver compelling empirical performance for data clustering.

two functions H k (v) and T k (v) only differ at v = 0, arg min v∈{u k ,0} H k (v) is the optimal solution to minv∈R H k (v) when u k = 0 or u k = 0 and G A ki ≥ 0.

When u k = 0 and G A ki < 0, when ε → 0 and ε = 0, 1) , ∇Q(Z i (t-1) ) (25)

H k (v) → G A ki and infv∈IR H k (v) = τ s 2 ( Z(t) ki ) 2 + γG A ki . Note that the infimum can never be achieved. Since infv∈IR H k (v) < H k (Z (t-1) ki ), we can always find ε = 0 such that H k (ε) ≤ H k (Z (t-1) ki ). Define H(v) = τ s 2 v -Zi (t) 2 2 + λ v 1 + γR A (v). Based on the above argument, H(Z i (t) ) ≤ H(Z i (t-1) ) which indicates that τ s 2 Z i (t) -Z i (t-1) 2 2 + Z i (t) -Z i (t-

EQUATION

Also, since s is the Lipschitz constant for the gradient of function Q(•), we have

Q(Z i (t) ) ≤ Q(Z i (t-1) ) + Z i (t) -Z i (t-1) , ∇Q(Z i (t-1) ) + s 2 Z i (t) -Z i (t-1) 2 2 (27)

Combining ( 25) and ( 27),

F (Z i (t) ) ≤ F (Z i (t-1) ) - (τ -1)s 2 Z i (t) -Z i (t-1) 2 2

Proof of Lemma 1. We first prove that the sequences {Z i (t) }t is bounded for any 1 ≤ i ≤ n. By Proposition 1, the sequence {F (Z i (t) )}t decreases, so we have

F (Z i (t) ) = 1 2 xi -DZ i (t) 2 2 + λ Z i (t) 1 + γR A (Z i (t) ) ≤ xi -DZ i (0) 2 2 + λ Z i (0) 0 ≤ 1 + R A (Z i (0) ) for t ≥ 1. Therefore, Z i (t) 1 ≤ 1 λ xi -DZ i (0) 2 2 + λ Z i (0) 0 ≤ 1 + R A (Z i (0) )

It follows that Z i (t) 1 is bounded, and Z i (t) 2 is also bounded. Since G A ki ≥ 0 for k = 1, . . . , p and the indicator function 1I • =0 is semi-algebraic function, R A (•) is also a semi-algebraic function and lower semicontinuous. Therefore, according to Theorem 1 by Bolte et al. (2014) , {Z i (t) }t converges to a critical point of F (Z i ), denoted by Ẑi .

Let v = D (D Ẑi -xi) + Ṗ( Ẑi ; b). For k such that G A ki = 0, since Ẑi is a critical point of F (Z i ), vk = 0.

Now we consider the case that G A ki = 0.

For for k ∈ Ŝi, since Ẑi is a critical point of F (Z i ) = 1 2 xi -DZ i 2 2 + λ Z i 1 + γR A (Z i ). then ∂(Q+λ Z i 1 ) ∂Z i k | Z i = Ẑi = 0 because ∂R A (Z i ) ∂Z i k | Z i = Ẑi = 0 . Note that min k∈ Ŝi | Ẑi k | > b, so ∂T ∂Z i k | Z i = Ẑi = 0,

and it follows that vk = 0.

For k / ∈ Ŝi, since dP k dZ i k ( Ẑi k +; b) = γG A ki b + λ and dP k dZ i k ( Ẑi k -; b) = - γG A ki b -λ, γG A ki b + λ ≥ | ∂Q ∂Z i k | Z i = Ẑi |, we

can choose the k-th element of Ṗ( Ẑi ; b) such that vk = 0. Therefore, v 2 = 0, and Ẑi is a local solution to the problem (21). Now we prove that Z i * is also a local solution to (21). Let v * = D (DZ i * -xi) + Ṗ(Z i * ; b), and Q is defined as before. For k such that G A ki = 0, since Z i * is the globally optimal solution of F (Z i ), v * k = 0.

Again we consider the case that G A ki = 0.

For k ∈ S * i , since Z i * is the globally optimal solution to problem (8), we also have

∂(Q+λ Z i 1 ) ∂Z i k | Z i =Z i * = 0. If it is not the case and ∂(Q+λ Z i 1 ) ∂Z i k | Z i =Z i * = 0, then we can change Z i k by a small amount in the direction of the gradient ∂(Q+λ Z i 1 ) ∂Z i k at the point Z i = Z i * while Z i

k is still nonzero, leading to a smaller value of the objective F (Z i ).

Published as a conference paper at ICLR 2017

Note that min k∈S:

* i |Z i k * | > b, so ∂T ∂Z i k | Z i = Ẑi = 0, and it follows that v * k = 0. For k / ∈ S * i , since γG A ki b + λ ≥ max k / ∈ Ŝi | ∂Q ∂Z i k | Z i =Z i * |, we can choose the k-th element of Ṗ(Z i * ; b) such that v * k = 0.

It follows that v * 2 = 0, and Z i * is also a local solution to the problem (21).

Proof of Theorem 1. According to Lemma 1, both Ẑi and Z i * are local solutions to problem (21). In the following text, let β I indicates a vector whose elements are those of β with indices in I. Let ∆ = Z i * -Ẑi , ∆ = Ṗ(Z i * ) -Ṗ( Ẑi ). By Lemma 1, we have

D D∆ + ∆ 2 = 0 It follows that ∆ D D∆ + ∆ ∆ ≤ ∆ 2 D D∆ + ∆ 2 = 0 Also, by the proof of Lemma 1, for k ∈ Ŝi ∩ S * i , since (D D∆) k = 2λ1I Z i k * Ẑi k <0 + 01I Z i k * Ẑi k >0

we have ∆k = -(D D∆) k . We now present another property on any nonconvex function P using the degree of nonconvexity in Definition 3: θ(t, κ) := sup s {-sgn(s -t)( Ṗ (s; b) -Ṗ (t; b)) -κ|s -t|} on the regularizer P. For any s, t ∈ IR, we have

EQUATION

Applying ( 28) with P = P k for k = 1, . . . , p, we have

EQUATION

On the other hand, ∆ D D∆ ≥ κ 2 0 ∆ 2 2 . It follows from (29) that

κ 2 0 ∆ 2 2 ≤ θ( Ẑi Si , κ) 2 ∆ 2 + κ ∆ 2 2 + ∆ 2 ∆Ŝ i ∩S * i 2

When ∆ 2 = 0, we have

EQUATION

According to the definition of θ, it can be verified that θ(t, κ) = max{0,

EQUATION

EQUATION

where ∆k

= -(D D∆) k = -2λ1I Z i k * Ẑi k <0 -01I Z i k * Ẑi k >0 for k ∈ Ŝi ∩ S * i .

This proves the result of this theorem.

In addition, we investigate the parameter sensitivity of SRSC, and show in Table 6 the performance change while varying γ, the weight for the support regularization term, and K, the number of nearest neighbors when building the KNN graph for the support regularization term, on the USPS data set. It can be observed that the performance of SRSC is stable over a relatively large range of λ and K. SRSC often has the highest NMI while maintaining a very competitive accuracy.

DEEP-SRSC WITH THE SECOND TEST SETTING (REFERRING TO THE TRAINING DATA):

We demonstrate the performance of SRSC and Deep-SRSC with the second test setting (referring to the training data) on clustering and semi-supervised learning. The ground truth code of the each test data point is computed by performing the PGD-style iterative method to solve the problem (8) where xi is the test point, D is Dsr obtained from the training data as in Section 5.2, A is the adjacency matrix of the KNN graph over the test point and the training data. Table 9 shows the prediction error of Deep-SRSC for different dictionary size p and different number of layers on the USPS data, which is comparable to the case of the first test setting in Table 3 .

Two more data sets are used in this subsection, i.e. MNIST for hand-written digit recognition and CIFAR-10 for image recognition. MNIST is comprised of 60000 training images and 10000 test images of ten digits from 0 to 9, and each image is of size 28 × 28 and represented as a 784-dimensional vector. CIFAR-10 consists of 50000 training images and 10000 testing images in 10 classes, and each image is a color one of size 32 × 32. Using the second test setting, Deep-SRSC is trained on the training set, and the codes of the test set predicted by 6-layer Deep-SRSC are used to perform clustering on the test set for MNIST and CIFAR-10 data, with comparison to other sparse coding based methods. The clustering results are shown in Table 7 and 8 respectively with dictionary size p = 300. We observe that SRSC and Deep-SRSC always achieve the best performance compared to other competing methods. We employ the fast deep neural network named CNN-F (Chatfield et al., 2014) trained on the ILSVRC 2012 data to extract the 4096-dimensional feature vector for each image in the CIFAR-10 data, and all the clustering methods are performed on the extracted features. In addition to the coordinate descent method employed in Section 2.1.2 and Algorithm 1 for the optimization of the sparse codes in SRSC, we further conduct the empirical study showing that the parallel coordinate descent method, which updates the coordinates in parallel for improved efficiency and fits the needs of large-scale data optimization, leads to almost the same results as the coordinate descent method on the CIFAR-10 data. Instead of optimization with respect to the sparse code of a single data point in the coordinate descent method, the parallel coordinate descent method updates the sparse codes of P data points in parallel using the same rule as that in the coordinate descent method in Section 2.1.2 and Algorithm 1. While the parallel coordinate descent method is originally designed for convex problems (Bradley et al., 2011; Richtárik & Takáč, 2016) , it demonstrates almost the empirical performance as the coordinate descent method for the clustering task on the test set of the CIFAR-10 data, with the accuracy of 0.4622 and NMI of 0.3864. P -parallel coordinate descent leads to P times speedup compared to the coordinate descent method. We choose P = 10 and the codes of the training data of CIFAR-10 are learned by the parallel coordinate descent method, and note that the optimization of the codes of the test data are inherently parallelizable due to the nature of the second test setting studied in this subsection.

Moreover, Table 10 shows the prediction error of Deep-SRSC on the MNIST data and the CIFAR-10 data. It can be observed again that deeper Deep-SRSC network leads to smaller prediction error.

We also show the application to semi-supervised learning via label propagation (Zhu et al., 2003) , a widely used semi-supervised learning method. Given the data {x1, x2, . . . , x l , x l+1 , . . . , xn} ⊂ IR d , the first l points {x1, x2, . . . , x l } are labeled and named the training data, and the remaining n -l points form the test data for semi-supervised learning. Semi-supervised learning by label propagation aims to predict the labels of the test data by encouraging local smoothness of the labels in accordance with the similarity matrix over the entire data. The performance of label propagation depends on the similarity matrix. For each sparse coding based method, the similarity matrix Y over the entire data is built by the support similarity introduced in Section 5.1: Yij = Aijq Ẑi q Ẑj , and Z i is the code of data point xi for different sparse coding methods including the 6-layer Deep-SRSC with the second test setting. Label propagation is performed on the similarity matrix Y to obtain the labels of the test data, and the error rate is reported. Note that in the experiment of semi-supervised learning by label propagation, the codes of the test data of each data set are obtained first (e.g. the 10000 test images in the MNIST data). If xi belongs to the test data of a data set, its code is obtained by performing the the corresponding sparse coding optimization with the dictionary learned on the training data of that data set; for SRSC and Deep-SRSC, such optimization also has the KNN graph over the test point xi and the training data as input. With the codes of all the data, the similarity matrix Y over the entire data is constructed. Then, a randomly sampled subset of each class is labeled as the training data, with the other data serving as the test data for semi-supervised learning.

The semi-supervised learning results of our methods are compared to that of the Gaussian kernel graph (Gaussian), i.e. the KNN graph with the edge weight set by the Gaussian kernel; Sparse Coding (SC) and 2 -RSC; and manifold based similarity adaptation (MBS) by Karasuyama & Mamitsuka (2013) , one of the state-of-the-art semi-supervised learning methods based on label propagation. MBS learns the manifold aligned edge similarity by local reconstruction for label propagation.

:

This material is based upon work supported by the National Science Foundation under Grant No. 1318971. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

R A (Z i ) is equal to the right hand side of (9) up to a constant.

Figures and Tables:

Figure 1: Illustration of LISTA network for approximate sparse coding.

b} b for some b > 0. It can be seen that the objective function of the capped-1 problem approaches that of (8) when min{|t|,b} b approaches the indicator function 1I t =0 as b → 0+. Define P(•; b) = λ • 1 + T(•; b), the location solution to the capped-1 problem is defined as follows. Definition 2. (Local solution) A vector β is a local solution to the problem (21) if D (D βxi) + Ṗ( β; b) 2 = 0 (22) where Ṗ( β; b) = [ Ṗ1 ( β1 ; b), Ṗ2 ( β2 ; b), . . . , Ṗp ( βp ; b)] , P k (t; b) = λ|t| + T k (t; b) for k = 1, . . . , p. Note that in the above definition and the following text, Ṗk (t; b) can be chosen as any value between the right differential ∂P k ∂t (t+; b) (or Ṗk (t+; b)) and left differential ∂P k ∂t (t-; b) (or Ṗk (t-; b)) for k = 1, . . . , p. Definition 3. (Degree of Nonconvexity of a Regularizer) For κ ≥ 0 and t ∈ IR, define θ(t, κ) := sup s {-sgn(s -t)( Ṗ (s; b) -Ṗ (t; b)) -κ|s -t|} as the degree of nonconvexity for function P . If u = (u 1 , . . . , u p ) ∈ IR p , θ(u, κ) = [θ(u 1 , κ), . . . , θ(u p , κ)]. sgn is the sign function.

κ| Ẑki -b| and γG A ki b

Figure 3: Illustration of Deep-SRSC for approximate Support Regularized Sparse Coding.

Figure 4: Training error of Deep-SRSC with dictionary size p = 100, p = 300, and p = 500. The test error of Deep-SRSC is shown in Figure 5 in the appendix.

illustrates the training error of Deep-SRSC w.r.t. the epoch number for 1 layer, 2 layers, and 6 layers respectively, and Figure5in the appendix illustrates the test error of Deep-SRSC. For each depth setting, Deep-SRSC is trained with 300 epoches, and testing is performed for every 5 epoches during training. It can be observed that deeper Deep-SRSC leads to smaller training and test error. Deep-SRSC is implemented with TensorFlow(Abadi et al., 2016). The initial learning rate is set to 10 -4 , and divided by 10 at 100-th epoch and 200-th epoch, so the final learning rate is 10 -6 upon the termination of the training.

• F and • p denote the Frobenius norm and the p -norm.

Table content: <table><tr><td>2 SUPPORT REGULARIZED SPARSE CODING</td></tr><tr><td>2.1 CAPTURING LOCALLY LINEAR STRUCTURE: SUPPORT REGULARIZED SPARSE CODING</td></tr></table>

Clustering results on USPS handwritten digits database. c in the left column is the cluster number, i.e. the first c clusters of the entire data are used for clustering.

Table content: <table><tr><td>USPS # Clusters</td><td>Measure</td><td>KM</td><td>SC</td><td>Sparse Coding</td><td>2 -RSC</td><td>SRSC</td></tr><tr><td>c = 4</td><td>AC NMI</td><td>0.9243 0.7782</td><td>0.4514 0.4160</td><td>0.9869 0.9429</td><td>0.9869 0.9429</td><td>0.9880 0.9467</td></tr><tr><td>c = 6</td><td>AC NMI</td><td>0.7130 0.6845</td><td>0.4325 0.4865</td><td>0.7781 0.8507</td><td>0.7781 0.8507</td><td>0.9723 0.9135</td></tr><tr><td>c = 8</td><td>AC NMI</td><td>0.7294 0.6851</td><td>0.4227 0.4811</td><td>0.8163 0.8669</td><td>0.8163 0.8669</td><td>0.9645 0.9027</td></tr><tr><td>c = 10</td><td>AC NMI</td><td>0.6878 0.6312</td><td>0.4041 0.4765</td><td>0.8178 0.8321</td><td>0.8287 0.8398</td><td>0.8293 0.8471</td></tr></table>

Clustering results on various data sets

Table content: <table><tr><td>Data Set</td><td>Measure</td><td>KM</td><td>SC</td><td>Sparse Coding</td><td>2 -RSC</td><td>SRSC</td></tr><tr><td>COIL-20</td><td>AC NMI</td><td>0.6274 0.7533</td><td>0.3347 0.5667</td><td>0.9903 0.9879</td><td>0.9903 0.9879</td><td>0.9944 0.9933</td></tr><tr><td>COIL-100</td><td>AC NMI</td><td>0.5221 0.7633</td><td>0.2372 0.5410</td><td>0.6979 0.8837</td><td>0.6979 0.8837</td><td>0.7267 0.8876</td></tr><tr><td>UCI Gesture Phase Segmentation</td><td>AC NMI</td><td>0.3868 0.1191</td><td>0.3375 0.1300</td><td>0.4003 0.1164</td><td>0.4023 0.1164</td><td>0.4123 0.1187</td></tr></table>

Prediction error (average squared error between the predicted codes and the ground truth codes) of Deep-SRSC with different depth and different dictionary size on the test set of USPS data, using the first test setting

Table content: <table><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="3">Dictionary Size</td><td colspan="2">1-layer</td><td colspan="2">2-layer</td><td>6-layer</td><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="2">p = 100</td><td/><td colspan="2">0.06</td><td/><td>0.04</td><td>0.04</td><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="2">p = 300</td><td/><td colspan="2">0.14</td><td/><td>0.09</td><td>0.07</td><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="2">p = 500</td><td/><td colspan="2">0.24</td><td/><td>0.12</td><td>0.11</td><td/><td/><td/><td/><td/><td/></tr><tr><td/><td colspan="7">0.14 Training Error versus Epoch Number for Deep-SRSC with p=100</td><td colspan="7">0.22 Training Error versus Epoch Number for Deep-SRSC with p=300</td><td colspan="7">0.35 Training Error versus Epoch Number for Deep-SRSC with p=500</td></tr><tr><td/><td>0.12</td><td/><td/><td/><td/><td>1-layer 2-layer 6-layer</td><td/><td>0.2</td><td/><td/><td/><td/><td>1-layer 2-layer 6-layer</td><td/><td>0.3</td><td/><td/><td/><td/><td>1-layer 2-layer 6-layer</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td>0.18</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td>0.1</td><td/><td/><td/><td/><td/><td/><td>0.16</td><td/><td/><td/><td/><td/><td/><td>0.25</td><td/><td/><td/><td/><td/></tr><tr><td>Error</td><td>0.08</td><td/><td/><td/><td/><td/><td>Error</td><td>0.12 0.14</td><td/><td/><td/><td/><td/><td>Error</td><td>0.2</td><td/><td/><td/><td/><td/></tr><tr><td/><td>0.06</td><td/><td/><td/><td/><td/><td/><td>0.1</td><td/><td/><td/><td/><td/><td/><td>0.15</td><td/><td/><td/><td/><td/></tr><tr><td/><td>0.04</td><td/><td/><td/><td/><td/><td/><td>0.08</td><td/><td/><td/><td/><td/><td/><td>0.1</td><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td>0.06</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td>0.02</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>0.05</td><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td>0.04</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td>0</td><td/><td/><td/><td/><td/><td/><td>0.02</td><td/><td/><td/><td/><td/><td/><td>0</td><td/><td/><td/><td/><td/></tr><tr><td/><td>0</td><td>50</td><td>100</td><td>150</td><td>200</td><td>250</td><td>300</td><td>0</td><td>50</td><td>100</td><td>150</td><td>200</td><td>250</td><td>300</td><td>0</td><td>50</td><td>100</td><td>150</td><td>200</td><td>250</td><td>300</td></tr><tr><td/><td/><td/><td/><td>Epoch Number</td><td/><td/><td/><td/><td/><td/><td>Epoch Number</td><td/><td/><td/><td/><td/><td/><td>Epoch Number</td><td/><td/></tr></table>

Clustering results on the test set of USPS data with different dictionary size p

Table content: <table><tr><td>Dictionary Size</td><td>Measure</td><td>KM</td><td>SC</td><td>Sparse Coding</td><td>2 -RSC</td><td>SRSC</td><td>6-Layer Deep-SRSC</td></tr><tr><td>p = 100</td><td>AC NMI</td><td>0.6020 0.5522</td><td>0.3279 0.4372</td><td>0.6363 0.7011</td><td>0.6363 0.7011</td><td>0.7105 0.7068</td><td>0.7155 0.6778</td></tr><tr><td>p = 300</td><td>AC NMI</td><td>--</td><td>--</td><td>0.6408 0.7011</td><td>0.6462 0.7011</td><td>0.7225 0.7045</td><td>0.7000 0.6817</td></tr><tr><td>p = 500</td><td>AC NMI</td><td>--</td><td>--</td><td>0.6263 0.6872</td><td>0.6268 0.6898</td><td>0.6248 0.7221</td><td>0.6836 0.6537</td></tr></table>

Peer review (iclr2017):
I*d like to thank the authors for their detailed response to my questions. The paper proposes a support regularized version of sparse coding that takes into account the underlying manifold structure of the data. For this purpose, the authors augment the classic sparse coding loss with a term that encourages near by points to have similar active set. Convergence guarantees for the optimization procedure are presented. Experimental evaluation on clustering and semi-supervised learning shows the benefits of the proposed approach. The paper is well written and a nice read. The most relevant contribution of this work is to including (and optimizing) the regularization function, and not an approximation or surrogate. The authors derive a a PGD-styple iterative method and present convergence analysis for it. Thanks for the clarifications regarding the assumptions used in Section 3. It would be nice to include some of that in the manuscript. The authors also propose a fast encoding scheme for their proposed method. The authors included a new experiment in semi-supervised consists of a very interesting use (of the method and the fast approximation). While this is an interesting addition, I think that using fast encoders is not particularly novel or the main part of the work. *Converting* iterative optimization algorithms into feed-forward nets for accelerating the inference process has been done in the past (several times with quite similar problems). Is natural that this can be done, and not very surprising. Maybe would be interesting to evaluate how important is to have an architecture matching the optimization algorithm, compared to a generic network (though some of this analysis has also been performed in the past).