Pith. sign in

REVIEW 3 major objections 5 minor 16 references

The Target Polish: A New Approach to Outlier-Resistant Non-Negative Matrix Factorization

T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read Target Polish makes robust NMF an order of magnitude faster by polishing data toward the global median instead of weighting the objective.

desk verdict 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. read the letter →

arxiv 2507.10484 v3 pith:3K6EG5CH submitted 2025-07-14 cs.LG

Paul Fogel (1) , Christophe Geissler (1) , George Luta (2) ((1) Data Services , Forvis Mazars , Levallois , France , (2) Department of Biostatistics , Bioinformatics
show 5 more authors
Biomathematics Georgetown University Medical Center Washington DC USA)
This is my paper · ORCID
classification cs.LG
keywords robustNMFweightedmedianFast-HALSoutlierresistancenon-negativematrixfactorizationimagecorruptionlow-rankapproximation
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

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.

What carries the argument

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)$.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

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.

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 (3)
  1. [Mathematical formulation, Eqs. (9)-(10)] 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.
  2. [Abstract and Tables 1-2] 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.
  3. [Methods, Eqs. (11)-(12); parameter choice] 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.
minor comments (5)
  1. [Data and Code availability] 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.
  2. [Equation (9)] 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.
  3. [Equation (11)] 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.
  4. [Figures 2 and 4] 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.
  5. [Results section] 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.

Circularity Check

1 steps flagged · score 4.0 of 10

The 'heuristic proof' that polishing reduces error is a restatement of Eq. (9)-(10); median-gravitation is assumed, and final accuracy is delegated to Weighted-NMF refinement.

  1. self definitional [Materials and methods, 'Mathematical formulation' (Eqs. 9-10 and the 'heuristic proof' paragraph)]
    "˜Xij = (1− Gij)med(X) +GijXij (9) ... 1. Poor approximation ( Gij ≈ 0) ... ˜Jij ≈ (med(X) − (W HT )ij)2 ... When approximation quality is poor, Xij is likely considered an outlier, making its replacement with med(X) a strategy that can further minimize the optimization criterion."

    The polished target in Eq. 9 is built from med(X), Xij, and Gij, where Gij is itself determined by the residual between the current factorization and X; Eq. 10 then minimizes distance to this constructed target. For a poorly approximated entry, Gij≈0 by construction, so the criterion reduces to (med(X) − (WH^T)ij)^2. The claimed 'further reduction' is therefore an algebraic consequence of how the target is defined, not evidence that Fast-HALS makes (WH^T)ij gravitate toward the median. That gravitation is exactly the unproved premise the proof needs. The paper's own Discussion concedes that a thorough examination of convergence properties remains a fundamental priority.

full rationale

The main empirical comparison (Tables 1-2) is self-contained: it runs Target Polish, Weighted CIM-NMF, and Weighted Huber-NMF on the public ORL and CroppedYaleb databases with block and salt corruption, so the runtime and accuracy numbers do not reduce to the construction. However, the paper's only theoretical justification for Target Polish is the 'heuristic proof' that replacing poorly approximated entries by med(X) reduces the adaptive criterion; that proof is a restatement of Eqs. (9)-(10), since Gij≈0 forces the target to the median. The median-gravitation of Fast-HALS iterates is assumed, not proven, and the paper itself lists convergence analysis as a fundamental priority. The final Weighted-NMF refinement also means the reported accuracy against uncorrupted images is not attributable to polishing alone, so the central robustness mechanism remains an ansatz rather than a derivation. Score 4 reflects partial circularity in the theoretical argument while the empirical evaluation has independent content.

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

The method introduces no new entities or particles. Its load-bearing assumptions are the heuristic convergence-to-median claim and the hand-set sampling/threshold parameters, both of which are untested across noise types and data scales.

