{"id":"fa2423ce-1b99-4566-b626-6be2930b29f2","arxiv_id":"1908.02503","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"An infimal-convolution reduction turns a non-convex two-penalty sparse recovery problem into a single-penalty problem with a cheap proximal step, and both it and the augmented counterpart converge linearly under standard conditions.","lead":"This paper studies numerical solvers for recovering sparse signals from noisy linear measurements when two penalties are used to encourage sparsity and suppress noise. It proves linear convergence for two solver families and proposes a reformulation that avoids a costly matrix computation, making large problems more tractable.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2.11 does not guarantee contraction: the second term in its displayed rate can push the constant above 1, so linear convergence of the infimal-convolution method is not proven as stated.","rationale":"The reader's weakest assumption focuses on the unproven convergence to a stationary point and the alpha threshold depending on d_min. Those are real but partly standard: the paper cites Kurdyka-Lojasiewicz results for convergence, and local convergence rates commonly depend on the limit point. The more load-bearing gap is that Theorem 2.11, as stated, does not prove a contraction factor below 1. Even if all the reader's conditions are granted, the second component of the rate, rho_{I^c}/(1+mu beta), can keep the overall constant above 1 unless beta is sufficiently large; the paper's Remark 2.12 sketches this but does not state or prove a quantitative condition. Since the central claim is linear convergence of the infimal-convolution reduction, this is a genuine correctness risk for the main novelty. The issue is addressable by adding assumptions (e.g., beta large enough or an RIP-type bound on the nullspace component) and proving C < 1, so the appropriate verdict remains conditional acceptance rather than rejection. Theorem 2.7 for the augmented formulation appears solid, and the numerical experiments give empirical support, which is why the concern is not fatal. The reader and I partially agree: we both see conditional gaps, but the missing contraction guarantee is more specific and more directly tied to the paper's advertised contribution.","tokens_in":18482,"tokens_out":25362,"duration_ms":234022,"concrete_test":"Compute the contraction constant C from Theorem 2.11 for the experimental setup of Section 3.2: A in R^{100 x 500} Gaussian, q = 1/2, alpha = 0.02, beta = 0.2, mu = 0.1, I = support of the recovered u*, and d_min = min_{i in I} |u*_i|. Evaluate rho_I, rho_{I^c}, and T, then check whether C < 1. If C >= 1, the theorem's bound is vacuous in the very regime the paper uses to demonstrate linear convergence. Then vary beta from 0.01 to 100 and find the smallest beta for which C < 1, comparing with the beta = 0.2 used in the paper.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Section A.5 derives for the infimal-convolution iterates the two inequalities ||(w^{k+1}-w*)_I|| <= rho_I (1-T)^{-1} ||w^k-w*|| and ||(w^{k+1}-w*)_{I^c}|| <= rho_{I^c} (1+mu beta)^{-1} ||w^k-w*||, where rho_I = ||P_I - mu A_I^T A||, rho_{I^c} = ||P_{I^c} - mu A_{I^c}^T A||, and T = alpha mu (1-q) (d_min/2)^{q-2}. Squaring and summing gives the stated constant C = sqrt( (rho_I/(1-T))^2 + (rho_{I^c}/(1+mu beta))^2 ). Linear convergence requires C < 1. Remark 2.12's condition alpha < alpha* only ensures the first summand is below 1; it does not control the second. For underdetermined A (m < n), the matrix I - mu A^T A has eigenvalue 1 on the nullspace of A, so rho_{I^c} can be close to 1; with moderate beta (e.g., beta = 0.2 in Section 3.2) the second term is not small. Consequently C can exceed 1, making Theorem 2.11 a bound with an unspecified constant rather than a linear convergence rate. The main claimed novelty for the infimal-convolution approach is therefore not established without an additional quantitative condition on beta or on the restricted conditioning of A.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript studies the multi-penalty regularization problem (2) with p=2 and 0<q<=1. It extends the augmented single-penalty reduction of [16] to the non-convex lq penalty and proposes a new reduction based on infimal convolution, leading to proximal-gradient algorithms (9) and (15). The paper claims linear convergence rates for both algorithms in Theorems 2.7 and 2.11, with parameter-dependent constants, and reports numerical experiments comparing alternating minimization, the augmented method, and the infimal-convolution method in terms of iteration counts and running time. The computational motivation for the infimal-convolution reduction is clear and the numerical illustrations support the qualitative efficiency claims.","tokens_in":18840,"tokens_out":13768,"duration_ms":134156,"significance":"The infimal-convolution reduction is an attractive way to avoid forming the matrix B_beta, and Lemma 2.10 offers a practical way to evaluate the proximal step of the Moreau envelope. The computational complexity discussion in Section 2.2.2 and the numerical comparison in Section 3 are useful and reproducible in spirit. However, the main theoretical claim for the infimal-convolution method -- linear convergence -- is not established by the proof as written, because the contraction constant in Theorem 2.11 can exceed one under the stated assumptions. The augmented-formulation theorem (Theorem 2.7) is sound once the missing positivity condition is added, but the central novelty of the paper depends on the infimal-convolution rate, which needs to be repaired or substantially qualified.","major_comments":[{"comment":"The contraction constant displayed in Theorem 2.11 is not guaranteed to be smaller than 1. The proof derives two separate inequalities with coefficients rho_I/(1-T) on the support I and rho_{I^c}/(1+mu beta) on I^c, and the displayed constant is the Euclidean norm of these two coefficients. Even if each individual coefficient is below 1, their squared sum can exceed 1; for example, with beta=0.2 and mu=0.1 as in Section 3.2, and with rho_{I^c}=1, the second coefficient equals 1/1.02 and the combined constant can easily be larger than 1. Consequently, Theorem 2.11 as stated provides an upper bound with an unspecified constant rather than a linear convergence rate, and the claim in Remark 2.12 that 'we get linear convergence of (15)' is not justified by the displayed inequality.","section":"Theorem 2.11 / Section A.5"},{"comment":"The inequality ||Id_n - mu A^T A|| < 1 used in (17) is false when A is rank-deficient, which is the relevant compressed-sensing regime m<n. In that case the nullspace of A gives eigenvalues of Id_n - mu A^T A equal to 1, so the spectral norm is exactly 1. This invalidates the claim ||P_{I^c} - mu A_{I^c}^T A|| < 1 and leaves the second term of the Theorem 2.11 constant controlled only by 1/(1+mu beta). The linear-convergence assertion in Remark 2.12 therefore requires an explicit lower bound on beta (or a different argument controlling the cross terms), and no such bound is provided.","section":"Remark 2.12, Eq. (17)"},{"comment":"Both theorems omit the positivity condition on the denominators. In Theorem 2.7 the denominator 1 - mu alpha (1-q)(dmin/2)^{q-2} must be positive for the displayed inequality to be meaningful; the condition alpha < alpha_star appears only in Remark 2.8(i) and is not part of the theorem statement. The same omission occurs in Theorem 2.11 for the factor 1 - alpha mu (1-q)(dmin/2)^{q-2}. Because these conditions depend on the unknown limit point through dmin, they should be stated explicitly among the assumptions, or the theorems should be formulated as conditional statements valid only when the denominators are positive.","section":"Theorem 2.7 and Theorem 2.11"}],"minor_comments":[{"comment":"The statement of Lemma 2.10 uses prox_{mu,lambda M_{t,f}}(x) and then writes the result in terms of prox_{(t+mu lambda),f}(x); the argument of the proximal operator in the formula is not fully specified. Aligning the notation with the definition in (10) would improve readability and avoid ambiguity.","section":"Lemma 2.10"},{"comment":"The same symbol alpha* is used in Remark 2.12 to denote a threshold that differs from the alpha_star defined in Remark 2.8(i). Overloading the symbol in this way is confusing; using a distinct notation for the two thresholds would clarify the conditions.","section":"Remark 2.12"}],"recommendation":"major_revision","confidential_remarks":"The paper contains a promising algorithmic idea and a clean equivalence between the multi-penalty problem and the infimal-convolution formulation. The gap in Theorem 2.11 is load-bearing: the claimed linear convergence of the proposed infimal-convolution method is not proven under the stated assumptions, and the argument in Remark 2.12 relies on an inequality that is false for the underdetermined case. I believe the issue is fixable by adding explicit conditions (e.g., beta sufficiently large or a weighted-norm analysis), but as it stands the central theoretical claim is not established. The authors should also add the positivity condition to Theorems 2.7 and 2.11. I would recommend major revision rather than rejection, since the algorithmic idea and the augmented-formulation result are valuable and the defects are localized to the rate analysis of the infimal-convolution method."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. The genuinely new piece is the infimal-convolution reduction: it turns the two-penalty objective (q<1, p=2) into a single-penalty proximal-gradient iteration and avoids computing the matrix square root hidden in the augmented formulation. That is a real computational win and the experiments make the case. The second thing is that the linear convergence theorem for that new scheme (Theorem 2.11) is not actually proved as stated. The displayed constant is sqrt((rho_I/(1-T))^2 + (rho_Ic/(1+mu beta))^2), and the condition in Remark 2.12 only ensures the first summand is below 1. In the typical underdetermined regime, rho_Ic = ||P_Ic - mu A_Ic^T A|| equals 1 (nullspace of A sits inside I^c), so the second summand is 1/(1+mu beta), around 0.98 for the paper's own beta=0.2, mu=0.1. Unless the first summand is forced much lower than alpha < alpha* does, the sum of squares is above 1 and you have no contraction. The remark's claim that ||Id - mu A^T A|| < 1 is wrong; the norm is 1. So Theorem 2.11 is a one-step error bound with an unspecified constant, not a linear rate. This is the central claimed novelty, so it matters. It is fixable by adding an explicit quantitative condition on beta or on the restricted conditioning of A, but as printed it overstates the result.\n\nWhat the paper does well: Theorem 2.7 for the augmented scheme is a clean extension of [16] to 0<q<=1 with an explicit constant and a reasonable condition (alpha < alpha*). The proofs are standard and mostly transparent: support/sign stabilization, Woodbury reduction, Moreau-envelope proximal identity. The computational complexity comparison is honest and the numerics support the efficiency claim, even if alpha is tuned using the ground-truth support size and there are no error bars. The citation pattern is appropriate; the earlier multi-penalty work is credited properly.\n\nLike most iterative-thresholding results, the rates are local: they assume the iterates converge and support/sign stabilize, delegated to KŁ arguments. That is fine for this literature, but the reader should not mistake the theorems for global guarantees.\n\nWho is this for: people working on multi-penalty sparse recovery or proximal-gradient methods for nonconvex regularization. The reduction is a useful addition to the toolbox. The rate theorem needs a serious revision. I would send it to peer review — the idea deserves referee time — but I would not accept it without fixing the contraction condition.","headline":"The infimal-convolution reduction is a real computational contribution, but Theorem 2.11 does not prove the claimed linear convergence because its rate constant can exceed 1 under the stated conditions.","tokens_in":19377,"tokens_out":7826,"would_cite":false,"duration_ms":75398,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","65K05","94A12"],"pacs":[],"model":"deepseek-v4-flash","headline":"Infimal convolution gives linear convergence for two-penalty sparse recovery.","keywords":["multi-penalty regularization","sparse recovery","infimal convolution","non-convex optimization","iterative thresholding","linear convergence","compressed sensing","noise folding"],"falsifier":"Take a small problem where $B_\\beta$ can be computed exactly, choose parameters within the allowed ranges ($0<\\mu<\\|A\\|^{-2}$ and $\\alpha$ below the stated threshold), run the infimal-convolution iteration from a random initialization, and record the relative error after the supports of the iterates stop changing; if the error does not decrease by a factor below 1 per iteration, the contraction bound in Theorem 2.11 would be contradicted.","tokens_in":18273,"feed_emoji":"📡","tokens_out":10945,"duration_ms":88986,"temperature":0.7,"pith_summary":"This paper deals with recovering a sparse signal from noisy linear measurements when noise enters both before and after the measurement step, a situation that calls for two separate penalties. The authors show that the resulting non-convex multi-penalty problem can be reduced to a single-penalty problem in two ways: an augmented formulation that needs a costly matrix square root and inverse, and a new infimal-convolution formulation that avoids that preprocessing. They prove that proximal-gradient iterations for either reduction converge linearly, once the iterates' support and sign pattern have stabilized, with rates that improve with sparsity and measurement count. The infimal-convolution route provides the same guarantee at $O(mn)$ cost per iteration instead of $O(m^\\rho)$, making it practical for large measurement matrices.","feed_headline":"Infimal convolution makes two-penalty sparse recovery fast and linear","feed_subtitle":"The new reduction runs each proximal step in O(mn), skipping the costly matrix square root of the augmented approach.","key_machinery":"The load-bearing object is the infimal convolution $g(w)=\\inf_{u\\in\\mathbb{R}^n}\\frac{\\alpha}{q}\\|u\\|_q^q+\\frac{\\beta}{2}\\|w-u\\|_2^2$, which merges the two penalties into one. Its proximal operator is computed through the identity $\\operatorname{prox}_{\\mu,\\lambda M_{t,f}}(x)=\\frac{t}{t+\\mu\\lambda}x+\\frac{\\mu\\lambda}{t+\\mu\\lambda}\\operatorname{prox}_{(t+\\mu\\lambda),f}(x)$ (Lemma 2.10), so the cost of one proximal-gradient step is dominated by the proximal map of the $\\ell_q$ quasinorm, a componentwise thresholding operator. The proofs also rely on a support-and-sign stabilization lemma: because the thresholding operator has a gap near zero, consecutive iterates' supports and signs can change only finitely many times, turning a global iteration into a local contraction on the stabilized support. That contraction is what produces the explicit linear rates in Theorems 2.7 and 2.11.","core_discovery":"The central claim is that the non-convex multi-penalty problem, with $0<q\\le 1$ and $p=2$, is equivalent to a single-penalty problem in which the $\\ell_q$ quasinorm and the quadratic penalty on the second component are combined through an infimal convolution. The paper proves that the minimizer of the original two-penalty functional is obtained by solving this single-penalty program and then splitting the solution via the proximal operator of the $\\ell_q$ term. For both the augmented and the infimal-convolution reductions, the paper establishes that once the iterates converge to a stationary point and the support and signs stabilize, the error contracts by a factor strictly below one at each step, provided the step size stays below the reciprocal of the squared spectral norm of $A$ and the regularization parameter $\\alpha$ lies below a threshold that depends on the smallest nonzero entry of the limit. The infimal-convolution route achieves this at $O(mn)$ per iteration, whereas the augmented route requires an $O(m^\\rho)$ preprocessing step to form $B_\\beta$. If the theorems hold, multi-penalty regularization with non-convex sparsity penalties becomes as cheap to run as ordinary iterative thresholding.","pith_inferences":["Because the admissible $\\alpha$ bound depends on $d_{\\min}$, the smallest nonzero entry of the yet-unknown solution, a practical implementation would need to estimate $d_{\\min}$ on the fly—for instance, by monitoring the stabilized support and adapting $\\alpha$—since the theoretical threshold cannot be evaluated before running the algorithm.","The local nature of the rate (it only starts after support stabilization) suggests that the algorithm's early phase, during which the support is still changing, may dominate wall-clock time; any improvement that speeds up support identification would directly accelerate overall recovery.","The Moreau-envelope reinterpretation for $q=1$ hints that for $0<q<1$ the method implicitly tracks a family of smoothed quasi-norms, which could open the door to step-size rules larger than $\\|A\\|^{-2}$ or to second-order accelerations, though the paper does not establish these.","One testable extension: on large-scale problems with $m$ in the thousands, the per-iteration gap between the two formulations should grow roughly as $m^{\\rho-1}$, so the infimal-convolution method should win by an increasingly wide margin as $m$ grows; this is a quantitative prediction that can be checked empirically."],"forward_implications":["The infimal-convolution formulation solves the non-convex two-penalty problem with per-iteration cost $O(mn)$, so multi-penalty recovery becomes practical for large measurement counts $m$ where the augmented formulation's $O(m^\\rho)$ preprocessing is prohibitive.","Both reductions converge linearly once the support and signs stabilize, with the contraction factor determined by the restricted isometry constant of $A$, the sparsity level, and the smallest nonzero entry of the solution.","Alternating minimization, which requires solving an inner thresholding problem at every outer step, is dominated by either single-penalty formulation in terms of total proximal-operator calls.","The infimal-convolution reduction is not tied to the $\\ell_q$ quasinorm; the same program applies to other sparsity-inducing regularizers such as SCAD, MCP, or the log-sum penalty, where the general rate analysis of [28] should carry over.","For $q=1$ the method is equivalent to proximal descent on the squared $\\ell_2$-norm of the gradient of a Moreau-smoothed $\\ell_1$ functional, pointing to a view of multi-penalty regularization as a smooth zero-finding procedure."],"supporting_citations":[{"why":"Supplies the augmented single-penalty reduction (their Lemma 1) that the paper extends to $0<q\\le 1$.","marker":"[16]"},{"why":"Provides the iterative-thresholding convergence lemmas and the support/sign stabilization argument used in both rate proofs.","marker":"[9]"},{"why":"The prior linear-convergence analysis for single-penalty iterative thresholding that the paper refines and adapts to the multi-penalty reductions.","marker":"[28]"},{"why":"Establishes the Kurdyka-\\L{}ojasiewicz framework used to justify convergence of proximal-gradient iterates to stationary points.","marker":"[4]"},{"why":"Gives the Moreau-envelope proximal operator identity that makes the infimal-convolution step computationally tractable.","marker":"[7]"},{"why":"Shows that the infimal-convolution function $g$ has the Kurdyka-\\L{}ojasiewicz property, supporting the convergence assumption in Theorem 2.11.","marker":"[27]"},{"why":"Underpins the claimed $O(m^\\rho)$ cost of the matrix square root and linear solve needed in the augmented formulation.","marker":"[11]"}],"fun_headline_variants":["Infimal convolution cuts cost of non-convex sparse recovery","New reduction makes non-convex multi-penalty recovery linear-time","Skip the square root: infimal convolution speeds up recovery","Non-convex sparse recovery via infimal convolution: O(mn) steps","Infimal convolution: fast linear convergence for multi-penalty problems"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The linear-rate theorems hold only after the iterates have already converged to a stationary point and the support and sign pattern have stabilized, and the paper does not prove that this stabilization occurs from an arbitrary initialization, relying instead on Kurdyka-\\L{}ojasiewicz arguments from the cited literature.","fun_headline_variants_meta":{"raw":{"variants":["Infimal convolution cuts cost of non-convex sparse recovery","New reduction makes non-convex multi-penalty recovery linear-time","Skip the square root: infimal convolution speeds up recovery","Non-convex sparse recovery via infimal convolution: O(mn) steps","Infimal convolution: fast linear convergence for multi-penalty problems"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00109,"raw_usage":{"total_tokens":4533,"prompt_tokens":904,"completion_tokens":3629,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":520,"completion_tokens_details":{"reasoning_tokens":3540}},"tokens_in":520,"tokens_out":3629,"duration_ms":25418,"temperature":1.0,"reasoning_tokens":3540,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:43:19.558624+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small problem where $B_\\beta$ can be computed exactly, choose parameters within the allowed ranges ($0<\\mu<\\|A\\|^{-2}$ and $\\alpha$ below the stated threshold), run the infimal-convolution iteration from a random initialization, and record the relative error after the supports of the iterates stop changing; if the error does not decrease by a factor below 1 per iteration, the contraction bound in Theorem 2.11 would be contradicted.","supporting_citations":[{"cited_title":"Grasmair and V","cited_arxiv_id":null,"evidence_quote":"Supplies the augmented single-penalty reduction (their Lemma 1) that the paper extends to $0<q\\le 1$."},{"cited_title":"Minimizationofnon-smooth, non-convexfunction- als by iterative thresholding.Journal of Optimization Theory and Applications, 165(1):78– 112, Apr 2015","cited_arxiv_id":null,"evidence_quote":"Provides the iterative-thresholding convergence lemmas and the support/sign stabilization argument used in both rate proofs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The prior linear-convergence analysis for single-penalty iterative thresholding that the paper refines and adapts to the multi-penalty reductions."},{"cited_title":"Attouch, J","cited_arxiv_id":null,"evidence_quote":"Establishes the Kurdyka-\\L{}ojasiewicz framework used to justify convergence of proximal-gradient iterates to stationary points."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Underpins the claimed $O(m^\\rho)$ cost of the matrix square root and linear solve needed in the augmented formulation."}],"review_version":1}