Title: LEARNING NON-LINEAR TRANSFORM WITH DISCRIM-INATIVE AND MINIMUM INFORMATION LOSS PRIORS

Abstract: This paper proposes a novel approach for learning discriminative and sparse representations. It consists of utilizing two different models. A predefined number of non-linear transform models are used in the learning stage, and one sparsifying transform model is used at test time. The non-linear transform models have discriminative and minimum information loss priors. A novel measure related to the discriminative prior is proposed and defined on the support intersection for the transform representations. The minimum information loss prior is expressed as a constraint on the conditioning and the expected coherence of the transform matrix. An equivalence between the non-linear models and the sparsifying model is shown only when the measure that is used to define the discriminative prior goes to zero. An approximation of the measure used in the discriminative prior is addressed, connecting it to a similarity concentration. To quantify the discriminative properties of the transform representation, we introduce another measure and present its bounds. Reflecting the discriminative quality of the transform representation we name it as discrimination power.
To support and validate the theoretical analysis a practical learning algorithm is presented. We evaluate the advantages and the potential of the proposed algorithm by a computer simulation. A favorable performance is shown considering the execution time, the quality of the representation, measured by the discrimination power and the recognition accuracy in comparison with the state-of-the-art methods of the same category.
Under review as a conference paper at ICLR 2018 a structural constraint on the dictionary or imposing a discriminative term on the sparse representations. Additionally, some works by Mairal et al. (2008); Guo et al. (2012) and Taalimi et al. (2015) consider even a joint estimation/learning of a dictionary, sparse representation, and classifier by using iterative alternating minimization strategy. The manuscripts by Bengio et al. (2012); Cai et al. (2014) and Gangeh et al. (2015) give comprehensive overview covering different approaches.
The general open issue for DDL methods is the computational complexity w.r.t. the optimal dictionary/transform learning and the discriminative encoding, since the sparse representation in the synthesis model is a solution to an inverse problem.

1. INTRODUCTION:

Learning a transform that provides sparse and discriminative representation is an active domain of research in various areas, some of which are data processing, pattern recognition, image processing, language modeling, text analysis and gene separation. A class of algorithms proposed by Kreutz-Delgado et al. (2003) ; Mairal et al. (2009) ; Bengio et al. (2012) ; Gangeh et al. (2015) ; Mairal et al. (2008) ; Jiang et al. (2011) ; Guo et al. (2012) ; Cai et al. (2014) and Liu et al. (2016) for learning discriminative sparse representations have been shown to perform well across various learning tasks. A subclass of them known as discriminative dictionary learning (DDL) Guo et al. (2012) ; Jiang et al. (2013) ; Cai et al. (2014) ; Shekhar et al. (2014) ; Xu et al. (2015) ; Liu et al. (2016) ; Bengio et al. (2012) ; Gangeh et al. (2015) ; Jiang et al. (2016) and Vu & Monga (2016) addreses the estimate of the dictionary in a supervised manner such that the representation w.r.t. words (vectors) from the resulting dictionary (vector set) is discriminative.

Most of the DDL methods synthesize the data sample k from class c, i.e, x c,k ∈ N as an approximation by a linear combination y c,k ∈ M (referred to as a sparse data representation y c,k 0 << M ) of a few words (vectors d m ), from a dictionary (vector set) D ∈ N ×M , i.e., x c,k = Dy c,k + v c,k , v c,k ∈ N , with v c,k denoting the approximation error. It is important to highlight that with the synthesis model approach the data reconstruction is addressed.

The differences between the DDL methods Guo et al. (2012) ; Jiang et al. (2013) ; Cai et al. (2014) ; Shekhar et al. (2014) ; Gangeh et al. (2015) ; Xu et al. (2015) ; Liu et al. (2016) ; Bengio et al. (2012) ; Jiang et al. (2016) and Vu & Monga (2016) are determined by the prior defined on the sparse representation and the prior defined for the relations between the sparse representations for the data samples from the same/different classes. The discrimination is enforced by replacing the prior with

1.2. APPROACH AND MOTIVATIONS:

Model Instead of addressing a synthesis model where the data reconstruction is targeted and the estimation of the discriminative representation is an inverse problem1 we present a novel, alternative approach. That is we propose non-linear transform models in the learning stage and a sparsifying transform model Rubinstein et al. (2010) , Rubinstein et al. (2013) , Rubinstein & Elad (2014) and Ravishankar & Bresler (2014) for testing. The sparsifying transform model assumes that the data sample x c,k is approximately sparsifiable under a linear transform A ∈ M ×N , i.e., Ax c,k = y c,k + z c,k , z c,k ∈ M , where y c,k is sparse y c,k 0 << M . It also represents a generalization of the analysis model Rubinstein et al. (2010; 2013) ; Ravishankar & Bresler (2014) ; Rubinstein & Elad (2014) .

The proposed non-linear transform model is an extension to the sparsifying transform model that considers additional assumptions. Both of the models used in this paper address a direct problem, where the estimation of the discriminative representation represents a low complexity constrained projection problem. Additionally, since these models have no restrictions on the transform representation to be in the column space of the dictionary (transform matrix A), they allow more freedom in modeling and imposing constraints on the transform representation2 . on the support intersection for the dissimilarity contribution between y c1,k1 and y c2,k2 .

Prior and its measure In the learning stage, central in the non-linear transform models is the novel parametric measure for a discriminative prior. It is defined on the support intersection for the transform representations. The first motivation behind the used measure is that the support intersection of the transform data allows more freedom in imposing regularization on the discriminative properties without taking into account any additional assumptions. Second, by approximating the parametric mesure with an non-parametric one the focus of the regularization is directly put on the contributing components for similarity/dissimilarity. Consider the measure (y + c1,k1 ) T y + c2,k2 + (y - c1,k1 ) T y - c2,k2 between two transform representations y c1,k1 and y c2,k2 where y c1,k1 = y + c1,k1y - c1,k1 where y + c1,k1 = max(y c1,k1 , 0) and y - c1,k1 = max(-y c1,k1 , 0). Note that

(y + c1,k1 ) T y + c2,k2 + (y - c1,k1 ) T y - c2,k2 = y + c1,k1 y + c2,k2 1 + y - c1,k1

y - c2,k2 1 captures the only contribution for the similarity (whereas y + c1,k1

y - c2,k2 1 + y - c1,k1

y + c2,k2 1 captures the only contribution for the dissimilarity) between the vectors y c1,k1 and y c2,k2 . Moreover, y T c1,k1 y c2,k2 = y c1,k1 y c2,k2 1 , only if the dissimilarity contribution -(y - c1,k1 ) T y + c2,k2 -(y + c1,k1 ) T y - c2,k2 for the vectors y c1,k1 and y c2,k2 is 0. That is y T c1,k1 y c2,k2 = (y + c1,k1

) T y + c2,k2 + (y - c1,k1 ) T y - c2,k2 -(y - c1,k1 ) T y + c2,k2 - (y + c1,k1 ) T y - c2,k2 ≤ (y + c1,k1 ) T y + c2,k2 + (y - c1,k1 ) T y - c2,k2 , now if -(y - c1,k1 ) T y + c2,k2 -(y + c1,k1 ) T y - c2,k2 is zero then y c1,k1 y c2,k2 1 = (y + c1,k1 ) T y + c2,k2 + (y - c1,k1 ) T y - c2,k2 = y T c1,k1 y c2,k2 . Third, the expectation E[ y - c1,k1 y - c2,k2 1 + y + c1,k1

y + c2,k2 1 ] captures the concentration of similarity. Therefore, it provides the possibility to define a formal notion that quantifies the discriminative properties. Fourth, (y + c1,k1 ) T y + c2,k2 + (y - c1,k1 ) T y - c2,k2 is not ambiguous w.r.t. a notion for similarity/dissimilarity between two sparse representations y c1,k1 and y c2,k2 . This is because the support intersections for the positive and the negative components

