A Spectral Gradient Projection Method for the Positive Semi-definite Procrustes Problem

Harry F. Oviedo

REVIEW 3 major objections 5 minor 18 references

A Spectral Gradient Projection Method for the Positive Semi-definite Procrustes Problem

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

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

Pith's one-line read A non-monotone spectral projected gradient method, using a Cholesky shortcut to skip eigen-decompositions, converges to a stationary solution of the positive semidefinite Procrustes problem and is numerically competitive with existing…

desk verdict The algorithm is a clean, honestly-derived special case of an existing method, but the numerical evidence is undermined by a tautological stopping criterion; the convergence theory holds, the experiments do not. read the letter →

arxiv 1908.06497 v1 pith:VUIRVMCR submitted 2019-08-18 math.NA cs.NA

Harry F. Oviedo This is my paper · ORCID

classification math.NAcs.NA MSC 65K0590C2590C3015A24

keywords positivesemidefiniteProcrustesproblemspectralprojectedgradientnon-monotonelinesearchCholeskyfactorizationmatrixprojectionglobalconvergenceleastsquareswithconstraint

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 addresses the positive semidefinite Procrustes problem: find a symmetric positive semidefinite matrix $X$ minimizing $\tfrac{1}{2}\|XA-B\|_F^2$, a least-squares problem over the PSD cone that appears in structure analysis, signal processing, and correlation-matrix estimation. It proposes OptPSDP, a projected gradient method whose step uses a spectral two-point step size regulated by a non-monotone line-search acceptance rule; when the trial point's symmetric part is already positive definite, a Cholesky factorization replaces the expensive eigenvalue decomposition behind the projection. The paper proves that every accumulation point of the generated sequence is a stationary point of the problem, by recognizing the update as a special case of a known globally convergent non-monotone scheme. In synthetic tests with known zero-optimal solutions, OptPSDP is competitive with existing gradient projection methods, and it is usually the fastest in CPU time when $A$ is square.

What carries the argument

The engine is the projected-gradient curve $Z(\tau)=\pi(X-\tau\nabla F(X))$ on the cone $S_+(n)$, together with the explicit projection formula $\pi(X)=V\max(\Sigma,0)V^\top$ applied to the symmetric part of $X$. The acceleration comes from the spectral two-point step-size formulas based on the most recent displacement and gradient difference, used in absolute value, and from a non-monotone acceptance rule that compares the objective at a trial point with a convex combination $C_k$ of recent function values rather than with the previous value alone. The proof machinery is Proposition 2: minimizing the projected-gradient subproblem is equivalent to minimizing the quadratic model $Q_k(X)=\operatorname{Tr}[\nabla F(X_k)^\top(X-X_k)] + \frac{1}{2\tau}\|X-X_k\|_F^2$ over $S_+(n)$, which embeds the method in a known globally convergent non-monotone algorithm. The practical shortcut is Cholesky: when the symmetric part of the trial point is positive definite, its projection is itself, so an eigenvalue decomposition can be replaced by a cheaper triangular factorization.

What would settle it

Run OptPSDP on a problem where $A$ and $B$ are independent random matrices, so no $X\in S_+(n)$ makes $XA=B$, and compare the final objective value with a high-accuracy solution of the convex problem; if the algorithm terminates with $\|X_{k+1}-X_k\|\le\epsilon$ but an objective value far from the true minimum, the numerical claims about finding the solution are falsified. At the theoretical level, a cycle with $\gamma$ close to 1 that violates every accumulation point being stationary would falsify Theorem 1.

Watch

Extended reading notes

Core claim

