×

zbMATH — the first resource for mathematics

Detecting Markov random fields hidden in white noise. (English) Zbl 1415.62062
Summary: Motivated by change point problems in time series and the detection of textured objects in images, we consider the problem of detecting a piece of a Gaussian Markov random field hidden in white Gaussian noise. We derive minimax lower bounds and propose near-optimal tests.

MSC:
62M05 Markov processes: estimation; hidden Markov models
62G10 Nonparametric hypothesis testing
62M10 Time series, auto-correlation, regression, etc. in statistics (GARCH)
62M40 Random fields; image analysis
PDF BibTeX XML Cite
Full Text: DOI Euclid
References:
[1] Addario-Berry, L., Broutin, N., Devroye, L. and Lugosi, G. (2010). On combinatorial testing problems. Ann. Statist.38 3063-3092. · Zbl 1200.62059
[2] Anandkumar, A., Tong, L. and Swami, A. (2009). Detection of Gauss-Markov random fields with nearest-neighbor dependency. IEEE Trans. Inform. Theory 55 816-827. · Zbl 1367.94108
[3] Arias-Castro, E., Bubeck, S. and Lugosi, G. (2012). Detection of correlations. Ann. Statist.40 412-435. · Zbl 1246.62142
[4] Arias-Castro, E., Bubeck, S. and Lugosi, G. (2015). Detecting positive correlations in a multivariate sample. Bernoulli 21 209-241. · Zbl 1359.62208
[5] Arias-Castro, E., Bubeck, S., Lugosi, G. and Verzelen, N. (2017). Supplement to “Detecting Markov random fields hidden in white noise.” DOI:10.3150/17-BEJ973SUPP. · Zbl 1415.62062
[6] Arias-Castro, E., Candès, E.J. and Durand, A. (2011). Detection of an anomalous cluster in a network. Ann. Statist.39 278-304. · Zbl 1209.62097
[7] Arias-Castro, E., Candès, E.J., Helgason, H. and Zeitouni, O. (2008). Searching for a trail of evidence in a maze. Ann. Statist.36 1726-1757. · Zbl 1143.62006
[8] Arias-Castro, E., Donoho, D.L. and Huo, X. (2005). Near-optimal detection of geometric objects by fast multiscale methods. IEEE Trans. Inform. Theory 51 2402-2425. · Zbl 1282.94014
[9] Baraud, Y. (2002). Non-asymptotic minimax rates of testing in signal detection. Bernoulli 8 577-606. · Zbl 1007.62042
[10] Berthet, Q. and Rigollet, P. (2013). Optimal detection of sparse principal components in high dimension. Ann. Statist.41 1780-1815. · Zbl 1277.62155
[11] Besag, J.E. (1975). Statistical Analysis of Non-Lattice Data. The Statistician 24 179-195.
[12] Boucheron, S., Bousquet, O., Lugosi, G. and Massart, P. (2005). Moment inequalities for functions of independent random variables. Ann. Probab.33 514-560. · Zbl 1074.60018
[13] Boucheron, S., Lugosi, G. and Massart, P. (2013). Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford Univ. Press: London. · Zbl 1279.60005
[14] Brockwell, P.J. and Davis, R.A. (1991). Time Series: Theory and Methods, 2nd ed. New York: Springer. · Zbl 0709.62080
[15] Cai, T.T. and Ma, Z. (2013). Optimal hypothesis testing for high dimensional covariance matrices. Bernoulli 19(5B) 2359-2388. · Zbl 1281.62140
[16] Chellappa, R. and Chatterjee, S. (1985). Classification of textures using Gaussian Markov random fields. Acoustics, Speech and Signal Processing, IEEE Transactions on 33 959-963.
[17] Cross, G.R. and Jain, A.K. (1983). Markov random field texture models. Pattern Analysis and Machine Intelligence, IEEE Transactions on PAMI-5(1) 25-39.
[18] Davidson, K.R. and Szarek, S.J. (2001). Local operator theory, random matrices and Banach spaces. In Handbook of the Geometry of Banach Spaces, Vol. I 317-366. Amsterdam: North-Holland. · Zbl 1067.46008
[19] Davis, R.A., Wei Huang, D. and Yao, Y.-C. (1995). Testing for a change in the parameter values and order of an autoregressive model. Ann. Statist.23 282-304. · Zbl 0822.62072
[20] Desolneux, A., Moisan, L. and Morel, J.-M. (2003). Maximal meaningful events and applications to image analysis. Ann. Statist.31 1822-1851. · Zbl 1046.62104
[21] de la Peña, V.H. and Giné, E. (1999). From dependence to independence, randomly stopped processes. \(U\)-statistics and processes. martingales and beyond. In Decoupling. New York: Springer.
[22] Donoho, D. and Jin, J. (2004). Higher criticism for detecting sparse heterogeneous mixtures. Ann. Statist.32 962-994. · Zbl 1092.62051
[23] Dryden, I.L., Scarr, M.R. and Taylor, C.C. (2003). Bayesian texture segmentation of weed and crop images using reversible jump Markov chain Monte Carlo methods. J. Roy. Statist. Soc. Ser. C 52 31-50. · Zbl 1111.62367
[24] Fritz, J. (1948). Extremum problems with inequalities as subsidiary conditions. In Studies and Essays Presented to R. Courant on His 60 th Birthday, January 8 187-204. New York, NY: Interscience Publishers, Inc. · Zbl 0034.10503
[25] Galun, M., Sharon, E., Basri, R. and Brandt, A. (2003). Texture segmentation by multiscale aggregation of filter responses and shape elements. In Proceedings IEEE International Conference on Computer Vision 716-723. Nice, France.
[26] Giraitis, L. and Leipus, R. (1992). Testing and estimating in the change-point problem of the spectral function. Lith. Math. J.32 15-29. · Zbl 0794.62066
[27] Grigorescu, S.E., Petkov, N. and Kruizinga, P. (2002). Comparison of texture features based on Gabor filters. IEEE Trans. Image Process.11 1160-1167.
[28] Guyon, X. (1995). Random Fields on a Network. New York: Springer. · Zbl 0839.60003
[29] Hofmann, T., Puzicha, J. and Buhmann, J.M. (1998). Unsupervised texture segmentation in a deterministic annealing framework. IEEE Trans. Pattern Anal. Mach. Intell.20 803-818.
[30] Horváth, L. (1993). Change in autoregressive processes. Stochastic Process. Appl.44 221-242.
[31] Huo, X. and Ni, X. (2009). Detectability of convex-shaped objects in digital images, its fundamental limit and multiscale analysis. Statist. Sinica 19 1439-1462. · Zbl 1191.62116
[32] Hušková, M., Prášková, Z. and Steinebach, J. (2007). On the detection of changes in autoregressive time series. I. Asymptotics. J. Statist. Plann. Inference 137 1243-1259. · Zbl 1107.62090
[33] Ingster, Y. (1993). Asymptotically minimax hypothesis testing for nonparametric alternatives I. Math. Methods Statist.2 85-114. · Zbl 0798.62057
[34] Ingster, Y.I. (1999). Minimax detection of a signal for \(ℓ^{l}_{n}\) balls. Math. Methods Statist.7 401-428. · Zbl 1103.62312
[35] Jain, A.K. and Farrokhnia, F. (1991). Unsupervised texture segmentation using Gabor filters. Pattern Recognit.24 1167-1186.
[36] James, D., Clymer, B.D. and Schmalbrock, P. (2001). Texture detection of simulated microcalcification susceptibility effects in magnetic resonance imaging of breasts. J. Magn. Reson. Imaging 13 876-881.
[37] Karkanis, S.A., Iakovidis, D.K., Maroulis, D.E., Karras, D.A. and Tzivras, M. (2003). Computer-aided tumor detection in endoscopic video using color wavelet features. IEEE Trans. Inf. Technol. Biomed.7 141-152.
[38] Kervrann, C. and Heitz, F. (1995). A Markov random field model-based approach to unsupervised texture segmentation using local and global spatial statistics. IEEE Trans. Image Process.4 856-862.
[39] Kim, K., Chalidabhongse, T.H., Harwood, D. and Davis, L. (2005). Real-time foreground-background segmentation using codebook model. Real-Time Imaging 11 172-185. Special Issue on Video Object Processing.
[40] Kumar, A. (2008). Computer-vision-based fabric defect detection: A survey. IEEE Trans. Ind. Electron.55 348-363.
[41] Kumar, S. and Hebert, M. (2003). Man-made structure detection in natural images using a causal multiscale random field. Proc. IEEE Comput. Soc. Conf. Comput. Vis. Pattern Recognit.1 119.
[42] Lauritzen, S.L. (1996). Graphical Models. Oxford Statistical Science Series 17. New York: The Clarendon Press.
[43] Lavielle, M. and Ludeña, C. (2000). The multiple change-points problem for the spectral distribution. Bernoulli 6 845-869. · Zbl 0998.62077
[44] Lehmann, E.L. and Romano, J.P. (2005). Testing Statistical Hypotheses, 3rd ed. Springer Texts in Statistics. New York: Springer. · Zbl 1076.62018
[45] Litton, C.D. and Buck, C.E. (1995). The Bayesian approach to the interpretation of archaeological data. Archaeometry 37 1-24.
[46] Malik, J., Belongie, S., Leung, T. and Shi, J. (2001). Contour and texture analysis for image segmentation. Int. J. Comput. Vis.43 7-27. · Zbl 0972.68604
[47] Manjunath, B.S. and Ma, W.Y. (1996). Texture features for browsing and retrieval of image data. IEEE Trans. Pattern Anal. Mach. Intell.18 837-842.
[48] Palenichka, R.M., Zinterhof, P. and Volgin, M. (2000). Detection of local objects in images with textured background by using multiscale relevance function. In Mathematical Modeling, Estimation, and Imaging (D.C. Wilson, H.D. Tagare, F.L. Bookstein, F.J. Preteux and E.R. Dougherty, eds.) 4121 158-169. Bellingham: SPIE.
[49] Paparoditis, E. (2009). Testing temporal constancy of the spectral structure of a time series. Bernoulli 15 1190-1221. · Zbl 1200.62049
[50] Picard, D. (1985). Testing and estimating change-points in time series. Adv. in Appl. Probab.17 841-867. · Zbl 0585.62151
[51] Portilla, J. and Simoncelli, E.P. (2000). A parametric texture model based on joint statistics of complex wavelet coefficients. Int. J. Comput. Vis.40 49-70. · Zbl 1012.68698
[52] Priestley, M.B. and Subba Rao, T. (1969). A test for non-stationarity of time-series. J. Roy. Statist. Soc. Ser. B 31 140-149. · Zbl 0182.51403
[53] Rue, H. and Held, L. (2005). Gaussian Markov Random Fields: Theory and Applications. Monographs on Statistics and Applied Probability.104. Boca Raton, FL: Chapman & Hall/CRC. · Zbl 1093.60003
[54] Samorodnitsky, G. (2006). Long range dependence. Found. Trends Stoch. Syst.1 163-257. · Zbl 1242.60033
[55] Shahrokni, A., Drummond, T. and Fua, P. (2004). Texture boundary detection for real-time tracking. In Computer Vision—ECCV 2004 (T. Pajdla and JiríJ. Matas, eds.). Lecture Notes in Computer Science 3022 566-577. Berlin/Heidelberg: Springer. · Zbl 1098.68858
[56] Song Chun Zhu, Wu, Y. and Mumford, D. (1998). Filters, random fields and maximum entropy (frame): Towards a unified theory for texture modeling. Int. J. Comput. Vis.27 107-126.
[57] Tony Cai, T., Ma, Z. and Wu, Y. (2013). Sparse PCA: Optimal rates and adaptive estimation. Ann. Statist.41 3074-3110. · Zbl 1288.62099
[58] Varma, M. and Zisserman, A. (2005). A statistical approach to texture classification from single images. Int. J. Comput. Vis.62 61-81.
[59] Verzelen, N. (2010). Adaptive estimation of stationary Gaussian fields. Ann. Statist.38 1363-1402. · Zbl 1189.62157
[60] Walther, G. (2010). Optimal and fast detection of spatial clusters with scan statistics. Ann. Statist.38 1010-1033. · Zbl 1183.62076
[61] Yilmaz, A.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.