free parameters (4)
  • fraction = 0.001
    Sampling fraction in Eq. 12 controls how often the full polished target is refreshed; chosen "based on our experience with corrupted images", no sensitivity analysis.
  • relative change threshold = 0.05
    Threshold in Eq. 11 decides when to recompute the fully polished target; also hand-set without sensitivity analysis.
  • rank r = not reported
    The number of components r is not stated in the paper; it is a standard NMF hyperparameter and its choice affects all results.
  • number of final Weighted NMF iterations = not reported
    The paper says "a few iterations of Weighted NMF" are performed after Target Polish convergence, without specifying the count or stopping rule.
assumptions (4)
  • standard math Fast-HALS converges for a fixed target matrix (Hou et al. 2024).
    The paper relies on the convergence properties of Fast-HALS for a fixed objective, cited from Hou, Chu, and Liao 2024, to justify speed.
  • domain assumption The global median med(X) is a robust center for image data with block and salt corruption.
    The polished target in Eq. 9 pulls outliers toward med(X); this assumes the median is a good stand-in for the true uncorrupted value, which holds for low-corruption images but may fail for dense or biased noise.
  • domain assumption CIM and Huber weight functions provide outlier resistance.
    The method inherits robustness from the weights defined in Eqs. 7-8, citing Du et al. 2012 and Wang et al. 2019; no new robustness theory is provided.
  • ad hoc to paper The factorization values (WH^T)ij gravitate toward med(X) under alternating projections.
    This is the core assertion of the "heuristic proof"; it is not proven and the Discussion admits convergence analysis is future work.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Target Polish: A New Approach to Outlier-Resistant Non-Negative Matrix Factorization." pith.science (2026). https://pith.science/paper/3K6EG5CH

@misc{pith2026250710484,
  author       = {Pith},
  title        = {Pith review of: The Target Polish: A New Approach to Outlier-Resistant Non-Negative Matrix Factorization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3K6EG5CH}},
  note         = {Machine review of arXiv:2507.10484}
}
read the original abstract

This paper introduces the "Target Polish," a robust and computationally efficient framework for Non-Negative Matrix Factorization (NMF). Although conventional weighted NMF approaches are resistant to outliers, they converge slowly due to the use of multiplicative updates to minimize the objective criterion. In contrast, the Target Polish approach remains compatible with the Fast-HALS algorithm, which is renowned for its speed, by adaptively "polishing" the data with a weighted median-based transformation. This innovation provides outlier resistance while maintaining the highly efficient additive update structure of Fast-HALS. Empirical evaluations using image datasets corrupted with structured (block) and unstructured (salt) noise demonstrate that the Target Polish approach matches or exceeds the accuracy of state-of-the-art robust NMF methods while reducing computational time by an order of magnitude in the studied scenarios.

Figures

Figures reproduced from arXiv: 2507.10484 by the authors.

