Abstract
Solving inverse problems is a fundamental component of science, engineering and mathematics. With the advent of deep learning, deep neural networks have significant potential to outperform existing state-of-the-art, model-based methods for solving inverse problems. However, it is known that current data-driven approaches face several key issues, notably hallucinations, instabilities and unpredictable generalization, with potential impact in critical tasks such as medical imaging. This raises the key question of whether or not one can construct deep neural networks for inverse problems with explicit stability and accuracy guarantees. In this work, we present a novel construction of accurate, stable and efficient neural networks for inverse problems with general analysis-sparse models, termed NESTANets. To construct the network, we first unroll NESTA, an accelerated first-order method for convex optimization. The slow convergence of this method leads to deep networks with low efficiency. Therefore, to obtain shallow, and consequently more efficient, networks we combine NESTA with a novel restart scheme. We then use compressed sensing techniques to demonstrate accuracy and stability. We showcase this approach in the case of Fourier imaging, and verify its stability and performance via a series of numerical experiments. The key impact of this work is demonstrating the construction of efficient neural networks based on unrolling with guaranteed stability and accuracy.
Similar content being viewed by others
Change history
Notes
The full quote reads: “Such hallucinatory features are not acceptable and especially problematic if they mimic normal structures that are either not present or actually abnormal.”
For example, in the work On hallucinations in tomographic image reconstruction [21] the authors write “The potential lack of generalization of deep learning-based reconstruction methods as well as their innate unstable nature may cause false structures to appear in the reconstructed image that are absent in the object being imaged”.
Specifically, in [84, Thm. 2] the objective error bound is given in terms of \(\hat{x}_{\mu }\), where \(\hat{x}_{\mu }\) is an optimal solution of the smoothed problem (4). But the proof does not use the optimality property in any way, only feasibility. It therefore applies to any feasible vector x. This minor modification is convenient for later developments.
References
Adcock, B., Hansen, A.C.: Compressive Imaging: Structure, Sampling, Learning. Cambridge University Press, Cambridge (2021)
Arridge, S., Maass, P., Öktem, O., Schönlieb, C.-B.: Solving inverse problems using data-driven models. Acta Numer. 28, 1–174 (2019)
Ravishankar, S., Ye, J.C., Fessler, J.A.: Image reconstruction: from sparsity to data-adaptive methods and machine learning. Proc. IEEE 108(1), 86–109 (2020)
FDA: 510k Premarket Notification of HyperSense (GE Medical Systems). https://www.accessdata.fda.gov/scripts/cdrh/cfdocs/cfpmn/pmn.cfm?ID=K162722
FDA: 510k Premarket Notification of MAGNETOM Aera And MAGNETOM Skyra With Syngo MR E11C - AP02 Software (Siemens Medical Solutions USA). https://www.accessdata.fda.gov/scripts/cdrh/cfdocs/cfpmn/pmn.cfm?ID=K163312
Wang, G., Ye, J.C., Mueller, K., Fessler, J.A.: Image reconstruction is a new frontier of machine learning. IEEE Trans. Med. Imag. 37(6), 1289–1296 (2018)
Knoll, F., Hammernik, K., Zhang, C., Moeller, S., Pock, T., Sodickson, D.K., Akçakaya, M.: Deep-learning methods for parallel Magnetic Resonance Imaging reconstruction: a survey of the current approaches, trends, and issues. IEEE Signal Process. Mag. 37(1), 128–140 (2020)
Liang, D., Cheng, J., Ke, Z., Ying, L.: Deep Magnetic Resonance image reconstruction: inverse problems meet neural networks. IEEE Signal Process. Mag. 37(1), 141–151 (2020)
Lundervold, A., Lundervold, A.: An overview of deep learning in medical imaging focusing on MRI. Z. Med. Phys. 29(2), 102–127 (2019)
McCann, M.T., Jin, K.H., Unser, M.: Convolutional neural networks for inverse problems in imaging: a review. IEEE Signal Process. Mag. 34(6), 85–95 (2017)
Ongie, G., Jalal, A., Metzler, C.A., Baraniuk, R.G., Dimakis, A.G., Willett, R.: Deep learning techniques for inverse problems in imaging. IEEE J. Sel. Areas Inf. Theory 1(1), 39–56 (2020)
Shen, C., Nguyen, D., Zhou, Z., Jiang, S.B., Dong, B., Jia, X.: An introduction to deep learning in medical physics: advantages, potential, and challenges. Phys. Med. Biol. 65(5), 05–01 (2020)
Zhang, H., Dong, B.: A review on deep learning in medical image reconstruction. J. Oper. Res. Soc. China 8, 311–340 (2020)
Gottschling, N.M., Antun, V., Adcock, B., Hansen, A.C.: The Troublesome Kernel: Why Deep Learning for Inverse Problems is Typically Unstable. arXiv:2001.01258 (2020)
Antun, V., Renna, F., Poon, C., Adcock, B., Hansen, A.C.: On instabilities of deep learning in image reconstruction and the potential costs of AI. Proc. Natl. Acad. Sci. USA 117(48), 30088–30095 (2020)
Huang, Y., Würfl, T., Breininger, K., Liu, L., Lauritsch, G., Maier, A.: Some investigations on robustness of deep learning in limited angle tomography. In: International Conference on Medical Image Computing and Computer-Assisted Intervention, pp. 145–153 (2018)
Muckley, M.J., Riemenschneider, B., Radmanesh, A., Kim, S., Jeong, G., Ko, J., Jun, Y., Shin, H., Hwang, D., Mostapha, M., et al.: Results of the 2020 fastMRI challenge for machine learning MR image reconstruction. IEEE Trans. Med. Imag. 40(9), 2306–2317 (2021)
Hoffman, D.P., Slavitt, I., Fitzpatrick, C.A.: The promise and peril of deep learning in microscopy. Nat. Methods 18(2), 131–132 (2021)
Belthangady, C., Royer, L.A.: Applications, promises, and pitfalls of deep learning for fluorescence image reconstruction. Nat. Methods 16(12), 1215–1225 (2019)
Herskovits, E.H.: Artificial intelligence in molecular imaging. Ann. Transl. Med. 9(9), 824 (2021)
Sayantan, B., Kelkar, V.A., Brooks, F.J., Anastasio, M.A.: On hallucinations in tomographic image reconstruction. IEEE Trans. Med. Imag. 40(11), 3249–3260 (2021)
Sidky, E.Y., Lorente, I., Brankov, J.G., Pan, X.: Do CNNs solve the CT inverse problem? IEEE Trans. Biomed. Eng. 68(6), 1799–1810 (2021)
Boche, H., Fono, A., Kutyniok, G.: Limitations of deep learning for inverse problems on digital hardware. arXiv:2202.13490 (2022)
Hardy, N.P., Mac Aonghusa, P., Neary, P.M., Cahill, R.A.: Intraprocedural artificial intelligence for colorectal cancer detection and characterisation in endoscopy and laparoscopy. Surgical Innov. 28(6), 768–775 (2021)
Laine, R.F., Arganda-Carreras, I., Henriques, R., Jacquemet, G.: Avoiding a replication crisis in deep-learning-based bioimage analysis. Nat. Methods 18(10), 1136–1144 (2021)
Larson, D.B., Harvey, H., Rubin, D.L., Irani, N., Justin, R.T., Langlotz, C.P.: Regulatory frameworks for development and evaluation of artificial intelligence-based diagnostic imaging algorithms: summary and recommendations. J. Am. Coll. Radiol. 18(3), 413–424 (2021)
Liu, X., Glocker, B., McCradden, M.M., Ghassemi, M., Denniston, A.K., Oakden-Rayner, L.: The medical algorithmic audit. Lancet Digital Health (2022)
Morshuis, J.N., Gatidis, S., Hein, M., Baumgartner, C.F.: Adversarial robustness of MR image reconstruction under realistic perturbations. arXiv:2208.03161 (2022)
Pal, A., Rathi, Y.: A review and experimental evaluation of deep learning methods for MRI reconstruction. Mach. Learn. Biomed. Imaging 1–10 (2022)
Qi, H., Cruz, G., Botnar, R., Prieto, C.: Synergistic multi-contrast cardiac magnetic resonance image reconstruction. Philos. Trans. R. Soc. A 379(2200), 20200197 (2021)
Singh, R., Wu, W., Wang, G., Kalra, M.K.: Artificial intelligence in image reconstruction: the change is here. Phys. Medica 79, 113–125 (2020)
Torres-Velázquez, M., Chen, W.-J., Li, X., McMillan, A.B.: Application and construction of deep learning networks in medical imaging. IEEE Trans. Radi. Plasma Med. Sci. 5(2), 137–159 (2020)
Varoquaux, G., Cheplygina, V.: Machine learning for medical imaging: methodological failures and recommendations for the future. NPJ Digital Med. 5(1), 1–8 (2022)
Yu, T., Hilbert, T., Piredda, G.F., Joseph, A., Bonanno, G., Zenkhri, S., Omoumi, P., Cuadra, M.B., Canales-Rodríguez, E.J., Kober, T., et al.: Validation and generalizability of self-supervised image reconstruction methods for undersampled MRI. arXiv:2201.12535 (2022)
Wu, E., Wu, K., Daneshjou, R., Ouyang, D., Ho, D.E., Zou, J.: How medical AI devices are evaluated: limitations and recommendations from an analysis of FDA approvals. Nat. Med. 27(4), 582–584 (2021)
Noordman, C.R.: Current issues in deep learning for undersampled image reconstruction. Preprint (2021)
Stumpo, V., Kernbach, J.M., van Niftrik, C.H.B., Sebök, M., Fierstra, J., Regli, L., Serra, C., Staartjes, V.E.: Machine learning algorithms in neuroimaging: an overview. In: Staartjes, V.E., Regli, L., Serra, C. (eds.) Machine Learning in Clinical Neuroscience. Acta Neurochirurgica Supplement, vol. 134, pp. 125–138. Springer, Cham (2022)
Tölle, M., Laves, M.-H., Schlaefer, A.: A mean-field variational inference approach to deep image prior for inverse problems in medical imaging. In: Heinrich, M., Dou, Q., de Bruijne, M., Lellmann, J., Schläfer, A., Ernst, F. (eds.) Proceedings of the Fourth Conference on Medical Imaging with Deep Learning. Proceedings of Machine Learning Research, vol. 143, pp. 745–760. PMLR, Lübeck, Germany (2021)
Lahiri, A.: Learning-based algorithms for inverse problems in MR image reconstruction and quantitative perfusion imaging. PhD thesis, The University of Michigan (2021)
Shimron, E., Tamir, J.I., Wang, K., Lustig, M.: Implicit data crimes: machine learning bias arising from misuse of public data. Proc. Natl Acad. Sci. USA 119(13), 2117203119 (2022)
Genzel, M., Macdonald, J., Marz, M.: Solving inverse problems with deep neural networks—robustness included? IEEE Trans. Pattern Anal. Machine Intell. 45(1), 1119–1134.(2022)
Zhang, C., Jia, J., Yaman, B., Moeller, S., Liu, S., Hong, M., Akçakaya, M.: Instabilities in conventional multi-coil MRI reconstruction with small adversarial perturbations. In: 2021 55th Asilomar Conference on Signals, Systems, and Computers, pp. 895–899 (2021)
Darestani, M.Z., Chaudhari, A.S., Heckel, R.: Measuring robustness in deep learning based compressive sensing. In: International Conference on Machine Learning, pp. 2433–2444 (2021)
Alaifari, R., Alberti, G.S., Gauksson, T.: Localized adversarial artifacts for compressed sensing MRI. arXiv:2206.05289 (2022)
Colbrook, M.J., Antun, V., Hansen, A.C.: The difficulty of computing stable and accurate neural networks: On the barriers of deep learning and smale’s 18th problem. Proc. Natl. Acad. Sci. USA 119(12), 2107151119 (2022)
Hasannasab, M., Hertrich, J., Neumayer, S., Plonka, G., Setzer, S., Steidl, G.: Parseval proximal neural networks. J. Fourier Anal. Appl. 26(4) , 1–31(2020)
Combettes, P.L., Pesquet, J.-C.: Lipschitz certificates for layered network structures driven by averaged activation operators. SIAM J. Math. Data Sci. 2(2), 529–557 (2020)
Adcock, B., Hansen, A.C., Roman, B.: A note on compressed sensing of structured sparse wavelet coefficients from subsampled Fourier measurements. IEEE Signal Process. Lett. 23(5), 732–736 (2016)
Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40(1), 120–145 (2011)
Chambolle, A., Pock, T.: On the ergodic convergence rates of a first-order primal-dual algorithm. Math. Program. 159(1–2), 253–287 (2016)
Roulet, V., d’Aspremont, A.: Sharpness, restart, and acceleration. SIAM J. Optim. 30(1), 262–289 (2020)
Renegar, J., Grimmer, B.: A simple nearly optimal restart scheme for speeding up first-order methods. Found. Comput. Math. 22(1), 211–256 (2022)
Colbrook, M.J.: WARPd: a linearly convergent first-order primal-dual algorithm for inverse problems with approximate sharpness conditions. SIAM J. Imaging Sci. 15(3), 1539–1575 (2022)
Fessler, J.A.: Optimization methods for magnetic resonance image reconstruction: key models and optimization algorithms. IEEE Signal Process. Mag. 37(1), 33–40 (2020)
Lustig, M., Donoho, D.L., Santos, J.M., Pauly, J.M.: Compressed sensing MRI. IEEE Signal Process. Mag. 25(2), 72–82 (2008)
Lustig, M., Donoho, D.L., Pauly, J.M.: Sparse MRI: the application of compressed sensing for rapid MRI imaging. Magn. Reson. Med. 58(6), 1182–1195 (2007)
Candès, E.J., Donoho, D.L.: Curvelets–a surprisingly effective nonadaptive representation for objects with edges. In: Rabut, C., Cohen, A., Schumaker, L.L. (eds.) Curves and Surfaces, pp. 105–120. Vanderbilt University Press, Nashville (2000)
Candès, E.J., Donoho, D.L.: Recovering edges in ill-posed inverse problems: optimality of curvelet frames. Ann. Statist. 30(3), 784–842 (2002)
Candès, E.J., Donoho, D.L.: New tight frames of curvelets and optimal representations of objects with piecewise \({C}^2\) singularities. Commun. Pure Appl. Math. 57(2), 219–266 (2004)
Candès, E.J., Donoho, D.L.: Ridgelets: a key to high dimensional intermittency? Philos. Trans. R. Soc. A 357(1760), 2495–2509 (1999)
Labate, D., Lim, W.-Q., Kutyniok, G., Weiss, G.: Sparse multidimensional representation using shearlets. In: Papadakis, M., Laine, A.F., Unser, M.A. (eds.) Wavelets XI, vol. 5914, pp. 254–262. SPIE, Bellingham (2005) . (International Society for Optics and Photonics)
Guo, K., Kutyniok, G., Labate, D.: Sparse multidimensional representations using anisotropic dilation and shear operators. In: Chen, G., Lai, M.-J. (eds.) Wavelets and Splines: Athens 2005, pp. 189–201. Nashboro Press, Brentwood (2006)
Guo, K., Labate, D.: Optimally sparse multidimensional representation using shearlets. SIAM J. Math. Anal. 39(1), 298–318 (2007)
Kutyniok, G., Lim, W.-Q.: Compactly supported shearlets are optimally sparse. J. Approx. Theory 163(11), 1564–1589 (2011)
Becker, S., Bobin, J., Candès, E.J.: NESTA: a fast and accurate first-order method for sparse recovery. SIAM J. Imaging Sci. 4(1), 1–39 (2011)
Becker, S.R.: Practical Compressed Sensing: Modern Data Acquisition and Signal Processing. PhD thesis, Stanford University (2011)
Roulet, V., Boumal, A.N.: d’Aspremont: computational complexity versus statistical performance on sparse recovery problems. Inf. Inference 9(1), 1–32 (2020)
Monga, V., Li, Y., Eldar, Y.C.: Algorithm unrolling: interpretable, efficient deep learning for signal and image processing. IEEE Signal Process. Mag. 38(2), 18–44 (2021)
Gregor, K., LeCun, Y.: Learning fast approximations of sparse coding. In: International Conference on Machine Learning, pp. 399–406 (2010)
Zhang, J., Ghanem, B.: ISTA-Net: interpretable optimization-inspired deep network for image compressive sensing. In: 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1828–1837 (2018)
Yang, Y., Sun, J., Li, H., Xu, Z.: Deep ADMM-Net for compressive sensing MRI. In: Advances in Neural Information Processing Systems, pp. 10–18 (2016)
Yang, Y., Sun, J., Li, H., Xu, Z.: ADMM-CSNet: a deep learning approach for image compressive sensing. IEEE Trans. Pattern Anal. Machine Intell. 42(3), 521–538 (2020)
Arvinte, M., Vishwanath, S., Tewfik, A.H., Tamir, J.I.: Deep J-Sense: Accelerated MRI Reconstruction Via Unrolled Alternating Optimization. arXiv:2103.02087 (2021)
Adler, J., Öktem, O.: Learned primal-dual reconstruction. IEEE Trans. Med. Imag. 37(6), 1322–1332 (2018)
Wang, S., Fidler, S., Urtasun, R.: Proximal deep structured models. In: Advances in Neural Information Processing Systems, pp. 865–873 (2016)
Chun, I.-Y., Fessler, J.A.: Deep BCD-net using identical encoding-decoding CNN structures for iterative image recovery. In: 2018 IEEE 13th Image, Video, and Multidimensional Signal Processing Workshop (IVMSP), pp. 1–5 (2018)
Cui, Z.-X., Cheng, J., Zhu, Q., Liu, Y., Jia, S., Zhao, K., Ke, Z., Huang, W., Wang, H., Zhu, Y., Liang, D.: Equilibrated zeroth-order unrolled deep networks for accelerated MRI. arXiv:2112.09891 (2021)
Metzler, C.A., Mousavi, A., Baraniuk, R.G.: Learned D-AMP: principled neural network based compressive image recovery. In: Advances in Neural Information Processing Systems, pp. 1770–1781 (2017)
Gilton, D., Ongie, G., Willett, R.: Neumann networks for linear inverse problems in imaging. IEEE Trans. Comput. Imag. 6, 328–343 (2020)
Hammernik, K., Klatzer, T., Kobler, E., Recht, M.P., Sodickson, D.K., Pock, T., Knoll, F.: Learning a variational network for reconstruction of accelerated MRI data. Magn. Reson. Med. 79(6), 3055–3071 (2018)
Gilton, D., Ongie, G., Willett, R.: Deep equilibrium architectures for inverse problems in imaging. IEEE Trans. Comput. Imag. 7, 1123–1133 (2021)
Foucart, S.: Stability and robustness of \(\ell _1\)-minimizations with Weibull matrices and redundant dictionaries. Linear Algebra Appl. 441, 4–21 (2014)
Nesterov, Y.: A method for solving the convex programming problem with convergence rate \(\cal{O}(1/k^2)\). Soviet Math. Dokl. 27, 372–376 (1983)
Nesterov, Y.: Smooth minimization of non-smooth functions. Math. Program. Ser. A 103, 127–152 (2005)
Adcock, B., Brugiapaglia, S., Webster, C.G.: Sparse Polynomial Approximation of High-Dimensional Functions. Comput. Sci. Eng. (2022) (Society for Industrial and Applied Mathematics, Philadelphia, PA)
Adcock, B., Dexter, N., Xu, Q.: Improved recovery guarantees and sampling strategies for TV minimization in compressive imaging. SIAM J. Imaging Sci. 14(3), 1149–1183 (2021)
Krahmer, F., Ward, R.: Stable and robust sampling strategies for compressive imaging. IEEE Trans. Image Process. 23(2), 612–622 (2013)
Poon, C.: On the role of total variation in compressed sensing. SIAM J. Imaging Sci. 8(1), 682–720 (2015)
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang, E., DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., Chintala, S.: PyTorch: an imperative style, high-performance deep learning library. In: Advances in Neural Information Processing Systems, pp. 8024–8035 (2019)
Guerquin-Kern, M., Lejeune, L., Pruessmann, K.P., Unser, M.: Realistic analytical phantoms for parallel Magnetic Resonance Imaging. IEEE Trans. Med. Imag. 31(3), 626–636 (2012)
Brugiapaglia, S., Adcock, B.: Robustness to unknown error in sparse regularization. IEEE Trans. Inf. Theory 64(10), 6638–6661 (2018)
Kutyniok, G., Lim, W.-Q.: Optimal compressive imaging of Fourier data. SIAM J. Imaging Sci. 11(1), 507–546 (2018)
Nam, S., Davies, M.E., Elad, M., Gribonval, R.: The cosparse analysis model and algorithms. Appl. Comput. Harmon. Anal. 34(1), 30–56 (2013)
Genzel, M., Kutyniok, G., März, M.: \(\ell ^1\)-analysis minimization and generalized (co-)sparsity: when does recovery succeed? Appl. Comput. Harmon. Anal. 52, 82–140 (2021)
Acknowledgements
BA acknowledges support from NSERC through Grant R611675. MNN acknowledges support from an NSERC CGS-M scholarship. Both authors would like to thank Vegard Antun and Matthew Colbrook for helpful advice and feedback.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
On behalf of all authors, the corresponding author states that there is no conflict of interest.
Additional information
Communicated by Ron Levie.
The original online version of this article was revised: The first equation line on page 6 has been corrected. The correct version reads: “\(\sigma _s(z)_{\ell ^1} = \min \left\{ \Vert z - u_S \Vert _{\ell ^1} \ : \ u \in \mathbb {C}^M, \ S \subseteq [M], \ |S| \le s \right\} \)”
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Neyra-Nesterenko, M., Adcock, B. NESTANets: stable, accurate and efficient neural networks for analysis-sparse inverse problems. Sampl. Theory Signal Process. Data Anal. 21, 4 (2023). https://doi.org/10.1007/s43670-022-00043-5
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s43670-022-00043-5