This paper establishes that the positive semidefinite Procrustes problem can be solved by a non-monotone spectral projected gradient iteration with a global convergence guarantee, while avoiding unnecessary spectral decompositions. The update takes $Y_k = X_k - \tau_k \nabla F(X_k)$, sets $X_{k+1}$ to the projection of $Y_k$ onto $S_+(n)$, computed as $V\max(\Sigma,0)V^\top$ where $V\Sigma V^\top$ is the spectral decomposition of the symmetric part of $Y_k$, and accepts $\tau_k$ through a non-monotone Armijo-type condition. When the symmetric part of $Y_k$ is positive definite, the projection is the identity, so a Cholesky factorization substitutes for the spectral decomposition. The paper proves that, for the non-monotone parameter $\gamma<1$, every accumulation point of the sequence is stationary, and reports numerical experiments where OptPSDP reaches the stopping tolerance with competitive iteration counts and, on square problems, often the lowest CPU time among the tested methods.

Load-bearing premise

The numerical claim rests on synthetic tests in which $B$ is set to $X^*A$ for a random positive semidefinite $X^*$, so the global optimum is known and has objective value zero; if zero-reachability or the stopping criterion based on successive iterates does not reflect a realistic Procrustes instance, the reported speeds and near-optimality may not transfer.

Editorial extensions

If this is right

For problems where iterates quickly become positive definite, the Cholesky shortcut replaces the dominant per-iteration cost, an eigen-decomposition, with a cheaper factorization, which is where the reported CPU-time gains come from.
Users can run the method without enforcing monotone decrease in the objective; the non-monotone acceptance rule plus step-size bounds is enough to guarantee convergence to a stationary point.
On square, well- and ill-conditioned instances in the reported tests, OptPSDP is often the fastest of the four compared methods in CPU time; on rectangular instances the parallel-tangent method is sometimes faster, while OptPSDP remains competitive.
Because the proof identifies a generic projected-gradient scheme, the same algorithmic recipe extends to any smooth objective over $S_+(n)$, a point the paper's Remark 1 states explicitly.

Reading between the lines

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

A natural stress test the paper does not perform is to run OptPSDP on instances where no exact positive semidefinite solution exists, so the optimal value is positive; on such problems the stopping rule $\|X_{k+1}-X_k\|\le\epsilon$ may terminate in a flat region far from the optimum, and reported XErr values of order $10^{-5}$ would need reinterpretation.
The Cholesky shortcut could be pushed further: for large $n$, replacing full Cholesky by an incomplete or block factorization when the symmetric part is only nearly positive definite may cut cost further while preserving feasibility, though the paper does not explore this.
The same spectral non-monotone projection template should transfer to other convex cones with cheap projections, such as the doubly nonnegative or second-order cones, because the convergence argument does not use Procrustes-specific structure beyond smoothness and convexity of the feasible set.
Since the constructed test problems all have a known zero-optimality solution, an informative comparison would report the true minimum distance for problems where the optimum is not zero, or use a first-order optimality residual rather than successive-difference stopping.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Briefly: this paper proposes OptPSDP, a non-monotone spectral projected gradient method for the PSD Procrustes problem, and the theory is fine because it is explicitly inherited from Francisco et al. The new bit is the Cholesky shortcut and the numerical study. The study, however, has a load-bearing flaw: XErr is defined as the distance from the final iterate to the penultimate one, and the stopping rule is exactly that this distance is below epsilon. So XErr approximately 1e-5 is guaranteed by construction and means nothing about solution accuracy. The honest metric, Global Error, is large (17, 43, etc.), which could partly be due to non-unique optima, but the Fval comparisons show OptPSDP stopping orders of magnitude above FGM on ill-conditioned cases (E6, E10). That is not 'all methods reach convergence.' The paper needs to be re-run with a projected-gradient norm or similar stationarity measure as the stopping criterion. Without that, the CPU-time and iteration comparisons are not trustworthy.

What it does well: Section 3.2 is transparent; Proposition 2 is correctly proved, and Theorem 1 is a valid inheritance of the Francisco et al. convergence result. The Cholesky shortcut is a reasonable heuristic, and the code is available, which is good practice. The writing is clear.

The flaws beyond the experiments are minor: no variance bars or performance profiles, only averages; the Cholesky trick is not analyzed theoretically; no comparison with SDPT3/QSDP despite mentioning them. These are minor compared to the stopping criterion issue.

