{"id":"4206673a-fa40-4bfd-96a1-198dde61b07c","arxiv_id":"1908.03465","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The optimal affine transform for the extended Davis-Kahan bound is a concave-convex fractional program, solved globally and shown to give tighter eigenvector subspace bounds in SBM and PCA examples.","lead":"This paper shows how to automatically compute the best affine transformation for an extended Davis-Kahan bound on the distance between eigenvector spaces of two symmetric matrices, using fractional programming. It demonstrates the resulting tighter bounds on stochastic blockmodel graphs and spiked covariance models, including cases where the classical Davis-Kahan bound cannot be applied.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The strict-inequality relaxation in the cvx implementation is the load-bearing gap: the computed 'global optimum' is a valid extended-DK bound only if it satisfies the strict Constraints 2 of Paper I, which is checked empirically but not guaranteed.","rationale":"The paper's optimization framework is otherwise mathematically sound: the fractional-programming transformation in (18)-(21) is correctly identified as a concave-convex fractional program, the concavity of δ and convexity of the norm denominator are valid, and the Charnes-Cooper and Dinkelbach approaches are standard. The numerical experiments are plausible and the comparison with standard Davis-Kahan bounds is informative. Nevertheless, the central claim of automatic global optimality is only as strong as the guarantee that the solved point is strictly feasible for the theorem. The paper itself acknowledges the strict-inequality relaxation and relies on empirical checking, which is a genuine gap in the proof of the computational claim. The reader's weakest_assumption identified both the inherited Paper I theorem and the strict-inequality relaxation; I agree with the latter as the more concrete and internally checkable load-bearing concern. The Section V-C index inconsistency noted by the reader is secondary and does not by itself change the verdict. No fatal flaw is apparent, so the conditional verdict is appropriate and should remain unchanged.","tokens_in":17120,"tokens_out":28549,"duration_ms":326825,"concrete_test":"Re-run all reported simulations in Sections V-C to V-E and, for each of the four subproblems and each cvx solution, record the strict-constraint slacks: s1 = δ, s2 = δ - (ψ_{j+r} - c1 φ_{j+r} - c0), and s3 = δ - (c1 φ_{j+1} + c0 - ψ_{j+1}). If every slack is positive by an order of magnitude above the solver tolerance, and if a small interior perturbation of the returned parameters changes the bound negligibly, then the concern is resolved for the demonstrated examples. In addition, construct a synthetic spectrum designed so that the optimum of the closed relaxation sits exactly on a boundary, for instance by forcing equality in one of the Constraints 2 of Paper I at the optimum; if cvx returns that boundary point unmodified, then no valid extended-DK bound is obtained and the automatic-global-optimum claim needs qualification.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central computational claim requires the minimizer of (15) over the open feasible set to be a valid theorem point. That feasible set is open: c1 > 0, δ > 0, and the strict inequalities in Constraints 2A of Paper I, e.g. δ > ψ_{j+r} - c1 φ_{j+r} - c0 and δ > c1 φ_{j+1} + c0 - ψ_{j+1}. However, cvx cannot handle strict inequalities, so the implementation solves the closed relaxation in (21) with non-strict inequalities, and then checks strict feasibility. If the relaxed optimum lies on a boundary where one of the inequalities is active, the returned point is not feasible for Theorem 5 of Paper I, and the value computed from (21) is not an upper bound on ρ1 or ρ2. The global-optimality result for concave-convex fractional programs applies to the relaxed closed problem; it does not by itself establish that the original open problem attains its minimum at a strictly feasible point. The supremum may be approached only as c1 → 0, δ → 0, or c0 → ±∞, in which case no finite affine transformation attains the reported optimum. The manuscript states in Section IV-D that this approach was found to work well with no convergence issues, but that is an empirical observation, not a proof. This is the weakest link between the fractional-programming machinery and the claim that globally optimal bound values can be computed automatically for arbitrary symmetric matrices.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This manuscript is the computational companion to the authors' Paper I, which extended the Davis–Kahan theorem by allowing a polynomial transform of one of the two symmetric matrices. Here the authors specialize to affine transformations and formulate the problem of choosing the affine parameters c1,c0 so as to minimize the extended Davis–Kahan bound as a fractional program. They prove that the relevant separations δ1,+, δ1,−, δ2,+, δ2,− are concave, show that the denominator is convex, and conclude that each of the four subproblems is a concave-convex fractional program for which every local optimum is global. The authors then discuss the Charnes–Cooper transformation and Dinkelbach's algorithm as solution strategies, implement the former in cvx, and apply the method to three examples: comparisons of graph shift operators from stochastic block models, comparisons of graph shift operators with their corresponding generating matrices, and comparisons of sample versus population covariance matrices in a spiked covariance model. The main claims are that the affine-extended Davis–Kahan bound is computable automatically via convex optimization, that it is always at least as tight as the standard Davis–Kahan bound, and that it yields finite informative values in settings where the standard theorem does not apply.","tokens_in":17419,"tokens_out":1930,"duration_ms":21848,"significance":"If the central claim holds, the paper makes a genuinely useful contribution: it turns the extended Davis–Kahan theorem into an automated tool, and the three applications—especially the graph-shift-operator comparisons where the standard theorem is inapplicable—demonstrate concrete value. The manuscript is also careful in several respects: the four subproblems are enumerated explicitly, the proof that the δ's are concave is elementary and correct, the Charnes–Cooper and Dinkelbach derivations are coherent, and the authors explicitly document that the strict-inequality constraints are relaxed in the cvx implementation and then checked a posteriori. The computational claims are made reproducible by reporting simulation parameters and run times.","major_comments":[{"comment":"The central gap is the strict-versus-closed feasibility issue. Problem (19) has a feasible set defined by open constraints, including δ1,+ > 0, δ1,+ > ψ_{j+r} − c1φ_{j+r} − c0, and δ1,+ > c1φ_{j+1} + c0 − ψ_{j+1}; cvx solves the closed relaxation (21). The manuscript states in Section IV-D that this 'works extremely well in practice,' but this is empirical. The global-optimality theorem for concave-convex fractional programs applies to the relaxed closed problem; it does not by itself establish that the minimum of the original open problem is attained at a strictly feasible point. If the relaxed optimum lies on an active constraint boundary, the computed point is not admissible for Theorem 5 of Paper I and the reported value is not an upper bound on ρ1 or ρ2. The authors should either prove that an optimal solution of the relaxed problem can always be chosen strictly feasible, or provide a rigorous perturbation argument, or quantify the gap between the relaxed optimum and the supremum over the open feasible set. This is load-bearing because it is the link between the convex machinery and the claimed validity of every reported bound.","section":"Section IV-D, Eq. (21)"},{"comment":"The examples with j = 1, r = 2 are the ones where the strict-inequality relaxation is most delicate, since Proposition 1's asymptotic guarantee applies only to j = 0 or j = n−r. For the graph-shift-operator comparisons in Section V-C, the authors do not report how often the cvx solution of the relaxed problem satisfied the strict constraints, nor how often the optimum occurred on a boundary, nor what the slack values were. Given that this example is the primary demonstration of cases where the standard Davis–Kahan theorem does not apply, the paper would be substantially strengthened by reporting these diagnostics. Without them, the reader cannot verify that the reported 'bound values' are valid for Theorem 5 of Paper I rather than values of the relaxed objective.","section":"Section V-C, Figs. 1 and 2"},{"comment":"Equation (24) contains a sign issue that is never addressed. The displayed chain states ||Wj − VjQ||_F ≤ ||WjW_j^T − (I − VjV_j^T)||_2 ≤ ...; the correct projector difference from Eq. (1) is ||WjW_j^T (I − VjV_j^T)||_2, not ||WjW_j^T − (I − VjV_j^T)||_2. These two quantities are not equal in general for r > 1. The text and figures labeled 'ρ2' rely on the correct form in the prose, but Eq. (24) is formally wrong and would confuse any reader attempting to reproduce the metric. This is a presentation error rather than a fatal one, but it should be corrected because Eq. (24) is the displayed definition used throughout the application section.","section":"Section V-B, Eq. (24)"}],"minor_comments":[{"comment":"The sentence 'In the original proposal of the transformation for linear fractional programs [4] the equality constraint ||y1Φ + y2I − tΨ||_2 = 1 was used' should specify that for linear fractional programs the equality constraint is an affine equality after the Charnes–Cooper substitution, which is why it is admissible there; the subsequent comparison with convex programs would then be clearer.","section":"Section IV-D"},{"comment":"In Eq. (22), the variable names are inconsistent: the text introduces the affine transformation parameters (c1,c0), but the displayed Dinkelbach problem uses (c,d). The notation should be unified.","section":"Section IV-E"},{"comment":"The l'Hôpital argument in the appendix computes limits of the lower and upper bounds in (25) and (26), but the sandwich conclusion is stated only in words. A single displayed chain of inequalities for each δ would make the proof easier to check; in particular, it should be explicit that the same c1 is held fixed while c0 tends to ±∞.","section":"Appendix A"},{"comment":"The text says 'degree extreme differences' but the x-axes of Figs. 1 and 3 are not defined in the captions. The authors should state exactly which quantity is plotted (e.g., max degree minus min degree) and how it is computed for each graph shift operator.","section":"Section V-C"},{"comment":"In Fig. 5(b), the text highlights simulation number 10 as a case where the bound is 'very close to tight'; it would be useful to state the numerical values of the attained ρ2 distance and the bound for that simulation, since the figure alone does not allow the reader to verify the claimed proximity.","section":"Section V-D, Fig. 5"},{"comment":"There are several typographical issues: in the abstract 'sec ond' appears as 'second' after a line break rendering; in Section V-B the re-scaled expression 'c−1_n,r' is used without defining the scaling of the metrics ρ1 and ρ2; and the references in the introduction are cited in an ad-hoc numeric order (e.g., [9], [13] before [5], [18]). These do not affect the mathematics.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"For the editor: the paper's main contribution is sound conditional on Paper I, and the fractional-programming formulation is correctly identified and derived. The strict-inequality relaxation is the key gap. I do not believe it is fatal, because the authors explicitly check strict feasibility and report no failures, but the absence of a proof or even a systematic numerical audit makes the current claim 'globally optimal bound values can be computed automatically' stronger than what is demonstrated. The paper would be acceptable after the authors either prove the relaxation gap is zero for these problems or substantially document its behavior in simulations, especially for the j=1, r=2 graphs. I would also request that the authors fix Eq. (24) and unify the notation, as these are easy corrections. The dependency on Paper I is appropriate for a two-part work; I would not treat that as a circularity concern."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper makes the affine extended Davis-Kahan bound from Paper I actually computable, and the central math holds up. The move is to cast the optimization as a concave-convex fractional program: the δ's are minima of two affine functions, hence concave, the denominator is a norm, hence convex, so the global-optimality theory applies. That is the real new content. The Charnes-Cooper and Dinkelbach implementations cross-check each other, and the applications—graph shift operators in stochastic blockmodels, spiked covariance PCA—show the affine bound beating the standard DK bound where both apply, and producing finite values where the standard theorem doesn't apply at all. The identity transform being in the feasible set is the key clean argument: it guarantees the optimized bound is never worse than the standard DK bound.\n\nThe genuine soft spot is the strict inequalities. Constraints 2 of Paper I define an open feasible set, while cvx solves the closed relaxation. The paper says this outright and reports that strict-feasibility checks have never failed in their runs. That is an empirical observation, not a proof, and the abstract's phrase 'globally optimal bound values can be computed automatically' goes a little beyond what is demonstrated. For generic eigenvalue data the optimum will be strictly feasible, so I don't see this as load-bearing; it's a gap a revision should close with a genericity argument, or by relaxing the theorem to non-strict separation if that holds.\n\nTwo smaller issues. The paper is not self-contained: the upper-bound property comes from Paper I's Theorem 5, so a referee must check Paper I before judging this one. And the Section V-C discussion of adjacency versus Laplacians is confusing about the spectral flip; the c1 < 0 subproblems handle it, but the text doesn't make that explicit. Also absent: released code, which is a genuine downside for an algorithmic paper. The citations otherwise look standard and appropriate.\n\nOverall, the optimization theory is sound, the numerical improvements over the standard DK bound are real, and the limitations are stated rather than hidden; the fallback to the trivial bound in Remark 3 is a good example. If I worked on spectral clustering or PCA diagnostics, I'd cite this. It deserves a serious referee—send it out, and ask for a resolution of the strict-inequality question and a code release in revision.","headline":"Solid computational companion to Paper I—affine extended DK bounds as a solvable concave-convex fractional program with real gains over standard DK; the cvx strict-inequality relaxation is the one real gap, acknowledged and empirically handled but not proven.","tokens_in":17867,"tokens_out":15005,"would_cite":true,"duration_ms":136346,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62H25","62H30","15A42","90C32","05C50"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper shows that the optimal affine-transform Davis–Kahan bound is the solution of a concave-convex fractional program, so it can be computed globally and automatically, always matching or beating the standard Davis–Kahan bound.","keywords":["Davis–Kahan theorem","eigenvector perturbation","affine matrix transformation","fractional programming","convex optimization","stochastic blockmodel","spiked covariance model","graph shift operator"],"falsifier":"Take two small symmetric matrices with known eigendecompositions, compute the true distance $\\inf_{R\\in O(r)}\\|W-VR\\|_F$, and solve the four affine subproblems; any reported bound smaller than that true distance would disprove the claim. A more targeted check is to construct a case where the relaxed convex solve violates the strict $\\delta_i>0$ constraints, which would mean the reported optimum is not actually feasible for the extended theorem.","tokens_in":16942,"feed_emoji":"🧮","tokens_out":10465,"duration_ms":100814,"temperature":0.7,"pith_summary":"This paper makes the extended Davis–Kahan theorem computable for affine transformations of one matrix. Rather than leaving the transformation parameters to the user, it frames the search for the tightest bound as a ratio-maximization problem and proves that the four relevant subproblems are concave-convex fractional programs with global optima. The result is a parameter-free procedure: one convex solve per subproblem returns the optimal bound automatically. In tests on stochastic blockmodel graph shift operators, their generating matrices, and spiked-covariance sample-versus-population eigenvectors, the affine bounds are never worse than the standard Davis–Kahan bounds and remain finite in several cases where the standard theorem cannot be applied.","feed_headline":"One convex solve yields the tightest affine eigenspace bound","feed_subtitle":"A fractional-programming reformulation beats the standard Davis–Kahan bound in graph and PCA examples.","key_machinery":"The load-bearing object is the ratio $\\|c_1\\Phi+c_0I-\\Psi\\|_2/\\delta_i$, where $\\delta_i$ is one of four possible Davis–Kahan eigenvalue-separation gaps that arise from the two interval choices and the sign of $c_1$. The argument proceeds by showing $\\delta_i$ is concave (it is a minimum of affine functions of $c_1,c_0$) while the norm denominator is convex, so maximizing the reciprocal ratio is a concave-convex fractional program. The parameter-free transformation $y_1=c_1/t$, $y_2=c_0/t$, $t=1/\\|c_1\\Phi+c_0I-\\Psi\\|_2$ converts each subproblem into a convex program with a norm inequality constraint, making the global optimum automatically computable.","core_discovery":"The paper's central claim is that the optimal affine extension of the Davis–Kahan theorem is a well-posed optimization problem. Writing the transformed matrix as $f(\\Phi)=c_1\\Phi+c_0I$, the bound on the distance between eigenspaces takes the form $c_{n,r}\\|f(\\Phi)-\\Psi\\|_2/\\delta_i$, where $\\delta_i$ is the post-transformation eigenvalue-separation gap. The paper proves each $\\delta_i$ is the minimum of two affine functions and hence concave, the denominator is convex, and the numerator is positive on the feasible set, so maximizing the reciprocal ratio is a concave-convex fractional program. A variable substitution turns it into an equivalent convex program, and an iterative parametric algorithm gives the same optimum; the authors use the first because it is a single convex solve. Consequently the tightest affine Davis–Kahan bound is obtained automatically, is always at least as tight as the standard bound (the identity transform is a feasible point), and can give finite values where the standard interval-separation condition fails.","pith_inferences":["Editorial inference: the same fractional-programming formulation should extend to polynomial transformations of degree two or more: the transformed spectrum is a sum of powers, so each interval endpoint is selected from finitely many orderings, and each selection still yields a ratio of concave/convex type that could be solved by branch-and-bound. This would test whether higher-degree transforms a","Editorial inference: because the bound is cheap to compute, it could be used as a finite-sample certificate inside spectral clustering or PCA pipelines: if the optimized bound is close to 1, the observed eigenvector space is not yet informative about the population space, giving a data-dependent rule of thumb for when more samples are needed.","Editorial inference: the spiked-covariance experiments suggest a practical diagnostic that goes beyond the paper: the optimized bound as a function of sample size $N$ could be inverted to choose the minimal $N$ at which the leading-$r$ sample eigenspace is guaranteed close to the population eigenspace at a user-specified tolerance."],"forward_implications":["For any pair of symmetric matrices satisfying the extended theorem's assumptions, the best affine bound is obtained by solving one convex program per sign/interval case; no parameter search or user tuning is needed.","The optimized bound is always at least as tight as the standard Davis–Kahan bound, and in the paper's stochastic-blockmodel and spiked-covariance examples it improves on the standard bound, often by about a factor of two.","When comparing eigenvectors of the largest or smallest eigenvalues, the affine-optimized bound always matches or beats the trivial bound $c_{n,r}$; Proposition 1 proves the cost function approaches 1 as $c_0\\to\\pm\\infty$.","The method supplies useful finite bounds in comparisons where the standard Davis–Kahan theorem is inapplicable, such as adjacency-matrix versus Laplacian eigenspaces in the stochastic blockmodel, because the transformation creates a positive separation gap.","The parameter-free and iterative parametric solution routes agree numerically, with the parameter-free route preferred because it solves a single convex problem."],"supporting_citations":[{"why":"Supplies the concave-convex fractional programming framework and the equivalence of optimality conditions used to classify the four subproblems.","marker":"[13]"},{"why":"Introduces the variable transformation that converts the ratio objective into an equivalent convex program.","marker":"[4]"},{"why":"Proves the equality and inequality norm constraints are equivalent for concave-convex fractional programs, justifying the relaxed constraint.","marker":"[20]"},{"why":"Provides the inversion identity used to rewrite the minimization as a maximization of the reciprocal ratio.","marker":"[21]"},{"why":"Proposes the iterative parametric algorithm used to verify the parameter-free solver's results.","marker":"[6]"},{"why":"Introduces the spiked covariance model used in the PCA application.","marker":"[14]"},{"why":"Gives the stochastic blockmodel parametrization used to generate the graph examples.","marker":"[17]"},{"why":"Supplies the conventions for the endpoints of the eigenvalue spectrum used in the Appendix's extreme-eigenvector analysis.","marker":"[28]"},{"why":"The convex optimization software used to implement the numerical solves.","marker":"[10]"}],"fun_headline_variants":["Affine Davis–Kahan bound tightened by convex programming","Tightest affine eigenspace bound via one convex solve","Optimal affine eigenspace bounds from fractional programming","Convex program beats standard Davis–Kahan bound","Automatic tightest bound for eigenvector comparison"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The computation inherits the extended Davis–Kahan inequality from the companion paper, and if that inequality is wrong, the minimized ratio is not a guaranteed upper bound; the practical solver also relaxes strict constraints to non-strict versions and checks feasibility afterward, without a general proof that this always succeeds.","fun_headline_variants_meta":{"raw":{"variants":["Affine Davis–Kahan bound tightened by convex programming","Tightest affine eigenspace bound via one convex solve","Optimal affine eigenspace bounds from fractional programming","Convex program beats standard Davis–Kahan bound","Automatic tightest bound for eigenvector comparison"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000165,"raw_usage":{"total_tokens":1260,"prompt_tokens":966,"completion_tokens":294,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":582,"completion_tokens_details":{"reasoning_tokens":230}},"tokens_in":582,"tokens_out":294,"duration_ms":3835,"temperature":1.0,"reasoning_tokens":230,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:14:20.347763+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take two small symmetric matrices with known eigendecompositions, compute the true distance $\\inf_{R\\in O(r)}\\|W-VR\\|_F$, and solve the four affine subproblems; any reported bound smaller than that true distance would disprove the claim. A more targeted check is to construct a case where the relaxed convex solve violates the strict $\\delta_i>0$ constraints, which would mean the reported optimum is not actually feasible for the extended theorem.","supporting_citations":[{"cited_title":"Frame work for link- level energy efficiency optimization with informed transmi tter,","cited_arxiv_id":null,"evidence_quote":"Supplies the concave-convex fractional programming framework and the equivalence of optimality conditions used to classify the four subproblems."},{"cited_title":"Programming with linear fract ional functionals,","cited_arxiv_id":null,"evidence_quote":"Introduces the variable transformation that converts the ratio objective into an equivalent convex program."},{"cited_title":"Parameter-free Convex Equivalent and Du al Programs of Fractional Programming Problems,","cited_arxiv_id":null,"evidence_quote":"Proves the equality and inequality norm constraints are equivalent for concave-convex fractional programs, justifying the relaxed constraint."},{"cited_title":"Minimization of Ratios,","cited_arxiv_id":null,"evidence_quote":"Provides the inversion identity used to rewrite the minimization as a maximization of the reciprocal ratio."},{"cited_title":"On Nonlinear Fractional Programming,","cited_arxiv_id":null,"evidence_quote":"Proposes the iterative parametric algorithm used to verify the parameter-free solver's results."},{"cited_title":"Grant & S","cited_arxiv_id":null,"evidence_quote":"The convex optimization software used to implement the numerical solves."}],"review_version":1}