Pith. sign in

REVIEW 1 major objections 4 minor 41 references

Stable Recovery of Regularized Linear Inverse Problems

T0 review · 1 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash

Pith's one-line read For continuous convex regularizers, stable recovery is exactly a second-order tangent-cone condition: the kernel of the observation map meets the conjugate subdifferential's tangent cone only at zero.

desk verdict Genuinely new geometric characterization of stable recovery, but the sufficiency direction leans on an unstated external convergence lemma that a referee must verify. read the letter →

arxiv 2412.11313 v2 pith:P3C6GJ7A submitted 2024-12-15 math.OC

classification math.OC MSC 49J5249J5349K4052A4190C2590C31
keywords stablerecoverylinearinverseproblemsregularizationmethodssecond-orderanalysistangentconegroupsparsityisotropictotalvariationconvexregularizers
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 tries to settle exactly when a convex regularized linear inverse problem recovers the true signal at the same rate as the noise level, the property called stable recovery. The central claim is a characterization: for any continuous convex regularizer, an optimal solution $x_0$ is stably recoverable if and only if the kernel of the measurement operator meets a certain tangent cone of the conjugate regularizer's subdifferential image only at zero. This is a second-order condition, and it explains why earlier first-order sufficient conditions (null space property, nondegeneracy source condition with restricted injectivity, minimum gain property) are not necessary: they imply sharp minima, and sharp minima imply the new condition but not conversely. The paper then derives new sufficient conditions for analysis group sparsity and isotropic total variation problems and reports numerical evidence that most strong non-sharp solutions of group sparsity problems are stably recoverable. This matters because it determines when linear convergence is guaranteed even in non-polyhedral problems where uniqueness alone is not enough.

What carries the argument

The load-bearing object is the tangent/contingent cone $T_{\partial R^*(\operatorname{Im}\Phi^*)}(x_0)$, the set of directions $w$ for which there are times $t_k \downarrow 0$ and vectors $w_k \to w$ with $x_0 + t_k w_k$ inside the image of the conjugate subdifferential restricted to $\operatorname{Im}\Phi^*$. The paper uses this set as a second-order derivative object: it records the directions in which the subdifferential of the conjugate regularizer, evaluated along the adjoint range, bends at $x_0$, and its intersection with $\operatorname{Ker}\Phi$ decides stability. Fenchel duality and subdifferential calculus set up the correspondence between primal feasible directions and dual certificates, while the critical cone and the set $W(x_0)$ are used to specialize the condition to analysis group sparsity problems, eventually yielding nonconvex quadratic conditions that can be checked numerically.

What would settle it

Compute, for a continuous convex regularizer $R$ and a unique minimizer $x_0$ of the noiseless problem, a sequence of noisy data $y_k$ with $\|y_k - y_0\| \le \delta_k \to 0$ whose regularized minimizers $x_k$ satisfy $\|x_k - x_0\|/\delta_k \to \infty$ while condition (3.8) holds; exhibiting such a sequence would refute the characterization, and the explicit matrices in Examples 3.2 and 3.4 provide small cases where this can be checked by hand. Similarly, a case where (3.8) fails but all regularized minimizers still converge at the linear rate would refute the converse direction.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 3.3: with $R$ a continuous convex function and $x_0$ an optimal solution of $\min R(x)$ subject to $\Phi x = y_0$, stable recovery occurs if and only if $\operatorname{Ker}\Phi \cap T_{\partial R^*(\operatorname{Im}\Phi^*)}(x_0) = \{0\}$, where $T$ denotes the contingent/tangent cone, $\partial R^*$ the subdifferential of the Fenchel conjugate of $R$, and $\operatorname{Im}\Phi^*$ the range of the adjoint operator. The proof builds explicit noisy problems to show that any nonzero common direction would let noise push regularized minimizers away at a nonlinear rate, and conversely uses the condition to rule out any sequence of minimizers that fails to approach $x_0$ linearly. The paper argues that this condition is genuinely second-order: it records directions in which the conjugate subdifferential image bends at $x_0$, not just first-order descent directions. It shows by example that stable recovery can hold without sharp minima, that strong minima do not always imply stable recovery, and that for piecewise linear-quadratic regularizers stable recovery is equivalent to solution uniqueness. For smooth convex regularizers the condition becomes $\operatorname{Ker}\Phi \cap \operatorname{Ker}\nabla^2 R(x_0) = \{0\}$, which is exactly the strong minimum condition.