Who is this for? Practitioners who want a simple, feasible, globally convergent method for SDP-constrained least squares. The algorithm is worth knowing about, but the numerical claims need a serious re-check before I would trust them.

Recommendation: send it to peer review, but with a strong request for a proper stationarity-based stopping test and re-evaluation of the experiments. The theory is not the problem.

Referee Report

3 major / 5 minor

Summary. This paper studies the positive semidefinite Procrustes problem (PSDP), min (1/2)||XA-B||_F^2 subject to X symmetric positive semidefinite. The author proposes Algorithm 1 (OptPSDP), a projected gradient method with the Zhang-Hager nonmonotone line search, Barzilai-Borwein step sizes, and a Cholesky-based test that skips the spectral projection when the symmetrized trial point is already positive definite. The convergence claim is that every accumulation point of the generated sequence is stationary, obtained by identifying the update as a special case of the nonmonotone quadratic-model algorithm of Francisco et al. Numerical experiments compare OptPSDP with Grad, FGM, and ParTan on synthetic problems with well- and ill-conditioned matrices A.

Significance. The method is simple, and the theoretical link to Francisco et al. is clearly presented; Proposition 2 is a correct and useful observation, and the Cholesky shortcut is a sensible practical heuristic. The availability of MATLAB code is a plus. The main weakness is that the numerical experiments do not validate the competitiveness claim as stated: the stopping criterion and the reported XErr are essentially the same quantity, and in several ill-conditioned cases OptPSDP stops at objective values orders of magnitude larger than FGM. If the experiments are redone with a proper stationarity measure, the method may still be competitive, but the evidence in the current manuscript is not sufficient.

major comments (3)

[Section 4 and Algorithm 1, line 1] The stopping criterion in Algorithm 1 is ||X_k - X_{k-1}||_F <= epsilon, and the text in Section 4 defines XErr = ||\hat X - X_k||_F with X_k the penultimate iterate. Consequently XErr is exactly the last step norm and is forced below epsilon by the stopping rule; it is not a measure of distance to a solution or of stationarity. The statements in Section 4 that 'all the methods reach convergence' because XErr is small are therefore unsupported. In Tables 2 and 3, OptPSDP stops with Fval much larger than FGM in several cases (e.g., Table 3 E10: 9.7e-3 vs 6.86e-6; Table 2 E6: 2.4e-3 vs 5.1e-6), so the CPU-time and iteration comparisons are made at different levels of objective accuracy. I recommend re-running all experiments with a stationarity-based stopping criterion, for example ||X_k - pi(X_k - grad F(X_k))||_F <= epsilon or a projected-gradient norm, and reporting Fval or distance to the optimal set as the primary quality measure.
[Section 3.1, Algorithm 1 line 2] The line search condition in Algorithm 1 reads 'while F(Z_k(τ)) > C_k + στ F(X_k)[Z_k(τ) - X_k]', but the derivation in equation (7) requires F(Z_k(τ)) <= C_k + σ <∇F(X_k), Z_k(τ) - X_k>. The algorithm as printed is missing the gradient symbol and contains an extra factor τ before the directional derivative. Since Theorem 1 is stated for Algorithm 1 and inherits convergence from Francisco et al. through condition (7), the pseudocode and the actual implementation must be corrected to match (7); otherwise the convergence guarantee does not apply to the method as written.
[Section 4, experimental design] The construction B = X*A with X* = π(\tilde X) means that whenever A is rank-deficient (all rectangular cases with m<n), the solution to F(X)=0 is not unique, so the reported 'Global Error' ||X* - \hat X||_F is not a meaningful measure of failure. For example, Global Errors around 17-48 in Tables 1-3 are compatible with Fval near zero for any matrix \hat X with \hat X A = X* A. The comparison should instead focus on Fval, on a projected-gradient optimality measure, or on distance to the set of global minimizers; the current tables do not separate the effect of the stopping criterion from the actual performance of the algorithms.

minor comments (5)

