Title: ON OPTIMALITY CONDITIONS FOR AUTO-ENCODER SIGNAL RECOVERY

Abstract: Auto-Encoders are unsupervised models that aim to learn patterns from observed data by minimizing a reconstruction cost. The useful representations learned are often found to be sparse and distributed. On the other hand, compressed sensing and sparse coding assume a data generating process, where the observed data is generated from some true latent signal source, and try to recover the corresponding signal from measurements. Looking at auto-encoders from this signal recovery perspective enables us to have a more coherent view of these techniques. In this paper, in particular, we show that the true hidden representation can be approximately recovered if the weight matrices are highly incoherent with unit 2 row length and the bias vectors takes the value (approximately) equal to the negative of the data mean. The recovery also becomes more and more accurate as the sparsity in hidden signals increases. Additionally, we empirically also demonstrate that auto-encoders are capable of recovering the data generating dictionary when only data samples are given.

1. INTRODUCTION:

Recovering hidden signal from measurement vectors (observations) is a long studied problem in compressed sensing and sparse coding with a lot of successful applications. On the other hand, autoencoders (AEs) (Bourlard and Kamp, 1988) are useful for unsupervised representation learning for uncovering patterns in data. AEs focus on learning a mapping x → h → x, where the reconstructed vector x is desired to be as close to x as possible for the entire data distribution. What we show in this paper is that if we consider x is actually generated from some true sparse signal h by some process (see section 3), then switching our perspective on AE to analyze h → x → ĥ shows that AE is capable of recovering the true signal that generated the data and yields useful insights into the optimality of model parameters of auto-encoders in terms of signal recovery. In other words, this perspective lets us look at AEs from a signal recovery point of view where forward propagating x recovers the true signal h. We analyze the conditions under which the encoder part of an AE recovers the true h from x, while the decoder part acts as the data generating process. Our main result shows that the true sparse signal h (with mild distribution assumptions) can be approximately recovered by the encoder of an AE with high probability under certain conditions on the weight matrix and bias vectors. Additionally, we empirically show that in a practical setting when only data is observed, optimizing the AE objective leads to the recovery of both the data generating dictionary W and the true sparse signal h, which together is not well studied in the auto-encoder framework, to the best of our knowledge.

2. SPARSE SIGNAL RECOVERY PERSPECTIVE:

While it is known both empirically and theoretically, that useful features learned by AEs are usually sparse (Memisevic et al., 2014; Nair and Hinton, 2010; Arpit et al., 2016) . An important question that has not been answered yet is whether AEs are capable of recovering sparse signals, in general. This is an important question for Sparse Coding, which entails recovering the sparsest h that approximately satisfies x = W T h, for any given data vector x and overcomplete weight matrix W. However, since this problem is NP complete (Amaldi and Kann, 1998) , it is usually relaxed to solving an expensive optimization problem (Candes et al., 2006; Candes and Tao, 2006) ,

arg min h x -W T h 2 + λ h 1 (1)

where W ∈ R m×n is a fixed overcomplete (m > n) dictionary, λ is the regularization coefficient, x ∈ R n is the data and h ∈ R m is the signal to recover. For this special case, Makhzani and Frey (2013) analyzed the condition under which linear AEs can recover the support of the hidden signal.

The general AE objective, on the other hand, minimizes the expected reconstruction cost

EQUATION

for some reconstruction cost L, encoding and decoding activation function s e (.) and s d (.), and bias vectors b e and b d . Notice however, in the case of auto-encoders, the activation functions can be non-linear in general, in contrast to the sparse coding objective. In this paper we consider linear decoding activation s d because it is a more general case 1 . In addition, in case of AEs we do not have a separate parameter h for the hidden representation corresponding to every data sample x individually. Instead, the hidden representation for every sample is a parametric function of the sample itself. This is an important distinction between the optimization in eq. 1 and our problem -the identity of h in eq. 1 is only well defined in the presence of 1 regularization due to the overcompleteness of the dictionary. However, in our problem, we assume a true signal h generates the observed data x as x = W T h + b d , where the dictionary W and bias vector b d are fixed. Hence, what we mean by recovery of sparse signals in an AE framework is that if we generate data using the above generation process, then can the estimate ĥ = s e (Wx + b e ) indeed recover the true h for some activation functions s e (.), and bias vector b e ? And if so, what properties of W, b e , s e (.) and h lead to good recovery? However, when given an x and the true overcomplete W, the solution h to x = W T h is not unique. Then the question arises about the possibility of recovering such an h. However, as we show, recovery using the AE mechanism is strongest when the signal h is the sparsest possible one, which from compressed sensing theory, guarantees uniqueness of h if W is sufficiently incoherent 2 .

3. DATA GENERATION PROCESS:

We consider the following data generation process:

x = W T h + b d + e (3)

where x ∈ R n is the observed data, b d ∈ R n is a bias vector, e ∈ R n is a noise vector, W ∈ R m×n is the weight matrix and h ∈ R m is the true hidden representation (signal) that we want to recover. Throughout our analysis, we assume that the signal h belongs to the following class of distribution, Assumption 1. Bounded Independent Non-negative Sparse (BINS): Every hidden unit h j is an independent random variable with the following density function:

EQUATION

where f c (.) can be any arbitrary normalized distribution bounded in the interval (0, l maxj ], mean µ hj , and δ 0 (.) is the Dirac Delta function at zero. As a short hand, we say that h j follows the distribution BINS(p, f c , µ h , l max ). Notice that E hj [h j ] = p j µ hj .

