{"id":"c3e9a6ae-7252-40eb-a574-be51421cf63a","arxiv_id":"1908.10776","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"For multichannel sparse blind deconvolution, Huber-loss Riemannian gradient descent with random initialization plus an LP-rounding step provably recovers the kernel and sparse signals up to a signed shift, with sample complexity O~(n^4).","lead":"This paper proves that a simple gradient descent routine can recover an unknown blur and a set of sparse signals from several blurred mixtures, up to a shift and sign ambiguity. It gives the first guarantee that ordinary Riemannian gradient descent with random starts succeeds for multichannel sparse blind deconvolution, and it needs far fewer measurements than previous provable methods.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.1's Phase-2 iteration count omits the θ^{-2} dependence forced by the paper's own sharpness analysis in Appendix D.9, so the claimed O(log(np) log(1/ε)) cost does not follow.","rationale":"The reader's weakest assumption was the generative statistical model (Bernoulli-Gaussian inputs and invertible kernel). That is a reasonable model-dependence caveat, but it is not the most load-bearing internal issue. My review of the proof found a more concrete gap in the claimed complexity: the Phase-2 sharpness analysis in Appendix D yields a contraction factor whose logarithm is O(θ^2 / log^2(np)), forcing O(θ^{-2} log^2(np) log(1/ε)) iterations, whereas Theorem 3.1 states O(log(np) log(1/ε)). This is not a refutation of the recovery guarantee, but it means the theorem's quantitative efficiency claim is unsupported as written. The main text's Proposition 3.5 appears to absorb the θ-dependence into constants, which is misleading if C1 and c2 are meant to be absolute constants. I therefore keep the reader's CONDITIONAL verdict: the paper's core geometric and recovery arguments may be sound, but the stated iteration complexity needs correction or clarification before the central claim can be accepted as stated. I credit the paper for a detailed appendix, a reproducible code link, and extensive numerical experiments; none of these resolve the specific mismatch between Theorem 3.1 and Proposition D.9. The right next step is an independent re-derivation of the Phase-2 contraction rate from the paper's own constants.","tokens_in":54340,"tokens_out":24093,"duration_ms":265824,"concrete_test":"Re-derive the contraction factor in Proposition D.9 exactly: set α = (1/50)√(2/π)θ, take β as defined there, and solve the recurrence (d^{k+1})^2 ≤ (d^k)^2 − 2ατ_k d^k + β^2τ_k^2 with τ_k = η^kτ_0 and τ_0 = (16/25)α/β^2. Compute the minimal k such that (2/5)η^k ≤ ε. If the resulting bound contains θ^{-2} log^2(np) log(1/ε), then Theorem 3.1's Phase-2 iteration count is incorrect. Independently, check whether the constant c2 in main-text Proposition 3.5 depends on θ; if it does, Theorem 3.1 cannot claim a θ-independent log(np) factor in the second term.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The quantitative efficiency claim in Theorem 3.1 is not supported by the sharpness/subgradient analysis in Appendix D. Proposition D.6 (via Lemmas D.7 and D.8) establishes the sharpness constant α = (1/50)√(2/π)θ for the Phase-2 LP objective. Proposition D.9 then sets β from the projected subgradient norm bound and chooses τ0 = (16/25)α/β^2 with contraction factor η satisfying η^2 ≥ 1 − c α^2/β^2. With α proportional to θ and β proportional to log(np), the number of Phase-2 iterations needed to go from d0 ≤ 2/5 to ε is k ≳ (β^2/α^2) log(1/ε) = C θ^{-2} log^2(np) log(1/ε) (using β as defined in D.9). Theorem 3.1 instead states only C1(log(np) log(1/ε)) for the second term. The main-text Proposition 3.5 hides this by writing η ≥ (1 − c2 log^{-2}(np))^{1/2} with c2 implicitly θ-dependent; if c2 is allowed to depend on θ, the stated iteration bound is not the claimed θ-independent polynomial. This does not refute recovery, but it is a genuine gap in the central 'efficient' claim: the theorem as stated overstates the Phase-2 complexity by a factor polynomial in θ^{-1} and log(np).","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies multichannel sparse blind deconvolution (MCS-BD), where one observes p circulant convolutions y_i = a * x_i with an invertible kernel a and i.i.d. Bernoulli-Gaussian sparse inputs x_i, and aims to recover a and all x_i up to the intrinsic signed-shift ambiguity. The authors formulate a smooth Huber-loss objective on the sphere with a data-dependent preconditioner and prove that a vanilla Riemannian gradient descent (RGD) method from a random initialization reaches an O(mu) neighborhood of the target, after which a projected subgradient method for an LP rounding problem converges linearly to the exact solution. The main theorem gives sample-complexity and iteration-complexity bounds, and the paper reports experiments on synthetic data and on a STORM microscopy dataset. The proof is developed in Appendices C-H through population geometry, concentration inequalities, and a perturbation analysis around RQ^{-1} approximately equal to I.","tokens_in":54656,"tokens_out":15096,"duration_ms":159674,"significance":"If the result is correct in its stated quantitative form, this is a significant contribution: it is the first provable guarantee that vanilla first-order methods with random initialization solve MCS-BD exactly (up to the signed-shift ambiguity), and its sample complexity improves on the prior nonconvex result of Li and Bresler. The paper is unusually careful in structure: the geometric assumptions are explicit, the regularity and implicit-regularization conditions are stated as separate propositions, the appendices contain a substantial amount of proof detail, and the authors provide code and honest discussion of the looseness of their bounds. The central recovery claim is not affected by the issue I raise below; however, the headline efficiency statement in Theorem 3.1 overstates what the Phase-2 sharpness analysis actually proves, and this needs to be corrected before the paper can be accepted in its present form.","major_comments":[{"comment":"The Phase-2 iteration count claimed in Theorem 3.1, namely C log(np) log(1/epsilon), does not follow from the sharpness analysis in Appendix D.3. Proposition D.9 sets the sharpness constant to alpha = (1/50) sqrt(2/pi) theta and the projected subgradient norm bound to beta = 36 log(np), and then chooses eta with eta^2 >= 1 - alpha^2/(2 beta^2). Consequently 1 - eta is proportional to theta^2 / log^2(np), so the number of projected subgradient iterations needed to reduce dist(q) from a constant to epsilon is k >= C theta^{-2} log^2(np) log(1/epsilon), not C log(np) log(1/epsilon). Proposition 3.5 conceals this dependence inside the unspecified constant c2 in the lower bound on eta. This is a load-bearing quantitative claim: the theorem as stated overstates the Phase-2 efficiency by a factor of theta^{-2} log(np). The recovery conclusion is not invalidated, but the complexity statement and Proposition 3.5 must be revised to state the theta and log factors explicitly.","section":"Theorem 3.1 / Appendix D.3 (Proposition D.9)"},{"comment":"The Phase-1 iteration bound is stated inconsistently across the paper. Theorem 3.1 uses theta^{-1} n^4 log(1/mu), while Proposition 3.4 states N := C theta n^4 log(1/mu) and Theorem D.1 states K := C theta max{n^4, n^{5/2}/mu} log(1/mu). The proof of Theorem D.1 derives contraction factors 1 - tau alpha_1 with tau alpha_1 on the order of theta/n^4 and 1 - tau alpha_2 with tau alpha_2 on the order of mu theta/n, which support the inverse theta dependence of the main theorem rather than the theta factor displayed in Proposition 3.4 and Theorem D.1. Please reconcile these statements so that the main theorem and the appendices report the same bound.","section":"Proposition 3.4 / Appendix D.1 (Theorem D.1)"}],"minor_comments":[{"comment":"The keyword 'Riemmanian' should be spelled 'Riemannian'.","section":"Abstract and keywords"},{"comment":"The time-complexity entry for 'Ours' should be updated after the Phase-2 complexity claim is corrected; as typeset it omits the theta and log(np) factors that the analysis in Appendix D.3 actually yields.","section":"Table 1"},{"comment":"The shorthand notation PqK is used without being defined in Appendix A; Appendix A defines the projection notation P_v and P_{v^\\perp}, so the shorthand should either be defined explicitly or replaced by the longer notation.","section":"Appendix G, proof of Proposition G.1"},{"comment":"The experiments use Riemannian line search rather than the fixed step sizes prescribed by Theorem 3.1; this is reasonable for illustration, but the text should state explicitly that the empirical convergence plots are not a direct test of the theorem's step-size and iteration-count prescriptions.","section":"Section 4.1"}],"recommendation":"major_revision","confidential_remarks":"The Phase-2 complexity gap identified above is real but local: it concerns the stated iteration count, not the validity of the recovery guarantee under the geometric assumptions. With a corrected Theorem 3.1 and a reconciled Phase-1 iteration formula, the paper is a strong candidate for acceptance. I therefore recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a substantial theory paper, and I think the recovery result is essentially right, but the advertised efficiency claim in Theorem 3.1 is overstated by a theta^{-2} log^2(np) factor in Phase 2. It deserves a serious referee; the gap is fixable.\n\nWhat is genuinely new: the authors give the first proof that a vanilla first-order method with random initialization on a Huber-loss objective with preconditioning drives iterates to an O(mu) neighborhood of a signed shift of the inverse kernel, with sample complexity O~(n^4) rather than Li-Bresler's O~(n^8/epsilon^8). The second stage is a projected subgradient method on an LP rounding problem, and they prove linear convergence to the exact solution. They also remove the restrictive spiky-kernel assumption from Wang-Chi. The appendices are extensive: population landscape, concentration, preconditioner perturbation. The regularity condition and implicit regularization are appropriate tools, and the paper honestly lists conditions and limitations. I checked the main structural steps and did not find circularity; the preconditioner is computed from data and no fitted constants drive the derivation.\n\nNow the soft spots. The stress-test note is correct. In Appendix D.9 the sharpness constant is alpha = (1/50)sqrt(2/pi)theta and the subgradient norm bound is beta = 36 log(np). The contraction factor eta in Proposition D.9 has eta^2 >= 1 - c alpha^2/beta^2, so reaching epsilon needs k ≳ (beta^2/alpha^2) log(1/epsilon) = C theta^{-2} log^2(np) log(1/epsilon). Theorem 3.1 instead states C1(log(np) log(1/epsilon)) for Phase 2. Proposition 3.5 hides this by writing eta >= (1 - c2 log^{-2}(np))^{1/2} with c2 allowed to depend on theta. So the theorem as stated overstates the Phase-2 complexity by a polynomial theta factor. The recovery guarantee survives; the efficiency claim does not, as written.\n\nTwo smaller issues. The abstract says vanilla RGD recovers the kernel and signals; the theorem actually needs the two-stage LP rounding for exact recovery, and RGD alone gives only O(mu) accuracy. That mismatch should be fixed. Second, the guarantees rest on i.i.d. Bernoulli-Gaussian inputs, known theta, and an invertible kernel with no zero DFT entries; those are explicit and standard for this literature, but they mean the practical claims are less general than the applications list suggests.\n\nWho this is for: people working on provable nonconvex blind deconvolution, dictionary learning, and structured inverse problems. It deserves peer review. I would tell the authors to correct the Phase-2 iteration bound, align the abstract with the two-stage algorithm, and provide reproducible code or machine-checked key inequalities.","headline":"Substantial and likely correct theory for multichannel sparse blind deconvolution, but the advertised Phase-2 iteration count omits a theta-dependence that its own sharpness analysis forces.","tokens_in":55208,"tokens_out":2923,"would_cite":true,"duration_ms":32265,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that plain Riemannian gradient descent, run from a random initialization on a preconditioned Huber-loss sphere, exactly recovers both the convolution kernel and the sparse inputs in multichannel sparse blind…","keywords":["nonconvex optimization","blind deconvolution","sparsity","Riemannian gradient descent","Bernoulli-Gaussian model","Huber loss","preconditioning","sample complexity"],"falsifier":"Generate measurements $y_i = a * x_i$ with $a$ an invertible kernel of condition number $\\kappa$, $x_i$ i.i.d. Bernoulli-Gaussian at $\\theta=0.25$, and choose $p$ above the Theorem 3.1 bound for small $n$ (say $n=64$, $\\theta=0.25$, $\\mu=10^{-2}$); the two-stage algorithm should recover the kernel and signals to $\\varepsilon$-precision with probability at least $1/2$. If it systematically fails at such parameters—for example, by converging to a spurious stationary point—the claimed guarantee is false; the same test with a kernel whose DFT contains a zero probes the boundary of the invertibility assumption rather than the core claim.","tokens_in":54151,"feed_emoji":"🎯","tokens_out":8253,"duration_ms":83005,"temperature":0.7,"pith_summary":"The paper sets out to prove that a straightforward algorithm—plain (vanilla) Riemannian gradient descent from a random point on the unit sphere, run on a smoothed $\\ell^1$ (Huber) loss with data preconditioning—recovers both the unknown kernel and the sparse input signals in multichannel sparse blind deconvolution, up to the unavoidable signed-shift ambiguity. Previous nonconvex guarantees needed noisy gradient steps or tolerated far worse sample and time complexity; this paper claims the first provable guarantee for vanilla first-order methods with random initialization. If the result holds, practitioners can use a simple gradient loop with no tunable noise schedule and still get exact recovery, provided the inputs are independent Bernoulli-Gaussian with known sparsity and the kernel has no zero Fourier entries. The proof works by showing that, after preconditioning, the objective's geometry is benign: every region of the sphere around a target solution has gradients pointing toward that solution, and a second LP-rounding phase sharpens the approximate solution to exact precision.","feed_headline":"Vanilla gradient descent provably solves sparse blind deconvolution","feed_subtitle":"Random starts on a Huber-loss sphere recover kernel and sparse inputs exactly via a two-stage method.","key_machinery":"The argument rests on three objects that work together. The preconditioner $P = (\\frac{1}{\\theta n p}\\sum_{i=1}^p C_{y_i}^{\\mathsf T} C_{y_i})^{-1/2}$ approximately orthogonalizes the circulant convolution operator: it makes $R = C_a P$ close to the orthogonal matrix $Q = C_a (C_a^{\\mathsf T} C_a)^{-1/2}$, symmetrizing the landscape and removing the ill-conditioning caused by a generic kernel. The Huber loss $h_\\mu(z)$, a first-order smooth surrogate of the $\\ell^1$ norm, promotes sparsity while keeping gradients Lipschitz, so random-process concentration and perturbation arguments go through. Finally, the $2n$ spherical regions $S_i^\\xi = \\{ q \\in S^{n-1} : |q_i|/\\|q_{-i}\\|_\\infty \\ge \\sqrt{1+\\xi},\\ q_i \\neq 0\\}$, each containing one target solution, allow the analysis to establish a regularity condition (the negative gradient aligns with the direction to $e_i$), an implicit-regularization bound (iterates never leave their region), and then a sharpness bound for the LP-rounding objective that gives linear convergence of the second phase.","core_discovery":"On the paper's own terms, the central discovery is that multichannel sparse blind deconvolution has benign global geometry for a smooth sparsity surrogate, not for the heavy-tailed $\\ell^4$ loss used in earlier nonconvex work. For an invertible kernel $a$ with condition number $\\kappa$ and i.i.d. Bernoulli-Gaussian inputs with sparsity $\\theta \\in (1/n, 1/3)$, the preconditioned Huber objective over the sphere satisfies a regularity condition in each region $S_i^\\xi$: the Riemannian gradient has inner product at least proportional to $\\|q - e_i\\|$ with the direction to the target basis vector $e_i$, and an implicit-regularization bound keeps iterates inside the region. With probability at least $1/2$ over a uniform random initialization, vanilla Riemannian gradient descent therefore converges linearly to an $O(\\mu)$-accurate solution in $O(\\theta^{-1} n^4 \\log(1/\\mu) + \\log(np)\\log(1/\\varepsilon))$ iterations, and a projected subgradient method on an LP-rounding problem converges linearly to the exact kernel and signals up to a signed shift. The sample complexity is $p \\ge C\\max\\{n, \\kappa^8/(\\theta \\mu^2 \\sigma_{\\min}^2) \\log^4 n\\}\\, \\theta^{-2} n^4 \\log^3 n \\log(\\theta n/\\mu)$, an improvement over the prior $p \\ge \\tilde{\\Omega}(\\max\\{n,\\kappa^8\\} n^8/\\varepsilon^8)$.","pith_inferences":["The paper's phase-transition plots show successful recovery with $p$ close to poly-logarithmic in $n$, far below the theorem's $n^4$ bound; my inference is that the sample-complexity statement is loose and a sharper concentration argument could reduce the polynomial gap.","The region-based geometry plus preconditioning is likely transferable to convolutional dictionary learning and blind gain-and-phase calibration, where similar bilinear nonconvex landscapes appear; the paper suggests these directions but does not prove them.","If the Bernoulli-Gaussian assumption is replaced by heavier-tailed or dependent sparse models, the concentration and sharpness arguments would need reworking; a natural testable extension is to determine empirically how far the phase transition degrades under correlated supports."],"forward_implications":["Vanilla Riemannian gradient descent from a random initialization converges linearly to an approximate solution, so the first phase has no noise-injection or step-size-schedule parameters to tune.","The two-stage method achieves exact recovery: the phase-two LP rounding converges linearly to the signed-shift target, removing the $O(\\mu)$ smoothing error introduced by the Huber loss.","The sample complexity is polynomial in $n$ (about $n^4$) and independent of the recovery precision $\\varepsilon$, improving on the previous $\\tilde{\\Omega}(n^8/\\varepsilon^8)$ bound; the iteration count is about $n^4 + \\log(1/\\varepsilon)$.","With FFT implementation, each gradient or subgradient update costs $O(p n \\log n)$, so the method is computationally practical for large $n$ and is demonstrated on 2D STORM super-resolution imaging data.","Constant sparsity levels $\\theta$ up to about $1/3$ are covered, in contrast to earlier convex approaches requiring $\\theta = O(1/\\sqrt{n})$."],"supporting_citations":[{"why":"prior $\\ell^4$-maximization nonconvex formulation over the sphere with noisy Riemannian gradient descent; the baseline sample/time complexity this paper improves.","marker":"[LB18]"},{"why":"earlier convex $\\ell^1$ approach that required a spiky kernel and $\\theta=O(1/\\sqrt{n})$; motivates relaxing the kernel and sparsity assumptions.","marker":"[WC16]"},{"why":"complete dictionary recovery over the sphere; supplies the spherical-region geometric framework and preconditioning ideas for sparse recovery.","marker":"[SQW16]"},{"why":"subgradient descent for orthogonal dictionary learning; source of the random-initialization-into-region argument and the challenge of non-Lipschitz $\\ell^1$ subgradients.","marker":"[BJS18]"},{"why":"gradient-descent dictionary learning with region-based landscape analysis that the regularity and implicit-regularization proof mirrors.","marker":"[GBW18]"},{"why":"defines the Huber loss $h_\\mu$ used as the smooth $\\ell^1$ surrogate.","marker":"[Hub92]"},{"why":"matrix analysis results on derivatives of $A^{-1/2}$ and Sylvester equations used in the preconditioning perturbation analysis.","marker":"[Bha13]"},{"why":"sharpness framework for subgradient methods with geometrically decreasing step sizes, used to prove linear convergence of LP rounding.","marker":"[DDMP18]"},{"why":"Bernstein inequality for moment-controlled random variables used in concentration of the empirical gradient.","marker":"[FR13]"}],"fun_headline_variants":["Exact recovery in sparse blind deconvolution via sphere descent","Random init + vanilla RGD: provable sparse deconvolution","Improved sample complexity for nonconvex blind deconvolution","Linear convergence for multichannel sparse blind deconvolution"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the generative model: the $p$ inputs are independent Bernoulli-Gaussian with known sparsity $\\theta$ in $(1/n, 1/3)$, and the kernel's discrete Fourier transform has no zero entries; if the signals are not independent sparse Gaussians or the kernel has deep frequency nulls, the benign geometry and the recovery guarantee can fail.","fun_headline_variants_meta":{"raw":{"variants":["Exact recovery in sparse blind deconvolution via sphere descent","Random init + vanilla RGD: provable sparse deconvolution","Improved sample complexity for nonconvex blind deconvolution","Linear convergence for multichannel sparse blind deconvolution"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000805,"raw_usage":{"total_tokens":3592,"prompt_tokens":1059,"completion_tokens":2533,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":675,"completion_tokens_details":{"reasoning_tokens":2463}},"tokens_in":675,"tokens_out":2533,"duration_ms":17273,"temperature":1.0,"reasoning_tokens":2463,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T10:35:06.170385+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Generate measurements $y_i = a * x_i$ with $a$ an invertible kernel of condition number $\\kappa$, $x_i$ i.i.d. Bernoulli-Gaussian at $\\theta=0.25$, and choose $p$ above the Theorem 3.1 bound for small $n$ (say $n=64$, $\\theta=0.25$, $\\mu=10^{-2}$); the two-stage algorithm should recover the kernel and signals to $\\varepsilon$-precision with probability at least $1/2$. If it systematically fails at such parameters—for example, by converging to a spurious stationary point—the claimed guarantee is false; the same test with a kernel whose DFT contains a zero probes the boundary of the invertibility assumption rather than the core claim.","supporting_citations":[],"review_version":1}