Effective Subspace Indexing via Interpolation on Stiefel and Grassmann manifolds
Authors: Wenqing Hu
Tiefeng Jiang
Zhu Li
Venue:  (2021)
Keywords: subspace indexing
locality preserving projection
Stiefel and Grassmann manifolds

Abstract: We propose a novel local Subspace Indexing Model with Interpolation (SIM-I) for low-dimensional embedding of image datasets. Our SIM-I is constructed via two steps: in the first step we build a piece-wise linear affinity-aware subspace model under a given partition of the dataset; in the second step we interpolate between several adjacent linear subspace models constructed previously using the `"center of mass" calculation on Stiefel and Grassmann manifolds. The resulting subspace indexing model built by SIM-I is a globally non-linear low-dimensional embedding of the original data set. Furthermore, the interpolation step produces a `"smoothed” version of the piece-wise linear embedding mapping constructed in the first step, and can be viewed as a regularization procedure. We provide experimental results validating the effectiveness of SIM-I, that improves PCA recovery for SIFT dataset and nearest-neighbor classification success rates for MNIST and CIFAR-10 datasets. 

Under review as a conference paper at ICLR 2021
EFFECTIVE SUBSPACE INDEXING VIA INTERPOLATION ON STIEFEL AND GRASSMANN MANIFOLDS
A Anonymous authors
Paper under double-blind review
ABSTRACT
We propose novel local Subspace Indexing Model with Interpolation (SIM-I) for low-dimensional embedding of image data sets. Our SIM-I is constructed via two steps: in the first step we build piece-wise linear affinity-aware subspace model under a given partition of the data set; the second step we interpolate between several adjacent linear subspace models constructed previously using the "center of mass" calculation on Stiefel and Grassmann manifolds. The resulting subspace indexing model built by SIM-I globally non-linear low-dimensional embedding of the original data set. Furthermore, the interpolation step produces a "smoothed" version of the piece-wise linear embedding mapping constructed in the first step, and can be viewed as a regularization procedure. We provide experimental results validating the effectiveness of STM-I, that improves PCA recovery for SIFT data set and neirest- classification success rates for MNIST and CIFAR- data sets.
INTRODUCTION
Subspace selection algorithms have been successful in many application problems related dimen- sion reduction (Zhou et al. (2010). Bian & Tao (2011), (Si et al. (2010), Zhang et al. (2009),, with applications including, e.g., human face recognition (Fu Huang (2008)) speech and gait recogni-
tion (Tao et al. (2007), ) etc.. The classical approaches of subspace selection in dimension reduction include algorithms like Principle Component Analysis (PCA, see Jolliffe (2022) and Linear Dis- criminant Analysis (LDA, see Bellhmeur et al. (1997). Tao et al. (2009) They are looking for globally linear subspace models. Therefore, they fail to estimate the nonlinearity the intrinsic data manifold, and ignore the local variation of the data (Saul & Roweis (2003), SStrassnn (969)), )) Consequently, these globally linear models are often ineffecttve for search problems on large scale image data sets. To resolve this difficulty, nonlinear algorithms such as kernel algorithms (Ham al. (2004) and manifold learning algorithms (Belkin et al. (2006), Guan et al. (201T)) are proposed. However, though these nonlinear methods significantly improve the recognition performance, they face serious computational challenge dealing with large-scale data sets due to the complexity of matrix decomposition at the size of the number of training samples.
W.
W
W
W.
(b)
Figure I: The idea of "smoothing" a piece-wise linear low-dimensional embedding model: (a) The piece-wise linear low-dimensional embedding model built from LPP; (b) The regularized low- dimensional embedding by taking Stiefel//rassmann manifold center- of-mass among adjacent lin- ear pieces.

---

Under review as a conference paper at ICLR 2021
Here we propose simple method, Subspace Indexing Model with Interpolation (SIM-I), that produces from a given data set a piece-wise linear, ppcality-awarg and globally nonlinear model of low-dimensional embedding. SIM-I I is constructed via two steps: in the first step build a piece- wise linear affinity-aware subspace model under a given partition of the data set; in the second step interpolate between several adjacent línear subspace models constructed previously using the "center of mass" calculation on Stiefel and Grassmann manifolds (Edleman et al. (1999). Kaneko al. (2013), Marrinnan et al. (2114). The interpolation step outputs a "smoothed" version (Figure D of the original piece- wise linear model, and can be regarded as regularization process. Compared to previously mentioned subspace methods, SIM-I enjoys the following advantages: (1) it captures the global nonlinearity and thus the local fluctuations of the data set; (2) it is compulationally feasible to large-scale data sets since avoids the complexity in matrix decomposition at the size of the number of training samples; (3) it includes regularization step via interpolating between several adjacent pieces of subspace models. Numerical experiments on PCA recovery task for SIFT data set and classification tasks via nearest-neighbor method for MNIST and CIFAR-10 data sets further validate the effectiveness of SIM-I.
2 PIECE-WISE LINEAR LOCALITY PRESERVING PROJECTION (LPP) MODEL
If an image data point x E R. is represented as vector in a very high-dimensional space, then we want to find low-dimensional embedding y = f(x E Rd d << D such that the embedding function f retains some meaningful properties of the original image data set, ideally close to its intrinsic dimension. If we restrict ourselves to linear maps of the form y WT x E Rd where the D x d projection matrix W = Di (assuming full rank), then such a procedure is called locally linear low www-imensiiona embedding (see Roweis & Saulm 2000); Van Der Maaten
et al. 2009)). ) The target is to search for a "good" projection matrix W. such that the projection + V WT x must preserve certain locality in the data set (this is called Locality Preserving Projection, or LPP projection, see He & Niyogil (2003)). The locality is interpreted as a kind of intrinsic relative geometric relations between the data points in the original high-dimensional space, usually represented by the affinity matrix S = (81g) (which is symmetric matrix with non-negative terms)) As an example, given unlabelled data points 21. In E RR," we can take || when ||x;; - xz < & and 8/j = 0 otherwise. Here o 0 and e > 0 is 20
Sij = =exp
small threshold parameter, and ||x; -xyll is the Euclidean norm in RR, Based on the affinity matrix S = (sig). the search for the projection matrix W can be formulated as the following optimization problem
min <(W) = Siz lus - y/
1
Σ
(1)
W
2
i,==1
in which y/ = WT x; and y₁ = WT xy and the norm |ay: y || is taken in the projected space Rdd Usually when ||=; x,y || is large, the affinity 8ij will be small, and vice versa. Thus ① is seeking for the embedding matrix W such that close pairs of image points x; and xy will be mapped to close pairs of embeddings y/i = W I, and y,, = W W and vice versa. This helps to preserve the local geometry of the data set, a.k.a the locality. To solve ( we introduce a weighted fully-connected graph G where the vertex set consists of all data points .i., Tn and the weight on the edge con- necting z; and zj is given by Sty 0. Consider the diagonal matrix D dia.((D...... Drn)) where
Du Σ Sij, and we then introduce the graph Laplacian = D - S. Then the minimization
problem 11, together with the normalization constraint
Σ Drvi = 1, reduces to the following
generalized eigenvalue problem (see He & Niyogi (2003)
XLX w =
(2)
where X [r,,..., ..... Fn
R Dxn
Assume we have obtained an increasing family of eigenvalues = Ay < < S.. A Let the corresponding eigenvectors be wo, W1, -.. Wn-1- Then the low-dimensional embedding matrix can
2

---

Under review as a conference paper at ICLR 2021
be taken as W (W1..... wa] (see He et al. (2005). By choosing different affinity matrices S (Sty), the above LPP framework includes many commonly seen practical examples. For example, the data 21, In are not labelled, then can take sty and (2 produces the classical Principle Component Analysis (PCA), For labelled data forming subsets X1 ..... Xm with same labels in each when Ty Rx and 8ij other-wise. Here nu is the cardinality of Xz. This will produce Linear Discriminant Analysis (LDA). The detailed justifications of these connections can be found in He et al. (2005).
1
subset, we can take Stj T
Given an input data set X' { Ln where each I; E RD,, either labelled or unlabelled, we can apply a k-d tree (Bentley 1975), Wang et al. (201T) based partition scheme to divide the whole data set X' into overlappeippngggggg. subsets Ci. O2 where h is the depth of the tree. Conventional subspace selection algorithms could be applied on the whole sample space before the whole space partitioned and indexed. For example, we can first apply a PCA to X, which selects the first d bases ....... da] with largest variance. Based on these bases, the covariance information obtained from global PCA is utilized in the indexing as follows: (1) we project all sample points I1, In onto the maximum variance basis 01, then we find the median value mı of the projected samples, and split the whole collection of data along d1 at m2, i.e. split the current node into left and right children; (2) starting from level i 2, for each left and right child, project the whole collection of data along the i-th maximum variance basis a, find the median value m,, and split all the children m,; (3) increase the level from i i and repeat (2) until i = h reaches the bottom of the tree. We collect all the 2 children at level i = h and obtain the disjoint subsets Cl,..., C2t. Each subset CR. k 1, 2.2..... 2h consists of family of input data in R... Based on them, using the above LPP framework, for each Ck. a low-dimensional embedding matrix W E R can be constructed. In this way, over the whole data set X, we have constructed a piece- wiie linear low-dimensional embedding model fxx) R + Rd (see Figure aa)) where E X. This model is given by the linear embedding matrices W 1, ..., n E IR Dxd
The above model construction can be regarded as a training process from the data set X. For a given test data point æ E H.,, not included in X. we can find the closest subset Ck(ar) to it, by selecting the index k = k(x) E [1,..., 20} with the smallest distance || mx(=))l Il- Here my is the mean among all data points in the subset CR. With the subset Ck(z) chosen, we map the test point E R² to its -iw-diensionnl embedding f(x) WT. (a)) Rd Such procedure extended the piece-wise linear embedding model f(x) : RRD + nd to all testing data points in R.D
3 CALCULATING THE "CENTER OF MASS" ON STIEFEL AND GRASSMANN MANIFOLDS
Subspace Indexing (Wang al. (2011) provides a d-dimensional representation of the data set (.1...., Fn) by the subspace span W1, Wa) (WTx,, x, E RR) generated from the linear em- bedding matrix W Rgxx In this case, we are only interested in the column space of W, so we can assume that wo, Wi,... Wn-1 is an orthonormal basis []] Such a matrix W belongs to the Stiefel
manifold, defined by
Definition
(Stiefel manifold) The compact Stiefel manifold Sud, D) is submanifold of the Eu- cilidean space IR Dxd such that
St(d, = tx e Dxd, x = 11)).
(3)
As example, if we are interested in signal recovery using low-dimensional PCA embedding, the projections we calculated from PCA analysis will be on Stiefel manifolds. However, for classifica- tion tasks, the exact distance information less important than label information. In this case, two such Stiefel matrices W1 and W₂ produce the same embedding if W1 = W₂O,, for some O₂ E O(d), where (d) the group of orthogonal matrices in dimension d. In this case, the relevant embedding we obtained is point on the Grassmann manifold, defined by
If this is not the case, we can replace the matrix (wo M/ ... wn-1] by the Q matrix of the QR decoopoopoiii of itself, without changing the corresponding subspace.
3