(y + c1,k1 ) T y + c2,k2 = (y + c1,k1 ) y + c2,k2 1 and (y - c1,k1 ) T y - c2,k2 = (y + c1,k1 ) T y + c2,k2 1

, respectively, are considered separately. In addition, taken into account is the strength on the support intersection, defined as y c1,k1 y c2,k2

EQUATION

2 ] captures the expected strength on the support intersection for that set. A schematic diagram of the transform and the main idea behind the proposed concept are shown in Figure 1 , a), b) and c). On Figure 1 d ), e) and f) are given illustrative examples for the support intersections between the positive and negative component of two vectors y c1,k1 and y c2,k2 in the transform domain.

A learning algorithm is presented using the proposed model with discriminative and minimum information loss priors. To quantify the discriminative properties, we introduce a measure named as discrimination power, which reflects the discriminate properties of the representation for a dataset. In addition, we present its lower and upper bounds, which depend on the parameters of the transform. On the practical side, the advantages and the potential of the proposed algorithm are demonstrated by a numerical experiments using the Extended YALE B Georghiades et al. (2001) , AR Martínez & Benavente (1998 ), Norb LeCun et al. (2004 ), Coil-20 Nene et al. (1996 ), Clatech101 LeCun et al. (2008) , UKB Nistér & Stewénius (2006) and MNIST Lecun & Cortes datasets. Under review as a conference paper at ICLR 2018 1.3 NOTATIONS A scalar variable is denoted using x, a vector is denoted by a bold, low caps symbols x, a matrix by bold, upper cap symbol A. A single element from a vector (or matrix) is denoted as x(n) (or A(m, n)). A set is denoted by a calligraphic symbol, i.e, S. The p -norm is denoted as . p and the nuclear norm as . * . The symbol represents the Hadamard product. Throughout the paper it is assumed that a set of data samples -1) as the matrix that has all the columns of X, except the column x c,k ∈ N , where

X = [X 1 , X 2 , ..., X C ] ∈ N ×L , L = CK from C classes is given and that every class c ∈ C = {1, 2, 3, ..., C} has K samples, X c = [x c,1 , x c,2 , ..., x c,K ] ∈ N ×K , x c,k ∈ N , ∀c ∈ C, ∀k ∈ K = {1, 2, ..., K}. We denote the transform data as Y = [Y 1 , Y 2 , ..., Y C ] ∈ M ×L , where Y c = [y c,1 , y c,2 , ..., y c,K ] ∈ M ×K and y c,k ∈ M . We denote X \{k∈c} = X 1 , X 2 , ..X c,\k , ...X C ∈ N ×(L

X c,\k = [x c,1 , x c,2 , ..., x c,k-1 , x c,k+1 , ..., x c,K ] ∈ N ×(K-1

) is a matrix that has all the columns of block X c , except the column x c,k , ∀c ∈ C and ∀k ∈ K. We let N = {1, 2, ..., N } and M = {1, 2, ..., M }.

2. LEARNING NON-LINEAR TRANSFORM WITH DISCRIMINATIVE AND MINIMUM INFORMATION LOSS PRIORS:

The proposed approach has two operational modes: learning and test. It considers two different models. A predefined number of non-linear transforms are used in the learning mode and one sparsifying transform is used for test time.

2.1. THE PARAMETRIC NON-LINEAR TRANSFORM MODELING:

Considering the learning mode, we assume that for every class c ∈ C there exist one non-linear transform defined by a set of parameters P c = {A ∈ M ×N , τ c ∈ M }, ∀c ∈ C3 . All nonlinear transforms described by {P 1 , ..., P C } share the linear map A and have distinct parameters τ c . One P c with τ c is related to only one class c. It is assumed that the parameters τ c are spread far apart in the transform domain. In addition, when all the non-linear transforms are applied to the corresponding class samples then the transform data samples are separable w.r.t. the different classes, in the transform domain.

As far as the non-linear transform we focus on transforms expressible by a two-steps operation, consisting of a linear mapping (step 1) followed by an element-wise non-linearity (step 2):

EQUATION

where

∀w c,k = Ax c,k ∈ M , H τc (w c,k ) = sign(w c,k ) max(|w c,k | -τ c , 0) : M → M ,

represents a non-linear thresholding function with parameters τ c ∈ M . We also have to mention that the thresholding is done with different thresholding parameters τ c (m) for the corresponding different transform dimensions m ∈ M.

At testing time we use one, common sparsifying transform defined by a set of parameters P = {A ∈ M ×N , τ 1 ∈ M } for all data samples, with a constant tresholding parameter τ . The transform matrix A is one and same for the C training and the testing models.

In the following section we describe the non-linear transform models, the proposed discriminative prior and its mesure, together with the main reason behind this particular use of non-linear transform models for learning and a sparsifying transform model for testing.

2.2. THE NON-LINEAR TRANSFORM MODEL WITH A DISCRIMINATIVE PRIOR:

The learning model This paper defines a compact description of the non-linear transform (1) by a non-linear transform model as follows:

EQUATION

where T Pc (.) : N → M is a parametric non-linear function that gives y c,k , by using the set of parameters P c . The term z c,k = Ax c,k -y c,k is the non-linear transform error vector that represents the deviation of Ax c,k from the targeted transform representation y c,k = T Pc (x c,k ) in the transform domain. Since the transform representation y c,k = T Pc (x c,k ) takes into acount a non-linearity, Ax c,k is only seen as its linear approximation. Knowing something in advance about the difference between y c,k -Ax c,k can be used in our model. However, since in advance we do not have any prior we assume that it is Gausssian like distributed. Therefore, the prior on z c,k is modeled as p(x c,k |y c,k , A) ∝ exp(-

Ax c,k -y c,k 2 2 β0

), where β 0 is a scaling parameter. Assuming additionally that the non-linear function T Pc (x c,k ) gives sparse y c,k , then we have the improper prior on y c,k , defined as p(y c,k ) ∝ exp(-

y c,k 1 β1

) where β 1 is a scaling parameter. This paper models the joint probability p(τ 1 , τ 2 , ...., τ C , y c,k ) as

EQUATION

and assumes that (A iid ) : ) where D(y c,k ; τ c ) is a parametric measure with parameter τ c . Assuming that D(y c,k ; τ c ) is determined by a relation on the support intersection between y c,k and τ c we propose the following definition of measure:

p(τ 1 , τ 2 , ...., τ C ) = c p(τ c ),

EQUATION

where

y + c,k τ + c 1 + y - c,k

τ - c 1 measures the similarity contribution on the support intersection using the positive and the negative components, y + c,k , τ + c and y - c,k , τ - c , respectively, of y c,k and τ c and y c,k τ c 2 2 measures the strength of the support intersection between y c,k and τ c . The true p(τ c ) and τ c are not known and instead of estimating them explicitly, an approximation to D(y c,k ; τ c ) is considered based only on the concentrations of the similarity on the support intersection and the expected strength of the support intersection for the transform data.

Non-parametric approximation:

We propose an approximation by sum of two expectations. The first one is the expected similarity on the support intersection for the positive and negative component between all y c,k and the coresponding sets of the transform representations Y \c that come from all classes c1 different from c, i.e., c = c1. The second is the expected strength on the support intersection between y c,k and the set of transform representations Y \c that come from all classes c1 different from c, c = c1. We define the approximation as:

c,k D(y c,k ; τ c ) ∼ D P 1 (X) + S P 2 (X)

where

EQUATION

(5)

we highlight that the transform represntations y c,k used in the approximation D P 1 (X) and S P 2 (X) are the result of applying the sparsifying transform with parameter set P to the data samples x c,k .

The m-th element y

+ c,k (m) of y + c,k is defined as y + c,k (m) = max(y c,k (m), 0) and similarly, y - c,k (m) = max(-y c,k (m), 0), ∀m ∈ M.

We also define the expected similarity using the positive and negative components of all y c,k across the transform representations Y \c that come from the same classes c as

D P 1,c (X) = c K k=1 k1∈{{1,2,...,K}\k} y + c,k y + c,k1 1 + y - c,k y - c,k1 1 . If the measure D P 1 (X)

is not used then the approximation ( 5) is most similar to the one proposed in Liu et al. (2016) .

Under review as a conference paper at ICLR 2018 By (5) a link is established between the non-linear transform models and the sparsifying transform model, or more generaly, assuming A is known, between a parametric and a non-parametric modeling view. The terms

2 ((C-1)K)(CK) c1∈{{1,2,...,C}\c} K k1=1 y - c1,k1 , 2 ((C1)K)(CK) c1∈{{1,2,...,C}\c} K k1=1 y + c1,k1 and 2 ((C1)K)(CK)

c1,c1 =c k1 y c1,k1 y c1,k1 are seen as finite sample estimates 4 5 of the positive, negative components and the Hadamard square, τ - c , τ + c and τ c τ c , respectivly, for the unknown variable τ c , ∀c ∈ C. Note that the Fisher discriminate constraint Yang et al. (2011b) , the pairwise constraint Guo et al. (2013) and the support intersection constraint Liu et al. (2016) are all approximations of a discriminative prior. However, they all have specific assumptions on the distribution of the data representation in the transform domain. The advantage of using ( 5) is that the approximation is without any prior to the probability distributions p(τ c ) and without any explicit assumption about the metric/measure, or space/manifold in the transform domain.

Given a training set X, the learning perspective w.r.t. a discriminative property is to estimate a non-linear transform models

P c = {A ∈ M ×N , τ c ∈ M } that minimize the empirical ex- pectation 1 CK c,k min 1≤c≤C D(y c,k ; τ c ) ∼ E[min 1≤c≤C D(y c,k ; τ c )].

Moreover, if the corresponding class labels for the training set X are given6 then c,k min 1≤c≤C D(y c,k ; τ c ) equals to c,k D(y c,k ; τ c ) and exactly matches the empirical expectation D P 1 (X) + S P 2 (X). The testing model Assume that the transform matrix A and the parameters τ 1 , τ 2 , ..., τ C are known, then given any data sample x c,k the transform representaton y c,k is estimated as:

EQUATION

which is euqialent to

min 1≤c1≤C min y c,k Ax c,k -y c,k 2 2 + λ 0 D(y c,k ; τ c1 ) + λ 1 y c,k 1 .

Furtheremore, if we assume that the measures D(y c,k ; τ c1 ) are zero, i.e., D(y c,k ; τ c1 ) = 0, then the discriminative prior is non-informative, in a sence that it has no influence in the models. Only then do the non-linear transforms reduce to the sparsifying transform model, since (6) reduce to: min

EQUATION

Considering the testing stage, we note that the result (5) sheds light on another view. Namely, the sparsifying transform model P = {A ∈ M ×N , λ1 ∈ M } is also seen as an approximation to the models represented by a set of parameters P c = {A ∈ M ×N , τ c ∈ M } with expected loss in the discriminative properties of the transform representations expressed by the similarity concentration measure D P 1 (X) + S P 2 (X). At the same time this measure can also be considered as an empirical risk Vapnik (1995) w.r.t. the discriminative properties, related to the generalization capabilities Vapnik (1995) and Mark (2010) of the sparsifying transform model. Note that the same model is also the simplest that approximates the non-linear transform models used in the learning stage.

2.3. THE LEARNING ALGORITHM:

In summary, the used priors are:

p(x c,k |y c,k , A) ∝ exp(- Ax c,k -y c,k 2 2 β 0 ) p(τ c , y c,k ) = p(τ c |y c,k )p(y c,k ) ∝ exp(- D(y c,k ; τ c ) β 2 ) exp(- y c,k 1 β 1 ). (8) 4 Since c1∈{{1,2,...,C}\c} k1 ( y + c,k y + c1,k1 1 + y - c,k y - c1,k1 1) = c1∈{{1,2,...,C}\c} k1 y + c1,k1 y + c,k 1 + c1∈{{1,2,...,C}\c} k1 y - c1,k1 y - c,k 1, τ - c ∼ 2 ((C-1)K)(CK) c1∈{{1,2,...,C}\c} k1 y - c1,k1 and τ + c ∼ 2 ((C-1)K)(CK) c1∈{{1,2,...,C}\c} k1 y + c1,k1 . 5 Since c1∈{{1,2,...,C}\c} k1 y c,k y c1,k1 2 2 = c1∈{{1,2,...,C}\c} k1 y c1,k1 y c1,k1 T (y c,k y c,k ), τc τc ∼ 2 ((C-1)K)(CK) c1∈{{1,2,...,C}\c} k1 y c1,k1 y c1,k1 .

Under review as a conference paper at ICLR 2018 Additionally, we have a prior on A that penalizes the information loss in order to avoid trivially unwanted matrices A, i.e., matrices that have repeated or zero rows. The prior is defined as:

EQUATION

where the A F penalty helps regularize the scale ambiguity, the log | det (A T A)| and A 2 F are functions of the singular values of A and together help regularize the conditioning of A. Assuming that the expected coherence µ 2 (A) between the rows a m of A (i.e.,

A T = [a 1 , a 2 , ..., a M ]) is defined as µ 2 (A) = 2 M (M -1) m1 =m2 |a m1 a T m2 | 2 , ∀m 1 , m 2 ∈ {1, 2, .., M }. Then AA T -I 2 F

measures the expected coherence µ 2 (A) and the 2 norm for the rows of A.

