November  2015, 9(4): 1093-1137. doi: 10.3934/ipi.2015.9.1093

Locally sparse reconstruction using the $l^{1,\infty}$-norm

1. 

Westfälische Wilhelms-Universität Münster, Institute for Computational and Applied Mathematics, Einsteinstrasse 62, D 48149 Münster, Germany

2. 

Technische Universität München, Department of Computer Science, Informatik 9, Boltzmannstrasse 3, D 85748 Garching, Germany

3. 

Westfälische Wilhelms-Universität Münster, Institute for Computational and Applied Mathematics, Einsteinstr. 62, D 48149 Münster, Germany

Received  June 2014 Revised  December 2014 Published  October 2015

This paper discusses the incorporation of local sparsity information, e.g. in each pixel of an image, via minimization of the $\ell^{1,\infty}$-norm. We discuss the basic properties of this norm when used as a regularization functional and associated optimization problems, for which we derive equivalent reformulations either more amenable to theory or to numerical computation. Further focus of the analysis is put on the locally 1-sparse case, which is well motivated by some biomedical imaging applications.
    Our computational approaches are based on alternating direction methods of multipliers (ADMM) and appropriate splittings with augmented Lagrangians. Those are tested for a model scenario related to dynamic positron emission tomography (PET), which is a functional imaging technique in nuclear medicine.
    The results of this paper provide insight into the potential impact of regularization with the $\ell^{1,\infty}$-norm for local sparsity in appropriate settings. However, it also indicates several shortcomings, possibly related to the non-tightness of the functional as a relaxation of the $\ell^{0,\infty}$-norm.
Citation: Pia Heins, Michael Moeller, Martin Burger. Locally sparse reconstruction using the $l^{1,\infty}$-norm. Inverse Problems & Imaging, 2015, 9 (4) : 1093-1137. doi: 10.3934/ipi.2015.9.1093
References:
[1]

Optimization for Machine Learning (eds. S. Sra, S. Nowozin, and S. J. Wright), MIT Press, 2011. Google Scholar

[2]

Foundations and Trends in Machine Learning, 4 (2012), 1-106. doi: 10.1561/2200000015.  Google Scholar

[3]

Statistical Science, 27 (2012), 450-468. doi: 10.1214/12-STS394.  Google Scholar

[4]

IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 5 (2012), 354-379. Google Scholar

[5]

Foundations and Trends in Machine Learning, 3 (2010), 1-122. doi: 10.1561/2200000016.  Google Scholar

[6]

Inverse problems, 20 (2004), 1411-1421. doi: 10.1088/0266-5611/20/5/005.  Google Scholar

[7]

Journal of the ACM, 58 (2011), 37pp. doi: 10.1145/1970392.1970395.  Google Scholar

[8]

IEEE Transactions on Information Theory, 57 (2011), 7235-7254. doi: 10.1109/TIT.2011.2161794.  Google Scholar

[9]

IEEE Transactions on Information Theory, 51 (2005), 4203-4215. doi: 10.1109/TIT.2005.858979.  Google Scholar

[10]

Mathematical Programming, 64 (1994), 81-101. doi: 10.1007/BF01582566.  Google Scholar

[11]

Journal of the American Mathematical Society, 22 (2009), 211-231. doi: 10.1090/S0894-0347-08-00610-3.  Google Scholar

[12]

IEEE Transactions on Signal Processing, 53 (2005), 2477-2488. doi: 10.1109/TSP.2005.849172.  Google Scholar

[13]

IEEE Transactions on Information Theory, 47 (2001), 2845-2862. doi: 10.1109/18.959265.  Google Scholar

[14]

in Proceedings of the 25th International Conference on Machine Learning, 2008. Google Scholar

[15]

in Large Scale Optimization: State of the Art, Kluwer Acad. Publ., Dordrecht, 1994, 115-134.  Google Scholar

[16]

corrected reprint edition, SIAM, 1999. doi: 10.1137/1.9781611971088.  Google Scholar

[17]

Optics and Photonics News, 13 (2002), 26-32. doi: 10.1364/OPN.13.11.000026.  Google Scholar

[18]

Springer, 1996. doi: 10.1007/978-94-009-1740-8.  Google Scholar

[19]

IEEE Transactions on Image Processing, 21 (2012), 3239-3252. doi: 10.1109/TIP.2012.2190081.  Google Scholar

