Density, overcompleteness, and localization of frames
Authors:
Radu Balan, Peter G. Casazza, Christopher Heil and Zeph Landau
Journal:
Electron. Res. Announc. Amer. Math. Soc. 12 (2006), 71-86
MSC (2000):
Primary 42C15; Secondary 46C99
DOI:
https://doi.org/10.1090/S1079-6762-06-00163-6
Published electronically:
July 7, 2006
MathSciNet review:
2237271
Full-text PDF Free Access
Abstract |
References |
Similar Articles |
Additional Information
Abstract: This work presents a quantitative framework for describing the overcompleteness of a large class of frames. It introduces notions of localization and approximation between two frames $\mathcal {F} = \{f_i\}_{i \in I}$ and $\mathcal {E} = \{e_j\}_{j \in G}$ ($G$ a discrete abelian group), relating the decay of the expansion of the elements of $\mathcal {F}$ in terms of the elements of $\mathcal {E}$ via a map $a \colon I \to G$. A fundamental set of equalities are shown between three seemingly unrelated quantities: the relative measure of $\mathcal {F}$, the relative measure of $\mathcal {E}$—both of which are determined by certain averages of inner products of frame elements with their corresponding dual frame elements—and the density of the set $a(I)$ in $G$. Fundamental new results are obtained on the excess and overcompleteness of frames, on the relationship between frame bounds and density, and on the structure of the dual frame of a localized frame. These abstract results yield an array of new implications for irregular Gabor frames. Various Nyquist density results for Gabor frames are recovered as special cases, but in the process both their meaning and implications are clarified. New results are obtained on the excess and overcompleteness of Gabor frames, on the relationship between frame bounds and density, and on the structure of the dual frame of an irregular Gabor frame. More generally, these results apply both to Gabor frames and to systems of Gabor molecules, whose elements share only a common envelope of concentration in the time-frequency plane.
[BCHL06a]BCHL05a R. Balan, P. G. Casazza, C. Heil, and Z. Landau, Density, overcompleteness, and localization of frames, I. Theory, J. Fourier Anal. Appl., 12 (2006), 105–143.
[BCHL06b]BCHL05b R. Balan, P. G. Casazza, C. Heil, and Z. Landau, Density, overcompleteness, and localization of frames, II. Gabor frames, J. Fourier Anal. Appl., 12 (2006), 307–344.
- A. G. Baskakov, Wiener’s theorem and asymptotic estimates for elements of inverse matrices, Funktsional. Anal. i Prilozhen. 24 (1990), no. 3, 64–65 (Russian); English transl., Funct. Anal. Appl. 24 (1990), no. 3, 222–224 (1991). MR 1082033, DOI https://doi.org/10.1007/BF01077964
- Peter G. Casazza, Ole Christensen, Alexander M. Lindner, and Roman Vershynin, Frames and the Feichtinger conjecture, Proc. Amer. Math. Soc. 133 (2005), no. 4, 1025–1033. MR 2117203, DOI https://doi.org/10.1090/S0002-9939-04-07594-X
- Peter G. Casazza and Janet Crandell Tremain, The Kadison-Singer problem in mathematics and engineering, Proc. Natl. Acad. Sci. USA 103 (2006), no. 7, 2032–2039. MR 2204073, DOI https://doi.org/10.1073/pnas.0507888103
[Chr03]Chr03 O. Christensen, An introduction to frames and Riesz bases, Birkhäuser, Boston, 2003.
- Ole Christensen, Baiqiao Deng, and Christopher Heil, Density of Gabor frames, Appl. Comput. Harmon. Anal. 7 (1999), no. 3, 292–304. MR 1721808, DOI https://doi.org/10.1006/acha.1999.0271
- Ole Christensen, Sergio Favier, and Felipe Zó, Irregular wavelet frames and Gabor frames, Approx. Theory Appl. (N.S.) 17 (2001), no. 3, 90–101. MR 1885530, DOI https://doi.org/10.1023/A%3A1015562614408
- Ingrid Daubechies, The wavelet transform, time-frequency localization and signal analysis, IEEE Trans. Inform. Theory 36 (1990), no. 5, 961–1005. MR 1066587, DOI https://doi.org/10.1109/18.57199
- 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
- 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 https://doi.org/10.1007/s00041-001-4018-3
- R. J. Duffin and A. C. Schaeffer, A class of nonharmonic Fourier series, Trans. Amer. Math. Soc. 72 (1952), 341–366. MR 47179, DOI https://doi.org/10.1090/S0002-9947-1952-0047179-6
- H. G. Feichtinger, Banach convolution algebras of Wiener type, Functions, series, operators, Vol. I, II (Budapest, 1980) Colloq. Math. Soc. János Bolyai, vol. 35, North-Holland, Amsterdam, 1983, pp. 509–524. MR 751019
- Hans G. Feichtinger, On a new Segal algebra, Monatsh. Math. 92 (1981), no. 4, 269–289. MR 643206, DOI https://doi.org/10.1007/BF01320058
- Hans G. Feichtinger and K. H. Gröchenig, Banach spaces related to integrable group representations and their atomic decompositions. I, J. Funct. Anal. 86 (1989), no. 2, 307–340. MR 1021139, DOI https://doi.org/10.1016/0022-1236%2889%2990055-4
- Hans G. Feichtinger and K. H. Gröchenig, Banach spaces related to integrable group representations and their atomic decompositions. II, Monatsh. Math. 108 (1989), no. 2-3, 129–148. MR 1026614, DOI https://doi.org/10.1007/BF01308667
[For03]For03 M. Fornasier, Constructive methods for numerical applications in signal processing and homogenization problems, Ph.D. Thesis, U. Padua, 2003.
- I. Gohberg, M. A. Kaashoek, and H. J. Woerdeman, The band method for positive and contractive extension problems, J. Operator Theory 22 (1989), no. 1, 109–155. MR 1026078
- Vivek K. Goyal, Jelena Kovačević, and Jonathan A. Kelner, Quantized frame expansions with erasures, Appl. Comput. Harmon. Anal. 10 (2001), no. 3, 203–233. MR 1829801, DOI https://doi.org/10.1006/acha.2000.0340
- Karlheinz Gröchenig, Foundations of time-frequency analysis, Applied and Numerical Harmonic Analysis, Birkhäuser Boston, Inc., Boston, MA, 2001. MR 1843717
- Karlheinz Gröchenig, Localized frames are finite unions of Riesz sequences, Adv. Comput. Math. 18 (2003), no. 2-4, 149–157. Frames. MR 1968117, DOI https://doi.org/10.1023/A%3A1021368609918
- Karlheinz Gröchenig, Localization of frames, Banach frames, and the invertibility of the frame operator, J. Fourier Anal. Appl. 10 (2004), no. 2, 105–132. MR 2054304, DOI https://doi.org/10.1007/s00041-004-8007-1
- Massimo Fornasier and Karlheinz Gröchenig, Intrinsic localization of frames, Constr. Approx. 22 (2005), no. 3, 395–415. MR 2164142, DOI https://doi.org/10.1007/s00365-004-0592-3
- Karlheinz Gröchenig and Michael Leinert, Wiener’s lemma for twisted convolution and Gabor frames, J. Amer. Math. Soc. 17 (2004), no. 1, 1–18. MR 2015328, DOI https://doi.org/10.1090/S0894-0347-03-00444-2
- K. Gröchenig and H. Razafinjatovo, On Landau’s necessary density conditions for sampling and interpolation of band-limited functions, J. London Math. Soc. (2) 54 (1996), no. 3, 557–565. MR 1413898, DOI https://doi.org/10.1112/jlms/54.3.557
- Deguang Han and Yang Wang, Lattice tiling and the Weyl-Heisenberg frames, Geom. Funct. Anal. 11 (2001), no. 4, 742–758. MR 1866800, DOI https://doi.org/10.1007/PL00001683
[Hei03]Hei03 C. Heil, An introduction to weighted Wiener amalgams, Wavelets and Their Applications (Chennai, January 2002), M. Krishna, R. Radha and S. Thangavelu, eds., Allied Publishers, New Delhi, 2003, pp. 183–216.
- 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 https://doi.org/10.1007/s00041-001-4017-4
- A. J. E. M. Janssen, A density theorem for time-continuous filter banks, Signal and image representation in combined spaces, Wavelet Anal. Appl., vol. 7, Academic Press, San Diego, CA, 1998, pp. 513–523. MR 1614987, DOI https://doi.org/10.1016/S1874-608X%2898%2980020-4
[KR05]KR05 A. Klappenecker and M. Rötteler, Mutually unbiased bases, spherical designs, and frames, Wavelets XI (San Diego, CA, 2005), Proc. SPIE 5914, M. Papadakis et al., eds., SPIE, Bellingham, WA (2005), pp. 196–208.
- Youming Liu and Yang Wang, The uniformity of non-uniform Gabor bases, Adv. Comput. Math. 18 (2003), no. 2-4, 345–355. Frames. MR 1968125, DOI https://doi.org/10.1023/A%3A1021350103925
- Jayakumar Ramanathan and Tim Steger, Incompleteness of sparse coherent states, Appl. Comput. Harmon. Anal. 2 (1995), no. 2, 148–153. MR 1325536, DOI https://doi.org/10.1006/acha.1995.1010
- Amin Shokrollahi, Babak Hassibi, Bertrand M. Hochwald, and Wim Sweldens, Representation theory for high-rate multiple-antenna code design, IEEE Trans. Inform. Theory 47 (2001), no. 6, 2335–2367. MR 1873925, DOI https://doi.org/10.1109/18.945251
- J. Sjöstrand, Wiener type algebras of pseudodifferential operators, Séminaire sur les Équations aux Dérivées Partielles, 1994–1995, École Polytech., Palaiseau, 1995, pp. Exp. No. IV, 21. MR 1362552
- Thomas Strohmer and Robert W. Heath Jr., Grassmannian frames with applications to coding and communication, Appl. Comput. Harmon. Anal. 14 (2003), no. 3, 257–275. MR 1984549, DOI https://doi.org/10.1016/S1063-5203%2803%2900023-X
- Wenchang Sun and Xingwei Zhou, Irregular wavelet/Gabor frames, Appl. Comput. Harmon. Anal. 13 (2002), no. 1, 63–76. MR 1930176, DOI https://doi.org/10.1016/S1063-5203%2802%2900002-7
- Patrick J. Wolfe, Simon J. Godsill, and Wee-Jing Ng, Bayesian variable selection and regularization for time-frequency surface estimation, J. R. Stat. Soc. Ser. B Stat. Methodol. 66 (2004), no. 3, 575–589. MR 2088291, DOI https://doi.org/10.1111/j.1467-9868.2004.02052.x
[UAL03]UAL03 M. Unser, A. Aldroubi, and A. Laine, eds., Special Issue on Wavelets in Medical Imaging, IEEE Trans. Medical Imaging, 22 (2003).
- Robert M. Young, An introduction to nonharmonic Fourier series, 1st ed., Academic Press, Inc., San Diego, CA, 2001. MR 1836633
[BCHL06a]BCHL05a R. Balan, P. G. Casazza, C. Heil, and Z. Landau, Density, overcompleteness, and localization of frames, I. Theory, J. Fourier Anal. Appl., 12 (2006), 105–143.
[BCHL06b]BCHL05b R. Balan, P. G. Casazza, C. Heil, and Z. Landau, Density, overcompleteness, and localization of frames, II. Gabor frames, J. Fourier Anal. Appl., 12 (2006), 307–344.
[Bas90]Bas90 A. G. Baskakov, Wiener’s theorem and asymptotic estimates for elements of inverse matrices, Funktsional. Anal. i Prilozhen., 24 (1990), 64–65; translation in Funct. Anal. Appl., 24 (1990), 222–224.
[CCLV05]CCLV03 P. G. Casazza, O. Christensen, A. Lindner, and R. Vershynin, Frames and the Feichtinger conjecture, Proc. Amer. Math. Soc., 133 (2005), 1025–1033.
[CT06]CT05 P. G. Casazza and J. C. Tremain, The Kadison–Singer problem in mathematics and engineering, Proc. Natl. Acad. Sci. USA, 103 (2006), 2032–2039.
[Chr03]Chr03 O. Christensen, An introduction to frames and Riesz bases, Birkhäuser, Boston, 2003.
[CDH99]CDH99 O. Christensen, B. Deng, and C. Heil, Density of Gabor frames, Appl. Comput. Harmon. Anal., 7 (1999), 292–304.
[CFZ01]CFZ01 O. Christensen, S. Favier, and Z. Felipe, Irregular wavelet frames and Gabor frames, Approx. Theory Appl. (N.S.), 17 (2001), 90–101.
[Dau90]Dau90 I. Daubechies, The wavelet transform, time-frequency localization and signal analysis, IEEE Trans. Inform. Theory, 39 (1990), 961–1005.
[Dau92]Dau92 I. Daubechies, Ten lectures on wavelets, SIAM, Philadelphia, 1992.
[DLL95]DLL95 I. Daubechies, H. Landau, and Z. Landau, Gabor time-frequency lattices and the Wexler-Raz identity, J. Fourier Anal. Appl., 1 (1995), 437–478.
[DS52]DS52 R. J. Duffin and A. C. Schaeffer, A class of nonharmonic Fourier series, Trans. Amer. Math. Soc., 72 (1952), 341–366.
[Fei80]Fei80 H. G. Feichtinger, Banach convolution algebras of Wiener type, Functions, Series, Operators, Proc. Conf. Budapest 38, Colloq. Math. Soc. János Bolyai, 1980, pp. 509–524.
[Fei81]Fei81 H. G. Feichtinger, On a new Segal algebra, Monatsh. Math., 92 (1981), 269–289.
[FG89a]FG89a H. G. Feichtinger and K. Gröchenig, Banach spaces related to integrable group representations and their atomic decompositions, I, J. Funct. Anal., 86 (1989) 307–340.
[FG89b]FG89b H. G. Feichtinger and K. Gröchenig, Banach spaces related to integrable group representations and their atomic decompositions, II, Monatsh. Math., 108 (1989) 129–148.
[For03]For03 M. Fornasier, Constructive methods for numerical applications in signal processing and homogenization problems, Ph.D. Thesis, U. Padua, 2003.
[GKW89]GKW89 I. Gohberg, M. A. Kaashoek, and H. J. Woerdeman, The band method for positive and contractive extension problems, J. Operator Theory, 22 (1989), 109–155.
[GKK01]GKK01 V. K. Goyal, J. Kovačević, and J. A. Kelner, Quantized frame expansions with erasures, Appl. Comput. Harmon. Anal., 10 (2001), 203–233.
[Grö01]Gro01 K. Gröchenig, Foundations of time-frequency analysis, Birkhäuser, Boston, 2001.
[Grö03]Gro03 K. Gröchenig, Localized frames are finite unions of Riesz sequences, Adv. Comput. Math., 18 (2003), 149–157.
[Grö04]Gro04 K. Gröchenig, Localization of frames, Banach frames, and the invertibility of the frame operator, J. Fourier Anal. Appl., 10 (2004), 105–132.
[GF05]GF04 K. Gröchenig and M. Fornasier, Intrinsic localization of frames, Constr. Approx., 22 (2005), 395–415.
[GL04]GL04 K. Gröchenig and M. Leinert, Wiener’s lemma for twisted convolution and Gabor frames, J. Amer. Math. Soc., 17 (2004), 1–18.
[GR96]GR96 K. Gröchenig and H. Razafinjatovo, On Landau’s necessary density conditions for sampling and interpolation of band-limited functions, J. London Math. Soc. (2), 54 (1996), 557–565.
[HW01]HW01 D. Han and Y. Wang, Lattice tiling and the Weyl–Heisenberg frames, Geom. Funct. Anal., 11 (2001), 742–758.
[Hei03]Hei03 C. Heil, An introduction to weighted Wiener amalgams, Wavelets and Their Applications (Chennai, January 2002), M. Krishna, R. Radha and S. Thangavelu, eds., Allied Publishers, New Delhi, 2003, pp. 183–216.
[Jan95]Jan95 A. J. E. M. Janssen, Duality and biorthogonality for Weyl–Heisenberg frames, J. Fourier Anal. Appl., 1 (1995), 403–436.
[Jan98]Jan98 A. J. E. M. Janssen, A density theorem for time-continuous filter banks, Signal and Image Representation in Combined Spaces, Y. Y. Zeevi and R. R. Coifman, eds., Wavelet Anal. Appl., Vol. 7, Academic Press, San Diego, CA, 1998, pp. 513–523.
[KR05]KR05 A. Klappenecker and M. Rötteler, Mutually unbiased bases, spherical designs, and frames, Wavelets XI (San Diego, CA, 2005), Proc. SPIE 5914, M. Papadakis et al., eds., SPIE, Bellingham, WA (2005), pp. 196–208.
[LW03]LW03 Y. Liu and Y. Wang, The uniformity of non-uniform Gabor bases, Adv. Comput. Math., 18 (2003), 345–355.
[RS95]RS95 J. Ramanathan and T. Steger, Incompleteness of sparse coherent states, Appl. Comput. Harmon. Anal., 2 (1995) 148–153.
[SHHS01]SHHS01 A. Shokrollahi, B. Hassibi, B. M. Hochwald, and W. Sweldens, Representation theory for high-rate multiple-antenna code design, IEEE Trans. Inform. Theory, 47 (2001), 2335–2367.
[Sjö95]Sjo95 J. Sjöstrand, Wiener type algebras of pseudodifferential operators, Séminaire sur les Équations aux Dérivées Partielles, 1994–1995, Exp. No. IV, École Polytech., Palaiseau, 1995.
[SH03]SH03 T. Strohmer and R. W. Heath, Jr., Grassmannian frames with applications to coding and communication, Appl. Comput. Harmon. Anal., 14 (2003), 257–275.
[SZ02]SZ02 W. Sun and X. Zhou, Irregular wavelet/Gabor frames, Appl. Comput. Harmon. Anal., 13 (2002), 63–76.
[WGW04]WGW04 P. J. Wolfe, S. J. Godsill, and W.-J. Ng, Bayesian variable selection and regularization for time-frequency surface estimation, J. R. Stat. Soc. Ser. B Stat. Methodol., 66 (2004), 575–589.
[UAL03]UAL03 M. Unser, A. Aldroubi, and A. Laine, eds., Special Issue on Wavelets in Medical Imaging, IEEE Trans. Medical Imaging, 22 (2003).
[You01]You01 R. Young, An introduction to nonharmonic Fourier series, Revised first edition, Academic Press, San Diego, 2001.
Similar Articles
Retrieve articles in Electronic Research Announcements of the American Mathematical Society
with MSC (2000):
42C15,
46C99
Retrieve articles in all journals
with MSC (2000):
42C15,
46C99
Additional Information
Radu Balan
Affiliation:
Siemens Corporate Research, 755 College Road East, Princeton, New Jersey 08540
MR Author ID:
356464
Email:
radu.balan@siemens.com
Peter G. Casazza
Affiliation:
Department of Mathematics, University of Missouri, Columbia, Missouri 65211
MR Author ID:
45945
Email:
pete@math.missouri.edu
Christopher Heil
Affiliation:
School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia 30332
Email:
heil@math.gatech.edu
Zeph Landau
Affiliation:
Department of Mathematics R8133, The City College of New York, Convent Avenue at 138th Street, New York, New York 10031
Email:
landau@sci.ccny.cuny.edu
Keywords:
Density,
excess,
frames,
Gabor systems,
modulation spaces,
overcompleteness,
Riesz bases,
wavelets,
Weyl–Heisenberg systems.
Received by editor(s):
July 10, 2005
Published electronically:
July 7, 2006
Additional Notes:
The second author was partially supported by NSF Grants DMS-0102686 and DMS-0405376.
The third author was partially supported by NSF Grant DMS-0139261.
The fourth author was partially supported by The City University of New York PSC-CUNY Research Award Program.
Communicated by:
Guido Weiss
Article copyright:
© Copyright 2006
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.