Note that the joint probability can be expressed as:

EQUATION

where

p(x c,k , y c,k , τ c |A) = p(x c,k |y c,k , A)p(τ c , |y c,k )p(y c,k ), since p(x c,k |y c,k , τ c , A) = p(x c,k |y c,k , A).

Given the available training data set X, maximizing p(x c,k , y c,k , τ c , A) over Y and A is same as minimizing the following problem:

EQUATION

where {λ 0 , λ 1 } are inversely proportional to the scaling parameters {β 2 , β 1 }. Note that the solution to ( 11) is not equivalent to the maximum a priory (MAP) solution, which is difficult to compute, as it involves integrating over the vectors y c,k . Considering the optimization perspective, the problem is not convex in the variables (Y, A). The proposed solution here is obtained by iteratively, marginally maximizing the probability p( Linear map estimation: Given the available data samples X and the corresponding transform representations Y the linear map A estimation problem reduces to:

EQUATION

where {λ 2 , λ 3 , λ 4 } are inversely proportional to the scaling parameters {β 3 , β 4 , β 5 } and we use the -close closed form solution estimated as follows: 12) has -close approximative solution as:

Proposition 1 ( -close closed form solution): Given Y ∈ M ×CK , ∀X ∈ N ×CK and M ≥ N , ∀λ 2 ≥ 0, λ 3 ≥ 0 and λ 4 ≥ 0 let the eigen value decomposition U X Σ X V T X of XX T + λ 2 I and the singular value decomposition U U X XY Σ U X XY V T U X XY of U T X XY T exist, then if and only if σ X (n) > 0, ∀n ∈ N = {1, 2, 3, ..., N }, (

EQUATION

where Discriminative encoding: Given the available data samples X and the current estimate of the transform A the discriminative representation estimation problem is formulated as

Σ A is diagonal matrix, Σ A (n, n) = σ A (n) ≥ 0 ,

(P DR ) : min Y AX -Y 2 F + λ 0 c,k D(y c,k ; τ c ) + λ 1 y c,k . (P DR ).

Even not knowing p(τ c ) or the model variables τ c we show that by the approximation (5), (P DR ) has an efficient solution. Assuming that Y \c is given, using the approximation (5), then for any sample k ∈ K from any class c ∈ C, problem (P DR ) reduces to a constrained projection problem:

EQUATION

and has a closed form solution as:

EQUATION

Under review as a conference paper at ICLR 2018 where we abuse notation to denote |y c,k | as the vector having as elements the absolute values of the corresponding elements in y c,k , is a Haddamard division,

g c = sign(max(Ax c,k , 0)) d + c + sign(max(-Ax c,k , 0)) d - c , d + c = c1 c1 =c k1 y + c1,k1 , d - c = c1 c1 =c k1 y - c1,k1 and s c = c1 c1 =c k1 y c1,k1 y c1,k1 (the proof is given in Appendix B).

We note that at convergence (which we do not prove here) we can only claim that a joint local maximum in (Y, A) of p(x c,k , y c,k , τ c , A) has been reached, even if, as in this case, each optimization step achieves the (marginal) -close and the global optimal solution, respectively.

2.4. A MEASURE FOR THE DISCRIMINATIVE PROPERTIES AND ITS BOUNDS:

This paper proposes a notion for the discriminative properties of a data set under a non-linear transform named as discrimination power, based on a measure for the relations between the concentrations D P 1,c (X) and D P 1 (X).

Proposition 2: The discrimination power for any dataset Y ∈ M ×CK under a non-linear transform with parameter set P is defined as:

EQUATION

where

B M = {A t ∈ M ×M , 0 ∈ M }, A t = I and > 0 is a small positive constant.

Remark 1: The advantage of this measure is that it logarithmically signifies the difference between D P 1,c (X) and D P 1 (X) 7 . The definition about the discrimination power of the original data set X, but, now under a model with a parameter set B N = {A o ∈ N ×N , 0 ∈ N } where A o = I is equivalent to the one defined for I t . We denote it as I o . The bound on the discrimination power is given by the following result.

Theorem 1: The discrimination power for any data set X ∈ N ×CK under any non-linear transform with parameter set P is bounded as:

EQUATION

)

The proof is given in Appendix D 8 .

At first the resulting bounds might look counterintuitive since the loss of information seems to increase the discrimination power. This fact is true, however, up to a certain limit. Therefore, it is important to distinguish two main conclusions. First, for any model with a set of parameters P for which there is no loss of information, that is, no thresholding, the only condition for the increase in the discrimination power is D

EQUATION

Y) holds true it will be possible to increase the discrimination power. Moreover, there is a trade-off between the increase in discrimination power as a result of the loss of information as consequence of the non-linear thresholding operation. 7 Assume we have a discriminative prior defined as p(τc|y c,k ) ∝ exp(-

τ + c y + c,k 1 + τ - c y - c,k 1 β 2

) and p(υc|y c,k ) ∝ exp(-

υ + c y + c,k 1 + υ - c y - c,k 1 β 2

), where τc and υc are unknown parameters. Then the difference D P 1 ,c (X) -D P 1 (X) between D P 1 ,c (X) and D P 1 (X) actually represents a finite sample approximation to a discriminative density since it approximates the density log

p(τc|y c,k ) p(υc|y c,k ) , i.e., D P 1 ,c (X) -D P 1 (X) ∼ -log p(τc,y c,k ) p(υc,y c,k ) and -log p(τc,y c,k ) p(υc,y c,k ) = D(τc, y c,k ) -D(υc, y c,k ) = τc + y + c,k 1 + τc - y - c,k 1 -( υc + y + c,k 1 + υc -y - c,k 1).

8 In Appendix C we also provide a sensitivity analysis that complements our result since it is related to the notion about the discriminative quality of the representation. The result in Appendix C also gives an informationtheoretic interpretation and information-geometric perspective about the model and the similarity concentration measure without the need of strict conditions for regularity, i.e., smoothness of the manifolds.

Under review as a conference paper at ICLR 2018 C 

3. NUMERICAL EXPERIMENTS:

