2010, 17: 125-137. doi: 10.3934/era.2010.17.125

Optimally sparse 3D approximations using shearlet representations

1. 

Department of Mathematics, Missouri State University, Springfield, Missouri 65804, United States

2. 

Department of Mathematics, University of Houston, Houston, Texas 77204, United States

Received  September 2010 Published  October 2010

This paper introduces a new Parseval frame, based on the 3-D shearlet representation, which is especially designed to capture geometric features such as discontinuous boundaries with very high efficiency. We show that this approach exhibits essentially optimal approximation properties for 3-D functions $f$ which are smooth away from discontinuities along $C^2$ surfaces. In fact, the $N$ term approximation $f_N^S$ obtained by selecting the $N$ largest coefficients from the shearlet expansion of $f$ satisfies the asymptotic estimate

||$f-f_N^S$||$_2^2$ ≍ $N^{-1} (\log N)^2, as N \to \infty.$

Up to the logarithmic factor, this is the optimal behavior for functions in this class and significantly outperforms wavelet approximations, which only yields a $N^{-1/2}$ rate. Indeed, the wavelet approximation rate was the best published nonadaptive result so far and the result presented in this paper is the first nonadaptive construction which is provably optimal (up to a loglike factor) for this class of 3-D data.
    Our estimate is consistent with the corresponding 2-D (essentially) optimally sparse approximation results obtained by the authors using 2-D shearlets and by Candès and Donoho using curvelets.

Citation: Kanghui Guo, Demetrio Labate. Optimally sparse 3D approximations using shearlet representations. Electronic Research Announcements, 2010, 17: 125-137. doi: 10.3934/era.2010.17.125
References:
[1]

E. J. Candès and D. L. Donoho, New tight frames of curvelets and optimal representations of objects with $C^2$ singularities,, Comm. Pure Appl. Math., 57 (2004), 219. doi: doi:10.1002/cpa.10116.

[2]

F. Colonna, G. Easley, K. Guo and D. Labate, Radon transform inversion using the shearlet representation,, Appl. Comput. Harmon. Anal., 29 (2010), 232. doi: doi:10.1016/j.acha.2009.10.005.

[3]

D. L. Donoho, Wedgelets: Nearly-minimax estimation of edges,, Annals of Statistics, 27 (1999), 859. doi: doi:10.1214/aos/1018031261.

[4]

D. L. Donoho, Sparse components of images and optimal atomic decomposition,, Constr. Approx., 17 (2001), 353. doi: doi:10.1007/s003650010032.

[5]

D. L. Donoho and G. Kutyniok., Microlocal analysis of the geometric separation problem,, preprint, (2010).

[6]

D. L. Donoho, M. Vetterli, R. A. DeVore and I. Daubechies, Data compression and harmonic analysis,, IEEE Trans. Inform. Th., 44 (1998), 2435. doi: doi:10.1109/18.720544.

[7]

G. R. Easley, D. Labate and F. Colonna, Shearlet-based total variation diffusion for denoising,, IEEE Trans. Image Proc., 18 (2009), 260. doi: doi:10.1109/TIP.2008.2008070.

[8]

G. R. Easley, D. Labate and W. Lim, Sparse directional image representations using the discrete shearlet transform,, Appl. Comput. Harmon. Anal., 25 (2008), 25. doi: doi:10.1016/j.acha.2007.09.003.

[9]

K. Guo, G. Kutyniok and D. Labate, Sparse multidimensional representations using anisotropic dilation and shear operators,, in, (2006), 189.

[10]

K. Guo and D. Labate, Optimally sparse multidimensional representation using shearlets,, SIAM J. Math. Anal., 9 (2007), 298. doi: doi:10.1137/060649781.

[11]

K. Guo and D. Labate, Characterization and analysis of edges using the continuous shearlet transform,, SIAM J. Imag. Sci., 2 (2009), 959. doi: doi:10.1137/080741537.

[12]

K. Guo and D. Labate, "Optimally Sparse Representations of 3D Data with $C^2$ Surface Singularities Using Parseval Frames of Shearlets,", Technical Report, (2010).

[13]

K. Guo, W.-Q Lim, D. Labate, G. Weiss and E. Wilson, Wavelets with composite dilations,, Electron. Res. Announc. Amer. Math. Soc., 10 (2004), 78. doi: doi:10.1090/S1079-6762-04-00132-5.

[14]

K. Guo, W-Q. Lim, D. Labate, G. Weiss and E. Wilson, Wavelets with composite dilations and their MRA properties,, Appl. Computat. Harmon. Anal., 20 (2006), 231. doi: doi:10.1007/0-8176-4504-7_11.

[15]

G. Kutyniok and W. Lim, Compactly supported shearlets are optimally sparse,, preprint, (2010).

[16]

G. Kutyniok and T. Sauer., Adaptive directional subdivision schemes and shearlet multiresolution analysis,, SIAM J. Math. Anal., 41 (2009), 1436. doi: doi:10.1137/08072276X.