The above distribution assumption fits naturally with sparse coding, when the intended signal is non-negative sparse. From the AE perspective, it is also justified based on the following observation.

In neural networks with ReLU activations (i.e. f c (x) = max(0, x)), hidden unit pre-activations have a Gaussian like symmetric distribution (Hyvärinen and Oja, 2000; Ioffe and Szegedy, 2015) . If we assume these distributions are mean centered 3 , then the hidden units' distribution after ReLU has a large mass at 0 while the rest of the mass concentrates in (0, l max ] for some finite positive l max , because the pre-activations concentrate symmetrically around zero. As we show in the next section, ReLU is indeed capable of recovering such signals. On a side note, the distribution from assumption 1 can take shapes similar to that of Exponential or Rectified Gaussian distribution 4 (which are generally used for modeling biological neurons) but is simpler to analyze. This is because we allow f c (.) to be 1 Linear decoding activation covers numerical range for commonly used non-linear decoding activations 2 Coherence is defined as max W i ,W j ,i =j any arbitrary normalized distribution. The only restriction assumption 1 has is that to be bounded. However, this does not change the representative power of this distribution significantly because: a) the distributions used for modeling neurons have very small tail mass; b) in practice, we are generally interested in signals with upper bounded values.

The generation process considered in this section (i.e. eq. 3 and assumptions 1) is justified because:

1. This data generation model finds applications in a number of areas (Yang et al., 2009; Kavukcuoglu et al., 2010; Wright et al., 2009) . Notice that while x is the measurement vector (observed data), which can in general be noisy, h denotes the actual signal (internal representation) because it reflects the combination of dictionary (W T ) atoms involved in generating the observed samples and hence serves as the true identity of the data.

2. Sparse distributed representation (Hinton, 1984) is both observed and desired in hidden representations. It has been empirically shown that representations that are truly sparse (i.e. large number of true zeros) and distributed usually yield better linear separability and performance (Glorot et al., 2011; Wright et al., 2009; Yang et al., 2009) .

Decoding bias (b d ): Consider the data generation process (exclude noise for now)

x = W T h + b d .

Here b d is a bias vector which can take any arbitrary value but similar to W, it is fixed for any particular data generation process. However, the following remark shows that if an AE can recover the sparse code (h) from a data sample generated as x = W T h, then it is also capable of recovering the sparse code from the data generated as x = W T h + b d and vice versa.

Remark 1. Let x 1 = W T h where x 1 ∈ R n , W ∈ R m×n and h ∈ R m . Let x 2 = W T h + b d where b d ∈ R n is a fixed vector. Let ĥ1 = s e (Wx 1 + b) and ĥ2 = s e (Wx 2 + b -Wb d ). Then ĥ1 = h iff ĥ2 = h.

Thus without any loss of generality, we will assume our data is generated from x = W T h + e.

4. SIGNAL RECOVERY ANALYSIS:

We analyse two separate classes of signals in this category-continuous sparse, and binary sparse signals that follow BINS. For notational convenience, we will drop the subscript of b e and simply refer this parameter as b since it is the only bias vector (we are not considering the other bias b d due to remark 1). The Auto-Encoder signal recovery mechanism that we analyze throughout this paper is defined as, Definition 1. Let a data sample x ∈ R n be generated by the process x = W T h + e where W ∈ R m×n is a fixed matrix, e is noise and h ∈ R m . Then we define the Auto-Encoder signal recovery mechanism as ĥse (x; W, b e ) that recovers the estimate ĥ = s e (Wx + b e ) where s e (.) is an activation function.

4.1. BINARY SPARSE SIGNAL ANALYSIS:

First we consider the noiseless case of data generation, Theorem 1. (Noiseless Binary Signal Recovery): Let each element of h follow BINS(p, δ 1 , µ h , l max ) and let ĥ ∈ R m be an auto-encoder signal recovery mechanism with Sigmoid activation function and bias b for a measurement vector

EQUATION

)

where a ij = W T i W j , δ = ln( δ 1-δ ) and W i is the i th row of the matrix W cast as a column vector. Analysis: We first analyse the properties of the weight matrix W that results in strong recovery bound. Notice the terms (δ + p i a ii ) 2 and (δ + (1 -p i )a ii ) 2 need to be as large as possible, while simultaneously, the term m j=1,j =i a 2 ij needs to be as close to zero as possible. For the sake of analysis, lets set 5 δ = 0 (achieved when δ = 0.5). Then our problem gets reduced to maximizing the ratio

(aii) 2 m j=1,j =i a 2 ij = Wi 4 m j=1,j =i (W T i Wj ) 2 = Wi 2 m j=1,j =i Wj 2 cos 2 θ ij

, where θ ij is the angle between W i and W j . From the property of coherence, if the rows of the weight matrix are highly incoherent, then cos θ ij is close to 0. Again, for the ease of analysis, lets replace each cos θ ij with a small positive number . Then

(aii) 2 m j=1,j =i a 2 ij ≈ Wi 2 2 m j=1,j =i Wj 2 = 1 2 m j=1,j =i Wj 2 / Wi 2 .

Finally, since we would want this term to be maximized for each hidden unit h i equally, the obvious choice for each weight length W i (i ∈ [m]) is to set it to 1. Finally, lets analyse the bias vector. Notice we have instantiated each element of the encoding bias b i to take valuej a ij p j . Since p j is essentially the mean of each binary hidden unit h i , we can say that b

i = -j a ij E hj [h j ] = -W T i W T E h [h] = -W T i E h [x].

