Pith. sign in

REVIEW 2 major objections 3 minor 44 references

A Support-Set Algorithm for Optimization Problems with Nonnegative and Orthogonal Constraints

T0 review · 2 major / 3 minor · reviewed 2026-08-03 · deepseek-v4-flash

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

Pith's one-line read This paper introduces a feasible support-set algorithm for nonnegative and orthogonal optimization problems, proving global convergence to a first-order stationary point with O(ε⁻²) iteration complexity.

desk verdict A genuinely new feasible support-set method with strong numerics, but the convergence theory currently rests on an unproven descent inequality that needs an ambient-smoothness fix. read the letter →

arxiv 2511.03443 v2 pith:PNVZ3MEK submitted 2025-11-05 math.OC cs.LGstat.ML

Lei Wang , Xin Liu , Xiaojun Chen This is my paper · ORCID
classification math.OCcs.LGstat.ML MSC 90C3090C2665K05
keywords nonnegativeorthogonalconstraintsStiefelmanifoldsupport-setalgorithmproximallinearizationfirst-orderstationarypointiterationcomplexityclosed-formsolutionPCA
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

The paper tackles optimization over matrices that are simultaneously nonnegative and orthogonal, a feasible set with a striking sparsity structure: each row has at most one nonzero entry. The authors show that minimizing a proximal linearization of the objective over a fixed support set admits an explicit closed-form solution, enabling an algorithm that keeps every iterate feasible. They prove that the support-set algorithm globally converges to a first-order stationary point and reaches an ε-approximate stationary point in O(ε⁻²) iterations, the first such complexity guarantee for these problems. A sympathetic reader should care because this turns a seemingly intractable combinatorial constraint into a tractable, provably convergent method with strong practical speedups.

What carries the argument

The support set S, a sign matrix encoding the allowed nonzero positions, is the central object. For a fixed S, the subproblem min{⟨X, ∇f(Z)−ηZ⟩ : X ∈ O₊^{n,p}, supp(X)⊆supp(S)} separates by columns and has the closed-form solution in Proposition 3.2, expressed through W = max{0, (ηZ−∇f(Z))⊙S}. The update scheme for support sets—assigning zero rows to the column of most negative gradient and moving small entries to the best alternative column—is what guarantees the stationarity condition for zero rows and drives descent. The proximal parameter η > L, where L is the Lipschitz constant of ∇f, is what makes the sufficient-descent lemmas hold.

What would settle it

Run Algorithm 1 on a smooth function with known Lipschitz constant L and deliberately set η < L (or use the adaptive BB stepsize where η_k dips below L). If the iterates fail to converge to a point satisfying conditions (2.1)-(2.2), or if the sufficient-descent inequality (Lemma 5.1) is violated numerically, then the core claim would be refuted. A direct check is to monitor whether ∥Y_k ⊙ gradf(Y_k)∥_F and the zero-row negativity max{0,−[∇f(Y_k)]_{i,j}} both tend to zero along a convergent subsequence; any counterexample would falsify Theorem 5.4.

Watch

Extended reading notes

Core claim

The central claim is that optimization with nonnegative and orthogonal constraints (problem (O+)) can be solved by a strictly feasible algorithm that dynamically updates the support set of the iterate. Because any feasible n×p matrix has at most one nonzero per row, fixing the support reduces the problem to independent column-normalization subproblems. The paper proves that the proximal-linearization subproblem on a fixed support has a closed-form global minimizer: set W = max{0, (ηZ − ∇f(Z))⊙S}, normalize each nonzero column, and fill zero columns with unit vectors chosen by a minimal-index rule. The algorithm alternately minimizes within the current support and, when progress stalls, reloc

Load-bearing premise

The whole convergence proof rests on Assumption 1—that f is continuously differentiable with a Euclidean gradient that is L-Lipschitz on the feasible set—and on choosing the proximal parameter η strictly larger than L; without this smoothness or that parameter choice, the descent lemmas and all convergence theorems collapse.

Editorial extensions