Load-bearing premise

The load-bearing assumption is the cited result that once $x_0$ is the unique solution of the noiseless problem, every sequence of regularized minimizers converges to $x_0$ as the noise vanishes; the proof of the 'if' direction imports this theorem without re-deriving it.

Editorial extensions

If this is right

  • If the theorem is right, stable recovery for any continuous convex regularizer is a second-order property, and all earlier first-order sufficient conditions are merely routes to the tangent-cone condition.
  • For piecewise linear-quadratic regularizers (elastic net, Huber norm, discrete Blake-Zisserman), stable recovery and solution uniqueness coincide, extending the known $\ell^1$ equivalence to a broad class.
  • For smooth convex regularizers, stable recovery is equivalent to strong minimality, so the condition is checkable as $\operatorname{Ker}\Phi \cap \operatorname{Ker}\nabla^2 R(x_0) = \{0\}$.
  • For analysis group sparsity problems, conditions (4.45) and (4.50) certify stable recovery at unique non-sharp minimizers and are independent of sharp minima.
  • Numerical experiments suggest that in random Gaussian group-sparsity and total-variation problems, most strong non-sharp optimal solutions pass the new stability test.

Reading between the lines

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

  • The paper does not pursue this, but the tangent-cone condition could be turned into a numerical certificate: an optimization over $\operatorname{Ker}\Phi$ and the tangent cone whose zero optimal value verifies stable recovery without solving the regularized problems.
  • Beyond the paper, the characterization suggests that measurement thresholds for group-sparse recovery are governed by this second-order cone rather than by sharp-minimum conditions, so random matrix theory for cones could yield direct bounds on the number of measurements needed for stable recovery.
  • For isotropic total variation the equality in Theorem 4.3 fails because the discrete gradient is not surjective, so the paper's sufficient condition leaves a gap; closing it likely requires a direct computation of the tangent cone for the TV regularizer, which the paper leaves open.
  • The same tangent-cone strategy may transfer to nuclear norm regularization, where the conjugate subdifferential image has known structure, potentially characterizing stable recovery in low-rank inverse problems.
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.

Referee Report

1 major / 4 minor

Summary. The paper studies stable recovery, meaning the linear (order δ) convergence of Tikhonov-regularized solutions to the true signal, for convex regularized linear inverse problems in finite dimensions. The central result, Theorem 3.3, characterizes stable recovery at an optimal solution x0 of the constrained problem (3.1) by the tangent-cone condition Ker Φ ∩ T_{∂R*(Im Φ*)}(x0) = {0}. The authors then derive consequences for smooth regularizers, for convex piecewise linear-quadratic regularizers, and for analysis group sparsity (ℓ1/ℓ2) and isotropic total variation regularizers, giving explicit sufficient conditions (Corollaries 4.8 and 4.9) and reporting numerical experiments on those two problem classes.

Significance. If Theorem 3.3 holds as stated, it is a substantial contribution: it gives a complete geometric characterization of stable recovery that exposes its second-order nature, and it shows that stable recovery can occur at non-sharp minimizers where the classical sufficient conditions (null space property, nondegeneracy source condition with restricted injectivity, minimum gain property) all fail. The examples in Section 3 are well constructed and illustrate the new phenomena convincingly. The extension to convex piecewise linear-quadratic regularizers (Corollary 3.8) and the group-sparsity sufficient conditions are useful and appear to be new. The numerical experiments, while not rigorous, provide encouraging evidence that the conditions are practical. The main theorem, however, has a load-bearing dependency on an external convergence result that is neither stated nor proved in the paper, and this gap must be addressed before the central characterization can be considered fully justified.