[Section 2, equation (2)] The directional derivative limit should be t→0, not t→∞.
[Algorithm 1, line 1] The stopping condition contains an unmatched parenthesis: '||X_k - X_{k-1})||_F' should be '||X_k - X_{k-1}||_F'.
[Section 4] The text mixes Spanish and English: 'Problema' appears repeatedly, 'demostraste' is used for 'demonstrate', and 'the methods that the methods that converge' is a duplicated phrase.
[Throughout] The gradient notation is inconsistent: Algorithm 1 uses 'F(X_k)[...]' where the directional derivative ∇F(X_k)[...] is meant; please use ∇F consistently.
[Problem (1)] The domain of X is written as R^{n×m}; it should be R^{n×n}.

Circularity Check

1 steps flagged · score 6.0 of 10

XErr is the stopping rule by definition, so the numerical convergence claim is tautological; the theoretical derivation is independent.

self definitional [Section 4, Algorithm 1 line 1 and the definition of XErr, Tables 1-4 and the paragraph after Table 3]
"while ||Xk − Xk−1)||F > ǫ do ... 'XErr', the average error || ˆX − Xk||F , and Xk penultimate point generated by each algorithm ... all the methods reach convergence, since all obtain small values of XErr."

Algorithm 1 terminates exactly when ||X_k − X_{k−1}||_F ≤ ε. The paper defines XErr = ||\hat{X} − X_k||_F, where X_k is the penultimate iterate and \hat{X} is the final iterate X_{k+1}. Thus XErr is the same last-step norm used in the stopping test and is automatically ≤ ε for every method. Claiming that 'all the methods reach convergence, since all obtain small values of XErr' is therefore circular: the reported error is the stopping criterion renamed, not an independent measure of distance to a solution. The independent columns (Fval, Global Error) show in ill-conditioned cases that OptPSDP can stop far from the minimizer, e.g., Table 3 E10: Fval 9.7e-3 and Global Error 43.58 while XErr is 1.04e-6.

full rationale

The theoretical core of the paper is not circular. Algorithm 1 is derived by showing in Proposition 2 that the projection step minimizes the quadratic model (10), which makes it a particular case of the non-monotone algorithm of Francisco et al. [7]; the convergence theorem is imported from that independent prior work, not from the authors' own results, and no fitted parameter is later relabeled as a prediction. The only circularity is in the numerical validation: the error metric XErr is defined as the norm of the difference between the final and penultimate iterates, which is exactly the quantity used in the termination test. Therefore the statement that all methods 'reach convergence' because XErr is small is true by construction and carries no evidential weight. Since the numerical comparison is one of the paper's main contributions, this is a load-bearing tautology, but it does not infect the derivation of the algorithm itself. Hence the overall score is 6, reflecting partial circularity in the experimental claims with an independent theoretical derivation.

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

The paper introduces no new free parameters: the step sizes are standard Barzilai-Borwein quantities, and the line search parameters (σ, η, γ, τmin, τmax) are chosen from standard practice. It postulates no new physical or mathematical entities. The axioms are mostly standard results in matrix analysis plus the assumption that the convergence framework of Francisco et al. carries over, which the paper proves in Proposition 2.

assumptions (4)

standard math The projection operator onto S+(n) is computed by spectral decomposition of the symmetric part, π(X) = V max(Σ,0) V^T.
Used in Section 2, Proposition 1, cited to Higham [9]. This is a classical result and is not a new axiom.
standard math The feasible set S+(n) is a closed convex cone, guaranteeing existence of a minimizer.
Stated in Section 1, cited to Higham [9].
domain assumption The convergence theory of Francisco et al. [7] applies verbatim to Algorithm 1.
Section 3.2 derives Algorithm 1 as a special case; the proof of the correspondence in Proposition 2 hinges on the identity between the projected gradient subproblem and the quadratic model.
ad hoc to paper The Cholesky factorization test correctly identifies when the projection is unnecessary.
Section 3.1, step 5: if the symmetric part of Yk is positive definite, it coincides with its projection. This is true mathematically, but the paper does not analyze the effect of this shortcut on the line search or on the iteration count.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Spectral Gradient Projection Method for the Positive Semi-definite Procrustes Problem." pith.science (2026). https://pith.science/paper/VUIRVMCR

