Successive Projection Algorithm Robust to Outliers

Nicolas Gillis

REVIEW 2 major objections 4 minor 12 references

Successive Projection Algorithm Robust to Outliers

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proposes Robust SPA (RSPA), which makes the successive projection algorithm select columns by reconstruction error so that outliers no longer hijack the pure-pixel search, while keeping SPA's speed and low-noise guarantees.

desk verdict RSPA is a genuinely new heuristic with strong empirical promise, but the paper's central provable-robustness claim is unsupported and Algorithm 3 misapplies Lemma 1. read the letter →

arxiv 1908.04109 v1 pith:NK5XVW5C submitted 2019-08-12 eess.SP cs.LGcs.NAeess.IVmath.NAstat.ML

Nicolas Gillis This is my paper · ORCID

classification eess.SPcs.LGcs.NAeess.IVmath.NAstat.ML

keywords nonnegativematrixfactorizationseparableNMFsuccessiveprojectionalgorithmpure-pixelsearchhyperspectralunmixingoutlierrobustnessgreedycolumnselectionreconstructionerror

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Separable nonnegative matrix factorization assumes every data column is a convex combination of a few 'pure' columns, and the successive projection algorithm (SPA) extracts those columns greedily. SPA is fast and provably robust to noise, but a single outlier with large norm can be selected instead of a true column, and SPA ignores how well the chosen columns fit the data. This paper introduces Robust SPA (RSPA), which changes only the selection step: it generates several diversified candidate columns, projects the residual onto each, and keeps the candidate whose residual has the smallest $p$-norm of column norms. RSPA inherits SPA's computational structure ($O(mnrd)$ instead of $O(mnr)$) and its low-noise robustness, while avoiding outliers in synthetic tests and on the San Diego hyperspectral image, where it cuts the relative fitting error from about 12.6% to 6.0%.

What carries the argument