[17]

G. Kutyniok, M. Shahram and D. L. Donoho., Development of a digital shearlet transform based on pseudo-polar FFT,, in, 7446 (2009), 1.

[18]

S. Mallat, "A Wavelet Tour of Signal Processing. The Sparse Way,", Academic Press, (2009).

[19]

E. M. Stein and G. Weiss, "Introduction to Fourier Analysis on Euclidean Spaces,", Princeton University Press, (1970).

[20]

S. Yi, D. Labate, G. R. Easley and H. Krim, A Shearlet approach to edge analysis and detection,, IEEE Trans. Image Process, 18 (2009), 929. doi: doi:10.1109/TIP.2009.2013082.

show all references

References:
[1]

E. J. Candès and D. L. Donoho, New tight frames of curvelets and optimal representations of objects with $C^2$ singularities,, Comm. Pure Appl. Math., 57 (2004), 219. doi: doi:10.1002/cpa.10116.

[2]

F. Colonna, G. Easley, K. Guo and D. Labate, Radon transform inversion using the shearlet representation,, Appl. Comput. Harmon. Anal., 29 (2010), 232. doi: doi:10.1016/j.acha.2009.10.005.

[3]

D. L. Donoho, Wedgelets: Nearly-minimax estimation of edges,, Annals of Statistics, 27 (1999), 859. doi: doi:10.1214/aos/1018031261.

[4]

D. L. Donoho, Sparse components of images and optimal atomic decomposition,, Constr. Approx., 17 (2001), 353. doi: doi:10.1007/s003650010032.

[5]

D. L. Donoho and G. Kutyniok., Microlocal analysis of the geometric separation problem,, preprint, (2010).

[6]

D. L. Donoho, M. Vetterli, R. A. DeVore and I. Daubechies, Data compression and harmonic analysis,, IEEE Trans. Inform. Th., 44 (1998), 2435. doi: doi:10.1109/18.720544.

[7]

G. R. Easley, D. Labate and F. Colonna, Shearlet-based total variation diffusion for denoising,, IEEE Trans. Image Proc., 18 (2009), 260. doi: doi:10.1109/TIP.2008.2008070.

[8]

G. R. Easley, D. Labate and W. Lim, Sparse directional image representations using the discrete shearlet transform,, Appl. Comput. Harmon. Anal., 25 (2008), 25. doi: doi:10.1016/j.acha.2007.09.003.

[9]

K. Guo, G. Kutyniok and D. Labate, Sparse multidimensional representations using anisotropic dilation and shear operators,, in, (2006), 189.

[10]

K. Guo and D. Labate, Optimally sparse multidimensional representation using shearlets,, SIAM J. Math. Anal., 9 (2007), 298. doi: doi:10.1137/060649781.

[11]

K. Guo and D. Labate, Characterization and analysis of edges using the continuous shearlet transform,, SIAM J. Imag. Sci., 2 (2009), 959. doi: doi:10.1137/080741537.

[12]

K. Guo and D. Labate, "Optimally Sparse Representations of 3D Data with $C^2$ Surface Singularities Using Parseval Frames of Shearlets,", Technical Report, (2010).

[13]

K. Guo, W.-Q Lim, D. Labate, G. Weiss and E. Wilson, Wavelets with composite dilations,, Electron. Res. Announc. Amer. Math. Soc., 10 (2004), 78. doi: doi:10.1090/S1079-6762-04-00132-5.

[14]

K. Guo, W-Q. Lim, D. Labate, G. Weiss and E. Wilson, Wavelets with composite dilations and their MRA properties,, Appl. Computat. Harmon. Anal., 20 (2006), 231. doi: doi:10.1007/0-8176-4504-7_11.

[15]

G. Kutyniok and W. Lim, Compactly supported shearlets are optimally sparse,, preprint, (2010).

[16]

G. Kutyniok and T. Sauer., Adaptive directional subdivision schemes and shearlet multiresolution analysis,, SIAM J. Math. Anal., 41 (2009), 1436. doi: doi:10.1137/08072276X.

[17]

G. Kutyniok, M. Shahram and D. L. Donoho., Development of a digital shearlet transform based on pseudo-polar FFT,, in, 7446 (2009), 1.

[18]

S. Mallat, "A Wavelet Tour of Signal Processing. The Sparse Way,", Academic Press, (2009).

[19]

E. M. Stein and G. Weiss, "Introduction to Fourier Analysis on Euclidean Spaces,", Princeton University Press, (1970).

[20]

S. Yi, D. Labate, G. R. Easley and H. Krim, A Shearlet approach to edge analysis and detection,, IEEE Trans. Image Process, 18 (2009), 929. doi: doi:10.1109/TIP.2009.2013082.

[1]

Changzhi Wu, Kok Lay Teo, Volker Rehbock. Optimal control of piecewise affine systems with piecewise affine state feedback. Journal of Industrial & Management Optimization, 2009, 5 (4) : 737-747. doi: 10.3934/jimo.2009.5.737