If this is right

  • If the convergence theorem is correct, the support-set algorithm is the first feasible method for problem (O+) with provable global convergence to a first-order stationary point, replacing infeasible penalty approaches.
  • The O(ε⁻²) iteration complexity directly gives a worst-case guarantee that practitioners can rely on, something previously unavailable for nonnegative orthogonal constraints.
  • Each iteration costs only O(n + r_k p) with at most n nonzero entries, compared to O(np²) projections for existing methods, so the algorithm scales to large n and p.
  • Finite support identification means that, when stationary points have no zero rows, the algorithm eventually locks onto the correct support pattern, enabling faster local convergence.
  • Closed-form subproblems make the method easy to implement and to embed in larger pipelines for nonnegative PCA, spectral clustering, ONMF, and community detection.

Reading between the lines

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

  • The theoretical analysis fixes η > L, but the numerical implementation uses an adaptive Barzilai-Borwein η_k; extending the convergence theory to adaptive stepsizes would close a gap between theory and practice.
  • The support-set viewpoint could inspire active-set or support-exploration methods for other structured nonconvex sets, such as the oblique manifold or the doubly stochastic matrices, where similar sparsity arguments may apply.
  • A natural next step is a second-order variant that uses curvature information within the fixed support, which the authors explicitly mention as future work; the closed-form subproblem structure may make Hessian-free quasi-Newton updates particularly cheap.
  • For boundary cases p = 1 and p = n, the feasible set changes character (sphere and permutation matrices respectively), and the present analysis explicitly restricts to 1 < p < n; adapting the algorithm to those extremes is a testable extension.
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

2 major / 3 minor

Summary. The paper proposes Support-Set, a feasible algorithm for minimizing a smooth function over the nonnegative Stiefel manifold O^{n,p}_+ (1<p<n). Key observations are that each feasible matrix has at most one nonzero entry per row and that, with a fixed support set, the proximal-linearization subproblem admits a closed-form solution. The algorithm updates the support set by relocating small nonzero entries or activating zero rows while maintaining feasibility. The main theoretical results assert that every accumulation point is first-order stationary (Theorem 5.4) and that an ε-approximate first-order stationary point is reached in O(ε^{-2}) iterations (Theorem 5.5), together with finite support identification (Theorem 5.6). Numerical experiments on nonnegative PCA, clustering, and community detection report substantial speedups over EP4Orth+ and SEPPG0/SEPPG+.

Significance. The algorithmic idea is attractive and the claimed guarantees, if established, would be a meaningful contribution: a feasible method with per-iteration cost O(n+r_k p) and global first-order convergence for this combinatorially constrained problem fills a real gap. The closed-form subproblem solution and the sparse-gradient exploitation are well conceived. The O(ε^{-2}) complexity bound appears new for this class of constraints. The numerical experiments are extensive and use external benchmarks, although the authors do not provide their own code. The main concern is a load-bearing gap in the descent lemma: as written, Assumption 1 does not support the key inequality. This is repairable and does not invalidate the algorithmic framework.

major comments (2)
  1. [§3, Lemma 3.1, inequality (3.1)] The proof of the descent inequality uses the standard chord-integral argument along Z+t(X-Z). However, for X,Z ∈ O^{n,p}_+, this chord is generally not contained in O^{n,p} (or O^{n,p}_+), so the assumed Lipschitz continuity of ∇f over O^{n,p} does not control the integrand. Consequently (3.1) is not established under Assumption 1. This gap propagates to Lemma 5.1, Corollary 5.2, Proposition 5.3, and Theorems 5.4–5.5. Please either strengthen Assumption 1 to ambient Lipschitz continuity of ∇f (e.g., on a convex neighborhood of O^{n,p} or on R^{n×p}) or provide a manifold-consistent proof with an appropriate modified inequality and constant. This is a load-bearing issue, not a cosmetic one.
  2. [§6.1, Implementation Details] The numerical implementation replaces the fixed proximal parameter η > L by the adaptive Barzilai-Borwein step η_k defined in Section 6.1. All convergence results (Theorems 5.4–5.5) are proven for Algorithm 1 with fixed η > L; the implemented variant is therefore not covered by the stated theory. The authors call this an empirical acceleration, but the distinction should be explicit. If the BB variant is to be presented as the practical form of the algorithm, either a convergence analysis for it should be supplied or the theoretical claims should be confined to the fixed-η algorithm.
