Exact spike train inference via \(\ell_{0}\) optimization. (English) Zbl 1412.62159

Summary: In recent years new technologies in neuroscience have made it possible to measure the activities of large numbers of neurons simultaneously in behaving animals. For each neuron a fluorescence trace is measured; this can be seen as a first-order approximation of the neuron’s activity over time. Determining the exact time at which a neuron spikes on the basis of its fluorescence trace is an important open problem in the field of computational neuroscience.
Recently, a convex optimization problem involving an \(\ell_{1}\) penalty was proposed for this task. In this paper we slightly modify that recent proposal by replacing the \(\ell_{1}\) penalty with an \(\ell_{0}\) penalty. In stark contrast to the conventional wisdom that \(\ell_{0}\) optimization problems are computationally intractable, we show that the resulting optimization problem can be efficiently solved for the global optimum using an extremely simple and efficient dynamic programming algorithm. Our R-language implementation of the proposed algorithm runs in a few minutes on fluorescence traces of 100,000 timesteps. Furthermore, our proposal leads to substantial improvements over the previous \(\ell_{1}\) proposal, in simulations as well as on two calcium imaging datasets.
R-language software for our proposal is available on CRAN in the package LZeroSpikeInference. Instructions for running this software in python can be found at https://github.com/jewellsean/LZeroSpikeInference.


62P10 Applications of statistics to biology and medical sciences; meta analysis
62J07 Ridge regression; shrinkage estimators (Lasso)
62H12 Estimation in multivariate analysis
68T05 Learning and adaptive systems in artificial intelligence
Full Text: DOI arXiv Euclid