The numerical experiments are summarized in two different parts. In the first series of the experiments the properties of the learned map A for the proposed algorithm are investigated. We evaluate the computational efficiency, as run time t e [min], the conditioning number C n (A) = λmax λmin , the expected mutual coherence µ(A) and the discrimination power across several databases for a learned non-linear transforms having different dimensionality. A comparison between the discrimination power uder different transforms is presented. The discriminatation power is estimated in the original domain, after transform by a random matrix (having Gaussian random samples as entries and transform dimension of M = 19000) and after a learned non-linear transform having transform dimension M = 19000 without and with discriminative prior, denoted as I 0 , I RT , I ST * and I N T , respectively. The second part evaluates a comparison of the discrimination power between the proposed algorithm and different DDL methods Ramirez et al. (2010) , Yang et al. (2011a) , Vu et al. (2015) and Vu & Monga (2016) . This comparison considers a setup where the used data sets are divided into a training and test set. Moreover, the learning is performed on the training set and the evaluation is performed on the test set. In the same series of experiments the recognition accuracy for the two data sets is also computed and compared. Nistér & Stewénius (2006) and MNIST (D7) Lecun & Cortes. All the images from the respective datasets were downscaled to resolutions 21 × 21, 32 × 28, 24 × 24, 20 × 25, 21 × 21, 20 × 25, 28 × 28, respectively, and are normalized to unit variance. Considering the used implementation of the algorithm we note that the singular value decomposition for a large matrix has high computational complexity. However, A -Â, where Â is estimated as a solution in the transform update step, can be considered as an proximal operator Parikh & Boyd (2014) for the gradient of the objective (12). Additionally, instead of using all of the available data samples X, a subset of them might be used. Therefore, one simple on-line variant for the update of A w.r.t. a subset of the available training set has the form A t+1 = A t -ρ(A t -Ât ) with ρ a predefined step size. In the numerical experiments we use the on-line variant of the algorithm (the convergence analysis for this variant of the algorithm is left for future work) were we used a baches of sizes equal to 10%-12% of the total amount of the available training data. The parameters λ 0 and λ 1 are set such that the resulting non-linear transform representation has a very small number of non-zeros w.r.t. the transform dimension. In the experiments this number is set to be 15. The rest of the parameters are set as {λ 2 , λ 3 , λ 4 } = {1000000, 1000000, 1000000}. The algorithm is initialized with a random matrix having i.i.d. Gaussian (zero mean, variance one) entries and is terminated after the 28th iteration. The results are obtained as the average of 3 runs. An implementation presented in Vu & Monga (2016) 

z c,k M 2 2 ] = E[ Ax c,k -y c,k 2 2 M

] and the discrimination power on the Extended Yale B and MNIST databases, respectively, on the transform representation Y, obtained by using a non-linear transform T P at different dimensionality M . sparse codes for the respective supervised dictionary learning methods DDL Ramirez et al. (2010) , Yang et al. (2011a) , Vu et al. (2015) and Vu & Monga (2016) .

Linear map properties, the similarity concentrations and the discrimination power The conditioning number and the expected coherence for the learned transforms are shown on Table 1 . The learned transforms for all the databases have good conditioning numbers and low expected coherence. The running time t e , measured in minutes, and the number of used dimensions, denoted as M are also shown in Table 1 . The learned transforms for all the data sets have relatively low execution time, regardless of the very high transform dimension M = 19000. The discrimination power is significantly increased in the transform domain I N T compared to the one in the original domain I O and is higher than I ST * and I RT .The evolution of the similarity concentrations

C1 = D B M 1,c (Y) and C2 = D B M 1 (Y)

, their ratio C1/C2 and the discrimination power log(C1/C2) = I t for subsets of the used databases after applying a non-linear transform with transform dimension M = 19000 is shown in Figure 2 . It is important to note that the similarity concentrations

C1 = D B M 1 ,c (Y) and

Under review as a conference paper at ICLR 2018

C2 = D B M 1 (Y)

are decreasing, meaning that there is a loss of information. However how this loss effects the resulting similarity concentration is crucial for the discrimination properties. As shown in Figure 2 , the slope of decrease for C2 is stronger. Therefore, the discrimination power increases per iteration. For the Coil-20 (D4) database there is a fluctuation. This is explained by the fact that during learning we used a small number of data samples from the same database and that in the data there is high variability. The conditioning number and the expected coherence for the learned transforms for all the databases at different transform dimensions 1150, 2200, 3250, 4300, 5350, 6400, 7450, 8500, 9550, 10600, 11650, 12700, 13750, 14800, 15850, 16900, 17950, 19000} are shown in Figure 3 . We see that the value of both the conditioning number and the coherence is reducing and it converges to common values. This confirms the effectiveness of the conditioning and the coherence constraints. The similarity concentrations

M ∈ Q = {100,

C1 = D B M 1,c (Y) and C2 = D B M 1 (Y)

, their ratio C1/C2 and the discrimination power log(C1/C2) = I t for a subsets of the used databases after applying a non-linear transform having transform dimensions M ∈ Q is shown in Figure 4 . We can see similar behavior as previous, that is, C1 and C1 are decreasing, but, the slope of decrease for C2 is stronger. Therefore, the discrimination power increases as the transform dimension increases.

NT vs DDL discrimination power and recognition performance:

The proposed method is compared with DLSIRamirez et al. ( 2010), F DDL Yang et al. (2011a) , COP AR Vu et al. (2015) and LRSDL Vu & Monga (2016) . Half of the data samples from the data set Extended YALE B, sampled at random are used for learning and the remaining other half are used for evaluation. Considering the MNIST database the training set is used for learning and the test set is used for both evaluating the discrimination power and the recognition accuracy. We compute both the discrimination power and the recognition accuracy on a subsets from the test sets. The dictionary size (transform dimension M ) is set to be equal to {150, 75, 1515, 3825, 570, 150, 300}for the used databases, respectivly, in all of the comparing algorithms. The discrimination power of the comparing methods is denoted as I DLSI , I F DDL , I COP AR and I LRSDL . The recognition results for the methods DLSI, F DDL, COP AR and LRSDL on the data sets Extended YALE B and MNIST were not computed here, rather we use the best reported result form the respective papers Ramirez et al. (2010) , Yang et al. (2011a) , Vu et al. (2015) and Vu & Monga (2016) . Considering the proposed algorithm the non-linear transform was learned for the transform dimensions M = {100, 500, 1500, 4000} and M = {1000, 4000, 6000, 12000}, respectively, for the used data sets. After the transform was learned, the transform data samples were computed for the respective training and test sets. Then, the transform training data samples were used as features to learn a linear SVM classifier in oneagainst-all regime. The results are shown in Table 2 a), b) and c). The discrimination power of the proposed non-linear transform is higher that the discrimination power of the comparing methods. The recognition accuracy is higher for high dimensionality of the proposed method and outperforms the DDL methods at dimensionality 4000 and 12000. In Figure 5 and Figure 6 are shown the recognition accuracy and the expected loss measured as E[

z c,k M 2 2 ] = E[ Ax c,k -y c,k 2 2

M:

] as a linear function of the discrimination power evaluated at transform dimension M = {100, 500, 1500, 4000} and M = {1000, 4000, 6000, 12000}. It is interesting to highlight that as the discrimination power at different transform dimension increases it also increases the accuracy of recognition. Moreover, the results on these two data sets show that this increase is approximately linear. On the other hand the expected loss decreases as the discrimination power at different transform dimensions increases.

4. CONCLUSION:

This paper presented a novel approach for learning discriminative and sparse representations. A novel discriminative prior was proposed and the properties of the models with the prior were investigated. A low complexity learning algorithm was presented. The preliminary results w.r.t. the introduced measures and the recognition accuracy on the used databases showed promising performance. We showed that it is possible to increase the discrimination power with information loss. Moreover, we highlight that when expanding to high dimensional space with non-linear transforms how the loss of information reflects the similarity concentrations is crucial for the discriminative properties. A study on the recognition capabilities for other databases are our next steps. An extention considering the sufficient conditions for increase in discrimination power in the transform domain, under supervised and unsupervised case, together with an analysis for a deep architecture where per single layer we have a non-linear transforms are left for our future work.

