On Convex Duality in Linear Inverse Problems

Debasish Chatterjee; Mohammed Rayyan Sheriff

REVIEW 2 major objections 5 minor 16 references

On Convex Duality in Linear Inverse Problems

T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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…

desk verdict 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. read the letter →

arxiv 1908.06065 v3 pith:PDQKA3FL submitted 2019-08-16 cs.LG eess.SPmath.OCstat.ML

Mohammed Rayyan Sheriff , Debasish Chatterjee This is my paper · ORCID

classification cs.LGeess.SPmath.OCstat.ML MSC 90C2590C4649N15

keywords convexdualitylinearinverseproblemsgaugefunctionmin-maxreformulationsaddlepointdictionarylearningbasispursuitdenoising

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

The 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.

Also: 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.

Who 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.

Referee Report

2 major / 5 minor

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.

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 (2)

[Definition 2.6 and Theorem 2.7] 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.
[Theorem 2.10 and Lemma 3.14] 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.

minor comments (5)

[Section 3, proof of Theorem 2.10] The proof heading appears as 'Proof of Theorem ??' instead of a numbered theorem; this placeholder should be corrected before publication.
[Definition 2.4] Definition 2.4 writes φ : Hn → RK, but the correct domain/codomain is RK → Hn, as used in Definition 2.2 and throughout the paper.
[Notation in Section 2] The definition of B(z,r) in Section 2 uses x and ε instead of z and r; it should read {y : ||z−y|| < r}.
[Theorem 2.10, footnote 3] 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.
[Remark 2.15] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the min-max and duality theorems are proved from first principles within the paper; the companion-paper self-citation supports dictionary-learning extensions but is not load-bearing for the central equivalence.

full rationale

The derivation chain is self-contained. The gauge function, its dual, the identity (13), and the strong-duality theorem (2.7) are all proved inside the paper from convex-geometric separation arguments (Lemmas 3.1-3.11), not imported from external results. The min-max theorem (2.10) is obtained by reducing (18) to Lemma 3.13's eta_h and Lemma 3.14's explicit sup evaluation; both lemmas are proved in the text, and the only input to the reduction is the definition of C_delta plus the already-proved duality. Definition 2.6's characterization of Lambda_delta uses <lambda,x> - epsilon||lambda|| = C_delta^(1/p) and ||lambda||'_phi = 1, but these are shown to be exactly the optimality conditions of (16) in Theorem 2.7, so the definition is a proved characterization rather than a tautological restatement. There are no fitted parameters, no data subsets, and no empirical predictions that could be forced by construction. The only self-citation is to the companion paper [SC19] for saddle-point and convergence properties of the dictionary-learning algorithm; that part is not proven here, but it is not needed to establish Theorem 2.10, and citing a companion for an extension is not circular. A skeptical counterexample concerning Definition 2.6's exclusion lambda not in B[0,epsilon] would be a correctness or bug issue, not a circularity, since the equivalence proof does not reduce to that exclusion by construction.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters are fitted; the constants r and q in Corollary 2.11 are set to normalize the prefactor. All assumptions are standard convex analysis or the stated regularity of the cost function. No new physical or mathematical entities are postulated.

assumptions (5)

domain assumption Assumption 2.1: the cost function c is positively homogeneous, with convex unit sublevel set Vc, and Vc is compact (inf-compactness).
The entire gauge-duality framework requires c to be a gauge-like function. This assumption is stated in Section 2 and used throughout; it is reasonable for atomic-norm formulations but restricts applicability.
standard math Finite-dimensional Hilbert space with Euclidean norm.
Used for strict convexity of the ball in Lemma 3.4 and projection arguments in Proposition 3.10.
standard math Hahn-Banach separation theorem for compact convex sets.
Invoked in Section 3.0.2 and Lemma 3.13 to separate B[x,epsilon] and S_delta.
standard math Weierstrass theorem for existence of optima of continuous coercive functions.
Cited as [R64, Theorem 4.16] in Section 2.1 to guarantee existence of solutions to the LIP.
domain assumption Slater's condition for strong duality in Lemma 3.13.
The paper asserts strict feasibility of lambda = alpha x; the proof of strong duality for problem (36) depends on this constraint qualification.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On Convex Duality in Linear Inverse Problems." pith.science (2026). https://pith.science/paper/PDQKA3FL

@misc{pith2026190806065,
  author       = {Pith},
  title        = {Pith review of: On Convex Duality in Linear Inverse Problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PDQKA3FL}},
  note         = {Machine review of arXiv:1908.06065}
}

read the original abstract

In this article we dwell into the class of so called ill posed Linear Inverse Problems (LIP) in machine learning, which has become almost a classic in recent times. The fundamental task in an LIP is to recover the entire signal / data from its relatively few random linear measurements. Such problems arise in variety of settings with applications ranging from medical image processing, recommender systems etc. We provide an exposition to the convex duality of the linear inverse problems, and obtain a novel and equivalent convex-concave min-max reformulation that gives rise to simple ascend-descent type algorithms to solve an LIP. Moreover, such a reformulation is crucial in developing methods to solve the dictionary learning problem with almost sure recovery constraints.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

[1]

K-svd: An algorithm for designing overcomplete dictionaries for sparse representation

