{"id":"1e38df5a-27b9-41f7-ac3b-c12c51026c3e","arxiv_id":"1908.06065","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"An exact convex-concave min-max reformulation of ill-posed linear inverse problems is derived, with saddle points characterized by the primal and dual optimal sets.","lead":"This paper gives a new mathematical reformulation of ill-posed linear inverse problems, turning them into min-max problems that are natural targets for simple alternating-update algorithms. The purpose is to enable new algorithms for sparse coding and dictionary learning with hard error constraints.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Definition 2.6's exclusion lambda notin B[0,epsilon] makes Lambda_delta empty in a valid 1D instance, so Theorems 2.7(ii)(b) and 2.10(b) are false as stated.","rationale":"The central claim is the exact saddle-point characterization in Theorem 2.10, parameterized by Lambda_delta. The reader identified the strict-convexity/generic-norm issue as the weakest assumption, but under the paper's Euclidean Hilbert-space assumptions that issue does not arise. The actual load-bearing flaw is internal: Definition 2.6 excludes the closed ball B[0,epsilon], and the proofs never use or verify this exclusion. The 1D example above satisfies Assumption 2.1 and ||x|| > epsilon, yet the unique optimal dual lambda = 0.5 lies in B[0,1], making Lambda_delta empty while the dual and min-max problems both have unique solutions. Consequently Theorem 2.7(ii)(b) and Theorem 2.10(b), as literally stated, are false. The mathematical construction is otherwise sound and the error is a one-line correction to Definition 2.6, so the appropriate verdict remains CONDITIONAL rather than ACCEPT or REJECT; the reader's verdict does not need to change, though the stated reason for conditionality should be updated to include this counterexample.","tokens_in":30134,"tokens_out":51437,"duration_ms":467752,"concrete_test":"Analytically verify the 1D instance: Hn = R, K = 1, phi(f) = f, c(f) = |f|/2, p = 1, delta = 0, epsilon = 1, x = 3. Compute C_delta = 1 and the unique dual optimum lambda = 0.5; then check Definition 2.6: ||lambda||'_phi = 1 and <lambda,x> - epsilon||lambda|| = 1 both hold, but lambda belongs to B[0,1], so Lambda_delta = empty. This contradicts Theorem 2.7(ii)(b) and proves the ball-exclusion clause in Definition 2.6 is erroneous; re-state the theorems with Lambda_delta defined without that exclusion and re-check Proposition 3.10 and Theorem 2.10(b).","verdict_should_be":"UNCHANGED","load_bearing_attack":"Definition 2.6 defines Lambda_delta as the set of lambda in Hn\\B[0,epsilon] (closed Euclidean ball) satisfying ||lambda||'_phi = 1 and <lambda,x> - epsilon||lambda|| = (C_delta)^{1/p}. The exclusion is not used in the proofs and is too strong. Take Hn = R, K = 1, phi = identity, c(f) = |f|/2, so Vc = [-2,2], p = 1, delta = 0, epsilon = 1, and x = 3. The LIP (9) has C_delta = 1 and F_delta = {2}. The dual gauge is ||lambda||'_phi = 2|lambda|, so the dual problem (16) maximizes 3lambda - |lambda| subject to 2|lambda| <= 1; its unique optimum is lambda = 0.5, with ||lambda|| = 0.5 < 1. However, under Definition 2.6 the set Lambda_delta is empty, because every candidate satisfying ||lambda||'_phi = 1 has |lambda| = 0.5, which lies in B[0,1]. Thus Theorem 2.7(ii)(b), which asserts optimal duals exist iff Lambda_delta is nonempty, is contradicted. Directly, the min-max problem (18) with r = 1 and q = 1/2 has the saddle point (h, lambda) = (2, 1/8): h = 2 lies in F_delta / C^{1/p}, and lambda = 1/8 equals 0.25 * 0.5, the scaled Lambda-element from Proposition 3.10. The intended theory is recovered by dropping the B[0,epsilon] exclusion from Definition 2.6, since lambda = 0 already fails ||lambda||'_phi = 1.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript studies convex duality for the linear inverse problem minimize c(f) subject to ||x−φ(f)|| ≤ ε+δc, where c is positively homogeneous with a convex compact unit sublevel set. It introduces a gauge function for the scaled atomic set, establishes strong duality with the dual gauge, and derives a convex-concave min-max reformulation whose minimizers and saddle points are characterized in terms of the primal optimal set. The authors apply this reformulation to dictionary learning, pointing to the companion paper [SC19]. The proof strategy is geometric: Lemma 3.4 identifies the unique intersection of the feasible Euclidean ball with the scaled atomic set; Lemmas 3.8–3.11 and Proposition 3.10 characterize separating functionals and optimal duals; Lemma 3.14 evaluates the inner supremum to prove the min-max formula.","tokens_in":30515,"tokens_out":8438,"duration_ms":80103,"significance":"If corrected, the min-max reformulation is a useful and nontrivial contribution: it is parameter-free in the sense that the delta regularizer is part of the model rather than a fitted parameter, it is self-contained, and it gives exact primal-dual characterizations instead of mere inequalities. The paper provides a clean bridge from gauge duality to a saddle-point problem that can be solved by ascent-descent, with concrete implications for dictionary learning. I found the central derivation from Lemmas 2.5 through Theorem 2.10 internally coherent apart from the definitional issue below, and I credit the paper for proving its strong-duality statement from first principles.","major_comments":[{"comment":"Definition 2.6 excludes the closed ball B[0,ε] from the candidate set Λδ. This exclusion is not merely harmless; it makes Theorem 2.7(ii) false in a valid one-dimensional instance. Take Hn=R, K=1, φ(f)=f, c(f)=|f|/2 (so p=1 and Vc=[−2,2]), δ=0, ε=1, and x=3. The primal problem (9) has Cδ(φ,x,ε)=1 and Fδ={2}. The gauge is ||z||_φ=|z|/2 and the dual gauge is ||λ||'_φ=2|λ|, so the dual problem (16) is maximize 3λ−|λ| subject to 2|λ|≤1. Its unique optimum is λ*=1/2 with value 1, which equals Cδ(φ,x,ε)^{1/p}. This λ* satisfies the two conditions in Definition 2.6, but ||λ*||=1/2<1, so λ* lies in B[0,ε] and is excluded; hence Λδ=∅. Theorem 2.7(ii)(b) therefore asserts that (16) has no optimal solution, which is false, and Theorem 2.7(ii)(c) is false as well. For the same instance, the inf-sup problem (18) with q=1/2 and r=1 has the saddle point (h,λ)=(2,1/8), contradicting Theorem 2.10(b). The exclusion is never used in the proofs; it should be removed (using Hn\\{0}, say), after which Proposition 3.10(ii) would correctly identify λ*=1/2.","section":"Definition 2.6 and Theorem 2.7"},{"comment":"Both statements take x ∈ Hn\\B[x,ε], but for any x and any ε≥0 the ball B[x,ε] contains x, so for ε>0 the set Hn\\B[x,ε] is empty. The intended hypothesis is x∈Hn\\B[0,ε] (equivalently ||x||>ε), as in Theorem 2.7 and Lemma 3.13. Without this correction the main min-max theorem is vacuous as stated.","section":"Theorem 2.10 and Lemma 3.14"}],"minor_comments":[{"comment":"The proof heading appears as 'Proof of Theorem ??' instead of a numbered theorem; this placeholder should be corrected before publication.","section":"Section 3, proof of Theorem 2.10"},{"comment":"Definition 2.4 writes φ : Hn → RK, but the correct domain/codomain is RK → Hn, as used in Definition 2.2 and throughout the paper.","section":"Definition 2.4"},{"comment":"The definition of B(z,r) in Section 2 uses x and ε instead of z and r; it should read {y : ||z−y|| < r}.","section":"Notation in Section 2"},{"comment":"The displayed formula for s(r,q) is garbled in the typeset footnote; the derivation in Lemma 3.14 suggests s(r,q)=r^{1/(1−q)} q^{q/(1−q)} (1−q), which should be stated cleanly.","section":"Theorem 2.10, footnote 3"},{"comment":"The extension to generic norms is asserted without proof, while Lemma 3.4 relies on strict convexity of the Euclidean norm for uniqueness of the intersection point; this remark should either be proved or phrased as an open direction.","section":"Remark 2.15"}],"recommendation":"major_revision","confidential_remarks":"The main theorem is false as stated because of the exclusion in Definition 2.6, but the error is local and readily fixable by removing that exclusion. The placeholder theorem number and notation typos should be addressed in revision. The novelty boundary with the companion paper [SC19] should also be confirmed, since the dictionary-learning application is outsourced to that paper."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main result here is real: an exact convex-concave min-max reformulation of the delta-regularized linear inverse problem (Theorem 2.10, problem 18), with an explicit saddle-point characterization. The derivation from gauge duality is mostly self-contained and the chain from Lemmas 2.5, 3.2, 3.4, 3.7, Proposition 3.10 to Theorem 2.10 is coherent. That is a legitimate extension of the CRPW12 gauge framework, and the dictionary-learning motivation is sensible. The companion paper [SC19] apparently uses this reformulation, and the abstract's algorithmic claims should be explicitly deferred to it.\n\nThe soft spot is more than cosmetic. The stress-test note is correct: Definition 2.6 excludes λ with ||λ|| ≤ ε, but in a valid 1D instance (Hn=R, c(f)=|f|/2, p=1, δ=0, ε=1, x=3) the unique dual optimum is λ=0.5 with ||λ||=0.5<1, so Λ_delta is empty and yet the dual problem has an optimum. That breaks Theorem 2.7(ii)(b) and Theorem 2.10(b) as stated. The fix is simple: drop the exclusion λ∉B[0,ε]; λ=0 already fails ||λ||'_phi=1. The saddle point at (h,λ)=(2,1/8) in that example is exactly the scaled Λ_delta once the exclusion is removed, so the intended theory survives. This is a statement-level bug, not a collapse of the main idea.\n\nAlso: the proof section contains a literal 'Proof of Theorem ??' placeholder, and the ball definitions at the top of Section 2 have typos (B(z,r) uses ||x−y|| instead of ||z−y||). The abstract overstates what is proven here versus in [SC19]. The uniqueness argument in Lemma 3.4 relies on strict convexity of the Euclidean ball; for generic norms the residual-direction characterization may fail, and Remark 2.15 is only a sketch. These are fixable but need attention.\n\nWho this is for: people working on convex duality for inverse problems or on dictionary learning with hard error constraints. It deserves a serious referee—the core idea is novel and the derivation is mostly correct, but the manuscript needs a careful revision. I would send it to peer review with the expectation of major revision, and I would not cite it in its current arXiv form.","headline":"A genuinely novel min-max reformulation of gauge-based linear inverse problems with a mostly sound derivation, but a real bug in the definition of the optimal dual set makes two theorem statements false as written.","tokens_in":31075,"tokens_out":4878,"would_cite":false,"duration_ms":44133,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C46","49N15"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that the gauge-cost linear inverse problem (8) is exactly equivalent to the convex-concave min-max game (18), whose value is a known power of the optimal cost and whose saddle points are the scaled primal-dual optimal…","keywords":["convex duality","linear inverse problems","gauge function","min-max reformulation","saddle point","dictionary learning","basis pursuit denoising"],"falsifier":"Numerically solve a two-dimensional instance with an $\\ell^\\infty$ error constraint and a two-atom dictionary chosen so that the optimal reconstruction lies on a face of the error ball; if the set of optimal dual variables is not a single scaled residual but a face of the dual unit ball, then Lemma 3.8 and Proposition 3.10 fail, and the min-max value formula of Theorem 2.10 would have to be modified for that norm. The paper's Remark 2.15 sketches generic norms without re-proving uniqueness, so the observable gap is precisely the non-strictly-convex case.","tokens_in":29892,"feed_emoji":"⚖️","tokens_out":14563,"duration_ms":111613,"temperature":0.7,"pith_summary":"This paper establishes that a broad class of ill-posed linear inverse problems—recovering a signal from noisy linear measurements under a convex gauge cost—can be rewritten, without loss, as a convex-concave min-max problem. The reformulation is exact: its optimal value is a known power of the original optimal cost, its minimizers are the scaled primal solutions, and when a dual optimum exists its saddle points are precisely the scaled primal-dual optimal pairs. This matters for computation, because the min-max form supports simple ascent-descent iterations, and for dictionary learning, because it moves the dictionary variable into the cost in a way that permits alternating updates.","feed_headline":"One min-max game solves gauge-cost linear inverse problems","feed_subtitle":"Its value equals a power of the original cost and turns dictionary learning into ascent-descent steps.","key_machinery":"The load-bearing object is the gauge body $S_\\delta(\\varphi,1) = \\bigcup_{h\\in V_c} B[\\varphi(h),\\delta]$ and its gauge function $\\|z\\|_\\varphi = \\min\\{r\\ge 0 : z \\in r S_\\delta(\\varphi,1)\\}$. The argument uses the dual gauge $\\|\\lambda\\|'_\\varphi = \\sup_{z\\in S_\\delta(\\varphi,1)}\\langle \\lambda, z\\rangle$ as the constraint set of the dual problem, and the unique intersection point $y^\\ast$ of $B[x,\\epsilon]$ with $(C_\\delta)^{1/p}S_\\delta(\\varphi,1)$, whose uniqueness rests on strict convexity of the Euclidean norm. That uniqueness converts Hahn-Banach separation into a single residual direction $x-\\varphi(f_x)$, yielding the exact dual variable and, after scalarization, the min-max value.","core_discovery":"The central discovery is Theorem 2.10: for the coding problem (8) with a positively homogeneous, pseudo-convex, inf-compact cost $c$, the value of the inf-sup problem (18) equals $s(r,q) C_\\delta(\\varphi,x,\\epsilon)^{q/(p(1-q))}$, the minimizer set of the outer variable $h$ is exactly $(1/C_\\delta^{1/p}) F_\\delta(\\varphi,x,\\epsilon)$, and when $\\Lambda_\\delta$ is nonempty the saddle points are exactly these $h^\\ast$ paired with scaled dual variables from $\\Lambda_\\delta$. The proof passes through Lemma 3.4, which pins down a unique intersection point $y^\\ast$ of the Euclidean error ball with the scaled gauge body; every separating functional is then proportional to the residual $x-\\varphi(f_x)$, which fixes the dual variable exactly.","pith_inferences":["Editorial inference: the exact equality of values suggests that any algorithm that provably finds a saddle point of (18) also solves the original hard-constrained recovery problem, so the min-max form could double as a certificate for recovery guarantees, not just a computational heuristic.","Editorial inference: if the error were measured in a norm whose unit ball is not strictly convex (say $\\ell^\\infty$), the intersection of the error ball with the scaled gauge body could be a face rather than a single point, so the residual-direction characterization of the dual would likely fail; this is directly testable in two dimensions.","Editorial inference: a stochastic/online variant of the dictionary-learning update is a natural next step, since the reformulated objective is linear in $D$ and concave in each $\\lambda_t$, so the empirical average could be replaced by online samples; the paper gestures at online updates but does not develop the protocol."],"forward_implications":["Any gauge-cost linear inverse problem can be solved by ascent-descent on (18), and the optimal dual variable can be read off from the primal optimal solution without solving a separate dual problem.","In dictionary learning, replacing the encoding cost $C_\\delta(D,x,\\epsilon)$ by the min-max form puts the dictionary $D$ explicitly in the objective; the update over $D$ with the $h_t,\\lambda_t$ held fixed is then a linear-sup problem for which simple ascent-descent iterations apply.","In the boundary case $\\delta=0$ with the open error ball missing the image of $\\varphi$, the dual problem has a finite supremum but no optimal solution, and the min-max problem has no saddle point—only a value.","For basis pursuit denoising with $\\ell^1$ cost and $\\ell^2$ error, the reformulation is $\\min_{\\|h\\|_1\\le 1}\\sup_{\\lambda: \\langle\\lambda,x\\rangle-\\epsilon\\|\\lambda\\|_2>0} 2\\sqrt{\\langle\\lambda,x\\rangle-\\epsilon\\|\\lambda\\|_2} - (\\delta\\|\\lambda\\|_2+\\langle\\lambda,\\varphi(h)\\rangle)$.","The same construction extends to cone-constrained variants such as non-negative matrix factorization by replacing $V_c$ with $V_c\\cap Q$, with the gauge body and dual defined relative to the smaller set."],"supporting_citations":[{"why":"Supplies the atomic-set and gauge-function view of linear inverse problems that motivates the general cost (8) and the recovery guarantees.","marker":"[CRPW12]"},{"why":"The authors' companion work, cited for the dictionary-learning algorithm and saddle-point guarantees that use the min-max reformulation.","marker":"[SC19]"},{"why":"Provides the basis pursuit denoising setup whose dual (20) and min-max (21) forms the paper works out.","marker":"[EA06]"},{"why":"Background on compressed sensing and noisy measurements that motivates the epsilon-error constraint.","marker":"[CW08]"},{"why":"Weierstrass theorem, referenced to guarantee existence of optimal solutions to the feasible coding problem.","marker":"[R`64]"}],"fun_headline_variants":["Min-max reformulation turns LIP into ascent-descent steps","Inf-sup value equals LIP cost, saddle points exact","One convex-concave game solves linear inverse problems","Dictionary learning via a single min-max game"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument leans on the Euclidean norm for the measurement error: its strictly convex balls make the error ball and the scaled gauge body meet at exactly one point, and that uniqueness fixes the optimal dual variable as a residual direction; with a generic norm this uniqueness—and with it the exact dual and min-max characterizations—can fail.","fun_headline_variants_meta":{"raw":{"variants":["Min-max reformulation turns LIP into ascent-descent steps","Inf-sup value equals LIP cost, saddle points exact","One convex-concave game solves linear inverse problems","Dictionary learning via a single min-max game"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000943,"raw_usage":{"total_tokens":3973,"prompt_tokens":832,"completion_tokens":3141,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":448,"completion_tokens_details":{"reasoning_tokens":3076}},"tokens_in":448,"tokens_out":3141,"duration_ms":23670,"temperature":1.0,"reasoning_tokens":3076,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:57:42.800524+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Numerically solve a two-dimensional instance with an $\\ell^\\infty$ error constraint and a two-atom dictionary chosen so that the optimal reconstruction lies on a face of the error ball; if the set of optimal dual variables is not a single scaled residual but a face of the dual unit ball, then Lemma 3.8 and Proposition 3.10 fail, and the min-max value formula of Theorem 2.10 would have to be modified for that norm. The paper's Remark 2.15 sketches generic norms without re-proving uniqueness, so the observable gap is precisely the non-strictly-convex case.","supporting_citations":[],"review_version":1}