Under review as a conference paper at ICLR 2018 Let the sign of y c1,k1 , i.e. sign(y c1,k1 ) be equal to the sign of sign(q c1,k1 ), and Hadamar multiply from the left side by sign(q c1,k1 ) then we have

X T P --→ Y ↓ ↓ log D B N 1 ,c (X) D B N 1 (X)+ log D P 1 ,c (X) D P 1 (X)+ = log D B M 1 ,c (Y) D B M 1 (Y)+ ↓ ↓ I o I t

EQUATION

note that sign(q c1,k1 ) sign(q + c1,k1 ) = sign(q + c1,k1 ) and that sign(q c1,k1 ) sign(q - c1,k1 ) = sign(-q - c1,k1 ), theretofore we have

EQUATION

since the magnitude might be only positive we have that

|y c1,k1 | (1 + 2λ 0 s c ) = max(|q c1,k1 | - λ 0 (sign(q + c1,k1 ) d + c + sign(-q - c1,k1 ) d - c ) -λ 1 1, 0). Denote g c = (sign(q + c1,k1 ) d + c + sign(-q - c1,k1 ) d - c

) then the closed form solution to ( 49) is:

EQUATION

which completes the proof

APPENDIX C. SENSITIVITY ANALYSIS AND INTERPRETATIONS:

The similarity concentration measure provides possibility to measure the discriminative properties, their deviation, increase (or decrease) and the corresponding relations between different non-linear transform models across one domain or different domains, thereby quantifying their quality w.r.t. the discriminative properties.

C.1 SENSITIVITY ANALYSIS W.R.T. THE SIMILARITY CONCENTRATION MEASURES:

An illustration about the definition of discriminative power given by a diagram is shown in Figure 7 .

To measure the ability for an increase in discriminative properties by a non-linear transform9 we first have to define a notion for the discriminative properties on a data set under different nonlinear transform models. Therefore, first we introduce the "special" base models and then analyze the properties of the similarity concentration measures under the change in model parameter and the relation between the base model and the proposed non-linear transform model defined by a parameter set P = {A ∈ M ×N , τ ∈ M }. A base original model provides a possibility to compare it with any other non-linear transform model with parameters

P = {A ∈ M ×N , τ ∈ M + }. Additionally, note that for B M = {A t = I ∈ D M , τ = 0 ∈ M } we have that D B M 1 ,c (Y) = D P 1,c (X) and that D B M 1 (Y) = D P 1 (X).

It implies that the similarity concentrations can be analyzed as a function in the original domain under model P or in the transform domain under model B M . The main relations considering the preservation of change in the similarity concentration between two models, defined not necessary in the same domain are stated by Lemma 1.

Lemma 1: The non-linear transform model (2) totally preserves the information in the change for the similarity concentration for a data set X w.r.t. a small change in the parameters of the models B N , B M and P if δ o * = 0 and δ t * = 0 as

EQUATION

where

EQUATION

Under review as a conference paper at ICLR 2018

The proof is given in Appendix C.2.

The terms z c,k represent the non-linear transform error vectors that appear in the model Ax c,k = y c,k + z c,k as a result of applying an element-wise non-liner operation H τ to Ax c,k , i.e., y c,k = H τ (Ax c,k ). As an example in the sparsifying transform model z c,k is the "loss of information", that is the information about the values of the elements in Ax c,k that are discarded. The terms δ o and δ t correlate the errors z c,k with the original data x c1,k1 and transform data y c1,k1 , respectively. Note that if there is no loss of information (in the earlier example it means that there is no thresholding and just a simple linear transform model is used) then δ o = 0 and δ t = 0. Moreover, δ o and δ t bear important information about the discriminative properties in the transform domain.

The terms 

EQUATION

This relation exists independently for:

∂D B N 1 ,c (X) ∂Ao | Ao=I and ∂D B N 1 (X) ∂Ao

| Ao=I , nevertheless, we will define the summarized and the independent versions. Therefore, first we define

∂J 1 (X) ∂Ao | Ao=I = ∂D B N 1 ,c (X) ∂Ao | Ao=I + ∂D B N 1 (X) ∂Ao | Ao=I and ∂J 1 (Y) ∂At | At=I = ∂D B N 1 ,c (Y) ∂At | At=I + ∂D B N 1 (Y) ∂At | At=I and rewrite (R1) as A ∂J (X) ∂Ao | Ao=I -δ o = ∂D P 1 ,c (X) ∂A + ∂D P 1 (X) ∂A

, then replace 

EQUATION

EQUATION

where V =AX

EQUATION

Under review as a conference paper at ICLR 2018

The expressions (R4) actually relate the metric in the original domain under the model B N to the induced metric in the transform domain for the model B M , with induction done by the model P with parameter set {A ∈ M ×N , τ ∈ M + }. Moreover, the model P might describe a transform domain with a non-smooth manifold. Since the manifolds of the original and the transform domain under the models B N and B M are smooth the analysis of their relations reveals insights about the relation between the manifolds under the models B N and P. The terms

∂J 1 (Z) ∂At | At=I and ∂J 1 (Y;Z) ∂At

| At=I carry out the information about the breaks and the discontinuities of the regularity and smoothness in the manifold induced by the model P. Also we note that

EQUATION

R4) in information geometry is seen as change of coordinates on a manifold, where the intrinsic properties of curvature remain unchanged under different parametrization.

APPENDIX C.2:

Note that for the model P t we have that

EQUATION

EQUATION

The first order derivative of the divergence D P t 1 (x; g) w.r.t. the parameter A is:

EQUATION

we assume that the threshold parameter τ is chosen such that the vector |Ax| -τ (or for any other q, the vector |Aq| -τ ) has least one non-zero element, then

EQUATION

and

EQUATION

combining ( 62) and ( 63) we have that

EQUATION

where 

EQUATION

EQUATION

note that at A o = I, P t 0 = B N and we have that

∂D B N 1 (x; g) ∂A o | Ao=I = xg T + gx T (68)

Also for the model P t 0 = {A t , τ = 0} we have that y t =T P t 0 (A t y) = sign(A t y) max(|A t y| -0, 0) = max(A t y -0, 0) -max(-A t y -0, 0), q t =T P t 0 (A t q) = sign(A t q) max(|A t q| -q, 0) = max(A t q -0, 0) -max(-A t q -0, 0).

(69):

The first order derivative of the divergence D P t 0 1 (y; q) w.r.t A t is: ∂D P t 0 1 (y; q) ∂A t = y t q T + q t y T , (70) note that at A t = I, P t 0 = B M and we have that

EQUATION

Consider the following a non-linear transform learned with one value for parameter λ for all the databases. Since all the databases have different variabilities and the amount of available data is different, this result suggest that per different database there should be different optimal values for the parameter λ.

EQUATION

EQUATION

Under review as a conference paper at ICLR 2018

