Dual Gramian analysis: Duality principle and unitary extension principle

Fan, Zhitao; Ji, Hui; Shen, Zuowei

doi:10.1090/mcom/2987

Dual Gramian analysis: Duality principle and unitary extension principle
HTML articles powered by AMS MathViewer

by Zhitao Fan, Hui Ji and Zuowei Shen;

Math. Comp. 85 (2016), 239-270

DOI: https://doi.org/10.1090/mcom/2987

Published electronically: June 23, 2015

PDF | Request permission

Abstract:

Dual Gramian analysis is one of the fundamental tools developed in a series of papers by Amos Ron and Zouwei Shen for studying frames. Using dual Gramian analysis, the frame operator can be represented as a family of matrices composed of the Fourier transforms of the generators of (generalized) shift-invariant systems, which allows us to characterize most properties of frames and tight frames in terms of their generators. Such a characterization is applied in the above-mentioned papers to two widely used frame systems, namely Gabor and wavelet frame systems. Among many results, we mention here the discovery of the duality principle for Gabor frames and the unitary extension principle for wavelet frames. This paper aims at establishing the dual Gramian analysis for frames in a general Hilbert space and subsequently characterizing the frame properties of a given system using the dual Gramian matrix generated by its elements. Consequently, many interesting results can be obtained for frames in Hilbert spaces, e.g., estimates of the frame bounds in terms of the frame elements and the duality principle. Moreover, this new characterization provides new insights into the unitary extension principle in a paper by Ron and Shen, e.g., the connection between the unitary extension principle and the duality principle in a weak sense. One application of such a connection is a simplification of the construction of multivariate tight wavelet frames from a given refinable mask. In contrast to the existing methods that require completing a unitary matrix with trigonometric polynomial entries from a given row, our method greatly simplifies the tight wavelet frame construction by converting it to a constant matrix completion problem. To illustrate its simplicity, the proposed construction scheme is used to construct a few examples of multivariate tight wavelet frames from box splines with certain desired properties, e.g., compact support, symmetry or anti-symmetry.

References