---

Under review as a conference paper at ICLR 2021
Definition 2 (Grassmann manifold) The Grassmann manifold Gr(d, D) is defined be the quo- tient manifold Gr(d, D) = Stíd, D)/O(d) A point on Gr(d, D) is defined by an equivalence class [W] aWOa, Oa O(d) where W Dt.
Given family of elements the Stiefel Grassmann manifold, the center-of-men is defined as an element on the same manifold that minimizes the functional given by the weighted sum of square distances. To be precise, we have
Definition 3 (Stiefel and Grassmann center-of-massee Given sequence of matrices Wi...., Wi St(d, D) and a sequence of weights W WI...., Wi > O, the Stiefel center-of-mass with respect to the distance d(W1, W2) St(d, D) is defined matrix We W (W1, i...., W1; "i:Wi.... wi) E St(d, D) such that
W = W (W1,.., W,.,,,... un) = arg min WeSt(d.D)
Σ wydd (W,
Similarly, if the corresponding equivalent classes are [W1] [Wi] E Gr(d, D), then the Grass- mann center-of-ne mass with respect the distance d([W)) (W2]) on Gr(d, D) is defined the equiv- alence class [Wel. where W. = WCrr (W1,.., W1, WT, wi) E St(d, D) is such that
We = wor (W1,... Wi: wi..... wi) aig min WE
(W1,
(5)
The distances d(,, W2) or d(Wil. (W2)) can taken in different ways. For example, for Wi. W22 E St(d, D), way is to consider d(W, W2) dy(W,,,, W2) [W, W2ll p. the ma- trix Frobenius norm of Wi 22. One can also take a more intrinsic distance, such as the geodesic distance between W1 and W2 the manifold (t, D) with the metric given by embedded geom- etry (see Edleman et al. (1999). ). For [W1], [W2] E Gr(d, D), one way is to consider the projected Frobenius norm d(Wi), 1 [2]] = dpr([W]], [W2]] [ WT - W2W22 ||.. There are also many other choices, such as using the principle angles between the subspaces, chordal norms, or other types of Frobenius norms (see Edleman et al. 1999 Section 4.3)).
With respect to matrix Frobenius norm and projected Frobenius norm, the Stiefel and Grassmann center-of-mase -faesss can be calculated explicitly in the following theorems.
Theorem (Stiefel center-of-mass with respect to Frobenius norm) We consider the singular value decomposition of the matrix Σj= wy wyW, W, = 0, where O₃ E O(D) and O₂ O(d),
A (ia. >a)axd and d 2 ... N N are the singular values. Then the Stiefel O(D-d)xd
center-of mass with respect to the distance given by Frobenius norm d(W1, W2) || W2llF is (diag(1,.... 1)
given by W. O₂AO2 where A -((iingf))
O1D-djxd
Theorem (Grassmann center-of-mass with respect to projected Frobenius norm) Set Ωz = -1 E)= Wj)
Wi. We consider the singular value decomposition of the symmetric matrix
Σ RWW = QAQ" where Q E O(D) and A = diag(o?,.... o%)), 2 23. M S=1
Then the Grassmann center-of-mass with respect to the distance given by projected Frobenius norm ([Wi), [Wa]) 2- 2-1/2 [,, W2W [ || the equivalence class [Wa] determined
by W. QA. where A (diag(1, (1,,g 1)axd O(D-d)xd
4 SIM-I: INTERPOLATING THE LPP MODEL FAMILY
Recall that we have developed a piece- wise linear embedding model f(x) : :R + Rd over the data
set X {I1, m. ).). The embedding (xx corresponds family of subspace indexing models
4

---

Under review as a conference paper at ICLR 2021
m
m
x
m
m
m
m
(a)
(b)
Figure 2: There are / 3 nearby subsets C₁ C2 C3 with means m,,, mg in the training set. (a) Test point x is apparently close to mi, and thus the low-dimensional embedding ((x) taken fz) WT 2, where W1 is the LPP subspace based C1; (b) Test point has approximately the same distances to m,, m2, my, and thus the embedding f(x) is taken as f(x) = W x. where We is the Stiefel/Grassmann center-of-man for the I.P subspace models Wi, W2, Wa based C2,CC,C.
Wi...., W2A E St D) (c.g. for PCA signal recovery tasks) or [W1l.... [W.z] E Gr(d, D) (e.g. for classification tasks). Each subspace model Wi is built from LPP embedding using the subset Ck C X' developed from k-d tree and is the depth tree. Given test point x E RD that does not lie in X,
map it to the low-dimensional embedding f(x) W k(z) Rdd. The index k(x))
corresponds to the subset Ck(z)) that lie closest to In practice, we can first compute the means my over all the data points the subset C2 for each & = 1, ..... 2 and sort the distances ||x - myll in ascending order | m&, (x) S ... < | m,, (z) l1. (x)) k2.(2)) = {[,..., 2 We then take k=x))= k (x: to be the index & corresponding the shortest distance. This effective when the test point x lies significantly close to one of the subsets Ck(z). see Figure (a).
Algorithm STM-TT I: Subspace Indexing Model with Interpolation
1: Input: Data set
{.1 Tn E RD} and its corresponding affinity matrix RP threshold ratio Titr > 1; tree depth h;; parameter K >
(8t) (8y)igussmi test point
2: Using initial PCA and k-d tree based partition scheme, decompose the data set X' into subsets CI.... Cgs, where the depth the tree
3: For each subset Ck., calculate its mean (center) my R and its LPP embedding matrix WA St(d, D) based on the affinity matrix S
4: Sort the distances || mall in ascending order || ma)( S S || (a)a)) (k)) (x)) = (1....,2*) 2
5:
Determine which is the first sub-index i of (x) such that | (C-mk)41(a)) > Thhll m (x)
6: Set (x) (x) for 1,2, 2...... I and obtain the embedding matrices W (.., (a)())
Stdd, D) their corresponding subspaces [W (.)) (W)(e)) Gr(d, D), together with the weights w; exp(-K || mjxx)) [| for I,...,
7: Find a center-of-mass W. = WW5(W,, (x)) Wy)(e)i wi,..., wr) (Stiefel case) or [Wa] [WGr (W, (... W (3) W1,.., wy)] (Grassmann case) according to Definition and Theo-
rems and 2
8:
Output: The low-dimensional embedding f(x) = W Rd
However, for a general test point æ E R.,, it might happen that this point lies at approximately the same distances to the centers of each of the several different subsets adjacent (see Figure (b)).
5

---

Under review as a conference paper at ICLR 2021
In this case, we aim interpolate between several subspace indexing models (x)) W (m)). To
do this, we first find the subspace indexes ji (z)), .... (z:) from the first / subsets C) (z)) ... (z()) closest to z, i.c., (z) =
= (r) given the sorted distances || - m2 mentioned above. In practice, the number I = T(x) is depending on x and can be chosen in the following way:
I is the first sub-index of (x) such that || - [ > Tuu || (az(a))
(a)) || where für > 1 is
threshold ratio that can be tuned. We then pick the weights w, exp(-K] -lllll=mm,,te [1]] for some K > and i = 1, 2.... 1. This is indicating that the closer x is to Cj(()). the heavier weights we as- sign to W; (z(zz) in the interpolation process. Given the embedding matrices W (a)) ..., W (x)())
St(d, D) or their corresponding subspaces (s)),,),... ..., [W (r)) E Gr(d, D), together with the weights w1;-., Wy > O, find center-of-mass We
WW'WW, (w)) W jr(ee) W1,--. wy) (Stiefel case) or [Wa] = W (W,, ji))........ ..... W (z)) WI,.... wy)] (Grassmann case) according Def- inition 3 and Theorems and Finally, we map the test point z to the low- now-dimensional embedding f(z) WTx E Rd. Notice that when I 1, the interpolation procedure reduces to projecting using (x) calculated from LPP analysis on the closest subset only. In general, the whole in- terpolation procedure can be regarded as providing regularized version of the piece-wise linear embedding we discussed in Section 2 (also see Figure [ We summarize our interpolation method as the SIM-I Algorithm [
5
EXPERIMENTS
5.1 PCA RECOVERY FOR SIFT DATA SET
SIFT (Scale Invariant Feature Transform, see Lowe (2044) data set a data set that computes for each keypoint real-valued descriptor, based on the content of the surrounding patch in terms of local intensity gradients. Given its remarkable performance, SIFT has been often used as starting point for the creation of other deseriptors. The final SIFT descriptor consists of 128 elements. This means that each data point in SIFT data set has dimension = 128, and we pick the embedding dimension d 16. The original SIFT data set has 10068850 data samples, that form the data set s ft_ stmple.... We randomly collect Reain 200 x 213 elements from these sample points as our target data set X' sift.train efficiency of PCA embedding of the SIFT data set. Let x be a point in sift_sample and let W be a Stiefel matrix in St(16, 128). The projection of onto the 16-dimensional space is then denoted by = Wxx. the Moore-Penrose pseudo-inverse WT. The recovery efficiency can then be quantified by the recovery error ||0 Ø||. where the Fuclidean norm is computed in 122
{II, Trmin {R). We consider the recovery
x. By recovery we meant to consider the point 2 = (WT) where (WT)-
We pick h 13 so that 2 8192. Then we decompose si siftraain into 8192 sub- sets Cl...., C8192 using k-d tree based partition. For each subset Cs. we calculate the mean mn E 12 and we obtain a PCA embedding matrix Wa E St(16, 128). We sort the distances ||x- k- = 1,2, ..., 8192 in ascending order so that || mm,ll < ... | Mkkioz Il. where (ky...., .91922 = {1,..., 8192]. Then we find among the subset means my. & = 1,2, 8192 the first I nearest x, with their indexes denoted by k; k,(x), i = 1, .., I. The number I = [(x) is depending on x and is chosen in the following way: 7 is the first sub-index i of k; such that ||æ m > rim | fi---mo m,, where firr is threshold ratio. We pick Fihr 2.
subset size nhen 500, and we denote the data as sist.test. For each test point x E sift.test, we consider sending it to the nearest subset Ck2 and the corresponding Stiefel matrix is WA, E St(16, 128). We can then consider the recovery point ā (WT)) W x and the benchmark recovery error Error.bm- - - E||-
For test data set, we randomly pick from s wwt.ssammlelssstttttt.
Consider the alternative recovery scheme using our method SIM-I I. We calculate the weights wy = exp(-K [||- - m,, )I for j = 1,.... ..., I and we choose the constant K = 10-8 8 We then find the
Stiefel center-of-mass W. = (W'rt(())) Wkr(s)5 Wi,..., wy) using Theorem I and taking the distance function to be the matrix Frobenius norm d(W1, W2) = W1 - W W2ll F. We consider the
recovery point R. ((W)) TT) -W.)"* and the recovery error Error c = || E.
Over the test set sift test, we find that for about 94.2% test points, Error c < Error bm, which implies that SIM-I improved the efficiency of recovery. The empirical average Error is

---

Under review as a conference paper at ICLR 2021
PGA Reassary Strers
Teardered
Figure 3: Comparison of the PCA Recovery Errors: Blue benchmark case using closest subset PCA recovery, with the error sorted from low to high; Red using SIM-I based on Stiefel center- of-mass and d(W1, W2) = [[ Wallr.
Figure Differences Error_c Error_bm in descending order.
402.089506, and the empirical average Error_bm 454.452314. Figure plots the Error_c and Error.bn bm (vertical axis) as functions of the test sample indexes. The red curve for Error_e and blue curve for Error_bne where we have sorted Error br in ascending order and reordered the test indexes correspondingly. Figure gives the differences Error_e Error bm in descending order. can be apparently seen that Error Error bm < 0 for most of test samples.
5.2 NEAREST-NEIGHBON CLASSIFICATION FOR MNIST AND CIFAR-10
Here we consider a labeled data set data = {(x, v)) = 1,2, .... N} where x; E RD are the inputs and y4 E N are the labels. We randomly select the training set data.train = (2, Y.). 1,2, Remin and the test set dat test = {(a, b,), 1,2, Phes) and we make them disjoint. We first project the training onto a kd PCA-dimensionall subspace via standard PCA.

---

Under review as a conference paper at ICLR 2021
Based on this initial embedding, using kd-tree with height h, divide data.train into 2 clusters Ck. k = 1,2, 2th For each Ck, we find an LPP embedding matrix W' E St(kd_LPP, D) by setting the affinity matrix to be & exp(-lla; z Il²) if z;, 22 E Ck are in the same class and 8i = 0 otherwise. Since we are having a classification problem, we can identify each W by the subspace it spans, i.e., consider [Wa] which is the equivalence class of W5 in Gr(kd_IPP, D)..
As before, we compute R the means my of each cluster C₁- For a test point x E data a_est, sort the distances ||æ mxll. m k 1,2,... ..., 2h in ascending order so that | my S ... S (1,.... 2". Then we find among the cluster means mg. k 1,.... I. The number 1 - (x) is depending on x and is chosen in the following way: is the first sub-index of k, such that ||x - m& > The || my, Il. where Tthr > 1 is threshold ratio. The parameter The can be treated as a hyper-paramett that we can tune here.
|| - 2, ll. where
1,2,... 2h the first I nearest to with their indexes denoted by k; (x),,,
For baseline method, we do nearest-neighhor classification for x on low-dimensional embedding of the cluster Ck and we pick the number of nearest-neighhors to be knn 2 1. Indeed we project and all training data points in Ck2 using Wk,, and perform nearest-neighbor classification on the resulting projection.
For our method SIM-I, we take the union Cke U...U Cky. Recall that each Cj. corresponds an LPP embedding projection matrix Wk. We set the weights w, exp(-Kg K|aæ m& Il²), m,, and we pick 10 We compute a center-of-mass We of the projection matrices WE, with weights i = 1, 2.2,.... ..., I using the Grassmann center-of-mass method, where the distance is taken as the projected Frobenius norm of Grassmann matrices, i.e., d(W1, W2) = =2 2-1/3||W,,?? and ||r is the matrix Frobenius norm. We obtain W. = W ( (k())) ...: W Wk)()); W1, ... Wy) and we project and all training data points in the union Ck, U Ck, using W We then perform neighbo classification for æ on this low-dimensional embedding with the number of nearest-neighhors being equal to knn.
W2 lI
Table I: Nearest-neighhor classification success rates.
data set
tree height
Thr
knn
baseline
STM-I with Grassmann center
MNIST
8
1.2
93.58%
96.55
MNIST
8
1.2
75
87.52%
94.21%
CIFAR-IU
1.05
29. 29.49%
33.04%
CIFAR-I0
1.1
75
30.25%
32.74%
We have been experimenting on 2 different data sets, for both of them we pick kd.PCA = 128, LPP 100: (1) The MNIST data set, with N 70000, Tuain 60000, fuatt 10000 data points and D = 784: (2) The CIFAR-10 data set, with N = 60000, Merain 50000, feest 10000 data points and D = 3072. Table [ shows the results, where the last columns are the nearest- neighbor classification success rates for baseline method, and for SIM-I using Grassmann center- of-mass and the rows are for different experiments. The first columns are for data sets, kd-tree height, threshold value Fihr the number of nearest-neighbors knn, respectively. We slightly tuned Tür to reach best performances. Clearly, SIM-I has its advantage.
REFERENCES
P. N. Belhumeur, J. P. Hespanha, and D. J. Kriegman. Eigenfaces fisherfaces: Recognition using class specific linear projection. IEEE Trans. Patlern Anal. Mach. Intell., 19(7):7117720 1997.
M. Belkin, P. Niyogi, and V. Sindhwani. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. J. Mach. Learn. Res., 1:1-48, 2006.
Bentley, Multidimensional binary search trees used for associative searching. Communications of the ACM, 1809):00-557 1975.
W. Bian and D. Tao. Max-min distance analysis by using sequential SDP relaxation for dimension reduction. IEEE Trans. Pattern Anal. Mach. Intell., 1335)100 2011.
8

---

Under review as a conference paper at ICLR 2021
A. Edleman, T. Arias, and S.T. Smith. The Geometry of Algorithms with Othogonality Constraints. SIAM Journal on Matrix Analysis and Applications, 20(2), 1999.
Y. Fu and T.-S. Huang. Image classification using correlation tensor analysis. IEEE Trans. Image Process., 17(2):226-234, 2008.
N. Guan, D. Tao, Z. Luo, and B. Yuan. Manifold regularized discriminative non-negative matrix factorization with fast gradient descent. IEEE Trans. Image Process, 2011.
J. Ham, D. D. Lee, S. Mika, and B. Schölkopf. A kernel view of the dimensionality reduction of manifolds. presented at the Int. Conf. Mach. Learning. 2004.
X. He and P. Niyogi. Locality Preserving Projections. Advances in Neural Information Processing Systems (NIPS), 2003.
X. He, S. Yan, Y. Hu, P. Niyogi, and H-J. Hong-Jiang Zhang. Face Recognition Using Laplacian- faces. IEEE Transactions on Puttenn Analysis and Machine Intelligence, 27(3), 2005.
I. T. Jolliffe. Principal Component Analysis, 2nd ed. new york. 2002.
T. Kaneko, S. Fiori, and T. Tanaka. Empirical Arithmetic Averaging Over the Compact Stiefel Manifold. IEEE Transactions on Signal Processing, 61(4), 2013.
D. G. Lowe. Distinctive image features from scale-invariant key points. Int. J. Comput. Vis., 60(2): 91-110, 2004.
T. Marrinan, J. R. Beveridge, B. Draper, and M. Kirby. Finding the Subspace Mean or Median to Fit Your Need. CVPR, 2014.
S.T. Roweis and L.K Saulm. Nonlinear dimensionality reduction by Locally Linear Embedding. Science, 290(5500):2323 22222,,, 2000.
L. K. Saul and T. Roweis. Think globally, fit locally: Unsupervised learning of low dimensional manifolds. Mach. Learn, Res., 4:119-155, 2003.
Si, D. Tao, and B. Geng. Bregman divergence-basee regularization for transfer subspace learning. IEEE Trans. Knowl. Data Eng., 22(7):929-99) 942, 2010.
V. Strassen. Gaussian elimination is not optimal. Numer Math., 13:54-356, 1969.
D. Tao, X. Li, X. Wu, and S. J. Maybank. General tensor discriminant analysis and gabor features for gait recognition. IEEE Trans. Pattern Anal. Mach. Intell,, 29(10): 2007.
D. Tao, X. Li, X. Wu, and S. J. Maybank. Geometric mean for subspace selection. IEEE Trans. Pattern Anal. Mach. Intell., (1 274, 2009.
L. Van Der Maaten, E. Postma, and J. Van den Herik. Dimensionality reduction: a comparative review, Tilburg University Technical Report, TICC-TR 2009-005, 2009.
X. Wang, Z. Li, and D. Tao. Subspace Indexing on Grassmann Manifold for Large Scale Multimedia Retrieval. IEEE Trans on Image Processing, 2009):627-2635. 2011. 2011.
T. Zhang, D. Tao, x. Li, and J. Yang. Patch alignment for dimensionality reduction. IEEE Trans. Knowl. Data Eng., 1299)11999-1311 2009.
Zhou, D. Tao, and X. Wu. Manifold elastic net: A unified frame-work for sparse dimension reduction. Data Min. Knowl. Disc., 22(3):340-377 2010.

