We call (k)a lift of T(k)onto M(A)and T(+1)a projection of (k)onto T(a).The projection operation is easy to complete.Suppose()=[then T()=[must be given by ty ∫，ifi卡j ai;ifi=j (5) For the lift operation,we have the following Theorem 3. Theorem 3.Suppose T =QTDQ is an eigen-decomposition of T where D =diag(d)with d=(d,d2dmT being T's eigenvalues which are ordered as d2d2.zdm.Then the nearest neighbor of T in M(A)is given by Z=QTAQ. (6) Proof.See Theorem 4.1 in [3]. 口 Since in each step we minimize the distance between T and Z,we have IT-ZlF≥lTk+)-ZF≥IlTk+)-Zk+9lF. It is easy to see that(T(),())will converge to a stationary point.The whole IsoHash algorithm based on LP,abbreviated as IsoHash-LP,is briefly summarized in Algorithm 1. Algorithm 1 Lift and projection based IsoHash(IsoHash-LP) Input:XE Rdxn,m EN+,tEN+ [A,W]=PCA(X,m),as stated in Section 2.2. ·Generate a random orthogonal matrix Qo∈Rmxm 。Zo)←Q6AQ0- ●fork=1→tdo Calculate T(k)from Z(k-1)by equation(5). Perform eigen-decomposition of T(k)to get QTDQ=T(k). Calculate Z(k)from Q&and A by equation (6). ●end for ·Y=sgn(QTWTX). Output:Y Because M(A)is not a convex set,the stationary point we find is not necessarily inside the intersec- tion of T(a)and M(A).For example,if we set Z(0)=A,the lift and projection learning algorithm would get no progress because the Z and T are already in a stationary point.To solve this problem of degenerate solutions,we initiate Z as a transformed A with some random orthogonal matrix Qo, which is illustrated in Algorithm 1. 2.3.2 Gradient Flow Another learning algorithm is a continuous one based on the construction of a gradient flow (GF) on the surface M(A)that moves towards the desired intersection point.Because there always ex- ists a solution for the problem in(3)according to Theorem 2,the objective function in(4)can be reformulated as follows[2: (Q)lldiag(QTAQ)-diag() (7) The details about how to optimize(7)can be found in [2].We just show some key steps of the learning algorithm in the following content. The gradient VF at Q can be calculated as 7F(Q)=2A6(Q): (8) where B(Q)=diag(QTAQ)-diag(a).Once we have computed the gradient of F,it can be projected onto the manifold O(m)according to the following Theorem 4.We call Z (k) a lift of T (k) onto M(Λ) and T (k+1) a projection of Z (k) onto T (a). The projection operation is easy to complete. Suppose Z (k) = [zij ], then T (k+1) = [tij ] must be given by tij =  zij , if i 6= j ai , if i = j (5) For the lift operation, we have the following Theorem 3. Theorem 3. Suppose T = QT DQ is an eigen-decomposition of T where D = diag(d) with d = [d1, d2, ..., dm] T being T’s eigenvalues which are ordered as d1 ≥ d2 ≥ · · · ≥ dm. Then the nearest neighbor of T in M(Λ) is given by Z = Q TΛQ. (6) Proof. See Theorem 4.1 in [3]. Since in each step we minimize the distance between T and Z, we have ||T (k) − Z (k) ||F ≥ ||T (k+1) − Z (k) ||F ≥ ||T (k+1) − Z (k+1)||F . It is easy to see that (T (k) , Z(k) ) will converge to a stationary point. The whole IsoHash algorithm based on LP, abbreviated as IsoHash-LP, is briefly summarized in Algorithm 1. Algorithm 1 Lift and projection based IsoHash (IsoHash-LP) Input: X ∈ R d×n, m ∈ N +, t ∈ N + • [Λ, W] = P CA(X, m), as stated in Section 2.2. • Generate a random orthogonal matrix Q0 ∈ R m×m. • Z (0) ← QT 0 ΛQ0. • for k = 1 → t do Calculate T (k) from Z (k−1) by equation (5). Perform eigen-decomposition of T (k) to get QT k DQk = T (k) . Calculate Z (k) from Qk and Λ by equation (6). • end for • Y = sgn(QT t WT X). Output: Y Because M(Λ) is not a convex set, the stationary point we find is not necessarily inside the intersec￾tion of T (a) and M(Λ). For example, if we set Z (0) = Λ, the lift and projection learning algorithm would get no progress because the Z and T are already in a stationary point. To solve this problem of degenerate solutions, we initiate Z as a transformed Λ with some random orthogonal matrix Q0, which is illustrated in Algorithm 1. 2.3.2 Gradient Flow Another learning algorithm is a continuous one based on the construction of a gradient flow (GF) on the surface M(Λ) that moves towards the desired intersection point. Because there always ex￾ists a solution for the problem in (3) according to Theorem 2, the objective function in (4) can be reformulated as follows [2]: min Q∈O(m) F(Q) = 1 2 ||diag(Q TΛQ) − diag(a)||2 F . (7) The details about how to optimize (7) can be found in [2]. We just show some key steps of the learning algorithm in the following content. The gradient ∇F at Q can be calculated as ∇F(Q) = 2Λβ(Q), (8) where β(Q) = diag(QTΛQ) − diag(a). Once we have computed the gradient of F, it can be projected onto the manifold O(m) according to the following Theorem 4. 5