{"id":"2daa4bdc-66fe-4deb-a18b-dca77e39d298","arxiv_id":"1908.06016","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Galerkin and Petrov-Galerkin methods for linear matrix equations inherit the optimality properties known for linear systems, with new error bounds and a structure-preserving constraint.","lead":"This paper shows that Galerkin and Petrov-Galerkin projection methods preserve their error and residual minimization properties when applied to linear matrix equations such as Lyapunov and Sylvester equations. It adds new convergence bounds and a constrained-optimization idea to keep approximate solutions physically structured.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection to the central optimality theorem; Prop. 2.2 holds under its stated S-spd hypothesis.","rationale":"The reader's weakest assumption, the spd condition on S, is indeed the main hypothesis needed for the Galerkin error-minimization result. I agree that this condition is necessary and is not guaranteed for general multiterm equations. However, the paper states this hypothesis explicitly, both in Definition 2.1 and before Proposition 2.2, and it is not internally inconsistent to build a conditional optimality theorem on it. The proof of Proposition 2.2 is abbreviated but correct: after vectorization it is exactly the standard Galerkin optimality argument for a symmetric positive definite linear system, with the trial space range(W_k⊗V_k). I therefore do not see a load-bearing flaw in the central claim. The more concrete issues I noticed are peripheral. Equation (5.3) states the full normal equation S^*(F−S(V_kY_kW_k^T))=0, which is false for a reduced k×k unknown; the correct stationarity condition is the projected equation V_k^T S^*(F−S(V_kY_kW_k^T))W_k=0. This typo does not invalidate the preceding residual-minimization statement (5.2) or the constrained proposal (5.6), because those are formulated directly from the minimization problem. The numerical comparison in Section 4 contains a suspicious lower bound on ||x||_2 before equation (4.5), and the constant in (4.5) does not appear to follow from (3.1) and the stated bound; this affects the quantitative comparison with CG, not the optimality theorem. Proposition 3.2 is stated with a proof sketch rather than a full derivation, but its plausibility is supported by the integral representation and the cited result [45]. None of these secondary concerns changes the accept recommendation for the central claim.","tokens_in":15595,"tokens_out":20417,"duration_ms":189616,"concrete_test":"Re-derive Proposition 2.2 in vector form: verify that V_m = W_k⊗V_k and that the equation V_m^T S_l V_m vec(Y_k)=V_m^T S_l vec(X) is exactly the matrix Galerkin equation V_k^T R_k W_k=0. This one-page algebraic consistency check should pass, settling that the claimed optimality is an immediate consequence of the stated assumptions.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After checking the argument chain, I find no load-bearing objection to the paper's central claim. Proposition 2.2 follows directly from vectorization: the matrix Galerkin condition V_k^T R_k W_k=0 is exactly (W_k⊗V_k)^T r_k=0, and with S_l symmetric positive definite this is the normal equation for minimizing ||X−Z||_S over Z=V_k Y W_k^T. No hidden assumption beyond the explicitly stated spd condition and full-column-rank V_k,W_k is used. The acknowledged limitation after Remark 2.3 that spd of a multiterm operator is not always checkable narrows applicability but does not undermine the theorem. Secondary issues such as the sketched proof of Prop. 3.2 and an apparent typo in the normal equation (5.3), which should read V_k^T S^*(R)W_k=0 rather than S^*(R)=0, do not affect the central optimality result.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper treats projection methods for the linear matrix equation S(X)=Σ_{j=1}^ℓ A_j X B_j=F. It proves that when S is symmetric positive definite (spd) in the sense of Definition 2.1, the Galerkin condition V_k^T R_k W_k=0 on the residual is equivalent to minimizing the S-norm of the error over all X_k=V_k Y W_k^T (Proposition 2.2). The proof identifies the matrix Galerkin condition with the normal equations of the vectorized least-squares problem. The paper then derives a convergence estimate for the Sylvester equation with Krylov subspaces (Proposition 3.2), contrasts the matrix Galerkin iteration with CG applied to the Kronecker-form linear system, and proposes a semidefinite-constrained minimal-residual Petrov-Galerkin formulation for Lyapunov equations. Numerical experiments illustrate monotone error decrease, the comparison with CG, and the effect of the semidefinite constraint.","tokens_in":15750,"tokens_out":12340,"duration_ms":112927,"significance":"If it holds, the central optimality theorem is a clean and useful unification: it shows that for any spd linear matrix-equation operator the optimality of the Galerkin condition is independent of the approximation spaces, and it recovers the classical normal-equation argument in Kronecker form. The proof of Proposition 2.2 is transparent and requires no hidden assumptions beyond the stated spd hypothesis and full column rank of V_k, W_k. The paper also extends the Simoncini-Druskin Lyapunov bound to Sylvester equations and offers a novel constrained-minimization viewpoint for preserving solution semidefiniteness in Petrov-Galerkin methods. The authors explicitly acknowledge that spd-ness of a general multiterm operator cannot always be checked from the spectra of the coefficient matrices; this limitation restricts the applicability of Proposition 2.2 but does not invalidate it.","major_comments":[],"minor_comments":[{"comment":"The proof of Proposition 3.2 is only a reference to [45, Proposition 3.1] through the phrase 'same arguments', but the displayed constants, especially 2/(λmin(A)+λmin(B)) and the bracket terms, are not derived; since this is a new result, please give a complete proof or a detailed verification of the constants.","section":"Section 3, Proposition 3.2"},{"comment":"Equation (4.5) uses the lower bound ‖x‖₂ > 1/(λmax+λmin), which is not valid for all right-hand sides: for A=diag(1,100) and F=e2e2^T the exact solution has ‖X‖_F=1/200<1/101. The quoted constant 4(√κ̂+1)√κ̂ also appears inconsistent with (3.1); please correct the bound or clearly label the comparison as heuristic.","section":"Section 4, Equation (4.5)"},{"comment":"The normal-equation equivalence in (5.3) is missing the projection: it should read V_k^T S^*(F−S(V_k Y_k W_k^T)) W_k=0 (equivalently (W_k⊗V_k)^T S_l^T r_k=0), rather than S^*(F−S(...))=0.","section":"Section 5, Equation (5.3)"},{"comment":"The equality κ = λmax(A)/λmin(A) = λmax(A)/λmin(A) is ambiguous because the Kronecker matrix A = A⊗I+I⊗A has eigenvalues twice those of A; please use separate notation for the original and Kronecker matrices.","section":"Section 4, Equation (4.3)"},{"comment":"The acknowledged limitation that spd of a general multiterm operator cannot be checked from the spectra of the A_j, B_j should be reflected in the abstract and conclusions, where the phrase 'carry over' could otherwise be read as unconditional.","section":"Section 2, after Remark 2.3"},{"comment":"The expression (√κ̂_A+1)/√κ̂_A in Proposition 3.2 is ambiguous in the typeset text; if the intended factor is √(κ̂_A+1)/√κ̂_A, please typeset it with an unambiguous radical.","section":"Section 3, Proposition 3.2"}],"recommendation":"minor_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague — this paper does what it says: it shows that Galerkin and Petrov-Galerkin optimality properties carry over to linear matrix equations, and it proves the main point cleanly via Kronecker products. Proposition 2.2 is correct: if S is spd, the matrix Galerkin condition V_k^T R_k W_k = 0 is exactly the normal equation for minimizing ||X − Z||_S over Z = V_k Y W_k^T. I checked the vectorization chain and there is no hidden assumption beyond the stated spd condition and full-rank bases. The paper is also honest about what is new: the Lyapunov bound for Krylov subspaces was already in [45], and the paper says so. What is genuinely new is the general framing, the Sylvester analogue in Proposition 3.2, and the constrained semidefinite residual minimization idea in Section 5.1.\n\nThe Sylvester bound is plausible and the integral-representation argument is reasonable, but the proof of Proposition 3.2 is compressed — “by applying the same arguments” — and a referee should ask the authors to spell out the details. I do not think the claim is wrong, but it is not fully demonstrated as written. The constrained minimization proposal is a good idea but it is only tested on one small example with an expensive semidefinite solver, and the authors themselves acknowledge the cost. That part is a proposal, not a developed method, and the paper should present it as such. There are minor typos: the normal equation in (5.3) should be V_k^T S^*(R) W_k = 0, and I would double-check the constants around (4.5). None of this touches the central theorem.\n\nThe main limitation is the one the paper acknowledges: for a general multiterm operator, spd cannot always be checked from the spectra of A_j and B_j, and without spd the Galerkin optimality theorem does not apply. That is a real scope restriction, but it is stated plainly and does not undermine the result.\n\nCitation pattern is fine. Prior work in [27], [45], [30], and [52] is cited where relevant, and the new claims are appropriately modest. This is a solid, incremental-but-useful paper for people working on numerical methods for matrix equations. It is not a breakthrough and does not pretend to be. I would send it to a serious referee; with the proof of Proposition 3.2 expanded and the typos fixed, it is an acceptable contribution. For my own work I would cite it, at least for the unified optimality statement.","headline":"Clean, honest generalization of Galerkin/Petrov-Galerkin optimality to matrix equations; main theorem holds, new results are modest but real, and the paper deserves refereeing.","tokens_in":16258,"tokens_out":2303,"would_cite":true,"duration_ms":23873,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65F10","65F30","15A06"],"pacs":[],"model":"deepseek-v4-flash","headline":"For a symmetric positive definite matrix-equation operator, the Galerkin condition on the residual is exactly equivalent to minimizing the error in that operator's norm, whatever the approximation spaces.","keywords":["linear matrix equations","Galerkin methods","Petrov-Galerkin methods","Sylvester equation","Lyapunov equation","error minimization","Kronecker product","semidefinite constraint"],"falsifier":"For any proposed multiterm equation, explicitly compute the smallest eigenvalue of $S_{\\ell}=\\sum_j B_j^T\\otimes A_j$, for instance for the six-term stochastic Galerkin example used in the paper, and compare its sign with the observed convergence history of the Galerkin iterates: if $\\lambda_{\\min}(S_{\\ell})\\le 0$, the hypothesis of Proposition 2.2 fails, and an observed increase in the $S$-norm error in such a case would show that the unconditional optimality claim is false; if $\\lambda_{\\min}(S_{\\ell})>0$ and the error still increases, the proof itself would be contradicted.","tokens_in":15391,"feed_emoji":"🎯","tokens_out":10330,"duration_ms":93169,"temperature":0.7,"pith_summary":"Projection methods for linear systems gain their power from two standard optimality facts: when the coefficient matrix is symmetric positive definite, the Galerkin condition minimizes the error in the energy norm, and when it is not, a suitable Petrov-Galerkin condition minimizes the residual. This paper proves that both facts carry over to linear matrix equations of the form $S(X)=\\sum_{j=1}^{\\ell} A_j X B_j = F$, provided the operator $S$, equivalently the Kronecker matrix $\\sum_j B_j^T \\otimes A_j$, is symmetric positive definite. In that setting, the Galerkin reduced solution $X_k = V_k Y_k W_k^T$ is the best approximation to the true solution in the $S$-norm over the entire two-sided space, for any choice of $V_k$ and $W_k$. The paper also extends a known Lyapunov convergence bound to Sylvester equations with definite coefficients and shows that the matrix-oriented formulation has a better condition number than applying conjugate gradients to the equivalent Kronecker-vector system. For non-definite operators, it confirms residual minimization for Petrov-Galerkin methods and proposes a constrained version that preserves the semidefiniteness of Lyapunov solutions.","feed_headline":"Galerkin is optimal for definite linear matrix equations","feed_subtitle":"The error-minimizing property behind conjugate gradients carries to Sylvester, Lyapunov, and multiterm equations","key_machinery":"The load-bearing object is the linear operator $S: X \\mapsto \\sum_j A_j X B_j$ and its Kronecker representation $S_{\\ell}=\\sum_j B_j^T\\otimes A_j$, together with the induced inner product $\\langle X,Y\\rangle_S=\\operatorname{trace}(X^T S(Y))$. Under the spd assumption this inner product defines a true norm, and the Galerkin condition $V_k^T R_k W_k=0$ is precisely the normal equation of the least-squares projection onto $\\operatorname{range}(W_k\\otimes V_k)$ in that norm. The Petrov-Galerkin half is carried by choosing the test space $L_m=S_{\\ell}K_m$, which turns residual minimization into a small reduced least-squares problem; for Lyapunov equations this reduced problem is a generalized Sylvester equation, and the paper's proposed novelty is to add the semidefiniteness constraint $Y\\preceq 0$ to it.","core_discovery":"The paper's central discovery is that the classical optimality of projection methods survives the passage from vectors to matrices. For $S(X)=\\sum_j A_j X B_j$ with $S_{\\ell}=\\sum_j B_j^T\\otimes A_j$ symmetric positive definite, the Galerkin condition $V_k^T R_k W_k=0$ with $R_k=F-S(X_k)$ and $X_k=V_k Y_k W_k^T$ is exactly the stationarity condition for minimizing $\\|X-Z\\|_S$ over all $Z=V_k Y W_k^T$. Thus the Galerkin solution is the $S$-norm minimizer on the approximation set, and enlarging the spaces monotonically decreases the $S$-norm error, independently of how the spaces are constructed. For Sylvester equations $AX+XB=b_1b_2^T$ with $A,B$ symmetric positive definite, the paper derives an explicit exponential convergence bound in the Euclidean or Frobenius norm, with rates governed by shifted condition numbers $\\hat\\kappa_A$ and $\\hat\\kappa_B$. When $S$ is not spd, Galerkin optimality is lost, but the Petrov-Galerkin choice of test space $L_m=S_{\\ell}K_m$ does yield residual minimization; for Lyapunov equations, the paper shows that the unconstrained reduced least-squares problem can lose semidefiniteness and proposes imposing $Y\\preceq 0$ as an explicit constraint.","pith_inferences":["The error-minimization equivalence should extend to tensor-structured equations beyond matrices, whenever the corresponding operator is spd in the natural inner product; this is a direct generalization the paper does not pursue.","The improved condition number $\\hat\\kappa=(\\kappa+1)/2$ suggests a rule of thumb: for the same data, a matrix-oriented Galerkin solver can be expected to need about half as many iterations as CG on the Kronecker-vector system in the worst case; this is a consequence of the paper's bounds, not an empirical claim.","The constrained residual-minimization idea could be applied to other equations whose exact solutions are known to lie in a convex cone, such as Sylvester equations with sign-definite right-hand sides, where preserving the cone during the iteration would improve reliability.","Because $S_{\\ell}$'s definiteness cannot be read off from the spectra of the summands, a practical code could add a cheap numerical check of the smallest eigenvalue of a projected $S_{\\ell}$ before relying on Galerkin optimality."],"forward_implications":["Any Galerkin solver for a symmetric positive definite linear matrix equation inherits monotone convergence in the $S$-norm as the approximation spaces grow, regardless of how those spaces are chosen.","For Sylvester equations with spd coefficients and rank-one right-hand side, the new bound gives an explicit iteration count to reach a prescribed accuracy, with a convergence factor governed by shifted condition numbers.","Solving a Lyapunov equation in matrix form instead of applying conjugate gradients to the Kronecker-vector system improves the worst-case convergence factor from $\\kappa$ to $(\\kappa+1)/2$, since $\\hat\\kappa = \\kappa/2 + 1/2$.","For non-spd operators, Petrov-Galerkin methods remain optimal in residual norm, and the constrained formulation allows structural properties such as semidefiniteness to be preserved during the iteration."],"supporting_citations":[{"why":"Supplies the Galerkin/Petrov-Galerkin framework and the classical optimality facts for linear systems from which the matrix-equation versions are derived.","marker":"[40]"},{"why":"Provides the Lyapunov convergence bound that the paper generalizes to Sylvester equations in Proposition 3.2.","marker":"[45]"},{"why":"Shows error minimization for tensor-product structured systems with specific spaces; the paper's Proposition 2.2 removes the dependence on the space choice.","marker":"[27]"},{"why":"Gives the stochastic Galerkin multiterm matrix equation used to demonstrate monotone $S$-norm convergence.","marker":"[38]"},{"why":"Develops the minimal-residual Petrov-Galerkin method for Lyapunov equations whose unconstrained reduced problem the paper analyzes and constrains.","marker":"[30]"},{"why":"Supplies the integral representation and spectral characterizations of linear matrix operators used in the convergence analysis.","marker":"[28]"},{"why":"Provides the positive-definiteness criterion for two-term Sylvester operators that motivates the spd assumption.","marker":"[52]"},{"why":"Establishes that the stochastic steady-diffusion operator is spd although its summands are not all definite, justifying the example.","marker":"[37]"}],"fun_headline_variants":["Galerkin optimality proven for linear matrix systems","Matrix equations extend Galerkin minimal-error result","Optimal projection schemes for Sylvester and Lyapunov","Galerkin stays optimal when equations become matrices","Petrov-Galerkin fixes nondefinite matrix optimality"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The theorem's load-bearing assumption is that the operator $S$, equivalently the Kronecker matrix $\\sum_j B_j^T\\otimes A_j$, is symmetric positive definite; if that fails, the $S$-norm is not a norm and the Galerkin condition no longer guarantees error minimization, and the paper itself notes that this definiteness cannot in general be certified from the spectra of the individual $A_j$ and $B_j$.","fun_headline_variants_meta":{"raw":{"variants":["Galerkin optimality proven for linear matrix systems","Matrix equations extend Galerkin minimal-error result","Optimal projection schemes for Sylvester and Lyapunov","Galerkin stays optimal when equations become matrices","Petrov-Galerkin fixes nondefinite matrix optimality"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000252,"raw_usage":{"total_tokens":1559,"prompt_tokens":939,"completion_tokens":620,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":555,"completion_tokens_details":{"reasoning_tokens":543}},"tokens_in":555,"tokens_out":620,"duration_ms":5804,"temperature":1.0,"reasoning_tokens":543,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:57:57.792545+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For any proposed multiterm equation, explicitly compute the smallest eigenvalue of $S_{\\ell}=\\sum_j B_j^T\\otimes A_j$, for instance for the six-term stochastic Galerkin example used in the paper, and compare its sign with the observed convergence history of the Galerkin iterates: if $\\lambda_{\\min}(S_{\\ell})\\le 0$, the hypothesis of Proposition 2.2 fails, and an observed increase in the $S$-norm error in such a case would show that the unconditional optimality claim is false; if $\\lambda_{\\min}(S_{\\ell})>0$ and the error still increases, the proof itself would be contradicted.","supporting_citations":[{"cited_title":"Saad, Iterative methods for sparse linear systems , SIAM, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2nd ed., 2003","cited_arxiv_id":null,"evidence_quote":"Supplies the Galerkin/Petrov-Galerkin framework and the classical optimality facts for linear systems from which the matrix-equation versions are derived."},{"cited_title":"Simoncini and V","cited_arxiv_id":null,"evidence_quote":"Provides the Lyapunov convergence bound that the paper generalizes to Sylvester equations in Proposition 3.2."},{"cited_title":"Kressner and C","cited_arxiv_id":null,"evidence_quote":"Shows error minimization for tensor-product structured systems with specific spaces; the paper's Proposition 2.2 removes the dependence on the space choice."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the stochastic Galerkin multiterm matrix equation used to demonstrate monotone $S$-norm convergence."},{"cited_title":"Lin and V","cited_arxiv_id":null,"evidence_quote":"Develops the minimal-residual Petrov-Galerkin method for Lyapunov equations whose unconstrained reduced problem the paper analyzes and constrains."},{"cited_title":"Lancaster, Explicit solutions of linear matrix equations , SIAM Rev., 12 (1970), pp","cited_arxiv_id":null,"evidence_quote":"Supplies the integral representation and spectral characterizations of linear matrix operators used in the convergence analysis."},{"cited_title":"Vandereycken and S","cited_arxiv_id":null,"evidence_quote":"Provides the positive-definiteness criterion for two-term Sylvester operators that motivates the spd assumption."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes that the stochastic steady-diffusion operator is spd although its summands are not all definite, justifying the example."}],"review_version":1}