@misc{pith2026190806497,
  author       = {Pith},
  title        = {Pith review of: A Spectral Gradient Projection Method for the Positive Semi-definite Procrustes Problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VUIRVMCR}},
  note         = {Machine review of arXiv:1908.06497}
}

read the original abstract

This paper addresses the positive semi-definite procrustes problem (PSDP). The PSDP corresponds to a least squares problem over the set of symmetric and semi-definite positive matrices. These kinds of problems appear in many applications such as structure analysis, signal processing, among others. A non-monotone spectral projected gradient algorithm is proposed to obtain a numerical solution for the PSDP. The proposed algorithm employs the Zhang and Hager's non-monotone technique in combination with the Barzilai and Borwein's step size to accelerate convergence. Some theoretical results are presented. Finally, numerical experiments are performed to demonstrate the effectiveness and efficiency of the proposed method, and comparisons are made with other state-of-the-art algorithms.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 16 canonical work pages

[1]

A constrained procrus tes problem

Lars-Erik Andersson and Tommy Elfving. A constrained procrus tes problem. SIAM Journal on Matrix Analysis and Applications , 18(1):124–139, 1997

work page 1997
[2]

Efficient Algorithms for Positive Semi-Definite Total Least Squares Problems, Minimum Rank Problem and Correlation Matrix Computation

Negin Bagherpour and Nezam Mahdavi-Amiri. Eﬃcient algorithms for positive semi-deﬁnite total least squares problems, minimum rank problem and correlation matrix computation. arXiv preprint arXiv:1407.3894, 2014

work page Pith review arXiv 2014
[3]

Two-point step size g radi- ent methods

Jonathan Barzilai and Jonathan M Borwein. Two-point step size g radi- ent methods. IMA journal of numerical analysis , 8(1):141–148, 1988

work page 1988
[4]

Nonlinear programming

Dimitri P Bertsekas. Nonlinear programming. Journal of the Operational Research Society, 48(3):334–334, 1997

1997
[5]

Optimal matrices describing linear systems

John E Brock. Optimal matrices describing linear systems. AIAA Jour- nal, 6(7):1292–1296, 1968

work page 1968
[6]

Projected barzilai-borwein me th- ods for large-scale box-constrained quadratic programming

Yu-Hong Dai and Roger Fletcher. Projected barzilai-borwein me th- ods for large-scale box-constrained quadratic programming. Numerische Mathematik, 100(1):21–47, 2005

work page 2005
[7]

Non- monotone algorithm for minimization on arbitrary domains with appli- cations to large-scale orthogonal procrustes problem

JB Francisco, FS Viloche Baz´ an, and M Weber Mendon¸ ca. Non- monotone algorithm for minimization on arbitrary domains with appli- cations to large-scale orthogonal procrustes problem. Applied Numerical Mathematics, 112:51–64, 2017. References 17

work page 2017
[8]

A semi-analytical approach for the positive semideﬁnite procrustes problem

Nicolas Gillis and Punit Sharma. A semi-analytical approach for the positive semideﬁnite procrustes problem. Linear Algebra and its Appli- cations, 540:112–137, 2018

work page 2018

Show all 18 references

[9]

Computing a nearest symmetric positive semideﬁ - nite matrix

Nicholas J Higham. Computing a nearest symmetric positive semideﬁ - nite matrix. Linear algebra and its applications , 103:103–118, 1988

1988
[10]

Least-squares solution of ax b= d over symmetric positive semideﬁnite matrices x

Anping Liao and Zhongzhi Bai. Least-squares solution of ax b= d over symmetric positive semideﬁnite matrices x. Journal of Computational Mathematics, pages 175–182, 2003

2003
[11]

Introductory lectures on convex programm ing volume i: Basic course

Yurii Nesterov. Introductory lectures on convex programm ing volume i: Basic course. Lecture notes, 3(4):5, 1998

1998
[12]

Numerical optimization

