Recovering edges in ill-posed inverse problems: Optimality of curvelet frames. (English) Zbl 1101.62335

Summary: We consider a model problem of recovering a function \(f(x_1,x_2)\) from noisy Radon data. The function f to be recovered is assumed smooth apart from a discontinuity along a \(C^2\) curve, that is, an edge. We use the continuum white-noise model, with noise level \(\varepsilon\). Traditional linear methods for solving such inverse problems behave poorly in the presence of edges. Qualitatively, the reconstructions are blurred near the edges; quantitatively, they give in our model mean squared errors (MSEs) that tend to zero with noise level \(\varepsilon\) only as \(O(\varepsilon^{1/2})\) as \(\varepsilon\to 0\). A recent innovation–nonlinear shrinkage in the wavelet domain–visually improves edge sharpness and improves MSE convergence to \(O(\varepsilon^{2/3})\). However, as we show here, this rate is not optimal.
In fact, essentially optimal performance is obtained by deploying the recently-introduced tight frames of curvelets in this setting. Curvelets are smooth, highly anisotropic elements ideally suited for detecting and synthesizing curved edges. To deploy them in the Radon setting, we construct a curvelet-based biorthogonal decomposition of the Radon operator and build “curvelet shrinkage” estimators based on thresholding of the noisy curvelet coefficients. In effect, the estimator detects edges at certain locations and orientations in the Radon domain and automatically synthesizes edges at corresponding locations and directions in the original domain.
We prove that the curvelet shrinkage can be tuned so that the estimator will attain, within logarithmic factors, the MSE \(O(\varepsilon^{4/5})\) as noise level \(\varepsilon\to 0\). This rate of convergence holds uniformly over a class of functions which are \(C^2\) except for discontinuities along \(C^2\) curves, and (except for log terms) is the minimax rate for that class. Our approach is an instance of a general strategy which should apply in other inverse problems; we sketch a deconvolution example.


62G20 Asymptotic properties of nonparametric inference
42C40 Nontrigonometric harmonic analysis involving wavelets and other special systems
62H35 Image analysis in multivariate analysis
62C20 Minimax procedures in statistical decision theory
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
Full Text: DOI Euclid


