{"id":"5396f0c7-250e-4dd8-9f11-a6ba6077d3cd","arxiv_id":"2507.10484","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Target Polish embeds outlier shrinkage into Fast-HALS updates, cutting robust NMF runtime by an order of magnitude while matching or exceeding accuracy only in some corrupted-image scenarios.","lead":"This paper introduces Target Polish, a modified Fast-HALS algorithm for non-negative matrix factorization that replaces poorly fitted data points with the global median to resist outliers. Early tests on face images with block and salt noise show about ten times faster runtime than weighted NMF baselines, but accuracy gains are not consistent across all settings.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The central mechanism is unsupported: Eq. (9) assumes WH^T gravitates to med(X) for poorly fit entries, but structured outliers can dominate least-squares projections, and the paper's own tables contradict the 'matches or exceeds accuracy' claim.","rationale":"The reader's weakest_assumption is close but broader; my concern sharpens it to a concrete failure mode. The paper itself concedes convergence analysis is a 'fundamental priority' (Discussion), and the heuristic proof is circular: it invokes the desired gravitation-to-median behavior to justify replacing X with med(X). The runtime advantage is credible because Fast-HALS is used and code is referenced, and ORL block results do show large gains. However, the abstract's 'matches or exceeds the accuracy' statement is contradicted by multiple rows of Tables 1-2. A conditional acceptance with a demand for the ablation, plus a revised abstract, is appropriate; I would not reject because the method may still be a useful empirical heuristic and the speed gain is real.","tokens_in":6691,"tokens_out":6512,"duration_ms":85153,"concrete_test":"Ablate the core step: run the full Target Polish pipeline with Eq. (9) replaced by tilde X = X (no polishing), keeping the same Fast-HALS update schedule, sampling rule, and final Weighted NMF refinement, on both block and salt corruptions of ORL and CroppedYaleb. If the no-polish baseline matches Target Polish in RRE/ACC/NMI, then the median-polishing mechanism is not the source of robustness and the paper's central contribution is unsupported. Optionally, in the same runs, record (WH^T)_ij at corrupted positions after the first few updates; if those values lie near the outlier intensities rather than near med(X), the gravitation premise of the heuristic proof fails directly.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The load-bearing step is the 'heuristic proof' around Eqs. (9)-(10). It claims that for a poorly approximated entry (G_ij ~ 0), (WH^T)_ij gravitates toward med(X), so replacing X_ij by med(X) reduces the adaptive criterion. This is the very property that needs proof, and it is not generally true: Fast-HALS minimizes a least-squares objective against the current target, so a large structured block of outliers is itself a strong low-rank pattern; alternating projections can make (WH^T)_ij track the outlier value rather than the global median. When that happens, Eq. (9) rewrites a well-fit outlier to the median, creates a spurious residual, and pulls W and H away from X. The final Weighted NMF refinement is supposed to correct this, but no experiment isolates how much of the reported accuracy comes from polishing versus from that refinement. The tables also undercut the abstract's accuracy claim: e.g., CroppedYaleb+block+CIM gives Target Polish RRE 0.2632 vs 0.2328 for Weighted NMF with lower ACC/NMI; ORL+salt+CIM gives RRE 0.1945 vs 0.1365. The robust advantage shown is mostly runtime, not accuracy.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proposes \"Target Polish,\" a robust NMF framework that keeps the fast additive updates of Fast-HALS. Instead of solving a weighted least-squares problem directly, the method replaces each entry of the data matrix X with a \"polished\" target X~_ij = (1-G_ij) med(X) + G_ij X_ij, where G_ij is a CIM- or Huber-type weight built from the current residual. Fast-HALS iterations are then run against X~, with the target refreshed only when a sampled relative-change criterion exceeds a threshold. After convergence, a few Weighted NMF iterations are run to bring the factorization back toward the original X. Experiments on ORL and CroppedYaleb with block and salt corruption report relative reconstruction error (against the uncorrupted images), clustering accuracy, NMI, and runtime. The consistent empirical finding is that Target Polish is much faster than Weighted NMF, often by an order of magnitude, whereas accuracy is mixed: in several rows Weighted NMF achieves lower RRE and comparable or higher ACC/NMI.","tokens_in":7061,"tokens_out":5441,"duration_ms":68120,"significance":"Robust NMF is an active and practically relevant area, and the idea of preserving Fast-HALS's speed while obtaining outlier resistance is attractive. The runtime gains reported in Tables 1 and 2 are consistently demonstrated, for example 2.48 s versus 19.38 s for ORL block CIM and 4.28 s versus 22.33 s for CroppedYaleb block CIM. The paper also computes RRE against the original uncorrupted images, which is a more honest error measure than RRE against the corrupted input. However, the central mechanism is justified only by a heuristic argument that assumes the very convergence behavior it needs to prove, and the abstract's claim that the method \"matches or exceeds the accuracy of state-of-the-art robust NMF methods\" is contradicted by several rows in Tables 1 and 2. There is no formal convergence analysis, no ablation isolating the contribution of the final Weighted NMF refinement, and no sensitivity analysis for the two central hyperparameters. The contribution is therefore promising but not yet established to the standard claimed in the abstract.","major_comments":[{"comment":"The \"heuristic proof\" that replacing a poorly approximated X_ij with med(X) reduces the adaptive criterion relies on the unproved assertion that alternating projections make (WH^T)_ij gravitate toward med(X) rather than toward extreme outliers. This is the central property at issue: Fast-HALS minimizes a least-squares objective against the current target, so a large structured block of outliers is itself a strong low-rank pattern and the factorization can track the outlier block instead of the global median. In that case Eq. (9) rewrites a well-fit outlier to the median, creates a spurious residual, and pulls W and H away from X. The Discussion acknowledges that convergence properties have not been examined. Please provide a rigorous statement with explicit assumptions, or at least a controlled experiment with large structured outliers and an ablation that isolates how much of the reported accuracy comes from the polishing step versus the final Weighted NMF refinement.","section":"Mathematical formulation, Eqs. (9)-(10)"},{"comment":"The abstract's claim that Target Polish \"matches or exceeds the accuracy of state-of-the-art robust NMF methods\" is not supported by the reported numbers. In Table 1, ORL salt CIM gives Target Polish RRE 0.1945 versus Weighted NMF 0.1365, and ORL salt Huber gives 0.2041 versus 0.1432. In Table 2, CroppedYaleb block CIM gives 0.2632 versus 0.2328, and CroppedYaleb salt Huber gives 0.2602 versus 0.2018. In these settings Weighted NMF has lower reconstruction error, and ACC/NMI are mixed. The consistent advantage is computational time, not accuracy. The abstract should be revised to state what the data actually show, for example comparable accuracy in most scenarios with an order-of-magnitude runtime reduction, or new experiments should be provided that support the stronger claim.","section":"Abstract and Tables 1-2"},{"comment":"The two hyperparameters, fraction=0.001 and relative-change threshold=0.05, are set \"based on our experience with corrupted images\" and no sensitivity analysis is reported. These parameters control how often the polished target is refreshed, which directly affects both convergence behavior and computational cost, and their appropriate values may depend on matrix size and noise type. Please report a sensitivity study across a range of these parameters, or provide a principled way to set them, so the reported speed and accuracy results can be assessed as reproducible rather than tied to a single hand-picked configuration.","section":"Methods, Eqs. (11)-(12); parameter choice"}],"minor_comments":[{"comment":"The text references \"Python jasoncoding13 code\" without a URL or version and gives only a GitHub link for enAInem; please provide exact repository URLs, commit hashes, and any wrapper scripts used to implement Eq. (9), so the experiments can be reproduced.","section":"Data and Code availability"},{"comment":"Please define med(X) precisely: it should be stated whether this is the global median over all entries of X, a per-row median, or a per-column median, and whether the median is recomputed when the target is refreshed.","section":"Equation (9)"},{"comment":"The sampling scheme is not fully specified: it is unclear how non-integer step sizes are handled, whether the same sampled subset is used for the relative-change criterion and for convergence, and how the subset is updated between refreshes.","section":"Equation (11)"},{"comment":"Both figures lack axis labels, and Figure 4 appears to compare several methods without a legend identifying the curves; these should be added so the convergence claims can be checked visually.","section":"Figures 2 and 4"},{"comment":"The sentence \"The small number of iterations is due to the poor performance of Weighted NMF\" is unclear: please specify which iterations are meant, report the actual numbers, and give standard deviations or confidence intervals for the ten runs, since only averages are reported.","section":"Results section"}],"recommendation":"major_revision","confidential_remarks":"The paper is a borderline major-revision case. The underlying idea is simple and attractive, and the runtime benefit is consistently demonstrated. However, the abstract overstates accuracy relative to the paper's own tables, and the load-bearing step of Eq. (9) is not justified beyond a heuristic argument. These issues are fixable within the scope of a revision: a rigorous or at least well-tested treatment of the target-polishing step, an ablation of the final Weighted NMF stage, a sensitivity analysis for the sampling parameters, and a more accurate abstract. The lack of a complete code release also hampers verification. I would not accept the manuscript in its current form."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Target Polish is a genuine algorithmic contribution with a clear, reproduced speed advantage and a weaker accuracy story than the abstract sells. The core trick — compute robust weights from the current residual, then replace each entry of X by a weighted blend of the entry and the global median before running Fast-HALS — is simple and I don't think it appears in the weighted-NMF literature. It preserves the additive update structure that makes Fast-HALS fast, and the runtime numbers are consistently in its favor: 2.48 s vs 19.38 s on ORL block CIM, 4.28 s vs 22.33 s on CroppedYaleb block CIM, and similar ratios elsewhere. The Python code is linked, so the speed claim is checkable. That is real evidence.\n\nThe abstract says the method 'matches or exceeds accuracy' of state-of-the-art robust NMF. The tables don't back that for salt noise and partly for block. ORL salt CIM gives RRE 0.1945 vs 0.1365 for weighted NMF; CroppedYaleb salt gives 0.2185 vs 0.2050 and worse ACC/NMI; CroppedYaleb block CIM is 0.2632 vs 0.2328. So the honest version is 'comparable or worse reconstruction, consistently much faster.' That is still publishable, but the claim needs to be dialed back.\n\nThe theoretical soft spot is the 'heuristic proof' after Eq. (10). It assumes poorly approximated entries have (WH^T)_ij pulled toward med(X) rather than toward the outlier. That is plausible for isolated salt pixels, but not for block corruption: a white rectangle is a low-rank pattern, and alternating least squares can happily fit it. The stress-test note describes exactly this failure mode, and the paper does not address it. The final Weighted NMF pass may be doing much of the cleanup, but there is no ablation separating polishing from refinement. The paper itself concedes convergence properties need examination; the hyperparameters fraction=0.001 and threshold=0.05 are from experience and no sensitivity analysis is reported. No error bars either, though ten simulations were run.\n\nFor all that, the paper is coherent and honest about its limitations. It is a practical speedup result, not a conceptual breakthrough. I'd send it to a serious referee: the algorithm is new, the runtime gain is reproducible, and the fixes are within reach — revise the abstract, add an ablation, and include at least a fixed-point analysis of the polishing step. My own recommendation would be conditional acceptance.","headline":"Target Polish is a genuinely faster robust NMF variant with a slick weighted-median trick, but the abstract overclaims accuracy and the convergence argument is more asserted than proven.","tokens_in":7555,"tokens_out":3949,"would_cite":false,"duration_ms":42829,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Target Polish makes robust NMF an order of magnitude faster by polishing data toward the global median instead of weighting the objective.","keywords":["robust NMF","weighted median","Fast-HALS","outlier resistance","non-negative matrix factorization","image corruption","low-rank approximation"],"falsifier":"Take a dataset where a large contiguous block of each image is corrupted by a constant offset that shifts the global median away from the true background, run Target Polish and the weighted baseline on the same random initializations, and compare reconstruction error on the clean ground truth; the claim would be falsified if Target Polish's error or clustering accuracy falls below the baseline's while its speed advantage narrows. A sharper in-run check is whether, for a poorly approximated corrupted entry, $(WH^T)_{ij}$ moves toward the corrupted value rather than toward $\\mathrm{med}(X)$ on the first polish update.","tokens_in":6555,"feed_emoji":"⚡","tokens_out":9212,"duration_ms":106902,"temperature":0.7,"pith_summary":"This paper claims that outlier-resistant non-negative matrix factorization can be made compatible with the fast Fast-HALS solver by polishing the data before each update rather than weighting the objective. The polish replaces each entry by a weighted average of the entry and the global median, where the weight is a robust function of how badly the current factorization approximates that entry. On face-image datasets corrupted with block and salt noise, the authors report that Target Polish matches or exceeds weighted CIM-NMF and the thresholded absolute-error robust NMF on reconstruction and clustering metrics while cutting computation time by an order of magnitude. If correct, robust NMF becomes practical for large image and tensor collections without sacrificing speed.","feed_headline":"Tenfold faster robust NMF by polishing data toward the median","feed_subtitle":"Target Polish keeps Fast-HALS speed while matching weighted NMF accuracy on corrupted face images.","key_machinery":"The load-bearing object is the polished target $\\tilde{X}_{ij} = (1-G_{ij})\\,\\mathrm{med}(X) + G_{ij}X_{ij}$, where $G_{ij}$ is a robust weight in $[0,1]$ computed from the current approximation error, e.g., the exponential CIM weight or the thresholded absolute-error weight. The paper minimizes the Frobenius criterion $\\tilde{J} = \\sum_{i,j}(\\tilde{X}_{ij}-(WH^T)_{ij})^2$ against this target, preserving the additive, associative update structure of Fast-HALS. Because $\\tilde{X}$ is only fully recomputed when the sampled relative change of Eq. (11) exceeds a threshold, the polish itself is cheap; the global median, rather than the mean, is the robust anchor, and the heuristic argument is that alternating projections pull poorly approximated entries toward $\\mathrm{med}(X)$.","core_discovery":"The paper's central claim is that robust NMF does not have to sacrifice the speed of Fast-HALS. Instead of folding per-entry weights into the Frobenius objective, which breaks the matrix-multiplication associativity that Fast-HALS exploits, Target Polish transforms the data matrix itself: each entry is replaced by a weighted blend of the entry and the global median, with weights derived from standard robust error measures. Minimizing the factorization error against this polished target keeps the Fast-HALS update rules intact, and repolishing is done only when a sampled relative-change test exceeds a threshold. On the ORL and CroppedYaleb face databases with block and salt corruption, Target Polish with the exponential CIM weight matches or exceeds weighted CIM-NMF and the thresholded absolute-error weighted NMF on reconstruction error and clustering agreement for block noise, matches them for salt noise, and runs roughly ten times faster.","pith_inferences":["One extension the authors leave implicit is that the global-median anchor assumes outliers are scattered entries; for row- or column-wise corruption, a per-row or per-column median variant would be a natural test and might preserve the speed advantage.","Because the paper's convergence argument is heuristic, a rigorous route would be to show each repolish is a bounded, data-dependent perturbation of the target matrix and that Fast-HALS convergence survives; proving the polish step is a contraction toward a robust fixed point would settle the question.","The speed advantage depends on the cost of sampling and the global median; on very large matrices the median computation may become a bottleneck, so a streaming or approximate median is a practical scalability test.","Hyperparameters such as the sampling fraction and the repolish threshold are set from experience with corrupted images, so testing on additive Gaussian outliers, contrast shifts, or structural anomalies would show whether recalibration is needed."],"forward_implications":["Robust NMF on large corrupted image collections can run roughly ten times faster than weighted NMF with exponential or thresholded absolute-error weights, making outlier-resistant factorization practical at scale.","Because the polish operates on the data matrix rather than the solver, Target Polish can be dropped into existing Fast-HALS pipelines with no change to the core update rules.","The same mechanism extends to tensors of any dimension, since the authors implement it for multidimensional arrays in their accompanying code.","Target Polish can serve as an initialization for weighted NMF, carrying the final robust weights forward, so the factorization is brought back to the original data efficiently.","For block-corrupted images the paper reports substantially better clustering accuracy and normalized mutual information than weighted CIM-NMF and thresholded absolute-error weighted NMF, while salt-corruption results are comparable."],"supporting_citations":[{"why":"Supplies the Fast-HALS additive update rules that Target Polish preserves by polishing the data instead of weighting the objective.","marker":"Cichocki and Phan 2009"},{"why":"Supplies the CIM and thresholded absolute-error weighting schemes used to define the weights in the polished-target formula and the weighted-NMF baselines.","marker":"Du, Li, and Shen 2012"},{"why":"Shows that weighted NMF multiplicative updates converge sub-linearly, the speed problem Target Polish is designed to avoid.","marker":"Badeau, Bertin, and Vincent 2011"},{"why":"Gives the robust weighted-least-squares principle that motivates replacing discrepant observations by low weights.","marker":"Green 1984"},{"why":"Establishes the NMF problem and the non-negativity and sparsity interpretation that Target Polish factorizes.","marker":"Lee and Seung 1999"},{"why":"Analyzes Fast-HALS convergence, the property Target Polish relies on between repolish updates.","marker":"Hou, Chu, and Liao 2024"}],"fun_headline_variants":["Robust NMF at Fast-HALS speed via median polish","Median-polish NMF: tenfold faster with outlier resistance","Target Polish: robust NMF without the speed penalty","Outlier-proof NMF now ten times faster with Target Polish","Fast-HALS speed with median polish for robust NMF"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that entries the current approximation fits poorly are outliers, so pulling them toward the global median of the data lowers the true error; the authors flag that convergence of this alternating process is not yet proven and that the two hyperparameters are set from experience with corrupted images.","fun_headline_variants_meta":{"raw":{"variants":["Robust NMF at Fast-HALS speed via median polish","Median-polish NMF: tenfold faster with outlier resistance","Target Polish: robust NMF without the speed penalty","Outlier-proof NMF now ten times faster with Target Polish","Fast-HALS speed with median polish for robust NMF"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000541,"raw_usage":{"total_tokens":2547,"prompt_tokens":855,"completion_tokens":1692,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":471,"completion_tokens_details":{"reasoning_tokens":1609}},"tokens_in":471,"tokens_out":1692,"duration_ms":13002,"temperature":1.0,"reasoning_tokens":1609,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:29:24.941814+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a dataset where a large contiguous block of each image is corrupted by a constant offset that shifts the global median away from the true background, run Target Polish and the weighted baseline on the same random initializations, and compare reconstruction error on the clean ground truth; the claim would be falsified if Target Polish's error or clustering accuracy falls below the baseline's while its speed advantage narrows. A sharper in-run check is whether, for a poorly approximated corrupted entry, $(WH^T)_{ij}$ moves toward the corrupted value rather than toward $\\mathrm{med}(X)$ on the first polish update.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows that weighted NMF multiplicative updates converge sub-linearly, the speed problem Target Polish is designed to avoid."}],"review_version":1}