The results about the ratio C1/C2 between the similarity concentrations C1 = D B M 1 ,c (Y) and C2 = D B M 1 (Y) and the discrimination power log(C1/C2) = I t on the Extanded-Yale-B and the MNIST data sets after applying a non-linear transform with transform dimensions M = {100, 500, 1500, 4000} and M = {1000, 4000, 6000, 12000}, and varying the thresholding parameter τ = λ1 are shown in Figure 10 . We again used 70 different values for the parameter λ, sampled uniformly from the interval 0, (max 1≤c≤C,1≤k≤K max 1≤m≤M |a T m x c,k |) . The results were obtained using a non-linear transforms learned with optimally choose values (by using crossvalidation) of the parameter λ for the two different databases. As expected, we can see that the extreme points of the ratio between the * -norms C1 and C2 of the similarity concentrations and the discrimination power is around the optimal values of the parameter τ = λ1.

:

Note that a solution to an inverse problem has a high computational complexity if the dimensionality of the dictionary (transform matrix) or the data dimensionality is high.

In fact it allows modeling other non-linearity also, i.e., ReLu can be modeled as a transform representation.

That is the number of non-linear transforms equals the number of classes.

Note that if the labels are not given then the unsupervised case can also be addressed by using a likelihood measure between a sample and the rest of the available samples, with the possibility to be defined in the original or in the transform domain.

Instead of using the term non-liner transform model as defined by (1) or (2) for short we just use the term model.

Figures and Tables:

Figure 1: a) Data samples X c , c ∈ {1, 2, 3, 4} from four different classes, b) given a k-th data sample x c,k from class c, the non-linear transform is represented as two step operation: linear mapping Ax c,k (step 1) followed by an element wise thresholding function y c,k = T Pc (Ax c,k ) (step 2), c) the transform data samples Y c , c ∈ {1, 2, 3, 4}, d) two transform representations y c1,k1 and y c2,k2 , e) the resulting Hadamar products y + c1,k1 y + c2,k2 and y - c1,k1 y - c2,k2 on the support intersection for the similarity contribution and f) the resulting Hadamar products y + c1,k1 y - c2,k2 and y - c1,k1 y + c2,k2

x c,k , y c,k , τ c , A) over Y and A which is equivalent to maximizing the conditional densities p(y c,k |x c,k , τ c , A) and p(A|x c,k , y c,k , τ c ), respectively. Meaning that at one iterating step one of the variables Y or A is fixed and w.r.t. the other the problem (11) is minimized. The following describes the iterating steps that consist of linear map estimation (maximizing p(A|x c,k , y c,k , τ c )) and discriminative encoding (maximizing p(y c,k |x c,k , τ c , A)).

and σ A (n) are solutions to quartic polynomials with global minimums (the proof is given in Appendix A.2).

Figure 2: The evolution of the similarity concentrations C1 = D B M 1,c (Y) and C2 = D B M 1 (Y), their ratio C1/C2 and the discrimination power log(C1/C2) = I t during the learning of the non-linear transform with transform dimension M = 19000.C n (A) µ(A) t e [min] D1 2.21 0.03 5.10 D2 1.80 0.02 5.45 D3 2.12 0.02 6.55 D4 0.08 0.02 8.92 D5 6.01 0.01 12.8 D6 33.1 0.02 30.1 D7 1.60 0.02 5.00

Figure 3: The conditioning number C n (A) = λmax λmin and the expected mutual coherence µ(A) for the learned linear transform A at different dimensionality M ∈ Q.

Figure 7: The relation for the definition of the discrimination power in the original and the transform domain under the base models B N and B M .

Figure 8: The original and the transform domains under a non-linear transforms with a set of parameters B N , P and B M , note that for T B N and T B M the original and the transform domains are the same.

of the similarity concentrations under infinitesimally small change of the parameter A from the model P. The terms Ao=I have dual interpretation. Assuming metric A o = I, then the first one is considered as a change of the similarity concentrations under infinitesimally small change of the space metric, or equivalently under small metric perturbation. Conversely, assuming the data samples are distributed under a Gaussian distribution with parameters identity covariance matrix and zero mean,i.e. x c,k ∼ N (µ = 0, Σ = I), then ∂D B N 1 ,c(X) ∂Ao | Ao=I and ∂D B N 1 (X) ∂Ao | Ao=I represent the change of the similarity concentrations under small change in the assumption away from a Gaussian distribution. Equation (R1) relates the base transform for the original domain B N with any arbitrary transform defined in the original domain P. The relation (R2) is a result about the preservation of change in the similarity concentration between two models B M and P defined on two different domains. Whereas (R3) gives the preservation of change in the similarity concentration between the error in the transform domain. The next result highlights the relation between: the linear projection (by the linear map A that appears in the model P) of the change in the similarity concentration under the model B N in the original domain and the change of the similarity concentration under the model B M in the transform domain.

R2) by the same term in (R1), use (R3), reorder and we have the following result. Lemma 2: For fixed τ any non-linear transform model (2) preservers the information in the change of similarity concentrations w.r.t. a small change in A by

)∀m ∈ M.Under review as a conference paper at ICLR 2018 Similarity, note that for the model P o 0 = {A o , τ = 0} we have thatx o =T P o 0 (A o x) = sign(A o x) max(|A o x| -0, 0) = max(A o x -0, 0) -max(-A o x -0, 0), g o =T P o 0 (A o g) = sign(A o g) max(|A o g| -g, 0) = max(A o g -0, 0) -max(-A o g -0, 0). g) w.r.t A o is:

Figure 9: The ratio C1/C2 of the similarity concentrations C1 = D B M 1,c (Y) and C2 = D B M 1 (Y) and the discrimination power log(C1/C2) = I t for randomly chosen subsets from all of the used databases under a non-linear transform with transform dimension M = 19000 and varying thresholding parameter τ = λ1.

Figure 10: The ratio of the similarity concentrations similarity concentrations C1 = D B M 1,c (Y) and C2 = D B M 1 (Y) and the discrimination power log(C1/C2) = I t for the Extended Yale B and MNIST databases under non-linear transforms having different transform dimension M and varying thresholding parameter τ = λ1.