The load-bearing object is Algorithm 3's diversification loop. Starting from the residual $R$, it computes $d$ candidate indices $k(i)=\arg\max_j\|Y(:,j)\|_2$ for $Y$ initialized as $R$, forms $u_i=R(:,k(i))/\|R(:,k(i))\|_2$, projects the residual to $R_i=(I-u_i u_i^T)R$, records $e(i)=\sum_k\|R_i(:,k)\|_2^p$, finds the largest column $k'(i)$ of $R_i$, and updates $Y\leftarrow(I-\alpha_i u_i u_i^T)Y$ with $\alpha_i$ from Lemma 1 chosen so that $\|(I-\alpha_i u_i u_i^T)y\|_2^2=\beta\|(I-\alpha_i u_i u_i^T)x\|_2^2$ for $x=Y(:,k(i))$ and $y=Y(:,k'(i))$. The final pick is $k^*=\arg\min_i e(i)$. Lemma 1's explicit formula for $\alpha_i$ is what makes the diversification step cheap, and the residual-error criterion is what makes the selection fit the data and reject outliers.

What would settle it

Run Algorithm 3 on a matrix where $R$ and $Y$ differ at iteration $i\ge2$ (for example, any matrix with more than one outlier and $d\ge2$), compute $\alpha_i$ from formula (1) using $x=Y(:,k(i))$, $y=Y(:,k'(i))$, and $u_i=R(:,k(i))/\|R(:,k(i))\|_2$, then check whether $\|(I-\alpha_i u_i u_i^T)y\|_2^2$ equals $\beta\|(I-\alpha_i u_i u_i^T)x\|_2^2$; if equality fails, the diversification guarantee that each $f_{i+1}$ cannot reselect $k(i)$ collapses, and RSPA's outlier-avoidance is unsupported.

Watch

Extended reading notes

Core claim

The paper's central claim is that SPA's selection step can be made outlier-robust without sacrificing provable low-noise behavior by replacing the single maximizer of $f(R(:,k))$ with a set of $d$ candidates, each maximizing a quadratic $f_i(x)=\|P_i\cdots P_1 x\|_2^2$, and choosing the candidate that minimizes $e(i)=\sum_k\|R_i(:,k)\|_2^p$. The matrices $P_{i+1}=I-\alpha_i u_i u_i^T$ are rank-one updates with $u_i=R(:,k(i))/\|R(:,k(i))\|_2$, and $\alpha_i\in(0,1)$ is chosen by Lemma 1 so that the next function $f_{i+1}$ has value $\beta$ times larger on the current residual's largest column than on the previously selected candidate, forcing the candidates to spread out. Each $f_i$ is strongly convex and satisfies the same assumption used for SPA's noise robustness, and for $d=1$ RSPA reduces exactly to SPA. On synthetic matrices with 10 outliers, RSPA(40,1,4) identifies more than 99% of the true columns once $m\ge25$, while SPA identifies almost none; on the San Diego hyperspectral image, RSPA extracts no outliers and lowers the relative error from 12.62% to 6.03%.

Load-bearing premise

The argument assumes that the formula for the diversification parameter $\alpha_i$ stays valid when the vector $x$ in the formula comes from the updated matrix $Y$ rather than from the residual $R$; after the first iteration $Y$ and $R$ are no longer the same, so this validity is not established.

Editorial extensions

If this is right

RSPA gives SPA users a drop-in replacement: only the selection step changes, and with $d=1$ it is exactly SPA, so low-noise calibration carries over.
With $d$ at least the number of outliers, RSPA can serve as an outlier-robust pure-pixel search without separate outlier pre- or post-processing; the paper's experiments support $d\ge40$, $p=1$, $\beta=4$ as a working configuration.
On the San Diego image, RSPA(20,1,4) reduces the relative approximation error from 12.62% to 6.03% and extracts none of the five outliers SPA selects, so the fitting-quality improvement is visible on real data.
The price is a factor $O(d)$ in runtime: RSPA runs in $O(mnrd)$ and measured about $2d$ to $3d$ times slower than SPA, which is still practical for offline hyperspectral unmixing.
The paper's own conclusion notes that the same residual-based selection idea could be applied to other greedy separable-NMF algorithms such as VCA and SNPA.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Beyond the paper: the outlier-robustness evidence depends on outliers being poorly correlated with the data; when outliers sit inside or close to the convex hull of the true columns, as in the Urban image, RSPA's advantage shrinks, which suggests a testable boundary for the method.
Beyond the paper: the tuning pattern (pick $d$ proportional to the expected number of outliers, $p=1$, $\beta=4$) hints at a practical rule of thumb, but the paper gives no theory for how these parameters should scale with noise or outlier norms.
Beyond the paper: a rigorous theorem bounding RSPA's error as a function of noise level and outlier count would require quantifying the residual gap between an outlier and a true column; the paper announces this analysis as future work, not part of the current result.
Beyond the paper: the strategy of generating a diversified candidate set before choosing by fitting error could be reused in other subset-selection problems beyond NMF, such as column subset selection or active-set methods.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague —

Short take: RSPA is a genuinely new algorithmic idea — diversify SPA's selection step with a set of quadratics and pick the candidate that minimizes the residual — and the experiments show it can beat SPA noticeably on synthetic and real hyperspectral data. The code is freely posted, and the paper is clearly written. That is the good part.

The weak part is the theory, and there is a real bug in the algorithm as written. The abstract claims RSPA is 'provably robust in low-noise settings,' but no theorem is proved. The only support is that the functions f_i satisfy Assumption 2, and the SPA robustness bound from [9] does not transfer because RSPA selects by residual norm rather than by argmax of a single f_i. The conclusion admits the rigorous analysis is future work. So the central claim is asserted, not derived.

More concretely, Algorithm 3 misuses Lemma 1 after the first inner iteration. Lemma 1 requires u = x/||x||, where x is the vector in the equation. The algorithm sets x = Y(:,k(i)) but u_i = R(:,k(i))/||R(:,k(i))||. At i = 1 those are the same. After the first Y update, Y(:,k(i)) is not generally a scalar multiple of R(:,k(i)), so the derivation of α_i ∈ (0,1) fails, and the guaranteed exclusion of k(i) from the next candidate set is unsupported. That exclusion is exactly what the diversification step needs to avoid outliers. So the published algorithm is not a correct instance of the lemma it cites.

None of this makes the paper worthless. As a heuristic, RSPA deserves attention; the experimental evidence is real and the cost increase is linear in d. The citation pattern is also appropriate — building on the Gillis–Vavasis analysis is fair, and the new selection rule is distinct from SPA, SNPA, and VCA. The paper would be useful to people working on pure-pixel search or separable NMF who need a fast outlier-resistant method and are willing to treat it as a heuristic.

For peer review: yes, I would send it to a serious referee — the core idea is promising and the fixes are likely small (either redefine u_i consistently or drop the provable-robustness wording). But in its current form I would not accept it: the theoretical claim is unsupported and the Algorithm/Lemma mismatch is load-bearing. A revision that fixes those points would make a decent applied paper.

Referee Report

2 major / 4 minor

Summary. The paper proposes Robust SPA (RSPA), a variant of the successive projection algorithm for separable nonnegative matrix factorization. RSPA replaces SPA's single selection rule with a two-stage procedure: Algorithm 3 generates d quadratic functions f_i via repeated partial projections, computes a candidate index k(i) for each function, and then selects the candidate whose orthogonal projection leaves the smallest residual, measured by the ℓ_p norm of the column-norm vector. The authors claim that RSPA is robust to outliers while remaining provably robust in low-noise settings, and they report experiments on synthetic data and three hyperspectral images showing improved reconstruction error relative to SPA.

Significance. If the central claim were established, RSPA would be a genuinely useful contribution: it is simple, inherits SPA's low computational complexity up to a factor d, and the experiments show clear practical gains on outlier-contaminated data, especially the San Diego hyperspectral image. The code is made available, and Lemma 1 is correct as a standalone algebraic statement. However, the advertised 'provably robust in low-noise settings' property is the distinguishing feature of the paper, and it is not supported by any theorem. The manuscript's own conclusion explicitly defers a rigorous robustness analysis to future work. The empirical evaluation is valuable evidence for RSPA as a heuristic, but it cannot compensate for the absence of the advertised guarantee.

major comments (2)

[Section 3, Algorithm 3, steps 4–9 and Lemma 1] Lemma 1 is proved only for the case u = x/||x||, but Algorithm 3 step 4 sets u_i = R(:,k(i))/||R(:,k(i))|| while step 8 calls Lemma 1 with x = Y(:,k(i)) and y = Y(:,k'(i)). After the first iteration, Y = P_i...P_1 R differs from R, so Y(:,k(i)) is not generally a scalar multiple of R(:,k(i)). Consequently the quantity Δ = β(u_i^T x)^2 - (u_i^T y)^2 in the proof need not satisfy Δ > β||x||^2 - ||y||^2, and the α_i computed from Eq. (1) can fall outside (0,1). The assertion that f_{i+1} will not select k(i) again, which is the mechanism for outlier diversification, is therefore not established.
[Section 3, paragraph beginning 'As long as the functions {f_i}' and Section 5] The abstract and this paragraph claim that RSPA is 'provably robust in low-noise settings' because the f_i satisfy Assumption 2, but no theorem or error bound is stated for RSPA. The robustness guarantee of SPA in [9] applies to a rule that selects the single column maximizing f at each step; RSPA instead generates d candidates from different f_i and selects among them by minimizing the residual e(i), so the analysis in [9] does not transfer. Section 5 explicitly lists 'a rigorous robustness analysis of RSPA with explicit error bounds' as future work, which contradicts the abstract's provable-robustness claim.

minor comments (4)

[Page 2, Introduction] The word 'nonnegtive' in the first sentence is a typo and should be 'nonnegative'.
[Section 3, Algorithm 3 input description] The input line of Algorithm 3 calls d the 'diversification parameter', while Algorithm 2 and the surrounding text call d the 'number of candidates'; please use consistent terminology.
[Section 3, Eq. (1)] The expression for α* lacks parentheses around the numerator and denominator of the fraction under the square root; the intended formula is α* = 1 - sqrt(1 - (β||x||^2 - ||y||^2)/(β(u^T x)^2 - (u^T y)^2)), and the displayed equation should be typeset accordingly.
[Section 3, Algorithm 3, step 5] The notation R_i for the projected matrix can be confused with the outer-loop residual R; using a different symbol, such as R_cur or a tilde, would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: RSPA is a self-contained algorithm with an unsupported robustness extension, not a result that reduces to its inputs.

full rationale

The paper's derivation chain is not circular. Algorithm 3 constructs the diversification functions f_i and the parameters alpha_i directly: Lemma 1 computes alpha_i from x = Y(:,k(i)) and y = Y(:,k'(i)) so that f_{i+1}(R(:,k'(i))) = beta f_{i+1}(R(:,k(i))), and the statement that k(i) will not be selected next is a direct consequence of that constructed inequality, not a fitted quantity being renamed as a prediction. The selection by e(i) is a data-dependent heuristic, and the reported numerical experiments compare RSPA against SPA on synthetic and real data, so the empirical claims are not forced by construction. The main weakness is that RSPA is asserted to be 'provably robust in low-noise settings' while the conclusion defers a rigorous robustness analysis to future work; this is an unproved claim and a derivation gap, not a circular reduction. The citation of the author's prior SPA robustness result [9] is legitimate background, especially for the d=1 case where RSPA reduces to SPA, and it does not by itself smuggle in the d>1 guarantee. The identified mismatch in Algorithm 3, where u_i is normalized from R(:,k(i)) while Lemma 1 requires u = x/||x|| with x = Y(:,k(i)) after the first iteration, is a correctness issue in the argument, not circularity.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The central contribution is an algorithmic heuristic. Its main free parameters are tuned empirically. The key unproved premises are the inheritance of SPA's low-noise guarantee and the validity of the alpha update in later diversification iterations.

free parameters (3)

d = d >= 40 (or order of outlier count)
Number of candidate directions. Experiments show best performance for d >= 40; too small fails on outliers.
p = 1
Error norm parameter in selection. p = 1 is less sensitive to large residual entries; p = 2 performs worse.
beta = 4
Diversification parameter. beta = 4 is best; too large makes P_i ill conditioned, too small gives poor diversification.

assumptions (4)

domain assumption Separability / pure-pixel assumption: X = W H with W columns in the data (Assumption 1).
The entire NMF problem is restricted to separable data, standard in hyperspectral unmixing.
standard math Strong convexity and Lipschitz gradient of selection functions (Assumption 2).
Imported from [9]'s SPA robustness analysis; needed for low-noise guarantees.
ad hoc to paper RSPA selection inherits SPA's low-noise robustness because each f_i satisfies Assumption 2.
Stated without proof in Section 3; the selection rule is not argmax f, so the transfer is non-obvious and the conclusion defers a rigorous analysis.
ad hoc to paper Formula (1) gives alpha_i in (0,1) at every diversification iteration.
Algorithm 3 uses x = Y(:,k(i)) with u_i = R(:,k(i))/||R(:,k(i))||; Lemma 1 assumes u = x/||x||, so the formula's guarantee is not established for i > 1.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Successive Projection Algorithm Robust to Outliers." pith.science (2026). https://pith.science/paper/NK5XVW5C

@misc{pith2026190804109,
  author       = {Pith},
  title        = {Pith review of: Successive Projection Algorithm Robust to Outliers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NK5XVW5C}},
  note         = {Machine review of arXiv:1908.04109}
}

abstract

The successive projection algorithm (SPA) is a fast algorithm to tackle separable nonnegative matrix factorization (NMF). Given a nonnegative data matrix $X$, SPA identifies an index set $\mathcal{K}$ such that there exists a nonnegative matrix $H$ with $X \approx X(:,\mathcal{K})H$. SPA has been successfully used as a pure-pixel search algorithm in hyperspectral unmixing and for anchor word selection in document classification. Moreover, SPA is provably robust in low-noise settings. The main drawbacks of SPA are that it is not robust to outliers and does not take the data fitting term into account when selecting the indices in $\mathcal{K}$. In this paper, we propose a new SPA variant, dubbed Robust SPA (RSPA), that is robust to outliers while still being provably robust in low-noise settings, and that takes into account the reconstruction error for selecting the indices in $\mathcal{K}$. We illustrate the effectiveness of RSPA on synthetic data sets and hyperspectral images.

Figures

Figures reproduced from arXiv: 1908.04109 by the authors.

**Figure 1.** Percentage of recovered columns of W for the synthetic data sets using SPA and RSPA. • RSPA does not perform well when p = 2 as it is more sensitive to large entries in the residual hence to outliers. We have also tried p = 0.5 and it performed similarly as p = 1. • RSPA performs best for β = 4. The parameter β should not be chosen too large as it makes Pi ill conditioned since αi will be close to 1, nor too small a… view at source ↗

**Figure 2.** Columns of X extracted by SPA, RSPA(10,1,4) and RSPA(20,1,4) on the San Diego HSI. Dashed lines represent outliers. We observe the following: • For Urban, RSPA variants allow to slightly reduce the relative error compared to SPA. The gain is appreciable (from 9.58% to 7.65% for RSPA(10,1,4) and to 6.66% for RSPA(20,1,4)) but not significant because the outliers are endmembers corresponding to materials present in sm… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

[9]

IEEE Transactions on Pattern Analysis and Machine Intelligence 36(4), 698–714 (2014)

Gillis, N., Vavasis, S.A.: Fast and robust recursive algorithmsfor se parable nonnegative matrix factorization. IEEE Transactions on Pattern Analysis and Machine Intelligence 36(4), 698–714 (2014)

work page 2014
[1]

Chemometrics and Intelligent Laboratory Systems 57(2), 65–73 (2001)

Ara´ ujo, U., Saldanha, B., Galv˜ ao, R., Yoneyama, T., Chame, H., V isani, V.: The successive projections algorithm for variable selection in spectroscopic multicomponent ana lysis. Chemometrics and Intelligent Laboratory Systems 57(2), 65–73 (2001)

work page 2001
[2]

In: International Co nference on Machine Learning, pp

Arora, S., Ge, R., Halpern, Y., Mimno, D., Moitra, A., Sontag, D., Wu, Y., Zhu, M.: A practical algorithm for topic modeling with provable guarantees. In: International Co nference on Machine Learning, pp. 280–288 (2013)

work page 2013
[3]

In: Proc

Arora, S., Ge, R., Kannan, R., Moitra, A.: Computing a nonnegative matrix factorization – provably. In: Proc. of the 44th Symp. on Theory of Computing (STOC ’12), pp. 14 5–162 (2012)

work page 2012
[4]

John Wiley & Sons (2009)

Cichocki, A., Zdunek, R., Phan, A.H., Amari, S.i.: Nonnegative matrix a nd tensor factorizations: applica- tions to exploratory multi-way data analysis and blind source separa tion. John Wiley & Sons (2009)

work page 2009
[5]

IEEE Signal P rocessing Magazine 36(2), 59–80 (2019)

Fu, X., Huang, K., Sidiropoulos, N.D., Ma, W.K.: Nonnegative matrix fa ctorization for signal and data analytics: Identiﬁability, algorithms, and applications. IEEE Signal P rocessing Magazine 36(2), 59–80 (2019)

work page 2019
[6]

SIAM Journal on Imaging Sciences 7(2), 1420–1450 (2014)

Gillis, N.: Successive nonnegative projection algorithm for robust nonnegative blind source separation. SIAM Journal on Imaging Sciences 7(2), 1420–1450 (2014)

work page 2014
[7]

Gillis, N.: The why and how of nonnegative matrix factorization. In: J. Suykens, M. Signoretto, A. Ar- gyriou (eds.) Regularization, Optimization, Kernels, and Support Ve ctor Machines, chap. 12, pp. 257–291. Chapman & Hall/CRC, Boca Raton, Florida (2014)

work page 2014

Show all 12 references

[8]

IEEE Transactions on Geoscience and Remot e Sensing 53(4), 2066–2078 (2014)

Gillis, N., Kuang, D., Park, H.: Hierarchical clustering of hyperspec tral images using rank-two nonnegative matrix factorization. IEEE Transactions on Geoscience and Remot e Sensing 53(4), 2066–2078 (2014)

2014
[10]

IEEE Signal Processing Magazine 31(1), 67–81 (2014)

Ma, W.K., Bioucas-Dias, J.M., Chan, T.H., Gillis, N., Gader, P., Plaza, A.J ., Ambikapathi, A., Chi, C.Y.: A signal processing perspective on hyperspectral unmixing: Insig hts from remote sensing. IEEE Signal Processing Magazine 31(1), 67–81 (2014)

2014
[11]

IEEE transactions on Geoscience and Remote Sensing 43(4), 898–910 (2005)

Nascimento, J.M., Dias, J.M.: Vertex component analysis: A fast a lgorithm to unmix hyperspectral data. IEEE transactions on Geoscience and Remote Sensing 43(4), 898–910 (2005)

2005
[12]

SIAM Journal on Optimization 20(3), 1364–1377 (2010) 8

Vavasis, S.A.: On the complexity of nonnegative matrix factoriza tion. SIAM Journal on Optimization 20(3), 1364–1377 (2010) 8

2010

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [9]

IEEE Transactions on Pattern Analysis and Machine Intelligence 36(4), 698–714 (2014)

Gillis, N., Vavasis, S.A.: Fast and robust recursive algorithmsfor se parable nonnegative matrix factorization. IEEE Transactions on Pattern Analysis and Machine Intelligence 36(4), 698–714 (2014)

work page 2014

[2] [1]

Chemometrics and Intelligent Laboratory Systems 57(2), 65–73 (2001)

Ara´ ujo, U., Saldanha, B., Galv˜ ao, R., Yoneyama, T., Chame, H., V isani, V.: The successive projections algorithm for variable selection in spectroscopic multicomponent ana lysis. Chemometrics and Intelligent Laboratory Systems 57(2), 65–73 (2001)

work page 2001

[3] [2]

In: International Co nference on Machine Learning, pp

Arora, S., Ge, R., Halpern, Y., Mimno, D., Moitra, A., Sontag, D., Wu, Y., Zhu, M.: A practical algorithm for topic modeling with provable guarantees. In: International Co nference on Machine Learning, pp. 280–288 (2013)

work page 2013

[4] [3]

In: Proc

Arora, S., Ge, R., Kannan, R., Moitra, A.: Computing a nonnegative matrix factorization – provably. In: Proc. of the 44th Symp. on Theory of Computing (STOC ’12), pp. 14 5–162 (2012)

work page 2012

[5] [4]

John Wiley & Sons (2009)

Cichocki, A., Zdunek, R., Phan, A.H., Amari, S.i.: Nonnegative matrix a nd tensor factorizations: applica- tions to exploratory multi-way data analysis and blind source separa tion. John Wiley & Sons (2009)

work page 2009

[6] [5]

IEEE Signal P rocessing Magazine 36(2), 59–80 (2019)

Fu, X., Huang, K., Sidiropoulos, N.D., Ma, W.K.: Nonnegative matrix fa ctorization for signal and data analytics: Identiﬁability, algorithms, and applications. IEEE Signal P rocessing Magazine 36(2), 59–80 (2019)

work page 2019

[7] [6]

SIAM Journal on Imaging Sciences 7(2), 1420–1450 (2014)

Gillis, N.: Successive nonnegative projection algorithm for robust nonnegative blind source separation. SIAM Journal on Imaging Sciences 7(2), 1420–1450 (2014)

work page 2014

[8] [7]

Gillis, N.: The why and how of nonnegative matrix factorization. In: J. Suykens, M. Signoretto, A. Ar- gyriou (eds.) Regularization, Optimization, Kernels, and Support Ve ctor Machines, chap. 12, pp. 257–291. Chapman & Hall/CRC, Boca Raton, Florida (2014)

work page 2014