major comments (1)
  1. [Section 3, proof of Theorem 3.3 (sufficiency direction)] The assertion immediately after (3.10) that "Since x0 is the unique solution of problem (3.1), it follows from [21, Proposition 3.1 and Remark 3.2] that xk → x0" is load-bearing for the 'if' direction: it is the only mechanism that yields tk ↓ 0 and hence the unit vector w in the tangent-cone intersection that contradicts (3.8). The paper neither states the cited proposition nor verifies its hypotheses under the assumptions of Theorem 3.3 (R continuous convex, x0 optimal). If [21, Proposition 3.1] requires, for instance, coercivity of R, boundedness of the feasible set, or some form of strong/sharp minimum, then the theorem as stated for all continuous convex regularizers is not justified. Please provide a self-contained proof of the convergence of the Tikhonov minimizers to the unique solution of (3.1), or state the proposition explicitly and confirm that its assumptions are satisfied under the paper's hypotheses.
minor comments (4)
  1. [Definition 3.1 and Section 3] The definition of stable recovery quantifies over "any optimal solution x(y,µ) of problem (3.3)" but the paper does not discuss existence of these minimizers for arbitrary continuous convex R. If the Tikhonov problem has no minimizer for some small δ, the property is vacuous; please add a short existence argument or an explicit standing assumption that minimizers exist for the relevant parameters.
  2. [Example 4.10, equation (4.51)] The optimization problem is stated as min over x ∈ R^6, but the regularizer uses four groups of two variables and the vector x0 has eight components; the correct setting is x ∈ R^8.
  3. [Section 5, problems (5.3)–(5.5)] The verification of conditions (4.45) and (4.50) is performed by solving nonconvex quadratic problems with Gurobi's NonConvex parameter and a 5-second time limit; Gurobi's nonconvex solver is a heuristic and does not provide global optimality certificates for general nonconvex QPs. Please state that the numerical conclusions are indicative rather than certified, or use a method that guarantees global optimality.
  4. [Definition 2.2 and references] The name "Crome" should be "Cromme" to match reference [14], and the external results [20, Theorem 4.5] and [21, Proposition 3.1 and Remark 3.2] should be stated or precisely described in the paper rather than only cited.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the main iff characterization is not reduced to its inputs, though the sufficiency direction imports two load-bearing lemmas from same-group prior work.

full rationale

The central result, Theorem 3.3, proves equivalence between stable recovery and the geometric condition (3.8). The necessity direction is self-contained: it starts from a tangent-cone vector, constructs perturbed observations and Tikhonov minimizers, and applies the definition of stable recovery directly; no equation is defined in terms of the conclusion. The sufficiency direction uses two cited results from prior work with overlapping authorship: [20, Theorem 4.5] for solution uniqueness and [21, Proposition 3.1 and Remark 3.2] for convergence xk -> x0. The convergence step is load-bearing because it is the mechanism producing the unit vector w that contradicts (3.8), and the paper does not restate or re-prove the cited proposition's hypotheses. However, this is a dependency or verifiability risk, not a circular reduction: the cited convergence lemma is a prior result about convergence, not the linear-rate stable-recovery conclusion of Theorem 3.3, and no equation in the present paper reduces to its own target by construction. The later sufficient conditions in Section 4 are algebraic applications of Theorem 3.3, and the numerical experiments test conditions rather than fit the theorem. Overall, the derivation chain is not circular; the score reflects the moderate reliance on same-group citations at a load-bearing point.

Assumptions & free parameters 1 free parameters · 6 assumptions · 0 invented entities

The central theorem introduces no fitted constants and no new physical or mathematical entities. The only hand-chosen numbers are experimental tolerances in Section 5, which are not part of the main derivation. The main external inputs are two prior theorems from the same research group, which are cited and used as black boxes.