where β 2 is a scaling parameter. By the assumption in subsection 2.1, τ c1 are spread far apart in the transform domain. Therefore, a minimum over D(y c,k ; τ c1 ) ensures that y c,k in the transform domain will be located to the closest τ c1 w.r.t. to the mesure D(y c,k ; τ c1 ). Moreover, given the class label c using (3) and (A iid ) the model for the discriminative prior reduces to p(τ c |y c,k ) ∝ exp(-

Table content: <table><tr><td>D(y c,k ;τc)</td></tr><tr><td>β2</td></tr></table>

The conditioning number C n (A) = λmax λmin and the expected mutual coherence µ(A) for the learned transform A. The execution time t e [min] in minutes of the proposed algorithm for 28 iterations at the transform domain dimensionality M = 19000.

Table content: <table><tr><td/><td/><td/><td/><td>I O</td><td>I RT</td><td>I ST  *</td><td>I N T</td></tr><tr><td>D1</td><td>2.21</td><td>0.03</td><td>5.10</td><td>0.03</td><td>0.18</td><td>0.68</td><td>1.98</td></tr><tr><td>D2</td><td>1.80</td><td>0.02</td><td>5.45</td><td>0.02</td><td>0.10</td><td>1.30</td><td>1.79</td></tr><tr><td>D3</td><td>2.12</td><td>0.02</td><td>6.55</td><td>0.00</td><td>0.01</td><td>0.71</td><td>1.61</td></tr><tr><td>D4</td><td>0.08</td><td>0.02</td><td>8.92</td><td>0.08</td><td>0.61</td><td>0.89</td><td>1.89</td></tr><tr><td>D5</td><td>6.01</td><td>0.01</td><td>12.8</td><td>0.01</td><td>0.16</td><td>1.02</td><td>2.12</td></tr><tr><td>D6</td><td>33.1</td><td>0.02</td><td>30.1</td><td>0.06</td><td>0.53</td><td>1.36</td><td>3.36</td></tr><tr><td>D7</td><td>1.60</td><td>0.02</td><td>5.00</td><td>0.13</td><td>0.63</td><td>1.06</td><td>1.96</td></tr></table>

was used to learn the dictionaries and estimate the a) The discrimination power for the methods DLSIRamirez et al. (2010), F DDL Yang et al. (2011a), COP AR Vu et al. (2015) and LRSDL Vu & Monga (2016) and the proposed method N T , b) and c) The recognition results on the Extended Yale B and MNIST database. The recognition results and the discrimination power on the Extended Yale B and MNIST databases, respectively, using a non-linear transform with different dimensionality M and linear SVM classifier on top of the transform representation.

Table content: <table><tr><td colspan="9">Under review as a conference paper at ICLR 2018</td><td/></tr><tr><td/><td colspan="2">I DLSI</td><td/><td>D1 0.71</td><td>D7 0.67</td><td colspan="2">DLSI</td><td colspan="3">D1 Acc. [%] 96.5</td><td>DLSI</td><td>D7 Acc. [%] 98.74</td></tr><tr><td/><td colspan="3">I F DDL</td><td>0.87</td><td>0.63</td><td colspan="2">F DDL</td><td colspan="3">97.5</td><td>F DDL</td><td>96.31</td></tr><tr><td/><td colspan="4">I COP AR 0.57</td><td>0.54</td><td colspan="2">COP AR</td><td colspan="3">98.3</td><td>COP AR</td><td>96.41</td></tr><tr><td/><td colspan="3">I LRSDL</td><td>0.42</td><td>0.40</td><td colspan="2">LRSDL</td><td colspan="3">98.7</td><td>LRSDL</td><td>-</td></tr><tr><td/><td colspan="2">I N T</td><td/><td>0.98</td><td>0.81</td><td>N T</td><td/><td colspan="3">99.7</td><td>N T</td><td>99.02</td></tr><tr><td/><td/><td/><td/><td>a)</td><td/><td/><td colspan="2">b)</td><td/><td>c)</td></tr><tr><td colspan="2">100</td><td colspan="2">E-YALE-B</td><td/><td/><td/><td/><td colspan="3">100</td><td>MNIST</td></tr><tr><td/><td>98</td><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td colspan="2">98</td></tr><tr><td>Accuracy</td><td>92 94 96</td><td/><td/><td/><td/><td/><td/><td>Accuracy</td><td colspan="2">96</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td colspan="2">94</td></tr><tr><td/><td>90</td><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td>0.2 88</td><td/><td>0.4</td><td>0.6</td><td>0.8</td><td>1</td><td>1.2</td><td/><td colspan="2">1.2 92</td><td>1.3</td><td>1.4</td><td>1.5</td></tr><tr><td/><td/><td/><td/><td colspan="2">Discriminative power</td><td/><td/><td/><td/><td>Discriminative power</td></tr><tr><td/><td>M</td><td/><td colspan="3">100 500 1.5K</td><td>4K</td><td/><td/><td colspan="2">M</td><td>1K</td><td>4K</td><td>6K</td><td>12K</td></tr><tr><td colspan="7">Acc. [%] 89.1 94.3 97.4 99.7</td><td/><td colspan="3">Acc. [%] 92.49 94.24 96.01 99.02</td></tr><tr><td/><td>I t</td><td/><td colspan="3">0.21 0.73 0.93</td><td>1.23</td><td/><td/><td colspan="2">I t</td><td>1.18</td><td>1.35</td><td>1.42</td><td>1.55</td></tr><tr><td colspan="3">Figure 5: 0.2 0 1 2 3 Expected loss per dimension ×10 -4</td><td>0.4</td><td colspan="2">0.6 Discriminative power 0.8</td><td colspan="2">1 E-YALE-B 1.2</td><td colspan="2">Expected loss per dimension</td><td>1.2 0 1 2 3 ×10 -5</td><td>Discriminative power 1.3 1.4</td><td>1.5 MNIST</td></tr><tr><td/><td colspan="2">M</td><td/><td colspan="3">100 500 1.5K</td><td>4K</td><td/><td/><td>M</td><td>1K</td><td>4K</td><td>6K</td><td>12K</td></tr><tr><td>E[</td><td colspan="7">z c,k M ][10 -3 ] 0.3 0.03 0.014 0.008 I t 0.21 0.73 0.93 1.23</td><td>E[</td><td colspan="2">z c,k M ][10 -4 ] 0.31 0.082 0.06 0.028 I t 1.18 1.35 1.42 1.55</td></tr><tr><td colspan="6">Figure 6: The expected loss E[</td><td/><td/><td/><td/></tr></table>

Peer review (iclr2018):
 Overview: This paper proposes a method for learning representations using a “non-linear transform”. Specifically, the approach is based on the form: Y =~ AX, where X is the original data, A is a projection matrix, and Y is the resulting representation. Using some assumptions, and priors/regularizers on Y and A, a joint objective is derived (eq. 10), and an alternating optimization algorithm is proposed (eq. 11 and 14). Both objective and algorithm use approximations due to hardness of the problem. Theoretical and empirical results on the quality and properties of the representation are presented. Disclaimer: this is somewhat outside my area of expertise, so this is a rather high-level review. I have not thoroughly checked proofs and claims. Comments: -I found the presentation quality to be rather poor, making it hard to fully understand and evaluate the approach. In particular, the motivation and approach are not clear (sec. 1.2), making it hard to understand the proposed method. There is no explicit formulation, instead there are references to other models (e.g., sparsifying transform model) and illustrative figures (fig. 1 and 2). Those are useful following a formal definition, but cannot replace it. The separation between positive and negative elements of the representation is not motivated and explained in a footnote although it seems central to the proposed approach. - The paper is 17 pages long (24 pages with the appendix), so I had to skim through some parts. Due to the extensive scope, perhaps a journal submission would be more appropriate. Minors: - Vu & Monga 2016b and 2016c are the same. - p. 1: meaner => manner - p. 1: refereed => referred - p. 1: “a structural constraints”; p. 2: “a low rank constraints”, “a pairwise constraints”; p. 4: “a similarity concentrations”, “a numerical experiments”, and others... - p. 2, 7: therms => terms - p. 2: y_{c_1,k_2} => y_{c_1,k_1}? - p. 3, 4: “a the” - p. 5: “an parametric” - p. 8: ether => either - Other typos… the paper needs proofreading.