[20]

SIAM Journal on Numerical Analysis, 46 (2008), 577-613. doi: 10.1137/0606668909.  Google Scholar

[21]

North-Holland, Amsterdam, 1983.  Google Scholar

[22]

in Augmented Lagrangian Methods: Applications to the Solution of Boundary-Value Problems, chapter 3, North-Holland, Amsterdam, 1983, 97-146. Google Scholar

[23]

IEEE Transactions on Information Theory, 50 (2004), 1341-1344. doi: 10.1109/TIT.2004.828141.  Google Scholar

[24]

Computational Optimization and Applications, 1 (1992), 93-111. doi: 10.1007/BF00247655.  Google Scholar

[25]

in Augmented Lagrangian Methods: Applications to the Solution of Boundary-Value Problems, chapter 9, North-Holland: Amsterdam, 1983, 299-332. Google Scholar

[26]

Computers and Mathematics with Applications, 2 (1976), 17-40. doi: 10.1016/0898-1221(76)90003-1.  Google Scholar

[27]

Revue Française d'Automatique, Informatique, et Recherche Opérationelle, 9 (1975), 41-76.  Google Scholar

[28]

Technical report, University of Wisconsin-Madison, 1987. doi: 10.1137/1.9781611970838.ch3.  Google Scholar

[29]

Phys. Med. Biol., 55 (2010), R111-R191. doi: 10.1088/0031-9155/55/20/R01.  Google Scholar

[30]

Journal of Cerebral Blood Flow and Metabolism, 22 (2002), 1425-1439. Google Scholar

[31]

Journal of Optimization Theory and Applications, 106 (2000), 337-356. doi: 10.1023/A:1004603514434.  Google Scholar

[32]

PhD thesis, Westfälische Wilhelms-Universität Münster, 2014. Google Scholar

[33]

Springer, 1993.  Google Scholar

[34]

IEEE Transactions on Biomedical Engineering, 44 (1997), 433-446. doi: 10.1109/10.581930.  Google Scholar

[35]

Mathematical Programming, 127 (2011), 57-88. doi: 10.1007/s10107-010-0417-z.  Google Scholar

[36]

IEEE Transactions on Information Theory, 57 (2011), 7221-7234. doi: 10.1109/TIT.2011.2158250.  Google Scholar

[37]

Applied and Computational Harmonic Analysis, 27 (2009), 303-324. doi: 10.1016/j.acha.2009.05.006.  Google Scholar

[38]

Biophysical Journal, 95 (2008), 378-389. doi: 10.1529/biophysj.107.125229.  Google Scholar

[39]

in Proceedings of the 26th Annual International Conference on Machine Learning, ICML '09, New York, NY, USA, 2009, 857-864. Google Scholar

[40]

IEEE Transactions on Signal Processing, 47 (1999), 187-200. doi: 10.1109/78.738251.  Google Scholar

[41]

IEEE Nuclear Science Symposium Conference Record, 5 (2007), 3260-3267. doi: 10.1109/NSSMIC.2007.4436834.  Google Scholar

[42]

SIAM Journal on Control and Optimization, 14 (1976), 877-898. doi: 10.1137/0314056.  Google Scholar

[43]

Medical and Biological Engineering and Computing, 25 (1987), 250-260. doi: 10.1007/BF02447421.  Google Scholar

[44]

PhD thesis, 2011. Google Scholar

[45]

in IEEE Conference on Computer Vision & Pattern Recognition (CVPR), 2008, 1-8. doi: 10.1109/CVPR.2008.4587367.  Google Scholar

[46]

Walter de Gruyter, 2012. doi: 10.1515/9783110255720.  Google Scholar

[47]

Inverse Problems, 23 (2007), 1851-1870. doi: 10.1088/0266-5611/23/5/005.  Google Scholar

[48]

Journal of the Royal Statistical Society: Series B (Methodological), 58 (1996), 267-288.  Google Scholar

[49]

Journal of the Royal Statistical Society: Series B (Statistical Methodology), 73 (2011), 273-282. doi: 10.1111/j.1467-9868.2011.00771.x.  Google Scholar

[50]

Winston, 1977.  Google Scholar

[51]

IEEE Transactions on Information Theory, 50 (2004), 2231-2242. doi: 10.1109/TIT.2004.834793.  Google Scholar

[52]

