×

Jump-penalized least absolute values estimation of scalar or circle-valued signals. (English) Zbl 1383.62124

Summary: We study jump-penalized estimators based on least absolute deviations which are often referred to as Potts estimators [R. B. Potts, Proc. Camb. Philos. Soc. 48, 106–109 (1952; Zbl 0048.45601)]. They are estimators for a parsimonious piecewise constant representation of noisy data having a noise distribution which has heavier tails or which leads to many severe outliers. We consider real-valued data as well as circle-valued data which appear, for instance, as time series of angles or phase signals. We propose efficient algorithms that compute Potts estimators for real-valued scalar as well as for circle-valued data. The real-valued version improves upon the state-of-the-art solver w.r.t. to computational time. In particular for quantized data, the worst case complexity is improved. The circle-valued version is the first efficient algorithm of this kind. As an illustration, we apply our method to estimate the steps in the rotation of the bacterial flagella motor based on real biological data, and to the estimation of wind directions.

MSC:

62G08 Nonparametric regression and quantile regression
62M10 Time series, auto-correlation, regression, etc. in statistics (GARCH)
62P12 Applications of statistics to environmental and related topics
62P10 Applications of statistics to biology and medical sciences; meta analysis
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory

Citations:

Zbl 0048.45601

Software:

circular; CircStats
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Auger, I.; Lawrence, C., Algorithms for the optimal identification of segment neighborhoods, Bull. Math. Biol., 51, 54, (1989) · Zbl 0658.92010 · doi:10.1007/BF02458835
[2] Bellman, R., Dynamic Programming, (1957) · Zbl 0077.13605
[3] Bellman, R.; Roth, R., Curve fitting by segmented straight lines, J. Am. Stat. Assoc., 64, 1084, (1969) · Zbl 1302.90239 · doi:10.1080/01621459.1969.10501038
[4] Bergmann, R.; Laus, F.; Steidl, G.; Weinmann, A., Second order differences of cyclic data and applications in variational denoising, SIAM J Imaging Sci., 7, 2953, (2014) · Zbl 1309.65022 · doi:10.1137/140969993
[5] Bhattacharya, R.; Patrangenaru, V., Large sample theory of intrinsic and extrinsic sample means on manifolds I, Ann. Stat., 31, 29, (2003) · Zbl 1020.62026 · doi:10.1214/aos/1046294456
[6] Bhattacharya, R.; Patrangenaru, V., Large sample theory of intrinsic and extrinsic sample means on manifolds II, Ann. Stat., 33, 1259, (2005) · Zbl 1072.62033 · doi:10.1214/009053605000000093
[7] Blake, A., The least-disturbance principle and weak constraints, Pattern Recognit Lett., 1, 399, (1983) · doi:10.1016/0167-8655(83)90077-6
[8] Blake, A.; Zisserman, A., Visual Reconstruction, (1987)
[9] Boysen, L.; Kempe, A.; Liebscher, V.; Munk, A.; Wittich, O., Consistencies and rates of convergence of jump-penalized least squares estimators, Ann. Stat., 37, 183, (2009) · Zbl 1155.62034 · doi:10.1214/07-AOS558
[10] Boysen, L.; Liebscher, V.; Munk, A.; Wittich, O., Scale space consistency of piecewise constant least squares estimators: another look at the regressogram, Lecture Notes-Monograph Series, vol. 55, Asymptotics: Particles, Processes and Inverse Problems: Festschrift for Piet Groeneboom, 84, (2007) · Zbl 1176.62033 · doi:10.1214/074921707000000274
[11] Bruce, J., Optimum quantization, Technical Report 429, (1965)
[12] Chambolle, A., Image segmentation by variational methods: Mumford and Shah functional and the discrete approximations, SIAM J. Appl. Math., 55, 863, (1995) · Zbl 0830.49015 · doi:10.1137/S0036139993257132
[13] Chambolle, A.; Pock, T., A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vis., 40, 145, (2011) · Zbl 1255.68217 · doi:10.1007/s10851-010-0251-1
[14] Clason, C.; Jin, B.; Kunisch, K., A duality-based splitting method for \[ℓ^1\]-TV image restoration with automatic regularization parameter choice, SIAM J. Sci. Comput., 32, 1505, (2009) · Zbl 1216.94009 · doi:10.1137/090768217
[15] Cremers, D.; Strekalovskiy, E., Total cyclic variation and generalizations, J. Math. Imaging Vis., 47, 277, (2013) · Zbl 1298.94011 · doi:10.1007/s10851-012-0396-1
[16] Dong, Y.; Hintermüller, M.; Neri, M., An efficient primal-dual method for \[L^1\] TV image restoration, SIAM J. Imaging Sci., 2, 1189, (2009) · Zbl 1187.68653 · doi:10.1137/090758490
[17] Donoho, D., Wedgelets: nearly minimax estimation of edges, Ann. Stat., 27, 897, (1999) · Zbl 0957.62029 · doi:10.1214/aos/1018031261
[18] Downs, T.; Mardia, K., Circular regression, Biometrika, 89, 698, (2002) · Zbl 1037.62056 · doi:10.1093/biomet/89.3.683
[19] Drobyshev, A.; Machka, C.; Horsch, M.; Seltmann, M.; Liebscher, V.; de Angelis, M.; Beckers, J., Specificity assessment from fractionation experiments (safe): a novel method to evaluate microarray probe specificity based on hybridisation stringencies, Nucleic Acids Res., 31, 10, (2003) · doi:10.1093/nar/gng001
[20] Dümbgen, L.; Kovac, A., Extensions of smoothing via taut strings, Electronic J. Stat., 3, 75, (2009) · Zbl 1326.62087 · doi:10.1214/08-EJS216
[21] Felzenszwalb, P.; Huttenlocher, D., Efficient belief propagation for early vision, Int. J. Comput. Vis., 70, 54, (2006) · doi:10.1007/s11263-006-7899-4
[22] Felzenszwalb, P.; Zabih, R., Dynamic programming and graph algorithms in computer vision, IEEE Trans. Pattern Anal. Mach. Intell., 33, 740, (2011) · doi:10.1109/TPAMI.2010.135
[23] Fisher, N., Statistical Analysis of Circular Data, (1995)
[24] Fisher, N.; Lewis, T., Estimating the common mean direction of several circular or spherical distributions with differing dispersions, Biometrika, 70, 341, (1983) · doi:10.1093/biomet/70.2.333
[25] Fletcher, P., Geodesic regression and the theory of least squares on Riemannian manifolds, Int. J. Comput. Vis., 105, 185, (2013) · Zbl 1304.62092 · doi:10.1007/s11263-012-0591-y
[26] Fletcher, P. T.; Venkatasubramanian, S.; Joshi, S., The geometric median on Riemannian manifolds with application to robust atlas estimation, NeuroImage, 45, S152, (2009) · doi:10.1016/j.neuroimage.2008.10.052
[27] Fornasier, M.; Ward, R., Iterative thresholding meets free-discontinuity problems, Found. Comput. Math., 10, 567, (2010) · Zbl 1202.65070 · doi:10.1007/s10208-010-9071-3
[28] Forney, G., The Viterbi algorithm, Proc. IEEE, 61, 278, (1973) · doi:10.1109/PROC.1973.9030
[29] Frick, K.; Marnitz, P.; Munk, A., Statistical multiresolution Dantzig estimation in imaging: fundamental concepts and algorithmic framework, Electronic J. Stat., 6, 268, (2012) · Zbl 1314.62094 · doi:10.1214/12-EJS671
[30] Frick, K.; Munk, A.; Sieling, H., Multiscale change point inference, J. R. Stat. Soc. Series B Stat. Methodol., 76, 580, (2014a) · doi:10.1111/rssb.2014.76.issue-3
[31] Frick, S.; Hohage, T.; Munk, A., Asymptotic laws for change point estimation in inverse regression, Stat. Sin., 24, 575, (2014b)
[32] Friedrich, F.; Kempe, A.; Liebscher, V.; Winkler, G., Complexity penalized M-estimation: fast computation, J. Comput. Graph. Stat., 17, 224, (2008) · doi:10.1198/106186008X285591
[33] Fu, H.; Ng, M.; Nikolova, M.; Barlow, J., Efficient minimization methods of mixed \(\) ℓ^\(1-\) ℓ^\[1 and\] ℓ^\(2-\) ℓ^\(1\) norms for image restoration, SIAM J. Sci. Comput., 27, 97, (2006) · Zbl 1103.65044 · doi:10.1137/040615079
[34] Geman, S.; Geman, D., Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images, IEEE Trans. Pattern Anal. Mach. Intell., 6, 741, (1984) · Zbl 0573.62030 · doi:10.1109/TPAMI.1984.4767596
[35] Giaquinta, M.; Modica, G.; Souček, J., Variational problems for maps of bounded variation with values in \[S^1\], Calc. Var. Partial Differ. Equ., 1, 121, (1993) · Zbl 0810.49040 · doi:10.1007/BF02163266
[36] Hotz, T.; Schutte, O. M.; Sieling, H.; Polupanow, T.; Diederichsen, U.; Steinem, C.; Munk, A., Idealizing ion channel recordings by a jump segmentation multiresolution filter, IEEE Trans. NanoBiosci., 12, 386, (2013) · doi:10.1109/TNB.2013.2284063
[37] Hupé, P.; Stransky, N.; Thiery, J.; Radvanyi, F.; Barillot, E., Analysis of array CGH data: from signal ratio to gain and loss of DNA regions, Bioinformatics, 20, 3422, (2004) · doi:10.1093/bioinformatics/bth418
[38] Ising, E., Beitrag zur Theorie des Ferromagnetismus, Zeitschrift für Physik A: Hadrons and Nuclei, 31, 258, (1925)
[39] Jackson, B.; Scargle, J. D.; Barnes, D.; Arabhi, S.; Alt, A.; Gioumousis, P.; Gwin, E.; Sangtrakulcharoen, P.; Tan, L.; Tsai, T. T., An algorithm for optimal partitioning of data on an interval, IEEE Signal Process. Lett., 12, 108, (2005) · doi:10.1109/LSP.2001.838216
[40] Jammalamadaka, S.; SenGupta, A., Topics in Circular Statistics, (2001) · doi:10.1142/SMA
[41] Joo, C.; Balci, H.; Ishitsuka, Y.; Buranachai, C.; Ha, T., Advances in single-molecule fluorescence methods for molecular biology, Annu. Rev. Biochem., 77, 76, (2008) · doi:10.1146/annurev.biochem.77.070606.101543
[42] Killick, R.; Fearnhead, P.; Eckley, I., Optimal detection of changepoints with a linear computational cost, J. Am. Stat. Assoc., 107, 1598, (2012) · Zbl 1258.62091 · doi:10.1080/01621459.2012.737745
[43] Kolmogorov, V.; Pock, T.; Rolinek, M., Total variation on a tree, SIAM J Imaging Sci, 9, 636, (2016) · Zbl 1367.68331 · doi:10.1137/15M1010257
[44] Lellmann, J.; Strekalovskiy, E.; Koetter, S.; Cremers, D., Total variation regularization for functions with values in a manifold, IEEE International Conference on Computer Vision (ICCV), 2951, (2013)
[45] Li, H.; Munk, A.; Sieling, H., FDR-contol in multiscale change-point segmentation, Electron. J. Statist., 10, 959, (2016) · Zbl 1338.62117 · doi:10.1214/16-EJS1131
[46] Little, M.; Jones, N., Generalized methods and solvers for noise removal from piecewise constant signals. I. Background theory, Proc. R. Soc. A Math. Phys. Eng. Sci., 467, 3114, (2011a) · Zbl 1239.94018 · doi:10.1098/rspa.2010.0671
[47] Little, M.; Jones, N., Generalized methods and solvers for noise removal from piecewise constant signals. II. New methods, Proc. R. Soc. A Math. Phys. Eng. Sci., 467, 3140, (2011b) · Zbl 1239.94019 · doi:10.1098/rspa.2010.0674
[48] Mora, T.; Yu, H.; Sowa, Y.; Wingreen, N., Steps in the bacterial flagellar motor, PLoS Comput. Biol., 5, e1000540, (2009) · doi:10.1371/journal.pcbi.1000540
[49] Mumford, D.; Shah, J., Boundary detection by minimizing functionals, IEEE Conference on Computer Vision and Pattern Recognition, 17, 154, (1985)
[50] Mumford, D.; Shah, J., Optimal approximations by piecewise smooth functions and associated variational problems, Commun. Pure Appl. Math., 42, 685, (1989) · Zbl 0691.49036 · doi:10.1002/(ISSN)1097-0312
[51] Oller, J.; Corcuera, J., Intrinsic analysis of statistical estimation, Ann. Stat., 23, 1581, (1995) · Zbl 0843.62027 · doi:10.1214/aos/1176324312
[52] Pennec, X., Intrinsic statistics on Riemannian manifolds: basic tools for geometric measurements, J. Math. Imaging Vis., 25, 154, (2006) · Zbl 1478.94072 · doi:10.1007/s10851-006-6228-4
[53] Potts, R., Some generalized order-disorder transformations, Math. Proc. Cambridge Philos. Soc., 48, 109, (1952) · Zbl 0048.45601 · doi:10.1017/S0305004100027419
[54] Snijders, A. M.; Nowak, N.; Segraves, R.; Blackwood, S.; Brown, N.; Conroy, J.; Hamilton, G.; Hindle, A. K.; Huey, B.; Kimura, K.; Law, S.; Myambo, K.; Palmer, J.; Ylstra, B.; Yue, J. P.; Gray, J. W.; Jain, A. N.; Pinkel, D.; Albertson, D. G., Assembly of microarrays for genome-wide measurement of DNA copy number by CGH, Nat. Genetics, 29, 264, (2001) · doi:10.1038/ng754
[55] Sowa, Y.; Berry, R., Bacterial flagellar motor, Q. Rev. Biophys., 41, 132, (2008) · doi:10.1017/S0033583508004691
[56] Sowa, Y.; Rowe, A.; Leake, M.; Yakushi, T.; Homma, M.; Ishijima, A.; Berry, R., Direct observation of steps in rotation of the bacterial flagellar motor, Nature, 437, 919, (2005) · doi:10.1038/nature04003
[57] Storath, M.; Weinmann, A.; Unser, M., Exact algorithms for \[L^1\]-TV regularization of real-valued or circle-valued signals, SIAM J. Sci. Comput., 38, A630, (2016) · Zbl 1382.94029 · doi:10.1137/15M101796X
[58] Unser, M.; Tafti, P., An Introduction to Sparse Stochastic Processes, (2014) · Zbl 1329.60002 · doi:10.1017/CBO9781107415805
[59] Viterbi, A., Error bounds for convolutional codes and an asymptotically optimum decoding algorithm, IEEE Trans. Inf. Theory, 13, 269, (1967) · Zbl 0148.40501 · doi:10.1109/TIT.1967.1054010
[60] Weinmann, A.; Storath, M., Iterative Potts and Blake-Zisserman minimization for the recovery of functions with discontinuities from indirect measurements, Proc. R. Soc. A, 471, (2015) · Zbl 1371.49016
[61] Weinmann, A.; Demaret, L.; Storath, M., Total variation regularization for manifold-valued data, SIAM J. Imaging Sci., 7, 2257, (2014) · Zbl 1309.65071 · doi:10.1137/130951075
[62] Weinmann, A.; Demaret, L.; Storath, M., Mumford-Shah and Potts regularization for manifold-valued data, J. Math. Imaging Vis., 55, 445, (2016) · Zbl 1344.49055 · doi:10.1007/s10851-015-0628-2
[63] Weinmann, A.; Storath, M.; Demaret, L., The \[{L}^1\]-Potts functional for robust jump-sparse reconstruction, SIAM J. Numer. Anal., 53, 673, (2015) · Zbl 1312.65097 · doi:10.1137/120896256
[64] Winkler, G.; Liebscher, V., Smoothers for discontinuous signals, J. Nonparametric Stat., 14, 222, (2002) · Zbl 1019.62090 · doi:10.1080/10485250211388
[65] Winkler, G.; Wittich, O.; Liebscher, V.; Kempe, A., Don’t shed tears over breaks, Jahresbericht der Deutschen Mathematiker-Vereinigung, 107, 87, (2005) · Zbl 1175.93232
[66] Wittich, O.; Kempe, A.; Winkler, G.; Liebscher, V., Complexity penalized least squares estimators: analytical results, Mathematische Nachrichten, 281, 595, (2008) · Zbl 1152.62062 · doi:10.1002/(ISSN)1522-2616
[67] Xia, Z.; Qiu, P., Jump information criterion for statistical inference in estimating discontinuous curves, Biometrika, 102, 408, (2015) · Zbl 1452.62298 · doi:10.1093/biomet/asv018
[68] Yao, Y.-C., Estimation of a noisy discrete-time step function: Bayes and empirical Bayes approaches, Ann. Stat., 12, 1447, (1984) · Zbl 0551.62069 · doi:10.1214/aos/1176346802
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.