{"id":"2bec9494-13da-42ea-9afa-bbfb74c3fbe8","arxiv_id":"1908.01327","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A new accelerated nonoverlapping block Jacobi method for the dual ROF denoising model is proven to converge with O(1/n^2) energy decay, with local problems solved by existing image denoising solvers.","lead":"This paper designs faster parallel methods for removing noise from images using the ROF total variation model. It proves a new accelerated block Jacobi scheme converges quadratically faster than previous nonoverlapping domain decomposition methods.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"O(1/n^2) rate rests on an unverified transfer of FISTA to a possibly degenerate pseudometric; the paper cites Beck–Teboulle without proving the telescoping argument for D.","rationale":"The relaxed block Jacobi O(1/n) theorem (Theorem 3.3) is internally coherent: Lemma 3.2 supplies the needed inequality and the summation is valid. The pre-relaxed constructions (Lemmas 3.10 and 3.11) are also algebraically sound; Lemma 3.11 is the exact analogue of the FISTA fundamental inequality after multiplication by N_c. The unresolved point is the jump from Lemma 3.11 to Theorems 3.12 and 3.14. The paper's one-sentence replacement of the norm in [2] does not state the hypotheses under which [2]'s proof is metric-agnostic. Since D is explicitly called a pseudometric and positive definiteness is not checked, a referee cannot tell from the text whether the telescoping proof is valid. This is the single most load-bearing concern: if the FISTA telescoping fails, the O(1/n^2) claim has no proof. The check I propose settles it by re-deriving the proof in the seminorm. My reading agrees with the reader's verdict conditionally; the reader's 'positive definiteness' worry is a possible symptom, but the real requirement is that the entire semidefinite proof be supplied. The lack of released code is a secondary reproducibility issue, not the main mathematical risk.","tokens_in":16878,"tokens_out":41212,"duration_ms":408175,"concrete_test":"Re-derive Theorem 4.4 of Beck–Teboulle in the semidefinite inner product ⟨u,v⟩_A = u^T A v with A = Σ R_k^* R_k div^* div R_k^* R_k (the Gram operator of D), starting from Lemma 3.11. Check every algebraic step of the telescoping proof: the completion-of-square identity, the definition of the auxiliary point v_k, and the summation that yields 4N_c D(p*,p^(0))/(n+1)^2. If every step uses only bilinearity, symmetry, and nonnegativity of ⟨·,·⟩_A — not A ≻ 0 — then Theorem 3.14 follows as stated. If any step invokes an inverse of A, strict convexity of the squared seminorm, or uniqueness of the prox, the theorem requires an additional assumption or a modified proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central O(1/n^2) claim (Theorem 3.14) is proved by direct citation: \"With the same argument as in Theorem 4.4 of [2]\" after replacing the Euclidean norm by ||·|| = (Σ_k ||div R_k^* R_k(·)||^2)^{1/2} = sqrt(2D), with D from (2.6). The paper proves the analogue of Beck–Teboulle's fundamental inequality (Lemma 3.11), but it never proves that the rest of the FISTA telescoping argument survives when this object is only a seminorm. D is not shown to be positive definite on C, and in the discrete divergence setting div has a nontrivial kernel, so sqrt(2D) is genuinely a pseudometric; the paper itself uses that word. If any step in [2]'s proof uses invertibility of the induced Gram operator, strict positivity of ||x-y||^2, or single-valuedness of the prox, then the constant 4N_c/(n+1)^2 in Theorem 3.14 is not established. This is load-bearing because no other argument for the accelerated rate is given; the numerical experiments cannot substitute for the missing proof. The gap is addressable: Lemma 3.11 may be enough, but the transfer must be written out.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops nonoverlapping block Jacobi methods for the Fenchel–Rockafellar dual of the discrete Rudin–Osher–Fatemi model. The authors prove an O(1/n) energy convergence rate for the relaxed block Jacobi method (Algorithm 3.1), introduce a pre-relaxed variant (Algorithm 3.2) that has an explicit forward-backward splitting structure, and then propose a FISTA-type accelerated version (Algorithm 3.3) for which they claim an O(1/n^2) energy convergence rate. The convergence-rate constants are expressed in terms of the number of colors N_c and a constant c_1 that depends on the image size and the number of subdomains. The paper also discusses local solvers, a three-coloring scheme, and reports numerical experiments comparing the methods on two test images with various decompositions and parameters.","tokens_in":17198,"tokens_out":20060,"duration_ms":182953,"significance":"If the O(1/n^2) theorem is made fully rigorous, the paper gives a meaningful contribution: it provides the first accelerated nonoverlapping domain-decomposition method for the dual ROF model with the same per-iteration cost as the unaccelerated block Jacobi method, and it gives explicit dependence of the convergence constant on the image size and subdomain interfaces. The O(1/n) analysis of Algorithm 3.1 and the derivation of the fundamental inequalities (Lemmas 3.2, 3.10, 3.11) are careful and appear correct. The numerical results support the practical interest of the method and show plausible agreement with the theoretical rates. The main weakness is the proof of the accelerated rate, which relies on a one-sentence transfer of the Beck–Teboulle FISTA argument to a pseudometric setting without fully stating the hypotheses needed for that transfer.","major_comments":[{"comment":"The O(1/n^2) bound is obtained by direct citation to Theorem 4.4 of [2] after replacing the Euclidean norm by the expression ||·|| = (Σ_k ||div R_k^* R_k(·)||^2)^{1/2} = sqrt(2D), with D defined in (2.6). Since the discrete divergence operator has a nontrivial kernel, D is only a positive semidefinite quadratic form, and the paper never verifies that the Beck–Teboulle telescoping argument remains valid for this pseudometric. The concern is load-bearing because Theorem 3.14 is the only argument for the central O(1/n^2) claim. I believe the transfer is in fact valid, since the FISTA proof uses only algebraic identities valid for any symmetric positive semidefinite bilinear form, but the authors must write out the transfer or prove the telescoping bound directly, rather than leaving the non-Euclidean replacement to a citation.","section":"§3.2, Theorem 3.14 (and Theorem 3.12)"},{"comment":"Lemma 3.11 is stated for p,q∈C, but in Algorithm 3.3 the extrapolated points q^(n+1) = p^(n+1) + ((t_n-1)/t_{n+1})(p^(n+1)-p^(n)) need not belong to C. The FISTA argument requires Lemma 3.11 with q equal to these extrapolated points, and also with p=q in the decrease inequality. The proof of Lemma 3.11 actually carries over without change to q∈W, because the local operators P_k are defined on all of W and the optimality condition (3.17) does not use q∈C. The lemma statement and proof should be extended to this broader domain before Theorem 3.14 can be applied to Algorithm 3.3.","section":"§3.2, Lemma 3.11 and Algorithm 3.3"}],"minor_comments":[{"comment":"The numerical experiments solve local problems approximately, using FISTA with the stated stopping criteria, while the theoretical results in Section 3 assume exact local solves. The paper should explicitly acknowledge this gap; the numerical evidence is indicative but does not by itself validate the exact-solve theory.","section":"§5"},{"comment":"The symbol N is used both for the image width in §2.1 and for the number of subdomains in §2.2 (N = M_s × N_s). This is a potential source of confusion and should be resolved, for example by using N_pix for the pixel dimension.","section":"§2.2"},{"comment":"The log-log plots of energy decay are informative, but the curves for the O(1/n) methods appear to have different slopes; adding reference lines with slopes -1 and -2 would make the claimed rates more immediately visible to the reader.","section":"§5, Figure 5.2"},{"comment":"The remark that the rates are independent of f and α is correct, but it would be helpful to note that the initial energy difference F(p^(0))-F(p*) in the bounds does depend on f and α, even though the other constants do not.","section":"Remark 3.15"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is competently written and the central algorithmic idea is sound. The only substantive technical issue is the proof of the accelerated O(1/n^2) rate: the authors need to spell out the pseudometric transfer from Beck–Teboulle and extend Lemma 3.11 to the extrapolated points that lie outside C. Both points are fixable in revision, but they are load-bearing for the paper's main claim. I see no novelty or attribution concerns."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The first thing to know: the O(1/n) rate for the nonoverlapping relaxed block Jacobi method (Algorithm 3.1) is real and complete. Lemma 3.2 is the core, and Theorem 3.3 follows with a clean telescoping argument. That alone is a genuine contribution, because prior convergence results for this method had no rate. The dependence on image size and subdomain count (Lemma 3.5, Corollary 3.8) is also useful and appears correctly derived. The paper is well-written and the numerical section is honest: they solve local problems with a strict criterion to avoid blaming the outer method, and they report iteration counts and wall-clock times.\n\nThe soft spot is the O(1/n^2) claim. Theorem 3.14 is proved by citing Theorem 4.4 of Beck–Teboulle and replacing the Euclidean norm with the pseudometric sqrt(2D). The stress-test note is right: D is not shown positive definite on C, and in the discrete setting div has a nontrivial kernel, so this is genuinely a seminorm. The paper itself calls it a pseudometric. Whether the FISTA telescoping argument survives with a seminorm is not automatic—the standard proof uses the squared norm in several places that can fail if ||x-y||^2 vanishes for x≠y. This does not mean the theorem is false; the numerics support O(1/n^2) and Lemma 3.11 gives the key inequality. But the proof as written is incomplete. The fix may be short, but the authors need to write it out rather than citing [2] directly.\n\nThere is no circularity: the rates follow from lemmas, not from fitting. The citation pattern is normal, with self-citations only where the prior work is genuinely the origin of the method. No code or data is released, which is a minor negative for reproducibility, but the numerical setup is described in enough detail to replicate.\n\nFor whom: researchers working on domain decomposition or first-order methods for nonsmooth convex optimization, especially anyone needing a parallel solver for the dual ROF model. The O(1/n) analysis is solid and worth citing; the O(1/n^2) result is plausible but should be cited with awareness of the gap.\n\nMy recommendation: this deserves peer review. A serious referee should ask for the missing proof of the FISTA transfer, but the paper has enough solid content that desk rejection would be wrong.","headline":"Solid O(1/n) analysis for a known method and a plausible O(1/n^2) accelerated variant whose proof rests on an unverified pseudometric transfer; worth refereeing but needs the FISTA gap closed.","tokens_in":17671,"tokens_out":634,"would_cite":true,"duration_ms":8397,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65N55","65Y05","65B99","65K10","68U10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Block-parallel denoising solver reaches O(1/n^2) energy decay","keywords":["domain decomposition","block Jacobi","Rudin–Osher–Fatemi model","total variation denoising","FISTA acceleration","convergence rate","dual formulation","parallel computing"],"falsifier":"Check whether the pseudometric $D$ has a nonzero kernel on the feasible set: if two distinct dual fields $p$ and $q$ satisfy $\\operatorname{div} R_k^*R_k(p-q)=0$ for every color $k$, then the $D$-term cannot separate them, and the telescoping bound that yields the constant $4N_c$ in Theorem 3.14 would require an additional argument. A direct numerical test of Algorithm 3.3 on a small image, plotting $\\log(F(p^{(n)})-F(p^*))$ against $\\log n$, would also settle the claimed $O(1/n^2)$ slope.","tokens_in":16679,"feed_emoji":"🖼️","tokens_out":7632,"duration_ms":71636,"temperature":0.7,"pith_summary":"The paper analyzes nonoverlapping block Jacobi methods for the dual of the Rudin–Osher–Fatemi (ROF) image denoising model, in which the image is split into rectangular subdomains and local problems are solved in parallel. It proves that the relaxed block Jacobi method converges with O(1/n) energy decay, and then introduces a 'pre-relaxed' variant that fits the forward-backward splitting structure used by accelerated gradient methods. Adding momentum to this variant yields the paper's central result: an O(1/$n^{2}$) convergence rate, with a constant that depends on the number of colors in the subdomain decomposition and on the total interface length. If correct, this gives a communication-light parallel solver that reaches a given energy tolerance in far fewer iterations than existing domain decomposition methods, at the same per-iteration cost.","feed_headline":"Block-parallel denoising solver reaches O(1/n^2) energy decay","feed_subtitle":"A pre-relaxed twist on parallel domain decomposition matches FISTA's fast rate at the same per-iteration cost.","key_machinery":"The load-bearing object is the pre-relaxed local solution operator $P_k(q) = \\arg\\min_{p_k\\in W_k} \\{F_k(N_c p_k - (N_c-1)R_k q; q) + \\chi_{C_k}(p_k)\\}$, which inserts the relaxation parameter into the local problem rather than applying it as a separate outer averaging step. The outer update $p^{(n+1)} = \\sum_{k=1}^{N_c} R_k^* P_k(q^{(n)})$ is then a proximal descent with respect to the pseudometric $d(p,q) = \\bigl(\\sum_k \\|\\operatorname{div} R_k^*R_k(p-q)\\|_2^2\\bigr)^{1/2} = \\sqrt{2D(p,q)}$, where $D$ is the sum of local Bregman distances. Lemma 3.11 shows that this update satisfies the exact inequality $F(p) - F(P(q)) \\ge D(p,P(q)) - D(p,q)$, the same template as the fundamental lemma behind FISTA's accelerated convergence proof, so the standard momentum recursion $t_{n+1} = (1+\\sqrt{1+4t_n^2})/2$ applies directly.","core_discovery":"The paper's central result is Theorem 3.14: for the fast pre-relaxed block Jacobi method (Algorithm 3.3), the dual energy gap is bounded by $$F($p^{{(n)}}$)-F(p^*) \\le \\frac{4N_c}{(n+1)^2}\\bigl(F($p^{{(0)}}$)-F(p^*)+2c_1\\bigr),$$ with $c_1=7(MN_s+M_sN-\\frac{11}{7}M_sN_s)$ depending on image dimensions and subdomain counts, while the relaxed block Jacobi method (Algorithm 3.1) is shown in Theorem 3.3 to converge at rate $O(1/n)$. The improvement comes from a modification called pre-relaxation: the relaxation parameter is folded into the local subproblem, so the outer update is exactly a proximal descent with respect to a pseudometric, matching the condition that the FISTA acceleration proof requires. The paper also proves that the convergence-rate constants depend on the number of colors $N_c$ and the total interface length of the partition, and verifies numerically that the accelerated method reaches the same denoising quality as full FISTA while taking far fewer wall-clock seconds.","pith_inferences":["The same pre-relaxation trick should apply to other nonsmooth convex problems whose duals decompose over nonoverlapping blocks, as long as the local divergence pseudometric has the needed decay; one testable extension is total variation minimization with $L^1$ fidelity.","The proof inherits FISTA's metric assumptions without verifying that the pseudometric is positive definite on the feasible set; if a nonzero direction lies in its nullspace, the stated constant could fail even if the rate survives.","Because the momentum step is taken in the dual variable, the recovered primal image may inherit non-monotone energy behavior; using a monotone variant of the momentum step would give a strictly decreasing energy while retaining the $O(1/n^2)$ complexity.","Overlapping decompositions are not covered by this analysis, but numerical experiments comparing overlap sizes would indicate whether the acceleration is a property of the splitting structure rather than of nonoverlap itself."],"forward_implications":["The accelerated method's energy gap decays as $O(1/n^2)$ regardless of the image $f$ and the weight $\\alpha$, so the worst-case rate is insensitive to noise level and regularization strength.","Each outer iteration keeps the same per-iteration cost as the relaxed method because local problems remain ROF-type denoising problems; existing local solvers can be plugged in unchanged.","The constants reveal a design trade-off: stripe-shaped decompositions with two colors converge faster when few subdomains are used, while window-shaped decompositions win for many subdomains because their total interface length grows only as the square root of the subdomain count.","Wall-clock experiments show the speed-up is realized in practice: on a 2048 x 3072 image, the fast method reaches the energy tolerance in about 4.7 seconds with a 16 x 16 partition versus about 53 seconds for full-problem FISTA."],"supporting_citations":[{"why":"Supplies the fundamental lemma and the O(1/n^2) momentum proof that Theorems 3.12 and 3.14 reuse with a pseudometric in place of the Euclidean norm.","marker":"[2]"},{"why":"Proposed the relaxed nonoverlapping block Jacobi method and proved its convergence without a rate; this paper's Theorem 3.3 supplies the rate and Algorithm 3.2 modifies the method.","marker":"[14]"},{"why":"Gives the overlapping-domain O(1/n) analysis and the optimality inequality of Lemma 2.2 that the nonoverlapping proof adapts; its remark that the proof breaks down as overlap shrinks motivates the new argument.","marker":"[8]"},{"why":"Provides the O(1/n) rate for block coordinate descent methods against which the accelerated block Jacobi method is compared and which it outperforms numerically.","marker":"[7]"}],"fun_headline_variants":["Dual ROF block Jacobi hits O(1/n^2) energy decay","Pre-relaxed block Jacobi accelerates denoising to O(1/n^2)","Parallel block Jacobi achieves O(1/n^2) for ROF denoising","Faster domain decomposition for ROF: O(1/n^2) convergence","Nonoverlapping blocks converge quadratically in ROF dual"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The O(1/$n^{2}$) proof assumes that the block-local divergence pseudometric $\\sqrt{2D}$ satisfies all the metric inequalities needed in the FISTA telescoping argument, even though the paper does not show this pseudometric is positive definite on the feasible set.","fun_headline_variants_meta":{"raw":{"variants":["Dual ROF block Jacobi hits O(1/n^2) energy decay","Pre-relaxed block Jacobi accelerates denoising to O(1/n^2)","Parallel block Jacobi achieves O(1/n^2) for ROF denoising","Faster domain decomposition for ROF: O(1/n^2) convergence","Nonoverlapping blocks converge quadratically in ROF dual"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000213,"raw_usage":{"total_tokens":1448,"prompt_tokens":998,"completion_tokens":450,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":614,"completion_tokens_details":{"reasoning_tokens":343}},"tokens_in":614,"tokens_out":450,"duration_ms":4824,"temperature":1.0,"reasoning_tokens":343,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:17:41.042791+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Check whether the pseudometric $D$ has a nonzero kernel on the feasible set: if two distinct dual fields $p$ and $q$ satisfy $\\operatorname{div} R_k^*R_k(p-q)=0$ for every color $k$, then the $D$-term cannot separate them, and the telescoping bound that yields the constant $4N_c$ in Theorem 3.14 would require an additional argument. A direct numerical test of Algorithm 3.3 on a small image, plotting $\\log(F(p^{(n)})-F(p^*))$ against $\\log n$, would also settle the claimed $O(1/n^2)$ slope.","supporting_citations":[{"cited_title":"Beck and M","cited_arxiv_id":null,"evidence_quote":"Supplies the fundamental lemma and the O(1/n^2) momentum proof that Theorems 3.12 and 3.14 reuse with a pseudometric in place of the Euclidean norm."},{"cited_title":"Hinterm ¨uller and A","cited_arxiv_id":null,"evidence_quote":"Proposed the relaxed nonoverlapping block Jacobi method and proved its convergence without a rate; this paper's Theorem 3.3 supplies the rate and Algorithm 3.2 modifies the method."},{"cited_title":"Chang, X.-C","cited_arxiv_id":null,"evidence_quote":"Gives the overlapping-domain O(1/n) analysis and the optimality inequality of Lemma 2.2 that the nonoverlapping proof adapts; its remark that the proof breaks down as overlap shrinks motivates the new argument."},{"cited_title":"Chambolle and T","cited_arxiv_id":null,"evidence_quote":"Provides the O(1/n) rate for block coordinate descent methods against which the accelerated block Jacobi method is compared and which it outperforms numerically."}],"review_version":1}