minor comments (3)
  1. [§6.1, termination criterion] The stopping criterion ∥X_{k+1}-X_k∥_F ≤ 1e-6 does not directly upper-bound the quantities in Definition 2.2, since the theory bounds stationarity violations by ∥Y_k-X_k∥_F and ∥X_{k+1}-Y_k∥_F. The practical stopping rule is reasonable, but its relation to ε-approximate stationarity should be stated.
  2. [§5.4, examples (i)–(ii)] The two examples illustrating stationary points without zero rows are asserted without proof. Adding a one-line verification that every row of ∇f(X) has a strictly negative entry would make the paragraph self-contained.
  3. [Algorithm 1, lines 12–13] The condition '[Y_k]_{u^{(t)}, w^{(t)}} = 1' is used to skip relocation; for readability, clarify that this occurs only when the row is already a unit vector, and that the subsequent inequality (4.11) still applies in this case.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the convergence and complexity theorems are proved from Assumption 1 and the algorithm's update rules; no fitted quantity or self-citation is doing the work.

full rationale

The derivation is self-contained in the relevant sense. Assumption 1 gives L-Lipschitz continuity of the Euclidean gradient on the feasible manifold; Proposition 3.2 explicitly solves the fixed-support proximal-linearization subproblem (3.5) by columnwise normalization using the support structure; and Lemma 5.1, Corollary 5.2, Proposition 5.3, Theorem 5.4, and Theorem 5.5 chain through algebraic inequalities based on that closed form and on the algorithmic definitions of Y_k and the support-update rule (4.1)-(4.12). The O(epsilon^{-2}) iteration complexity follows by summing the descent inequality and bounding the stationarity measure by consecutive-iterate distances; it is not imported from a prior result and no fitted constant is later renamed as a prediction. Numerical comparisons use external benchmarks and fixed published parameters for EP4Orth+, SEPPG0, and SEPPG+, and the synthetic nonnegative PCA example uses a constructed global minimizer only as an evaluation target, not as an input to the theory. The self-citations [26]-[30] appear as background or as inspiration for a numerical Barzilai-Borwein stepsize in Section 6.1; they do not carry the convergence proof. I therefore find no step that is equivalent to its inputs by construction. A separate correctness caveat, not a circularity: Lemma 3.1's inequality (3.1) is asserted from manifold-restricted Lipschitz smoothness, although the standard proof integrates along the chord X-Z, which is generally outside O^{n,p}; if the argument requires ambient/segment smoothness, Assumption 1 should be strengthened. This is a proof-gap concern, not a definitional or fit circularity, so it does not affect the score.

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

The central claim rests on the stated smoothness/compactness assumptions and on algorithm hyperparameters that are not fitted to data. No new physical or mathematical entities are introduced.

free parameters (3)
  • eta (proximal parameter) = fixed eta > L in theory; BB-adaptive eta_k in experiments
    Needed to make the proximal linearization a descent model. The theory requires eta > L, while the experiments set it adaptively, which is outside the proved regime.
  • delta (small-row threshold) = 0.1 in experiments
    Controls which rows are considered for support relocation. Convergence holds for any delta in (0,1), but the value affects practical behavior.
  • theta (support-update threshold) = 1e-2 in experiments
    Determines when the support set is changed. Convergence holds for any theta > 0, but the value affects how often support updates occur.
assumptions (2)
  • domain assumption Assumption 1: f is continuously differentiable and nabla f is L-Lipschitz over O^{n,p}
    Used in Lemmas 3.1 and 5.1, Proposition 5.3, and all convergence theorems; without this smoothness there is no descent or stationarity bound.
  • standard math O^{n,p}_+ is compact and f is bounded on it
    Used in Corollary 5.2 and Theorem 5.5 to make the sum of squared consecutive distances converge finite.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Support-Set Algorithm for Optimization Problems with Nonnegative and Orthogonal Constraints." pith.science (2026). https://pith.science/paper/PNVZ3MEK