[1] BERTERO, M. (1989). Linear inverse and ill-posed problems. In Advances in Electronics and Electron physics (P. W. Hawkes, ed.). Academic Press, New York.
[2] BERTERO, M., DE MOL, C. and PIKE, E. R. (1985). Linear inverse problems with discrete data I: General formulation and singular sy stem analysis. Inverse Problems 1 301-330. · Zbl 0615.65057
[3] BROWN, L. D. and LOW, M. G. (1996). Asy mptotic equivalence of nonparametric regression and white noise. Ann. Statist. 24 2384-2398. · Zbl 0867.62022
[4] CANDÈS, E. J. (1998). Ridgelets: theory and applications. Ph.D. dissertation, Dept. Statistics, Stanford Univ.
[5] CANDÈS, E. J. (1999). Harmonic analysis of neural networks. Appl. Comput. Harmon. Anal. 6 197-218. · Zbl 0931.68104
[6] CANDÈS, E. J. (1999). Monoscale ridgelets for image compression and denoising. Unpublished manuscript.
[7] CANDÈS, E. J. and DONOHO, D. L. (1999). Ridgelets: a key to high-dimensional intermittency? Philos. Trans. Roy. Soc. London Ser. A 357 2495-2509. · Zbl 1082.42503
[8] CANDÈS, E. J. and DONOHO, D. L. (1999). Curvelets. Unpublished manuscript. Available at www.stat.stanford.edu/ donoho/Reports/1999/curvelets.pdf URL: · Zbl 0989.42020
[9] CANDÈS, E. J. and DONOHO, D. L. (2000). Curvelets: A surpisingly effective nonadaptive representation of objects with edges. In Curve and Surface Fitting (A. Cohen, C. Rabut and L. L. Schumaker, eds.) 105-120. Vanderbilt Univ. Press, Nashville, TN.
[10] CHARBONNIER, P., BLANC-FÈRAUD, L., AUBERT, G. and BARLAUD, M. (1997). Deterministic edge-preserving regularization in computed imaging. IEEE Trans. Image Process. 6 298-311.
[11] DAUBECHIES, I. (1992). Ten Lectures on Wavelets. SIAM, Philadelphia. · Zbl 0776.42018
[12] DAVISON, M. E. (1981). A singular value decomposition for the Radon transform in n-dimensional space. Numer. Funct. Anal. Optim. 3 321-340. · Zbl 0467.65069
[13] DEANS, S. R. (1983). The Radon Transform and Some of Its Applications. Wiley, New York. · Zbl 0561.44001
[14] DOBSON, D. and SANTOSA, F. (1996). Recovery of blocky images from noisy and blurred data. SIAM J. Appl. Math. 56 1181-1198. JSTOR: · Zbl 0858.68121
[15] 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
[16] DONOHO, D. L. (1994). Statistical estimation and optimal recovery. Ann. Statist. 22 238-270. · Zbl 0805.62014
[17] DONOHO, D. L. (1994). Asy mptotic minimax risk for sup norm loss: Solution via optimal recovery. Probab. Theory Related Fields 99 145-170. · Zbl 0802.62007
[18] DONOHO, D. L. (1995). Nonlinear solution of linear inverse problems by wavelet-vaguelette decomposition. Appl. Comput. Harmon. Anal. 2 101-126. · Zbl 0826.65117
[19] DONOHO, D. L. (1995). Denoising by soft-thresholding. IEEE Trans. Inform. Theory 41 613-627. · Zbl 0820.62002
[20] DONOHO, D. L. (1997). Renormalizing experiments for nonlinear functionals. In Festschrift for Lucien Le Cam (D. L. Pollard, E. N. Torgersen and G. L. Yang, eds.) 167-181. Springer, New York. · Zbl 0921.62058
[21] DONOHO, D. L. (1999). Wedgelets: nearly minimax estimation of edges. Ann. Statist. 27 859-897. · Zbl 0957.62029
[22] DONOHO, D. L. (2000). Orthonormal ridgelets and linear singularities. SIAM J. Math. Anal. 31 1062-1099. · Zbl 0952.42020
[23] DONOHO, D. L. (2001). Sparse components of images and optimal atomic decompositions. Constr. Approx. 17 353-382. · Zbl 0995.65150
[24] DONOHO, D. L. and JOHNSTONE, I. M. (1994). Minimax risk over p balls for q losses. Probab. Theory Related Fields 99 277-303. · Zbl 0802.62006
[25] DONOHO, D. L. and JOHNSTONE, I. M. (1994). Ideal spatial adaptation via wavelet shrinkage. Biometrika 81 425-455. JSTOR: · Zbl 0815.62019
[26] DONOHO, D. L. and JOHNSTONE, I. M. (1995). Empirical atomic decomposition. Unpublished manuscript.
[27] DONOHO, D. L. and JOHNSTONE, I. M. (1998). Minimax estimation via wavelet shrinkage. Ann. Statist. 26 879-921. · Zbl 0935.62041
[28] DONOHO, D. L. and JOHNSTONE, I. M. (1999). Asy mptotic minimaxity of wavelet estimators with sampled data. Statist. Sinica 9 1-32. · Zbl 1065.62518
[29] DONOHO, D. L. and LIU, R. C. (1991). Geometrizing rates of convergence III. Ann. Statist. 19 668-701. · Zbl 0754.62029
[30] DONOHO, D. L. and LOW, M. G. (1992). Renormalization exponents and optimal pointwise rates of convergence. Ann. Statist. 20 944-970. · Zbl 0797.62032
[31] DONOHO, D. L. and NUSSBAUM, M. (1990). Minimax quadratic estimation of a quadratic functional. J. Complexity 6 290-323. · Zbl 0724.62039
[32] EFROIMOVICH, S. YU. and PINSKER, M. S. (1981). Estimation of square-integrable density on the basis of a sequence of observations. Problemy Peredachi Informatsii 17 50-68 (in Russian). Problems Inform. Transmission 17 (1982) 182-196 (in English). · Zbl 0475.62073
[33] EFROIMOVICH, S. YU. and PINSKER, M. S. (1982). Estimation of square-integrable probability density of a random variable. Problemy Peredachi Informatsii 18 19-38 (in Russian). Problems Inform. Transmission 18 (1983) 175-189 (in English). · Zbl 0514.62045
[34] EFROMOVICH, S. and SAMAROV, A. (1996). Asy mptotic equivalence of nonparametric regression and white noise models has its limits. Statist. Probab. Lett. 28 143-145. · Zbl 0849.62023
[35] FRAZIER, M. and JAWERTH, B. (1985). Decomposition of Besov spaces. Indiana Univ. Math. J. 34 777-799. · Zbl 0551.46018
[36] FRAZIER, M. and JAWERTH, B. (1990). A discrete transform and decompositions of distribution spaces. J. Funct. Anal. 93 34-170. · Zbl 0716.46031
[37] 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
[38] GEMAN, D. and REy NOLDS, G. (1992). Constrained restoration and the recovery of discontinuities. IEEE Trans. Pattern Anal. Mach. Intell. 14 367-382.
[39] GEMAN, D. and YANG, C. (1995). Nonlinear image recovery with half-quadratic regularization. IEEE Trans. Image Processing 4 932-946.
[40] HELGASON, S. (1980). The Radon Transform. Birkhäuser, Boston. · Zbl 0453.43011
[41] IBRAGIMOV, I. A. and HAS’MINSKII, R. Z. (1984). Nonparametric estimation of the value of a linear functional in a Gaussian white noise. Theory Probab. Appl. 29 18-32. · Zbl 0532.62061
[42] JOHNSTONE, I. M. and SILVERMAN, B. W. (1990). Speed of estimation in positron emission tomography and related inverse problems. Ann. Statist. 18 251-280. · Zbl 0699.62043
[43] JOHNSTONE, I. M. and SILVERMAN, B. W. (1991). Discretization effects in statistical inverse problems. J. Complexity 7 1-34. · Zbl 0737.62099
[44] JOHNSTONE, I. M. and SILVERMAN, B. W. (1997). Wavelet threshold estimators for data with correlated noise. J. Roy. Statist. Soc. Ser. B. 59 319-351. JSTOR: · Zbl 0886.62044
[45] JONSSON, E., HUANG, S. C. and CHAN, T. (1998). Total variation regularization in positron emission tomography. Technical report, Dept. Mathematics, Univ. California, Los Angeles.
[46] KALIFA, J. and MALLAT, S. G. (1999). Thresholding estimators for inverse problems and deconvolutions. Unpublished manuscript. · Zbl 1102.62318
[47] KHAS’MINSKII, R. Z. and LEBEDEV, V. S. (1990). On the properties of parametric estimators for areas of a discontinuous image. Problems Control Inform. Theory 19 375-385. · Zbl 0724.62085
[48] KOROSTELEV, A. P. and TSy BAKOV, A. B. (1993). Minimax Theory of Image Reconstruction. Lecture Notes in Statist. 82. Springer, New York. · Zbl 0833.62039
[49] LEMARIÉ, P. G. and MEy ER, Y. (1986). Ondelettes et bases hilbertiennes. Rev. Mat. Iberoamericana 2 1-18. · Zbl 0657.42028
[50] LOUIS, A. K. (1986). Incomplete data problems in X-ray computerized tomography I. Singular value decomposition of the limited-angle transform. Numer. Math. 48 251-262. · Zbl 0578.65131
[51] MALLAT, S. G. (1989). Multiresolution approximations and wavelet orthonormal bases of L2(R). Trans. Amer. Math. Soc. 315 69-87. JSTOR: · Zbl 0686.42018
[52] MEy ER, Y. (1990). Ondelettes et Opérateurs I. Ondelettes. Hermann, Paris.
[53] MEy ER, Y. (1990). Ondelettes et Opérateurs II. Opérateurs de Calderón Zy gmund. Hermann, Paris.
[54] NUSSBAUM, M. (1985). Spline smoothing in regression models and asy mptotic efficiency in L2. Ann. Statist. 13 984-997. · Zbl 0596.62052
[55] O’SULLIVAN, F. (1986). A statistical perspective on ill-posed inverse problems. Statist. Sci. 1 502-527. · Zbl 0955.65500
[56] PILZ, J. (1986). Minimax linear regression estimation with sy mmetric parameter restrictions. J. Statist. Plann. Inference 13 297-318. · Zbl 0602.62054
[57] PINSKER, M. S. (1980). Optimal filtering of square integrable signals in Gaussian white noise. Problemy Peredachi Informatsii 16 52-68 (in Russian). Problems Inform. Transmission 16 (1980) 120-133 (in English). · Zbl 0452.94003
[58] RUDIN, L., OSHER, S. and FATEMI, E. (1992). Nonlinear total variation based noise removal algorithms. Phy s. D 60 259-268. · Zbl 0780.49028
[59] STEIN, E. M. (1970). Singular Integrals and Differentiability Properties of Functions. Princeton Univ. Press. · Zbl 0207.13501
[60] TEBOUL, S., BLANC-FÉRAUD, L., AUBERT, G. and BARLAUD, M. (1998). Variational approach for edge-preserving regularization using coupled PDEs. IEEE Trans. Image Processing 7 387-397.
[61] TERZOPOULOS, D. (1986). Regularization of inverse visual problems involving discontinuities. IEEE Trans. Pattern Anal. Machine Intell. 8 413-424.
[62] TIKHONOV, A. N. (1963). Solution of incorrectly formulated problems and the regularization method. Soviet Math. Doklady 4 1035-1039. · Zbl 0141.11001
[63] VETTERLI, M. and KOVACEVIC, J. (1995). Wavelets and Subband Coding. Prentice-Hall, Englewood Cliffs, NJ.
[64] WAHBA, G. (1990). Spline Models for Observational Data. SIAM, Philadelphia. · Zbl 0813.62001
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.