Signal recovery is strong for binary signals when the recovery mechanism is given by

EQUATION

where the rows of W are highly incoherent and each hidden weight has length ones ( W i 2 = 1), and each dimension of data x is approximately uncorrelated (see theorem 3). Now we state the recovery bound for the noisy data generation scenario.

Proposition 1. (Noisy Binary Signal Recovery): Let each element of h follow BINS(p, δ 1 , µ h , l max ) and let ĥ ∈ R m be an auto-encoder signal recovery mechanism with Sigmoid activation function and bias b for a measurement vector x = W T h + e where e ∈ R n is any noise vector independent of h.

EQUATION

)

where

a ij = W T i W j , δ = ln( δ 1-δ

) and W i is the i th row of the matrix W cast as a column vector.

We have not assumed any distribution on the noise random variable e and this term has no effect on recovery (compared to the noiseless case) if the noise distribution is orthogonal to the hidden weight vectors. Again, the same properties of W lead to better recovery as in the noiseless case. In the case of bias, we have set each element of the bias b

i -j a ij p j -W T i E e [e] ∀i ∈ [m]. Notice from the definition of BINS, E hj [h j ] = p j . Thus in essence, b i = -j a ij E hj [h j ] -W T i E e [e]. Expanding a ij , we get, b i -W T i W T E h [h] -W T i E e [e] = -W T i E h [x]

. Thus the expression of bias is unaffected by error statistics as long as we can compute the data mean. In this section, we will first consider the case when data (x) is generated by linear process x = W T h + e, and if W and encoding bias b have certain properties, then the signal recovery bound ( hĥ ) is strong. We will then consider the case when data generated by a non-linear process x = s d (W T h + b d + e) (for certain class of functions s d (.)) can be recovered as well by the same mechanism. For deep non-linear networks, this means that forward propagating data to hidden layers, such that the network parameters satisfy the required conditions, implies each hidden layer recovers the true signal that generated the corresponding data. We have moved all the proofs to appendix for better readability.

4.2. CONTINUOUS SPARSE SIGNAL RECOVERY:

Theorem 2. (Noiseless Continuous Signal Recovery): Let each element of h ∈ R m follow BINS(p, f c , µ h , l max ) distribution and let ĥReLU (x; W, b) be an auto-encoder signal recovery mechanism with Rectified Linear activation function (ReLU) and bias b for a measurement vector

x ∈ R n such that x = W T h. If we set b i -j a ij p j µ hj ∀i ∈ [m], then ∀ δ ≥ 0, Pr 1 m ĥ -h 1 ≤ δ ≥ 1 - m i=1   e -2 (δ+ j (1-p j )(lmax j -2p j µ h j ) max(0,a ij )) 2 j a 2 ij l 2 max j +e -2 (δ+ j (1-p j )(lmax j -2p j µ h j ) max(0,-a ij )) 2 j a 2 ij l 2 max j   (9)

where a i s are vectors such that

EQUATION

)

W i is the i th row of the matrix W cast as a column vector.

Analysis::

We first analyze the properties of the weight matrix that results in strong recovery bound. We find that for strong recovery, the terms

(δ + j (1 -p j )(l maxj -2p j µ hj ) max(0, a ij )) 2 and (δ+ j (1-p j )(l maxj -2p j µ hj ) max(0, -a ij ))

2 should be as large as possible, while simultaneously, the term j a 2 ij l 2 maxj needs to be as close to zero as possible. First, notice the term (1 -p j )(l maxj -2p j µ hj ). Since µ hj < l maxj by definition, we have that both terms containing (1 -p j )(l maxj -2p j µ hj ) are always positive and contributes towards stronger recovery if p j is less than 50% (sparse), and becomes stronger as the signal becomes sparser (smaller p j ). Now if we assume the rows of the weight matrix W are highly incoherent and that each row of W has unit 2 length, then it is safe to assume each a ij (∀i, j ∈ [m]) is close to 0 from the definition of a ij and properties of W we have assumed. Then for any small positive value of δ, we can approximately say

(δ+ j (1-pj )(lmax j -2pj µ h j ) max(0,aij )) 2 j a 2 ij l 2 max j ≈ δ 2 j a 2 ij l 2 max j

where each a ij is very close to zero. The same argument holds similarly for the other term. Thus we find that a strong signal recovery bound would be obtained if the weight matrix is highly incoherent and all hidden vectors are of unit length.

In the case of bias, we have set each element of the bias b

i -j a ij p j µ h j ∀i ∈ [m]. Notice from the definition of BINS, E hj [h j ] = p j µ hj . Thus in essence, b i = -j a ij E hj [h j ]. Expanding a ij , we get b i = -W T i W T E h [h] + E hi [h i ] = -W T i E h [x] + E hi [h i ].

The recovery bound is strong for continuous signals when the recovery mechanism is set to

EQUATION

and the rows of W are highly incoherent and each hidden weight has length ones ( W i 2 = 1). 

EQUATION

)

where a i s are vectors such that

EQUATION

)

W i is the i th row of the matrix W cast as a column vector.

Notice that we have not assumed any distribution on variable e, which denotes the noise. Also, this term has no effect on recovery (compared to the noiseless case) if the noise distribution is orthogonal to the hidden weight vectors. On the other hand, the same properties of W lead to better recovery as in the noiseless case. However, in the case of bias, we have set each element of the bias b

