Abstract
Finite tight frames are widely used for many applications. An important problem is to construct finite frames with prescribed norm for each vector in the tight frame. In this paper we provide a fast and simple algorithm for such a purpose. Our algorithm employs the Householder transformations. For a finite tight frame consisting of m vectors in ℝn or ℂn only O(nm) operations are needed. In addition, we also study the following question: Given a set of vectors in ℝn or ℂn, how many additional vectors, possibly with constraints, does one need to add in order to obtain a tight frame?
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J.J. Benedetto and M. Fickus, Finite normalized tight frames, Adv. Comput. Math. 18 (2003) 357–385.
P.G. Casazza, Modern tools for Weyl–Heisenberg (Gabor) frame theory, Adv. Image Electron Phys. 115 (2000) 1–127.
P.G. Casazza and M. Leon, Existence and construction of finite tight frames, Preprint.
P.G. Casazza, M. Leon and J.C. Tremain, Custom built tight frames, Preprint.
P.G. Casazza and J. Kovačević, Equal-norm tight frames with erasures, Adv. Comput. Math. 18 (2003) 387–430.
R.J. Duffin and A.C. Schaeffer, A class of nonharmonic Fourier series, Trans. Amer. Math. Soc. 72 (1952) 341–366.
Y. Elder and G.D. Forney, Optimal tight frames and quantum measurement, Preprint.
V.K. Goyal, J. Kovačević and J.A. Kelner, Quantized frame expansions with erasures, Appl. Comput. Harmon. Anal. 10 (2001) 203–233.
V.K. Goyal, M. Vetterli and N.T. Thao, Quantized overcomplete expansions in ℝN: analysis, synthesis, and algorithms, IEEE Trans. Inform. Theory 44 (1998) 16–31.
K. Gröchenig, Foundation of Time-Frequency Analysis (Birkhäuser, Boston, 2001).
A.S. Householder, The Theory of Matrices in Numerical Analysis (Blaisdell Publishing Co. Ginn and Co., New York, 1964).
W.V. Parker and J.C. Eaves, Matrices (The Ronald Press Co., New York, 1960).
D. Serre, Matrices. Theory and Applications, Translated from the 2001 French original, Grad. Texts in Math., Vol. 216 Springer, (New York, 2002).
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by J. Benedetto
Dedicated to Dr. Micchelli for his 60th birthday
Mathematics subject classification (2000)
Primary 42C15.
De-Jun Feng: Supported in part by the Special Funds for Major State Basic Research Projects in China.
Yang Wang: Supported in part by the National Science Foundation, grants DMS-0070586 and DMS-0139261.
Rights and permissions
About this article
Cite this article
Feng, DJ., Wang, L. & Wang, Y. Generation of finite tight frames by Householder transformations. Adv Comput Math 24, 297–309 (2006). https://doi.org/10.1007/s10444-004-7637-9
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s10444-004-7637-9