Signal Processing - Sparse approximations in signal and image processing, 86 (2006), 589-602. doi: 10.1016/j.sigpro.2005.05.031.  Google Scholar

[53]

IEEE Transactions on Information Theory, 52 (2006), 1030-1051. doi: 10.1109/TIT.2005.864420.  Google Scholar

[54]

SIAM Journal on Control and Optimization, 29 (1991), 119-138. doi: 10.1137/0329006.  Google Scholar

[55]

in Pattern Recognition - 32nd DAGM Symposium, Volume 6376, Springer Berlin Heidelberg, 2010, 252-261. doi: 10.1007/978-3-642-15986-2_26.  Google Scholar

[56]

Journal of Optimization Theory and Applications, 109 (2001), 415-429. doi: 10.1023/A:1017522623963.  Google Scholar

[57]

Linear Algebra and its Applications, 170 (1992), 33-45. doi: 10.1016/0024-3795(92)90407-2.  Google Scholar

[58]

Elsevier Academic Press, San Diego, CA, 2004. Google Scholar

[59]

Journal of the Royal Statistical Society: Series B (Statistical Methodology), 68 (2006), 49-67. doi: 10.1111/j.1467-9868.2005.00532.x.  Google Scholar

[60]

Technical report, Rutgers University, NJ, Januar 2012. Google Scholar

show all references

References:
[1]

Optimization for Machine Learning (eds. S. Sra, S. Nowozin, and S. J. Wright), MIT Press, 2011. Google Scholar

[2]

Foundations and Trends in Machine Learning, 4 (2012), 1-106. doi: 10.1561/2200000015.  Google Scholar

[3]

Statistical Science, 27 (2012), 450-468. doi: 10.1214/12-STS394.  Google Scholar

[4]

IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 5 (2012), 354-379. Google Scholar

[5]

Foundations and Trends in Machine Learning, 3 (2010), 1-122. doi: 10.1561/2200000016.  Google Scholar

[6]

Inverse problems, 20 (2004), 1411-1421. doi: 10.1088/0266-5611/20/5/005.  Google Scholar

[7]

Journal of the ACM, 58 (2011), 37pp. doi: 10.1145/1970392.1970395.  Google Scholar

[8]

IEEE Transactions on Information Theory, 57 (2011), 7235-7254. doi: 10.1109/TIT.2011.2161794.  Google Scholar

[9]

IEEE Transactions on Information Theory, 51 (2005), 4203-4215. doi: 10.1109/TIT.2005.858979.  Google Scholar

[10]

Mathematical Programming, 64 (1994), 81-101. doi: 10.1007/BF01582566.  Google Scholar

[11]

Journal of the American Mathematical Society, 22 (2009), 211-231. doi: 10.1090/S0894-0347-08-00610-3.  Google Scholar

[12]

IEEE Transactions on Signal Processing, 53 (2005), 2477-2488. doi: 10.1109/TSP.2005.849172.  Google Scholar

[13]

IEEE Transactions on Information Theory, 47 (2001), 2845-2862. doi: 10.1109/18.959265.  Google Scholar

[14]

in Proceedings of the 25th International Conference on Machine Learning, 2008. Google Scholar

[15]

in Large Scale Optimization: State of the Art, Kluwer Acad. Publ., Dordrecht, 1994, 115-134.  Google Scholar

[16]

corrected reprint edition, SIAM, 1999. doi: 10.1137/1.9781611971088.  Google Scholar

[17]

Optics and Photonics News, 13 (2002), 26-32. doi: 10.1364/OPN.13.11.000026.  Google Scholar

[18]

Springer, 1996. doi: 10.1007/978-94-009-1740-8.  Google Scholar

[19]

IEEE Transactions on Image Processing, 21 (2012), 3239-3252. doi: 10.1109/TIP.2012.2190081.  Google Scholar

[20]

SIAM Journal on Numerical Analysis, 46 (2008), 577-613. doi: 10.1137/0606668909.  Google Scholar

[21]

North-Holland, Amsterdam, 1983.  Google Scholar

[22]

in Augmented Lagrangian Methods: Applications to the Solution of Boundary-Value Problems, chapter 3, North-Holland, Amsterdam, 1983, 97-146. Google Scholar

[23]

IEEE Transactions on Information Theory, 50 (2004), 1341-1344. doi: 10.1109/TIT.2004.828141.  Google Scholar