i -j a ij p j µ h j -W T i E e [e] ∀i ∈ [m]. From the definition of BINS, E hj [h j ] = p j µ hj . Thus b i = -j a ij E hj [h j ] -W T i E e [e]. Expanding a ij , we get, b i -W T i W T E h [h] + E hi [h i ] - W T i E e [e] = -W T i E h [x] + E hi [h i ].

Thus the expression of bias is unaffected by error statistics as long as we can compute the data mean (i.e. the recovery is the same as shown in eq. 11).

4.3. PROPERTIES OF GENERATED DATA:

Since the data we observe results from the hidden signal given by x = W T h, it would be interesting to analyze the distribution of the generated data. This would provide us more insight into what kind of pre-processing would ensure stronger signal recovery. Theorem 3. (Uncorrelated Distribution Bound): If data is generated as

x = W T h where h ∈ R m has covariance matrix diag(ζ), (ζ ∈ R + m ) and W ∈ R m×n (m > n)

is such that each row of W has unit length and the rows of W are maximally incoherent, then the covariance matrix of the generated data is approximately spherical (uncorrelated) satisfying,

EQUATION

where

Σ = E x [(x -E x [x])(x -E x [x]

) T ] is the covariance matrix of the generated data.

Analysis: Notice that for any vector v ∈ R m , m v 2 2 ≥ v 2 1 , and the equality holds when each element of the vector v is identical. Data x generated using a maximally incoherent dictionary W (with unit 2 row length) as x = W T h guarantees x is highly uncorrelated if h is uncorrelated with near identity covariance. This would ensure the hidden units at the following layer are also uncorrelated during training. Further the covariance matrix of x is identity, if all hidden units have equal variance. This analysis acts as a justification for data whitening where data is processed to have zero mean and identity covariance matrix. Notice that although the generated data does not have zero mean, the recovery process (eq. 11) subtracts data mean and hence it does not affect recovery.

4.4. CONNECTIONS WITH EXISTING WORK:

Auto-Encoders (AE): Our analysis reveals the conditions on parameters of an AE that lead to strong recovery of h (for both continuous and binary case), which ultimately implies low data reconstruction error. However, the above arguments hold for AEs from a recovery point of view. Training an AE on data may lead to learning of the identity function. Thus usually AEs are trained along with a bottle-neck to make the learned representation useful. One such bottle-neck is the de-noising criteria given by,

J DAE = min W,b x -W T s e (Wx + b) 2 (15)

where s e (.) is the activation function and x is a corrupted version of x. It has been shown that the Taylor's expansion of DAE (Theorem 3 of Arpit et al., 2016) has the term

m j,k=1 j =k ∂hj ∂aj ∂h k ∂a k (W T j W k ) 2 .

If we constrain the lengths of the weight vectors to have fixed length, then this regularization term minimizes a weighted sum of cosine of the angle between every pair of weight vectors. As a result, the weight vectors become increasingly incoherent. Hence we achieve both our goals by adding one additional constraint to DAE-constraining weight vectors to have unit length. Even if we do not apply an explicit constraint, we can expect the weight lengths to be upper bounded from the basic AE objective itself, which would explain the learning of incoherent weights due to the DAE regularization.On a side note, our analysis also justifies the use of tied weights in auto-encoders.

Sparse Coding (SC): SC involves minimizing x -W T h 2 using the sparsest possible h. The analysis after theorem 2 shows signal recovery using the AE mechanism becomes stronger for sparser signals (as also confirmed experimentally in section 5). In other words, for any given data sample and weight matrix, as long as the conditions on the weight matrix and bias are met, the AE recovery mechanism recovers the sparsest possible signal; which justifies using auto-encoders for recovering sparse codes (see Henaff et al., 2011; Makhzani and Frey, 2013; Ng, 2011 , for work along this line). Independent Component Analysis(ICA): ICA (Hyvärinen and Oja, 2000; Arora et al., 2012) assumes we observe data generated by the process x = W T h where all elements of the h are independent and W is a mixing matrix. The task of ICA is to recover both W and h given data. This data generating process is precisely what we assumed in section 3. Based on this assumption, our results show that 1) the properties of W that can recover such independent signals h; and 2) auto-encoders can be used for recovering such signals and weight matrix W. k-Sparse AEs : Makhzani and Frey (2013) propose to zero out all the values of hidden units smaller than the top-k values for each sample during training. This is done to achieve sparsity in the learned hidden representation. This strategy is justified from the perspective of our analysis as well. This is because the PAC bound (theorem 2) derived for signal recovery using the AE signal recovery mechanism shows we recover a noisy version of the true sparse signal. Since the noise in each recovered signal unit is roughly proportional to the original value, de-noising such recovered signals can be achieved by thresholding the hidden unit values (exploiting the fact that the signal is sparse). This can be done either by using a fixed threshold or picking the top k values. Data Whitening: Theorem 3 shows that data generated from BINS and incoherent weight matrices are roughly uncorrelated. Thus recovering back such signals using auto-encoders would be easier if we pre-process the data to have uncorrelated dimensions.

5. EMPIRICAL VERIFICATION:

We empirically verify the fundamental predictions made in section 4 which both serve to justify the assumptions we have made, as well as confirm our results. We verify the following: a) the optimality of the rows of a weight matrix W to have unit length and being highly incoherent for AE signal recovery; b) effect of sparsity on AE signal recovery; and c) in practice, AE can recover not only the true sparse signal h, but also the dictionary W that used to generate the data.

5.1. OPTIMAL PROPERTIES OF WEIGHTS AND BIAS:

Our analysis on signal recovery in section 4 (eq. 11) shows signal recovery bound is strong when a) the data generating weight matrix W has rows of unit 2 length; b) the rows of W are highly incoherent; c) each bias vector element is set to the negative expectation of the pre-activation; d) signal h has each dimension independent. In order to verify this, we generate N = 5, 000 signals h ∈ R m=200 from BINS(p=0.02,f c =uniform, µ h =0.5,l max =1) with f c (.) set to uniform distribution for simplicity. We then generate the corresponding 5, 000 data sample x = cW T h ∈ R 180 using an incoherent weight matrix W ∈ R 200×180 (each element sampled from zero mean Gaussian, the columns are then orthogonalized, and 2 length of each row rescaled to 1; notice the rows cannot be orthogonal). We then recover each signal using,

EQUATION

where c and ∆b are scalars that we vary between [0.1, 2] and [-1, +1] respectively. We also generate N = 5, 000 signals h ∈ {0, 1} m=200 from BINS(0.02,δ 1 , 0.02,1) with f c (.) set to Dirac delta function at 1. We then generate the corresponding 5, 000 data sample x = cW T h ∈ R 180 following the same procedure as for the continuous signal case. The signal is recovered using

EQUATION

)

where σ is the sigmoid function. 

EQUATION

where we set to 0.1 for continuous signals and 0 for binary case, 1(.) is the indicator operator, ĥi j denotes the j th dimension of the recovered signal corresponding to the i th true signal and,

w h i j = 0.5 p if h i j > 0 0.5 1-p if h i j = 0 (19)

The error is weighted with w h i j so that the recovery error for both zero and non-zero h i j s are penalized equally. This is specially needed in this case, because h i j is sparse and a low error can also be achieved by trivially setting all the recovered ĥi j s to zero. Along with the incoherent weight matrix, we also generate data separately using a highly coherent weight matrix that we get by sampling each element randomly from a uniform distribution on [0, 1] and scaling each row to unit length. According to our analysis, we should get least error for c = 1 and ∆b = 0 for the incoherent matrix while the coherent matrix should yield both higher recovery error and a different choice of c and b (which is unpredictable). The error heat maps for both continuous and binary recovery6 are shown in fig. 1 . For the incoherent weight matrix, we see that the empirical optimal is precisely c = 1 and ∆b = 0 (which is exactly as predicted) with 0.21 and 0.0 APRE for continuous and binary recovery, respectively. It is interesting to note that the binary recovery is quite robust with the choice of c and ∆b, which is because 1) the recovery is denoised through thresholding, and 2) the binary signal inherently contains less information and thus is easier to recover. For the coherent weight matrix, we get 45.75 and 32.63 APRE instead (see fig. 5 ). We also experiment on the noisy recovery case, where we generate the data using incoherent weight matrix with c = 1 and ∆b = 0. For each data dimension we add independent Gaussian noise with mean 100 with standard deviation varying from 0.001 to 1. Both signal recovery schemes are quite robust against noise (see fig. 2 ). In particular, the binary signal recovery is very robust, which conforms with our previous observation.

5.2. EFFECT OF SPARSITY ON SIGNAL RECOVERY:

We analyze the effect of sparsity of signals on their recovery using the mechanism shown in section 4. In order to do so, we generate incoherent matrices using two different methods-Gaussian7 and orthogonal (Saxe et al., 2013) . In addition, all the generated weight matrices are normalized to have unit 2 row length. We then sample signals and generate data using the same configurations as mentioned in section 5.1; only this time, we fix c = 1 and ∆b = 0, vary hidden unit activation probability p in [0.02, 1], and duplicate the generated data while adding noise to the copy, which we sample from a Gaussian distribution with mean 100 and standard deviation 0.05. According to our analysis, noise mean should have no effect on recovery so the mean value of 100 shouldn't have any effect; only standard deviation affects recovery. We find for all weight matrices, recovery error reduces with increasing sparsity (decreasing p, see fig. 3 ). Additionally, we find that both recovery are robust against noise. We also find the recovery error trend is almost always lower for orthogonal weight matrices, especially when the signal is sparse. 8 Recall theorem 2 suggests stronger recovery for more incoherent matrices. So we look into the row coherence of W ∈ R m×n sampled from Gaussian and Orthogonal methods with m = 200 and varying n ∈ [100, 300]. We found that orthogonal initialized matrices have significantly lower coherence even though the orthogonalization is done column-wise (see fig. 6 .). This explains significantly lower recovery error for orthogonal matrices in figure 3 . 

5.3. RECOVERY OF DATA DICTIONARY:

We showed the conditions on W and b for good recovery of sparse signal h. In practice, however, one does not have access to W, in general. Therefore, in this section, we empirically demonstrate that AE can indeed recover both W and h through optimizing the AE objective. We generate 50, 000 signals h ∈ R m=200 with the same BINS distribution as in section 5.1. The data are then generated as x = W T h using an incoherent weight matrix W ∈ R 200×180 (same as in section 5.1). We then recover the data dictionary Ŵ by:

Ŵ = arg min W E x x -W T s e (W(x -E x [x])) 2 ,

where

EQUATION