[1] Ahrens, M. B., Orger, M. B., Robson, D. N., Li, J. M. and Keller, P. J. (2013). Whole-brain functional imaging at cellular resolution using light-sheet microscopy. Nat. Methods10 413-420.
[2] Aue, A. and Horváth, L. (2013). Structural breaks in time series. J. Time Series Anal.34 1-16. · Zbl 1274.62553 · doi:10.1111/j.1467-9892.2012.00819.x
[3] Auger, I. E. and Lawrence, C. E. (1989). Algorithms for the optimal identification of segment neighborhoods. Bull. Math. Biol.51 39-54. · Zbl 0658.92010 · doi:10.1007/BF02458835
[4] Bien, J. and Witten, D. (2016). Penalized estimation in complex models. In Handbook of Big Data. 285-303. CRC Press, Boca Raton, FL.
[5] Boyd, S. and Vandenberghe, L. (2004). Convex Optimization. Cambridge Univ. Press, Cambridge. · Zbl 1058.90049
[6] Boysen, L., Kempe, A., Liebscher, V., Munk, A. and Wittich, O. (2009). Consistencies and rates of convergence of jump-penalized least squares estimators. Ann. Statist.37 157-183. · Zbl 1155.62034 · doi:10.1214/07-AOS558
[7] Braun, J. V. and Müller, H.-G. (1998). Statistical methods for DNA sequence segmentation. Statist. Sci.13 142-162. · Zbl 0960.62121
[8] Brunel, N. and Wang, X.-J. (2003). What determines the frequency of fast network oscillations with irregular neural discharges? I. Synaptic dynamics and excitation-inhibition balance. J. Neurophysiol.90 415-430.
[9] Cavallari, S., Panzeri, S. and Mazzoni, A. (2016). Comparison of the dynamics of neural interactions between current-based and conductance-based integrate-and-fire recurrent networks. Frontiers in Neural Circuits8.
[10] Chen, T.-W., Wardill, T. J., Sun, Y., Pulver, S. R., Renninger, S. L., Baohan, A., Schreiter, E. R., Kerr, R. A., Orger, M. B., Jayaraman, V. et al. (2013). Ultrasensitive fluorescent proteins for imaging neuronal activity. Nature499 295-300.
[11] Dalalyan, A. S., Hebiri, M. and Lederer, J. (2017). On the prediction performance of the Lasso. Bernoulli23 552-581. · Zbl 1359.62295 · doi:10.3150/15-BEJ756
[12] Davies, P. L. and Kovac, A. (2001). Local extremes, runs, strings and multiresolution. Ann. Statist.29 1-65. · Zbl 1029.62038 · doi:10.1214/aos/996986501
[13] Davis, R. A., Lee, T. C. M. and Rodriguez-Yam, G. A. (2006). Structural break estimation for nonstationary time series models. J. Amer. Statist. Assoc.101 223-239. · Zbl 1118.62359 · doi:10.1198/016214505000000745
[14] de Rooi, J. and Eilers, P. (2011). Deconvolution of pulse trains with the \(L_0\) penalty. Anal. Chim. Acta705 218-226.
[15] de Rooi, J. J., Ruckebusch, C. and Eilers, P. H. C. (2014). Sparse deconvolution in one and two dimensions: Applications in endocrinology and single-molecule fluorescence imaging. Anal. Chem.86 6291-6298.
[16] Deneux, T., Kaszas, A., Szalay, G., Katona, G., Lakner, T., Grinvald, A., Rózsa, B. and Vanzetta, I. (2016). Accurate spike estimation from noisy calcium signals for ultrafast three-dimensional imaging of large neuronal populations in vivo. Nat. Commun.7 12190.
[17] Dombeck, D. A., Khabbaz, A. N., Collman, F., Adelman, T. L. and Tank, D. W. (2007). Imaging large-scale neural activity with cellular resolution in awake, mobile mice. Neuron56 43-57.
[18] Friedrich, J. and Paninski, L. (2016). Fast active set methods for online spike inference from calcium imaging. In Advances in Neural Information Processing Systems 1984-1992.
[19] Friedrich, J., Zhou, P. and Paninski, L. (2017). Fast online deconvolution of calcium imaging data. PLoS Comput. Biol.13 e1005423.
[20] Fryzlewicz, P. (2014). Wild binary segmentation for multiple change-point detection. Ann. Statist.42 2243-2281. · Zbl 1302.62075 · doi:10.1214/14-AOS1245
[21] Grewe, B. F., Langer, D., Kasper, H., Kampa, B. M. and Helmchen, F. (2010). High-speed in vivo calcium imaging reveals neuronal network activity with near-millisecond precision. Nat. Methods7 399-405.
[22] Harchaoui, Z. and Lévy-Leduc, C. (2010). Multiple change-point estimation with a total variation penalty. J. Amer. Statist. Assoc.105 1480-1493. · Zbl 1388.62211 · doi:10.1198/jasa.2010.tm09181
[23] Hastie, T., Tibshirani, R. and Friedman, J. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction, 2nd ed. Springer, New York. · Zbl 1273.62005
[24] Hastie, T., Tibshirani, R. and Wainwright, M. (2015). Statistical Learning with Sparsity: The Lasso and Generalizations. Monographs on Statistics and Applied Probability143. CRC Press, Boca Raton, FL. · Zbl 1319.68003
[25] Hawrylycz, M., Anastassiou, C., Arkhipov, A., Berg, J., Buice, M., Cain, N., Gouwens, N. W., Gratiy, S., Iyer, R., Lee, J. H. et al. (2016). Inferring cortical function in the mouse visual system through large-scale systems neuroscience. Proc. Natl. Acad. Sci. USA113 7337-7344.
[26] Hocking, T. D., Rigaill, G., Fearnhead, P. and Bourque, G. (2017). A log-linear time algorithm for constrained changepoint detection. Preprint. Available at ArXiv:1703.03352. · Zbl 1502.92008
[27] Holekamp, T. F., Turaga, D. and Holy, T. E. (2008). Fast three-dimensional fluorescence imaging of activity in neural populations by objective-coupled planar illumination microscopy. Neuron57 661-672.
[28] Hugelier, S., de Rooi, J. J., Bernex, R., Duwé, S., Devos, O., Sliwa, M., Dedecker, P., Eilers, P. H. and Ruckebusch, C. (2016). Sparse deconvolution of high-density super-resolution images. Sci. Rep.6.
[29] Jackson, B., Scargle, J. D., Barnes, D., Arabhi, S., Alt, A., Gioumousis, P., Gwin, E., Sangtrakulcharoen, P., Tan, L. and Tsai, T. T. (2005). An algorithm for optimal partitioning of data on an interval. IEEE Signal Process. Lett.12 105-108.
[30] Johnson, N. A. (2013). A dynamic programming algorithm for the fused lasso and \(L_0\)-segmentation. J. Comput. Graph. Statist.22 246-260.
[31] Killick, R., Fearnhead, P. and Eckley, I. A. (2012). Optimal detection of changepoints with a linear computational cost. J. Amer. Statist. Assoc.107 1590-1598. · Zbl 1258.62091 · doi:10.1080/01621459.2012.737745
[32] Lee, C.-B. (1995). Estimating the number of change points in a sequence of independent normal random variables. Statist. Probab. Lett.25 241-248. · Zbl 0839.62015 · doi:10.1016/0167-7152(94)00227-Y
[33] Lin, K., Sharpnack, J., Rinaldo, A. and Tibshirani, R. J. (2016). Approximate recovery in changepoint problems, from \(ℓ_2\) estimation error rates. Preprint. Available at ArXiv:1606.06746.
[34] Maidstone, R., Hocking, T., Rigaill, G. and Fearnhead, P. (2017). On optimal multiple changepoint algorithms for large data. Stat. Comput.27 519-533. · Zbl 1505.62269 · doi:10.1007/s11222-016-9636-3
[35] Mammen, E. and van de Geer, S. (1997). Locally adaptive regression splines. Ann. Statist.25 387-413. · Zbl 0871.62040 · doi:10.1214/aos/1034276635
[36] Mazzoni, A., Panzeri, S., Logothetis, N. K. and Brunel, N. (2008). Encoding of naturalistic stimuli by local field potential spectra in networks of excitatory and inhibitory neurons. PLoS Comput. Biol.4 e1000239, 20.
[37] Olshen, A. B., Venkatraman, E., Lucito, R. and Wigler, M. (2004). Circular binary segmentation for the analysis of array-based DNA copy number data. Biostatistics5 557-572. · Zbl 1155.62478 · doi:10.1093/biostatistics/kxh008
[38] Pnevmatikakis, E. A., Merel, J., Pakman, A. and Paninski, L. (2013). Bayesian spike inference from calcium imaging data. In Signals, Systems and Computers, 2013 Asilomar Conference on 349-353. IEEE.
[39] Pnevmatikakis, E. A., Soudry, D., Gao, Y., Machado, T. A., Merel, J., Pfau, D., Reardon, T., Mu, Y., Lacefield, C., Yang, W. et al. (2016). Simultaneous denoising, deconvolution, and demixing of calcium imaging data. Neuron89 285-299.
[40] Prevedel, R., Yoon, Y.-G., Hoffmann, M., Pak, N., Wetzstein, G., Kato, S., Schrödel, T., Raskar, R., Zimmer, M., Boyden, E. S. et al. (2014). Simultaneous whole-animal 3D imaging of neuronal activity using light-field microscopy. Nat. Methods11 727-730.
[41] Qian, J. and Jia, J. (2012). On pattern recovery of the fused lasso. Preprint. Available at ArXiv:1211.5194. · Zbl 1468.62161 · doi:10.1016/j.csda.2015.08.013
[42] Rinaldo, A. (2009). Properties and refinements of the fused lasso. Ann. Statist.37 2922-2952. · Zbl 1173.62027 · doi:10.1214/08-AOS665
[43] Rojas, C. R. and Wahlberg, B. (2014). On change point detection using the fused lasso method. Preprint. Available at ArXiv:1401.5408.
[44] Sasaki, T., Takahashi, N., Matsuki, N. and Ikegaya, Y. (2008). Fast and accurate detection of action potentials from somatic calcium fluctuations. J. Neurophysiol.100 1668-1676.
[45] Scott, A. J. and Knott, M. (1974). A cluster analysis method for grouping means in the analysis of variance. Biometrics30 507-512. · Zbl 0284.62044 · doi:10.2307/2529204
[46] Theis, L., Berens, P., Froudarakis, E., Reimer, J., Rosón, M. R., Baden, T., Euler, T., Tolias, A. S. and Bethge, M. (2016). Benchmarking spike rate inference in population calcium imaging. Neuron90 471-482.
[47] Tibshirani, R., Saunders, M., Rosset, S., Zhu, J. and Knight, K. (2005). Sparsity and smoothness via the fused lasso. J. R. Stat. Soc. Ser. B. Stat. Methodol.67 91-108. · Zbl 1060.62049 · doi:10.1111/j.1467-9868.2005.00490.x
[48] van Rossum, M. C. (2001). A novel spike distance. Neural Comput.13 751-763. · Zbl 0979.92011 · doi:10.1162/089976601300014321
[49] Victor, J. D. and Purpura, K. P. (1996). Nature and precision of temporal coding in visual cortex: A metric-space analysis. J. Neurophysiol.76 1310-1326.
[50] Victor, J. D. and Purpura, K. P. (1997). Metric-space analysis of spike trains: Theory, algorithms and application. Network8 127-164. · Zbl 0927.92011 · doi:10.1088/0954-898X_8_2_003
[51] Vogelstein, J. T., Watson, B. O., Packer, A. M., Yuste, R., Jedynak, B. and Paninski, L. (2009). Spike inference from calcium imaging using sequential Monte Carlo methods. Biophys. J.97 636-655.
[52] Vogelstein, J. T., Packer, A. M., Machado, T. A., Sippy, T., Babadi, B., Yuste, R. and Paninski, L. (2010). Fast nonnegative deconvolution for spike train inference from population calcium imaging. J. Neurophysiol.104 3691-3704.
[53] Volgushev, M., Ilin, V. and Stevenson, I. H. (2015). Identifying and tracking simulated synaptic inputs from neuronal firing: Insights from in vitro experiments. PLoS Comput. Biol.11 e1004167.
[54] Yaksi, E. and Friedrich, R. W. (2006). Reconstruction of firing rate changes across neuronal populations by temporally deconvolved Ca2+ imaging. Nat. Methods3 377-383.
[55] Yao, Y.-C. (1988). Estimating the number of change-points via Schwarz’ criterion. Statist. Probab. Lett.6 181-189. · Zbl 0642.62016 · doi:10.1016/0167-7152(88)90118-6
[56] Yao, Y.-C. and Au, S. T. (1989). Least-squares estimation of a step function. Sankhyā Ser. A51 370-381. · Zbl 0711.62031
[57] Zou, H. (2006). The adaptive lasso and its oracle properties. J. Amer. Statist. Assoc.101 1418-1429. · Zbl 1171.62326 · doi:10.1198/016214506000000735
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.