{"id":"392a6374-3b5b-46ca-8f21-79775c8292d0","arxiv_id":"2505.15661","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Soft-OMP and Soft-IHT are differentiable relaxations of greedy sparse recovery algorithms with provable approximation guarantees, unrolled into trainable networks that outperform their classical counterparts on structured sparse recovery.","lead":"Greedy sparse recovery algorithms like OMP and IHT rely on a non-differentiable sorting step, which blocks them from being trained as neural networks. The authors replace that step with a soft, differentiable approximation called softsort, prove error bounds, and build trainable OMP-Net and IHT-Net that learn latent support structure and beat standard OMP and IHT in undersampled settings.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.9's proof only covers η=1, so the claimed Soft-IHT guarantee for general step size is unsupported; the stated theorem is not established as written.","rationale":"The reader's weakest_assumption was the min-gap condition, which is indeed load-bearing in the sense that the approximation guarantee degrades when gaps shrink. However, that condition is an input hypothesis inherent to any approximation of a discontinuous sorting operator, and the paper states it explicitly. The more concrete and internal problem is that Theorem 3.9's proof silently fixes η=1. The algorithm's defining update includes η, the experiments use η=0.5/0.6, and the theorem's L and C(n) contain no η; a careful reader cannot verify the stated result for η≠1 from Appendix C. This is a genuine gap in the central theoretical claim, and it warrants the conditional verdict: the authors should either prove the theorem for general η with appropriate modified constants or explicitly restrict the claim to η=1. The Lemma B.2 constant mismatch is a smaller quantitative issue that also supports 'conditional', since the sufficient τ condition is stated too optimistically. The paper's qualitative insight, that softsort-based unrolling of OMP and IHT is a sound differentiable approximation under separation assumptions, is still credible and the empirical demonstrations are useful; the concern is about the rigor of the stated theorem, not the viability of the approach.","tokens_in":24674,"tokens_out":11005,"duration_ms":96676,"concrete_test":"Re-derive Lemma C.1 and Theorem 3.9 for general η, replacing u by u_η=(I-ηA^*A)x+ηA^*y and tracking L_η=||I-ηA^*A||, the η-scaled coherence, and the η-scaled ||y|| term. If the resulting bound differs from the printed C(n) and L for any η≠1, Theorem 3.9 as stated is not proven; at minimum the theorem must be restricted to η=1 or restated with η-dependent constants. A numerical cross-check: in the Section 5.2 setup (η=0.5, m=36, N=256), fix one A, x, y, compute the gap g, set eps=g/(4L) with L=||I-A^*A||, set τ=(g-2Leps)/log(C(n)/eps), and compute the exact max error over n iterations; if the error exceeds eps, the theorem's constants as printed are not the ones the proof supplies.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central guarantee for Soft-IHT, Theorem 3.9, is stated for arbitrary step size η>0, but the proof in Appendix C only treats η=1. Lemma C.1 defines u(x) := (I-A^*A)x + A^*y, with Lipschitz constant L=||I-A^*A||, and the bound's constant C(n) uses ||y|| and μ(A). For general η, the IHT update is u_η(x) = (I-ηA^*A)x + ηA^*y, whose Lipschitz constant is L_η=||I-ηA^*A||, whose coherence term scales as ημ, and whose inhomogeneous term is ηA^*y. The printed theorem gives no way to absorb η into L, μ, and ||y|| as stated. Since the numerical validation and the IHT-Net experiments use η=0.5 and 0.6, the paper's central claim that Soft-IHT approximates IHT with controllable accuracy is not supported in the demonstrated regime. This is an internal proof gap, not a disagreement with external consensus. A secondary but real constant error: Lemma B.2 obtains ||Π-\\tildeΠ||_F^2 ≤ 2n(N-1)^2 e^{-2\\tilde g/τ}; taking square roots gives sqrt(2n)(N-1)e^{-\\tilde g/τ}, not sqrt(2n(N-1))e^{-\\tilde g/τ}. The printed C(n) is therefore too small by a factor sqrt(N-1) for N>1, which weakens the sufficient τ condition quantitatively but does not change the qualitative conclusion.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes differentiable relaxations of two greedy sparse recovery algorithms, OMP and IHT, by replacing the non-differentiable argsort operation with softsort-based approximate permutation matrices. It defines Soft-OMP and Soft-IHT, states approximation theorems (Theorems 3.6 and 3.9) bounding the distance to the exact algorithms in terms of the softsort temperature tau and certain min-gaps, and unrolls the soft algorithms into trainable OMP-Net and IHT-Net architectures. Numerical experiments validate the tau-asymptotic behavior and demonstrate that learned structure-aware weights can outperform the classical algorithms in a structured undersampled recovery task.","tokens_in":25009,"tokens_out":6803,"duration_ms":58410,"significance":"If the results hold, this is a valuable contribution to algorithm unrolling for greedy sparse recovery: it gives a principled, differentiable replacement for the discontinuous argsort operator with explicit approximation guarantees, rather than relying on ad hoc engineering fixes. The main theorems are not circular: the bounds follow from softsort convergence and least-squares perturbation analysis, not from the trained network weights. The paper also provides detailed appendices and a public code repository, which strengthens reproducibility. The principal caveats are that the guarantees are conditional on data-dependent min-gaps that are not known a priori, and that the IHT guarantee as stated is not actually proved for the general step size used in the experiments; these points are addressed in the major comments.","major_comments":[{"comment":"Theorem 3.9 is stated for arbitrary step size eta > 0, but the proof in Appendix C only covers eta = 1. Lemma C.1 defines u(x) = (I - A^*A)x + A^*y and sets L = ||I - A^*A||; for general eta the IHT update is u_eta(x) = (I - eta A^*A)x + eta A^*y, whose Lipschitz constant is ||I - eta A^*A|| and whose inhomogeneous term is eta A^*y. The theorem's constant C(n) contains no eta, so the printed argument cannot establish the stated bound. Since the numerical validation in Section 5.1 uses eta = 0.6 and the IHT-Net experiments in Section 5.2 use eta = 0.5, the claimed guarantee is not supported in the demonstrated regime. Please either extend the proof to general eta with constants depending on eta, or restate the theorem and lemma for eta = 1 and adjust the experiments accordingly.","section":"§3.3, Theorem 3.9 and Appendix C, Lemma C.1"},{"comment":"The proof of Lemma B.2 concludes ||Pi^(n) - tilde-Pi^(n)||_F^2 <= 2n(N-1)^2 e^{-2 tilde-g^(1:n)/tau}; taking square roots gives sqrt(2n)(N-1)e^{-tilde-g^(1:n)/tau}, not sqrt(2n(N-1))e^{-tilde-g^(1:n)/tau}. As a result, the constant C(n) in Theorem 3.6 is too small by a factor of sqrt(N-1) for N > 1. The qualitative exponential-in-tau conclusion remains, but the displayed constant and the sufficient condition on tau must be corrected.","section":"Appendix B, Lemma B.2 and Theorem 3.6"}],"minor_comments":[{"comment":"In the update for tilde-v^(n+1), the right-hand side should read |tilde-u^(n+1)| rather than |u^(n+1)|; the tilde is missing.","section":"Algorithm 3.4"},{"comment":"The input lines list the observation vector as y in C^N; the measurement vector should be in C^m, as in Algorithms 2.1 and 2.2.","section":"Algorithms 3.3 and 3.4"},{"comment":"The notation 'N trial' for the number of trials is inconsistent with the later definition of N_trial; please standardize the notation.","section":"Section 5.1"},{"comment":"Both theorems assume positive min-gaps; it would be helpful to state explicitly that the guarantees are vacuous when any tie occurs, since a tie makes g^(i) = 0.","section":"Theorems 3.6 and 3.9"},{"comment":"The phrase 'controllable degree of accuracy' overstates the result because the min-gap is data-dependent and is not known a priori; a phrase such as 'controlled, provided the min-gaps are sufficiently large' would be more precise.","section":"Abstract and Section 1.1"}],"recommendation":"major_revision","confidential_remarks":"The eta = 1 proof gap in Theorem 3.9 is the main technical obstacle; it appears fixable by carrying eta through Lemma C.1 with L_eta = ||I - eta A^*A|| and scaling the inhomogeneous term by eta. The self-citation to [34] is disclosed and appropriately scoped. The paper fits the journal's interest in algorithm unrolling and model-based deep learning. I would encourage the authors also to include a brief discussion of whether the min-gap conditions are typical or checkable under standard random measurement models, since this affects the practical reading of the theorems."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is one of the cleaner algorithm-unrolling papers I have seen. The idea is to replace argsort in OMP and IHT with softsort and prove that the soft iterations track the exact ones. That is genuinely new for IHT, and the OMP part extends their CoSeRa paper in a disclosed way. The theory is not circular: the bounds depend on softsort convergence and least-squares sensitivity, not on trained weight values. Credit where due: Theorems 3.6 and 3.9 have real proofs, the min-gap conditions are honestly stated, and the numerical section actually tests the approximation claim first (Figure 5.1) before showing that trainable networks can beat OMP/IHT under structured support.\n\nThe main problem is Theorem 3.9. It is stated for arbitrary step size eta > 0, but Lemma C.1, which does all the work, is written for eta = 1: u(x) = (I - A*A)x + A*y, with Lipschitz constant ||I - A*A|| and inhomogeneous term A*y. For general eta the update is u_eta(x) = (I - eta A*A)x + eta A*y, so the Lipschitz constant becomes ||I - eta A*A||, the coherence term scales with eta, and the ||y|| term scales with eta. Nothing in the printed proof absorbs those changes; the induction in Appendix C just invokes Lemma C.1. So the theorem as stated is not established. This matters because the IHT experiments use eta = 0.5 and 0.6, exactly the regime the proof does not cover. The gap looks fixable -- restate Lemma C.1 with eta, or restrict Theorem 3.9 to eta = 1 -- but as submitted the central Soft-IHT guarantee is unsupported in the demonstrated regime.\n\nThere is also a smaller constant error in Lemma B.2: the proof gives ||Pi - tilde Pi||_F^2 <= 2n(N-1)^2 e^{-2g/tau}, so the square root has (N-1), not sqrt(N-1). The printed bound is too small by sqrt(N-1). This weakens the sufficient-tau condition quantitatively but does not change the qualitative conclusion. Minor. The GitHub URL in Section 5 has a space and should be fixed.\n\nOverall: the high-level claim -- softsort can make greedy sparse recovery differentiable with controllable approximation error -- holds up for OMP and is very likely fixable for IHT. The paper deserves a serious referee, but the referee should send it back for a proof repair and re-statement before acceptance.","headline":"Honest and useful unrolling paper: the OMP half is solid, the IHT approximation theorem is not proven for the step sizes used in the experiments, but the gap looks fixable.","tokens_in":25547,"tokens_out":2999,"would_cite":true,"duration_ms":24853,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07","94A12","65F22"],"pacs":[],"model":"deepseek-v4-flash","headline":"Softsort unrolls greedy sparse recovery into trainable networks with exact error control.","keywords":["sparse recovery","algorithm unrolling","orthogonal matching pursuit","iterative hard thresholding","softsort","differentiable sorting","neural networks","structured sparsity"],"falsifier":"Run OMP and Soft-OMP on a constructed instance where, at some iteration, the two largest entries of $|A^*(y-Ax^{(n)})|$ are exactly equal or differ by less than $2\\|A\\|\\epsilon$; then the row-wise argmax of the soft permutation matrix will not match OMP's selection and the $\\epsilon$-accuracy guarantee of Theorem 3.6 fails, showing visible divergence between the iterates. The same check applies to IHT by making two entries of $|u|$ closer than $2L\\epsilon$.","tokens_in":24471,"feed_emoji":"🧠","tokens_out":4431,"duration_ms":37883,"temperature":0.7,"pith_summary":"This paper shows that two classic greedy sparse-recovery algorithms, OMP and IHT, can be made differentiable without losing control over accuracy. The trick is to replace the hard argsort step, the piecewise-constant operation that blocks gradient flow, with softsort, a smooth permutation-matrix relaxation governed by a temperature parameter $\\tau$. The authors prove that for $\\tau$ small enough relative to the gaps between sorted magnitudes, the soft trajectories stay within any prescribed $\\epsilon$ of the exact OMP and IHT trajectories (Theorems 3.6 and 3.9). This turns unrolling of greedy algorithms into a rigorous, trainable network design, and the paper demonstrates numerically that the resulting OMP-Net and IHT-Net can outperform the classical algorithms in heavily undersampled structured recovery.","feed_headline":"Softsort unrolls greedy sparse recovery into trainable nets","feed_subtitle":"Replacing argsort with a smooth proxy gives OMP and IHT proven error control, and trained nets beat the classics.","key_machinery":"The central object is softsort, a continuous relaxation of argsort that maps a vector $v\\in\\mathbb{R}^N$ to a row-stochastic matrix $\\tilde{P}_{\\text{argsort}}(v) = \\text{softmax}(-|\\text{sort}(v)\\mathbf{1}^\\top - \\mathbf{1}v^\\top|/\\tau)$, whose rows approximate the one-hot rows of the exact permutation matrix with a temperature parameter $\\tau$ controlling sharpness. The paper re-expresses OMP as projection-based pOMP and IHT as pIHT, both built from permutation matrices, then substitutes the soft surrogate. The proofs hinge on a Lipschitz property of softsort (Proposition 3.3), a bound on how quickly the soft permutation matrix converges to the exact one (Lemma B.2), and sensitivity analysis of least squares (Lemma B.1) for OMP, or a one-step perturbation bound for the hard-thresholding mask (Lemma C.1) for IHT.","core_discovery":"Soft-OMP and Soft-IHT are differentiable counterparts of OMP and IHT that approximate them with controllable accuracy: for iteration counts up to $n$, if the temperature satisfies $\\tau \\le (g^{(1:n)} - 2\\|A\\|\\epsilon)/\\log(C/\\epsilon)$ for OMP or $\\tau \\le (g^{(1:n)} - 2L\\epsilon)/\\log(C/\\epsilon)$ for IHT, then the maximum deviation between soft and exact iterates stays below $\\epsilon$. The min-gap $g^{(1:n)}$ is the separation between the largest and remaining sorted magnitudes in OMP, and between all magnitudes in IHT. Consequently, unrolled networks built from these soft algorithms inherit recovery guarantees, and with trainable weight vectors they learn latent support structure and beat classical OMP and IHT by orders of magnitude in undersampled, structured experiments.","pith_inferences":["The same permutation-proxy recipe could be applied to other argsort-based greedy solvers such as CoSaMP or subspace pursuit; the paper lists these as future candidates, and the error analysis would follow the same pattern with a different perturbation term.","The min-gap assumption is data-dependent, so in adversarial or exactly-tied settings the guarantee disappears; in practice ties are rare due to round-off, but a tie-breaking or gap-regularized variant could make the method robust to near-ties.","Because the bounds' constants involve properties like the restricted isometry constant and coherence, the theoretical regime may be far more conservative than the observed performance, so the practical range of $\\tau$ may extend well beyond the proven range.","Making $\\tau$ itself a trainable parameter or a per-layer schedule could balance the accuracy-gradient trade-off dynamically, an extension the paper does not explore."],"forward_implications":["OMP and IHT can be unrolled into deep networks with rigorous approximation guarantees, closing the differentiability gap that previously forced ad-hoc engineering fixes.","OMP-Net and IHT-Net, trained with weight-sharing on structure-aware weights, recover signals near the noise floor in undersampled regimes ($m=22$ for OMP, $m=36$ for IHT with $N=256$) where classical OMP and IHT fail.","Because $\\|\\tilde{x} - x\\| \\le \\|\\tilde{x} - x^{(n)}\\| + \\|x^{(n)} - x\\|$, classical recovery guarantees for OMP and IHT transfer to the soft algorithms (Remark 3.8).","The temperature $\\tau$ is a knob trading approximation accuracy (small $\\tau$) against gradient flow and trainability (larger $\\tau$); numerical experiments place the sweet spot in the transition region of the accuracy curve.","Learned weights capture the latent set $T$ containing the support, providing interpretable structure extraction from data rather than just a black-box improvement."],"supporting_citations":[{"why":"Defines softsort and its properties (continuity, row-stochasticity, asymptotic convergence to argsort), which is the core differentiable proxy.","marker":"[38]"},{"why":"Introduces k-sparse IHT, the exact algorithm that Soft-IHT approximates and whose convergence theory underlies the transferred guarantees.","marker":"[7]"},{"why":"Introduces Orthogonal Matching Pursuit, the exact algorithm that Soft-OMP approximates.","marker":"[16]"},{"why":"LISTA is the seminal unrolling baseline that motivates treating unrolled iterations as trainable networks and provides the comparison point for trainable sparse recovery.","marker":"[22]"},{"why":"Documents stability barriers for unrolled networks and motivates the need for rigorous approximation guarantees when unrolling algorithms.","marker":"[12]"},{"why":"Supplies OMP recovery guarantees that, combined with Theorem 3.6, yield a recovery guarantee for Soft-OMP via the triangle inequality.","marker":"[46]"},{"why":"Provides the least-squares sensitivity bound (Lemma B.1) that the OMP approximation proof relies on to control perturbations in the projection subspace.","marker":"[42]"},{"why":"The authors' earlier OMP-Net work that this paper extends by adding Soft-IHT, IHT-Net, and the full theoretical treatment.","marker":"[34]"}],"fun_headline_variants":["Softsort unrolls greedy recovery into trainable networks","Differentiable OMP and IHT via softsort, proven accurate","Soft-OMP and Soft-IHT: differentiable greedy sparse recovery","Trainable sparse recovery with softsort-based unrolling","Softsort makes greedy sparse recovery neural-friendly"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The bounds collapse if at any iteration the gap between the top magnitude and the next one (OMP) or between any two magnitudes (IHT) becomes zero or very small, because the theorem's condition that $\\tau$ be small relative to that gap cannot be met.","fun_headline_variants_meta":{"raw":{"variants":["Softsort unrolls greedy recovery into trainable networks","Differentiable OMP and IHT via softsort, proven accurate","Soft-OMP and Soft-IHT: differentiable greedy sparse recovery","Trainable sparse recovery with softsort-based unrolling","Softsort makes greedy sparse recovery neural-friendly"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00052,"raw_usage":{"total_tokens":2518,"prompt_tokens":945,"completion_tokens":1573,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":561,"completion_tokens_details":{"reasoning_tokens":1493}},"tokens_in":561,"tokens_out":1573,"duration_ms":11242,"temperature":1.0,"reasoning_tokens":1493,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T15:13:18.561312+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run OMP and Soft-OMP on a constructed instance where, at some iteration, the two largest entries of $|A^*(y-Ax^{(n)})|$ are exactly equal or differ by less than $2\\|A\\|\\epsilon$; then the row-wise argmax of the soft permutation matrix will not match OMP's selection and the $\\epsilon$-accuracy guarantee of Theorem 3.6 fails, showing visible divergence between the iterates. The same check applies to IHT by making two entries of $|u|$ closer than $2L\\epsilon$.","supporting_citations":[{"cited_title":"Prillo and J","cited_arxiv_id":null,"evidence_quote":"Defines softsort and its properties (continuity, row-stochasticity, asymptotic convergence to argsort), which is the core differentiable proxy."},{"cited_title":"Blumensath and M","cited_arxiv_id":null,"evidence_quote":"Introduces k-sparse IHT, the exact algorithm that Soft-IHT approximates and whose convergence theory underlies the transferred guarantees."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces Orthogonal Matching Pursuit, the exact algorithm that Soft-OMP approximates."},{"cited_title":"Gregor and Y","cited_arxiv_id":null,"evidence_quote":"LISTA is the seminal unrolling baseline that motivates treating unrolled iterations as trainable networks and provides the comparison point for trainable sparse recovery."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Documents stability barriers for unrolled networks and motivates the need for rigorous approximation guarantees when unrolling algorithms."},{"cited_title":"Zhang , Sparse recovery with orthogonal matching pursuit under RIP , IEEE Transactions on Information Theory, 57 (2011), pp","cited_arxiv_id":null,"evidence_quote":"Supplies OMP recovery guarantees that, combined with Theorem 3.6, yield a recovery guarantee for Soft-OMP via the triangle inequality."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the least-squares sensitivity bound (Lemma B.1) that the OMP approximation proof relies on to control perturbations in the projection subspace."},{"cited_title":"Mohammad-Taheri, M","cited_arxiv_id":null,"evidence_quote":"The authors' earlier OMP-Net work that this paper extends by adding Soft-IHT, IHT-Net, and the full theoretical treatment."}],"review_version":1}