# American Mathematical Society

 Publications Meetings The Profession Membership Programs Math Samplings Policy and Advocacy In the News About the AMS
Information for
Member Journals

 You are here: Home > Meetings > Short Courses

# AMS Short Courses

## 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. 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

1. R. Balan, P. Casazza, D. Edidin, On signal reconstruction without phase, Appl. Comput. Harmon. Anal. 20 (2006), 345–356.
2. R. Balan, Reconstruction of Signals from Magnitudes of Redundant Representations: The Complex Case, arXiv:1304.1839v1[math.FA] 6, April 2013.
3. E. Candè s, T. Strohmer, V. Voroninski, PhaseLift: Exact and stable signal recovery from magnitude measurements via convex programming, Comm. Pure and App. Math6, no. 8, (2013), 1241–1274.

### Construction of Finite Frames with Optimal Ambiguity Function Behavior

John J. Benedetto, Norbert Weiner Center, Department of Mathematics, University of Maryland, College Park.

The $N \times N$ normalized Discrete Fourier Transform (DFT) matrix $D_N = (1/\sqrt{N})(e^{2\pi i mn/N})$ gives rise to equal norm tight frames for ${\mathbb C}^d,$ where $d \leq N$ and the particular frame is characterized by the specific $d$ columns of $D_N$ which are chosen. In fact, the norm of each frame element is $(d/N)^{1/2}$ and the frame constant is $1.$ Clearly, this frame is an orthonormal basis for ${\mathbb C}^d$ in the case $d=N.$ $D_N$ is a special case of an $N \times N$ complex Hadamard matrix $H = H_N = (1/\sqrt{N})(h_{m,n}),$ defined by the properties of constant amplitude, i.e., each $|h_{m,n}| = 1/\sqrt{N}$, and orthonormality (unitarity), i.e., $HH^{*} = {\mathbb I},$ the identity, where $H^{*}$ is the Hermitian transpose of $H.$

Let $x \colon {\mathbb Z} / N {\mathbb Z} \longrightarrow {\mathbb C},$ and define the discrete narrow band ambiguity function, $A(x)(m,n),$ of $x$ as $$A(x)(m,n) = \sum_{k=0}^{N-1} x[m + k]\,\overline{x[k]}\, e^{-2\pi i kn/N},$$ and the autocorrelation of $x$ on ${\mathbb Z}/N{\mathbb Z}$ as $A(x)(m, 0).$ These notions are central to applications such as communications and radar, see, e.g., [3], as well as a host of other applications ranging from pure mathematics to physics to statistics.

Now, let $H_x$ be the circulant matrix with first row, $x = (x[0], x[1], \dotsb , x[N-1]).$ We shall say that $x$ is a constant amplitude zero autocorrelation (CAZAC) sequence if each $|x[n]| = 1/\sqrt{N}$ and if $A(x)(m,0) = 0$ on ${\mathbb Z}/N{\mathbb Z} \setminus \{0\}.$ It is elementary to prove that $x$ is a CAZAC sequence if and only if $H_x$ is a Hadamard matrix.

In this context, it is of interest to construct CAZAC sequences, e.g. [2], to construct "CAZAC frames" analogous to DFT frames, and to find optimal ambiguity function bounds associated with CAZAC sequences using classical Welch bound estimates as a guideline. We shall make such constructions and shall see the role played by algebraic number theory, e.g., the Riemann hypothesis for finite fields (see [1]), and algebraic geometry in making such constructions. We shall give a state of the art overview of the subject and list some open problems. We shall also integrate this material into the matter of analyzing finite Gabor frames with CAZAC generating functions. This provides background for a critical comparison of such deterministic frames with the probabilistic frames arising in compressive sensing.

### References

1. John J. Benedetto, Robert L. Benedetto, and Joseph T. Woodworth, Optimal ambiguity functions and Weil's exponential sum bound, Journal of Fourier Analysis and Applications 18 (2012), no. 3, 471–487.
2. John J. Benedetto and Jeffrey J. Donatelli, Ambiguity function and frame theoretic properties of periodic zero autocorrelation waveforms, IEEE J. Special Topics Signal Processing 1 (2007), 6–20.
3. Nadav Levanon and Eli Mozeson, Radar Signals, Wiley Interscience, IEE Press, 2004.

### 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

1. P. G. Casazza, The art of frame theory, Taiwanese Journal of Math 4, No. 2, (2000), 129–201.
2. P. G. Casazza and G. Kutyniok (eds.), Finite Frames: Theory and Applications, Birkhauser, Boston, 2012.
3. O. Christensen, An Introduction to Frames and Riesz Bases, Applied and Numerical Harmonic Analysis, Birkhauser, Boston, 2001.

### A Primer on Finite Unit Norm Tight Frames

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

1. John J. Benedetto, Matthew Fickus, Finite normalized tight frames, Adv. Comput. Math. 18 (2003), 357–385.
2. 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.
3. Jameson Cahill, Dustin G. Mixon, Nate Strawn, Connectivity and irreducibility of algebraic varieties of finite unit norm tight frames, Available online: arXiv:1311.4748
4. Matthew Fickus, Dustin G. Mixon, Miriam J. Poteet, Frame completions for optimally robust reconstruction, Proc. SPIE 8138, Wavelets and Sparsity XIV (2011), 81380Q.
5. 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.

### 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

1. E. Candès and M. Wakin, An introduction to compressive sampling, IEEE Signal Processing Magazine 25 (2008), no. 2, 21–30.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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.

### 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

1. X. Chen, G. Kutyniok, K. A. Okoudjou, F. Philipp, and R. Wang, Measures of scalability, arXiv:1406.2137.
2. G. Kutyniok, K. A. Okoudjou, F. Philipp, and K. E. Tuley, Scalable frames, Linear Algebra Appl 438 (2013), 2225–2238. arXiv:1204.1880
3. 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)
4. 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
5. 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

### 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

1. D. Mixon, J. Cahill,and N. Strawn, Connectivity and irreducibility of algebraic varieties of finite unit norm tight frames. Preprint.
2. 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.
3. 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 starts on September 2, 2014. Onsite registration will take place on Thursday, January 8, at a location to be announced.