Figure 1
Figure 1. Sample from the ORL image database. Right panel [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Relative error as a function of the update iteration [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Sample from the ORL image database. Right panel [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Relative error (using the non-corrupted data) as a [PITH_FULL_IMAGE:figures/full_fig_p005_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 11 canonical work pages

  1. [1]

    Badeau, R.; Bertin, N.; and Vincent, E. 2011. Stability analysis of multiplicative update algorithms for non-negative matrix factorization. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 1--4. Prague, Czech Republic: IEEE. doi:10.1109/ICASSP.2011.5946456

    work page arXiv 2011

  2. [2]

    W.; Browne, M.; Langville, A

    Berry, M. W.; Browne, M.; Langville, A. N.; Pauca, V. P.; and Plemmons, R. J. 2007. Algorithms and Applications for Approximate Nonnegative Matrix Factorization. Computational Statistics & Data Analysis 52(1): 155--173. doi:10.1016/j.csda.2006.11.006

    work page doi:10.1016/j.csda.2006.11.006 2007

  3. [3]

    Cichocki, A.; and Phan, A.-H. 2009. Fast Local Algorithms for Large Scale Nonnegative Matrix and Tensor Factorizations. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E92.A(3): 708--721. doi:10.1587/transfun.E92.A.708

    work page doi:10.1587/transfun.e92.a.708 2009

  4. [4]

    H.; and Amari, S

    Cichocki, A.; Zdunek, R.; Phan, A. H.; and Amari, S. I. 2009. Nonnegative Matrix and Tensor Factorizations: Applications to Exploratory Multi-way Data Analysis and Blind Source Separation. John Wiley & Sons. ISBN 978-0470746660

    work page 2009

  5. [5]

    Devarajan, K. 2008. Nonnegative Matrix Factorization: An Analytical and Interpretive Tool in Computational Biology. PLoS Computational Biology 4(7): e1000029. doi:10.1371/journal.pcbi.1000029

    work page doi:10.1371/journal.pcbi.1000029 2008

  6. [6]

    Du, L.; Li, X.; and Shen, Y.-D. 2012. Robust Nonnegative Matrix Factorization via Half-Quadratic Minimization. In 2012 IEEE 12th International Conference on Data Mining, 201--210. IEEE. doi:10.1109/ICDM.2012.89

    work page doi:10.1109/icdm.2012.89 2012

  7. [7]

    Fogel, P.; Geissler, C.; Augé, F.; Boldina, G.; and Luta, G. 2024. Integrated Sources Model: A New Space-Learning Model for Heterogeneous Multi-View Data Reduction, Visualization, and Clustering. Artificial Intelligence in Health 1(3): 89--113. doi:10.36922/aih.3427

    work page doi:10.36922/aih.3427 2024

  8. [8]

    Green, P. J. 1984. Iteratively Reweighted Least Squares for Maximum Likelihood Estimation, and Some Robust and Resistant Alternatives. Journal of the Royal Statistical Society: Series B (Methodological) 46(2): 149--192. doi:10.1111/j.2517-6161.1984.tb01288.x

    arXiv 1984

Show all 16 references
  1. [9]

    Guillamet, D.; Bressan, M.; and Vitria, J. 2002. Non-negative Matrix Factorization for Face Recognition. In Topics in Artificial Intelligence. Lecture Notes in Computer Science, volume 2527, 336--344. Springer. doi:10.1007/3-540-36127-6_31

    2002 doi

  2. [10]

    R.; Ronchetti, E

    Hampel, F. R.; Ronchetti, E. M.; Rousseeuw, P. J.; and Stahel, W. A. 1986. Robust Statistics: The Approach Based on Influence Functions. New York: John Wiley & Sons

    1986

  3. [11]

    Ho, N.-D. 2008. Nonnegative Matrix Factorization - Algorithms and Applications. Ph.D. thesis, Université Catholique De Louvain. ://perso.uclouvain.be/paul.vandooren/ThesisHo.pdf

    2008

  4. [12]

    Hou, L.; Chu, D.; and Liao, L. Z. 2024. Convergence of a Fast Hierarchical Alternating Least Squares Algorithm for Nonnegative Matrix Factorization. IEEE Transactions on Knowledge and Data Engineering 36(1): 77--89. doi:10.1109/TKDE.2023.3279369

    2024

  5. [13]

    Lam, E. Y. 2008. Non-negative Matrix Factorization for Images with Laplacian Noise. In 2008 IEEE Asia Pacific Conference on Circuits and Systems, 798--801. IEEE. doi:10.1109/APCCAS.2008.4746143

    2008

  6. [14]

    D.; and Seung, H

    Lee, D. D.; and Seung, H. S. 1999. Learning the parts of objects by non-negative matrix factorization. Nature 401(6755): 788--791. doi:10.1038/44565

    1999 doi

  7. [15]

    Paatero, P.; and Tapper, U. 1994. Positive Matrix Factorization: A Non-negative Factor Model with Optimal Utilization of Error Estimates of Data Values. Environmetrics 5(2): 111--126. doi:10.1002/env.3170050203

    1994 doi

  8. [16]

    Wang, C.-Y.; Liu, J.-X.; Yu, N.; and Zheng, C.-H. 2019. Sparse Graph Regularization Non-Negative Matrix Factorization Based on Huber Loss Model for Cancer Data Analysis. Frontiers in Genetics Volume 10 - 2019. ISSN 1664-8021. doi:10.3389/fgene.2019.01054. ://www.frontiersin.or...

    2019

Pith tools

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