Short-and-sparse deconvolution (SaSD) is the problem of extracting localized, recurring motifs in signals with spatial or temporal structure. Variants of this problem arise in applications such as image deblurring, microscopy, neural spike sorting, and more. The problem is challenging in both theory and practice, as natural optimization formulations are nonconvex. Moreover, practical deconvolution problems involve smooth motifs (kernels) whose spectra decay rapidly, resulting in poor conditioning and numerical challenges. This paper is motivated by recent theoretical advances (Zhang et al., 2017;Kuo et al., 2019), which characterize the optimization landscape of a particular nonconvex formulation of SaSD and give a provable algorithm which exactly solves certain non-practical instances of the SaSD problem. We leverage the key ideas from this theory (sphere constraints, datadriven initialization) to develop a practical algorithm, which performs well on data arising from a range of application areas. We highlight key additional challenges posed by the ill-conditioning of real SaSD problems, and suggest heuristics (acceleration, continuation, reweighting) to mitigate them. Experiments demonstrate the performance and generality of the proposed method.
This paper analyzes some of the optimization challenges presented by a particular formulation of "short-and-sparse deconvolution" and proposes a new general purpose algorithm to try to alleviate them. The paper is reasonably clearly written and the experimental results seem impressive (as a non-specialist in this area). However the experimental investigation on real data does not compare to a baseline, which seems like an essential part of investigating the proposed method. If this were corrected I would recommend an accept.
I would like to make it clear that I have little experience in this area and am not familiar with relevant previous literature, so I was only able to roughly judge novelty of the ideas and how the experimental results might compare with existing approaches.
Major comments:
For the experimental investigations on real data there was no baseline presented. Are there no task-specific algorithms that have previously been developed for deconvolution of calcium signals, fluoresence microscopy and calcium imaging? At the very least it would be helpful to compare to one of the other general purpose methods used for figure 6.
It seemed like a lot of the paper is taken up with a recap of the results presented in Kuo et al. (2019), and it didn't always seem clear exactly what the relevance of these results were to the present paper. In particular it seemed strange to me to devote so much space in section 2 to the ABL objective given that it is not used (as far as I can tell) for the proposed algorithm.
Minor comments:
The abstract says "We leverage... sphere constraints, data-driven initialization". Is the effect of these actually investigated experimentally?
In the abstract, "This is used to derive a provable algorithm" makes it sounds to me like this will be done in the current paper.
In the abstract, a reference for the "due to the spectral decay of the kernel a_0" claim would be helpful.
In the notation section, the definition of the Riemannian gradient seems a little sloppy mathematically: strictly f needs to be defined on $\reals^p$ (or an open subset of $\reals^p$ containing $S^{p - 1}$) in order for the right side of the gradient expression to be defined.
At the start of section 2, it would be helpful to give a one-sentence description of the unifying theme of the section.
It might be helpful to explicitly state that "coherence" is related to the strength of temporal / spatial correlations to aid developing the reader's intuition for the meaning of $\mu(a)$.
Throughout the paper the problems that multiple equivalent local optima (due to shift symmetry) cause come up repeatedly. What happens if this symmetry is removed straightforwardly by adding a term to the cost function to encourage a particular value of $a$ to be the largest?
In section 2.1, for "It analyzes an ABL...", it's not completely clear what "It" refers to (I presume Kuo et. al (2019) from context).
Marginalization in my experience refers to a "partial summing" operation, whereas just above (4) it is used to refer to a "partial maximization" operation. This seems non-standard to me, but is this usage standard in this field?
I didn't understand the relevance of the sentence "Under its marginalization... smaller dimension p << m." to the present paper. The sentence also seemed vague and difficult to understand if you were not already familiar with this result. It should also have a reference to justify this claim.
It wasn't clear to me whether figure 1 were schematic "rough intuition" diagrams intended merely to be suggestive, or provably showing the type of behavior that happens in all cases. Also, what are the axes, generic "parameter space", I guess? I also didn't follow why (a) appears projected on to a plane while (b) and (c) appear projected on to a sphere(?)
In section 3, under "momentum acceleration", it would be helpful to justify the claim that "In shift-coherent settings, the Hessian... ill-conditioned...".
In figure 4, the axis labels are much too small to read. In figure 5 (b), the red poorer results obscure the green better results.
In figure 4 (d), is it fair to say that the main convergence speed improvement for homotopy-iADM is in going faster from "quite near" the optimum to "really near" it, rather than getting "quite near" it in the first place? If so, isn't the latter more often what's relevant in practical applications?
In figure 5, it's a little confusing to switch color meanings between (a) and (b).
Reweighting seems to have a dramatic positive effect in figure 5. Is it worth investigating its effect in the other experiments as well, for example in figure 4?
In figure 6 (b), is there any reason not to compare against standard black box optimizers like vanilla SGD, ADAM, etc (possibly with projection to satisfy the sphere constraint if necessary)? Would they perform very badly?
Typo "Whilst $a_0$ nor $x_0$" should be "Whilst $a_0$ and $x_0$".
What does the square-boxed convolution operator in (8) mean?