AMS Short Course on Finite Frame Theory: A Complete Introduction to Overcompleteness
This two-day course will take place on Thursday and Friday, January 8 and 9, before the joint meeting actually begins in Room 212, Henry B. Gonzalez Convention Center. It is organized by Kasso A. Okoudjou, Norbert Wiener Center, Department of Mathematics, University of Maryland, College Park.
Introduction: Hilbert space frames have traditionally been used to decompose, process and reconstruct signals/images. Today frame theory is an exciting, dynamic subject with applications to pure mathematics, applied mathematics, engineering, medicine, computer science, and quantum computing. From a mathematical perspective, frame theory is at the intersection of many fields such as functional and harmonic analysis, numerical analysis, matrix theory, numerical linear algebra, algebraic and differential geometry, probability, statistics, and convex geometry. Problems in frame design arising in applications often present fundamental, completely new challenges never before encountered in mathematics.
The goals of this short course are to: (1) introduce the fundamental tools and examples of frames; (2) describe a number of applications that required the design of specific frames; (3) present the connection of frames to some of the research fields and notions described above; (4) present some recent frame-based developments in compressed sensing and dictionary learning.
Frames and Phaseless Reconstruction
Radu Balan, Department of Mathematics and Center for Scientific Computations and Mathematical Modeling, University of Maryland, College Park.
Frame design for phaseless reconstruction is now part of the broader problem of nonlinear reconstruction and is an emerging topic in harmonic analysis. The problem of phaseless reconstruction can be simply stated as follows. Given the magnitudes of the coefficients of an output of a linear redundant system (frame), we want to reconstruct the unknown input. This problem has first occurred in X-ray crystallography starting from the early 20th century. In 1985 the Nobel prize in chemistry was awarded to Herbert Hauptman (a mathematician) for his contributions to the development of X-ray crystallography. The same nonlinear reconstruction problem shows up in speech processing, particularly in speech recognition.
In this lecture we shall cover existing analysis results as well as algorithms for signal recovery including: (1) Necessary and sufficient conditions for injectivity; (2) Lipschitz bounds of the nonlinear map and its left inverses; (3) Stochastic performance bounds; (4) Convex relaxation algorithms for inversion; (5) Least-Squares inversion algorithms.
References
- R. Balan, P. Casazza, D. Edidin, On signal reconstruction without phase, Appl. Comput. Harmon. Anal. 20 (2006), 345–356.
- R. Balan, Reconstruction of Signals from Magnitudes of Redundant Representations: The Complex Case, arXiv:1304.1839v1[math.FA] 6, April 2013.
- E. Candès, T. Strohmer, V. Voroninski, PhaseLift: Exact and stable signal recovery from magnitude measurements via convex programming, Comm. Pure and App. Math 6, no. 8, (2013), 1241–1274.
An Introduction to Finite Frame Theory
Peter G. Casazza, Frame Research Center, University of Missouri.
Hilbert space frames have traditionally been used in signal/image processing. However, today frame theory is an exciting, dynamic subject with applications to pure mathematics, applied mathematics, engineering, medicine, computer science, quantum computing, and more with new applications arising every year. Problems in frame design arising in applications often present fundamental, completely new challenges never before encountered in mathematics.
In this lecture we will introduce the basics of frame theory including:
(1) The definition of a Hilbert space frame and the basics of the subject.
(2) The operators associated with frames including the analysis, synthesis and frame operators, reconstruction Parseval frames and equiangular frames.
(3) A number of examples to illustrate the concepts and the basics of frame construction.
(4) Matrix formulations of these concepts including the Grammian matrix and its properties.
(5) Dual frames and their applications.
(6) Naimark’s Theorem classifying Parseval frames.
(7) Equivalence of frames, redundancy and spanning and independence properties of frames.
(8) A brief introduction to some of the significant applications of frame theory.
References
- P. G. Casazza, The art of frame theory, Taiwanese Journal of Math 4, No. 2, (2000), 129–201.
- P. G. Casazza and G. Kutyniok (eds.), Finite Frames: Theory and Applications, Birkhauser, Boston, 2012.
- O. Christensen, An Introduction to Frames and Riesz Bases, Applied and Numerical Harmonic Analysis, Birkhauser, Boston, 2001.
Compressed Sensing and Dictionary Learning
Guangliang Chen, San Jose State University, and Deanna Needell, Claremont McKenna College.
Compressed sensing is a new field that arose as a response to inefficient traditional signal acquisition schemes. Under the assumption that the signal of interest is sparse, one wishes to take a small number of linear samples and later utilize a reconstruction algorithm to accurately recover the compressed signal. Typically, one assumes the signal is sparse itself or with respect to some fixed orthonormal basis. However, in applications one instead more often encounters signals sparse with respect to a tight frame which may be far from orthonormal. In the first part of this lecture, we will introduce the compressed sensing problem as well as recent results extending the theory to the case of sparsity in tight frames.
The second part of the lecture focuses on dictionary learning which is also a new field, but closely related to compressive sensing. Briefly speaking, a dictionary is an overcomplete and redundant system consisting of prototype signals that are used to express other signals. Due to the redundancy, for any given signal, there are many ways to represent it, but normally the sparsest representation is preferred for simplicity and easy interpretability. A good analog is the English language where the dictionary is the collection of all words (prototype signals) and sentences (signals) are short and concise combinations of words. In this lecture, we will introduce the problem of dictionary learning, its origin and applications, and existing solutions.
References
- E. Candès and M. Wakin, An introduction to compressive sampling, IEEE Signal Processing Magazine 25 (2008), no. 2, 21–30.
- E. J. Candès, Y. C. Eldar, D. Needell, and P. Randall, Compressed sensing with coherent and redundant dictionaries, Appl. Comput. Harmon. Anal. 31 (2010), no. 1, 59–73.
- A. M. Bruckstein, D. L. Donoho, and M. Elad, From sparse solutions of systems of equations to sparse modeling of signals and images, SIAM Review 51 (2009), no. 1, 34–81.
- J. Mairal, F. Bach, J. Ponce, and G. Sapiro, Online learning for matrix factorization and sparse coding, Journal of Machine Learning Research 11 (2010), 19–60.
- W. K. Allard, G. Chen, and M. Maggioni, Multiscale geometric methods for data sets II: Geometric multiresolution analysis, Appl. Comput. Harmon. Anal. 32 (2012), no. 3, 435–462. http://arxiv.org/pdf/1105.4924v3.pdf.
- R. Rubinstein, T. Peleg, and M. Elad, Analysis K-SVD: A dictionary-learning algorithm for the analysis sparse model, IEEE Trans. Signal Processing 61 (2013), no. 3.
Unit Norm Tight Frames in Finite-Dimensional Spaces
Dustin G. Mixon, Air Force Institute of Technology.
Finite unit norm tight frames (FUNTFs) are one of the most fundamental objects in frame theory. A FUNTF can be efficiently described as the collection of columns of a matrix whose rows are orthogonal with equal norm and whose columns each have unit norm. The purpose of this lecture is to introduce and develop a working understanding of FUNTFs in three different ways:
(i) Describe a variety of applications of FUNTFs.
(ii) Develop an intuition for the frame potential and the “physical” behavior of FUNTFs.
(iii) Introduce the theory of eigensteps to construct all FUNTFs.
References
- John J. Benedetto, Matthew Fickus, Finite normalized tight frames, Adv. Comput. Math. 18 (2003), 357–385.
- Jameson Cahill, Matthew Fickus, Dustin G. Mixon, Miriam J. Poteet, Nate Strawn, Constructing finite frames of a given spectrum and set of lengths, Appl. Comput. Harmon. Anal. 35 (2013), 52–73.
- Jameson Cahill, Dustin G. Mixon, Nate Strawn, Connectivity and irreducibility of algebraic varieties of finite unit norm tight frames, Available online: arXiv:1311.4748
- Matthew Fickus, Dustin G. Mixon, Miriam J. Poteet, Frame completions for optimally robust reconstruction, Proc. SPIE 8138, Wavelets and Sparsity XIV (2011), 81380Q.
- Matthew Fickus, Dustin G. Mixon, Miriam Poteet, Nate Strawn, Constructing all self-adjoint matrices with prescribed spectrum and diagonal, Adv. Comput. Math. 39 (2013), 585–609.
Preconditioning Techniques in Frame Theory and Probabilistic Frames
Kasso A. Okoudjou, Norbert Wiener Center, Department of Mathematics, University of Maryland, College Park.
The recently developed algebro-geometric methods for constructing FUNTFs are not effective when extra constraints on the FUNTFs are added. It is therefore desirable to have generic methods that would allow one to transform a frame into a tight one. These methods will be analogs of preconditioning methods prevalent in numerical linear algebra. Recently, various techniques have been used to describe a class of frames called scalable frames which have the property that their frame vectors can be rescaled to result in tight frames. In the first part of this lecture, we shall (1) describe the class of scalable frames using some convex geometry tools; (2) provide another geometric formulation of scalable frames based on Fritz John ellipsoid theorem.
Frames are intrinsically defined through their spanning properties. However, in real euclidean spaces, they can also be viewed as distributions of point masses. In this context, the notion of probabilistic frames was introduced as a class of probability measures with finite second moment and whose support spans the entire space. This notion is a special case of continuous frames for Hilbert spaces that has applications in quantum computing. In the second part of the lecture, we shall introduce a probabilistic interpretation of frames, and use this framework to: (1) define probabilistic frames as a generalization of frames and as a subclass of continuous; (2) investigate the minimizers of the frame potential and certain of its generalization in this probabilistic setting.
References
- X. Chen, G. Kutyniok, K. A. Okoudjou, F. Philipp, and R. Wang, Measures of scalability, arXiv:1406.2137.
- G. Kutyniok, K. A. Okoudjou, F. Philipp, and K. E. Tuley, Scalable frames, Linear Algebra Appl 438 (2013), 2225–2238. arXiv:1204.1880
- G. Kutyniok, K. A. Okoudjou, and F. Philipp, Scalable frames and convex geometry, Contemp. Math. 345, Amer. Math. Soc., Providence, RI, to appear. (arXiv:1310.8107)
- M. Ehler and K. A. Okoudjou, Probabilistic frames: An overview, in: “Finite Frames,” Applied and Numerical Harmonic Analysis, (2013), 415–436, Eds: P. Casazza and G. Kutyniok, Birkhaüser. arXiv:1108.2169
- M. Ehler and K. A. Okoudjou, Minimization of the probabilistic p-frame potential, J. Statist. Plann. Inference 142 (2012), no. 3, 645-659. arXiv:1101.0140
Quantization for Finite Frames
Alexander M. Powell, Vanderbilt University
Frames are a tool for providing stable and robust signal representations in a wide variety of pure and applied settings. Frame theory uses a set of frame vectors to discretely represent a signal in terms of its frame coefficients. Frame expansions and dual frames allow one to reconstruct a signal from its frame coefficients--the use of redundant or overcomplete frames ensures that this process is robust against noise and other forms of data loss. Although frame expansions provide discrete signal decompositions, the frame coefficients generally take on a continuous range of values and must also undergo a lossy step to discretize their amplitudes so that they become amenable to digital processing and storage. This analog-to-digital conversion step is known as quantization. We shall give an introduction to quantization for finite frames, with particular emphasis on the class of Sigma-Delta algorithms and the role of non-canonical dual frame reconstruction.
References
- J. J. Benedetto, A.M. Powell and Ö. Yilmaz, Sigma-Delta $(\Sigma\Delta)$ quantization and finite frames. IEEE Transactions on Information Theory, 52 (2006), no. 5, 1990-2005.
- I. Daubechies and R. DeVore, Approximating a bandlimited function using very coarsely quantized data: a family of stable sigma-delta modulators of arbitrary order. Annals of Mathematics, 158 (2003), no. 2, 679-710.
- J. Blum, M. Lammers, A.M. Powell and Ö. Yilmaz, Sobolev duals in frame theory and sigma-delta quantization. Journal of Fourier Analysis and Applications, 16 (2010), no. 5, 365-381.
- C.S. Güuntürk, M. Lammers, A.M. Powell, R. Saab and Ö. Yilmaz, Sobolev duals for random frames and sigma-delta quantization of compressed sensing measurements. Foundations of Computational Mathematics, 13 (2013), no. 1, 1-36.
- A.M. Powell, R. Saab and Ö. Yilmaz, Quantization and finite frames. In "Finite frames", 267-302, Applied and Numerical Harmonic Analysis, Birkhäuser/Springer, New York, 2013.
Algebro-Geometric Techniques and Geometric Insights for Finite Frames
Nate Strawn, Duke University.
The finite unit norm tight frames (FUNTFs) have a rich geometric structure that can be exploited to carry out dictionary optimization for various applications. Algebraically, FUNTFs are quadratic varieties. Geometrically, the FUNTFs lie in the intersection of a product of spheres and a Stiefel manifold. The interplay between these two perspectives illuminates the structure of the FUNTF spaces.
This goal of this lecture is to answer five important questions about the FUNTF varieties:
(1) What are the singular points?
(2) When is the FUNTF variety a manifold?
(3) What are the tangent spaces at the nonsingular points?
(4) Using elimination theory, can the system of defining quadratic equations be solved explicitly?
(5) Are the FUNTF varieties irreducible?
During the course of this lecture, we’ll carry out a series of examples to answers these questions.
References
- D. Mixon, J. Cahill,and N. Strawn, Connectivity and irreducibility of algebraic varieties of finite unit norm tight frames. Preprint.
- J. Cahill and N. Strawn. Algebraic geometry and finite frames. In Finite Frame Theory, P. G. Casazza and G. Kutyniok (eds.), Birkhäuser, Boston, 2012.
- N. Strawn, Finite frame varieties: Nonsingular points, tangent spaces, and explicit local parameterizations, J. Four. Anal. Appl. 17(5):821–853, 2011.
Registration
There are separate fees to register for this Short Course. Advance registration fees for members are US\$108; nonmembers are US\$160; and students/unemployed or emeritus members are US\$52. These fees are in effect until December 23, 2014. If you choose to register onsite, the fees for members are US\$142; nonmembers are US\$190; and students/unemployed or emeritus members are US\$77. Advance registration is open now. The on-site Registration Desk for this short course will be located outside meeting Room 212 in the center, on Thursday (1/8/15) from 7:30 a.m. - noon.