Improved algorithm and bounds for successive projection
Authors: Jiashun Jin
Tracy Ke
Gabriel Moryoussef
Jiajun Tang
Jingming Wang
Venue: ICLR 2024 poster (2024)
Keywords: Simplex
vertex hunting
successive projection
pseudo-points
pruning
hyper-spectral unmixing
archetypal analysis
network analysis.
Primary area: learning on graphs and other geometries & topologies
TL;DR: A new approach to estimating the vertices of a simplex

Abstract: Consider a $K$-vertex simplex in a $d$-dimensional  space. We measure $n$ points on the simplex, but due to the measurement noise, 
some of the observed points fall outside the simplex. The interest is vertex hunting (i.e.,  estimating the vertices of the simplex).  The successive projection algorithm (SPA)  is one of the most popular approaches to vertex hunting, but it is vulnerable to noise and outliers, and may perform unsatisfactorily.  We propose pseudo-point SPA  (pp-SPA) as a new approach to vertex hunting. The approach contains 
two novel ideas (a projection step and a denoise step) and generates roughly $n$ pseudo-points, which can be fed in to SPA for vertex hunting. For theory, we first derive an improved non-asymptotic bound for the orthodox SPA, and then use the result to derive the bounds for pp-SPA.  Compared with the orthodox SPA,  pp-SPA has a faster rate and more satisfactory numerical performance in a broad setting.  The analysis is quite delicate: the non-asymptotic bound is hard to derive, and we need precise results on the extreme values of (possibly) high-dimensional random vectors.

