×
Donoho, David L.

Wedgelets: Nearly minimax estimation of edges. (English) Zbl 0957.62029

Ann. Stat. 27, No. 3, 859-897 (1999).
Summary: We study a simple “horizon model” for the problem of recovering an image from noisy data; in this model the image has an edge with \(\alpha\)-Hölder regularity. Adopting the viewpoint of computational harmonic analysis, we develop an overcomplete collection of atoms called wedgelets, dyadically organized indicator functions with a variety of locations, scales and orientations. The wedgelet representation provides nearly optimal representations of objects in the horizon model, as measured by minimax description length.
We show how to rapidly compute a wedgelet approximation to noisy data by finding a special edgelet-decorated recursive partition which minimizes a complexity-penalized sum of squares. This estimate, using sufficient subpixel resolution, achieves nearly the minimax mean-squared error in the horizon model. In fact, the method is adaptive in the sense that it achieves nearly the minimax risk for any value of the unknown degree of regularity of the horizon, \(1\leq\alpha\leq 2\).
Wedgelet analysis and denoising may be used successfully outside the horizon model. We study images modelled as indicators of star-shaped sets with smooth boundaries and show that complexity-penalized wedgelet partitioning achieves nearly the minimax risk in that setting also.

Cited in 1 Review
Cited in 73 Documents

MSC:

62G07 Density estimation
41A30 Approximation by other special function classes
62C20 Minimax procedures in statistical decision theory
62G20 Asymptotic properties of nonparametric inference
41A63 Multidimensional problems

Keywords:

minimax estimation; edges; edgels; edgelets; fast algorithms; complexity penalized estimates; recursive partitioning; subpixel resolution; oracle inequalities

Software:

PDCO
Cite Review PDF
Full Text: DOI

References:

[1] BARRON, A. and COVER, T. 1991. Minimum complexity density estimation. IEEE Trans. Inform Theory 37 1034 1054. · Zbl 0743.62003 · doi:10.1109/18.86996
[2] BENNETT, N. 1997. Fast algorithms for best anisotropic Walsh bases, and relatives. Ph.D. dissertation, Yale Univ.
[3] BIRGE, L. and MASSART, P. 1997. From model selection to adaptive estimation. In Festschrift Ź. for Lucien Le Cam D. Pollard, E. Torgersen and G. Yang, eds. 55 89. Springer, New York. · Zbl 0920.62042
[4] BREIMAN, L., FRIEDMAN, J., OLSHEN, R. and STONE, C. J. 1983. Classification and Regression Trees. Wadsworth, Belmont, CA. · Zbl 0541.62042
[5] CANDES, E. and DONOHO, D. 1999. Ridgelets: the key to high-dimensional intermittency? Philos. Trans. Roy. Soc. To appear. JSTOR: · Zbl 1082.42503 · doi:10.1098/rsta.1999.0444
[6] CHEN, S., DONOHO, D. L. and SAUNDERS, M. A. 1999. Atomic decomposition by basis pursuit. SIAM J. Sci Comput. 20 33 61. · Zbl 0919.94002 · doi:10.1137/S1064827596304010
[7] COIFMAN, R. R., MEYER, Y., QUAKE, S. and WICKERHAUSER, M. V. 1994. Wavelet analysis Z and signal processing. In Wavelets and Their Applications J. S. Byrnes, J. L. Byrnes,. K. A. Hargreaves and K. Berry, eds. 363 380. Kluwer, Boston. · Zbl 0818.94005
[8] COIFMAN, R. R. and WICKERHAUSER, M. V. 1992. Entropy-based algorithms for best-basis selection. IEEE Trans. Inform Theory 38 713 718. · Zbl 0849.94005 · doi:10.1109/18.119732
[9] DAUBECHIES, I. 1992. Ten Lectures on Wavelets. SIAM, Philadelphia. · Zbl 0776.42018
[10] DAVID, G. and SEMMES, S. 1993. Analysis of and on Uniformly Rectifiable Sets. Amer Math Soc., Providence, RI. · Zbl 0832.42008
[11] DEVORE, R. A. and LORENTZ, G. G. 1993. Constructive Approximation. Springer, New York. · Zbl 0797.41016
[12] DONOHO, D. L. 1993. Unconditional bases are optimal bases for data compression and for statistical estimation. Appl. Comput. Harmon. Anal. 1 100 115. · Zbl 0796.62083 · doi:10.1006/acha.1993.1008
[13] DONOHO, D. L. 1995. Abstract statistical estimation and modern harmonic analysis. In Proc. 1994 Internat. Congr. Math. 997 1005. Birkhauser, Basel. \" · Zbl 0851.62027
[14] DONOHO, D. L. 1996. Unconditional bases and bit-level compression. Appl. Comput. Harmon. Anal. 3 388 392. · Zbl 0936.62004 · doi:10.1006/acha.1996.0032
[15] DONOHO, D. L. 1997. CART and best-ortho-basis: a connection: Ann. Statist. 25 1870 1911. · Zbl 0942.62044 · doi:10.1214/aos/1069362377
[16] DONOHO, D. L. 1998. Sparse components analysis and optimal atomic decomposition. TechZ nical report, Dept. Statistics, Stanford Univ. http: www-stat.stanford.. edu donoho Reports 1998 SCA.ps. URL:
[17] DONOHO, D. L. and JOHNSTONE, I. M. 1994. Ideal spatial adaptation via wavelet shrinkage. Biometrika 81 425 455. JSTOR: · Zbl 0815.62019 · doi:10.1093/biomet/81.3.425
[18] DONOHO, D. L. and JOHNSTONE, I. M. 1994. Ideal de-noising in a basis chosen from a library of orthonormal base. Comp. R. Acad. Sci. Paris A 319 1317 1322. · Zbl 0819.94007
[19] DONOHO, D. L. and JOHNSTONE, I. M. 1994. Empirical atomic decomposition. Unpublished manuscript.
[20] DONOHO, D. L. and JOHNSTONE, I. M. 1998. Minimax estimation via wavelet shrinkage. Ann. Statist. 26 879 921. · Zbl 0935.62041 · doi:10.1214/aos/1024691081
[21] DONOHO, D. L., JOHNSTONE, I. M., KERKYACHARIAN, G. and PICARD, D. 1995. Wavelet shrinkage: asymptopia? J. Roy. Statist. Soc. Ser. B 57 301 369. JSTOR: · Zbl 0827.62035
[22] DONOHO, D. L., JOHNSTONE, I. M., KERKYACHARIAN, G. and PICARD, D. 1996. Density estimation by wavelet thresholding. Ann. Statist. 24 508 539. · Zbl 0860.62032 · doi:10.1214/aos/1032894451
[23] FOSTER, D. and GEORGE, E. I. 1994. The risk inflation factor in multiple linear regression. Ann. Statist. 22 1947 1975. · Zbl 0829.62066 · doi:10.1214/aos/1176325766
[24] FRAZIER, M., JAWERTH, B. and WEISS, G. 1991. Littlewood Paley Theory and the Study of Function Spaces. Amer. Math. Soc., Providence, RI. · Zbl 0757.42006
[25] GEMAN, S. and GEMAN, D. 1984. Stochastic relaxation. Gibbs distributions, and the Bayesian restoration of images. IEEE Trans. Patt. Anal. Mach. Intel. 6 721 741. · Zbl 0573.62030 · doi:10.1109/TPAMI.1984.4767596
[26] JONES, P. W. 1990. Rectifiable sets and the travelling salesman problem. Invent. Math. 102 1 15. · Zbl 0731.30018 · doi:10.1007/BF01233418
[27] KOROSTELEV, A. P. 1987. Minimax estimation of a discontinuous signal. Theory Probab. Appl. 32 796 799. · Zbl 0659.62103 · doi:10.1137/1132110
[28] KOROSTELEV, A. P. and TSYBAKOV, A. 1993. Minimax Theory of Image Reconstruction. Lecture Notes in Statist. 82. Springer, New York. · Zbl 0833.62039
[29] MALLAT, S. 1997. A Wavelet Tour of Signal Processing. Academic Press, New York.
[30] MALLAT, S. and ZHANG, Z. 1993. Matching pursuit in a time frequency dictionary. IEEE Trans. Signal Processing 41 3397 3415. · Zbl 0842.94004
[31] MARR, D. 1982. Vision. Freeman, New York.
[32] MEYER, Y. 1990. Ondelettes et Operateurs I: Ondelettes. Hermann, Paris. English transla. tion: Wavelets and Operators. Cambridge Univ. Press.
[33] MEYER, Y. 1993. Wavelets: Algorithms and Applications. SIAM, Philadelphia.
[34] MULLER, H. G. and SONG, K. S. 1994. Maximin estimation of multidimensional boundaries. \" J. Multivariate Anal. 50 265 281. · Zbl 0798.62053 · doi:10.1006/jmva.1994.1042
[35] OLSHAUSEN, B. A. and FIELD, D. J. 1996. Emergence of simple-cell receptive field properties by learning a sparse code for natural images. Nature 381 607 609.
[36] THIELE, C. M. and VILLEMOES, L. F. 1996. A fast algorithm for adapted time frequency tilings. Appl. Comput. Harmon. Anal. 3 91 100. · Zbl 0857.65148 · doi:10.1006/acha.1996.0009
[37] WICKERHAUSER, M. V. 1994. Adapted Wavelet Analysis from Theory to Software. Peters, Boston. · Zbl 0818.42011
[38] STANFORD, CALIFORNIA 94305 E-MAIL: donoho@stat.stanford.edu
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.