[24]

Computational Optimization and Applications, 1 (1992), 93-111. doi: 10.1007/BF00247655.  Google Scholar

[25]

in Augmented Lagrangian Methods: Applications to the Solution of Boundary-Value Problems, chapter 9, North-Holland: Amsterdam, 1983, 299-332. Google Scholar

[26]

Computers and Mathematics with Applications, 2 (1976), 17-40. doi: 10.1016/0898-1221(76)90003-1.  Google Scholar

[27]

Revue Française d'Automatique, Informatique, et Recherche Opérationelle, 9 (1975), 41-76.  Google Scholar

[28]

Technical report, University of Wisconsin-Madison, 1987. doi: 10.1137/1.9781611970838.ch3.  Google Scholar

[29]

Phys. Med. Biol., 55 (2010), R111-R191. doi: 10.1088/0031-9155/55/20/R01.  Google Scholar

[30]

Journal of Cerebral Blood Flow and Metabolism, 22 (2002), 1425-1439. Google Scholar

[31]

Journal of Optimization Theory and Applications, 106 (2000), 337-356. doi: 10.1023/A:1004603514434.  Google Scholar

[32]

PhD thesis, Westfälische Wilhelms-Universität Münster, 2014. Google Scholar

[33]

Springer, 1993.  Google Scholar

[34]

IEEE Transactions on Biomedical Engineering, 44 (1997), 433-446. doi: 10.1109/10.581930.  Google Scholar

[35]

Mathematical Programming, 127 (2011), 57-88. doi: 10.1007/s10107-010-0417-z.  Google Scholar

[36]

IEEE Transactions on Information Theory, 57 (2011), 7221-7234. doi: 10.1109/TIT.2011.2158250.  Google Scholar

[37]

Applied and Computational Harmonic Analysis, 27 (2009), 303-324. doi: 10.1016/j.acha.2009.05.006.  Google Scholar

[38]

Biophysical Journal, 95 (2008), 378-389. doi: 10.1529/biophysj.107.125229.  Google Scholar

[39]

in Proceedings of the 26th Annual International Conference on Machine Learning, ICML '09, New York, NY, USA, 2009, 857-864. Google Scholar

[40]

IEEE Transactions on Signal Processing, 47 (1999), 187-200. doi: 10.1109/78.738251.  Google Scholar

[41]

IEEE Nuclear Science Symposium Conference Record, 5 (2007), 3260-3267. doi: 10.1109/NSSMIC.2007.4436834.  Google Scholar

[42]

SIAM Journal on Control and Optimization, 14 (1976), 877-898. doi: 10.1137/0314056.  Google Scholar

[43]

Medical and Biological Engineering and Computing, 25 (1987), 250-260. doi: 10.1007/BF02447421.  Google Scholar

[44]

PhD thesis, 2011. Google Scholar

[45]

in IEEE Conference on Computer Vision & Pattern Recognition (CVPR), 2008, 1-8. doi: 10.1109/CVPR.2008.4587367.  Google Scholar

[46]

Walter de Gruyter, 2012. doi: 10.1515/9783110255720.  Google Scholar

[47]

Inverse Problems, 23 (2007), 1851-1870. doi: 10.1088/0266-5611/23/5/005.  Google Scholar

[48]

Journal of the Royal Statistical Society: Series B (Methodological), 58 (1996), 267-288.  Google Scholar

[49]

Journal of the Royal Statistical Society: Series B (Statistical Methodology), 73 (2011), 273-282. doi: 10.1111/j.1467-9868.2011.00771.x.  Google Scholar

[50]

Winston, 1977.  Google Scholar

[51]

IEEE Transactions on Information Theory, 50 (2004), 2231-2242. doi: 10.1109/TIT.2004.834793.  Google Scholar

[52]

Signal Processing - Sparse approximations in signal and image processing, 86 (2006), 589-602. doi: 10.1016/j.sigpro.2005.05.031.  Google Scholar

[53]

IEEE Transactions on Information Theory, 52 (2006), 1030-1051. doi: 10.1109/TIT.2005.864420.  Google Scholar

[54]

SIAM Journal on Control and Optimization, 29 (1991), 119-138. doi: 10.1137/0329006.  Google Scholar

[55]

in Pattern Recognition - 32nd DAGM Symposium, Volume 6376, Springer Berlin Heidelberg, 2010, 252-261. doi: 10.1007/978-3-642-15986-2_26.  Google Scholar