free parameters (1)
  • Experimental classification tolerances = rho in (0.95, 1.05); norm threshold 0.99 for K; recovery tolerance 1e-3; QCQP optimality tolerance 1e-6
    Used only in Section 5 to decide which solutions are called sharp, non-sharp, recovered, and stable. These thresholds are chosen by hand and affect the reported percentages, but they do not enter the theoretical characterization.
assumptions (6)
  • standard math X and Y are finite-dimensional Euclidean spaces.
    Section 2: 'Throughout the paper, X and Y are Euclidean spaces.' Compactness and subsequence arguments in Theorem 3.3 rely on finite dimension.
  • domain assumption R is a continuous convex function on X.
    Theorem 3.3 assumes this; it guarantees local Lipschitzness, nonempty compact subdifferentials, and the duality relation (2.2).
  • domain assumption Optimal solutions of the Tikhonov problem P(y,mu) exist for the considered y and mu.
    Definition 3.1 refers to 'any optimal solution x(y,mu)'; existence is not proved for general continuous convex R but holds for the norms/seminorms used in applications.
  • standard math [20, Theorem 4.5]: solution uniqueness of (3.1) is characterized by Ker Phi intersect cone(dR*(v)-x0) = {0} for dual certificates v.
    Invoked in the proof of Theorem 3.3 to derive uniqueness from condition (3.8). This is an external result by the same group, not re-derived here.
  • standard math [21, Proposition 3.1 and Remark 3.2]: Tikhonov minimizers converge to x0 when x0 is the unique solution.
    Used in the 'if' direction of Theorem 3.3 to guarantee xk -> x0 and tk = ||xk-x0|| down to 0; this convergence is the load-bearing bridge in the contradiction proof.
  • standard math For convex piecewise linear-quadratic R, the graph of dR* is piecewise polyhedral and projections of polyhedra are polyhedra.
    Used in Corollary 3.8; cited to Rockafellar-Wets [35].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Stable Recovery of Regularized Linear Inverse Problems." pith.science (2026). https://pith.science/paper/P3C6GJ7A

@misc{pith2026241211313,
  author       = {Pith},
  title        = {Pith review of: Stable Recovery of Regularized Linear Inverse Problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/P3C6GJ7A}},
  note         = {Machine review of arXiv:2412.11313}
}
read the original abstract

Recovering a low-complexity signal from its noisy observations by regularization methods is a cornerstone of inverse problems and compressed sensing. Stable recovery ensures that the original signal can be approximated linearly by optimal solutions of the corresponding Morozov or Tikhonov regularized optimization problems. In this paper, we propose new characterizations for stable recovery in finite-dimensional spaces, uncovering the role of nonsmooth second-order information. These insights enable a deeper understanding of stable recovery and their practical implications. As a consequence, we apply our theory to derive new sufficient conditions for stable recovery of the analysis group sparsity problems, including the group sparsity and isotropic total variation problems. Numerical experiments on these two problems give favorable results about using our conditions to test stable recovery.

Figures

Figures reproduced from arXiv: 2412.11313 by the authors.

