Neural Networks for Principal Component Analysis: A New Loss Function Provably Yields Ordered Exact Eigenvectors 
Authors: Reza Oftadeh
Jiayi Shen
Zhangyang Wang
Dylan Shell
Venue:  (2020)
Keywords: Principal Component Analysis
Autoencoder
Neural Network

Abstract: In this paper, we propose a new loss function for performing principal component analysis (PCA) using linear autoencoders (LAEs). Optimizing the standard L2 loss results in a decoder matrix that spans the principal subspace of the sample covariance of the data, but fails to identify the exact eigenvectors. This downside originates from an invariance that cancels out in the global map. Here, we prove that our loss function eliminates this issue, i.e. the decoder converges to the exact ordered unnormalized eigenvectors of the sample covariance matrix. For this new loss, we establish that all local minima are global optima and also show that computing the new loss (and also its gradients) has the same order of complexity as the classical loss. We report numerical results on both synthetic simulations, and a real-data PCA experiment on MNIST (i.e., a 60,000 x784 matrix), demonstrating our approach to be practically applicable and rectify previous LAEs' downsides.

Under review as a conference paper at ICLR 2020
NEURAL NETWORKS FOR PRINCIPAL COMPONENT ANALYSIS: A NEW LOSS FUNCTION PROVABLY YIELDS ORDERED EXACT EIGENVECTORS
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, propose new loss function for performing principal component analysis (PCA) using linear autoencoders (LAEs). Optimizing the standard L2 loss results in decoder matrix that spans the principal subspace of the sample covariance of the data, but fails to identify the exact eigenvectors. This downside originates from an invariance that cancels out in the global map. Here, we prove that our loss function eliminates this issue, i.c. the decoder converges to the exact ordered unnormalized eigenvectors of the sample covariance matrix. For this new loss, we establish that all local minima are global optima and also show that com- puting the new loss (and also its gradients) has the same order of complexity as the classical loss. We report numerical results on both synthetic simulations, and real-data PCA experiment on MNIST (i.e., a 60, 000 x 784 matrix), demonstrating approach to be practically applicable and rectify previous LAEs' downsides.
INTRODUCTION
Ranking among the most widely-used and valuable statistical tools. Principal Component Analysis (PCA) represents given set of data within new orthogonal coordinate system in which the data are uncorrelated and the variance of the data along each orthogonal axis is successively ordered from the highest to lowest. The projection of data along each axis gives what are called principal components. Theoretically, eigendecomposstion of the covariance matrix provides exactly such transformation. For large data sets, however, classical decomposition techniques are infeasible and other numerical methods, such as least squares approximation schemes, practically employed. An especially notable instance the problem of dimensionality reduction, where only the largest principal components
the best representative of the data- are desired. Linear autoencoders (LAEs) are one such scheme for dimensionality reduction that is applicable to large data sets.
An LAE with single fully-connected and linear hidden layer, and Mean Squared Error (MSH) loss function can discover the linear subspace spanned by the principal components. This subspace is the same as the one spanned by the weights of the decoder. However, it failure to identify the exact principal directions. This is due to the fact that, when the encoder is transformed by some matrix, transforming the decoder by the inverse of that matrix will yield no change in the loss. In other words, the loss possesses a symmetry under the action of a group of invertible matrices, so that directions (and orderrins/permmuaationss thereto) will not be discriminated.
The early work of [ourlard & Kamp (1988) and Baldi & Hornik (1989) connected LAES and PCA and demonstrated the lack identifiability of principal components. Several methods for neural networks compute the exact eigenvectors (Rubner & Tavan 1989 Xu 1993] Kung & Diamantaras, 1990 Oja et al. 1992), but they depend on either particular network structures or special optimiza- tion methods. It was recently observed (Plaut) 2018 Kunin et al. 2019) that regularization causes the left singular vectors of the decoder to become the exact eigenvectors, but recovering them still requires extra decomposition step. As Plaut (2018) point out, existent method recovers the eigenvectors from an LAE in an coamiiaatioo-nddeeeeeeee way on a standard network - this work fills that void.

---