[56]

Journal of Optimization Theory and Applications, 109 (2001), 415-429. doi: 10.1023/A:1017522623963.  Google Scholar

[57]

Linear Algebra and its Applications, 170 (1992), 33-45. doi: 10.1016/0024-3795(92)90407-2.  Google Scholar

[58]

Elsevier Academic Press, San Diego, CA, 2004. Google Scholar

[59]

Journal of the Royal Statistical Society: Series B (Statistical Methodology), 68 (2006), 49-67. doi: 10.1111/j.1467-9868.2005.00532.x.  Google Scholar

[60]

Technical report, Rutgers University, NJ, Januar 2012. Google Scholar

[1]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017

[2]

Kha Van Huynh, Barbara Kaltenbacher. Some application examples of minimization based formulations of inverse problems and their regularization. Inverse Problems & Imaging, 2021, 15 (3) : 415-443. doi: 10.3934/ipi.2020074

[3]

Jianli Xiang, Guozheng Yan. The uniqueness of the inverse elastic wave scattering problem based on the mixed reciprocity relation. Inverse Problems & Imaging, 2021, 15 (3) : 539-554. doi: 10.3934/ipi.2021004

[4]

Ahmad Mousavi, Zheming Gao, Lanshan Han, Alvin Lim. Quadratic surface support vector machine with L1 norm regularization. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021046

[5]

Xue-Ping Luo, Yi-Bin Xiao, Wei Li. Strict feasibility of variational inclusion problems in reflexive Banach spaces. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2495-2502. doi: 10.3934/jimo.2019065

[6]

Wenbin Li, Jianliang Qian. Simultaneously recovering both domain and varying density in inverse gravimetry by efficient level-set methods. Inverse Problems & Imaging, 2021, 15 (3) : 387-413. doi: 10.3934/ipi.2020073

[7]

Kazuhiro Kurata, Yuki Osada. Variational problems associated with a system of nonlinear Schrödinger equations with three wave interaction. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021100

[8]

Jinye Shen, Xian-Ming Gu. Two finite difference methods based on an H2N2 interpolation for two-dimensional time fractional mixed diffusion and diffusion-wave equations. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021086

[9]

Jiangang Qi, Bing Xie. Extremum estimates of the $ L^1 $-norm of weights for eigenvalue problems of vibrating string equations based on critical equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (7) : 3505-3516. doi: 10.3934/dcdsb.2020243

[10]

Zhihua Zhang, Naoki Saito. PHLST with adaptive tiling and its application to antarctic remote sensing image approximation. Inverse Problems & Imaging, 2014, 8 (1) : 321-337. doi: 10.3934/ipi.2014.8.321

[11]

Jamal Mrazgua, El Houssaine Tissir, Mohamed Ouahi. Frequency domain $ H_{\infty} $ control design for active suspension systems. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021036

[12]

Sergi Simon. Linearised higher variational equations. Discrete & Continuous Dynamical Systems, 2014, 34 (11) : 4827-4854. doi: 10.3934/dcds.2014.34.4827

[13]

Andrea Cianchi, Adele Ferone. Improving sharp Sobolev type inequalities by optimal remainder gradient norms. Communications on Pure & Applied Analysis, 2012, 11 (3) : 1363-1386. doi: 10.3934/cpaa.2012.11.1363

[14]

Raphaël Côte, Frédéric Valet. Polynomial growth of high sobolev norms of solutions to the Zakharov-Kuznetsov equation. Communications on Pure & Applied Analysis, 2021, 20 (3) : 1039-1058. doi: 10.3934/cpaa.2021005

[15]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021

[16]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271

[17]

Hsin-Lun Li. Mixed Hegselmann-Krause dynamics. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021084

[18]

Andreas Neubauer. On Tikhonov-type regularization with approximated penalty terms. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021027

[19]

Jon Aaronson, Dalia Terhesiu. Local limit theorems for suspended semiflows. Discrete & Continuous Dynamical Systems, 2020, 40 (12) : 6575-6609. doi: 10.3934/dcds.2020294

[20]

Zhenbing Gong, Yanping Chen, Wenyu Tao. Jump and variational inequalities for averaging operators with variable kernels. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021045

2019 Impact Factor: 1.373

Metrics

  • PDF downloads (78)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]