Figure 1
Figure 1. below illustrates the success rate of the above regularization method when Φ ∈ Rm×n is a uniform Gaussian matrix for problem (1.2) in two different cases: (a) The group sparsity reg￾ularization problems [22, 24, 33, 40] with the ℓ1/ℓ2 norm R(x) = ∥x∥1,2 in Rn of recovering signals x0 ∈ R2000 with 100 non-overlap groups of 20 elements and 10 nonzero active groups; (b) The isotropic total variation problems [11, 36] w… view at source ↗
Figure 2
Figure 2. Group sparsity problems with different active groups of the signals [PITH_FULL_IMAGE:figures/full_fig_p026_2.png] view at source ↗
Figure 3
Figure 3. Images randomly sampled from the Extended MNIST dataset [PITH_FULL_IMAGE:figures/full_fig_p027_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Isotropic total variation problems with different group sparsity of the images’ gradients. [PITH_FULL_IMAGE:figures/full_fig_p028_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

41 extracted references · 40 canonical work pages

  1. [20]

    Solution uniqueness of convex optimization problems via the radial cone

    J. Fadili, T. T. Nghia, and D. N. Phan. Solution uniqueness of convex optimization problems via the radial cone. arXiv preprint arXiv:2401.10346, 2024

  2. [1]

    Aubin and H

    J.-P . Aubin and H. Frankowska. Set-valued analysis , volume 2 of Systems & Control: Foundations & Applications. Birkh ¨auser Boston, Inc., Boston, MA, 1990

  3. [2]

    Bello-Cruz, G

    Y. Bello-Cruz, G. Li, and T. T. Nghia. On the linear convergence of forward–backward splitting method: Part i—convergence analysis. Journal of Optimization Theory and Applications, 188:378–401, 2021

  4. [3]

    Benning and M

    M. Benning and M. Burger. Modern regularization methods for inverse problems. Acta Numerica, 27:1–111, 2018

  5. [4]

    Blake and A

    A. Blake and A. Zisserman. Visual reconstruction. MIT Press Series in Artificial Intelligence. MIT Press, Cambridge, MA, 1987

  6. [5]

    J. F. Bonnans and A. Shapiro. Perturbation analysis of optimization problems. Springer Science & Business Media, 2000. 28

  7. [6]

    A. M. Bruckstein, D. L. Donoho, and M. Elad. From sparse solutions of systems of equations to sparse modeling of signals and images. SIAM Rev., 51(1):34–81, 2009

  8. [7]

    Cand `es and B

    E. Cand `es and B. Recht. Simple bounds for recovering low-complexity models. Math. Program., 141(1- 2, Ser. A):577–589, 2013

Show all 41 references
  1. [8]

    E. J. Cand `es and B. Recht. Exact matrix completion via convex optimization. Found. Comput. Math. , 9(6):717–772, 2009

  2. [9]

    E. J. Candes, J. K. Romberg, and T. Tao. Stable signal recovery from incomplete and inaccurate mea- surements. Communications on Pure and Applied Mathematics, 59(8):1207–1223, 2006

  3. [10]

    E. J. Candes and T. Tao. Decoding by linear programming.IEEE Trans. Inform. Theory, 51(12):4203–4215, 2005

  4. [11]

    Chambolle and T

    A. Chambolle and T. Pock. A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vision, 40(1):120–145, 2011

  5. [12]

    Chandrasekaran, B

    V . Chandrasekaran, B. Recht, P . A. Parrilo, and A. S. Willsky. The convex geometry of linear inverse problems. Foundations of Computational Mathematics, 12(6):805–849, 2012

  6. [13]

    Cohen, S

    G. Cohen, S. Afshar, J. Tapson, and A. van Schaik. Emnist: Extending mnist to handwritten letters. In 2017 International Joint Conference on Neural Networks (IJCNN), pages 2921–2926, 2017

  7. [14]

    L. Cromme. Strong uniqueness: A far-reaching criterion for the convergence analysis of iterative procedures. Numerische Mathematik, 29(2):179–193, 1978

  8. [15]

    Diamond and S

    S. Diamond and S. Boyd. CVXPY: A Python-embedded modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1–5, 2016

  9. [16]

    D. L. Donoho, M. Elad, and V . N. Temlyakov. Stable recovery of sparse overcomplete representations in the presence of noise. IEEE Transactions on Information Theory, 52(1):6–18, 2005

  10. [17]

    D. L. Donoho and X. Huo. Uncertainty principles and ideal atomic decomposition. IEEE Trans. Inform. Theory, 47(7):2845–2862, 2001

  11. [18]

    H. W. Engl, M. Hanke, and A. Neubauer. Regularization of Inverse Problems , volume 375. Springer Science & Business Media, 1996

  12. [19]

    Fadili, T

    J. Fadili, T. T. Nghia, and D. N. Phan. Geometric characterizations for strong minima with applications to nuclear norm minimization problems. arXiv preprint arXiv:2308.09224, 2023

  13. [21]

    Fadili, T

    J. Fadili, T. T. Nghia, and T. T. Tran. Sharp, strong and unique minimizers for low complexity robust recovery. Information and Inference: A Journal of the IMA, 12(3):1461–1513, 2023

  14. [22]

    Fadili, G

    J. Fadili, G. Peyr ´e, S. Vaiter, C. Deledalle, and J. Salmon. Stable recovery with analysis decomposable priors. International Conference on Sampling Theory and Application, 2013

  15. [23]

    Foucart and H

    S. Foucart and H. Rauhut. A mathematical introduction to compressive sensing . Applied and Numerical Harmonic Analysis. Birkh¨auser/Springer, New York, 2013

  16. [24]

    Grasmair

    M. Grasmair. Linear convergence rates for Tikhonov regularization with positively homogeneous functionals. Inverse Problems, 27(7):075014, 16, 2011

  17. [25]

    Grasmair, O

    M. Grasmair, O. Scherzer, and M. Haltmeier. Necessary and sufficient conditions for linear conver- gence of ℓ1-regularization. Communications on Pure and Applied Mathematics, 64(2):161–182, 2011

  18. [26]

    Gurobi Optimizer Reference Manual, 2024

    Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024

  19. [27]

    Haltmeier

    M. Haltmeier. Block-sparse analysis regularization of ill-posed problems via l2,1-minimization. In 2013 18th International Conference on Methods & Models in Automation & Robotics (MMAR) , pages 520–

  20. [28]

    J. He, C. Kan, and W. Song. On solution uniqueness and robust recovery for sparse regularization with a gauge: from dual point of view. arXiv preprint arXiv:2312.11168, 2023

  21. [29]

    P . J. Huber. Robust regression: asymptotics, conjectures and Monte Carlo. Ann. Statist., 1:799–821, 1973

  22. [30]

    V . A. Morozov. Regularization Methods for Ill-Posed Problems. CRC Press, Boca Raton, 1993

  23. [31]

    Paszke, S

    A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala. Pytorch: An imperative style, high-per...

  24. [32]

    B. T. Polyak. Introduction to Optimization. New York, Optimization Software, 1987

  25. [33]

    N. Rao, B. Recht, and R. Nowak. Universal measurement bounds for structured sparse signal recovery. In Artificial Intelligence and Statistics, pages 942–950. PMLR, 2012

  26. [34]

    R. T. Rockafellar. Convex analysis. Princeton, 1970

  27. [35]

    R. T. Rockafellar and R. J.-B. Wets. Variational Analysis. Springer Verlag, 1998

  28. [36]

    L. I. Rudin, S. Osher, and E. Fatemi. Nonlinear total variation based noise removal algorithms. Phys. D, 60(1-4):259–268, 1992. Experimental mathematics: computational issues in nonlinear science (Los Alamos, NM, 1991)

  29. [37]

    A. N. Tikhonov and V . J. Arsenin. Solutions of Ill-Posed Problems. Winston, 1977

  30. [38]

    Vaiter, M

    S. Vaiter, M. Golbabaee, J. Fadili, and G. Peyr´e. Model selection with low complexity priors.Information and Inference: A Journal of the IMA, 4(3):230–287, 2015

  31. [39]

    Vaiter, G

    S. Vaiter, G. Peyr ´e, and J. Fadili. Low complexity regularization of linear inverse problems. Sampling Theory, a Renaissance: Compressive Sensing and Other Developments, pages 103–153, 2015

  32. [40]

    Yuan and Y

    M. Yuan and Y. Lin. Model selection and estimation in regression with grouped variables. Journal of the Royal Statistical Society Series B: Statistical Methodology, 68(1):49–67, 2006

  33. [41]

    Zou and T

    H. Zou and T. Hastie. Regularization and variable selection via the elastic net. J. R. Stat. Soc. Ser. B Stat. Methodol., 67(2):301–320, 2005. 30

Pith tools

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