Published as a conference paper at ICLR 2024
IMPROVED ALGORITHM AND BOUNDS FOR SUCCES- SIVE PROJECTION
Jiashun Jín & Gabriel Moryoussef
Zheng Tracy Ke & Jiajun Tang & Jingming Wang
Department of Statistics Carnegie Mellon University Piusburgh, PA 15213, USA
Department of Statistics
Harvard University Cambridge, MA 02138, USA {zke, jiatuntang, j weingginggwnn hgwang) @fss harvard. edu
(jiashun, gmoryous] @andrew. cmu edu
ABSTRACT
Given a K-vertex simplex in a d-dimensional space, suppose we measure n points on the simplex with noise (hence, some of the observed points fall outside the sim- plex). Vertex hunting is the problem of estimating the K vertices of the simplex. popular vertex hunting algorithm is successive projection algorithm (SPA). How- ever, SPA is observed to perform unsatisfactorily under strong noise or outliers. We propose peeudo-point SPA (pp-SPA). It uses a projection step and denoise step to generate sreudo-points and feed them into SPA for vertex hunting. We derive error bounds for pp-SPA, leveraging on extreme value theory of (possibly) high-dimensional random vectors. The results suggest that pp-SPA has faster rates and better numerical performances than SPA. Our analysis includes an improved non-asymin -on-totmpooiic bound for the original SPA, which is of independent interest.
INTRODUCTION
Fix d 2 and suppose we observe n vectors X1, X2, Xy,..., X, in IR, where
iid N(0,
X; = 46,
(1)
The Gaussian assumption is for technical simplicity and can be relaxed. For an integer 1 < K
<
+ 1, we assume that there is simplex with K vertices Sy on the hyperplane Hg such that each r; falls within the simplex (note that a simplex with K vertices always falls on (K - 1)-dimensional hyperplane of Rd). In other words, let U1, U2 ...; UK E Rd be the vertices of the simplex and let V [01, ........ ug]- We assume that for each 1 < i I there is K K-dimensional weight vector Ty (a weight vector is vector where all entries are non-negative with a unit sum) such that
K
(k) Vm;
(2)
Here, TT's are unknown but are of major interest, and to estimate n. the key is vertex hunting (i.e., estimating the vertices of the simplex Sg). fact, once the vertices are estimated, we can estimate T1, . Tu by the relationship of X, R VT,, Motivated by these, the primary interest of this paper is vertex hunting (VH). The problem may arise in many application areas. (1) Hyper- spectral unmixing: Hyperspectral unmixing (Bioucas- Dias al. 2012) is the problem of separating the pixel spectra from a hyperspectral image into a collection of constituent spectra. X; contains the spectral measurements of pixel d different channels, ui...., UK the constituent spectra (called endmembers), and π; contains the fractional abundances of endmembers at pixel i. It is of great interest to identify the endmembers and estimate the abundances. (2) Archetypal analysis. Archytypal analysis (Cutler & Breiman 1994) is useful tool for representation learning, Take its application in genetics for example (Satija et al. 2015). Each X, the gene expression of cell i, and each is an archetypal expression pattern. Identifying these archetypal expression patterns is useful for inferring a transcriptome-wide map of spatial patterning. (3) Network membership estimation. Let A E "R be the adjacency matrix of an undirected network with nodes and K communities.
Let (Rx, Ex) be the k-th eigenpair of A, and write _ 1 E,,...,6.. Exc. Under certain network

---

Published as a conference paper at ICLR 2024
models (e.g.. Huang et al. 2023); Airoldi al. 2008 Zhang et al. 2020 Ke & Jin (2023): Rubin- Delanchy et al. ()022). ) there is a -evertex simplex in R such that for each S S n, the i-th row of E falls (up to noise corruption) inside the simplex, and vertex hunting is an important step in community analysis. (4) Topic modeling. Let D " be the frequency of word counts of text documents, where p is the dictionary size. If D follows the Hoffman's 's model with K topics, then there is also simplex in the spectral domain (Ke & Wang 2022)), so vertex hunting is useful.
Existing vertex hunting approaches can be roughly divided into two lines: constrained optimizations and stepwise algorithms. In the first line, one proposes an objective function and estimates the ver- tices by solving an optimization problem. The minimum volume transform (MVT) (Craig 1994), archetypal analysis (AA) (Cutler & Breiman 1994, Davadi & Montanari (020), and N-FINDER (Winter, 1999) are approaches of this line. In the second line, uses stepwise algorithm which iteratively identifies one vertex of the simplex at a time. This includes the popular successive projec- tion algorithm (SPA) (Araújo al. 2001). SPA is stepwise greedy algorithm. It does not require an objective function (how to select the objective function may be a bit subjective), is computationally efficient, and has theoretical guarantee. This makes SPA especially interesting.
Our contributions. Our primary interest is to improve SPA. Despite many good properties afore- mentioned, SPA is greedy algorithm, which is vulnerable to noise and outliers, and may be signif- icantly inaccurate. Below, we list two reasons why SPA may underperform. First, typically in the literature (e.g.. Araújo et al. (00T)), one apply the SPA directly the d-dimensional data points X regardless of what (K,d) are. However, since the true vertices u1,..., .K lie on 1)-1---dmensionn hyperplane, if we directly apply SPA X1, X2..... Xn. the resultant hyper- plane formed by the estimated simplex vertices is likely to deviate from the true hyperplane, due to noise corruption. This will cause inefficiency of SPA. Second, since the SPA is a greedy algorithm, it tends to be biased outward bound. When we apply SPA, it is frequently found that most of the estimated vertices fall outside of true simplex (and some of them are faraway from the true simplex).
For illustration, Figure I presents an example, where X1, X2,....... X,, are generated from Model [[] with (n, K, d, or (1000, 3, 2, 1), and r, are uniform samples over T (T is the triangle with vertices (1, 1), (2, 4), and (5, 2)). In this example, the true vertices (large black points) form a triangle (dashed black lines) on 2-dimensional hyperplane. The green and cyan-colored triangles are estimated by SPA and pp- SPA (our main algorithm be introduced; since d equal to K 1,,, the hyperplane projection is skipped), respectively. In this example, the estimated simplex by SPA is significantly biased outward bound, sug- gesting a large room for improvement. Such outward bound bias of SPA is related to the design of the al- gorithm and is frequently observed GGilis 2019).
5
3
sample data true simplex
SPA
PP-SPA
Figure 1: A numerical example (d=2, K=3).
To fix the issues, propose pseudo-point SPA (pp-SPA) as new approach to vertex hunting. It contains two novel ideas as follows. First, since the simplex Sy is on the hyperplane Hy, we first use all data Xj.. Xx, to estimate the hyperplane, and then project all these points to the hyperplane. Second, since SPA is vulnerable to noise and outliers, a reasonable idea is to add denoise step before apply SPA. We propose a pxeudo-poine (pp) approach for denoising, where for each data point, we replace it by a pseudo point, computed as the average of all of its neighbors within a radius of A. Utilizing information in the nearest neighborhood is a known idea in classification (Hastie) et al. 2009), and the well-known k-nearest neighborhood (KNN) algorithm is such an approach. However, KNN or similar ideas were never used as a denoise step for vertex hunting. Compared with KNN, the idea of pseudo- aseudo-point approach is motivated by the underlying geometry and is for different purpose. For these reasons, the idea is new at least to some extent.
We have two theoretical contributions. First, Gillis & Vavasis (0033) derived a non- -snmmptpiiiiic error bound for SPA, but the bound is not always tight. Using a very different proof, we derive sharper non-asympiotic bound for SPA. The improvement is substantial in the following case. Recall that
V ey U..... UK] and let s (V) be the k-th largest singular value of V. The bound in Gillis & Vavasis 2013 is proportional to 1/5 3.x((V (V), while our our bound is proportional to 1/sk-
2

---

Published as a conference paper at ICLR 2024
Since all vertices lie (K -iddennnsin hyperplane, Sk-1 (V) is bounded away from 0, as long as the volume of true simplex is lower bounded. However, Sx (V) may be 0 or nearly O; in this case, the bound in Gillis & Vavasis (2013) is too conservative, but our bound is still valid. Second, we use our new non-asymptotic bound to derive the rate for Pp-SPA, and show that the rate is much faster than the rate of SPA, especially when d >> K. Even when d O(K), the bound we get for Pp-SPA is still sharper than the bound of the original SPA. The main reason is that, for those points far away outside the true simplex, the corresponding pseudo-points we generate are much closer to the true simplex. This greatly reduces the outward bound biases of SPA (see Figure
Related literature. was observed that SPA is susceptible to outliers, motivating several variants of SPA (Gillis & Vavasis 2205;; Mizutani & Tanaka 2018, Gillis 2019). For example, |Bhattabharyaal Kannan (2020); Bakshi al. (2021): Nadisic et al. (2023) modified SPA by incorporating smooth- ing at each iteration. In contrast, our approach involves generating all pseudo points through neigh- borhood averaging before executing all successive projection steps. Additionally, we exploit the fact that the simplex resides in a low-dimensional hyperplane and apply hyperplane projection step prior to the denoising and successive projection steps. Our theoretical results surpass those existing works for several reasons: (a) we propose version of the non-asymptotic bound than the commonly one in Gillis & Vavasis (2013); and (c) we incorporate delicate random matrix and extreme value theory in our analysis.
variant of SPA; (b) our analyses build upon better
2
A NEW VERTEX HUNTING ALGORITHM
The successive projection algorithm (SPA) (Araújo et al. 2001) is popular vertex hunting method. This is an iterative algorithm that estimates one vertex a time. At each iteration, it first projects all points to the orthogonal complement of those previously found vertices and then takes the point with the largest Euclidean norm as the next estimated vertex. See Algorithm [ for a detailed description.
Algorithm The (orthodox) Successive Projection Algorithm (SPA)
Input: X1, X2,...,, .... Xn, and K. Initialize u = O, and = X;, for 1 S i n. For k = 1,2,...........,..,.,.. K,
Update yi to (Ia - un)),; Obtain is = arg max isisn ll Update u = =|Vvill' 11 yi.. Output: G2 Xiz, for 1 S k < K.
.
We propose PP-SPA as an improved version of the (orthodox) SPA, containing two main ideas: a hy- perplane projection step and a pseudo-point denoise step. We now discuss the two steps separately.
Consider the hyperplane projection step first. In our model @ the noiseless points rI,...,> Tn live in (K -)ddimensional hyperplane. However, with noise corruption, the observed data Xi...., X, are not exactly contained in a hyperplane. Our proposal is to first use data to find a 'best-fit' hyper- plane and then project all data points to this hyperplane. Fix d > K 2 Given point zg Rd and projection matrix H E Dd ddxd with rank K - 1, the (K- - -1)- diddennsion hyperplane associated with (zo, H) is
{i E Rd (Ia - Hz xp) 0). For any x E Rdd the Euclidean distance between x and the hyperplane is equal to [I Hx - -ro)]l- Given X1, X2,... Xa, we aim to find a hyperplane to minimize the sum of square distances:
min (S(zo. H)} where S(zo, H)
Σ (I H)(X 10)
Let Z = [2 Zn.. where Z, = X; X and X = 1 ET X,. For each k. let us E g be the ktth left singular vector of Z. Write U = [ui...., ux The next lemma is proved in the appendix.
Lemma 1 S(zo, H) is minimized by xo X and H UU'.
For each 1 < i < n, we first project each X, to X, and then transform X; to Y,, where
(4) These steps reduce noise. To see this, we note that the true simplex lives in a hyperplane with a projection matrix Ho U-Uy It can be shown that U ~ Uo (up rotation) and Y, rī Uge..
X = X + H(,, - X), UU:=U'X;
note that H = UU and Y, E K-1
3

---

Published as a conference paper at ICLR 2024
with r:= = + Ugr, These points rf still live in a simplex (in dimension (K- 1)). Comparing this with the original model X; = rs + e,, we see that Uhe, are iid samples from (0, o² I and 6, are iid samples from N(0, o² Ia). Since K - 1 < d in may applications, the projection may significantly reduce the dimension of the noise variable. Later in Section 4l we see that this implies significant improvement in the convergence rate.
Next, consider the neighborhood denoise step. Fix an A > 0 and an integer N 2 1. Define the A- neighborhood of Y; by (Y, = {x E IR RKK11; || Y:ll I AJ. When there fewer than N points in Ba (including Y, itself), remove Y; for the vertex hunting step next. Otherwise, replace Y, by the average of all points in (Y;) (denoted by Y, The main effect of the denoise effect on the points that are far outside the simplex. For these points, we either delete them for the vertex hunting step (see below), or replace by a point closer to the simplex. This way, we pull all these points "towards" the simplex, and thus reduce the estimation error in the subsequent vertex hunting step.
Finally, we apply the (orthodox) successive projection algorithm (SPA) to YJ, "y...,, "Y, and let 61, ,g....,0 be the estimated vertices. Let V [01, .2..... 0g]. See Algorithm 2
Algorithm 2 Pseudo-Point Successive Projection Algorithm (pp-SPA)
Input: X2,........ ................................ X,, E Idd the number of vertices K, and tuning parameters (N, A). Step 1 (Projection). Obtain X A Σx= X, and Z X-x1,, Let U [ui, [u,,..., uK- contain the first (K- 1) singular vectors of Z. For S i S n, let Y; U'X; E EK
Step 2 (Denoise). Let (Y) {ar E RK-1 || Y; < A} denote the A-neighborhood of Y,
If there are fewer than N points (including Y; itself) in Ba (Y:). delete this point. Otherwise, replace Y, by Y,", which is the average of all points in Ba
Step 3 (VH). Let J C {l....,,7) n) be the set of retained points in Step 2. Apply Algorithm I to
{Y;) to get 0f, ..,, Ox E R Let 0n = (La H X + U E R. k
Output: The estimated vertices Új,-..,ūk: 0K-
The complexity of the orthodox SPA is (ndK)). Regarding the complexity of pp-SPA it applies SPA -)-mm-ddmansionall pseudo-points pseudo points, we need a projection step and a denoise step. The projection step extracts the first (K-1) singular vectors of matrix Z(n x d). Performing the whole SVD decomposition would result in O Omiinn"dd, )d)) time complexity. However, faster approach exists such as the truncated SVD which would decrease this complexity to OnddK). In the denoise step, we need to find the A-neighborhoods for all points Y1, Y2, the KD-Tree. The construction of KD- Tree takes On log n), and the search of neighbors typically
Remark 1:
the complexity is ( To obtain these
Yn. This can be made computationally efficient using
lakes O( (2- x-r) + =m)) where m is the maximum number of points in a neighborhood.
Remark 2: Algorithm 2 has tuning parameters (N, A), where A is the radius of the neighborhood, and N is used prune out points far away from the simplex. For N, we typically take N log(n) in theory and N = 3 in practice. Concerning A, we use a heuristic choice A = max; Y - f/1/5, where Y - Y, It works satisfactorily in simulations.
Remark (P-SPA and D-SPA): We can view Pp-SPA as a generic algorithm, where we may either replace the projection step by a different dimension reduction step, or replace the denoise step by different denoise idea, or both. In particular, it is interesting to consider two special cases: (i) P-SPA, which skips the denoise step and only uses the projection and VH steps; (ii) D-SPA, which skips the projection step and only uses the denoise and VH steps. We analyze these algorithms, together with PP-SPA (see Table [ and Section C of the appendix). In this way, we can better understand the respective improvements of the projection step and the denoise step.
3 AN IMPROVED BOUND FOR SPA
Recall that V = [0i, U2 ......, uK|. whose columns are the K vertices of the true simplex Sp. Let
(1|xk]) l), g(V) = 1 + 80 (V)
(V) = max
8(x) = max (|<+:]])
(5)
1SkSK
$ (V)
15i5n
4

---

Published as a conference paper at ICLR 2024
Lemma 2 GGillis& & Vavasis (2013), orthodox SPA) Consider d-dinensional vectors X1..... .,, Xn. where X, = r; + i n and r2 satisfy model
(2) For each 1 S k S K there is an such that min 2 }}. Apply the orthodox SPA . UK be the output. Up to a permutation of these K vectors.
T = Eg. Suppose maxigign ||=:ll S 1+807=(V)/ (x
*x(V)
X1...., Xn and let 01, B2, B2.....
(V)
floe 1 & [+ 80 ISASK
max
||E/|| == (V) -B. ISiS
max
S (V)
Lemma 2 among the best known results for SPA, but this bound still not satisfying. One issue is that #g (V) depends on the location (i.e., center) of Sp. but how well we can do vertex hunting should not depend on its location. We expect that vertex hunting is difficult only if Sg has a small volume (so the simplex is nearly flat). To see how these insights connect to singular values of V, let 1 K Σ be the center of So, define V = [M] C, ,,...,, UK Gj. and let 8% (V) be the k-th singular value of V. The next lemma is proved in the appendix:
Lemma Volume(So)
VR (K 1J! K= Su (V), SK-I(V) 2 sK-I and sK (V) S K
K-1
Lemma yields several observations. First, as we shift the location of So so that its center gets close (V) = 0. In this case, the bound in Lemma becomes almost useless. Second, the volume of Sg is determined by the first (K - 1) singular values of V, irrelevant to the Kth singular value. Finally, if the volume of So is lower bounded, then we immediately get lower bound for (V). These observations motivate us to modify gVV) in (5) to a new quantity that depends on (V) instead of SK (V); see (6) below.
to the origin, ||ج||||||| z O, and s
Another issue of the bound in Lemma 2 is that ((X) de- pends on the maximum of |||/]|, which is too conserva- tive. Consider a toy example in Figure 2 where So is the dashed triangle, the red stars represent ry's and the black points are X;'s. We observe that X2 and X; are deeply in the interior of So, and they should not affect the performance of SPA. We hope to modify ((X) to a new quantity that does not depend on ||<||| and |cs]]. One idea to modify ((X) to 3 (X, V) max; Dist So), where Dist(-, is the Euclidean distance from a point to the simplex. For any point inside the simplex, this Fu- clidean distance is exactly zero. Hence, for this toy exam- ||ea]. However, we cannot simply replace 3(X) by 8 (XX, V), because [|G] also af- fects the performance of SPA and should not be left out. Note that ri is the only point located the top vertex. When X2 is far away from 71, no matter whether X₁ is inside or outside Sg. SPA still makes large error in estimating this vertex. This inspires us define (X, V)= max; min (i.r ||s When 3t V) is small, it means for each Ug. there exists at least one X, that is close enough to Uj. To this end, let Snew (X, V) max{.3* (X, V), St (x,
Figure 2: A toy example to show the dif- ference between 3(X) and Bnew(X V), where B(X) Fnew [X, V) & (2.5) [|G]]--
ple, (X, V)= S max
max; ||alll and
Under this definition, Snew (X)= < (2.55 ||c/].. which is exactly as hoped.
Inspired by the above discussions, we introduce (for a point E Rd, Dist(2, Sp) is the Euclidean distance from x to So: this distance is zero if E S))
30>(V)
?(V)
Inew (V) 1+
(K) max 8K (xx)((v))
Buew (X) = max{ max (o,, max min ISkSR (
[X - v1ll
(6)
Theorem Consider d-dimensional vectors X1: NI....,X,, where X, = 6, S i S n and r satisfy model 2 For each S. k S K there an i such that ग. = Ck. Suppose for a properly small +x) Apply the orthodxx SPA to universal constant c² > 0, max(1, (1, ox [VV Fnew (X, V) S c 7(V)
2(V)
X1y..., Xn and let 61, 02,..., 0x be the output. Up to permutation of these K vectors, V).
max {1lir -vell S Iuew (V) V)ee
1
5

---

Published as a conference paper at ICLR 2024
Note that Inew (V) (VV) and neew (X, V) I B(X). The non-asymptotic bound in Theorem
is always better than the bound in Lemma 2 We use an example to illustrate that the improvement
can be substantial. Let K d 3. U1 (20, 20, 10), 02 (20, 30, 10), and V33 = (30, 22, 10). We put 71, P2, r3s at each of the three vertices, r4, rs, ra at the mid-point of each edge, and 77 at the center of the simplex (which is 7). We sample e c ..., 67 i.i.d., from the unit sphere in R Let = 0.01e,, for 1 S i 6, and E7 = 0.05e By straightforward calculations, g(V) = 4.3025 x 10 Inew (V) - 6.577 3(X) 0.05, Bnew (X, V) = 0.03. Therefore, the bound in Lemma 2 gives max; | - S 2151.3, while the improved bound in Theorem I gives max; ||0 110--240 1/ < 18.7. A
more complicated version of this example can be found in Section of the supplementary material.
The main reason we can achieve such significant improvement is that our proof idea is completely different from the one in Gillis& & Vavasis (013). The proof in Gillis & Vavasis (2013) is driven by matrix norm inequalities and does not use any geometry. This is why they need to rely on quantities such as 8g (V) and max; ||(/]] to control the norms of various matrices in their analysis. It very difficult to modify their proof to obtain Theorem D as the quantities in (6) are insufficient to provide strong matrix norm inequalities. In contrast, our proof is guided by geometric insights. We construct simplicial neighborhood near each true vertex and show that the estimate úg in each step of SPA must fall into one of these simplicial neighborhoods.
4 THE BOUND FOR PP-SPA AND ITS IMPROVEMENT OVER SPA
We focus on the orthodox SPA in Section In this section, we show that we can further improve the bound significantly if we use PP-SPA for vertex hunting. Recall that we have also introduced P-SPA and D-SPA in Section 2 as simplified versions of PP-SPA. We establish error bounds for P-SPA, D-SPA, and PP-SPA, under the Gaussian noise assumption in (T). A high-level summary Recall that PPSA D-SPA, and pp-SPA all create pseudo-points and then feed them into SPA. Different ways of creating pseudo-points only affect the term Snew (X, V) in the bound in Assuming that Iuew (V) 2 C, the order of (uew (X, V) fully captures the error bound.
in Table []
Theorem I
Table lists the sharp orders of Bnew (X, V) (including the constant).
Table 1: The sharp orders of Snew (X, V) (settings: K 2 3, d satisfies (K--((V) > C, and m satisfies the condition in Theorem 3). P-SPA and D-SPA use the projection only and the denoise only,
respectively. The constant co E (0, 1) comes from m, and the constant 01 > 2 is as in Lemma
< log(n)
= ag log(n)
log(n) < < n²
mp
d 2 n
5p.
SPA
v (n)
Va, log(n)
vd
P-SPA
2 (o)(n)
v (o)))(n)
v 2 log(n)
2 log(n))
D-SPA
20g log(n)
NA
NA
NA
PP-SPA
22g log(n)
/20g log(n)
2cp log(n)
2 (og(n)
The results suggest that Pp-SPA always has strictly better error bound than SPA. When d >> log(n), the improvement is a factor of o (1): ); the larger d, the more improvement. When d = (log(n))). the improvement constant factor that is strictly smaller than 1. In addition, by comparing P-SPA and D-SPA with SPA, we have some interesting observations:
The projection effect. From the first two rows of Table | the error bound of P-SPA is never worse than that of SPA. In many cases, P-SPA leads significant improvement. When d >> log(n), the rate faster by a factor of / Vlog(n). (ngnd/ddd (which a huge improvement for high-dimensional data). When d x log(n), there is still a constant factor of improvement.
The denoise effect. We compare the error bounds for P-SPA and PP-SPA, where the differ- ence is caused by the denoise step. In three out of the four cases of d in Table [ PP-SPA strictly improves P-SPA by constant factor Co < 1.
We note that PP-SPA applics denoise to the projected data in IR 1RK-1 -1, We may also apply denoise to the original data in IRd, which gives D-SPA. By Table when d < Vlog(n), D- SPA improves SPA by constant factor. However, for d >> log (2), we always recommend applying denoise to the projected data. In such cases, the leading term in the extreme value of chi-square (see Lemma 5) is d, the denoise is not effective if applied to original data.

---

Published as a conference paper at ICLR 2024
Table 1 and the above discussions are for general settings. In slightly more restrictive setting (see Theorem 2 below), both projection and denoise can improve the error bounds by a factor of o(1).
We now present the rigorous statements. Owing to space constraint, we only state the error bounds of pp-SPA in the main text. The error bounds of P-SPA and D-SPA can be found in the appendix.
4.1 SOME USEFUL PRELIMINARY RESULTS
, ux] and r; Vmg 1 sii n. Let 0, F, and ß be the empirical means of Recall that V [Mt, ( .......,.......
en uu's, rs's, and n; s. respectively. Introduce V = [V] [1 ...... UK UK-Uj,
0). R 1/2 [ri -...., I'n Tn--f] and G = (1/n) Ei= (T; (T; - R).. Lemma relates singular values of I to those of G and V and proved the appendix (A < B: B
positive semi-definite. Also, (x is the k-th largest (absolute value) eigenvalue of G, (V) is the k-th largest singular value of V; same below).
Lemma 4
The following statements are true: (a) RR' VGV. (b) Ax- VV 3 VGV" 3 (G) VV', and (c) (K-I(G) (V) - 3 (G) (V).
To analyze SPA and pp-SPA, we need precise results on the extreme values of chi-square variables. Lemma iss proved in the appendix.
Lemma Let Mn be the maximum of n iid samples from x2 As -> xo, (a) if < log(n), (n), then Mn/(2 (n)) + 1. (b) if d >> log(n),. then Ma/d - 1, and (c) if d = ag log(n) for constant ag > 0. then Mn/(a) log(n)) + where ai > is unique solution of the equation a1 ag log(a1) (1) = 2 + ag ag (oo) (convergence in three cases convergence in probability).
4.2 REGULARITY CONDITIONS AND MAIN THEOREMS
We assume
K= o(log(n)/ log log(n)). d d(
These are mild conditions. In fact, in practice, the dimension of the true simplex is usually relatively low, so the first condition is mild. Also, when the (lww-dmeensiona) true simplex is embedded in high dimensional space, it is not preferable to directly apply vertex hunting. Instead, one would use tools such PCA to significantly reduce the dimension first and then perform vertex hunting. For this reason, the second condition is also mild. Moreover, recall that G = n > ( (T; + the empirical covariance matrix of the (weight vector) n. and <VV max [1va]]). We assume for some constant C > 0,
Xk-1(G)
AGG)
(V) C.
(8)
The first two items are mild balance condition on n; and the last one is natural condition on V. Finally, in order for the (orthodox) SPA to perform well, we need
o In many applications, vertex hunting used module in the main algorithm. and the data points fed into VH are from previous steps of some algorithm and satisfy a = o(1) (for example, see Jin
-> 0.
al. 2023);
Ke & Wang (2022). Hence, this condition reasonable.
We present the main theorems (which are used to obtain Table T.. In what follows, Theorem 3 is for general setting, and Theorem 2
concerns slightly more restrictive setting. For each setting, we will specify explicitly the theoretiallyy optimal choices of thresholds (t,, e,, in PP-SPA
For < k < K, let J4 {i : r, = } be the set of r; located vertex Up. and let ni [Jg]. for 1 S k < K. Let (()) denote the standard Gamma function. Define
K + 1
m minffi 72...... m
= 0.5(2e²) x 22/(K - []
(10)
2
Note that as K + xe, 62 + 0.5/ Ve. We also introduce
Vd
2x vn
On Vnsik_1(V)
(1 + /mx//daaaadpmm 2 log(n))),
6
mmxx (d, 2 log(n)).
(11)
The following theorem is proved in the appendix.
7

---

Published as a conference paper at ICLR 2024
Theorem 2 Suppose X1, X2....... Xn are generated from model 7 where m 2 cin fir a stant 01 > and conditions
hold. Fix on such that (K log(n) < on < 1, and let
in = vK 1 log(n) below. Ler V [81, 02 uk). where 01, u2,,.................... ................................ , ,, the estimated vertices.
We apply pp-SPA to X2.. X, with (N, A) to be determined
n
In the first case, on < tn- We take N = log(n) and A = cytno in PP-SPA, for a constant C3 I C2. Up to a permutation fi..... ......,ÜK. Üg, maxisAsK ( [0g - 2xl1 S Juew (V)V + Canl + bn-
v l
* In the second case, tn < an & L. We take N = log(n) and A = Jan in pp- SPA. Up to permutation of 01,..., ÜK. maxisksk (1 vv S Jnew (V) (1 (1)) lo))(n).
To interpret Theorem 2 we consider special case where = 0 sk SK-1 1 lower bounded by a constant, and we set on = log (n)) lo)(()). By our assumption 7 d = d= It follows that
On x max dd, v log(n)) Vi. by x V max(d, log(m))/n,, and in x [log(n)) কーं /n 1--(1) K-- We observe that an always dominates bn/o. Whether an dominates fn is determined by d/n. When d/n is properly small so that Oi & tu. using the first case in Theorem 2 we get (ax
s O( Olog log(n)). When d/n is properly large so we get max: (1 u = O ((loogn))) We
C'( V /log(log(n)) + max [d, V /dllo(())//
that On > tn. using the second case in Theorem 2
then combine these two cases and further plug in the constants in Theorem 2
It yields
{
v log log(n)
if d/nnii is properly small;
(1 wxll S Jnew (V) ISKCK
max
112 + (())
if d/n is properly large.
(12)
It is worth comparing the error bound in Theorem 2 with that of the orthodox SPA (where we directly
apply SPA the original data points Xx, Xx)). Recall that ((X) is as defined in (6). Note
that (X) I maxigisn ||aall, where |<a|1 are i.i.d. variables from x²( Combining Lemma
and Theorem 1. we immediately obtain that for the (orthodox) SPA estimates 6:50a 02
up to permutation of these vectors (the constant a₁ is as in Lemma 5 and satisfies 01 > 2):
/mxxfd d, 2 2lo((n)) 01 log(n)
d < log(n) or > log(n);
max 15kSK
(1l
11 S (Vnnew())
d = 0g log(n).
(13)
This bound is tight (e.g., when all r; fall into vertices), We compare log(n), the improvement is factor of /log(n/dd, which is huge when d is large. If = O(og(()) the improvement can still be factor of o(1) sometimes (e.g., in the first case of Theorem 2
13 with Theorem 2 If d >>>>>>>>>>>>>
Theorem 2 assumes that there are a constant fraction of ry falling at each vertex. This can be greatly relaxed. The following theorem is proved in the appendix.
Theorem 3 Fix 0 < co < and a sufficiently small constant O < 8 co. Suppose X1, NT.X2..... Xn are generated from model ( where m 2 nl-cot5 and conditions 77-19 hold. Let tú
VK- 1 ( - We apply PP-SPA to X1, X2...., with (N, A) to be determined below. Let V [01, 82 . úK]] where é,, 02,..., êg are the estimated vertices.
In the first case, an < the We take N = -log(n) and A = estro in pp-SPA, for a constant cs I c Up to a permutation of o1,.... 0K, maxigkek {llo - vall - - dgeew (V)) loggg( + Canl + bn.
In the second case, On >> tr, Suppose an = o(). We take N = log(n) and A = an in PP-SPA Up to a permutation of 01,...,, maxigask (1 - vell S oynew (V) (2(o)))))
Comparing Theorem 3 with Theorem 2, the difference is in the first case, where the o(1) factor of 8, is replaced by a constant factor of co < 1. Similarly as in [2 we obtain
{
20n log (n)
if d/n is properly small; if n is properly large.
max I {116p1 - 2R } < Juew (V)
(14)
/ [2 + o o(1) log(n)
8

---

Published as a conference paper at ICLR 2024
20
SPA
PSPA
AP-SRA Sob
www.
5.
Mecorotrution
3
30
20
30
49
0.5
1.0
2.0
500
1000
1500
2030
Dimonsion (4)
Noise (sigma)
Samp size
Figure 3: Performances SPA, P-SPA, D-SPA, and pp-SPA in Experiment 1-3.
In this relaxed setting, we also compare Theorem 3 with 13 (a) When >> log(n), the improve- ment is factor of /log(n)/d. (b) When d = (log(n)), the improvement is at the constant order. It interesting further compare these "constants", Note that Inew (Vee (V) the same for all meth- ods. It suffices to compare the constants in the bound for (new((V] In Case (b), the error bound of Pp-SPA smaller than that of SPA by factor of co (0, For the practical purpose, even the improvement of a constant factor can have huge impact, especially when the data contain strong noise and potential outliers. Our simulations in Section SanioonSffurttta further confirm this point.
NUMERICAL STUDY
We compare SPA, Pp-SPA, and two simplified versions P-SPA and D-SPA (for illustration). We also compared these approaches with robust-SPA (Gillis) 2019) from bit t.. wwwlyyyoouussst. (with de- fault tuning parameters). For pp-SPA and D-SPA, we need to specifyy tuning parameters (N, A). We the heuristic choice in Remark 2. Fix K 3 and three points (y1, 12, ys in R Given (n, d, a), we first draw (n (2-30) points uniformly from the 2-dimensional simplex whose vertices are y1 3/2 Va- and then put 10 points on each vertex of this simplex. Denote these points by wi, W2. .... W, E R Next, we fix a matrix A E Rdx2, whose top 2 x 2 block is equal to Ia and the remaining en- tries
Let ri Aw;, for all i. Finally, We consider three experiments. In Experiment 1, we fix (n, a) = (1000, 1) and let d range in {1, (1.2...., 49, 50). In Experiment 2, we fix (n, In Experiment 3, we fix (d. vertex hunting error max, f [ r (subject to a permutation of 01. ..... 0g). For each set of parameters, we report the average error over 20 repetitions. The results are in Figure 3 They are consistent with our theoretical insights: The performances of P-SPA and D-SPA are both better than that of SPA, and the performance of PP-SPA is better than those of P-SPA and D-SPA. It suggests that both the projection and denoise steps are effective in reducing noise, and it is beneficial to com- bine them. When d < 10, SP-SPA, P-SPA and D-SPA all outperform robust-SPA: when > 10, both PP-SPA and P-SPA outperform robust-SPA, and D-SPA (the simplified version without hyper- plain projection) underperforms robust-SPA. The code reproduce these experiments is available wtttesss//gkaabb.cc////aaaeeea/a
generate X1, X2,..., Xx from model [
(1000, 4) and let range in {0.2, 0.3. ... 2). (4, 1) and let n range in {500, 600. 1500}. We evaluate the
ing
DISCUSSION
Vertex hunting is a fundamental problem found in many applications. The Successive Projection al- gorithm (SPA) is popular approach, but may behave unsatisfactorily in many settings. We propose Pp-SPA as new approach to vertex hunting. Compared to SPA, the new algorithm provides much improved theoretical bounds and encouraging improvements We also provide sharper non-asymptotic bound for the orthodox SPA. For technical simplicity, our model assumes Gaussian noise, but our results are readily extendable to subGaussian noise. Also, our non-asymptotic bounds do not require any distributional assumption, and are directly applicable to different settings. For future work, we note that an improved bound on vertex hunting frequently implies improved bounds for methods that contains veriex hunting as important step, such as Hixed-SCORE for network analysis (Jin et al. 2023 Bhattacharya et al.) 2023), Topic-SCORE for text analysis (Ke & Wang, 2022), and state compression of Markov processes (Zhang & Wang, 2019). where vertex hunting plays key role. Our algorithm and bounds may also be useful for related problems such estimation of convex density support (Brunel 2016).
wide variety of numerical study.

---

Published as a conference paper at ICLR 2024
REFERENCES
Edoardo M. Airoldi, David M. Blei, Stephen E. Fienberg, and Eric P. Xing. Mixed membership stochastic blockmodels. Mach. Learn. Res., 9:1981 2014,, 2008
M. C. U. Araújo, I. C. Saldanha, and R. K. H. Galvao et al. The successive projections algorithm for variable selection in spectroscopic multicomponent analysis. Chemom. Intell. Lab. Syst., 57 (2):65-73, 2001.
Ainesh Bakshi, Chiranjib Bhattacharyya, Ravi Kannan, David Woodruff, and Samson Zhou. Learning a latent simplex in input-sparsity time. Proceedings of the International Conference on Learning Representations (ICLR), pp. 1-11, 2021.
Sohom Bhattacharya, Jianqing Fan, and Jikai Hou. Inferences on mixing probabilities and ranking in mixed meneeddhmmbbrshipp models. arXiv:2308. 14988, 2023.
Chiranjib Bhattacharyya and Ravindran Kannan. Finding a latent k-simplex in o*(k nnz (data)) time via subset smoothing. In Proceedings of the Fourleenth Annual ACM-SIAM Symposium Discrete Algorithms, pp. 122-140. SIAM, 2020.
José M Bioucas-Dias, Antonio Plaza, Nicolas Dobigeon, Mario Parente, Qian Du, Paul Gader, and Jocelyn Chamussot. Hyperspectral unmixing overview: Geometrical, statistical, and sparse regression-basees approaches. IEEE journal of selected topics in applied earth observations and remote sensing, 5(2):354-379, 2012.
Victor- Secto--mmmnuul Brunel. Adaptive estimation convex and polytopal density support. Probability Theory and Related Fields, (44(1-))11-16, 2016.
Maurice Craig. Minimum-volune transforms for remotely sensed data. IEEE Transactions on Geoscience and Remote Sensing, 32(3):542-555 1994.
Adele Cutler and Leo Breiman. Archetypal analysis. Technometrics, 36(4):338-344 1994.
Nicolas Gillis. Successive projection algorithm robust to outliers. In 2019 IEEE 8th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), pp. 331- 335. IEEE, 2019.
Nicolas Gillis and Stephen A Vavasis. Fast and robust recursive algorithmsfor separable nonnegative matrix factorization. IEEE transactions on pattern analysis and machine intelligence, 36(4):698- 714, 2013.
Nicolas Gillis and Stephen Vavasis. Semidefinite programming based preconditioning for more robust near-separable nonnegative matrix factorization. SIAM Journal on Optimization, 25(1): 677-698, 2015.
Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The elements of statistical learning. Springer, 2nd edition, 2009.
Sihan Huang, Jiajin Sun, and Yang Feng. Peabm: munity detection. Journal of the American Statistical Association, (just-accepted): 2023.
Pairwise covariates-adjusted block model for com-
Hamid Javadi and Andrea Montanari. Nonnegative matrix factorization via archetypal analysis.
Journal of the American Statistical Association, 115 115(530):896-077,0 2020.
Jiashun Jin, Zheng Tracy Ke, and Shengming Luo. Mixed membership estimation for social net- works. J. Econom., https://doi.org// 1000
2023.
Zheng Tracy and Jiashun Jin. The SCORE normalization, especillyy for heterogeneous network and text data. Stat, 12 320J/4/4...ttt////o..//////00012 2023.
Zheng Tracy Ke and Minzhe Wang. Using SVD for topic modeling. Journal of the American Statistical Association,
2022.
10

---

Published as a conference paper at ICLR 2024
Tomohiko Mizutani and Mirai Tanaka. Efficient preconditioning for noisy separable nonnegative matrix factorization problems by successive projection based low-rank approximations. Machine Learning. 107:643-677 673, 2018.
Nicolas Nadisic, Nicolas Gillis, and Christophe Kervazo. Smoothed separable nonnegative matrix factorization. Linear Algebra and its Applications, 676:174 174-144, 2023.
Patrick Rubin-Delanchy, Joshua Cape, Minh Tang, and Carey E Priebe. A statistical interpretation of spectral embedding: The generalised random dot product graph. Journal of the Royal Statistical Suciety Series B: Statistical Methodology, 84(4):1446-1477 2022.
Rahul Satija, Jeffrey A Farrell, David Gennert, Alexander F Schier, and Aviv Regev. Spatial recon- struction of single-cell gene expression data. Nature biotechnology. 33(5):495- 502, 2015.
Michael E Winter. N-FINDR: An algorithm for fast autonomous spectral end-member determination in hyperspectral data. In SPIE's International Symposium on Optical Science, Engineering, and Instrumentation, pp. 266-275, 1999.
Anru Zhang and Mengdi Wang. Spectral state compression of markov processes. IEEE transactions on information theory, 6665)):202-3231, 2019.
Yuan Zhang, Elizaveta Levina, and Ji Zhu. Detecting overlapping communities networks using spectral methods. SIAM J. Math. Data Sci., 2(2):265-28) 2020.


Reviews:
[{"review_id": "6WFo6l4Kps", "reviewer": "Reviewer_KsqF", "summary": "Fix a dimension $d$, and let $r_1, ..., r_n$ be $n$ vectors that lie on the same $K$ dimension simplex with extremal vertices $v_1, ..., v_K$, where $1\\leq K \\leq d+1$. The authors consider the (practical) problem of having noisy realisations $X_i = r_i + \\epsilon_i$ where $\\epsilon_i$ is some Gaussian noise.  This Gaussian noise assumption can be relaxed; the authors don't explain how, but looking at the proofs, I don't doubt that claim. \n\nWe are interested in writing each $r_i$ as a linear combination of $v_1, .., v_K$. This would ofcourse be trivial if we have access to $r_1, ..., r_n$, because we can find the extremal vertices $v_1, ..., v_K$, and then the problem amounts to solving a linear system of equation. Unfortunately, we only have access to the noisy $X_1, ..., X_n$, so finding the extremal vertices is not possible. Intuitively, we want to solve a linear system \"approximately\". \n\nThe existing algorithm for this problem is called SPA, or the successive projection algorithm. The algorithm starts with an empty extremal set K. at iteration $k$, given the current residual space, the algorithm projects all the points to the compliment of the previous residual space, then adds the vertex that maximizes the Euclidean norm greedily to the extremal set. \n\nThe authors claim that the current SPA algorithm has an issue of being biased outward bound. To counter this, they do a few contributions (in the paper):\n\n1) They introduce a new practical variant of the classical SPA algorithm, pp-SPA. This algorithm has two steps. First, it uses the fact that the points $r_1, ..., r_n$ lie on the same $K-1$ dimensional hyperplane $H$. So they project the noisy readings $X_1, ..., X_n$ onto the plane that minimizes the least square error with respect to the noisy realizations. Next, it \"averages\" each point using KNN to create more robustness and crease \"pseudo-points\". This is where the pp term in the algorithm name comes from. The algorithm seems to do better in practice.  \n\n2) The authors tighten the non-asymptotic bound for the classical SPA result from depending on $O(1/s_k^2)$ to $O(1/s_{k-1}^2)$ where $s_k$ is the $k$-th largest Eigen value of the extremal vertices $v_1, ..., v_K$. They also a similar bound for pp-SPA.", "questions": "My questions are listed in the Weakness section if any.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I like the pp-SPA algorithm a lot, and it feels like a very natural idea. It's an added bonus that the authors were able to get tighter theoretical bounds, which while admittedly are too complicated sometimes to compare fairly to classical SPA, are clearly tighter. It's not clear to me at all when the bounds for pp-SPA beat the bounds for classical SPA, simply because of how complicated the bounds are. \n\nI was able to follow most proofs as a non-expert, so the **proofs** are well written (the actual writing is a whole other story, see below). The analysis for the SPA algorithm is a bit gross; I spent several days following the proof, it felt like a nightmare. I don't claim I understand all steps there, but otherwise the proof looked kosher to me. Perhaps spend some time on simplifying it, but that's easier said than done. \n\nOverall, I think that together with the new practical and nice pp-SPA algorithm that clearly does better in practice from the experiments, and the new non trivial theory to back it up, the paper is above acceptance threshold.", "weaknesses": "1) For some reason, the authors do not compare pp-SPA with any robust SPA. I found many results in the literature on robust SPA, so it seems bizare it is not included in the experimental section here. Please try to include at least one robust variant of SPA/similar algorithm in the experimental section. \n\n2) The writing can be dramatically improved. See below minor points, but if this is accepted, please spent a few iterations on improving the writing. It's extremely terse at time. \n\n3) You reprove several \"elementary\" results that I am almost certain must exist in the literature. Please don't do this, and spend some time to search for the result you need and cite appropriately. You don't need to prove everything from first principles! For example, Lemma 1 can be given as a HW question for an honors linear algebra class.... \n\n4) The statements of Theorem 2/3 are an absolute nightmare, and I struggle to see how anyone would cite/use your result without a ton of heavy lifting in understanding your proofs. \n\n----------------------------------------------------------------\nMinor comments: \n\nPage 2 \"and so on and so forth\" Akward, please change. \n\n\"However, since the simplex lies on a\nhyperplane of (K − 1)-dimension, it is inefficient if we directly apply SPA to X1, X2, . . . , Xn\"  This needs more explanation\n\n\"The results suggest that the SPA may be significantly\nbiased outward bound, and there is a large room for improvement\" No! This result suggests that SPA is biased outward bound for this example! Why would this suggest it is a general phenomenon?! Actually, how do you know your own algorithm doesn't display this phenomenon for other examples?\n\n\n\"he triangles in black, green, and cyan are the true simplex (which is a triangle since (K −1) = 2), the simplex estimated by SPA, and the simplex estimated by D-SPA (D- SPA is a special case of pp-SPA where the projection step is skipped and pp-SPA is a new approach to be introduced; see below), respectively.\" Rewrite this sentence! \n\n\nPage 2 \"Roughly say\" --> Informally, ...\n\n\n\"successive projection algorithm (SPA) (Ara´ujo et al., 2001)\" The \"term\" successive projection algorithm might've originated from the Araujo paper from 2001, but I can't believe that this algorithm was first discovered in 2001. To start off, it has similarities to the Frank-Wolfe minimum norm point algorithm, and several polyhedral algorithms. Can you please verify where the original **idea** was derived, to keep historical accuracy? \n\nLemma 1 (Best-fit hyperplane) There is no way this result isn't known. I can literally prove this result without even looking at your Appendix with Lagrangian multipliers and straightforward linear algebra identities. Please search for where this result was first proved, and don't reprove old things unless your proof is starkly different (which is absolutely not the case here)", "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": "", "extra_scores": {}}, {"review_id": "euoDgP5B7l", "reviewer": "Reviewer_wP9r", "summary": "The paper describes an algorithm for the vertex hunting problem. In this problem, one is given a set of points from a given simplex that underwent some noise. The goal is to identify the simplex, i.e., to find its vertices. A previously known algorithm for this problem is SPA, which repeatedly chooses the largest sampled point as a vertex, then projects the remaining points to its orthogonal space. \n\nThis paper proposes a different algorithm, which is more appropriate for handling noise. \nThe algorithm first identifies a subspace in which the simplex might exist, and projects the points to this subspace. \nThen, a denoising step eliminates \"outliers\". \nFinally, standard SPA is applied to the remaining points. \n\nThe paper evaluates this method both theoretically and experimentally.\nOn the theoretical side, the paper introduces an improved analysis for classic SPA, and shows further improvement is achieved by their method (pp-SPA). \nHere, performance is measured in terms of the maximum distance between an estimated vertex and a matched actual vertex (for the best possible matching). \nOn the experimental side, the paper compares pp-SPA to standard SPA, as well as variants that use only some of the steps in pp-SPA (only projection and only denoising), and shows that pp-SPA achieves the best reconstruction error.", "questions": "none", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper gives ample motivating examples for which the problem is relevant. The paper makes attempts to motivate the given bounds. The algorithm itself seems intuitive.", "weaknesses": "The bounds given in the paper, e.g. Theorem 2, are very complex; they contain multiple terms and are subject to many conditions. It is hard to understand whether those conditions are restrictive, or whether the bounds are significant. \nI think the presentation of the problem could be expanded upon.", "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": "", "extra_scores": {}}, {"review_id": "TusOHeQwDb", "reviewer": "Reviewer_xzLC", "summary": "The *main problem* tacked by the reviewed paper is the **vertex hunting**, i.e.:  the estimation of $K$ vertices defining a simplex in $\\mathbb{R}^d$ given $n$ sampled points belonging to the simplex perturbed by iid zero-centered Gaussian noise with variance $\\sigma$.  The discussed problem is essential in many problems in ML/data analysis, e.g.: hypespectral unmixing, archetypal analaysis, and community detection in networks, topic modelling in NLP.\n\nThe *main innovation* is the *pseudo-point successive projection algorithm* (pp-SPA), which is the improvement of the well studied SPA method that is simple and effective. The proposed innovation consists of two parts: (i) in applying PCA to estimate the K-1 dimensional linear subspace defining the simplex (ii) to perform K-nearest neighbours averaging on the points. Both of these actions are meant to help with denoising of the given sample points and to help with correct estimation in high-noise settings.\n\nThe *main contribution* of the paper, apart from proposing the two denoise methods to SPA, comes from the supplied theoretical analysis. The authors show an upper bound on the error that depends on $K-1$th singular value of the matrix formed by the concatenated sampled points $X = [x_1,x_2, \\ldots x_n]$. This is a contrast to the existing bound that includes $K$th singular value in the work of (Gillis & Vavasis, 2013) that proved the first recovery bounds for the basic SPA algorithm. The authors claim that this is a significant difference, especially since the sampled points are guaranteed to lie in a $K-1$ lin. subspace, thus the $K-1$th singular value is bounded away from zero, while the $K$th singular value is not.\n\nThe *numerical comparisons* with the basic SPA and the related ablation studies are provided in the text and show benefits of the proposed methods in the specific cases of small $d=2$ and $K=3$, however, other situations of interest when the denoise function can be more pronounced, e.g., when d >> K is not showed. \n\nThe proofs seem to be technically involved, but it is difficult for me to check the soudness of the results as I am not an expert in the area.", "questions": "* How does the theory differ in the case of 3-simplex in 2D? Is there a difference in the $K$ vs $K-1$ singular value?\n* How does the algorithm perform for higher dimensional problems?\n* In the second sentence on the first page you state that Gaussian assumption can be relaxed. Can the theory by applied also when the errors are not Gaussian?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I believe, the paper brings potentially several strong contributions:\n1) The authors propose algorithm seems to practically make a lot of sense\n2) The theoretical results are novel and non-trivial. The authors exploit the specific Gaussianity of the noise to be able to derive these bounds\n3) The experiments are limited, but they support the statements of the paper", "weaknesses": "There are some considerable difficulties I have with the paper:\n1) The writing and the structure of the text should be improved. For example:\n* It is not clear to me what the illustration in Figure 1 shows? Is it obvious that one of these is better and what does ``idea simplex'' denote?\n* At times a statement is given without citation, e.g. you say in \"Our contributions.\", pg 2  that: \"since the SPA is greedy algorithm, it tends to be biased outward bound.\", but it is not clear where this can be seen.\n* It is very difficult to follow the motivation of Theorem 1, and how it shows that the previous results of (Gillis & Vavasis, 2013) is non-satisfactory. It is very difficult to see the comparison with the bound in (5) for $\\beta_{new}$. \n2) The numerical experiments are done only for very small sizes. I am not sure how big is the effect of denoising using low-dimensional PCA projection in this case.", "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": "", "extra_scores": {}}, {"review_id": "LMbbbudqtX", "reviewer": "Reviewer_WFSc", "summary": "This paper consider recovering the k-vertex simplex. Exploiting the idea of K-nearest neighbor, this paper improves the SPA algorithm (Araujo et al. 2001) and propose pp-SPA (shown in Algorithm 2).  Compared with the analysis in Gilis and Vavasis, this paper obtain some improvements as in Theorem 2 and Theorem 3.", "questions": "1. Will more samples contribute to the reconstruction performance? My intuition is that the reconstruction performance will improve with more observations, that is, the reconstruction error will decrease with an increasing sample $n$. However, the relation between sample number $n$ and the reconstruction error is largely missing. \n\n2. How is the algorithm compared with the matrix completion solution? To be more specific, we can stack the observations and obtain the sensing relation $X = V\\Pi + N$, where observation $X_i$ is the $i$th column of matrix $X$, and $N$ is the sensing noise. Easily, we can verify that $V\\Pi$ is a matrix with rank at most $K$. Hence, we can view matrix $X$ as a linear combination of low-rank matrix and noise matrix. Then, we exploit the research on low-rank matrix reconstruction and solve the problem. \n\n3. In comparing the performance between Theorem 1 over Lemma 4, what if we have $\\gamma(V) \\ll s_{K-1}(V)$? In such case, lemma 4 may be more tight then Theorem 1.", "limitations": "", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This paper proposes a novel algorithm to reconstruct the k-vertices and analyze its performance. The analysis seems to be solid. Compared with the prior work (Gillis and Vavasis), improvements are obtained under certain scenarios.", "weaknesses": "+ This paper seems to be a incremental work based on Gillis & Vavasis (published in 2013).  \n\n+ There is only limited numerical experiments to validate the peformance of the proposed algorithms. (c.f. Figure 2).", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)