Notice that although given sparse signal h the data dictionary W is unique (Hillar and Sommer, 2015) , there are m! number of equivalent solutions for Ŵ, since we can permute dimension of h in AE. To check if the original data dictionary is recovered, we therefore pair up the rows of W and Ŵ by greedily selecting the pairs that result in the highest dot product value. We then measure the goodness of the recovery by looking at the values of all the paired dot products. In addition, since we know the pairing, we can calculate APRE to evaluate the quality of recovered hidden signal. As can be observed from fig. 4 , by optimizing the AE objective we can recover the original data dictionary W (almost all of the cosine distances are 1). The final achieved 1.61 and 0.15 APRE for continuous and binary signal recovery, which is a bit less than what we achieved in section 5.1. However, one should note that for this set of experiments we only observed data x and no other information regarding W is exposed. Not surprisingly, we again observed that the binary signal recovery is more robust as compared to the continuous counterpart, which may attribute to its lower information content. We also did experiments on noisy data and achieved similar performance as in section 5.1 when the noise is less significant (see supplementary materials for more details). These results strongly suggests that AEs are capable of recovering the true hidden signal in practice.

6. CONCLUSION:

In this paper we looked at the sparse signal recovery problem from the Auto-Encoder perspective and provide novel insights into conditions under which AEs can recover such signals. In particular, 1) from the signal recovery stand point, if we assume that the observed data is generated from some sparse hidden signals according to the assumed data generating process, then, the true hidden representation can be approximately recovered if a) the weight matrices are highly incoherent with unit 2 row length, and b) the bias vectors are as described in equation 11 (theorem 2) 9 . The recovery also becomes more and more accurate with increasing sparsity in hidden signals. 2) From the data generation perspective, we found that data generated from such signals (assumption 1) have the property of being roughly uncorrelated (theorem 3), and thus pre-processing the data to have uncorrelated dimensions may encourage stronger signal recovery. 3) Given only measurement data, we empirically show that the AE reconstruction objective recovers the data generating dictionary, and hence the true signal h. 4) These conditions and observations allow us to view various existing techniques, such as data whitening, independent component analysis, etc., in a more coherent picture when considering signal recovery.

Appendix: On Optimality Conditions for Auto-Encoder Signal Recovery

1 PROOFS Remark 1. Let x 1 = W T h where x 1 ∈ R n , W ∈ R m×n and h ∈ R m . Let x 2 = W T h + b d where b d ∈ R n is a fixed vector. Let ĥ1 = s e (Wx 1 + b) and ĥ2 = s e (Wx 2 + b -Wb d ). Then ĥ1 = h iff ĥ2 = h. Proof: Let ĥ1 = h. Thus h = s e (Wx 1 + b). On the other hand, ĥ2 = s e (Wx 2 + b -Wb d ) = s e (WW T h + Wb d + b -Wb d ) = s e (WW T h + b) = s e (Wx 1 + b) = h.

The other direction can be proved similarly.

Theorem 1. Let each element of h follow BINS(p, δ 1 , µ h , l max ) and let ĥ ∈ R m be an auto-encoder signal recovery mechanism with Sigmoid activation function and bias b for a measurement vector

EQUATION

)

where

a ij = W T i W j , δ = ln( δ 1-δ

) and W i is the i th row of the matrix W cast as a column vector.

Proof. Notice that,

EQUATION

and from definition 1,

EQUATION

Thus,

EQUATION

Notice that Pr(σ

EQUATION

Let T j = E hj e taij (hj -pj ) . Then,

EQUATION

Let e g(t) T j , thus,

g(t) = -tp j a ij + ln(1 -p j + p j e taij ) =⇒ g(0) = 0 (27) g (t) = -p j a ij + p j a ij e taij 1 -p j + p j e taij =⇒ g (0) = 0 (28) g (t) = p j (1 -p j )a 2 ij e taij (1 -p j + p j e taij ) 2

(29)

EQUATION

(31)

Setting g (t) = 0, we get t * = 1 aij ln(

1-pj pj ). Thus, g (t) ≤ g(t * ) = a 2 ij 4

. By Taylor's theorem, ∃c ∈ [0, t]∀t > 0 s.t.,

EQUATION

Thus we can upper bound T j as,

T j ≤ e t 2 a 2 ij 8 (33)

Hence we can write Pr(z i ≥ δ ) as

EQUATION

On the other hand, notice Pr(σ(-

j a ij h j -b i ) ≥ δ h i = 1) = Pr(-j a ij h j -b i ≥ ln( δ 1-δ ) h i = 1) = Pr(-z i ≥ δ h i = 1). Pr(-z i ≥ δ h i = 1) ≤ E h [e -tzi ] e tδ =

E h e -t j =i aij (hj -pj )-t(1-pi)aii e tδ (35) = E h j =i e -taij (hj -pj ) e t(δ +(1-pi)aii)

(36)

EQUATION

Let T j = E hj e -taij (hj -pj ) . Then we can similarly bound Pr(-z i ≥ δ ) by effectively flipping the sign of a ij 's in the previous derivation,

Pr(-z i ≥ δ ) ≤ j =i T j e t(δ +aii(1-pi)) = j =i e t 2 a 2 ij 8 e t(δ +aii(1-pi)) = e t 2 j =i a 2 ij 8 -t(aii(1-pi)+δ ) (38)

Minimizing both 34 and 38 with respect to t and applying union bound, we get,

Pr(| ĥi -h i | ≥ δ) ≤ (1 -p i )e -2(a ii p i +δ ) 2 j =i a 2 ij + p i e -2(a ii (1-p i )+δ ) 2 j =i a 2 ij (39)

Since the above bound holds for all i ∈ [m], applying union bound on all the units yields the desired result.

Proposition 1. Let each element of h follow BINS(p, δ 1 , µ h , l max ) and let ĥ ∈ R m be an autoencoder signal recovery mechanism with Sigmoid activation function and bias b for a measurement vector x = W T h + e where e ∈ R n is any noise vector independent of h.

EQUATION

)

