Convolutional Dictionary Learning With Grid Refinement

Andrew H. Song, Francisco J. Flores, Demba E. BaIEEE TSP 2020 · OpenReview

Abstract

Given a continuous-domain signal that can be modeled as the superposition of localized events from multiple sources, the goal of Convolutional Dictionary Learning (CDL) is to identify the location of the events—by Convolutional Sparse Coding (CSC)—and learn the template for each source—through a Convolutional Dictionary Update (CDU) step. In practice, because we observe samples of the continuous-domain signal on a discrete grid, classical CSC methods can only produce estimates of the locations of the events on this grid, which degrades the performance of the CDU step. We introduce a CDL framework that significantly reduces the errors arising from performing the estimation on the grid. Specifically, we construct an expanded dictionary that comprises, not only discrete shifts of the templates, but also variants shifted by a non-integer amount and smoothly interpolated, that enable CSC and CDU to operate at a finer resolution than that of the original sampling grid. We term this approach CDL with grid refinement. For CSC, we develop a novel computationally efficient algorithm, termed Convolutional Orthogonal Matching Pursuit with an interpolated dictionary (COMP-INTERP). We use simulated data to compare COMP-INTERP to state-of-the-art CSC algorithms for estimating off-the-grid events, and demonstrate that it 1) achieves a competitive level of accuracy, and 2) is one order of magnitude faster. For CDU, we derive a novel procedure to update the templates given sparse codes that can occur both on and off the sampling grid. We also show that 3) dictionary update with the overcomplete dictionary yields more accurate templates. Finally, we demonstrate the competitive performance of the algorithms in two applications, namely spike sorting and super-resolution microscopy.

The Challenge of Off-the-Grid Events

In signal processing, complex signals are often modeled as a superposition of simple "templates" occurring at specific times—such as neural spikes in an electrode recording or individual molecules in a microscope image. This is the core domain of Convolutional Dictionary Learning (CDL).

Standard CDL approaches assume these events occur exactly on the discrete ticks of a sampling grid. However, physical phenomena are continuous; a neuron might fire between two sampling points. Forcing these events onto the nearest grid point introduces time-quantization errors. This misalignment doesn't just degrade timing accuracy; it also "blurs" the learned templates during the update phase, as the algorithm attempts to average out misaligned events. While increasing the sampling rate could theoretically solve this, it quickly becomes computationally prohibitive due to memory and processing constraints.

Methods: Moving Beyond the Grid

To address these limitations, this framework introduces a two-part solution for "off-the-grid" learning:

1. Interpolated Dictionary

Instead of a standard dictionary, the authors construct an expanded, overcomplete version. Using bandlimited (sinc) interpolation, they create versions of each template shifted by non-integer amounts (fractions of a sampling interval). This allows the model to represent events that fall between the original grid points.

The process of generating an interpolated dictionary through D/C conversion, non-integer shifting, and resampling.

2. COMP-INTERP and the "Cholesky Trick"

For sparse coding, the authors developed COMP-INTERP (Convolutional Orthogonal Matching Pursuit with Interpolated Dictionary). While standard Orthogonal Matching Pursuit (OMP) is often slow for convolutional data due to expensive projection steps, this algorithm utilizes a clever Cholesky factorization update. By updating the Cholesky factor of the system matrix iteratively rather than recomputing it, the algorithm achieves extreme efficiency, bypassing the performance gap that typically makes greedy methods slower than simpler matching pursuit alternatives.

Key Results and Insights

The framework was validated using synthetic signals and real-world extracellular recordings from a rat hippocampus. The results highlight three major breakthroughs:

  • Massive Speedup: In benchmarks against Continuous Basis Pursuit (CBP)—the previous state-of-the-art convex method—COMP-INTERP was two orders of magnitude faster (e.g., 1.16 seconds vs. 145 seconds for a 3-second signal).
  • Timing Precision: COMP-INTERP significantly reduced "hit error" compared to standard discrete methods. As the interpolation factor ($K$) increased, the algorithm identified event times with much higher precision.
  • Template Fidelity: By accounting for non-integer shifts during the dictionary update phase (CDU-INTERP), the algorithm prevents the "smearing" effect. This leads to sharper, more biologically plausible templates in neural applications.
Comparison of standard pursuit (COMP, BP) vs. interpolated versions (COMP-INTERP, CBP). The red lines show how grid refinement allows the algorithm to estimate event locations between grid points, matching the ground truth (bottom black dot) more closely than blue discrete-grid estimates.

Conclusion

This research demonstrates that a properly optimized greedy approach can match the accuracy of complex convex optimization while being vastly more practical for large-scale datasets. By refining the grid through interpolation, CDL can finally account for the continuous nature of physical signals without the computational burden of oversampling. Future work aims to extend this to multi-channel sensor arrays and leverage GPU acceleration for even greater performance.

Summary updated

Abstract

Given a continuous-domain signal that can be modeled as the superposition of localized events from multiple sources, the goal of Convolutional Dictionary Learning (CDL) is to identify the location of the events-by Convolutional Sparse Coding (CSC)-and learn the template for each source-through a Convolutional Dictionary Update (CDU) step. In practice, because we observe samples of the continuous-domain signal on a discrete grid, classical CSC methods can only produce estimates of the locations of the events on this grid, which degrades the performance of the CDU step. We introduce a CDL framework that significantly reduces the errors arising from performing the estimation on the grid. Specifically, we construct an expanded dictionary that comprises, not only discrete shifts of the templates, but also variants shifted by a non-integer amount and smoothly interpolated, that enable CSC and CDU to operate at a finer resolution than that of the original sampling grid. We term this approach CDL with grid refinement. For CSC, we develop a novel computationally efficient algorithm, termed Convolutional Orthogonal Matching Pursuit with an interpolated dictionary (COMP-INTERP). We use simulated data to compare COMP-INTERP to state-of-the-art CSC algorithms for estimating off-the-grid events, and demonstrate that it 1) achieves a competitive level of accuracy, and 2) is one order of magnitude faster. For CDU, we derive a novel procedure to update the templates given sparse codes that can occur both on and off the sampling grid. We also show that 3) dictionary update with the overcomplete dictionary yields more accurate templates. Finally, we demonstrate the competitive performance of the algorithms in two applications, namely spike sorting and super-resolution microscopy.
BibTeX
@article{song2020convolutional,
  author = {Andrew H. Song and Francisco J. Flores and Demba E. Ba},
  title = {{Convolutional Dictionary Learning With Grid Refinement}},
  journal = {IEEE Trans. Signal Process.},
  year = {2020},
  url = {https://openreview.net/forum?id=90TnyyMfbs},
}
Figure