[2]

Fritz Colonius, Alexandre J. Santana. Topological conjugacy for affine-linear flows and control systems. Communications on Pure & Applied Analysis, 2011, 10 (3) : 847-857. doi: 10.3934/cpaa.2011.10.847

[3]

Tiantian Wu, Xiao-Song Yang. A new class of 3-dimensional piecewise affine systems with homoclinic orbits. Discrete & Continuous Dynamical Systems - A, 2016, 36 (9) : 5119-5129. doi: 10.3934/dcds.2016022

[4]

Hongren Wang, Xue Yang, Yong Li, Xiaoyue Li. LaSalle type stationary oscillation theorems for Affine-Periodic Systems. Discrete & Continuous Dynamical Systems - B, 2017, 22 (7) : 2907-2921. doi: 10.3934/dcdsb.2017156

[5]

Sigurdur F. Hafstein, Christopher M. Kellett, Huijuan Li. Computing continuous and piecewise affine lyapunov functions for nonlinear systems. Journal of Computational Dynamics, 2015, 2 (2) : 227-246. doi: 10.3934/jcd.2015004

[6]

Kanghui Guo, Demetrio Labate, Wang-Q Lim, Guido Weiss and Edward Wilson. Wavelets with composite dilations. Electronic Research Announcements, 2004, 10: 78-87.

[7]

Hildebrando M. Rodrigues, Tomás Caraballo, Marcio Gameiro. Dynamics of a Class of ODEs via Wavelets. Communications on Pure & Applied Analysis, 2017, 16 (6) : 2337-2355. doi: 10.3934/cpaa.2017115

[8]

Liming Zhang, Tao Qian, Qingye Zeng. Edge detection by using rotational wavelets. Communications on Pure & Applied Analysis, 2007, 6 (3) : 899-915. doi: 10.3934/cpaa.2007.6.899

[9]

Guoshan Zhang, Shiwei Wang, Yiming Wang, Wanquan Liu. LS-SVM approximate solution for affine nonlinear systems with partially unknown functions. Journal of Industrial & Management Optimization, 2014, 10 (2) : 621-636. doi: 10.3934/jimo.2014.10.621

[10]

Elena Goncharova, Maxim Staritsyn. On BV-extension of asymptotically constrained control-affine systems and complementarity problem for measure differential equations. Discrete & Continuous Dynamical Systems - S, 2018, 11 (6) : 1061-1070. doi: 10.3934/dcdss.2018061

[11]

Vadim Azhmyakov, Alex Poznyak, Omar Gonzalez. On the robust control design for a class of nonlinearly affine control systems: The attractive ellipsoid approach. Journal of Industrial & Management Optimization, 2013, 9 (3) : 579-593. doi: 10.3934/jimo.2013.9.579

[12]

Yong Li, Hongren Wang, Xue Yang. Fink type conjecture on affine-periodic solutions and Levinson's conjecture to Newtonian systems. Discrete & Continuous Dynamical Systems - B, 2018, 23 (6) : 2607-2623. doi: 10.3934/dcdsb.2018123

[13]

Bruno Sixou, Valentina Davidoiu, Max Langer, Francoise Peyrin. Absorption and phase retrieval with Tikhonov and joint sparsity regularizations. Inverse Problems & Imaging, 2013, 7 (1) : 267-282. doi: 10.3934/ipi.2013.7.267

[14]

Qiao-Fang Lian, Yun-Zhang Li. Reducing subspace frame multiresolution analysis and frame wavelets. Communications on Pure & Applied Analysis, 2007, 6 (3) : 741-756. doi: 10.3934/cpaa.2007.6.741

[15]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017

[16]

Jian Lu, Lixin Shen, Chen Xu, Yuesheng Xu. Multiplicative noise removal with a sparsity-aware optimization model. Inverse Problems & Imaging, 2017, 11 (6) : 949-974. doi: 10.3934/ipi.2017044

[17]

A. Calogero. Wavelets on general lattices, associated with general expanding maps of $\mathbf R^n$. Electronic Research Announcements, 1999, 5: 1-10.

[18]

Jakob S. Jørgensen, Emil Y. Sidky, Per Christian Hansen, Xiaochuan Pan. Empirical average-case relation between undersampling and sparsity in X-ray CT. Inverse Problems & Imaging, 2015, 9 (2) : 431-446. doi: 10.3934/ipi.2015.9.431

[19]

Henrik Garde, Kim Knudsen. 3D reconstruction for partial data electrical impedance tomography using a sparsity prior. Conference Publications, 2015, 2015 (special) : 495-504. doi: 10.3934/proc.2015.0495

[20]

Patrick Fischer. Multiresolution analysis for 2D turbulence. Part 1: Wavelets vs cosine packets, a comparative study. Discrete & Continuous Dynamical Systems - B, 2005, 5 (3) : 659-686. doi: 10.3934/dcdsb.2005.5.659

2016 Impact Factor: 0.483

Metrics

  • PDF downloads (10)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]