{"id":"39100392-6794-4a62-b4a0-cfefb63c93ef","arxiv_id":"1908.06497","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A non-monotone spectral projected gradient method with a Cholesky shortcut is shown to be competitive with existing gradient projection methods on synthetic positive semidefinite Procrustes problems.","lead":"This paper proposes a spectral projected gradient algorithm for solving a least squares problem over the set of positive semidefinite matrices. It combines known acceleration techniques and compares its implementation against three existing methods on synthetic test problems.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The reported XErr is the last-step norm, not a solution error: the stopping criterion forces XErr below tolerance, so the numerical claims do not establish convergence; use a projected-gradient stationarity measure.","rationale":"The paper's theoretical core is sound: Algorithm 1 is correctly derived as a special case of the Francisco et al. non-monotone framework (Proposition 2), and the Cholesky shortcut is equivalent to the projection when the symmetric part is positive definite, so the global convergence result is inherited. The central weakness is empirical, and it is precisely the stopping criterion. The paper defines XErr as the distance between the final and penultimate iterates, which is the same quantity used in the termination test. Therefore the small XErr values reported in every table are not evidence of convergence; they are a consequence of the stopping rule. Meanwhile, the true global errors are large and often comparable across methods, and OptPSDP's final objective values on ill-conditioned instances are orders of magnitude worse than FGM's even though both report similar XErr. This means the comparison of CPU time and iterations is potentially comparing different stopping points, not different speeds to the same accuracy. The reader's weakest assumption identified the same risk; the present analysis sharpens it by showing that XErr is not merely a weak proxy but is tautologically bounded by the tolerance. The appropriate response is to retain the CONDITIONAL verdict: the algorithm and convergence proof are not invalidated, but the numerical claims must be re-run with a valid stationarity measure and with variability information before they can be accepted.","tokens_in":11314,"tokens_out":7228,"duration_ms":75742,"concrete_test":"Rerun all experiments in Tables 1-4 replacing the stopping rule ||X_k - X_{k-1}|| <= epsilon with a projected-gradient stationarity residual, e.g., ||X_k - pi(X_k - grad F(X_k))||_F <= epsilon (equivalently, the KKT residual for the PSD cone), and record true error ||X* - X_hat||_F and Fval. If OptPSDP's Fval and Global Error become comparable to FGM/ParTan under this criterion, the numerical claim survives; if OptPSDP stops with Fval orders of magnitude larger, the claim should be revised. Additionally, report standard deviations or performance profiles over the 50 instances, since only averages are currently given.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing weakness is in the Section 4 evaluation protocol. Algorithm 1 terminates when ||X_k - X_{k-1}||_F <= epsilon (Algorithm 1, line 1), and the paper defines XErr = ||X_hat - X_k||_F where X_k is the penultimate iterate. Thus XErr is exactly the last step norm and is guaranteed to be <= epsilon by the stopping rule; it is not an estimate of distance to a solution. The tables report XErr ~1e-5 for every method, which is tautological. The true errors (Global Error, ||X* - X_hat||_F) are large (e.g., about 17 in E1/E5, about 0.26 in E8, about 43 in E10) and often similar across methods, and in ill-conditioned cases OptPSDP stops with Fval orders of magnitude above FGM (e.g., Table 3 E10: 9.7e-3 vs 6.86e-6; E6: 2.4e-3 vs 5.1e-6) while still reporting XErr ~1e-6. This shows the step-size stopping rule can halt OptPSDP far from stationarity, so the paper's claim that all methods reach convergence, and the CPU/iteration comparisons, are not supported as stated. The numerical competitiveness claim is load-bearing for the paper's contribution and needs re-testing with a stationarity-based stopping criterion.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":11658,"tokens_out":5963,"duration_ms":56474,"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":[{"comment":"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":"Section 4 and Algorithm 1, line 1"},{"comment":"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":"Section 3.1, Algorithm 1 line 2"},{"comment":"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.","section":"Section 4, experimental design"}],"minor_comments":[{"comment":"The directional derivative limit should be t→0, not t→∞.","section":"Section 2, equation (2)"},{"comment":"The stopping condition contains an unmatched parenthesis: '||X_k - X_{k-1})||_F' should be '||X_k - X_{k-1}||_F'.","section":"Algorithm 1, line 1"},{"comment":"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.","section":"Section 4"},{"comment":"The gradient notation is inconsistent: Algorithm 1 uses 'F(X_k)[...]' where the directional derivative ∇F(X_k)[...] is meant; please use ∇F consistently.","section":"Throughout"},{"comment":"The domain of X is written as R^{n×m}; it should be R^{n×n}.","section":"Problem (1)"}],"recommendation":"major_revision","confidential_remarks":"The numerical validation issue is the main reason for major revision; if the author can rerun the experiments with a stationarity-based stopping rule and correct the line search in the pseudocode, the paper could be suitable for publication. No concerns about novelty or attribution beyond the appropriate citation to Francisco et al."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat 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.\n\nThe 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.\n\nWho 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.\n\nRecommendation: 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.","headline":"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.","tokens_in":12117,"tokens_out":3472,"would_cite":false,"duration_ms":34786,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65K05","90C25","90C30","15A24"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["positive semidefinite Procrustes problem","spectral projected gradient","non-monotone line search","Cholesky factorization","matrix projection","global convergence","least squares with semidefinite constraint"],"falsifier":"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.","tokens_in":11034,"feed_emoji":"🧮","tokens_out":10749,"duration_ms":94946,"temperature":0.7,"pith_summary":"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.","feed_headline":"Spectral gradient + Cholesky shortcut solves PSD Procrustes fast","feed_subtitle":"Combines spectral step sizes with a non-monotone search to skip costly eigen-decompositions; fastest on square systems.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the two-point spectral step-size formulas used to accelerate the projection step.","marker":"[3]"},{"why":"Provides the globally convergent non-monotone algorithm from which the paper's convergence theorem follows.","marker":"[7]"},{"why":"Defines the FGM gradient projection method for the same problem and supplies the main numerical competitor.","marker":"[8]"},{"why":"Supplies the non-monotone line-search acceptance rule and the convex combination update used to regulate the step size.","marker":"[18]"},{"why":"Gives the projection formula onto $S_+(n)$ and the convex-cone properties used in Proposition 1 and existence guarantees.","marker":"[9]"},{"why":"Introduces the parallel-tangent method used as a numerical competitor.","marker":"[1]"}],"fun_headline_variants":["Cholesky shortcut makes PSD Procrustes solver faster","Spectral gradient method with global convergence for PSD Procrustes","Non-monotone search accelerates PSD Procrustes solution","Skipping eigen-decompositions speeds PSD Procrustes"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Cholesky shortcut makes PSD Procrustes solver faster","Spectral gradient method with global convergence for PSD Procrustes","Non-monotone search accelerates PSD Procrustes solution","Skipping eigen-decompositions speeds PSD Procrustes"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000772,"raw_usage":{"total_tokens":3392,"prompt_tokens":892,"completion_tokens":2500,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":508,"completion_tokens_details":{"reasoning_tokens":2423}},"tokens_in":508,"tokens_out":2500,"duration_ms":17381,"temperature":1.0,"reasoning_tokens":2423,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:42:06.829129+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Two-point step size g radi- ent methods","cited_arxiv_id":null,"evidence_quote":"Supplies the two-point spectral step-size formulas used to accelerate the projection step."},{"cited_title":"Non- monotone algorithm for minimization on arbitrary domains with appli- cations to large-scale orthogonal procrustes problem","cited_arxiv_id":null,"evidence_quote":"Provides the globally convergent non-monotone algorithm from which the paper's convergence theorem follows."},{"cited_title":"A semi-analytical approach for the positive semidefinite procrustes problem","cited_arxiv_id":null,"evidence_quote":"Defines the FGM gradient projection method for the same problem and supplies the main numerical competitor."},{"cited_title":"A nonmonotone line search technique and its application to unconstrained optimization","cited_arxiv_id":null,"evidence_quote":"Supplies the non-monotone line-search acceptance rule and the convex combination update used to regulate the step size."},{"cited_title":"Computing a nearest symmetric positive semidefi - nite matrix","cited_arxiv_id":null,"evidence_quote":"Gives the projection formula onto $S_+(n)$ and the convex-cone properties used in Proposition 1 and existence guarantees."},{"cited_title":"A constrained procrus tes problem","cited_arxiv_id":null,"evidence_quote":"Introduces the parallel-tangent method used as a numerical competitor."}],"review_version":1}