Wedgelets: nearly minimax estimation of edges

An overcomplete collection of atoms called wedgelets, dyadically organized indicator functions with a variety of locations, scales, and orientations are developed, which provides nearly-optimal representations of objects in the Horizon model, as measured by minimax description length.

Abstract

We study a simple “horizon model” for the problem of\nrecovering an image from noisy data; in this model the image has an edge with\n$\\alpha$-Hölder regularity. Adopting the viewpoint of computational\nharmonic analysis, we develop an overcomplete collection of atoms called\nwedgelets, dyadically organized indicator functions with a variety of\nlocations, scales and orientations. The wedgelet representation provides nearly\noptimal representations of objects in the horizon model, as measured by minimax\ndescription length. We show how to rapidly compute a wedgelet approximation to\nnoisy data by finding a special edgelet-decorated recursive partition\nwhich minimizes a complexity-penalized sum of squares. This estimate, using\nsufficient subpixel resolution, achieves nearly the minimax mean-squared error\nin the horizon model. In fact, the method is adaptive in the sense that it\nachieves nearly the minimax risk for any value of the unknown degree of\nregularity of the horizon, $1 \\leq \\alpha \\leq 2$. Wedgelet analysis and\ndenoising may be used successfully outside the horizon model. We study images\nmodelled as indicators of star-shaped sets with smooth boundaries and show that\ncomplexity-penalized wedgelet partitioning achieves nearly the minimax risk in\nthat setting also.