Statistical multiresolution Dantzig estimation in imaging: fundamental concepts and algorithmic framework. (English) Zbl 1314.62094
Summary: In this paper we are concerned with fully automatic and locally adaptive estimation of functions in a “signal + noise”-model where the regression function may additionally be blurred by a linear operator, e.g. by a convolution. To this end, we introduce a general class of statistical multiresolution estimators and develop an algorithmic framework for computing those. By this we mean estimators that are defined as solutions of convex optimization problems with \(\ell_{\infty}\)-type constraints. We employ a combination of the alternating direction method of multipliers with Dykstra’s algorithm for computing orthogonal projections onto intersections of convex sets and prove numerical convergence. The capability of the proposed method is illustrated by various examples from imaging and signal detection.
MSC:
| 62G05 | Nonparametric estimation |
| 68U10 | Computing methodologies for image processing |
| 90C06 | Large-scale problems in mathematical programming |
Keywords:
alternating direction method of multipliers (ADMM); biophotonics; Dantzig selector; Dykstra’s projection algorithm; local adaption; signal detection; statistical imaging; statistical multiscale analysis; statistical regularizationReferences:
| [1] | Aujol, J.-F., Aubert, G., Blanc-Féraud, L. and Chambolle, A. (2005). Image decomposition into a bounded variation component and an oscillating component., J. Math. Imaging Vision 22 71-88. · Zbl 1371.94031 · doi:10.1007/s10851-005-4783-8 |
| [2] | Becker, S., Candès, E. and Grant, M. (2011). Templates for convex cone problems with applications to sparse signal recovery., Math. Program. Comput. 3 165-218. · Zbl 1257.90042 · doi:10.1007/s12532-011-0029-5 |
| [3] | Bertalmio, M., Caselles, V., Rougé, B. and Solé, A. (2003). TV based image restoration with local constraints., J. Sci. Comput. 19 95-122. Special issue in honor of the sixtieth birthday of Stanley Osher. · Zbl 1034.49036 · doi:10.1023/A:1025391506181 |
| [4] | Bickel, P. J., Ritov, Y. and Tsybakov, A. B. (2009). Simultaneous analysis of lasso and Dantzig selector., Ann. Statist. 37 1705-1732. · Zbl 1173.62022 · doi:10.1214/08-AOS620 |
| [5] | Boyle, J. P. and Dykstra, R. L. (1986). A method for finding projections onto the intersection of convex sets in Hilbert spaces. In, Advances in order restricted statistical inference (Iowa City, Iowa, 1985) . Lecture Notes in Statist. 37 28-47. Springer, Berlin. · Zbl 0603.49024 · doi:10.1007/978-1-4613-9940-7_3 |
| [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] | Candès, E. and Tao, T. (2007). The Dantzig selector: statistical estimation when, p is much larger than n . Ann. Statist. 35 2313-2351. · Zbl 1139.62019 · doi:10.1214/009053606000001523 |
| [8] | Chen, S. S., Donoho, D. L. and Saunders, M. A. (2001). Atomic Decomposition by Basis Pursuit., SIAM Review 43 129-159. · Zbl 0979.94010 · doi:10.1137/S003614450037906X |
| [9] | Csiszár, I. (1991). Why least squares and maximum entropy? An axiomatic approach to inference for linear inverse problems., Ann. Statist. 19 2032-2066. · Zbl 0753.62003 · doi:10.1214/aos/1176348385 |
| [10] | Davies, P. L. and Kovac, A. (2001). Local extremes, runs, strings and multiresolution., Ann. Statist. 29 1-65. With discussion and rejoinder by the authors. · Zbl 1029.62038 · doi:10.1214/aos/996986501 |
| [11] | Davies, P. L. and Kovac, A. (2004). Densities, spectral densities and modality., Ann. Statist. 32 1093-1136. · Zbl 1093.62042 · doi:10.1214/009053604000000364 |
| [12] | Davies, P. L., Kovac, A. and Meise, M. (2009). Nonparametric regression, confidence regions and regularization., Ann. Statist. 37 2597-2625. · Zbl 1173.62023 · doi:10.1214/07-AOS575 |
| [13] | Deutsch, F. and Hundal, H. (1994). The rate of convergence of Dykstra’s cyclic projections algorithm: the polyhedral case., Numer. Funct. Anal. Optim. 15 537-565. · Zbl 0807.41019 · doi:10.1080/01630569408816580 |
| [14] | Dobson, D. C. and Vogel, C. R. (1997). Convergence of an iterative method for total variation denoising., SIAM J. Numer. Anal. 34 1779-1791. · Zbl 0898.65034 · doi:10.1137/S003614299528701X |
| [15] | Dong, Y., Hintermüller, M. and Rincon-Camacho, M. (May 2011). Automated Regularization Parameter Selection in Multi-Scale Total Variation Models for Image Restoration., J. Math. Imaging Vision 40 82-104(23). · Zbl 1255.68230 · doi:10.1007/s10851-010-0248-9 |
| [16] | Dümbgen, L. and Johns, R. B. (2004). Confidence Bands for Isotonic Median Curves Using Sign Tests., J. Comput. Graph. Statist 13 519-533. · doi:10.1198/1061860043506 |
| [17] | Dümbgen, L. and Spokoiny, V. G. (2001). Multiscale testing of qualitative hypotheses., Ann. Statist. 29 124-152. · Zbl 1029.62070 · doi:10.1214/aos/996986504 |
| [18] | Dümbgen, L. and Walther, G. (2008). Multiscale inference about a density., Ann. Statist. 36 1758-1785. · Zbl 1142.62336 · doi:10.1214/07-AOS521 |
| [19] | Ekeland, I. and Temam, R. (1976)., Convex analysis and variational problems . Studies in Mathematics and its Applications 1 . North-Holland Publishing Co., Amsterdam-Oxford. · Zbl 0322.90046 |
| [20] | Fortin, M. and Glowinski, R. (1983)., Augmented Lagrangian methods . Studies in Mathematics and its Applications 15 . North-Holland Publishing Co., Amsterdam. Applications to the numerical solution of boundary value problems, Translated from the French by B. Hunt and D. C. Spicer. · Zbl 0525.65045 |
| [21] | Frick, K., Marnitz, P. and Munk, A. (2010). Shape Constrained Regularisation by Statistical Multiresolution for Inverse Problems: Asymptotic Analysis Technical Report. Available at, . · Zbl 1250.47009 |
| [22] | Frick, K. and Scherzer, O. (2010). Regularization of ill-posed linear equations by the non-stationary Augmented Lagrangian Method., J. Integral Equations Appl. 22 217-257. · Zbl 1203.90156 · doi:10.1216/JIE-2010-22-2-217 |
| [23] | Gaffke, N. and Mathar, R. (1989). A Cyclic Projection Algorithm Via Duality., Metrika 36 29-54. · Zbl 0676.90054 · doi:10.1007/BF02614077 |
| [24] | Grasmair, M. (2007). The equivalence of the taut string algorithm and BV-regularization., J. Math. Imaging Vision 27 59-66. · Zbl 1478.94041 · doi:10.1007/s10851-006-9796-4 |
| [25] | Hawkins, D. M. and Wixley, R. A. J. (1986). A Note on the Transformation of Chi-Squared Variables to Normality., Amer.Statist. 40 296-298. |
| [26] | Hell, S. W. (2007). Far-Field Optical Nanoscopy., Science 316 1153-1158. |
| [27] | Hell, S. W. and Wichmann, J. (1994). Breaking the diffraction resolution limit by stimulated emission: stimulated-emission-depletion fluorescence microscopy., Opt. Lett. 19 780-782. |
| [28] | Hotz, T., Marnitz, P., Stichtenoth, R., Davies, L., Kabluchko, Z. and Munk, A. (2012). Locally adaptive image denoising by a statistical multiresolution criterion., Comput. Stat. Data An. 56 543 - 558. · Zbl 1239.62116 |
| [29] | James, G. M., Radchenko, P. and Lv, J. (2009). DASSO: connections between the Dantzig selector and lasso., J. R. Stat. Soc. Ser. B Stat. Methodol. 71 127-142. · Zbl 1231.62129 · doi:10.1111/j.1467-9868.2008.00668.x |
| [30] | Kabluchko, Z. (2011). Extremes of the standardized Gaussian noise., Stochastic Process. Appl. 121 515-533. · Zbl 1225.60084 · doi:10.1016/j.spa.2010.11.007 |
| [31] | Kabluchko, Z. and Munk, A. (2009). Shao’s theorem on the maximum of standardized random walk increments for multidimensional arrays., ESAIM Probab. Stat. 13 409-416. · Zbl 1188.60014 · doi:10.1051/ps:2008020 |
| [32] | Kaipio, J. and Somersalo, E. (2005)., Statistical and computational inverse problems . Applied Mathematical Sciences 160 . Springer-Verlag, New York. · Zbl 1068.65022 |
| [33] | Lu, Z., Pong, T. K. and Zhang, Y. (2010). An Alternating Direction Method for Finding Dantzig Selectors Technical Report. Available at, . · Zbl 1255.62096 |
| [34] | 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 |
| [35] | Meyer, Y. (2001)., Oscillating patterns in image processing and nonlinear evolution equations . University Lecture Series 22 . American Mathematical Society, Providence, RI. The fifteenth Dean Jacqueline B. Lewis memorial lectures. · Zbl 0987.35003 |
| [36] | Mildenberger, T. (2008). A geometric interpretation of the multiresolution criterion in nonparametric regression., J. Nonparametr. Stat. 20 1048-5252. · Zbl 1147.62037 · doi:10.1080/10485250802360994 |
| [37] | Mohler, G. O., Bertozzi, A. L., Goldstein, T. A. and Osher, S. J. (2011). Fast TV Regularization for 2D Maximum Penalized Likelihood Estimation., J. Comput. Graph. Statist 20 479-491. · doi:10.1198/jcgs.2010.09048 |
| [38] | Munk, A., Bissantz, N., Wagner, T. and Freitag, G. (2005). On difference-based variance estimation in nonparametric regression when the covariate is high dimensional., J. R. Stat. Soc. Ser. B Stat. Methodol. 67 19-41. · Zbl 1060.62047 · doi:10.1111/j.1467-9868.2005.00486.x |
| [39] | Pawley, J. B. (2006)., Handbook of Biological Confocal Microscopy . Springer. |
| [40] | Polzehl, J. and Spokoiny, V. G. (2000). Adaptive weights smoothing with applications to image restoration., J. R. Stat. Soc. Ser. B Stat. Methodol. 62 335-354. · doi:10.1111/1467-9868.00235 |
| [41] | Romberg, J. K. (2008). The Dantzig selector and generalized thresholding. In, CISS 22-25. IEEE. |
| [42] | Siegmund, D. and Yakir, B. (2000). Tail probabilities for the null distribution of scanning statistics., Bernoulli 6 191-213. · Zbl 0976.62048 · doi:10.2307/3318574 |
| [43] | Tibshirani, R. (1994). Regression Shrinkage and Selection Via the Lasso., J. R. Stat. Soc. Ser. B Stat. Methodol. 58 267-288. · Zbl 0850.62538 |
| [44] | Vogel, C. R. (2002)., Computational methods for inverse problems . Frontiers in Applied Mathematics 23 . Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA. With a foreword by H. T. Banks. · Zbl 1008.65103 · doi:10.1137/1.9780898717570 |
| [45] | Wang, Z., Bovik, A. C., Sheikh, H. R. and Simoncelli, E. P. (2004). Image Quality Assessment: From Error Visibility to Structural Similarity., IEEE Trans. Image Process. 13 600-612. |
| [46] | Xu, S. (2000). Estimation of the convergence rate of Dykstra’s cyclic projections algorithm in polyhedral case., Acta Math. Appl. Sinica (English Ser.) 16 217-220. · Zbl 0980.90500 · doi:10.1007/BF02677683 |
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.
