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

Pia  Heins; Michael  Moeller; Martin  Burger

doi:10.3934/ipi.2015.9.1093

Article Contents

2015, Volume 9, Issue 4: 1093-1137. Doi: 10.3934/ipi.2015.9.1093

This issue Previous Article A parallel space-time domain decomposition method for unsteady source inversion problems Next Article Bilevel optimization for calibrating point spread functions in blind deconvolution

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
2.
Technische Universität München, Department of Computer Science, Informatik 9, Boltzmannstrasse 3, D 85748 Garching
3.
Westfälische Wilhelms-Universität Münster, Institute for Computational and Applied Mathematics, Einsteinstr. 62, D 48149 Münster

Received: May 31, 2014

Revised: November 30, 2014

Published: October 2015

Abstract Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 65F50, 49N45; Secondary: 68U10.

Citation:

Related Papers

Cited by

References

[1]	F. Bach, R. Jenatton, J. Mairal and G. Obozinski, Convex Optimization with Sparsity-Inducing Norms, Optimization for Machine Learning (eds. S. Sra, S. Nowozin, and S. J. Wright), MIT Press, 2011.
[2]	F. Bach, R. Jenatton, J. Mairal and G. Obozinski, Optimization with sparsity-inducing penalties, Foundations and Trends in Machine Learning, 4 (2012), 1-106.doi: 10.1561/2200000015.
[3]	F. Bach, R. Jenatton, J. Mairal and G. Obozinski, Structured sparsity through convex optimization, Statistical Science, 27 (2012), 450-468.doi: 10.1214/12-STS394.
[4]	J. M. Bioucas-Dias, A. Plaza, N. Dobigeon, M. Parente, Q. Du, P. Gader and J. Chanussot, Hyperspectral unmixing overview: Geometrical, statistical, and sparse regression-based approaches, IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 5 (2012), 354-379.
[5]	S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends in Machine Learning, 3 (2010), 1-122.doi: 10.1561/2200000016.
[6]	M. Burger and S. Osher, Convergence rates of convex variational regularization, Inverse problems, 20 (2004), 1411-1421.doi: 10.1088/0266-5611/20/5/005.
[7]	E. J. Candès, X. Li, Y. Ma and J. Wrigh, Robust principal component analysis?, Journal of the ACM, 58 (2011), 37pp.doi: 10.1145/1970392.1970395.
[8]	E. J. Candès and Y. Plan, A probabilistic and ripless theory of compressed sensing, IEEE Transactions on Information Theory, 57 (2011), 7235-7254.doi: 10.1109/TIT.2011.2161794.
[9]	E. J. Candès and T. Tao, Decoding by linear programming, IEEE Transactions on Information Theory, 51 (2005), 4203-4215.doi: 10.1109/TIT.2005.858979.
[10]	G. Chen and M. Teboulle, A proximal-based decomposition method for convex minimization problems, Mathematical Programming, 64 (1994), 81-101.doi: 10.1007/BF01582566.
[11]	A. Cohen, W. Dahmen and R. Devore, Compressed sensing and best k-term approximation, Journal of the American Mathematical Society, 22 (2009), 211-231.doi: 10.1090/S0894-0347-08-00610-3.
[12]	S. Cotter, B. Rao, K. Engan, and K. Kreutz-Delgado, Sparse solutions to linear inverse problems with multiple measurement vectors, IEEE Transactions on Signal Processing, 53 (2005), 2477-2488.doi: 10.1109/TSP.2005.849172.
[13]	D. L. Donoho and X. Huo, Uncertainty principles and ideal atomic decomposition, IEEE Transactions on Information Theory, 47 (2001), 2845-2862.doi: 10.1109/18.959265.
[14]	J. Duchi, S. Shalev-Shwartz, Y. Singer, and T. Chandra, Efficient projections onto the l1-ball for learning in high dimensions, in Proceedings of the 25th International Conference on Machine Learning, 2008.
[15]	J. Eckstein and M. Fukushima, Some reformulations and applications of the alternating direction method of multipliers, in Large Scale Optimization: State of the Art, Kluwer Acad. Publ., Dordrecht, 1994, 115-134.
[16]	I. Ekeland and R. Témam, Convex Analysis and Variational Problems, corrected reprint edition, SIAM, 1999.doi: 10.1137/1.9781611971088.
[17]	D. Elson, S. Webb, J. Siegel, K. Suhling, D. Davis, J. Lever, D. Phillips, A. Wallace and P. French, Biomedical applications of fluorescence lifetime imaging, Optics and Photonics News, 13 (2002), 26-32.doi: 10.1364/OPN.13.11.000026.
[18]	H. W. Engl, M. Hanke and A. Neubauer, Regularization of Inverse Problems, Volume 375, Springer, 1996.doi: 10.1007/978-94-009-1740-8.
[19]	E. Esser, M. Möller, S. Osher, G. Sapiro and J. Xin, A convex model for nonnegative matrix factorization and dimensionality reduction on physical space, IEEE Transactions on Image Processing, 21 (2012), 3239-3252.doi: 10.1109/TIP.2012.2190081.
[20]	M. Fornasier and H. Rauhut, Recovery algorithms for vector valued data withjoint sparsity constraints, SIAM Journal on Numerical Analysis, 46 (2008), 577-613.doi: 10.1137/0606668909.
[21]	M. Fortin and R. Glowinski, Augmented Lagrangian Methods: Applications to the Solution of Boundary-Value Problems, North-Holland, Amsterdam, 1983.
[22]	M. Fortin and R. Glowinski, On decomposition-coordination methods using an augmented Lagrangian, in Augmented Lagrangian Methods: Applications to the Solution of Boundary-Value Problems, chapter 3, North-Holland, Amsterdam, 1983, 97-146.
[23]	J.-J. Fuchs, On sparse representations in arbitrary redundant bases, IEEE Transactions on Information Theory, 50 (2004), 1341-1344.doi: 10.1109/TIT.2004.828141.
[24]	M. Fukushima, Application of the alternating direction method of multipliers to separable convex programming problems, Computational Optimization and Applications, 1 (1992), 93-111.doi: 10.1007/BF00247655.
[25]	D. Gabay, Applications of the method of multipliers to variational inequalities, in Augmented Lagrangian Methods: Applications to the Solution of Boundary-Value Problems, chapter 9, North-Holland: Amsterdam, 1983, 299-332.
[26]	D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximations, Computers and Mathematics with Applications, 2 (1976), 17-40.doi: 10.1016/0898-1221(76)90003-1.
[27]	R. Glowinski and A. Marrocco, Sur l'approximation, par elements finis d'ordre un, et la resolution, par penalisation-dualité, d'une classe de problems de dirichlet non lineares, Revue Française d'Automatique, Informatique, et Recherche Opérationelle, 9 (1975), 41-76.
[28]	R. Glowinski and P. L. Tallec, Augmented Lagrangian Methods for the Solution of Variational Problems, Technical report, University of Wisconsin-Madison, 1987.doi: 10.1137/1.9781611970838.ch3.
[29]	G. T. Gullberg, B. W. Reutter, A. Sitek, J. S. Maltz and T. F. Budinger, Dynamic single photon emission computed tomography - basic principles and cardiac applications, Phys. Med. Biol., 55 (2010), R111-R191.doi: 10.1088/0031-9155/55/20/R01.
[30]	R. N. Gunn, S. R. Gunn, F. E. Turkheimer, J. A. D. Aston and V. J. Cunningham, Positron emission tomography compartmental models: A basis pursuit strategy for kinetic modeling, Journal of Cerebral Blood Flow and Metabolism, 22 (2002), 1425-1439.
[31]	B. S. He, H. Yang and S. L. Wang, Alternating direction method with self-adaptive penalty parameters for monotone variational inequalities, Journal of Optimization Theory and Applications, 106 (2000), 337-356.doi: 10.1023/A:1004603514434.
[32]	P. Heins, Reconstruction Using Local Sparsity - A Novel Regularization Technique and an Asymptotic Analysis of Spatial Sparsity Priors, PhD thesis, Westfälische Wilhelms-Universität Münster, 2014.
[33]	J. B. Hiriart-Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithms I, Grundlehren der mathematischen Wissenschaften (Fundamental Principles of Mathematical Sciences), A Series of Comprehensive Studies in Mathematics, Springer, 1993.
[34]	G. Huiskamp and F. Greensite, A new method for myocardial activation imaging, IEEE Transactions on Biomedical Engineering, 44 (1997), 433-446.doi: 10.1109/10.581930.
[35]	A. Juditsky and A. Nemirovski, On verifiable sufficient conditions for sparse signal recovery via l1-minimization, Mathematical Programming, 127 (2011), 57-88.doi: 10.1007/s10107-010-0417-z.
[36]	S. M. Kakade, D. Hsu and T. Zhang, Robust matrix decomposition with sparse corruptions, IEEE Transactions on Information Theory, 57 (2011), 7221-7234.doi: 10.1109/TIT.2011.2158250.
[37]	M. Kowalski, Sparse regression using mixed norms, Applied and Computational Harmonic Analysis, 27 (2009), 303-324.doi: 10.1016/j.acha.2009.05.006.
[38]	G.-J. Kremers, E. B. van Munster, J. Goedhart and T. W. J. Gadella Jr., Quantitative lifetime unmixing of multiexponentially decaying fluorophores using single-frequency fluorescence lifetime imaging microscopy, Biophysical Journal, 95 (2008), 378-389.doi: 10.1529/biophysj.107.125229.
[39]	A. Quattoni, X. Carreras, M. Collins and T. Darrell, An efficient projection for $l_{1,\infty}$ regularization, in Proceedings of the 26th Annual International Conference on Machine Learning, ICML '09, New York, NY, USA, 2009, 857-864.
[40]	B. Rao and K. Kreutz-Delgado, An affine scaling methodology for best basis selection, IEEE Transactions on Signal Processing, 47 (1999), 187-200.doi: 10.1109/78.738251.
[41]	A. J. Reader, Fully 4d image reconstruction by estimation of an input function and spectral coefficients, IEEE Nuclear Science Symposium Conference Record, 5 (2007), 3260-3267.doi: 10.1109/NSSMIC.2007.4436834.
[42]	R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM Journal on Control and Optimization, 14 (1976), 877-898.doi: 10.1137/0314056.
[43]	H. Roozen and A. Van Oosterom, Computing the activation sequence at the ventricular heart surface from body surface potentials, Medical and Biological Engineering and Computing, 25 (1987), 250-260.doi: 10.1007/BF02447421.
[44]	A. Sawatzky, (Nonlocal) Total Variation in Medical Imaging, PhD thesis, 2011.
[45]	M. Schmidt, K. Murphy, G. Fung, and R. Rosales, Structure learning in random fields for heart motion abnormality detection, in IEEE Conference on Computer Vision & Pattern Recognition (CVPR), 2008, 1-8.doi: 10.1109/CVPR.2008.4587367.
[46]	T. Schuster, B. Kaltenbacher, B. Hofmann and K. S. Kazimierski, Regularization Methods in Banach spaces, Volume 10, Walter de Gruyter, 2012.doi: 10.1515/9783110255720.
[47]	G. Teschke and R. Ramlau, An iterative algorithm for nonlinear inverse problems with joint sparsity constraints in vector-valued regimes and an application to color image inpainting, Inverse Problems, 23 (2007), 1851-1870.doi: 10.1088/0266-5611/23/5/005.
[48]	R. Tibshirani, Regression shrinkage and selection via the lasso, Journal of the Royal Statistical Society: Series B (Methodological), 58 (1996), 267-288.
[49]	R. Tibshirani, Regression shrinkage and selection via the lasso: A retrospective, Journal of the Royal Statistical Society: Series B (Statistical Methodology), 73 (2011), 273-282.doi: 10.1111/j.1467-9868.2011.00771.x.
[50]	A. N. Tikhonov and V. Y. Arsenin, Solutions of Ill-Posed Problems, Winston, 1977.
[51]	J. A. Tropp, Greed is good: Algorithmic results for sparse approximation, IEEE Transactions on Information Theory, 50 (2004), 2231-2242.doi: 10.1109/TIT.2004.834793.
[52]	J. A. Tropp, Algorithms for simultaneous sparse approximation part II: Convex relaxation, Signal Processing - Sparse approximations in signal and image processing, 86 (2006), 589-602.doi: 10.1016/j.sigpro.2005.05.031.
[53]	J. A. Tropp, Just relax: Convex programming methods for identifying sparse signals in noise, IEEE Transactions on Information Theory, 52 (2006), 1030-1051.doi: 10.1109/TIT.2005.864420.
[54]	P. Tseng, Applications of a splitting algorithm to decomposition in convex programming and variational inequalities, SIAM Journal on Control and Optimization, 29 (1991), 119-138.doi: 10.1137/0329006.
[55]	J. E. Vogt and V. Roth, The group-lasso: $l_{1,\infty}$ regularization versus $l_{1,2}$ regularization, in Pattern Recognition - 32nd DAGM Symposium, Volume 6376, Springer Berlin Heidelberg, 2010, 252-261.doi: 10.1007/978-3-642-15986-2_26.
[56]	S. L. Wang and L. Z. Liao, Decomposition method with a variable parameter for a class of monotone variational inequality problems, Journal of Optimization Theory and Applications, 109 (2001), 415-429.doi: 10.1023/A:1017522623963.
[57]	G. A. Watson, Characterization of the subdifferential of some matrix norms, Linear Algebra and its Applications, 170 (1992), 33-45.doi: 10.1016/0024-3795(92)90407-2.
[58]	M. N. Wernick and J. N. Aarsvold, editors, Emission Tomography: The Fundamentals of PET and SPECT, Elsevier Academic Press, San Diego, CA, 2004.
[59]	M. Yuan and Y. Lin, Model selection and estimation in regression with grouped variables, Journal of the Royal Statistical Society: Series B (Statistical Methodology), 68 (2006), 49-67.doi: 10.1111/j.1467-9868.2005.00532.x.
[60]	C.-H. Zhang and T. Zhang, A General Framework of Dual Certificate Analysis for Structured Sparse Recovery Problems, Technical report, Rutgers University, NJ, Januar 2012.