where a ij = W T i W j , δ = ln( δ 1-δ ) and W i is the i th row of the matrix W cast as a column vector.

Proof. Notice that,

EQUATION

and from definition 1,

EQUATION

Thus,

EQUATION

Notice that Pr(σ( j a ij h j +b i +W T i e) ≥ δ h i = 0) = Pr( j a ij h j +b i +W T i e ≥ ln( δ 1-δ ) h i = 0). Let z i = j a ij h j + b i + W T i e and δ = ln( δ 1-δ ). Then,

setting b i = -E h [ j a ij h j ] - W T i E e [e]

=j a ij p j , using Chernoff's inequality on random variable h, for any t > 0,

Pr(z i ≥ δ h i = 0) ≤ E h [e tzi ] e tδ -tW T i (e-Ee[e]) =

E h e t j =i aij (hj -pj )-tpiaii e tδ -tW T i (e-Ee[e]) = E h j =i e taij (hj -pj ) e t(δ -tW T i (e-Ee[e])+piaii) = j =i E hj e taij (hj -pj ) e t(δ -tW T i (e-Ee[e])+piaii) (46) Setting δ := δ -W T i (e -E e [e]), we can rewrite the above inequality as

EQUATION

Since the above inequality becomes identical to equation 25, the rest of the proof is similar to theorem 2.

Theorem 2. Let each element of h ∈ R m follow BINS(p, f c , µ h , l max ) distribution and let ĥReLU (x; W, b) be an auto-encoder signal recovery mechanism with Rectified Linear activation function (ReLU) and bias b for a measurement vector

EQUATION

)

where a i s are vectors such that

a ij = W T i W j if i = j W T i W i -1 if i = j (49)

W i is the i th row of the matrix W cast as a column vector.

Proof. From definition 1 and the definition of a ij above, ĥi = max{0,

EQUATION

The above inequality is obtained by ignoring the positive terms that depend on the condition |z i | > δ and marginalizing over h i . For any t > 0, using Chernoff's inequality,

EQUATION

Setting b i =j a ij µ j , where

EQUATION

Let T j = E hj e taij (hj -µj ) . Then,

EQUATION

where f c (a, b, µ h ) denotes any arbitrary distribution in the interval (a, b] with mean µ h . If a ij ≥ 0, let α = -µ j and β = l maxj -µ j which essentially denote the lower and upper bound of h j -µ j . Then,

EQUATION

Proposition 2. Let each element of h follow BINS(p, f c , µ h , l max ) distribution and let ĥ ∈ R m be an auto-encoder signal recovery mechanism with Rectified Linear activation function and bias b for a measurement vector x ∈ R n such that x = W T h + e where e is any noise random vector independent of h.

EQUATION

)

where a i s are vectors such that

EQUATION

)

W i is the i th row of the matrix W cast as a column vector.

Proof. Recall that, ĥi = max{0,

j a ij h j + h i + W T i e + b i } (81) ĥi -h i = max{-h i , j a ij h j + W T i e + b i } (82) Let z i = j a ij h j + b i + W T i e.

Then, similar to theorem 2, conditioning upon z i ,

EQUATION

For any t > 0, using Chernoff's inequality for the random variable h,

EQUATION

)

Setting b i = -j a ij µ j -W T i E e [e]

, where µ

EQUATION

Setting δ := δ -W T i (e -E e [e]), we can rewrite the above inequality as

EQUATION

Since the above inequality becomes identical to equation 57, the rest of the proof is similar to theorem 2.

Theorem 3. (Uncorrelated Distribution Bound): If data is generated as x = W T h where h ∈ R m has covariance matrix diag(ζ), (ζ ∈ R + m ) and W ∈ R m×n (m > n) is such that each row of W has unit length and the rows of W are maximally incoherent, then the covariance matrix of the generated data is approximately spherical (uncorrelated) satisfying,

EQUATION

where

Σ = E x [(x -E x [x])(x -E x [x]

) T ] is the covariance matrix of the generated data.

Proof. Notice that,

EQUATION

Thus,

E x [(x -E x [x])(x -E x [x]) T ] = E h [(W T h -W T E h [h])(W T h -W T E h [h]) T ] (93) = E h [W T (h -E h [h])(h -E h [h]) T W] (94) = W T E h [(h -E h [h])(h -E h [h]) T ]W (95)

Substituting the covariance of h as diag(ζ), For noisy signal recovery we add independent Gaussian noise to data with mean 100 and standard deviation ranging from 0.01 to 0.2. Note that the data is normally within the range of[-1, 1], so the noise is quite significant when we have a standard deviation > 0.1. It is clear that even in noisy case AE can recover the dictionary (see fig. 7 ). However, the recovery is not very strong when the noise is large > 0.1 for continous signals, which is because 1) the precise value in this case is continous and thus is more influenced by the noise, 2) the dictionary recovery is poor, which result poor signal recovery. On the other hand, the recovery is robust in case of recovering binary signals. Similar results were found on the APRE of recovered hidden signals. The reason for more robust recovery for binary signal is that 1) the information content is lower and 2) we binarize the recovered hidden signal by thresholding it, which further denoised the recovery. When optimizing the AE objective for binary

EQUATION

:

Setting δ = 0.5 is not such a bad choice after all because for binary signals, we can recover the exact true signal with high probability by simply binarize the signal recovered by Sigmoid with some threshold.