Michal Aharon, Michael Elad, and Alfred Bruckstein. K-svd: An algorithm for designing overcomplete dictionaries for sparse representation. IEEE Transactions on signal processing , 54(11):4311--4322, 2006

work page 2006
[2]

Exact matrix completion via convex optimization

Emmanuel J Cand \`e s and Benjamin Recht. Exact matrix completion via convex optimization. Foundations of Computational mathematics , 9(6):717, 2009

work page 2009
[3]

The convex geometry of linear inverse problems

Venkat Chandrasekaran, Benjamin Recht, Pablo A Parrilo, and Alan S Willsky. The convex geometry of linear inverse problems. Foundations of Computational mathematics , 12(6):805--849, 2012

work page 2012
[4]

Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information

Emmanuel J Cand \`e s, Justin Romberg, and Terence Tao. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on information theory , 52(2):489--509, 2006

work page 2006
[5]

Stable signal recovery from incomplete and inaccurate measurements

Emmanuel J Candes, Justin K Romberg, and Terence Tao. Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences , 59(8):1207--1223, 2006

work page 2006
[6]

An introduction to compressive sampling [a sensing/sampling paradigm that goes against the common knowledge in data acquisition]

Emmanuel J Cand \`e s and Michael B Wakin. An introduction to compressive sampling [a sensing/sampling paradigm that goes against the common knowledge in data acquisition]. IEEE signal processing magazine , 25(2):21--30, 2008

work page 2008
[7]

Compressed sensing

David L Donoho et al. Compressed sensing. IEEE Transactions on information theory , 52(4):1289--1306, 2006

work page 2006
[8]

Image denoising via sparse and redundant representations over learned dictionaries

Michael Elad and Michal Aharon. Image denoising via sparse and redundant representations over learned dictionaries. IEEE Transactions on Image processing , 15(12):3736--3745, 2006

work page 2006

Show all 16 references

[9]

Non-negative matrix factorization with sparseness constraints

Patrik O Hoyer. Non-negative matrix factorization with sparseness constraints. Journal of machine learning research , 5(Nov):1457--1469, 2004

2004
[10]

Learning the parts of objects by non-negative matrix factorization

Daniel D Lee and H Sebastian Seung. Learning the parts of objects by non-negative matrix factorization. Nature , 401(6755):788, 1999

1999
[11]

Algorithms for non-negative matrix factorization

Daniel D Lee and H Sebastian Seung. Algorithms for non-negative matrix factorization. In Advances in neural information processing systems , pages 556--562, 2001

2001
[12]

Mairal, F

J. Mairal, F. Bach, J. Ponce, and G. Sapiro. Online learning for matrix factorization and sparse coding. Journal of Machine Learning Research , 11(Jan):19--60, 2010

2010
[13]

Principles of mathematical analysis , volume 3

Walter Rudin et al. Principles of mathematical analysis , volume 3. McGraw-hill New York, 1964

1964
[14]

Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization

Benjamin Recht, Maryam Fazel, and Pablo A Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM review , 52(3):471--501, 2010

2010
[15]

Dictionary learning with almost sure error constraints

Mohammed Rayyan Sheriff and Debasish Chatterjee. Dictionary learning with almost sure error constraints. arXiv preprint arXiv:1910.08828 , 2019

1910 arXiv
[16]

Tosic and P

I. Tosic and P. Frossard. Dictionary learning. IEEE Signal Processing Magazine , 28(2):27--38, 2011

2011

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

K-svd: An algorithm for designing overcomplete dictionaries for sparse representation

Michal Aharon, Michael Elad, and Alfred Bruckstein. K-svd: An algorithm for designing overcomplete dictionaries for sparse representation. IEEE Transactions on signal processing , 54(11):4311--4322, 2006

work page 2006

[2] [2]

Exact matrix completion via convex optimization

Emmanuel J Cand \`e s and Benjamin Recht. Exact matrix completion via convex optimization. Foundations of Computational mathematics , 9(6):717, 2009

work page 2009

[3] [3]

The convex geometry of linear inverse problems

Venkat Chandrasekaran, Benjamin Recht, Pablo A Parrilo, and Alan S Willsky. The convex geometry of linear inverse problems. Foundations of Computational mathematics , 12(6):805--849, 2012

work page 2012

[4] [4]

Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information

Emmanuel J Cand \`e s, Justin Romberg, and Terence Tao. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on information theory , 52(2):489--509, 2006

work page 2006

[5] [5]

Stable signal recovery from incomplete and inaccurate measurements

Emmanuel J Candes, Justin K Romberg, and Terence Tao. Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences , 59(8):1207--1223, 2006

work page 2006

[6] [6]

An introduction to compressive sampling [a sensing/sampling paradigm that goes against the common knowledge in data acquisition]

Emmanuel J Cand \`e s and Michael B Wakin. An introduction to compressive sampling [a sensing/sampling paradigm that goes against the common knowledge in data acquisition]. IEEE signal processing magazine , 25(2):21--30, 2008

work page 2008

[7] [7]

Compressed sensing

David L Donoho et al. Compressed sensing. IEEE Transactions on information theory , 52(4):1289--1306, 2006

work page 2006

[8] [8]

Image denoising via sparse and redundant representations over learned dictionaries

Michael Elad and Michal Aharon. Image denoising via sparse and redundant representations over learned dictionaries. IEEE Transactions on Image processing , 15(12):3736--3745, 2006

work page 2006