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. Google Scholar

[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. Google Scholar

[3]

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

[4]

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

[5]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[9]

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

[10]

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

[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. Google Scholar

[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). Google Scholar

[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. Google Scholar

[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. Google Scholar

[15]

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

[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. Google Scholar

[17]

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

[18]

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

[19]

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

[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. Google Scholar

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. Google Scholar

[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. Google Scholar

[3]

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

[4]

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

[5]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[9]

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

[10]

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

[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. Google Scholar

[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). Google Scholar

[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. Google Scholar

[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. Google Scholar

[15]

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

[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. Google Scholar

[17]

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

[18]

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

[19]

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

[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. Google Scholar

[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]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

Ville Kolehmainen, Matthias J. Ehrhardt, Simon R. Arridge. Incorporating structural prior information and sparsity into EIT using parallel level sets. Inverse Problems & Imaging, 2019, 13 (2) : 285-307. doi: 10.3934/ipi.2019015

[19]

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

[20]

Marco Castrillón López, Pablo M. Chacón, Pedro L. García. Lagrange-Poincaré reduction in affine principal bundles. Journal of Geometric Mechanics, 2013, 5 (4) : 399-414. doi: 10.3934/jgm.2013.5.399

2018 Impact Factor: 0.263

Metrics

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

Other articles
by authors

[Back to Top]