Jorge Nocedal and Stephen Wright. Numerical optimization . Springer Science & Business Media, 2006

2006
[13]

The barzilai and borwein gradient method for t he large scale unconstrained minimization problem

Marcos Raydan. The barzilai and borwein gradient method for t he large scale unconstrained minimization problem. SIAM Journal on Optimiza- tion, 7(1):26–33, 1997

1997
[14]

Approximation by a hermitian positive semideﬁnite toeplitz matrix

TJ Suﬀridge and TL Hayden. Approximation by a hermitian positive semideﬁnite toeplitz matrix. SIAM journal on matrix analysis and ap- plications, 14(3):721–734, 1993

1993
[15]

An inexact primal–dual path following algorithm for convex quadratic sdp

Kim-Chuan Toh. An inexact primal–dual path following algorithm for convex quadratic sdp. Mathematical programming, 112(1):221–254, 2008

2008
[16]

Sdpt3a matlab software package for semideﬁnite programming, version 1.3

Kim-Chuan Toh, Michael J Todd, and Reha H T¨ ut¨ unc¨ u. Sdpt3a matlab software package for semideﬁnite programming, version 1.3. Optimiza- tion methods and software , 11(1-4):545–581, 1999

1999
[17]

Least-squares solution of f= pg over positiv e semideﬁnite symmetric p

Keith G Woodgate. Least-squares solution of f= pg over positiv e semideﬁnite symmetric p. Linear algebra and its applications , 245:171– 190, 1996

1996
[18]

A nonmonotone line search technique and its application to unconstrained optimization

Hongchao Zhang and William W Hager. A nonmonotone line search technique and its application to unconstrained optimization. SIAM jour- nal on Optimization , 14(4):1043–1056, 2004

2004

Pith tools

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

[1] [1]

A constrained procrus tes problem

Lars-Erik Andersson and Tommy Elfving. A constrained procrus tes problem. SIAM Journal on Matrix Analysis and Applications , 18(1):124–139, 1997

work page 1997

[2] [2]

Efficient Algorithms for Positive Semi-Definite Total Least Squares Problems, Minimum Rank Problem and Correlation Matrix Computation

Negin Bagherpour and Nezam Mahdavi-Amiri. Eﬃcient algorithms for positive semi-deﬁnite total least squares problems, minimum rank problem and correlation matrix computation. arXiv preprint arXiv:1407.3894, 2014

work page Pith review arXiv 2014

[3] [3]

Two-point step size g radi- ent methods

Jonathan Barzilai and Jonathan M Borwein. Two-point step size g radi- ent methods. IMA journal of numerical analysis , 8(1):141–148, 1988

work page 1988

[4] [4]

Nonlinear programming

Dimitri P Bertsekas. Nonlinear programming. Journal of the Operational Research Society, 48(3):334–334, 1997

1997

[5] [5]

Optimal matrices describing linear systems

John E Brock. Optimal matrices describing linear systems. AIAA Jour- nal, 6(7):1292–1296, 1968

work page 1968

[6] [6]

Projected barzilai-borwein me th- ods for large-scale box-constrained quadratic programming

Yu-Hong Dai and Roger Fletcher. Projected barzilai-borwein me th- ods for large-scale box-constrained quadratic programming. Numerische Mathematik, 100(1):21–47, 2005

work page 2005

[7] [7]

Non- monotone algorithm for minimization on arbitrary domains with appli- cations to large-scale orthogonal procrustes problem

JB Francisco, FS Viloche Baz´ an, and M Weber Mendon¸ ca. Non- monotone algorithm for minimization on arbitrary domains with appli- cations to large-scale orthogonal procrustes problem. Applied Numerical Mathematics, 112:51–64, 2017. References 17

work page 2017

[8] [8]

A semi-analytical approach for the positive semideﬁnite procrustes problem

Nicolas Gillis and Punit Sharma. A semi-analytical approach for the positive semideﬁnite procrustes problem. Linear Algebra and its Appli- cations, 540:112–137, 2018

work page 2018