{"id":"ea33663f-cfbc-4d3d-9f1a-fc481f51fe77","arxiv_id":"1908.04109","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"RSPA is a new SPA variant that selects columns by minimizing residual error across several diversified candidates, giving better outlier robustness in separable nonnegative matrix factorization.","lead":"This paper introduces RSPA, a modified successive projection algorithm that keeps working when a data set contains a few unusual, outlier columns. RSPA is meant for problems such as finding pure materials in satellite images and important words in documents, where the old method fails on outliers.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 3 misapplies Lemma 1 after the first loop: u_i=R(:,k(i))/||R(:,k(i))|| but x=Y(:,k(i)), so Eq. (1) need not give α∈(0,1) and the promised outlier-avoidance guarantee is unsupported.","rationale":"The reader's weakest assumption identifies the same point: Lemma 1 is called with x=Y but u built from R. This is load-bearing because the only argument connecting RSPA's diversification to outlier avoidance is that equality, and once Y diverges from R the precondition u=x/||x|| fails. The abstract's 'provably robust in low-noise settings' is not backed by any theorem; the concluding paragraph explicitly lists a rigorous robustness analysis as future work. That self-acknowledged lack of support, together with the likely algorithmic inconsistency, justifies the reader's REJECT. I would not change the verdict; the empirical section is clearly presented and the code is a useful artifact, but the central claim as written is not established.","tokens_in":7191,"tokens_out":10144,"duration_ms":101499,"concrete_test":"Instrument Algorithm 3 on a small synthetic R (e.g., m=2 or m=3 with two large, correlated columns). After i=1, set Y=(I−α_1u_1u_1^T)R, choose k(2)=argmax_j||Y(:,j)||, and inspect x=Y(:,k(2)), u=R(:,k(2))/||R(:,k(2))||. Since u≠x/||x|| in general, compute α by Eq. (1) and test whether α∈(0,1) and whether ||(I−αuu^T)Y(:,k'(2))||² = β||(I−αuu^T)Y(:,k(2))||². One counterexample disproves the claimed guarantee; if none exists over an exhaustive random search, the concern would be weakened.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Algorithm 3's diversification step is where outlier avoidance is supposed to be guaranteed, but the application of Lemma 1 is inconsistent. 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)). Lemma 1 requires u=x/||x||. At i=1, Y=R and the requirement holds; for i>1, Y=P_i...P_1R, so Y(:,k(i)) is not generally a scalar multiple of R(:,k(i)). Hence Eq. (1) is not the unique α∈(0,1) solving ||(I−αu_i u_i^T)Y(:,k')||²=β||(I−αu_i u_i^T)Y(:,k)||²; the required Δ=β(u_i^Tx)²−(u_i^Ty)² can be too small or negative, so the computed α may fail to be in (0,1). The claim that f_{i+1} will not identify k(i) again is therefore not established. Separately, the paper asserts that RSPA is 'provably robust in low-noise settings' but gives no theorem; the conclusion defers a 'rigorous robustness analysis' to future work, and SPA's known robustness proof does not transfer to this different selection rule. The experiments are useful evidence for RSPA as a heuristic, but they do not support the central provable-robustness claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":7556,"tokens_out":6839,"duration_ms":65891,"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":[{"comment":"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":"Section 3, Algorithm 3, steps 4–9 and Lemma 1"},{"comment":"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.","section":"Section 3, paragraph beginning 'As long as the functions {f_i}' and Section 5"}],"minor_comments":[{"comment":"The word 'nonnegtive' in the first sentence is a typo and should be 'nonnegative'.","section":"Page 2, Introduction"},{"comment":"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":"Section 3, Algorithm 3 input description"},{"comment":"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":"Section 3, Eq. (1)"},{"comment":"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.","section":"Section 3, Algorithm 3, step 5"}],"recommendation":"reject","confidential_remarks":"The manuscript would be more credible if reframed as a heuristic algorithm with empirical evaluation; as written, the abstract overclaims a provable robustness property that the paper itself defers to future work, and the diversification step in Algorithm 3 has a concrete technical inconsistency. Because the unsupported guarantee is the central selling point, I do not see a path to acceptance without substantial new theoretical work."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague —\n\nShort 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.\n\nThe 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.\n\nMore 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.\n\nNone 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.\n\nFor 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.","headline":"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.","tokens_in":8024,"tokens_out":6830,"would_cite":false,"duration_ms":58004,"reading_group":"yes","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["nonnegative matrix factorization","separable NMF","successive projection algorithm","pure-pixel search","hyperspectral unmixing","outlier robustness","greedy column selection","reconstruction error"],"falsifier":"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.","tokens_in":6979,"feed_emoji":"🛰️","tokens_out":10021,"duration_ms":85092,"temperature":0.7,"pith_summary":"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%.","feed_headline":"Outlier-robust SPA recovers endmembers classic SPA loses","feed_subtitle":"A diversified selection step cuts hyperspectral unmixing error on San Diego from 12.6% to 6.0 percent.","key_machinery":"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.","core_discovery":"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%.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"supplies SPA's low-noise robustness guarantees and the O(mnr) complexity that RSPA extends to O(mnrd)","marker":"[9]"},{"why":"introduces the original successive projection algorithm that RSPA modifies","marker":"[1]"},{"why":"provides the provable separable NMF guarantees that motivate SPA's use","marker":"[3]"},{"why":"describes VCA, a related greedy algorithm whose linear selection function is not noise-robust and serves as a comparison baseline","marker":"[11]"},{"why":"describes SNPA, another greedy algorithm the paper expects to fail on outliers like SPA","marker":"[6]"},{"why":"ties separability to the pure-pixel assumption in hyperspectral unmixing, the main application tested","marker":"[10]"},{"why":"describes the three hyperspectral images (Urban, San Diego, Cuprite) used in the experiments","marker":"[8]"},{"why":"motivates separable NMF for document classification, the other target application mentioned","marker":"[2]"}],"fun_headline_variants":["Outlier-robust SPA halves hyperspectral unmixing error","RSPA: SPA that ignores outliers, slashes unmixing error","Robust SPA selection recovers endmembers despite outliers","SPA variant robust to outliers improves unmixing accuracy"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Outlier-robust SPA halves hyperspectral unmixing error","RSPA: SPA that ignores outliers, slashes unmixing error","Robust SPA selection recovers endmembers despite outliers","SPA variant robust to outliers improves unmixing accuracy"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000773,"raw_usage":{"total_tokens":3466,"prompt_tokens":1031,"completion_tokens":2435,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":647,"completion_tokens_details":{"reasoning_tokens":2363}},"tokens_in":647,"tokens_out":2435,"duration_ms":16301,"temperature":1.0,"reasoning_tokens":2363,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:51:25.117196+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"IEEE Transactions on Pattern Analysis and Machine Intelligence 36(4), 698–714 (2014)","cited_arxiv_id":null,"evidence_quote":"supplies SPA's low-noise robustness guarantees and the O(mnr) complexity that RSPA extends to O(mnrd)"},{"cited_title":"Chemometrics and Intelligent Laboratory Systems 57(2), 65–73 (2001)","cited_arxiv_id":null,"evidence_quote":"introduces the original successive projection algorithm that RSPA modifies"},{"cited_title":"In: Proc","cited_arxiv_id":null,"evidence_quote":"provides the provable separable NMF guarantees that motivate SPA's use"},{"cited_title":"IEEE transactions on Geoscience and Remote Sensing 43(4), 898–910 (2005)","cited_arxiv_id":null,"evidence_quote":"describes VCA, a related greedy algorithm whose linear selection function is not noise-robust and serves as a comparison baseline"},{"cited_title":"SIAM Journal on Imaging Sciences 7(2), 1420–1450 (2014)","cited_arxiv_id":null,"evidence_quote":"describes SNPA, another greedy algorithm the paper expects to fail on outliers like SPA"},{"cited_title":"IEEE Signal Processing Magazine 31(1), 67–81 (2014)","cited_arxiv_id":null,"evidence_quote":"ties separability to the pure-pixel assumption in hyperspectral unmixing, the main application tested"},{"cited_title":"IEEE Transactions on Geoscience and Remot e Sensing 53(4), 2066–2078 (2014)","cited_arxiv_id":null,"evidence_quote":"describes the three hyperspectral images (Urban, San Diego, Cuprite) used in the experiments"},{"cited_title":"In: International Co nference on Machine Learning, pp","cited_arxiv_id":null,"evidence_quote":"motivates separable NMF for document classification, the other target application mentioned"}],"review_version":1}