---

Under review as a conference paper at ICLR 2021
A PROOF OF THEOREM
Let D 2 2 1. Recall St(d, D) stands for the Stiefel manifold, that is, each matrix in St(d, D) is a D by matrix with columns being orthogonally normal. For any matrix M, recall that [ M)] [u[MM"M)]
the Frobenius norm of M.
Theorem (Stiefel center-of-mant with respect to Frobenius norm) We consider the singular
value decomposition of the matrix Σ wy W = O,202, where Or E O(D) and O2 E O(d),
A (dag((),,.. ,.., Aa)axa and x1 2 2 da 2 are the singular values. Then the Stiefel DiD-dixd
center-of-mann with respect the distance given by Frobenius norm d(W,, W2) || W2llF is given by W. = A, where A (diag(1, 1)xxd
O d)xd
Σ wy Willi. and we are looking for Proof. For W E St(d, D) define f(W)
minimizer We of f on (td, D). Write
IW W = (W) - -W,)]
= tr(TW) + mrW?W,,) ) 2tr(WTW,)
= 2p 2p-2t(W"',,
It follows that
f(W) = 2p Σ w
w - 2 2 Wj tr(
1=1
3=1
wh 2p 1=ر
where B = Σ wy Wy. By singular value decomposition, there are D x D orthogonal matrix O
and d orthogonal matrix O2 such that 0, where A (diag(A (e,,(A,,.,,,lll da)axd and
((D-d)xe
\1 ... 2 Aa 2 are the singular values of B. follows that tr(WT B) tr m(AO,WTTO,)
D
Observe that (O,W²O,)* St(d, D). Write OrWTO, (GG))axD Then Σ Hence
for each
tr(WT Σ Ascs S Σ Ai
1=1
with equality holds when O2WTO, (Id, O) where O the d x (D d) matrix with all entries
(diag(1, 1)xxd) is the maximizer of 0(D- being zero. This says that W. 0,AO2 where A (( -)
tr( tr(WTB) The so obtained W. serves the minimizer of S(W) on St D) and is thus the center- of-mass.
B PROOF THEOREM 2
Recall that Gr(d, D) = St(d, (d)O Every point W on St(d, D) will correspond to an equiv- alence class [W] (WOa: Oa E O(d)} which is a point on Gr(d, D). To represent points on Gr(d, D) using matrices, we notice that every point on Gr(d, D) corresponds to unique choice of matrix WWT where W St(d, D). In this way, we can define the projected Frobenius distance
between two classes [W1] and [Wg] in Gr(d, D) as d2 (Wi), (W)) 2-1/2 1/, W,W? ll
10

---

Under review as a conference paper at ICLR 2021
Theorem 2 (Grassmann center-of-mass with respect to projected Frobenius norm) Set Ωz
Wj. We consider the singular value decomposition of the symmetric matrix
E WF QAQ where Q E O(D) and A di.. of 2.... 2 0.
Then the Grassmann center-of-mass with respect to the distance given by projected Frobenius norm
[Wa]) = 2-112 [W,T W2W2 || is the equivalence class [Wa] determined by W. = QA. where A [diag(1 (0,ag(1.....) ,..., 1)xxd
(D-x)
Proof. Set M WWT and M, W, then are looking for minimizer W. St(d, D) of ())>= w [W],, 2-
f(W) = 1j-lwadp...
2
Σ w - M, li. For two D x D matrices M1, M2
we define (M,, M2)) ur(M M2). It is easy to verify that (,) is an inner product and | MM. Thus we write
2f(W) = E wy M - M
Σ wy (M, -2 Σ uz (M, + Σ wj (M,, (MM.MM) M,)
5-l
=
wi 5=1
Σ
(M, - (M, Σ )2MM))
1
Σ j=1
wy (Mdg, M11)
12
Σ (M
- Σ MgMM M - Σ
(g.M)) - プ w/
Σ M
+ + W,
5=1
5=1
1=1
|
Σ Wi
m
M
Σ
M,
Σ
w
Σ Ω2 M₁ 1=1
+ Σ W1
1=1
j=l
So the minimum is taken when
M
Σ My is minimized. Since each W, W is symmetric
matrix, we consider the SVD decomposition
Σ S,W,W? = QQQQ" where Q E ((D) and = J=1
diag .... of 2 of 2 2 of 2 0. Thus suffices to set W. arg min |WWT_ WESt(d,D)
QAQ Since W E St(d, D). we have WWT = PVP" where P is an orthogonal matrix of size D x D and V diag(1. 11 1, ... 1, 0, J........ ..., 0) is an D x D matrix with rank(V)) = d. Moreover, P can be chosen as P (W Z) where Z is an D x (D d) matrix. So
min ()
|WWT QVQ"11
min PEO(D)
||PV QQQQ"
Let the orthgonal matrix O 1 Then we further have
min PeO(m)
-PVP"-QAQ'
min [IQ(vor A)Q OEO(n)
min trQQ(OVTT ~)²QT)
Oc0(m)
min toVo - 2)P. OEO(m)
We then show that min tr(OVOT - 2 is achieved at the orthogonal matrix OEO(n)
Opxx
0
0*
O O(n-p)((mp))
11

---

Under review as a conference paper at ICLR 2021
for any Opxp O(p) and any (nn-))x(n-p) O(n p). Indeed, have tr(OVOT A)2
D
in(OVOT)+ + tr( 2t(AAOVO)); so that we only have to maximize u(AOVV*) Σ ofcs
where OVOT = (Ci)) Let O = (Vig) then it is easy to calculate that = Σ U/j
j=1
D Moreover since Σ o = 1 for all i and Σ bj = 1 for all j. we know that 0 & Ca S
and
D Ea = d. Thus from of 2 2 D we see tr(Aov))) of $ Σ of with
=1
equality if and only if Cü for ... d and cu for d 1,,,.
D. This gives that, for
0 (U1s)DDD we have Σ o 1 when 1...., d and Σ Vij j=d+1
when d 1, ,.... D.
==1
Thus the minimum of min tr(OVOT A)2 is achieved at O" = (Oaxd OεO(n)
((D-ax((-aa) for
any Oaxd E O(d) and any O(D- E O(D d). We can pick Oaxd diag (1, ..., a and since P = QO = (W, Z) where Z is an x (D d) matrix, we get the conclusion of the Theorem about W
12


Reviews:
[{"review_id": "h80zx0arp49", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "### Summary: \n\nThis submission proposed a subspace index method with the additional interpolation (smoothing) step, i.e., SIM-I, first to build a piecewise linear affinity-aware subspace model under a given partition of the data set; next is to interpolate between several local linear subspace models by using the “center of mass” on Grassmann manifolds. \n\nExperimental results on SIFT data, MNIST, and CIFAR-10 are included to support the effectiveness of SIM-I, including some comparisons with baseline methods.  \n\n### Strengths & Originality: \n\nSubspace index plus interpolation is a reasonable idea, and view the interpolation step as some sort of regularization is interesting. \n\nComputation complexity should be one of the advantage of this work, compared with many nonlinear dimension reduction methods need to solve an eigen-decomposition problem for a N-by-N matrix (N as number of samples). However, seems no clear summary of the total complexity for SIM-I in this submission.\n\nSupplementary materiel is provided with the source code in MATLAB, this is good to see. \n\n### Weakness: \n\nThe proposed method share similar framework with \"Subspaces Indexing Model on Grassmann Manifold\" (Ref [1], SIM-GM). We can see the differences by read through both papers, but, seems there is no clear summary for major contributions made against SIM-GM [1] by this submission.   \n\nThe interpolation step in SIM-I, i.e., step 5-8 in Algorithm 1, can be viewed as some sort of \"smoothing\" from a number of subspace. Here the proposed \"center-of-mass\" on Grassmann manifolds is reasonable but not clear why, i,e., will be nice to see discussion or some theoretical analysis here. For example, there is a long history of local space alignment & smoothing works related to dimension reduction & manifold learning, e.g., one of the pointer work is LTSA (Ref. [4]) . \n\nExperiential results on (1) reconstruction from embedding space (2) NN classification are reasonable, but there is no comparison with alternative methods, as only baseline method such as PCA is included in Section 5.1. For example, it will be informative to see the comparison with SIM-GM. \n\nK-d tree is not quite effective in high dimensional space, and this is probably why the 1st step in both the proposed SIM-I and SIG-GM [1] is to use global linear PCA for dimension reduction. This seems fine, still raising some concerns for using PCA as the foundation step for non-linear low-dimensional embedding methods.  \n\n### Reference:\n\nRelated works from non-linear dimension reduction and manifold learning are discussed in this submission. Also, it seems GPCA (Ref. [5]) is related to the concept of subspace index model, so put it here. \n1. Xinchao Wang, Zhu Li, and Dacheng Tao. Subspace Indexing on Grassmann Manifold for Large Scale Multimedia Retrieval. IEEE Trans on Image Processing, 2011\n2. Xiaofei He and Partha Niyogi. Locality Preserving Projections. Advances in Neural Information Processing Systems (NIPS), 2003\n3. Mikhai Belkin and Partha Niyogi. Laplacian Eigenmaps for Dimensionality Reduction and Data Representation, Neural Computation, 2003\n4. Zhengyue Zhang and Hongyuan Zha. Principal Manifolds and Nonlinear Dimension Reduction via Local Tangent Space Alignment. SIAM Journal on Scientific Computing, 2005\n5. Rene Vidal, Yi Ma, and Shankar Sastry. Generalized principal component analysis (GPCA). CVPR 2003", "extra_scores": {}, "extra_text": {}}, {"review_id": "O5OEF2ciRI7", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "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 presents an approach to low-dimensional embedding of data, with an emphasis on image datasets. The algorithm proceeds by first finding several local subspaces that fit the data and then tying these subspaces together using the center of mass calculation on the Stiefel/Grassmann manifold. The method appears to be computationally efficient, since it can be applied to fairly large image datasets, though no formal analysis is given. The main drawback of the paper is that the empirical results compare only to PCA. Several more modern methods for low-dimensional embeddings exist (e.g., T-SNE, UMAP), and it would be appropriate to compare to these. UMAP also allows for the incorporation of labeled data.\n\nAside from this, the paper is quite difficult to follow due to the current organizational structure. A final minor comment is that the figure text is too small to be reasonably legible.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Hwv9Mc5_yxp", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "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": "The authors propose an approach towards computing  globally non-linear, low-dimensional embeddings of high dimensional data. In particular, they consider a sub-space indexing model with interpolation (called SIM-I) which consists of two steps. First, a locally linear model of the data is generated (using kD-trees and PCA) and second, averaging operations on the respective projection matrices are carried out. These are computed based on center of mass computations on Stiefel or Grasammanian manifolds. Anectdotal experimental evidence shows that this approach outperforms simple baseline techniques. \n\nWhile non-linear dimensionality reduction is certainly of considerable practical interest, the work reported here is not yet convincing enough to merit publication. \n\nFirst of all, there is a very rich literature on \"local PCA\" which is not acknowledged and the practical performance of corresponsing earlier methods is not considered / reported. Second of all, the authors list various previously popular techniques such as locally linear embeddings or Laplcaian eigenmaps but again do not consider those in their practical evaluation. As a consequence, it is difficult to assess the merits of the proposed approach over well known baselines. Third of all, while generally interesting, the proposed approach constitutes but a mash-up of existing ideas and can be considered  ad-hoc and a bit outdated. A clear cut motivation or provable guarantees of the proposed method are missing. Finally, the authors critize the fact that previous non-linear methods \"face a serious computational challenge dealing with large-scale data sets due to the complexity\" but do not provide evidence for a superior runtime behavior of their approach. Indeed, the experiments considered here, also only consider data sets of moderate sizes when compared to modern standards.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "37LhDrXC6-I", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "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": "Summary:\nThis paper proposes a subspace indexing model with interpolation (SIM-I) for dimension reduction. To capture the global nonlinearity and the local variation of data, SIM-I split the global space into a collection of local disjoint partitions by a kd-tree style scheme and build a subspace indexing model (e.g., LPP) for each local partition. The main contribution of this paper is to propose an interpolation technique to combine several subspace indexing models to determine a more promising model for low-dimensional embedding. Two experiments on PCA recovery and nearest neighbour classification validate the effectiveness of SIM-I.\n\nPros:\n1. The authors introduce a new way to compute the centre-of-masses of Stiefel and Grassmann with respect to Frobenius norm and projected Frobenius norm with the theoretical analysis.\n2. The idea of using interpolation to get a new model for the query locating at the boundary is interesting. Compared to [1], this idea seems simpler and more effective since it considers all of the close local partitions with a distance threshold.\n3. The paper is clear to read. The authors present their algorithm step-by-step in detail. It is easy to reproduce the algorithms with the guideline. \n\nCons:\n1. The key concern of this paper is the lack of rigorous experiments for the evaluation of SIM-I. More details can be found in minor comments.\n2. The novelty is limited. The LPP model [4][5] and the kd-tree partitioning scheme [1] are not proposed by the authors. To make a clear difference between former work and the current work, I suggest the authors add a preliminary section to review these methods.\n3. The discussion of related work is missing, and the references may be out-of-date since no reference is included in the recent five years.\n4. As the authors claim their method can handle large scale data set, space and time complexity analysis should be included for an illustration. And it will be better to add a table to compare with other SOTA methods. \n\nMinor Comments or Typos:\n1. The benchmark method is too weak, which is only a special case of SIM-I. Despite the authors claimed there exists drawbacks of globally linear subspace model (e.g., PCA, LDA, and LPP) and nonlinear methods such as the kernel methods and manifold learning, they did not choose any of it as a competitor for further validation. This is very limited. At least, the authors should compare [1] with SIM-I since both of them use kd-tree for partitioning and belong to globally nonlinear methods. \n2. The authors claim SIM-I is computationally feasible to large-scale data sets. However, this paper lacks experiments for validation. Compared to SOTA methods, how fast it can be? How large scale data it can handle in a reasonable time?\n3.  Since the authors introduce a new way to compute the centre-of-masses of Stiefel and Grassmann, can the authors add an ablation study to verify the efficiency and effectiveness of this way compared with the methods [2][3] they mentioned in the section of introduction?\n4. Moreover, the study of parameters is necessary. Is the model sensitive to tree depth h? threshold ratio r_{thr}? The parameter K for the weight?\n5. Figure 1 is not clear. And the “LPP” has first appeared without illustration.\n6. Consider the last two lines in Page 2, \n\\lambda_0 < \\lambda_1 \\leq … \\leq \\lambda_{n-1}  -->  \\lambda_0 < \\lambda_1 \\leq … \\leq \\lambda_{d-1}\nw_0, w_1,…, w _{n-1}  -->  w_0, w_1,…, w _{d-1}, and hence consider the first line of Page 3,\nW=[w_1,w_2,…,w_d]  -->  W=[w_0, w_1,…,w_{d-1}]\n7. Consider the first paragraph of Section 3 and the footnote 1 in Page 3, \nw_0,w_1,…,w_{n-1}  -->  w_0, w_1, …, w_{d-1},\n[w_0 w_1 … w_{n-1}]  --> [w_0 w_1 … w_{d-1}]\n8. I suggest the authors add download link or citation for the three data sets used in the experiments, especially for the sift data set they used for the reproductivity purpose. \n9. For the PCA recovery experiments, since the authors measure the recovery error, it would be better to call recovery effectiveness instead of recovery efficiency. \n\nReference\n\n[1] Wang, Xinchao, Zhu Li, and Dacheng Tao. \"Subspaces indexing model on Grassmann manifold for image search.\" IEEE Transactions on Image Processing 20, no. 9 (2011): 2627-2635.\n\n[2] Kaneko, Tetsuya, Simone Fiori, and Toshihisa Tanaka. \"Empirical arithmetic averaging over the compact Stiefel manifold.\" IEEE Transactions on Signal Processing 61, no. 4 (2012): 883-894.\n\n[3] Marrinan, Tim, J. Ross Beveridge, Bruce Draper, Michael Kirby, and Chris Peterson. \"Finding the subspace mean or median to fit your need.\" In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1082-1089. 2014.\n\n[4] He, Xiaofei, and Partha Niyogi. \"Locality preserving projections.\" In Advances in neural information processing systems, pp. 153-160. 2004.\n\n[5] He, Xiaofei, Shuicheng Yan, Yuxiao Hu, Partha Niyogi, and Hong-Jiang Zhang. \"Face recognition using laplacianfaces.\" IEEE transactions on pattern analysis and machine intelligence 27, no. 3 (2005): 328-340.\n\n\n===============================================================================================\n\nUpdate: \nSince the authors did not give any feedback for the reviews, I retain my original decision. Thank you.\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Thanks for your submission to ICLR.

This paper proposes a subspace indexing model for low-dimensional embedding.  The reviewers were all generally in agreement that the paper is not ready for publication.  In particular, they felt that the paper had several key weaknesses:

-Relevant literature is not discussed
-Relevant methods are not evaluated against in the experiments
-Experiments on the whole were limited and not sufficiently convincing
-The novelty of the paper is not very high

Please consider the reviewer comments carefully when preparing a future version of your paper.
Decision: Reject