We use 0.55 as the threshold to binarize the recovered signal using sigmoid function.

Gaussian and Xavier (Glorot and Bengio, 2010) initialization becomes identical after weight length normalization

notice the rows of W are not orthogonal for overcomplete filters, rather the columns are orthogonalized, unless W is undercomplete

For binary recovery, the bias equation is described in 6

Figures and Tables:

Figure 1: Error heatmap showing optimal values of c and ∆b for recovering continous (left) and binary (right) signal using inchoherent weights.

Figure 3: Effect of signal sparseness on continuous (left) and binary (right) signal recovery. Noise in parenthesis indicate the generated data was corrupted with Gaussian noise. Sparser signals are recovered better.

96) Thus, Σ -αI 2 F = tr (W T diag(ζ)W -αI)(W T diag(ζ)W -αI) T (97) = tr W T diag(ζ)WW T diag(ζ)W + α 2 I -2αW T diag(ζ)W(98)Using the cyclic property of trace,Σ -αI 2 F = tr WW T diag(ζ)WW T diag(ζ) + α 2 I -2αWW T diag(ζ) matrix is maximally incoherent, using Welch bound, we have that, µ ∈ m-n n(m-1) , 1 .Plugging the lower bound of µ (maximal incoherence) for any fixed m and n into the above bound yields, the recovery error (APRE) for signals generated with coherent weight matrix, and as expected the recovery result is poor and the values of c and ∆b are unpredictable. The minimum average percentage recovery error we got for continous signal is 45.75, and for binary signal is 32.63.

Figure 5: Error heatmap showing optimal values of c and ∆b for recovering continous (left) and binary (right) signal using coherent weights.

Figure 6: Coherence of orthogonal and Gaussian weight matrix with varying dimensions.

Peer review (iclr2018):
 This papers proposes to analyze auto-encoders under sparsity constraints of an underlying signal to be recovered. Based on concentration inequality, the reconstruction provided for a simple class of functions is guaranteed to be accurate in l1 norm with high probability. The proof techniques are classical, but the results seem novel as far as I know. As an open question, could the results be given for other lp norms, in particular for infinity-norm? Indeed, this is a privileged norm for support recovery. Presentation issues: - section should be Section when stating for instance "section 1". Idem for eq, equation, assumption... - bold fonts for vectors are randomly used: some care should be given to harmonizing symbols fonts. - equations should be cited with brackets References issues: - harmonize citations: if you add first name for some authors add it for all references: why writing Roland Makhzani and J. Wright? - Candes -> Cand.`es - Consider citing "Sparse approximate solutions to linear systems", Natarajan 1995 when mentioning Amaldi and Kann 1998. Specific comments: page 1: - hasn*t -> has not. page 2: - "activation function": at this stage s_e and s_d are just functions. What is the "activation" refers to? Also a clarification on the space they act on should be stated. Idem for b_e and b_d. - "the identity of h in eq. 1 is only well defined in the presence of l1 regularization due to the over-completeness of the dictionary" : this is implicitly stating the uniqueness of the Lasso. Not that it is well known that there are cases where the Lasso is non-unique. Please, clarify your statement accordingly. - for simplicity b_d could be removed here. - in (4) it would be more natural to write f_j(h_j) instead of f(h_j) - "has is that to be bounded"-> is boundedness? - what is l_max_j here? moreover the bold letters seem to represent vectors but this should be state explicitly somewhere. page 3: - what is the precise meaning of "distributed" when referring to representation - In remark 1: the font has changed weirdly for W and h. - "two class"->two classes - Definition 1: again what is a precise definition of activation function? - "if we set": bold issue. - b should b_e in Theorem 1, right? Also, please recall the definition of the sigmoid function here. Moreover l_max and mu_h seem useless in this theorem... why referring to them? - "if the rows of the weight matrix is"-> if the rows of the weight matrix are page 4: - Proposition 1 could be stated as a theorem and Th.1 as a corollary (with e=0). The same is true for proposition 2 I suspect. - Again the influence of l_max and mu_h are none here... - Please, provide the definition of the ReLu function here. Is this just x->x_+ ? page 6: - R^+m -> font issue again. - "are maximally incoherent": what is the precise meaning of this statement? - what the motivation for Theorem 3? This should be discussed. - De-noising -> de-noising - the discussion after (15) should be made more precise. page 7: - Figure 1 and 2 should be postponed to page 8. - in Eq. (16) one needs to known E_h(x) and E_h_i(h_i), but I suspect this quantity are usually unknown to the practitioner. Can the author comment on that? page 8: - "the recovery is denoised through thresholding": where is this step analyzed? page 9: - figure 3: sparseness-> sparsity; also what is the activation function used here? - "are then generate"->are then generated - "by greedily select"->by greedily selecting - "the the" - "and thus pre-process"-> and thus pre-processing Supplementary: page 1: - please define .sigma, and its simple properties used along the proof. page 2: - g should be g_j (in eq 27 - > 31) - overall this proof relies on ingredients such as the one used for Hoeffding*s inequality. Most ingredients could be taken from standard tools on concentration (see for instance Boucheron, Lugosi, Massart: "Concentration Inequalities: A Nonasymptotic Theory of Independence", 2013). Moreover, some elements should be factorized as they are shared among the next proofs. This should reduce the size of the supplementary dramatically. page 7: - Eq. (99): it should be reminded that W_ii=1 here. - the upper bound used on .mu to get equation 105 seems to be in the wrong order.