@misc{pith2026251103443,
  author       = {Pith},
  title        = {Pith review of: A Support-Set Algorithm for Optimization Problems with Nonnegative and Orthogonal Constraints},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PNVZ3MEK}},
  note         = {Machine review of arXiv:2511.03443}
}
abstract

In this paper, we investigate optimization problems with nonnegative and orthogonal constraints, where any feasible matrix of size $n \times p$ exhibits a sparsity pattern such that each row accommodates at most one nonzero entry. Our analysis demonstrates that, by fixing the support set, the global solution of the minimization subproblem for the proximal linearization of the objective function can be computed in closed form with at most $n$ nonzero entries. Exploiting this structural property offers a powerful avenue for dramatically enhancing computational efficiency. Guided by this insight, we propose a support-set algorithm preserving strictly the feasibility of iterates. A central ingredient is a strategically devised update scheme for support sets that adjusts the placement of nonzero entries. We establish the convergence of the support-set algorithm to a first-order stationary point, and show that its iteration complexity required to reach an $\epsilon$-approximate first-order stationary point is $O (\epsilon^{-2})$. Numerical results are strongly in favor of our algorithm in real-world applications, including nonnegative PCA, clustering, and community detection.

Figures

Figures reproduced from arXiv: 2511.03443 by the authors.