C. de Boor, K. Höllig, and S. Riemenschneider, Box splines, Applied Mathematical Sciences, vol. 98, Springer-Verlag, New York, 1993. MR 1243635, DOI 10.1007/978-1-4757-2244-4
Jian-Feng Cai, Raymond H. Chan, and Zuowei Shen, A framelet-based image inpainting algorithm, Appl. Comput. Harmon. Anal. 24 (2008), no. 2, 131–149. MR 2393979, DOI 10.1016/j.acha.2007.10.002
Jian-Feng Cai, Bin Dong, Stanley Osher, and Zuowei Shen, Image restoration: total variation, wavelet frames, and beyond, J. Amer. Math. Soc. 25 (2012), no. 4, 1033–1089. MR 2947945, DOI 10.1090/S0894-0347-2012-00740-1
J. Cai, H. Ji, C. Liu, and Z. Shen, Blind motion deblurring from a single image using sparse approximation, IEEE Conference on Computer Vision and Pattern Recognition, Miami, 2009, IEEE.
Jian-Feng Cai, Hui Ji, Chaoqiang Liu, and Zuowei Shen, Blind motion deblurring using multiple images, J. Comput. Phys. 228 (2009), no. 14, 5057–5071. MR 2537844, DOI 10.1016/j.jcp.2009.04.022
Jian-Feng Cai, Stanley Osher, and Zuowei Shen, Linearized Bregman iterations for frame-based image deblurring, SIAM J. Imaging Sci. 2 (2009), no. 1, 226–252. MR 2486529, DOI 10.1137/080733371
Jian-Feng Cai, Stanley Osher, and Zuowei Shen, Split Bregman methods and frame based image restoration, Multiscale Model. Simul. 8 (2009/10), no. 2, 337–369. MR 2581025, DOI 10.1137/090753504
Peter G. Casazza, Gitta Kutyniok, and Mark C. Lammers, Duality principles in frame theory, J. Fourier Anal. Appl. 10 (2004), no. 4, 383–408. MR 2078264, DOI 10.1007/s00041-004-3024-7
P. G. Casazza, G. Kutyniok, and M. C. Lammers, Duality principles, localization of frames, and Gabor theory, Wavelets XI. Proceedings of the SPIE, 5914 (2005), 389–397.
Maria Charina, Charles K. Chui, and Wenjie He, Tight frames of compactly supported multivariate multi-wavelets, J. Comput. Appl. Math. 233 (2010), no. 8, 2044–2061. MR 2564038, DOI 10.1016/j.cam.2009.09.038
Maria Charina, Mihai Putinar, Claus Scheiderer, and Joachim Stöckler, An algebraic perspective on multivariate tight wavelet frames, Constr. Approx. 38 (2013), no. 2, 253–276. MR 3097047, DOI 10.1007/s00365-013-9191-5
Maria Charina and Joachim Stöckler, Tight wavelet frames for irregular multiresolution analysis, Appl. Comput. Harmon. Anal. 25 (2008), no. 1, 98–113. MR 2419706, DOI 10.1016/j.acha.2007.09.007
Charles K. Chui and Wenjie He, Compactly supported tight frames associated with refinable functions, Appl. Comput. Harmon. Anal. 8 (2000), no. 3, 293–319. MR 1754930, DOI 10.1006/acha.2000.0301
Charles K. Chui and Wenjie He, Construction of multivariate tight frames via Kronecker products, Appl. Comput. Harmon. Anal. 11 (2001), no. 2, 305–312. MR 1848710, DOI 10.1006/acha.2001.0355
Charles K. Chui, Wenjie He, and Joachim Stöckler, Compactly supported tight and sibling frames with maximum vanishing moments, Appl. Comput. Harmon. Anal. 13 (2002), no. 3, 224–262. MR 1942743, DOI 10.1016/S1063-5203(02)00510-9
Ingrid Daubechies, Ten lectures on wavelets, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 61, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1162107, DOI 10.1137/1.9781611970104
Ingrid Daubechies, Bin Han, Amos Ron, and Zuowei Shen, Framelets: MRA-based constructions of wavelet frames, Appl. Comput. Harmon. Anal. 14 (2003), no. 1, 1–46. MR 1971300, DOI 10.1016/S1063-5203(02)00511-0
Ingrid Daubechies, H. J. Landau, and Zeph Landau, Gabor time-frequency lattices and the Wexler-Raz identity, J. Fourier Anal. Appl. 1 (1995), no. 4, 437–478. MR 1350701, DOI 10.1007/s00041-001-4018-3
Bin Dong, Hui Ji, Jia Li, Zuowei Shen, and Yuhong Xu, Wavelet frame based blind image inpainting, Appl. Comput. Harmon. Anal. 32 (2012), no. 2, 268–279. MR 2880283, DOI 10.1016/j.acha.2011.06.001
Bin Dong and Zuowei Shen, MRA-based wavelet frames and applications, Mathematics in image processing, IAS/Park City Math. Ser., vol. 19, Amer. Math. Soc., Providence, RI, 2013, pp. 9–158. MR 3098080, DOI 10.1090/pcms/019/02
Z. Fan, A. Heinecke, and Z. Shen, Duality for frames, preprint, National University of Singapore, 2014.
Bin Han, Compactly supported tight wavelet frames and orthonormal wavelets of exponential decay with a general dilation matrix, J. Comput. Appl. Math. 155 (2003), no. 1, 43–67. Approximation theory, wavelets and numerical analysis (Chattanooga, TN, 2001). MR 1992289, DOI 10.1016/S0377-0427(02)00891-9
Bin Han, Matrix splitting with symmetry and symmetric tight framelet filter banks with two high-pass filters, Appl. Comput. Harmon. Anal. 35 (2013), no. 2, 200–227. MR 3062472, DOI 10.1016/j.acha.2012.08.007
B. Han, Properties of discrete framelet transforms, Math. Model. Nat. Phenom. 8 (2013), no. 1, 18–47. MR 3022977, DOI 10.1051/mmnp/20138102
Bin Han, Symmetric tight framelet filter banks with three high-pass filters, Appl. Comput. Harmon. Anal. 37 (2014), no. 1, 140–161. MR 3202306, DOI 10.1016/j.acha.2013.11.001
Bin Han, Gitta Kutyniok, and Zuowei Shen, Adaptive multiresolution analysis structures and shearlet systems, SIAM J. Numer. Anal. 49 (2011), no. 5, 1921–1946. MR 2837490, DOI 10.1137/090780912
Bin Han and Qun Mo, Splitting a matrix of Laurent polynomials with symmetry and its application to symmetric framelet filter banks, SIAM J. Matrix Anal. Appl. 26 (2004), no. 1, 97–124. MR 2112853, DOI 10.1137/S0895479802418859
Bin Han and Qun Mo, Tight wavelet frames generated by three symmetric $B$-spline functions with high vanishing moments, Proc. Amer. Math. Soc. 132 (2004), no. 1, 77–86. MR 2021250, DOI 10.1090/S0002-9939-03-07205-8
Bin Han and Qun Mo, Symmetric MRA tight wavelet frames with three generators and high vanishing moments, Appl. Comput. Harmon. Anal. 18 (2005), no. 1, 67–93. MR 2110513, DOI 10.1016/j.acha.2004.09.001
Likun Hou, Hui Ji, and Zuowei Shen, Recovering over-/underexposed regions in photographs, SIAM J. Imaging Sci. 6 (2013), no. 4, 2213–2235. MR 3126993, DOI 10.1137/120888302
A. J. E. M. Janssen, Duality and biorthogonality for Weyl-Heisenberg frames, J. Fourier Anal. Appl. 1 (1995), no. 4, 403–436. MR 1350700, DOI 10.1007/s00041-001-4017-4
Ming-Jun Lai and Joachim Stöckler, Construction of multivariate compactly supported tight wavelet frames, Appl. Comput. Harmon. Anal. 21 (2006), no. 3, 324–348. MR 2274841, DOI 10.1016/j.acha.2006.04.001
Ming Li, Zhitao Fan, Hui Ji, and Zuowei Shen, Wavelet frame based algorithm for 3D reconstruction in electron microscopy, SIAM J. Sci. Comput. 36 (2014), no. 1, B45–B69. MR 3158792, DOI 10.1137/130914474
Sherman D. Riemenschneider and Zuowei Shen, Box splines, cardinal series, and wavelets, Approximation theory and functional analysis (College Station, TX, 1990) Academic Press, Boston, MA, 1991, pp. 133–149. MR 1090554
Sherman D. Riemenschneider and Zuowei Shen, Wavelets and pre-wavelets in low dimensions, J. Approx. Theory 71 (1992), no. 1, 18–38. MR 1180872, DOI 10.1016/0021-9045(92)90129-C
A. Ron and Z. Shen, Frames and stable bases for subspaces of $L_2(\mathbb {R}^d)$: the duality principle of Weyl-Heisenberg sets, In M. Chu, R. Plemmons, D. Browns, and D. Ellison, editors, Proceedings of the Lanczos Centenary Conference, pages 422–425, Raleigh, NC, 1993.
Amos Ron and Zuowei Shen, Frames and stable bases for shift-invariant subspaces of $L_2(\mathbf R^d)$, Canad. J. Math. 47 (1995), no. 5, 1051–1094. MR 1350650, DOI 10.4153/CJM-1995-056-1
Amos Ron and Zuowei Shen, Affine systems in $L_2(\mathbf R^d)$: the analysis of the analysis operator, J. Funct. Anal. 148 (1997), no. 2, 408–447. MR 1469348, DOI 10.1006/jfan.1996.3079
Amos Ron and Zuowei Shen, Affine systems in $L_2(\textbf {R}^d)$. II. Dual systems, J. Fourier Anal. Appl. 3 (1997), no. 5, 617–637. Dedicated to the memory of Richard J. Duffin. MR 1491938, DOI 10.1007/BF02648888
Amos Ron and Zuowei Shen, Weyl-Heisenberg frames and Riesz bases in $L_2(\mathbf R^d)$, Duke Math. J. 89 (1997), no. 2, 237–282. MR 1460623, DOI 10.1215/S0012-7094-97-08913-4
Amos Ron and Zuowei Shen, Compactly supported tight affine spline frames in $L_2(\mathbf R^d)$, Math. Comp. 67 (1998), no. 221, 191–207. MR 1433269, DOI 10.1090/S0025-5718-98-00898-9
Amos Ron and Zuowei Shen, Generalized shift-invariant systems, Constr. Approx. 22 (2005), no. 1, 1–45. MR 2132766, DOI 10.1007/s00365-004-0563-8
Zuowei Shen, Wavelet frames and image restorations, Proceedings of the International Congress of Mathematicians. Volume IV, Hindustan Book Agency, New Delhi, 2010, pp. 2834–2863. MR 2827995
Zuowei Shen, Kim-Chuan Toh, and Sangwoon Yun, An accelerated proximal gradient algorithm for frame-based image restoration via the balanced approach, SIAM J. Imaging Sci. 4 (2011), no. 2, 573–596. MR 2810898, DOI 10.1137/090779437