Under review as a conference paper at ICLR 2020
Moreover, analyzing the loss surface for various architectures of linear/non- linear neural networks is a highly active and prominent area of research (e.g. [Baldi & Hornik (1989); Kunin et al. (2019); Pretorius et al. (2118): Frye et al. (2019). Most of these works extend the results of Baldi & Hormik (1989) for shallow LAFs to more complex networks. However, most retain the original MSE loss, and they prove the same critical point characterization for their specific architecture of interest. Most notably Zhou & Liang (2018) extends the results of Baldi & Hornik (1989) to deep linear networks and shallow RELU networks. In contrast in this work we are going after a loss with better loss surface properties.
We propose new loss function for performing PCA using LAEs. We show that with the proposed loss function, the decoder converges to the exact ordered unnormalized eigenvectors of the sample covariance matrix. The idea simple: for identifying p principal directions we build up a total loss function as a sum of p squared error losses, where the 1th loss function identifies only the first i principal directions. This approach breaks the symmetry since minimizing the first loss results in the first principal direction, which forces the second loss to find the first and the second. This constraint is propagated through the rest of the losses, resulting in all p principal components being identified. For the new loss we prove that all local minima are global minima.
Consequently, the proposed loss function has both theoretical and practical implications. Theoret- ically, it provides better understanding of the loss surface. Specifically, we show that any critical point of our loss T. is a critical point of the original MSE loss but not vice versa, and conclude that T. eliminates those undesirable global minima of the original loss (i.e., exactly those which suffer from the invariance). Given that the set of critical points of L is subset of critical points of MSE loss, many of the previous work on loss surfaces of more complex networks likely extend. In light of the removal of undesirable global minima through L, examining more complex networks is certainly a very promising direction.
As for practical consequences, we show that the loss and its gradients can be compactly vectorized so that their computational complexity is no different from the MSE loss. Therefore, the loss L can be used to perform PCA/SVD on large datasets using any method of optimization such as Stochas- tic Gradient Descent (SGD). Chief among the compellingly reasons to perform PCA/SVD using this method is that, in recent years, there has been unprecedented gains in the performance of very large SGD optimizations, with autoencoders nigh-ddmensional training data (c.g., images). The loss function we offer is attractive in terms of parallelizability and distributability, and does not prescribe any single specific algorithm or imple- mentation, so stands to continue to benefit from the arms race between SGD and its competitors.
particular successfully handling larger numbers of
More importantly, this single loss function (without an additional post hoc processing step) fits seam- lessly into optimization pipelines (where SGD is but one instance). The result is that the loss allows for PCA/SVD computation as single optimization layer, akin to an instance of a fully differentiable building block in NN pipeline Amos & Kolter (0117), potentially as part of much larger network.
2 THE PROPOSED Loss FUNCTION AND REVIEW OF FINAL RESULTS
Let X E Raxm and Y E Raxm be the input and output matrices, where m centered sample points, each n-dimensional, are stacked column-wiss Let æ E R and yy RD be the jth sample input and output (i.e. the jth column of X and Y. respectively). Define the loss function L(A, B)
P m
P Σ
L(A
y
ALe
Bxy
I
BXI
(1)
1=
where ( and 11- are the Frobenius inner product and norm, Lup is a p matrix with all ele- ments zero except the first i diagonal elements being one. (Or, equivalently, the matrix obtained by
[
setting the last p- diagonal elements of a x identity matrix to zero, e.g. 12.3 = 0
0
J) In
0
0
0
what follows, we shall denote the transpose of matrix M by M'. Moreover, the matrices A E RRaxp. and B& E RRxm can be viewed as the weights of the decoder and encoder parts of an LAE.
The results are based on the following standard assumptions that hold generically:
2

---

Under review as a conference paper at ICLR 2020
Assumption 1. For an input X and output Y. let Eez Xx' Ezy == XY,, E Eyz == En and yn YY' be their sample covariance matrices. We assume
The input and output data are centered (zero mean).
Ema Exg Syz and Eny are positive definite (of full rank and invertible).
The covariance matrix Σ = Eyz Du Eay is of full rank with n distinct eigenvalues An.
>2
The decoder matrix has no zero columns.
Claim. The main result of this work proved in Theorem is as follows:
If the above assumptions hold then all the local minima L(A, B) are achieved A and B are of the form
A = Ut Dr
B D U D E D-l
where the Th column of L1:p is the unit cigenvector Ef E
xx Egy corresponding to the 7h largest eigenvalue and D, is diagonal matrix with nonzero diagonal elements. In other words, contains ordered unnormalized eigenvectors of Σ corresponding to the largest eigenvalues.
Moreover, all the local minima are global minima with the value the loss function those global minima being
P
L(A, B) - Tr(E,)) Σ
Cv-i+1)A
where >; is the ht largest eigenvalue of Σ == Ey E Eny- In the case of autoencoder (Y = X): Σ Ena. Finally, while L 3 in the given form contains O(p) matrix products, will show that can be evaluated with constant (less than 7) matrix products independent of the value
NOTATION
In this paper. the underlying field is always R, and positive semidefinite matrices are symmetric by definition. The following constant matrices are used extensively throughout. The matrices Tç E Rexp and Sp R2x are defined
(Tp)is (p i 1) dej, i.c. Tp- diag (p.P 1,... 1),
(2)
p-
17
1-1 p
4
3
2
17
3
3
2
(S)))=p-mxx((-)+11 i.e. S,=
: ', 2 2
e.g. S4=
(3)
2
2
2
1
Another matrix that will appear in the formulation is Sp == ' Clearly, the diagonal
matrix T, is positive definite. As shown in Lemma S, and S, are positive definite as well.
4 MAIN THEOREMS
The general strategy to prove the above claim as follows. First the analytical gradients of the loss is derived in a matrix form in Propositions [ and [ We compare the gradients with that of the original Minimum Square Error (MSE) loss. Next, we analyze the loss surface by solving the gradient equations which yields the general structure of critical points based the rank of the decoder matrix A. Next, we delineate several interesting properties of the critical points, notably, any critical point of the loss is also critical point for the MSE loss but not the other way around. Finally, by performing second order analysis on the loss in Theorem the exact equations for local minima are derived which is shown to be claimed.

---

Under review as a conference paper at ICLR 2020
Let L(A, B) and L(A, B) be the original loss, and the proposed loss function, respectively, i.e.,
m
(AAB) = Σ 1y ABa,I1
M(, B)
15
Al Bay
==1
i j=1
= Y ABX 1r
Σ
Y A
The first step is calculate the gradients with respect A and B and set them to zero derive the implicit expressions for the critical points. In order to do so, first, in Lemma | for a fixed A, we derive the directional (Gateaux) derivative of the loss with respect B along an arbitrary direction W E R"x* denoted as dp (A, B) W.W.c. i.c.
LA W) L(A,
dnL(A,
lim W
W
As shown in the proof of the lemma, dBL(A, B)W is derived by writing the norm in the loss as an inner product, opening up using linearity inner product, dismiss second order terms in W(ie. (([)) and rearrange the result as the inner product between the gradient with respect to B, and the direction W, which yields
dBL(A,B) = Tr (W' (T, ym (Sp (A'A)) BEar) = -TT,,AA' - (S, o (A' BE W)F,
(4)
where, is the Hadamard product and the constant matrices Tù and Sy, were defined in the be- ginning. Second, the same process is done in Lemma 6 to derive d T. (A, BVV; the derivative of L with respect to derive the implicit expressions for the critical points. The results are formally stated in the two following propositions.
in an arbitrary direction
IR 7y for fixed B, which is then set zero
Proposition 1. For any fixed matrix A Ruxp the function L(A, B) is convex in the coefficients of B and attains its minimum for any B satisfying the equation
(Sp
= T,A'E EyEn. yas
where o is the Hadamard (element-wise product operator, and Sp and Tp are constant matrices defined the previous section. Further, if has no zero column, then I(AA, B) is strictly convex in B and has unique minimum when the critical B is
B B(A) (Sp (A'A)) 'T, En
(6)
and in the autoencoder case it becomes
B B(A) (S, -T,'''
(6')
The proof is given in appendix A.2
Remark 1. Note that as long as A has no zero column, Sp a (A'A) ) is nonsingular (we will explain the reason soon). In practice, A with zero columns can always be avoided by nudging the zero columns of A during the gradient decent process.
Proposition 2. For any fixed matrix E IRpx" the function L(A, B) is a convex function Moreover, for fixed B, the matrix A that satisfies
A (S, o (BE,, B')) - BTT,
a critical point of L(A, B).
The proof is given in appendix A.3
The pair (A, B) B) pair of directions (V, W). Therefore, the implicit equations for critical points given below, next to the ones derived by Baldi & Hornik (1989) for ī. A, B).
a critical point of L if they make d ((A, B)W and d' BVV zero for any
4

---

Under review as a conference paper at ICLR 2020
For L(A, B): A'A = A y'Eyzi y2 ABE,
For L(A, B): Σ
(S, o (A ge = TpA'Eys A (BE,, = Eya
By B'.
Remark 2. Notice the similarity, and the difference only being the presence of Hadamard product by Sp in the left and by diagonal Tp in the right. Therefore, practically, the added computational cost of evaluating the gradients is negligible compare to that of MSE loss.
The next step is to determine the structure of (A, B) that satisfies the above equations, and find the subset of those solutions that account for local minima. For the original loss, the first expression (A' ABA Fr = yz is used to solve for B and put it in the second to derive an expression solely based on A. Obviously, in order to solve the first expression for B, two cases are considered separately: the case where A is of full rank p. so A'A is invertible, and the case of A being of rank r < p. Here we do the same but there is a twist; for us there is only one case. The reason as long as (not necessarily full rank) A has no zero column, Sp o (A'A A) is positive definite and hence, invertible. This is discussed in detail in Lemma 2 and we briefly explain it here. As shown in the lemma, Sp is positive definite and by Shur product theorem for any A (of any rank), S, (A'A) is positive semidefinite. However, as a result of Oppenheim inequality (Horn & Johnson (2012), Thm 7.8.16), that in our case translates to det (A'A): < dct(S,, (A' zero column, [I, > O and therefore, det (A' A)) > 0. Here, we assume A of any rank S p has no zero column (since this can be easily avoided in practice) and consider Sp (A' A) to be always invertible. Therefore, ( (A, B) define a critical point of losses i. and if
long A has no
For [(A, B) and full rank A:
For L(A, B) and no zero column A:
B = (AA = (A'A) 1 yz yz Eー1 ABE, B' Eyz B'.
B = B(A) = (Sp (A'A)) TAA' yz E 22 ASp 9 (BE,,, B)) = B'T,
Before, we state the main theorem we need the following definitions. First, a rectangular permu- tation matrix II, E xxx is a matrix that each column consists of at most one nonzero element with the value 1. If the rank of II, is r with < p then clearly. II, has p r zero columns. Also, by taking away those zero columns the resultant r submatrix of II, is a standard square permutation matrix.
E Ey my has an Second, under the conditions provided in Assumption 1 the matrix Σ = Eg E z. eigenvalue decomposition Σ UAU', where the 2t column of U, denoted as u, is an eigenvector of Σ corresponding to the 7th largest eigenvalue of Σ, denoted as A₁. Also, A = diag(An (A,,... ),) the diagonal vector of ordered eigenvalues of E, with \ > X2 > ... A,, > O. We use the following notation to organize subset of eigenvectors of Σ into rectangular matrix. Let for any r S. 1. (i,,... ir [1 < i < .... < i, < n) be any ordered r r-index set. Define Un. E Bnxx as 11 [ u. That is the columns of U1. are the ordered orthonormal eigenvectors of E associated with eigenvalues dG, < ... < Xo. Clearly, when r = p. we have U,, = [u.,.... U corresponding to p- index set Ip (i,,-.. (1 < in <... < ip < n). Similarly, we define )i,)
A1. E PR as AI,- = diag(Ai,
Theorem 1. Let A E RaxP and B E Roxn such that A is of rank r S p. Under the conditions provided in Assumption ] and the above notation, The matrices A and B define a critical point of L(A, B) if and only for any given r -index set Ir, and nonsingular diagonal matrix D E Br
A and B are of the form
A = UI,
(8)
= -(A)) E
(9)
where, C E REXP is of of full rank r with nonzero and normalized columns such that Ic (S, o (C'C) T,,C' is rectangular permutation matrix of rank and CIIc I,- For all
1 S p. such C always exists. In particular, if matrix A is of full rank p. i.e. = the two given conditions on II are satisfied iff the invertible matrix C is any squared p x p permutation matrix II. In this case (A, B) define critical point of L(A, B) iff they are of the form
A A IID,
(10)
5

---

Under review as a conference paper at ICLR 2020
== B(A) = -'' Egn
(11)
The proof is given in appendix A.4
Remark 3. The above theorem provides explicit equations for the critical points of the loss surface in terms of the rank of the decoder matrix A and the eigenvectors of Σ. This explicit structure allows us further analyze the loss surface and its local/global minima.
Here, we provide proof sketch for the above theorem to make the claims more clear. Again as a reminder, the EVD of Σ = D
Σ UAU" For both L and L, the corresponding B (A) is replaced by B on the RHS of critical point equations. For the loss [(A, B), as shown in the proof of the theorem, results in the following identity
U'A S (BER=B') A'
(12)
where A = (S, (A''A) 'T is symmetric and positive semidefinite. The LHS of eq. 12 is symmetric the RHS is symmetric too, AA = =(A))= A'A' = AA. Therefore, A commutes with the diagonal matrix of eigenvalues A. Since eigenvalues are assumed to be is positive definite and U is an orthogonal matrix. Therefore, r = rank A) rank ()) = rank(U" AU), which implies that the diagonal matrix A, has r nonzero and positive diagonal entries. There exists an r-index set I, corresponding to the nonzero diagonal elements of A. Forming a diagonal matrix 4,, E R2"x" by filling its diagonal entries (in order) by the nonzero diagonal elements of A, we have
distinct, A has be diagonal well. By Lemma (S, L o A))
UAU U1, U = U
Def A
(13) which indicates that the matrix A has the same column space as Ur.. Therefore, there exists a full rank matrix C' E Rx such that A Ui, C. Since A has no zero column, C' has no zero column.
(S, -
Further, by normalizing the columns of we can write A = U2 CD, where D E RPxP is diagonal that contains the norms of columns of C.
Baldi & Hornik 1989) did something similar for full rank A for the loss İ to derive (A, = =UI, Õ) U1,O),
But their C' can be any invertible p X p matrix. However, in our case, the matrix C Rrxp corresponding to rank r I p matrix A, has to satisfy eq. ([3) by replacing A by U1 and eq. 12) by replacing B(A) by BUU CD). In the case Baldi & Hornik (1989), for the original loss L. equations similar to eq. (13) and eq. (12) appear but they are are satisfied trivially by any invertible matrix Ć. Simplifying those equations by using A = U1, CD after some algebraic manipulation results in the following two conditions for C:
CT (C')) T,C'' =A,, and C (Spp ((Sp (C'C)) A1, (S, (C'C)) C' =A,
(14)
(15)
As detailed in proof of Theorem solving for C' leads to its specific structure as laid out in the theorem.
Remark 4. Note that when is of rank r < with no zero columns then the invariant matrix C is not necessarily a rectangular permutation matrix but Ic = (Sp o (C"C) C" is rectangular permutation matrix with CTTc I,.. It is only when permutation matrix. Nevertheless, as we show in the following corollary, the global map is always Vr p:p:C G AB Ug, U, matrices) for the invariant matrix C' when r < However, this is not necessary as we soon show that all rank deficient matrix As are saddle points for the loss and ideally should be passed by during the gradient decent process. Based on some numerical results our conjecture is that when r < p the matrix C' can only start with a r X l rectangular permutation matrix of rank r with r < k S p and the rest of p l columns of C' is arbitrary as long as none of the columns are identically zero
p that the invariant matrix C becomes
Ena --1 It is possible to find further structure (in terms of block
Corollary 1. Let (A, B) be a critical point of L(A, B) under the conditions provided in Assump- tion 7 and rankA T S p. Then the following are true
1. The matrix BE B' is a P X diagonal matrix of rank r.

---

Under review as a conference paper at ICLR 2020
2. For all 1 r p. for any critical pair (A, B). the global map G AB becomes
G --U,, E Dx
(16)
For the autoencoder case (Y = X the global map is simply G UU
3. (A, B) is also the critical point of the classical loss -) Y ABX
The proof is given in appendix A.5
Remark The above corollary implies that L(A, B) not only does not add any extra critical point compare to the original loss L(A, B),, provides the same global map G AB. only limits the structure of the invariance matrix C' as described in Theorem so that the decoder matrix A can recover the exact eigenvectors of Σ.
Lemma 1. The loss function L(A, B) can be written as L) = Tr( - 2'Tr (AT, + Tr (B' (S, o (A' BEzz). The above identity shows that the number of matrix operations required for computing the loss T. (, B) is constant and thereby independent of the value of p.
(17)
The proof is given in appendix A.6
Theorem 2. Let A' E RRxxp and B E Bexx such that A is of rank S p. Under the conditions
provided in Assumption 7 (A* B²) define local minima of the proposed loss function iff they are of the form
A" D, B" = D E
(18)
(19)
where the 1th column of Uv:p is a unit eigenvector of E corresponding the th largest eigenvalue and Dy diagonal matrix with nonzero diagonal elements. In other words, A contains ordered unnormalized eigenvectors of E corresponding to the largest eigenvalues. Moreover all the local minima are global minima with the value of the loss function those global minima being
L(A", B Tr(E TTT
Σ 1p-i+1o
(20)
where X is the 7th largest eigenvalue of E.
The proof is given in appendix A.7
Remark 6. Finally, the second and third assumptions we made in the beginning in Assumption | be relaxed by requiring only Σ,x to be full rank. The output data can have different dimension than the input. That Y E R= and X Rn' xm where * n'. The reason that the given loss function structurally is very similar to MSE loss and can be represented as a Frobenius norm ---E, ve Ezy is still
on the space of n X m matrices. In this case the covariance matrix Σ == En En
n. Clearly, for under-constraince systems with < n' the full rank assumption of Σ holds. For the overdetermined case, where ní >> n the second and third assumptions in Assumption can be relaxed: we only require Exr be full rank since this is the only matrix that is inverted in the theorems. Note that if p > min(n', n) then A1,: the X diagonal matrix of eigenvalues of for p-index-set I., bounds to have some zeros and will be say rank encoder A with rank However, the Theorem iis proved for encoder of any rank S p. Finally, following theorem 2 then the first columns the encoder A converges to ordered eigenvectors remaining columns span the kernel space of Σ. Moreover, Σ need not to this case Ag, becomes a block diagonal matrix, where the blocks
p. which in turn, results in the
of Σ while the have distinct eigenvectors. correspond to identical eigenvalues Σr, In this case, the corresponding eigenvectors in A are not unique but they span the respective eigenspace.
EXPERIMENTS
5.1 EXPERIMENTAL. SETUP
LAEs with Two Loss functions We will verify the loss function L(A,B) defined in eq. [1 by setting the input matrix X R equal to the output matrix Y E Raxm (Y X), where the
7

---

Under review as a conference paper at ICLR 2020
linear autodecoder (LAE) becomes solution to PCA. In order for comparison, we train another
LAE using the MSE loss Í(A, B) defined as Í(A, B) Y ABX where Y
X is also
applied in our experiments.
The weights of networks are initialized to random numbers with a small enough standard deviation (10-7 in our case). We choose to the Adam optimizer with a scheduled learning rate (starting from 10-3 and ending with 10-6 in our case), which empirically benefits the optimization process. The two training processes are stopped the same iteration which one of the models firstly finds all of the principal directions. As side note, we feed all data samples to the network at one time with batch size equal m, although mini-batch implementations are apparently amendable.
Evaluation Metrics We use the classical PCA approach to get the ground truth principal direction matrix A" E RRxx, by conducting Eigen Value Decomposition (EVD) XX' E TR*x or Singular Value Decomposition (SVD) to X E R As reminder, A E R stands for the decoder weight matrix of an trained LAE given a loss function L. To measure the distance between A and A, we propose an absolute cosine similarity (ACS) matrix inspired by mutual coherence (Donoho
et al. 2005), which is defined as:
ACS. |AA, A,) || ||,|1|
(21)
||
where A; E [ denotes the 7th ground truth principal direction, and A, E IR*x1 denotes the jth
column of the decoder A, j.j = 1, ......P... p. The elements of ACS E R2xp in eq. (21 take values
between [0.1], measuring pair- pair similarity across two sets of vectors. The absolute value absorbs the sign ambiguity of principal directions.
The performances of LABs evaluated by defining the following metrics:
Ratiorp
IACS,, 1 1- -cl/p
(22)
Ratiorr =
IACS, > >1
- cl/p, and
(23)
4-=1 (f)
Ratiorotal = Ratiorp + Ratiosp,
(24)
where I is the indicator function and e a manual tolerance threshold (c = 0.01 in our case). two vectors have absolute cosine similarity over 1 c, they deemed equal. Considering some columns of decoder may be correct principal directions but not in the right order, we introduce Ratiorr and Ratiorp p in eqs. (22) and (23) check the ratio of correct in- in-place and out-of-place principal directions respectively. Then Ratiorotal in eq. (24) measures the total ratio of the correctly obtained principal directions by the LAE regardless of the order.
Datasets As a proof-of-concept, both synthetic data and real data are used. For the synthetic data, 2000 zero-centered data samples are generated from a 1000-dimension zero mean multivariate normal distribution with the covariance matrix being diag(N,). For the real data, we choose to use MNIST dataset (LeCun al. 1998), which includes 60,000 grayscale handwritten digits images, each of dimension 28 x 28-
784.
5.2 EVALUATION AND ANALYSIS
Synthetic Data Experiments In our experiment, p. the number of desired principal components (PCs), is set to 100, i.c. the dimension is be reduced from 1000 to 100. Figures I and 2 demon- strate a few conclusions. First, during the training process, the loss ratio of both losses continuously decreases to 1, i.e. they both converge to the optimal loss value. However, when both get close enough, L require more iterations since the optimizer is forced to find the right directions: fully converges only after it has found all the principal directions in the right order.
Second, using the loss L results in finding more and more correct principal directions, with Ratiorp continuously rising; and ultimately affords all correct and ordered principal directions,
8

---

Under review as a conference paper at ICLR 2020
Performance of lancing the principal directions for both and
Convergence of and & consepooning opšimurn
Ratio detected principal divections
2.00
1.0
144.8)
1.76
1.50
L.).0.)
0.8
Rationad for
Lo8s Ratio
1.25
Ratloyp for L
1.00
Ratiopp
0.76
Ratiorwa for L
0.25
10'
10P
10 Iterations on log scale (i)
16a
Iterations on log scale (1)
Figure 1: Convergence of losses to their corre- Figure 2: Performance of both losses L and É in sponding optimal loss. Note that the correct shift finding the principal directions at the columns of and scaling of the y-axis tick values is printed at their respective decoders. the top left corner of the figure.
with Ratiorp ending with 100%. Notice that occasionally and temporarily, some of the principal directions is found but not at their correct position, which is indicated by the rise of Ratiopp in the figure. However, as optimization continues they are shifted to the right column, which results in Patiorp going back zero, and Ratiorp reaching one. As for L, fails identify any principal directions; both Ratiorp and Ratiopp for L stay at O, which indicates that none of the columns of the decoder Å, aligns with any principal direction.
Third, as shown in the figure, while the optimizer finds almost all the principal directions rather quickly, requires much more iterations to find some final ones. This is because some eigenvalues in the empirical covariance matrix of the finite 2000 samples become very close (the difference becomes less than 1). Therefore, the loss has to get very close to the optimal loss, making the gradient of the loss hard to distinguish between the two.
Real Data: MNIST Experiments We set the number of principal components (PCs) as 100, i.e. the dimension is to be reduced from 784 to 100. We also try to reconstruct with the top- 10 columns found in this case. As in Fig. the reconstruction performance of L is consistently better than L. That also reflects that L does not identify PCs, while I directly applicable to performing PCA without bells and whistles.
0
(a) Original
(b) Full decoder
(c) 10 columns
CONCLUSION
In this paper, we have introduced loss func- tion for performing principal component anal- ysis and linear regression using linear autoen- coders. We have proved that the optimizing with the given loss results in the decoder ma- trix converges to the exact ordered unnormal- ized eigenvectors of the sample covariance ma- trix. We have also demonstrated the claims on synthetic data set of random samples drawn from a multivariate normal distribution and on MNIST data set. There are several possible generalizations of this approach ing on. One is improving performance when the corresponding eigenvalues of two principal direc- tions very close and another is generalization of the loss for tensor decomposition.
(d) Original
(c) Full decoder
(f) 10 columns
Figure 3: Real data experimental comparison in the reconstruction performance of MNIST im- ages. First column: original image. Second col- umn: reconstructed image using full columns of the decoder. Third column: reconstructed image using the first 10 columns of the decoder. Top row: using Bottom row: using L.
currently work-

---

Under review as a conference paper at ICLR 2020
REFERENCES
Brandon Amos and Zico Kolter. Optnet: Differentiable optimization as a layer in neural networks. In International Conference on Machine Learning, pp. 136-145, 2017.
Pierre Baldi and Kurt Hornik, Neural networks and principal component analysis: Learning from examples without local minima. Neural networks, 2(1):53-55, 1989.
Hervé Bourlard and Yves Kamp. Auto-association by multilayer perceptrons and singular value decomposition. Biological cybernetics, 59(4-5):21 1988.
David L Donoho, Michael Elad, and Vladimir N Temlyakov. Stable recovery of sparse overcomplete representations in the presence of noise. IEEE Transactions information theory, 52(1):6-18, 2005.
Charles G Frye, Neha S Wadia, Michael R DeWeese, and Kristofer E Bouchard. Numerically recovering the critical points of deep linear autoencoder. arXiv preprint arXiv:1901.1003, 2019.
R.A. Horn and C.R. Johnson. Matrix Analysis. Cambridge University Press, 2012. ISBN 9781 139788885.
Sun-Yuan Kung and KI Diamantaras, A neural network learning algorithm for adaptive principal component extraction (apex). In International Conference on Acoustics, Speech, and Signal Pro- cessing, pp. 861-864 IEEE, 1990.
Daniel Kunin, Jonathan M Bloom, Aleksandrina Goeva, and Cotton Seed. Loss landscapes of regu- larized linear autoencoders. arXiv preprint arXiv:1901.08163 2019.
Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, et al. Gradient- based learning applied document recognition. Proceedings of the IEEE, 86(1 1):2788-2324, 1998.
Erkki Oja, Hidemitsu Ogawa, and Jaroonsakdi Wangviwattana. Principal component analysis by homogeneous neural networks, part 1: The weighted subspace criterion. IEICE Transactions on Information and Systems, 75(3):366-3755 1992.
Elad Plaut. From principal subspaces to principal components with linear autoencoders. arXiv preprint arXiv:1804. 10253, 2018.
Arnu Pretorius, Steve Kroon, and Herman Kamper. Learning dynamics of linear denoising autoen- coders. In International Conference on Machine Learning, pp. 4138 4148-4147, 2018.
Jeanne Rubner and Paul Tavan. A oelf-organizing network for sincipal-componedt analysis. EPL (Europhysics Letters), 10(7):693, 1989.
Lei Xu. Least mean square error reconstruction principle for self-organizing neural-nets. Neural networks, 6(5):627-648, 1993.
E. Zeidler. Applied Functional Analysis: Main Principles and Their Applications. Applied Mathe- matical Sciences. Springer New York, 1995. ISBN 9780387944227.
Y Zhou and Y Liang. Critical points of linear neural networks: Analytical forms and landscape properties. In Proc. Sixth International Conference on Learning Representations (ICLR), 2018.
10

---

Under review as a conference paper at ICLR 2020
APPENDIX
A PROOFS
A.I PRELIMINARIES
Before we present the proof for the main theorems, the following two lemmas introduce some nota- tions and basic relations that are required for the proofs.
Lemma 2. The constant matrices T, RR and Sp IRpPP are defined as
(Tp)s (p - dij, i.e. Tp diag (p, 1,... ,),
- 1
2
17
p
p
4
3
2
17
2
1
(Sp)) = max(i.)) +1, Le. Sp
2
e.g. S4
2
2
1
2
2
2
2
1
1
1
1
1
1
Clearly, the diagonal matrix Tp is positive definite, Another matrix that will appear in the formula- tion is Sp Tp 1
(5p) ij
=TT," STTT)) p () Le T SpT
e.g. S4
The following properties of Hadamard product and matrices Tp and Sp are used throughout:
1. For any arbitrary matrix A nxx
Icp = =Tp. and
(25)
1m
A'A = (A'A),
(26)
1=1
where, a is the Hadamard (element-wise) product.
2. For any matrices M1, M2 E IRxx and diagonal matrices 9,6 E TRPX,
(M1 M2) & (9M,6) M, M1 (9M²6). Moreover, if II, Il, R permutation matrices then
II, (M1 M2) 1l (11,, M,ll).
3. Sp invertible and its inverse is a symmetric tridiagonal matrix
0
i=j=1
2
-1
0
i=j$1
(5 )1
L.c Sp1
-1
-1
otherwise
0
-1
2

---

Under review as a conference paper at ICLR 2020
4. Sp is positive definite.
5. For any matrix A E Ruxp, Sp (A' A) is positive semidefinite. (not necessarily full rank) A has no zero column then Sp o (A'A) is positive definite.
6. For any diagonal matrix g E <Rxp
Sp = T, and
(27)
Sp = T
(28)
7. Let 9,6 &RpEP be positive semidefinite matrices, where & has no zero diagonal element, and 2 is of rank S. Also, let for any S <p, Jr fir,-.. i S i < ... < i < n)
be any ordered r index set. Then 9 and 6 satisfy
(S,0 2
(Sp
if and only if. the following two conditions are satisfied:
(a) The matrix ② is diagonal with p zero diagonal elements and positive diagonal elements indexed by the set Jr- That is for any E Jr (D) > and the rest of elements of D are (b) For any i.j J, and + we have ).. = O.
Clearly, if ( is positive definite then J, = N2 and hence, both D and & are diagonal.
Proof. The proof of the properties are follows.
1. eq. (25) is trivial. For eq. (26) note that Alip selects the first columns of A (zeros out the rest), and similarly, Tip A selects the first i rows of A (zeros the rest). Therefore,
1p A' AA up is paxx p matrix that its Leading Principal Submatrix of order (LPS,) same as the LPS; of A'A (and the rest of the elements are zero). Hence, > I..p A AAL (counting backwards) adds LPS, of A'A (i.e. A'A A itself) with LPSp-1 that doubles LPS,-1 part of the result and then adds LPSp-2 that triples the LPSp-2 part of result, the process continues until by the last addition LPS, added to the result for the times. This exactly the same as evaluating S, (A'A).
I is the
2. This a standard result (Hom & Johnson 2012), and no proof is needed.
3. Directly compute S,
(S,551), Σ (pp)a(())))) (
(5 ) + |,sh
(5, )
2 2
j jSp -
(Sp) (S) )PP
= p
)11 h I (S )2,1
j =
(Sp) (S Sp)titt
25jSp-1
j=p
(Sp) - -Sp))z
j=1
max(i.j 1) - max(i,,) + max(i,j +
25išp-1
-(p max 1) + 1) + 2(p max(i,p) 1)
j=p
max(i, + max(i,
j=1
'oor X matrix, the leading principal submatrix of order is x matrix derived by removing the last p i rows and columns of the original matrix (Hom & Johnson (2012) P17)
12

---

Under review as a conference paper at ICLR 2020
max(i, - 1) - max(i, + max(i,j+1) p
1 1- p + max(i, p 1)
==p
max(i, max(i. 1)
j=1
[1 i=j
1 k<j <p
10 i
[1 i=p
10 ipp
j=p
(I,):
[1 i=1
10 122 j=1
4. Firstly, note that Sp1 is symmetric and nonsingular so all the eigenvalues real and nonzero. It is also diagonally dominant matrix (Horn & Johnson (2012), Def 6.1.)) since
Wi {1, : (Sp 2
E 1(5 R., j=1
where the inequality is strict for the first and the last row and equal for the rows in the middle. Moreover, by Gersgorin circle theorem (Homn & Johnson 2012). Thm 6.1.1) for every eigenvalue 4 S, there exists such that 4 E C. R. C. R.]. Since Vi : C; R3 we have all the eigenvalues are non-negative. They are also nonzero, hence, Sp is positive definite, which implies Sp is also positive definite.
5. For any matrix A R A'A is positive semidefinite. Also, Sp is positive definite so by Schur product theorem (Horn & Johnson (0012). Thm 7.5.3(a)). Sp a (A'A) is positive semidefinite. Moreover, all diagonal elements of A'A are positive (i.e. A has zero column) by the extension of Schur product theorem (Horn & Johnson (012)), Thm 7.5.3(b))
it is positive definite. This can also be easily deduced using the Oppenheim inequality (Horn & Johnson (2012). Thm 7.8.16); that is for positive semidefinite matrices S, and A'A: (et(Spp) [Sp) [A'A] )as I (S, A)). Since, Sp is positive definite, det (S)) )
(in fact it is for any p) and if A' AA has no zero diagonal then det(S, (A'A)) > 0 and therefore, S, (A' A) is positive definite.
6. Clearly, the matrix T, is achieved by setting the off- oif-diagonal elements of Sp to zero. Hence, for any diagonal matrix 9 RPXP; S, Tp 9. For the diagonal matrices Hadamard product and matrix product are interchangeable so the latter may also be written as T 9. The same argument applies for the second identity.
7. This property can easily be proved by induction on p and careful bookkeeping of indices.
Lemma 3 (Simultaneous diagonalization by congruence). Let MI, M2 E RRXp, where M is positive definite and M. is positive semidefinite. Also, let 9, 8 E Rr be positive definite diagonal matrices with r S p. Further, assume there is E Rrxp of rank S such that
CM,C" =9 and
CM₂C² =96.
Then there exists nonsingular C RPXP that its first rows are the matrix C and
Č = and
CM,C' -
where, - a which 6 -R.-rxp-r a nonnegative diagonal matrix. Clearly, the rank of M2 plus the number of nonzero diagonal elements of &.
diagonal matrix and & = 8 66 is another X diagonal matrix,
Proof. The proof is rather straightforward since this lemma is the direct consequence Theorem 7.6.4 in Horn & Johnson| 2012). The theorem basically states that if M,, M2 E IRPxP is symmetric
13

---

Under review as a conference paper at ICLR 2020
and M1 is positive definite then there exists invertible S E Rexp such that SM1S' = I, and SM2S' is a diagonal matrix with the same inertia as M2. Here, we have M2 that is positive semidefinite and C' xrx of rank S p such that
9 r C
Mi
9 c
=I, and
9 9 C
g C) -8. M2
C Therefore, since is of full rank p and 9 c is rank r S p, there exists - r rows in that are linearly independent of rows of 2 - C. Establish C E RRPX by adding those p rows to C. Then C has p linearly independent rows so nonsingular, and fulfillss the lemma's proposition that is
CM C' =9 and CM2C² -96,
where, 2 1 I,-p is an x diagonal matrix and 8 8 + 8 another p x p diagonal matrix, in which 6 1R--xpp- is nonnegative diagonal matrix.
Lemma 4. Let and B define critical point of L. Further, ler V R and W E Rox= are such that || |I W | = Os)) for some & > O. Then
L(A B W) (A (VT, BY B', V)F
-2 WT,, A (Sp (BE W' WW B')) V)F +(SS (A' A)) WE W)F O
(29)
Further, for W W (S, (A'A)) V
E Lys E-1 the above equation becomes
L(A+V B + W) L(A, B) = IY (V'V B') - V'EVI, (S, o (A' Tτ)
+2TH V A Sp BE VT, (S, (A'A))
+ (Sp 0 (A' A))
E'
yp B' ))) + +s(5))
(30)
Finally, in case the critical A is of full rank and so, (A, B) = (Ut, IID, (U,,II encoder direction V with V|] O(s) and W = W we have,
ID)), for the
L(A + V, B W L B Tr (V'VII', A IIT D -T (ITT(VV'VV (V'EVT,D) D-2
+2 Tr V IID Sp D DI''IT' EVD
+2 (V'U, IID (S, 22 VV' IID IID
+0((²).
(31)
Proof. As described in appendix B.1 then given by eq. 63 i.c.
the second order Taylor expansion for the loss L(A, B) is
W) ((A -d -AA dd B)W + 7 A.MAA
+dAB B) - P T(A, B) + Rv, B).
[ F W || = O(s) then R(V. W = 0 Moreover, when and B define BW O. By setting the derivatives
critical point of L we have LAL(A,BV d' L(A, V2, dA eq. (66) respectively, the above equation simplifies
dBL(A, (A), that are given by eq. 69 eq. (68). and
14

---

Under review as a conference paper at ICLR 2020
MA+V,B+W) B) (V (B V)F
-2 WT,, (S, (BE.. W' B')) V)r
+((Sp (A' ()) W ez W)F O
Now, based on the first item in Corollary BE :2 B' is a x diagonal matrix, so based on eq. (27
(B B²) By B'. The substitution then yields eq. 29.. Finally, in the above equation
replace W with W (S, (A'A))
V y E
We have
L B + W) L(A, B)
= =VV B', F) 2(Σ D VT, (S, (A'A)) Tpp V)
+2(A(S,, [BE a2 Eg VT Sp A'
(A' (A'A)) V E Ege B¹) Vip
+(S,, (A' (Sp (A 'T, E
(Sp (A'A)) -1 T, V'E 3 F +0(=0)
Tr (V'V, BE B') TTt (VEVT, S (A) T,
+ TT (V'A( S, BE, VT, (Sp ()) (Sp 0 (A'A)) A'A)))-T,V' V B' ))) + +c*))
which is eq.
30 For the final equation, we have
T, B' -T HU E yg D D En E Bay U1 IID
=T II U EU, IID T,D II A IID
AI,'AI, IIT, D
and
(32)
T, (S, (A'A))
T, -I, -T,
Sp DUTUUU
II (S, D2)
Tp= = I,T, D TT = TTD
(33)
Replace the above in eq.
30 and simplify:
I(A+V,B+ B I(A - B') Tr V'EVT, (VVEVT,, (Sp (A' 'T,)
+2TH ( S, BE VT, (Sp (A'A))
(S, o (A'A)) T, T E
B'
+ +EE)
L(A+V, B+ (A++VB++W L(A, Th V VII A D 3) Tr (V'EVV,
(V A (S, (BEny VD + D 2 V B'))
+0(E)) A=U; IDD
B= ID)
L(A+V, B B) L(A, Th VI'III' A IT, 2) (VEVT,
+2Th V'U, IID S D''UU', EVD
+2Th (VU IID (Sp D VV IID II))
+0(5'),
which finalizes the proof.
A.2 PROOF OF PROPOSITION
For this proof we use the first and second order derivatives for L(A, B) wrt B derived in Lemma From eq. (66). have that for a given A the second derivative wrt to B of the cost T.(A, B) B.
15

---

Under review as a conference paper at ICLR 2020
and in the direction W is the quadratic form
f (A, B)W² = 2T (W' (Sp A'A) WE,)).
The matrix Ege is positive-definite and by Lemma Sp A'A 'A is positive-semidefnite. Hence, pp [[ B)W is clearly non-negative for all W E RPx=. Therefore, L(A, B) is convex in coefficients of B for fixed matrix A. Also the critical points of L(A, B) for fixed A is matrix B that satisfies vW E Rex"; (AA, B)W = -0 and hence, from eq. (64) we have
-2 yx (Sp (A'A)) BE W)F =
Setting W =T,'' yr (Sp o (A' (A'A) A)) BΣ we have
Tp TpA' go - (Sp (A'A)) BE = O.
For fixed A, the cost L(A, is equation corresponds to minimum L(A, B). Further, if A has no zero column then by Lemma 2 S, A'A is positive definite. Hence, VW E Rxx= 2 2 (W" (Sp o A) WDgr)) is positive. Therefore, the cost L(A, B) becomes strictly convex and the unique global minimum is achieved at B B(A) as defined in eq. (6).
in B, any matrix B that satisfies the above
(A B)W²
A.3 PROOF OF PROPOSITION 2
For this proof we use the first and second order derivatives for L(A, B) wrt A derived in Lemma 6 For fixed B, based on eq. (69) the second derivative wrt A of L(A, B) at A, and in the direction V is the quadratic form
LA= B)V 2(V (S, (BE,BB))) = (V (Sp
V').
The matrix En,. positive-definite and by Lemma 2 Sp o (BE,, B') positive-semidefnnite Hence, de d (A, V' non-negative for all V paxp. Therefore, L(A, B) is convex in coefficients of A for a fixed matrix B. Based on eq. 67 the critical point of L(A, B) for fixed B is a matrix A that satisfies for all V R
dAL(A, BJV = (-2 (E nz BTT (S, (BE,, V)F =0
Eng B'T, = A (S, o
which is eq.
A.4
PROOF OF THEOREM 1
Before we start, a reminder on notation and some useful identities that are used throughout the proof. The matrix Σ Enn En Exy has an eigenvalue decomposition Σ UAU', where the ith column of U, denoted as u,, an eigenvector of Σ corresponding the 7th largest eigenvalue of Σ, denoted as 7₁ Also, A = (Ai, Aa) is the diagonal vector of ordered eigenvalues of Σ, with A X2 > >...> An O. We use the following notation organize subset of eigenvectors of Σ into a rectangular matrix. Let for any r S p. 1p = {i).-- ... (1 < i1 < ... < i, < n) be any ordered r-index set. Define U, R.xP as U, [u,, u. That the columns of U,. are the ordered orthonormal eigenvectors of Σ associated with eigenvalues dG < .... Xi,- The following identities are then easy to verify:
U². U1. =I,,
EU, AU,
(34)
U EU1, =Ai,-
(35)
The sufficient condition:
Let A of rank r < p and no zero column be given by eq. and the accompanying conditions are met. Notice that U U1 I, implies that DC'DD
88. B E Rxxx given by eq.
DCU A'A, so
Ie =e==(s, 'T,,'' "T,C'
B D- UIU E
En
--1 1x
D-1D=1,
16

---

Under review as a conference paper at ICLR 2020
B D- " DT, yyz Di1
Lemma
DT, DT,=T,D
T, DC Enn En D'=D'C'U
B S (DC'CD)
DC'CD-A'A
B = (Sp (A' (TTA)))TTpA'' TA ga E B(A),
which is eq. (6) Therefore, based Proposition for the given A. the matrix B defines critical
point of L(A, B). For the gradient wrt to A, first note that with B given by eq. we have
BDD D D
E
U1 D
-D- U Dyz E E
E my
U,
I
35
BE, B' -D DIA IT'
(36)
The matrix Ic is a rectangular permutation matrix so C IT's is diagonal so as
D D D Therefore, BE, B' is diagonal and by eq. (2 in Lemma 6 we have
Sp o (BE m2 B3) -T,By or B' -BE,. BTT
=D- IT TT Ax
A (S, (BE Em B))) = AD A IT A=Ui, CD
A
(S, (BE B')) CDD A IT' "T,
AD
-U,, CTle A1, D' CIle=1,
A (Sp (BE,,
A1 D T
eq.
EUI IT' T
Eye EnI Eny U1, I 'T
Eyn (D "D- Eyz Σ Tp
Σー1
- BTTp,
which is eq. (7) Therefore, based on Proposition Proposition 2 for the given B, the matrix A define a critical point of L(A, B). Hence, and together define critical point of L(A, B).
The necessary condition:
Based on Proposition and Proposition 2 for (with no zero column) and B. to define a critical point of L(A, B), has to ((A) given by eq. (6). and has to satisfy eq. (7). That
A (BE,.B')
Eyy
B(A) RHS
A (S, (BE,, B') -E Ey E-I (S, (A'A)) 'T
AA'
Σ=E En E
A (S, (, (BE, B') A' -EA, (A'AA) E-UAU"
xU,U'x
U' (S (BEI.B') B')
AU -UUAU (S, o (A'A)) AT,''U U'U=1
U'A S, (BEr B')
A'U =AA,
(37)
where, U' AT,,,S o (A' A'U is symmetric and positive semidefinite. The LHS of the above equation is symmetric the RHS is symmetric too, AA (AA) = A'A' AA. Therefore, A commutes with the diagonal matrix of eigenvalues A. Since, eigenvalues are assumed to be distinet, A has to be diagonal as well. By Lemma TT, (Sp (A' A)) - Tр is positive definite and an orthogonal matrix. Therefore. r = rank A) rank( A) rank(U" AU) which implies that the diagonal matrix A, has nonzero and positive diagonal entries. There exists
17

---

Under review as a conference paper at ICLR 2020
r-inddx set I, corresponding the nonzero diagonal elements of A. Forming diagonal matrix 1, E IR*x by filling its diagonal entries (in order) by the nonzero diagonal elements of A we have
UAU = U1 A Ug
Def A
UU' (S, o " = US UI, (S, (A'A)) 'T,A' U,, U/.. which indicates that the matrix A has the same column space UI,. Therefore, there exists full rank matrix C' E R such that A U1, C. Since A has no zero column, C' has no zero column. Further, by normalizing the columns of Ć we can write A U,D CDD where D RRxp diagonal that contains the norms of columns of Ò. Therefore, is exactly in the form given by eq. 8 The matrix C' has to satisfy eq. (38) that is
(38)
A-U.C
(S, (A'A)) 'T,'' U1 1 U
U1, (D,, (4'A)) " = 1 U
XU Un.
A'A=DC'CD
CST,(S, (DC'CD)-'TCC')) Ar, Lemma
(CC) AI.
(S, (C'C))- AT.
(39)
Now that the structure A has been identified, evaluate B(A) of eq. that is
by setting A UU, CD,
gir E B B(A) = (Sp -TpA' (Sp o (DC'C E E
Lemma B2
B = D- (C'C)) Eyx E-1
which by defining Ic (Sp (C'C)) "T,)' gives eq. (34 for B as claimed. While C has to satisfy eq. (39). A and B in the given form have to satisfy eq. (37) that provides another condition for C as follows. First, note that
Sp (BE.I B') Sp
D (S, (C'C)) CT,(S, (C'C))-
S, (S, (C,')) o (C'C))-
Lemina E
D (Sp ((s, (T,CA) CT, o (C'C))-1)) D-1
Now, replace and B in eq. (37) by their respective identities that we just derived, Performing the same process for eq. (37) we have
U'A S (S, (BER.B') AU AA
A=U,,
xU',Ux
C (CCC)))(((Ss(CCCC)))T,CCCCC CT, (C' C'U,, = UAAU U
XU
C ((s, ( (,0,, CT, (C'C) C (S, o (SS, (C'C)) CT, (C'C)) AT
-'
(40)
Now we have to find such that satisfies eq. 33 and eq. 44).. To make the process easier to follow, lets have them in one place. The matrix C' R prxp have satisfy
CT, (C'C)) (C'C))"'T,C' T,C' = =A, and C (S, o ((S, (C, A, CS, o C A
(41)
(42)
Since C' is a rectangular matrix, solving above equations for C in this form seems intractable. We trick to temporarily extend C into an invertible square matrix as follows.
18

---

Under review as a conference paper at ICLR 2020
Temporarily, let M1 ((Sp o (C"C) (S,, (C"))))) Then M1 is positive definite and M2 is positive semidefinite, so they are simultancously diagonalizable by congruence that is based on Lemma and eq. (41) and eq. (42) there exists a nonsingular C that C' consists of the first r rows of and
Tp. and M2 Sp
RPxx such
CT, (S, o (C'C)) T,C' = C c(s, ((sp o (C'C)) T,C'A, CT. (S, (C'C)) 0² A
(43)
(44)
where, A., = A1, @ IT- is ap x diagonal matrix and AI, = 1, e A is another p x diagonal matrix, in which A R -r--xx-p is nonnegative diagonal matrix.
Substitute Ar, from eq. (43 in eq. 44)), then left multiply by C²-1, and right multiply by I'r
δ c(S, ( (C'C)) T,C',, (CCC))
C'
A (S, T,, C'Ipp X
A, C'Irsp (s, o ( ",, CT, (S, (C'C))
C'I,AA,, (Sp (C'C)) Tp.
Now we can revert back everything to C again. Since C' consists of the first rows of C we have Cr = C"C, and C' LI C C²A,, C, which turns the above equation into
C'O (S, (S, (I (S, o (C'C) 1 CT, (Sp (C'C) ;1,)))))))))
I,C' CT, (Sp (C'C)) Tp
In the above equation, T o (C'C))TTp11 (Sp o (C'C))
replace
Ip by Tp T in LHS and by
Tp in the RHS. Use Il
(Sp (C'C)) T,CC' to shrink it into
C' (TT* AT - (S,
By the second property of Lemma 2 we can collect diagonal matrices Tp-ss around Sp to arrive at
(C'C) (Sp (
( (T,
where, = TTT,
Define p matrices 6, == C'C and 2, = =,T:T, IT Substitute in the above to arrive at:
8, (,,50..) -5, 9,-
[5,08,)
Both 9, and 6, in the above identity positive semidefinite. Moreover, since by as- sumption C has no zero columns, &, has no zero diagonal element. Then the 7th property of Lemma Dimmiimmmmiiisss implics the following two conclusions:
1. The matrix 2- is diagonal. The rank of D, is r so it has exactly r positive di- agonal elements and the rest is zero. This argument true for p T-19,TT,* I1 Since Ar, is a diagonal positive definite matrix, the p matrix IC == (S, (CC)))"T,,C' of rank r should have p - r zero rows. Let Jr be an indxexx set corresponding to nonzero diagonal elements of A IT' Then the matrix []] N,] (r x submatrix of II consist of its J, rows) is nonsingular. 2. For every í,j E Ir and + j. (6,)is = 0. Since &- == C'C' and so (6+) the inner product of 4th and 7th columns of C, we conclude that the columns of CN,,, Jr] (r submatrix of C consist of its Jr columns) words C IC,, Jr] is diagonal. The columns C are normalized. Therefore, C,N,, CC N,, J.] I, and hence, JT] is an orthogonal matrix.
orthogonal in other
19

---

Under review as a conference paper at ICLR 2020
We the two conclusions to solve the original eq. (S, (C"C)) T2C'' to shrink them into
(41 and eq.
42
First
He
CT =
(45)
(S ( IT))) C" =A, A...
(46)
Next, by the first conclusion, the matrix T 2 -TTTI I,A, IT' diagonal and so eq. (46) becomes
CT.HI Ar, C' -1 A.
45
A Ar T. ITC' = CII
(47)
which one of the two claimed conditions. What is left is to show that Hc is rectangular permutation matrix. From the first conclusion we also have Hc has exactly r nonzero columns indexed by J, so
U.
By the second conclusion C[N,JJr] is orthogonal matrix therefore. J,. is the orthogonal matrix C,,, Jzl'. Moreover, we had T. 2,T," = A, A,A,,,,, IT' is a p diagonal matrix with exactly r nonzero diagonal elements. Hence, an r x r positive definite diagonal matrix with A,, having distinct diagonal elements, and [I[[,, being orthogonal. Therefore, [IIJJ,,,, (as well as C[M,, JrJ should be a square permutation matrix. Putting back the zero columms, we conclude that C should be such that Ic = (Sp (C"C) C' is a rectangular permutation matrix and CIIc = I,. Note that it is possible to further analyze these con- ditions and determine the exact structure of C. However, this is not needed in general for the critical point analysis of the next theorem except for the case where r = p and C' is square invertible matrix. In this case, square matrix He is of full rank p, J, Np and therefore, C[Nr,Jer CiN,, Np] C. Hence, C is any square permutation matrix II, C'C II'II and Ic = (Sp (C'C)) T2,C' T, 'T,II' II', which verifies eq. and eq. (IT) for A and when A is of full rank p.
Ic M, Jr Ar, IT [IJ ]
A.5 PROOF OF COROLLARY
1. We already show in the proof Theorem that for critical (A, B) the matrix BE,, B' is given by eq. (36) that
BE, B' =D= IT
The matrix He is a p rectangular permutation matrix Ic Il is diagonal as well as D A D D-1 1 Therefore, BE,, is diagonal. The diagonal matrix Aj. is of rank therefore, BE B' is of rank
2. Again by Theorem critical (A, B) is of the form given by ( and eq. (9) with the proceeding conditions on the invariance C. Therefore, the global map is
G AB CDD TEDD-ITOGH, E En
U1, CT Eye E-1 CHl.=1.
G G=U, Eyg I-1
3. Based on Baldi & Hornik 1989)
(A, B) define a critical point of İ(A,B)
=
Σ
Y
ABX
iff they satisfy
= AA and ABA BY
(48)
ABE,, B'= B'.
(49)
Again by assumption (A, B) define a critical point of L( B) so by Theorem they are of the form given by eq. ( and eq. 9 with the proceeding conditions on the invariance C. Hence,
A' ABE =DC U. CDD 1 UC Eyz
20

---

Under review as a conference paper at ICLR 2020
DCC U2 Ey
C
cTl.=I
A'ABE =DC 2
A A'E ym.
Hence, eq. (48) is satisfied. For the second equation we use the first property of this corol-
lary that is BE B' is diagonal and satisfy eq. 7 of Proposition 2 that is
BE., B' diagonal
A (S, (BErr B))) = BT,
BE., B' is diagonal
AT, B gn B' - BTg
ABE,; BT, = BTp AB B' -y B'.
Hence, the second condition, eq. (49) is also satisfied. Therefore, any critical point of
L(A, B) is critical point of AAA
A.6 PROOF OF LEMMA
Proof. We have
L( = Σ Y - BX Σ Y Al BX,Y A B
1=1
= Σ
YY + (Y, AT BX) + A-
1=1
AI BX, A
P
= -YYY - -((Y,A ΣLED
BX) + Σ (AL BX, BX)
09. 23
=PT((YY) 2T (AT, +
TT AT BX)
P = -p'T(EEnn) - Tr (AT,BEngg) TT XX'B'
(Jip A'A B
eq. 24
i=1
=p'T(EE,n)) - 2 (AT, BE.g) + Tr (B' (S, o (A' A)) BE.>),
which is eq.
17
A.7
PROOF OF THBOREM 2
Proof. The full rank matrices A' and B" given by eq. (8) and eq. (19) are clearly of the form given by Theorem [ with I, Np = f1.2.... .P). and II, = Ip. Hence, they define critical point of L(A, B). We want to show that these are the only local minima, that is any other critical (A, B) saddle points. The proof similar the second partial derivative test. However, in this case the Hessian is forth order tensor. Therefore, the second order Taylor approximation of the loss, derived in Lemma 4 used directly. To prove the necessary condition, we show that at any other critical point (A, B), where the first order derivatives are zero, there exists infinitesimal direction along which the second derivative of loss is negative. Next, for the sufficient condition we show that the any critical point of the form (A", B*) ) is a local and global minima.
The necessary condition:
Recall that UI, is the matrix of eigenvectors indexed by the p-index set Ip and II is permutation matrix. Since all the index sets T,, r S p are assumed to be ordered, the only way to have Up, Un II is by having I, = N, and IT p. Let A (with no zero column) and B define an arbitrary critical point of L B). Then Based on the previous theorem, either A U C
with r < or A = U, IID while both cases B = B(A) given by eq. (6) (A, B) is not of the form of (A", B*) then there three possibilities either 1) A Ur, CT with p, 2)
21

---

Under review as a conference paper at ICLR 2020
A U IID having the "right" and/or "enough" eigenvectors. and the third corresponds to not having the "right" ordering. We introduce the following notation and investigate each case separately. Let >> 0 and Uny E Rexp be matrix of all zeros except the 7th column, which contains Uy; the eigenvector of E corresponding to the yth largest eigenvalue. Therefore,
IID with + Ny or A U but II +Ip. The first two cases corresponds to not
EU UAU'US = E,
(50)
where, E, R is matrix zeros except the 1th diagonal element that contains In what follows, for each case we define a encoder direction V E Rx with || O and set the decoder
direction W E [2x as W W == (Sp o (A'A)) -1 T, y' Then we use eq. 30) and eq. (31 of Lemma 4 to show that the given direction (V, W) infinitssimllly reduces the loss and hence, in every case the corresponding critical (A, B) is a saddle point.
1. For the case A = CD, with r < p, note that based on the first item in Corollary | B' is ap x diagonal matrix of rank so has p- zero diagonal elements. Pick an i N₂ such that (BE,,') B',, n is zero and a j E Np \ \ Set V = =U D and W = W. Clearly,
V'A = DU CD.
(51)
V'VT,BE mm B' = DU, U.s DT,,E,,,
= D' B'
E (BE,,. B') = 0 and
(52)
V'EV = DDU
D
(53)
Notice, | [ || = =O(s), so based on eq. (30) of Lemma
we have
L(A+ V B W) I[(A, B)
(V BY rr B') -Tr V'EVT, (Sp (A'A))
+2T V A S, .BE. VT, (Sp (A) 1 + (S, (A'A))
+ +
51
L(A V. B W) B)A
TTr V V'EVT, (A'AA) TTp) 0(+))
eg.
VA-DC'CD
U(A V, B W) - L)A
- Ir
D'E.D-
T T STT
o (C'O) D-1 +0(58)=
- ((), " +0(E"). i
Therefore, since ($, a (C'C)) -1
is positive definite matrix, as --> -+00, 0, we have I.(A + V.B W) < L(A, B). Hence, any (A, B) (UI,CD) B(U, with r < is saddle point.
2. Next, consider the case where A U, ip IID with I, + Np. Then there exists at least one E 4p N, and i E N, L, such that i < j (so A; >y). Let be the permutation corresponding to the permutation matrix II. Also, let > 0 and Un(): E Raxp be a matrix of all zeros except the oi) column, which contains u;; the eigenvector of Σ corresponding the 7h largest eigenvalue. Set V =Uao): and W W. Then, since & Ip have
V'U = DDDU' U1 =0,
(54)
V'V = DU' DU' Uonna ²D2 =DDDEoo), and
(55)
22

---

Under review as a conference paper at ICLR 2020
V'EV =E UAU
otj): D= = x2 Er())
(56)
Since |V W F - O(e), based on eq.
31 Lemma 4 we have
L B + W) L(A, Tr (V VII A IIT, D D) Tr (V'EVT,D'
+2Th (V'U,,
IID S D UT EVD
+2Th ( IDD Ss D VE IID
54
+0(e
56
MA+V, - L(A, = Tr (e D2 Eog II AT D
- Tr (= E EOú) D, 9) + (ss)))
=r Tr E II' A I HTT, -E² Tr (B) +0(=²)
= Tr (Ba()) Tp)) ^; Tr E (1()) Tp) + (E
6 o(j) (1, + +(=)).
Note that in the above, the diagonal matrix II' A1, II has the same diagonal elements as AG, but they are permuted by σ. So Eoú,) IT' As, s, selects x diagonal element of II' Ar, II that is the j diagonal element of AJ,, which is nothing but Xy. Now, since i < A > Xy and ojj) p. as - O, we have L(A+ V, B + W) S LAA.B) Hence, any (A, B) = (Ui, IID, B IID)) is a saddle point.
3. Finally consider the case where A = UR, IID with II * Ip. Since II + Ip, the per- mutation of the set Np, corresponding to the permutation matrix II, has at least a cycle (1,22-0 ... )x), where < i, < 12 i..... < ig < and 2 S k S p. Hence, II can be decom- posed as II = II (in II, where II is the permutation matrix corresponding to other cy- cles of a. The cycle (1 can be decomposed into transpositions as (i102 --. in) (ixin- 1) (igi)), which in matrix form is (31 Therefore, II can be decomposed as II = (((s))) II, where ī II (igis)) (ixiee-))) II. Note that Il ((g4)) the permutation matrix corresponding to transposition (ixi)) is a sym- metric involutory matrix, i.e. IT2 (1 Ip- Set V (Unn,, Unati IDD and W -W. Again we replace V and W in eq. (3I) of Lemma There are some tedious steps sim- plify the equation, which is given in appendix [A.7.] The final result is as follows. With the given V and W, the third and forth terms the RHS of eq. (37) are canceled and the first two terms are simplified to
( (art2) (1
Tr (V'VIT'AN, IT, =
Ar, (p - im + 1), and Tr (V'EVT D D-2)--)) =E=)= +1 + ^,,, (p im + 1),
(57)
(58)
in which, m max(k: (11 then im = iz. But if for the selected cycle (λ1 -. i k is greater than 2 then fm = f--1- Using above equations, eq. (31 yields
2). This means that If the selected cycle is just a transposition
L(A+V, L(A, Tr (V VIT A ITT,D (V'VVV +0(E))
= d2, i + 1) + 22 Xi t (p i im + 1)
-8 >i - - -
(p-ine im + 1) + 0
- - - -mi + =i1 + +miin
-
8² (()is )im -1)) + 0
(59)
By the above definition of êm we have i.. in > 0 and since é1 < it. di Xig > 0.
Hence, the first term in the above equation negative and as E - 0, we have L (AA +
V, B + w) L(A, B) < O. Therefore, any any (A, B) = (U, IID, B(U II)) with II # Ip is saddle point.
23

---

Under review as a conference paper at ICLR 2020
The Sufficient condition:
From Lemma |
we know that the loss L(A, B) can be written in the form of eq.
17
Use this
equation evaluate loss at (A*, B²) (UN, Dp. D p
U Eyz E,1 follows
L(A', BB) p (r) 2Th (A Exy Tr B" Sp o A A'' B'Ezz)
=
, = p Tr(
2Tr
D.T.D UK
Eya Da Ezz
+ T
(S,)
Dp Un Un, D3)
Dj UK Dyz 2x
Eza
1-15 28
Day Un, D2'
=
L(A', B²) p (r(Ewy) - 2TT T, D U EUN,
+ TT (( ((500 (k)) (4p)
DDD UN EUN, P Dp
L(A", B3) = pT)) 2TH (TAAN,) Tr (pAN,)
L(A', ( = Tr - Tr (TGAR,,) = Tr (gg)
10-
which is eq. (20). as claimed. Notice that the above value independent of the diagonal matrix D From the necessary condition know that any critical point not in the form of (A* B*) is saddle point. Hence, due to the convexity of the loss at least one (A", B²) is a global minimum but since the value of the loss (A', .B") is independent of D, all these critical points yield the same value for the loss. Therefore, any critical point in the form of (A", B²) is a local and global minima. D
A.7.1 SUPPLEMENTARY DETAILS OF THE PROOF OF THEOREM
To verify eq. 57 eq 58 and eq. (59 in the proof of Theorem 2 we want to replace V and W in
eq. 31 of Lemma with V = m0:1 Usi IID and W = W and simplify. eq. 31 is
L(A V B W L(A, Tr (V'VIT'A A IIT, D 2) Tr (V'EVT,
+2 (V'U,, IID S D (D-'IT' EVD +2Th (V'U, IID (S, (D V'',, IID +0(5)).
We investigate each term on the RHS separately. but before note that
E,UT, = (iI,, E. (Tp) E. (p- 1)EE,
(60)
where, ē and its function inverse --1 permutations corresponding πi and IT' respectively. IT' is a diagonal matrix where diagonal elements of Tp ordered based on Ø-1 More- over, recall that we decomposed the permutation matrix II in A with a cycle (i1d ... is) as II ((r)e) ((())))) II (iris-))) ( II, where i,, i2, .-- in are fixed points of I. There-
fore, with being the permutation corresponding to II we have
o(in) = = ā -- (i1) i1, and (4x im r - ims
(61)
(62)
where, m = max(k- 1, 2}. This means that If the selected cycle is just transposition (i10)) then
im = 12. But if for the selected cycle (.id2...ig) is greater than 2 then im i
For the first term we have
U Uw
V'V =6² (U (, U Ulena (U
-Uaste DiD
24

---

Under review as a conference paper at ICLR 2020
Ur Unge Uiios B.y
V'V DU 11:11 Uni + +
Unig Unaia DTD
Unii Uniin E.y
(B, + Ei ) diagonal
V'V DI' -E, IDD
V'V = + E DI
(VV'VI''A,,TTTDD = VV D II' (14)) As, N ((os)) LTT,
= Tr
e'II' [E; + E ID
(11i)) Ag,
II (a
Lp
Tr (E., + E II (bri)) AN, Il (ia iT,
= Tr \11 E,, iTT, + X13 E., IT, iT
oq. 60
Tr (V'' D =6² No. (p ā 5- (ii) 1) Ei, + (p - -ix)) + E
Tr (V'VIT'A IT, IT, 3) = 2 Xo (p 1, + 1 E;, + + (p im + Ein which is eq. as claimed.
For the second term we have
V'EV DU 115h ( - -Uis LĀD
= DI' Wit UAU'U U UAU'U
Ary F.
U ini UAU' +U
Desi UAU'U IL
Aig Eig
"Ai E,, + An EN
Tr (V'EVT,DD') = Tr (T: E,, + > Eig DID D-
= Tr \1 E., iTT, fT' + Ao. E., 1TT, IT'
eq.
( = Xi, (p à (1n) 1) Xi. (p 5 (ike + 1)
eq.
cq. 62
Tr (V -p- - 11 + 1 + + (p im + +),
which is eq. 58 as claimed.
Finally, we have to show that the third and the forth terms of the eq. 31 are canceled. First, observe that
Tr (V'U,, IID
S, o D ''', EVD -VD- )) =
Tr (U ( U minh UN, II Sp IT'U EVD-2 2))
eTr (TT( E Sp IT'U EVD 2) D
2 (iI - EiJ)II Sp (Xi, Ei, di E,, | 1))
Tr (E ( E )ii) ( (IS
IIII' (Ai, E., d E. iin )))
T ( (EE Eii.) (Aig Eij Xi E,, 11
$² T (I.,, (dis Ei, + >in E.,) )) and
Tr (V's,, IID (Sp (D 2--V'E EU ID (D-1))
25

---

where, 4 ... ig are fixed points of permutation corresponding to ń so i' has the same values at diagonal positions i and ig as the original matrix Sp. The only permutation that is only on the left side is ( which exchanges the i and ig rows of Sp. Since S, is such that the elements at each row before the diagonal element are the same and in i1, we have the i and in diagonal Under review as a conference paper at ICLR 2020
Tr (=DIT(UU,.. 1ith - U UU II (Sp DD V'EUN, ID 1))
eTr (i E,, II Sp (D EUN, m1 =
T² (B, - E Sp (A En >ix E iT'
2² (En - Eis) (II,, (III Ei - X Ei
=²Th (E,, - Eii)) (IS, (II (A,, E,, - -Ni Eis II ((b)))))
8² Tr (Ei, Ei,) [IS,IIT]) o ((Ai E;, X1, E En,)))
e² Ir (II,, ((E, (Ai, Bi, ^i Ei,)) Tr (IS, (As, Ea A Es,)) Tr II))) (Ni, Ei, Ai. E,,))
Now, note that in both cases the matrices that are multiplied elementwise with II are diagonal and hence, only need to look at diagonal elements of IIS,IT Morcover,
IS, = (1r (1.)))) ... II (1yi IIS (wvie11) (.(I))))))))
elements of IIS II' have the same value. Let that value be denoted as Then the sum of the above two equations yields m(As, + dix)) m(,,, + die) = 0, as claimed.
26

---

Under review as a conference paper at ICLR 2020
B DERIVATIVES OF THE LOSS FUNCTION
B. FIRST AND SECOND ORDER FRÉCHET DERIVATIVE
In order to derive and analyze the critical points of the cost function which is real-valued function of matrices we use the first and second order Fréchet derivatives as described in chapter 4 of Zeidler 1995). For function f Ruxm + IR the first order Fréchet derivative at the point A E R"x" is linear functional df (A) R + R such that
[A + V) f(A) (A)V
lim
||
where we used the shorthand of (A)V (d)())) Similarly, the 2nd derivative is a bilinear functional de (AA [R x Raxm + R such that
df df(()K - f(A)VK 0,
lim
I for all | I 1, where again d d(f(AVVK (A))( K). The generalized Taylor formula then becomes:
f(A+ + V) f(A) - VV)) + [(AV22 + +oll 13),
2
Moreover, we derive functions Vf Raxm + Raxm and H(A) R + R such that V (A), V)F and o' f(A)2 (V)(V). Then clearly, A BR critical point of f iff (A(A) 0 and for such As the sign of the bilinear form (H()), Voovver directions determines the type of the critical point.
(H() V)F, where again (()
Extending the generalized Taylor theorem of Zeidler 1995). the second order Taylor expansion for the loss L(A, A, B) is then given by
L(A V B w) L(A.B) = B)V + ddBL(A 2 L.,
BA + H LLLAA + (v.
(63)
where, if VIIF I. / = O(E) then |R(V, = Clearly, as at critical points where dAL(A, BVV B) = 0, as 0 we have K..w(A. B) and the sign of the sum of the second order partial Fréchet derivatives determines the type of the critical point very much similar second partial derivative test for two variable functions. However, here for local minima we have to show the sign is positive in all directions and for saddle points have to show the sign is positive in some directions and negative least in on direction. Finally, note that the smoothness of the loss entails that Fréchet derivative and directional derivative (Gateaux) both exist and (foregoing some subtleties in definition) are the same.
B.2 FIRST AND SECOND ORDER DERIVATIVE OF THE LOSS WRT TO B
Lemma 5. The first and second (partial Fréchet derivative of the loss L(A, B) wri to B is derived as follows.
d (A, B)W= -2Tr (W' (T, yr (Sp o (A'A)) BE
(64)
= A'',,A'E, yar (Sp o (A'A)) BE W)F-
(65)
B)) = =((SS, (A'A)) WEg., W)F = 2Tr (W' (S, (A'A)) WE,.).
(66)
Proof. Directly compute
L(A, w = Σ - AI B + 2
1=1
27

---

Under review as a conference paper at ICLR 2020
p
ALE (B+
(B W)
P Σ - AI a - AA w
Y Al B AL BX) F
i=1
Al WX,Y - BX) +
A- WX, - A
L( B 2
,
BX, A WX) (( =
1=1
- - = -2 -2 - BX + "=
2=1
(BL(A, - Σ
IIX - A
i=1
III Al BXXx)
= - W
Σ Tep
A'YX-
= 2TT ( (T,A'XX' (Sp -Sp (A) BXX)),
which can be written the given form. For the second derivative B we have
dBL(A, B)W = -2(TT,A'' gm (S, (A)A)) BE W)F = dBL(A, + W)W = -2(T, ze (S, (A'A)) (B + W) W)F
= -22 yu (Sp o (A'A)) BE W)F
+ + o (A'A)) WE Z8: W)F F
=
dBL(A, B W)W - LBL = 2((S,, (A'A)) WE a22 W)F,
which by having W - results in the second order partial derivative.
B.3 FIRST AND SECOND ORDER DERIVATIVE OF THE LOSS WRT TO A
Lemma 6. The first and second (partial Fréchet derivative of the loss L(A, B) wrt A is derived
as follows.
dAL,A, B)V= , A (S, o B)),
(67)
B) 22 WT,, AS, o (BE,, (B)) A (S, (WE,,, B')) V)r
(68)
B) 2(V (S, (BE B')) V)F.
(69)
Proof. Directly compute
I(A = Σ Y VA+ BX, (A , BX)r
Σ (Y AI,
AL BX)
Σ Al BX, V VI
VI &
BX,
AL BX p Σ
--, - VI BX)
= L)
2 -A
BX, V ip
BX) F
V VI. BX VX
28

---

Under review as a conference paper at ICLR 2020
P
MA+ - =- Σ 2(Y BX, BI + O(IVI))) =
P
dAL(A, Σ 2(Y Al ug
VI hp B BX)
- B' Σ 1pp A
Lup BEgg B' B =
i=1
dAL B)V BT,, A (Sp p
1) V)F
d V. B)V -2 (A+ V) () o BB V)F F
dAL(A+V.BV dAL B (Sp BB B')) V)F =
(V V) 2(V (S, 0 (BEgr B')) V)F =
A= B) = 2(V (S, o (BE B)),, V)F
dAL(A, B W)V 2(E ( (B TT V)F (S (l + W W)E (B + WY)), V)F
B'T, (S, (BE,B'')) V)F
=dAL(A, B)V - 2 np WT V)F
(2, (BE,, W')) (S,
V)D (
BAL(A,B+W]) dAL(A, -2 WTp, V)F
-2(-A (BE,H) W')) - A (WE,,, V)r
+ (::)
W-0
LA B\VW- N-=--Qg 2(E WT, (S, (BE,, W')) AS, 0 (WE,, V)F.
29


Reviews:
[{"review_id": "SylQ9IDCtB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new loss function for performing principal component analysis (PCA) using linear autoencoders (LAEs). With this new loss function, the decoder weights of LAEs can eventually converge to the exact ordered unnormalized eigenvectors of the sample covariance matrix. The main contribution is to add the identifiability of principal components in PCA using LAEs and. Two empirical experiments were done to show the effectiveness of proposed loss function on one synthetic dataset and the MNIST dataset. \nOverall, this paper provides a nontrivial contribution for performing principal component analysis (PCA) using linear autoencoders (LAEs), with this new novel loss function. This paper is well presented.\nThere are some issues to be addressed:\n1. The output matrix is constrained to be the same size of the input, which is scarcely seen in practical applications.\n2. Literature on (denoising) auto-encoder can be reviewed more thoroughly.\n3. Comparison with state-of-the-art auto-encoder can be provided to demonstrate the effectiveness of the proposed algorithm.\n4. It is better to explain the meaning of each variable when it first appears, e.g., , the projection matrices A and B, and Variable A* in theorem 2.\n5. In the experiment part, in both the Synthetic Data or MNIST, the size of each data set is relatively small. It's better to add experimental results on big data sets with larger dimension.\n6. In order to better show the effectiveness of the new loss function, you can add some comparative test for different choice of compressed dimension p.\n7. There are some typos, such as ‘faila’ in the second line of the second paragraph in the INTRODUCTION. \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HkxnO6hitS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new loss function to compute the exact ordered eigenvectors of a dataset. The loss is motivated from the idea of computing the eigenvectors sequentially. However doing so would be computationally expensive, and the authors show that the loss function they propose (sum of sequential losses) has the same order (constant less than 7) of computational complexity as using the squared loss. A proof of the correctness of the algorithm is given, along with experiments to verify its performance.\n\nThe loss function proposed in the paper is useful, and the decomposition in Lemma 1 shows that it is not computationally expensive. While the writing of the proofs of the theorems is clear, I find it hard to understand the flow of the paper. It would help if the authors could summarize the argument of the proof at the start of Sec 4. Along a similar vein, it would also help if the authors could describe in words the significance / claim of every theorem.\n\nThe repetition in stating the theorems can be avoided. The main result (Theorem 2) is stated twice.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "Byl_DpEy9S", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes and analyzes a new loss function for linear autoencoders (LAEs) whose minima directly recover the principal components of the data. The core idea is to simultaneously solve a set of MSE LAE problems with tied weights and increasingly stringent masks on the encoder/decoder matrices. My intuition is that the weights that touch every subproblem are the most motivated to find the largest principal component, the weights that touch all but one find the next largest, and so forth; I found this idea clever and elegant.\n\nThat said, I lean towards rejection, because the paper does not do a very good job of demonstrating the practical or theoretical utility of this approach. As I see it, there are two main claims that one could make to motivate this work:\n1. This is a practical algorithm for doing PCA.\n2. This is a step towards better understanding (and perhaps improving) nonlinear autoencoders, which do things that PCA can't.\nClaim (2) might be compelling, but the authors do not make it, and it isn't self evident.\n\nI do not find claim (1) convincing on the basis of the evidence presented. PCA is an extremely well studied problem, with lots of good solutions such as randomized SVD (Halko et al., 2009). A possible advantage of using LAEs to address the PCA problem is that they play nicely with SGD, but again, the claim that the SGD-LAE approach is superior to, say, randomized SVD on a data subsample requires evidence. Also, even if one buys the claim that LAEs are a good way to solve PCA, one can always recover the eigenvectors/eigenvalues by a final decomposition step; the authors claim that an advantage of their approach is that it does not require such \"bells and whistles\", but this seems like a pretty minor consideration; implementing the proposed loss function seems at least as complicated as making a call to an SVD solver, and it's hard for me to imagine a situation where the cost of that final SVD isn't dominated by the cost of solving the MSE LAE problem.\n\nIn summary, I think this paper proposes a clever and elegant solution to a problem that doesn't seem to be very important. I can't recommend acceptance unless the authors can come up with a stronger argument for why it's not just interesting but also useful.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Quoting from R3: "This paper proposes and analyzes a new loss function for linear autoencoders (LAEs) whose minima directly recover the principal components of the data. The core idea is to simultaneously solve a set of MSE LAE problems with tied weights and increasingly stringent masks on the encoder/decoder matrices."  With two weak acceptance recommendations and a recommendation for rejection, this paper is borderline in terms of its scores.

The approach and idea are interesting.  The main shortcoming of the paper, as highlighted by the reviewers, is that the approach and theoretical analysis are not properly motivated to solve an actual problem faced in real-world data.  The approach does not provide a better algorithm for recovering the eigenvectors of the data, nor is it proposed as part of a learning framework to solve a real-world problem.  Experiments are shown on synthetic data and MNIST.  As a stand-alone theoretical result, it leaves open questions as to the proposed utility.
Decision: Reject