Figure 1
Figure 1. Numerical comparison of different algorithms for solving nonnegative PCA problems. [PITH_FULL_IMAGE:figures/full_fig_p019_1.png] view at source ↗
Figure 2
Figure 2. Numerical comparison of different algorithms for clustering. [PITH_FULL_IMAGE:figures/full_fig_p020_2.png] view at source ↗
Figure 3
Figure 3. Numerical comparison of different algorithms for community detection. [PITH_FULL_IMAGE:figures/full_fig_p021_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

44 extracted references · 4 linked inside Pith

  1. [1]

    Absil, R

    P.-A. Absil, R. Mahony, and R. Sepulchre.Optimization Algorithms on Matrix Manifolds. Prince- ton University Press, Princeton, 2008

    2008

  2. [2]

    Barzilai and J

    J. Barzilai and J. M. Borwein. Two-point step size gradient methods.IMA Journal of Numerical Analysis, 8(1):141–148, 1988

    1988

  3. [3]

    Boumal.An Introduction to Optimization on Smooth Manifolds

    N. Boumal.An Introduction to Optimization on Smooth Manifolds. Cambridge University Press, Cambridge, 2023

    2023

  4. [4]

    Boutsidis, P

    C. Boutsidis, P. Drineas, and M. W. Mahoney. Unsupervised feature selection for thek-means clustering problem.Advances in Neural Information Processing Systems, 22:1–9, 2009

    2009

  5. [5]

    D. Cai, Q. Mei, J. Han, and C. Zhai. Modeling hidden topics on document manifold. InProceedings of the 17th ACM Conference on Information and Knowledge Management, pages 911–920, 2008

    2008

  6. [6]

    Carson, D

    T. Carson, D. G. Mixon, S. Villar, and R. Ward. Manifold optimization for k-means clustering. InProceedings of the 2017 International Conference on Sampling Theory and Applications, pages 73–77. IEEE, 2017

    2017

  7. [7]

    X. Chen, Y. He, and Z. Zhang. Tight error bounds for the sign-constrained Stiefel manifold. SIAM Journal on Optimization, 35(1):302–329, 2025

    2025

  8. [8]

    C. Ding, T. Li, W. Peng, and H. Park. Orthogonal nonnegative matrix t-factorizations for cluster- ing. InProceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 126–135, 2006

    2006

Show all 44 references
  1. [9]

    Ding and K.-C

    K. Ding and K.-C. Toh. On exploration of an interior mirror descent flow for stochastic nonconvex constrained problem.arXiv:2507.15264, 2025

    2025 arXiv

  2. [10]

    Hiriart-Urruty and A

    J.-B. Hiriart-Urruty and A. Seeger. A variational approach to copositive matrices.SIAM Review, 52(4):593–629, 2010

    2010

  3. [11]

    Jiang, Y.-F

    B. Jiang, Y.-F. Liu, and Z. Wen.L p-norm regularization algorithms for optimization over permu- tation matrices.SIAM Journal on Optimization, 26(4):2284–2313, 2016. 22

    2016

  4. [12]

    Jiang, X

    B. Jiang, X. Meng, Z. Wen, and X. Chen. An exact penalty approach for optimization with nonnegative orthogonality constraints.Mathematical Programming, 198(1):855–897, 2023

    2023

  5. [13]

    Kuang, C

    D. Kuang, C. Ding, and H. Park. Symmetric nonnegative matrix factorization for graph clustering. InProceedings of the 2012 SIAM International Conference on Data Mining, pages 106–117. SIAM, 2012

    2012

  6. [14]

    E. L. Lawler. The quadratic assignment problem.Management Science, 9(4):586–599, 1963

    1963

  7. [15]

    B. Li, G. Zhou, and A. Cichocki. Two efficient algorithms for approximately orthogonal nonneg- ative matrix factorization.IEEE Signal Processing Letters, 22(7):843–846, 2014

    2014

  8. [16]

    Y. Li, D. Sun, and L. Zhang. Unsupervised feature selection via nonnegative orthogonal con- strained regularized minimization.arXiv:2403.16966, 2024

    2024 arXiv

  9. [17]

    Liu and N

    C. Liu and N. Boumal. Simple algorithms for optimization on Riemannian manifolds with con- straints.Applied Mathematics&Optimization, 82(3):949–981, 2020

    2020

  10. [18]

    D. Luo, C. Ding, H. Huang, and T. Li. Non-negative Laplacian embedding. InProceedings of the 9th IEEE International Conference on Data Mining, pages 337–346. IEEE, 2009

    2009

  11. [19]

    Montanari and E

    A. Montanari and E. Richard. Non-negative principal component analysis: Message passing algorithms and sharp asymptotics.IEEE Transactions on Information Theory, 62(3):1458–1484, 2015

    2015

  12. [20]

    Nocedal and S

    J. Nocedal and S. J. Wright.Numerical Optimization. Springer Science & Business Media, New York, 2006

    2006

  13. [21]

    Pan and M

    J. Pan and M. K. Ng. Orthogonal nonnegative matrix factorization by sparsity and nuclear norm optimization.SIAM Journal on Matrix Analysis and Applications, 39(2):856–875, 2018

    2018

  14. [22]

    Paul and Y

    S. Paul and Y. Chen. Orthogonal symmetric non-negative matrix factorization under the stochas- tic block model.Statistica Sinica, 35:1811–1834, 2025

    2025

  15. [23]

    Pompili, N

    F. Pompili, N. Gillis, P.-A. Absil, and F. Glineur. Two algorithms for orthogonal nonnegative matrix factorization with application to clustering.Neurocomputing, 141:15–25, 2014

    2014

  16. [24]

    Povh and F

    J. Povh and F. Rendl. A copositive programming approach to graph partitioning.SIAM Journal on Optimization, 18(1):223–241, 2007

    2007

  17. [25]

    Y. Qian, S. Pan, and L. Xiao. Error bound and exact penalty method for optimization problems with nonnegative orthogonal constraint.IMA Journal of Numerical Analysis, 44(1):120–156, 2024

    2024

  18. [26]

    L. Wang, B. Gao, and X. Liu. Multipliers correction methods for optimization problems over the Stiefel manifold.CSIAM Transactions on Applied Mathematics, 2(3):508–531, 2021

    2021

  19. [27]

    Wang and X

    L. Wang and X. Liu. Decentralized optimization over the Stiefel manifold by an approximate augmented Lagrangian function.IEEE Transactions on Signal Processing, 70:3029–3041, 2022

    2022

  20. [28]

    L. Wang, X. Liu, and X. Chen. The distributionally robust optimization model of sparse principal component analysis.arXiv:2503.02494, 2025

    2025 arXiv

  21. [29]

    L. Wang, X. Liu, and Y. Zhang. A communication-efficient and privacy-aware distributed algo- rithm for sparse PCA.Computational Optimization and Applications, 85(3):1033–1072, 2023

    2023

  22. [30]

    L. Wang, X. Liu, and Y. Zhang. Seeking consensus on subspaces in federated principal component analysis.Journal of Optimization Theory and Applications, 203:529–561, 2024

    2024

  23. [31]

    Wang, T.-H

    S. Wang, T.-H. Chang, Y. Cui, and J.-S. Pang. Clustering by orthogonal NMF model and non- convex penalty optimization.IEEE Transactions on Signal Processing, 69:5273–5288, 2021. 23

    2021

  24. [32]

    Wen and W

    Z. Wen and W. Yin. A feasible method for optimization with orthogonality constraints.Mathe- matical Programming, 142(1):397–434, 2013

    2013

  25. [33]

    Xia and Y.-X

    Y. Xia and Y.-X. Yuan. A new linearization method for quadratic assignment problems.Opti- mization Methods and Software, 21(5):805–818, 2006

    2006

  26. [34]

    N. Xiao, T. Tang, S. Wang, and K.-C. Toh. An exact penalty approach for equality constrained optimization over a convex set.arXiv:2505.02495, 2025

    2025 arXiv

  27. [35]

    W. Xu, X. Liu, and Y. Gong. Document clustering based on non-negative matrix factoriza- tion. InProceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Informaion Retrieval, pages 267–273, 2003

    2003

  28. [36]

    Y. Yang, Y. Yang, H. T. Shen, Y. Zhang, X. Du, and X. Zhou. Discriminative nonnegative spectral clustering with out-of-sample extension.IEEE Transactions on Knowledge and Data Engineering, 25(8):1760–1771, 2012

    2012

  29. [37]

    Yang and E

    Z. Yang and E. Oja. Linear and nonlinear projective nonnegative matrix factorization.IEEE Transactions on Neural Networks, 21(5):734–749, 2010

    2010

  30. [38]

    Yoo and S

    J. Yoo and S. Choi. Orthogonal nonnegative matrix tri-factorization for co-clustering: Multi- plicative updates on Stiefel manifolds.Information Processing&Management, 46(5):559–570, 2010

    2010

  31. [39]

    Zass and A

    R. Zass and A. Shashua. Nonnegative sparse PCA.Advances in Neural Information Processing Systems, 19:1–7, 2006

    2006

  32. [40]

    Zhang, H

    J. Zhang, H. Liu, Z. Wen, and S. Zhang. A sparse completely positive relaxation of the modularity maximization for community detection.SIAM Journal on Scientific Computing, 40(5):A3091– A3120, 2018

    2018

  33. [41]

    Zhang, S

    K. Zhang, S. Zhang, J. Liu, J. Wang, and J. Zhang. Greedy orthogonal pivoting algorithm for non- negative matrix factorization. InProceedings of the 36th International Conference on Machine Learning, volume 97, pages 7493–7501. PMLR, 2019

    2019

  34. [42]

    Zhang, Q

    Y. Zhang, Q. Wang, D.-W. Gong, and X.-F. Song. Nonnegative Laplacian embedding guided subspace learning for unsupervised feature selection.Pattern Recognition, 93:337–352, 2019

    2019

  35. [43]

    Zhao and G

    Y. Zhao and G. Karypis. Empirical and theoretical comparisons of selected criterion functions for document clustering.Machine Learning, 55(3):311–331, 2004

    2004

  36. [44]

    Y. Zhou, C. Bao, C. Ding, and J. Zhu. A semismooth Newton based augmented Lagrangian method for nonsmooth optimization on matrix manifolds.Mathematical Programming, 201(1):1– 61, 2023. 24

    2023

Pith tools

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