×

Greedy low-rank algorithm for spatial connectome regression. (English) Zbl 1437.92005

Summary: Recovering brain connectivity from tract tracing data is an important computational problem in the neurosciences. Mesoscopic connectome reconstruction was previously formulated as a structured matrix regression problem [the third author, S. Mihalas and E. Shea-Brown, “High resolution neural connectivity from incomplete tracing data using nonnegative spline regression”, in: Advances in neural information processing systems 29. Proceedings from the conference “Neural Information Processing Systems 2016”. Red Hook, NY: Curran Associates, Inc. 3099–3107 (2016)], but existing techniques do not scale to the whole-brain setting. The corresponding matrix equation is challenging to solve due to large scale, ill-conditioning, and a general form that lacks a convergent splitting. We propose a greedy low-rank algorithm for the connectome reconstruction problem in very high dimensions. The algorithm approximates the solution by a sequence of rank-one updates which exploit the sparse and positive definite problem structure. This algorithm was described previously [D. Kressner and P. Sirković, Numer. Linear Algebra Appl. 22, No. 3, 564–583 (2015; Zbl 1363.65075)] but never implemented for this connectome problem, leading to a number of challenges. We have had to design judicious stopping criteria and employ efficient solvers for the three main sub-problems of the algorithm, including an efficient GPU implementation that alleviates the main bottleneck for large datasets. The performance of the method is evaluated on three examples: an artificial “toy” dataset and two whole-cortex instances using data from the Allen Mouse Brain Connectivity Atlas. We find that the method is significantly faster than previous methods and that moderate ranks offer a good approximation. This speedup allows for the estimation of increasingly large-scale connectomes across taxa as these data become available from tracing experiments. The data and code are available online.

MSC:

92B20 Neural networks for/in biological studies, artificial life and related topics

Citations:

Zbl 1363.65075

Software:

LBFGS-B; softImpute
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Altas, I.; Dym, J.; Gupta, M.; Manohar, R., Multigrid solution of automatically generated high-order discretizations for the biharmonic equation, SIAM J Sci Comput, 19, 1575-1585 (1998) · Zbl 0918.65079 · doi:10.1137/S1464827596296970
[2] Benner, P., Solving large-scale control problems, IEEE Control Syst Mag, 14, 44-59 (2004)
[3] Benner, P.; Breiten, T., Low rank methods for a class of generalized Lyapunov equations and related issues, Numer Math, 124, 441-470 (2013) · Zbl 1266.65068 · doi:10.1007/s00211-013-0521-0
[4] Benner, P.; Li, R-C; Truhar, N., On the ADI method for Sylvester equations, J Comput Appl Math, 233, 1035-1045 (2009) · Zbl 1176.65050 · doi:10.1016/j.cam.2009.08.108
[5] Benner, P.; Saak, J., Numerical solution of large and sparse continuous time algebraic matrix Riccati and Lyapunov equations: a state of the art survey, GAMM-Mitt, 36, 32-52 (2013) · Zbl 1279.65044 · doi:10.1002/gamm.201310003
[6] Bota, M.; Dong, H-W; Swanson, LW, From gene networks to brain networks, Nat Neurosci, 6, 795-799 (2003) · doi:10.1038/nn1096
[7] Buckner, RL; Margulies, DS, Macroscale cortical organization and a default-like apex transmodal network in the marmoset monkey, Nat Commun, 10 (2019) · doi:10.1038/s41467-019-09812-8
[8] Byrd, R.; Lu, P.; Nocedal, J.; Zhu, C., A limited memory algorithm for bound constrained optimization, SIAM J Sci Comput, 16, 1190-1208 (1995) · Zbl 0836.65080 · doi:10.1137/0916069
[9] Cai, D.; He, X.; Han, J.; Huang, TS, Graph regularized nonnegative matrix factorization for data representation, IEEE Trans Pattern Anal Mach Intell, 33, 1548-1560 (2011) · doi:10.1109/TPAMI.2010.231
[10] Candes, EJ; Plan, Y., Matrix completion with noise, Proc IEEE, 98, 925-936 (2010) · doi:10.1109/JPROC.2009.2035722
[11] Chambolle, A.; Pock, T., An introduction to continuous optimization for imaging, Acta Numer, 25, 161-319 (2016) · Zbl 1343.65064 · doi:10.1017/S096249291600009X
[12] Cichocki A, Zdunek R, Huy Phan A, Amari S. Nonnegative matrix and tensor factorizations: applications to exploratory multi-way data analysis and blind source separation. New York: Wiley; 2009. · doi:10.1002/9780470747278
[13] Damm, T., Direct methods and ADI-preconditioned Krylov subspace methods for generalized Lyapunov equations, Numer Linear Algebra Appl, 15, 853-871 (2008) · Zbl 1212.65175 · doi:10.1002/nla.603
[14] Gămănuţ, R.; Kennedy, H.; Toroczkai, Z.; Ercsey-Ravasz, M.; Essen, DC; Knoblauch, K.; Burkhalter, A., The mouse cortical connectome, characterized by an ultra-dense cortical graph, maintains specificity by distinct connectivity profiles, Neuron, 97, 698-715 (2018) · doi:10.1016/j.neuron.2017.12.037
[15] Golub GH, Van Loan CF. Matrix computations. 4th ed. Baltimore: Johns Hopkins University Press; 2013. · Zbl 1268.65037
[16] Grasedyck, L., Existence of a low rank or H-matrix approximant to the solution of a Sylvester equation, Numer Linear Algebra Appl, 11, 371-389 (2004) · Zbl 1164.65381 · doi:10.1002/nla.366
[17] Grillner, S.; Ip, N.; Koch, C.; Koroshetz, W.; Okano, H.; Polachek, M.; Poo, M.; Sejnowski, TJ, Worldwide initiatives to advance brain research, Nat Neurosci (2016) · doi:10.1038/nn.4371
[18] Hardt, M.; Wootters, M., Fast matrix completion without the condition number, Barcelona, Spain, June 13-15, 2014
[19] Harris, KD; Mihalas, S.; Shea-Brown, E., High resolution neural connectivity from incomplete tracing data using nonnegative spline regression (2016)
[20] Harshman R. Foundations of the PARAFAC procedure: models and conditions for an “explanatory” multi-modal factor analysis. UCLA Working Papers in Phonetics. 1970;16.
[21] Jarlebring E, Mele G, Palitta D, Ringh E. Krylov methods for low-rank commuting generalized Sylvester equations. Numer Linear Algebra Appl. 2018. · Zbl 07031731
[22] Jenett, A.; Rubin, GM; Ngo, T-TB; Shepherd, D.; Murphy, C.; Dionne, H.; Pfeiffer, BD; Cavallaro, A.; Hall, D.; Jeter, J.; Iyer, N.; Fetter, D.; Hausenfluck, JH; Peng, H.; Trautman, ET; Svirskas, RR; Myers, EW; Iwinski, ZR; Aso, Y.; DePasquale, GM; Enos, A.; Hulamm, P.; Chun Benny Lam, S.; Li, H-H; Laverty, TR; Long Lei Qu, F.; Murphy, SD; Rokicki, K.; Safford, T.; Shaw, K.; Simpson, JH; Sowell, A.; Tae, S.; Yu, Y.; Zugates, CT, A GAL4-driver line resource for drosophila neurobiology, Cell Reports, 2, 991-1001 (2012) · doi:10.1016/j.celrep.2012.09.011
[23] Kasthuri, N.; Hayworth, KJ; Berger, DR; Lee Schalek, R.; Conchello, JA; Knowles-Barley, S.; Lee, D.; Vázquez-Reina, A.; Kaynig, V.; Jones, TR; Roberts, M.; Lyskowski Morgan, J.; Carlos Tapia, J.; Sebastian Seung, H.; Gray Roncal, W.; Tzvi Vogelstein, J.; Burns, R.; Lewis Sussman, D.; Priebe, CE; Pfister, H.; Lichtman, JW, Saturated reconstruction of a volume of neocortex, Cell, 162, 648-661 (2015) · doi:10.1016/j.cell.2015.06.054
[24] Kennedy H, Van Essen DC, Christen Y, editors. Micro-, meso- and macro-connectomics of the brain. Research and perspectives in neurosciences. Berlin: Springer; 2016.
[25] Knox JE, Decker Harris K, Graddis N, Whitesell JD, Zeng H, Harris JA, Shea-Brown E, Mihalas S. High Resolution Data-Driven Model of the Mouse Connectome. bioRxiv 2018. p. 293019. https://doi.org/10.1101/293019.
[26] Kressner, D.; Sirković, P., Truncated low-rank methods for solving general linear matrix equations, Numer Linear Algebra Appl, 22, 564-583 (2015) · Zbl 1363.65075 · doi:10.1002/nla.1973
[27] Kressner, D.; Tobler, C., Krylov subspace methods for linear systems with tensor product structure, SIAM J Matrix Anal Appl, 31, 1688-1714 (2010) · Zbl 1208.65044 · doi:10.1137/090756843
[28] Lein, ES; Hawrylycz, MJ; Ao, N.; Ayres, M.; Bensinger, A.; Bernard, A.; Boe, AF; Boguski, MS; Brockway, KS; Byrnes, EJ; Chen, L.; Chen, L.; Chen, T-M; Chi Chin, M.; Chong, J.; Crook, BE; Czaplinska, A.; Dang, CN; Datta, S.; Dee, NR; Desaki, AL; Desta, T.; Diep, E.; Dolbeare, TA; Donelan, MJ; Dong, H-W; Dougherty, JG; Ben Duncan, J.; Ebbert, AJ; Eichele, G.; Estin, LK; Faber, C.; Facer, BA; Fields, R.; Fischer, SR; Fliss, TP; Frensley, C.; Gates, SN; Glattfelder, KJ; Halverson, KR; Hart, MR; Hohmann, JG; Howell, MP; Jeung, DP; Johnson, RA; Karr, PT; Kawal, R.; Kidney, JM; Knapik, RH; Kuan, CL; Lake, JH; Laramee, AR; Larsen, KD; Lau, C.; Lemon, TA; Liang, AJ; Liu, Y.; Luong, LT; Michaels, J.; Morgan, JJ; Morgan, RJ; Mortrud, MT; Mosqueda, NF; Ng, LL; Ng, R.; Orta, GJ; Overly, CC; Pak, TH; Parry, SE; Pathak, SD; Pearson, OC; Puchalski, RB; Riley, ZL; Rockett, HR; Rowland, SA; Royall, JJ; Ruiz, MJ; Sarno, NR; Schaffnit, K.; Shapovalova, NV; Sivisay, T.; Slaughterbeck, CR; Smith, SC; Smith, KA; Smith, BI; Sodt, AJ; Stewart, NN; Stumpf, K-R; Sunkin, SM; Sutram, M.; Tam, A.; Teemer, CD; Thaller, C.; Thompson, CL; Varnam, LR; Visel, A.; Whitlock, RM; Wohnoutka, PE; Wolkey, CK; Wong, VY; Wood, M.; Yaylaoglu, MB; Young, RC; Youngstrom, BL; Feng Yuan, X.; Zhang, B.; Zwingman, TA; Jones, AR, Genome-wide atlas of gene expression in the adult mouse brain, Nature, 445, 168-176 (2007) · doi:10.1038/nature05453
[29] Mackevicius EL, Bahle AH, Williams AH, Gu S, Denissenko NI, Goldman MS, Fee MS. Unsupervised Discovery of Temporal Sequences in High-Dimensional Datasets, with Applications to Neuroscience. bioRxiv 2018. p. 273128. https://doi.org/10.1101/273128.
[30] Majka, P.; Chaplin, TA; Yu, H-H; Tolpygo, A.; Mitra, PP; Wójcik, DK; Rosa, MGP, Towards a comprehensive atlas of cortical connections in a primate brain: mapping tracer injection studies of the common marmoset into a reference digital template, J Comp Neurol, 524, 2161-2181 (2016) · doi:10.1002/cne.24023
[31] Mazumder, R.; Hastie, T.; Tibshirani, R., Spectral regularization algorithms for learning large incomplete matrices, J Mach Learn Res, 11, 2287-2322 (2010) · Zbl 1242.68237
[32] Mitra, PP, The circuit architecture of whole brains at the mesoscopic scale, Neuron, 83, 1273-1283 (2014) · doi:10.1016/j.neuron.2014.08.055
[33] Nouy, A., Proper generalized decompositions and separated representations for the numerical solution of high dimensional stochastic problems, Arch Comput Methods Eng, 17, 403-434 (2010) · Zbl 1269.76079 · doi:10.1007/s11831-010-9054-1
[34] Oh, SW; Harris, JA; Ng, L.; Winslow, B.; Cain, N.; Mihalas, S.; Wang, Q.; Lau, C.; Kuan, L.; Henry, AM; Mortrud, MT; Ouellette, B.; Nghi Nguyen, T.; Sorensen, SA; Slaughterbeck, CR; Wakeman, W.; Li, Y.; Feng, D.; Ho, A.; Nicholas, E.; Hirokawa, KE; Bohn, P.; Joines, KM; Peng, H.; Hawrylycz, MJ; Phillips, JW; Hohmann, JG; Wohnoutka, P.; Gerfen, CR; Koch, C.; Bernard, A.; Dang, C.; Jones, AR; Zeng, H., A mesoscale connectome of the mouse brain, Nature, 508, 207-214 (2014) · doi:10.1038/nature13186
[35] Ortega JM, Rheinboldt WC. Iterative solution of nonlinear equations in several variables. Philadelphia: SIAM; 2000. · Zbl 0949.65053 · doi:10.1137/1.9780898719468
[36] Palitta D, Kürschner P. On the convergence of krylov methods with low-rank truncations. e-print arXiv:1909.01226 math.NA, 2019. · Zbl 1482.65067
[37] Pati, YC; Rezaiifar, R.; Krishnaprasad, PS, Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition, No. 1, 40-44 (1993) · doi:10.1109/ACSSC.1993.342465
[38] Pnevmatikakis, EA; Soudry, D.; Gao, Y.; Machado, TA; Merel, J.; Pfau, D.; Reardon, T.; Mu, Y.; Lacefield, C.; Yang, W.; Ahrens, M.; Bruno, R.; Jessell, TM; Peterka, DS; Yuste, R.; Paninski, L., Simultaneous denoising, deconvolution, and demixing of calcium imaging data, Neuron, 89, 285-299 (2016) · doi:10.1016/j.neuron.2015.11.037
[39] Powell, CE; Silvester, D.; Simoncini, V., An efficient reduced basis solver for stochastic Galerkin matrix equations, SIAM J Sci Comput, 39, a141-a163 (2017) · Zbl 1381.35257 · doi:10.1137/15M1032399
[40] Reimann, MW; Gevaert, M.; Shi, Y.; Lu, H.; Markram, H.; Muller, E., A null model of the mouse whole-neocortex micro-connectome, Nat Commun, 10, 1-16 (2019) · doi:10.1038/s41467-019-11630-x
[41] Ringh, E.; Mele, G.; Karlsson, J.; Jarlebring, E., Sylvester-based preconditioning for the waveguide eigenvalue problem, Linear Algebra Appl, 542, 441-463 (2018) · Zbl 1418.65050 · doi:10.1016/j.laa.2017.06.027
[42] Rudin, LI; Osher, S.; Fatemi, E., Nonlinear total variation based noise removal algorithms, Phys D: Nonlinear Phenom, 60, 259-268 (1992) · Zbl 0780.49028 · doi:10.1016/0167-2789(92)90242-F
[43] Shank, SD; Simoncini, V.; Szyld, DB, Efficient low-rank solution of generalized Lyapunov equations, Numer Math, 134, 327-342 (2015) · Zbl 1348.65078 · doi:10.1007/s00211-015-0777-7
[44] Simoncini, V., Computational methods for linear matrix equations, SIAM Rev, 38, 377-441 (2016) · Zbl 1386.65124 · doi:10.1137/130912839
[45] Sorber, L.; Barel, M.; Lathauwer, L., Optimization-based algorithms for tensor decompositions: canonical polyadic decomposition, decomposition in rank-\(({L}_r, {L}_r,1)\) terms, and a new generalization, SIAM J Optim, 23, 695-720 (2013) · Zbl 1277.90073 · doi:10.1137/120868323
[46] Sporns O. Networks of the brain. 1st ed. Cambridge: MIT Press. 2010. · doi:10.7551/mitpress/8476.001.0001
[47] Essen, DC, Cartography and connectomes, Neuron, 80, 775-790 (2013) · doi:10.1016/j.neuron.2013.10.027
[48] Wahba G. Spline models for observational data. Philadelphia: SIAM; 1990. · Zbl 0813.62001 · doi:10.1137/1.9781611970128
[49] Ypma, RJF; Bullmore, ET, Statistical analysis of tract-tracing experiments demonstrates a dense, complex cortical network in the mouse, PLoS Comput Biol, 12 (2016) · doi:10.1371/journal.pcbi.1005104
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.