Ingrid Daubechies - US grants

Wavelets are families of functions generated from one single function (or, in higher dimensions, from a finite set of functions) by dilations and translations. Particularly interesting are discrete families of wavelets that span all of L2(Rn), and lead to numerically stable decomposition + reconstruction algorithms. Such families can either be redundant (frames) or not (bases). For certain frames or bases of wavelets, there exist easily implementable, elegant tree- algorithms for the numerical computation of decomposition coefficients. Dr. Daubechies will investigate how these can be used to solve wave equations numerically. Wavelets seem very promising for this purpose for both theoretical and practical reasons, since they are inherently a tool for microlocalization and have been used as such in singular integral problems, while they also incorporate the idea of different scales and "zoom-in" on singularities, similar to refining grid techniques in numerical analysis. A successful use of wavelets for this purpose would lead to better orientation specificity than is available in presently used numerical techniques. The interactive activities involve teaching a graduate course and participating in seminars. This project furthers VPW program objectives which are (1) to provide opportunities for women to advance their careers in engineering and in the disciplines of science supported by NSF and (2) to encourage women to pursue careers in science and engineering by providing greater visibility for women scientists and engineers employed in industry, government, and academic institutions. By encouraging the participation of women in science, it is a valuable investment in the Nation's future scientific vitality.

Wavelet analysis is based on the existence of single functions whose dilations and translates form bases for function spaces used in various areas of mathematics. The theory as developed over the past decade has proved its worth through important applications to problems in signal processing, data compression, and seismic exploration, to name a few. The advantages of wavelet decompositions of functions over more traditional harmonic analysis techniques lies in the ability of properly chosen wavelets to remain local in time and frequency: a function and its Fourier transform have representations whose coefficients depend only on the values of the function in small neighborhoods distributed throughout space. Most wavelet analysis focuses on the representation or approximation of functions defined on the entire line or throughout space. There is a need to develop wavelet analyses for functions restricted to intervals. That is one of the primary goals of this project. One cannot take a wavelet theory and simply restrict it to an interval. The end points create obstacles which preclude the use of a single wavelet. At issue then is how efficiently can a wavelet theory be built on intervals in the sense of using the minimal number of auxiliary functions and maintaining the same qualities of the wavelet theory. One drawback of wavelets is their lack of symmetry. This shortcoming can be overcome by using a construction of dual Riesz bases of symmetric wavelets (one forfeits the use of a single wavelet to do all the work and replaces it by two). The adaptation of wavelets to finite intervals also opens the possibility for the construction of dual bases in this context. Very little work has been done in this direction to date, although applications to image processing appear to be very promising. One simple approach to this dual basis construction is to consider truncations of existing infinitely supported wavelets used in various applications and truncating them. These may provide interesting dual bases but they will only be of value if their conditioning numbers can be held close to unity. Work will be done investigating various examples.

Daubechies 9401785 Work supported by this award focuses on the mathematical development of wavelet analysis and its applications. This is a branch of harmonic analysis closely allied with applications to many areas of science. The underlying goals of wavelet analysis are (i) to determine functions whose integer translates and dyadic dilates form orthogonal (or biorthogonal) bases for square-integrable functions (ii) to ensure that the basis elements localize both time and frequency and (iii) that they have the requisite smoothness dictated by the problem. Normally, wavelets are also expected to have compact support. In this project five goals are to be addressed. They include analysis of the smoothness of infinitely supported wavelets, the construction of redundant families of analytic wavelets associated with a multiresolution analysis and a study of the consequences of truncating wavelet filter coefficients and finding ways of doing the trunction in a stable manner. Work will also be done in applying wavelets, with new filters, and a new nonlinear squeezing technique, to speech analysis. Finally, effort will be made to construct a special family of multifractal functions for which the so-called thermodynamic formalism can be verified explicitly, and which can be used as a mathematical laboratory. The theory of wavelets, as it has become known, is actually a body of ideas which has developed dramatically over the past decade, following several important discoveries by physicists, computer scientists and engineers concerned with signal processing and data compression. It evolved into a synthesis of many existing techniques into a framework which offers possibilities for improved applications and challenging mathematical ideas which will require years to reach what might be considered a mature stage. Many areas of science are now adapting wavelet constructs to important problems currently under investigation. These included statisticians lo oking for patterns in large data sets, compression of fingerprint data, edge reconstruction of images and the generation of fractal sets with prescribed characteristics.

Daubechies ABSTRACT Daubechies will concentrate on several aspects of wavelet algorithms and their applications: a) Riesz bases of wavelets on the sphere: Recent constructions of wavelet algorithms on the sphere lead to good numerical performance; so far no proof exists that they correspond to Riesz bases for the square integrable functions on the sphere. Traditional methods for planar constructions exploit translational invariance, absent for triangulations on the sphere. b) Irregular subdivision schemes construct curves or surfaces from irregular grids, placing new grid points in positions that are not equally spaced (even locally) as the grids are refined. Similar to the equally spaced case, preservation of polynomial behavior plays an important role in determining the smoothness of the limit curve or surface. Such irregular subdivision schemes are being explored. c) Approaches to decompose wavelet filters into elementary matrices in an efficient manner, and possibly using only integers. d) Frames of wavelets can be used for multiplexing of signals, similar to CDMA, as well as for sending information efficiently over multiple channels. e) The role of smart coding strategies in realizing the full potential of wavelet-based nonlinear approximation theorems. Wavelets are a mathematical technique that allows us to view a complex structure as consisting of several, increasingly detailed layers. This "multi-resolution analysis" is analogous to viewing a painting from a distance, where only large features can be distinguished, and then, as we approach closer, perceiving more detailed, smaller features, until, when we are very close, we can detect even individual brush strokes. As a mathematical tool that has this potential to "fill in" detail at increasingly small scales, and only where needed, wavelets have turned out to be useful in computer aided graphic design, in image and data compression, and in mathematical analysis and numerical computation, in particular for composite materials. Several of the mathematical problems in this proposal are inspired by such applications of wavelets, and their solutions will widen the scope of settings in which we can use multi-resolution analysis.

Princeton VIGRE program - Abstract. General Philosophy. The VIGRE program at Princeton is a joint venture of the Mathematics Department and the Program in Applied and Computational Mathematics (PACM); it aims at exposing undergraduate students, graduate students, and postdoctoral fellows to a broader research and teaching experience. On top of disciplinary depth, we want to foster educational exploration and breadth-qualities that are increasingly important in the current rapidly changing research world and job market. It is more important than ever to prepare students and postdoctoral fellows for a variety of different teaching tasks and research opportunities. Whether they proceed to academic or non-academic careers, all student and postdoctoral fellows will benefit from experience in teaching and exposition, and from contacts with the mathematical world at other institutions and outside academia. The different components. Our VIGRE program has components that pertain to graduate training, to undergraduate education, to postdoctoral fellowships, to curriculum innovation, and to outreach activities. Several components are vertically integrated and have aspects that fit under several headings. For most initiatives, we do not distinguish between Mathematics and PACM students, postdocs, or faculty: the VIGRE program will draw on and combine the strengths of the two programs. 2A Graduate training. Mathematics, as perceived by graduate students through the filter of most graduate educations, has become increasingly fragmented. This is the case for virtually all disciplines within mathematics, regardless of how "pure" or "applied" they are. Integration of the different components encountered during graduate education into a more global view is typically left to postdoctoral studies. In our program we want to coordinate initiatives that will help launch our graduate students into their research and teaching careers, exposing them to a broader view of mathematics and its application s. All students, whether VIGRE supported or not, will be encouraged to participate in these activities. Some of the activities will be required for VIGRE students. We shall run research seminars aimed at graduate students, featuring expository presentations (by faculty members, visitors or graduate students) about open problems, often related to applications. In a companion problem seminar, interested graduate students will work on open problems (typically more complex than a homework problem but not a thesis-size problem); they will be invited to present their results to the research seminar. This initiative has started already with an Analysis and Application series, and can be extended to other fields. Every Fall, we shall bring non-academic mathematicians (e.g. from industrial research labs, from government organizations, and from the financial world) to Princeton for a series of presentations, aimed at our graduate and advanced undergraduate students, about mathematics outside academia. We shall encourage students to do at least one internship (probably but not necessarily during the summer) in another environment, during their graduate studies. We shall put together a "portfolio" of such opportunities, and continue to work on updating it and adding new possibilities. VIGRE students will spend at least one summer internship or another extended visit at another research institute, academic or not. Where appropriate, we shall involve graduate students in "partnerships in research" with individual research labs. Such collaborations will typically start with work on a mini-project, leading to a publication after completion, as well as a presentation at the research seminar series mentioned above. In some cases, these projects could grow into Ph.D. theses. A student colloquium committee, consisting of graduate students together with an undergraduate representation, will organize expository talks, aimed at students, in which speakers can be faculty or outsiders, or students ; the committee will be given the means to invite outside speakers known for their expository skills. Every week during the term there will be at least one student speaker and at least one faculty or visiting speaker, invited by this committee. Graduate students will be involved in the development of new courses and course material for undergraduates (see also below). VIGRE supported students will teach one precept of a course for at least one full semester during their training. 2B Undergraduate education. Participation in the student-run expository talks series (see above). Internships in non-academic mathematical environments, similar to the graduate internships (and in some cases, coupled to them) will be encouraged strongly, and a portfolio of opportunities will be put together. We shall set up an undergraduate laboratory in mathematics for math majors, with involvement by graduate students and faculty. We shall collect a database of problems and conjectures which are mathematically interesting and (with modest background and machines) amenable to numerical experimentation and scientific examination. The undergraduate project (which could be used for one of the two required junior papers, or, if more substantial, for the senior thesis) would be to examine experimentally (i.e., numerically) some phenomenon; students will be encouraged to probe further on their own, as well as to try their hand at proving special cases. This will lead them to experience the thrill of discovery (as well as the agony of defeat, part of research as well!). Experience in oral presentation: students enrolled in the PACM undergraduate certificate program will make a presentation about their independent work to the weekly PACM certificate seminar; these presentations are first rehearsed and edited with PACM graduate students. Math majors will be encouraged to make a similar presentation (about their senior thesis, or possibly about a summer research experience or a project in the undergraduate lab) to the student-run expository talks series. 2C Postdoctoral Fellowships. VIGRE postdocs will be encouraged to visit another institute during one term of their fellowships, possibly with other funding (e.g. GOALI). Postdoctoral fellows will be called upon to contribute substantially to course development (see below), and will be encouraged to participate in the teaching of innovative undergraduate courses. VIGRE postdoctoral fellows will be given the opportunity to teach graduate courses: either advanced courses in their own specialty, or, if they are interested, introducing graduate courses. 2D Curriculum and development and review. We want to develop and enhance new courses in mathematics that broaden and integrate. The following are a few examples. We expect to develop others as well: New modules for Math Alive: This course was developed to explain the importance of mathematics in our society by pointing at concrete objects or issues and probing into the underlying mathematical ideas and concepts; it is aimed at students who will not major in mathematics, science, or engineering. The course is organized in largely independent two-week modules; for presently existing modules see http://www.princeton.edu/~matalive/. We want to develop new modules with other themes. We will also develop a similar course tailored to the greater mathematical experience and skills of math majors; this course will be structured again in (fewer) modules, but it will explore each in greater depth. We also want to develop an integrated analysis course that will cover several semesters. It will integrate and closely interrelate several fields, such as partial differential equations, harmonic analysis, real and complex analysis, analytic number theory and probability theory. This course will be primarily directed to third- and fourth-year undergraduate majors and b

An interdisciplinary team, bridging academia and industry, proposes a united effort to study the dynamics of the global Internet, moving beyond the traditional single-timescale, single-network, single-protocol paradigm to a description that compactly incorporates a wide range of time-scales, a broad spectrum of spatial network topology structures, andmultiple protocols interacting with one another and across the different networking layers. Achieving such a global, multi-scale, and multi-layer understanding of complex large-scale networks is imperative for the successful design and development of the next-generation Internet protocols and engineering tools, where issues related to robustness,scalability, and efficiency take center stage.
In this united effort, there are three main ingredients. First, the researchers plan to fully exploit a new breed of datasets of network-wide measurements - unprecedented in volume and quality - that are the result of recent exciting networking research projects, such as the National Internet Measurement Infrastructure project (NIMI). Another source of such data will be various Internet Service Providers (ISPs), such as AT&T, employer of one of the PIs, which will also provide supplementary funding if this proposal is accepted. Second, the researchers will rely on a new breed of network simulation tools, such as SSFNET, largely developed by another of our PIs, and capable of simulating internetworks unprecedented in scale and detail. All these new measurements, whether real or virtual, will constitute huge datasets with very high and networking-specific semantic content, creating completely novel challenges for data analysis. This is where the third ingredient comes in: multiscale and multiresolution/wavelet techniques, developed by several of the PIs, will take center stage when it comes to analyzing, visualizing, and uncovering the rich information that is contained in these network measurements. Although the flexibility and the speed of wavelet decompositions have been put to good use in the past in many applications, including the empirical observation of certain types of time-scaling behaviors in measured network traffic, the technology as it is known and used today cannot yet cope with the fascinating new challenges posed by the available and anticipated Internet data. A central objective of this project is to develop Internet-appropriate multiresolution techniques that match the multiscale nature of the underlying Internet structure and can be validated step-by-step against measurements. The researchers expect that tools and theories that have been developed in the context of computer graphics, irregular sampling, and scattered data approximation will be utilized to this end.
The ultimate goal of the proposed research effort is to identify interesting patterns that can be extracted from the measured data via fast algorithms, that are linked to physical concepts and are meaningful in the networking context, that characterize different states or behaviors of the network, and that can aid the development of novel network measurement analysis and visualization techniques in support of a new generation of monitoring and engineering tools for future Internet architectures. Given that so much of this area is still uncharted, it may be not realistic to hope to attain this goal in a few years' time. Nevertheless, we are convinced that only an interdisciplinary effort like ours can hope to achieve anything in this direction; we expect that our collaboration will lead to deeper insights and understanding; a first identification of models, patterns, the influences of various external factors and protocols; and an initial glimpse at the underlying "physics of the Internet" - a solid understanding of how basic networking mechanisms and user behaviors contribute to the fascinating dynamic observed in today's Internet.

Abstract


A detailed mathematical study will be undertaken of so-called "Sigma-Delta"
conversion schemes, which use simple and easily implementable algorithms to represent bandlimited functions by one-bit sequences; convolving such a one-bit sequence with an appropriately chosen filter leads to an approximation of the original bandlimited function. Different schemes, corresponding to different approximation orders, will be studied in detail; we expect the mathematical insights gained will lead to new variants that have better mathematical properties, and to generalizations to other settings than the
approximation of bandlimited functions.

Analog-to-digital and digital-to-analog conversion, present in a wide range of
applications, some familiar to all of us (e.g., CD players), others more confined to the field of scientific instrumentation, makes use of schemes that start by taking highly redundant information, and then replacing it by one-bit or few-bit sequences, from which the original information can be reconstituted with good precision. Because of the physical constraints in these conversions, the schemes used in practice have very interesting mathematical properties, quite different from the standard representation of numbers by a decimal or binary notation. It is proposed to study these properties in more detail, with the goal of proposing variants on the schemes, and to identify a wider range of applications for these conversion schemes.

The aim is to provide a better mathematical framework and
alternative design methodologies for coarse quantization of signals in
a highly oversampled setting. The central themes is "sigma-delta
quantization" in analog-to-digital conversion of audio signals and its
counterpart "error-diffusion" in digital halftoning of images. In both
cases, a given target analog signal is represented by a judiciously
chosen one-bit (or few-bit) sequence which approximates the signal in a
suitable low-pass subspace. A wide range of different schemes exist for
this purpose, each corresponding to a different implementation and
approximation order. As our primary mathematical objective, we expect
to better understand the law of error decay of the existing schemes as
well as to improve on these by new designs. On the algorithmic side, we
aim to extend this analysis to settings with computational and other
implementational constraints.

The fact that digital signals and data sets can be processed, stored
and retrieved with great precision and speed places high demands of
accuracy on the conversion process from and to the analog world.
However, the devices used in the translation process (such as in the
case of analog-to-digital and digital-to-analog conversion circuits in
audio applications, and printers in image reproduction) are of
necessity analog devices, which have physical limitations that, at
first sight, conflict with those accuracy demands. To cope with this
problem, engineers have empirically developed special signal processing
techniques leading to alternative signal and number representations
that are quite different from standard decimal or binary
representations. Typical techniques take advantage of the highly
accurate performance of the analog devices in sampling very densely in
time or space to compensate for the lack of amplitude precision of
those devices. Interestingly, while these empirical schemes have proved
efficient and have been used in consumer products for a long time, the
corresponding framework of signal processing has little mathematical
support. We aim to study these schemes in more detail, with the
goals of improving the mathematical theory as well as proposing
variants that outperform those used presently, and to identify a wider
range of applications.

[unreadable] DESCRIPTION (provided by applicant): Available methods of analysis for functional Magnetic Resonance Imaging offer a wealth of possibilities to researchers using this neuroimaging modality. However, these tools suffer from the inherent low signal to noise ratio of the data, and from the limitations of widely used model-based approaches. These problems have been addressed by the community and the literature now describes numerous methods that can remove part of the noise and extract brain activity pattern in a data-driven fashion. This project focuses on the design of optimized algorithms for the estimation and removal of the noise, on the understanding of the applicability of existing data-driven approaches, and on the development of new blind source separation methods for fMRI data. Particular attention will be given to quantification of the gains provided by the newly proposed methods by working on simulated datasets and specifically designed fMRI experiments. The first specific aim is to use a spatio-temporal four-dimensional multiresolution analysis to define an "'ideal denoising" scheme for a given study. It will make extensive use of the concept of best wavelet packet basis, which allows the most efficient representation of a signal. The concept wilt first be validated on fMRI rest datasets, and its efficiency will then be measured on simulated and actual data. The second specific aim focuses on blind source separation methods. An in depth study of Independent Component Analysis will be carried out to precisely define its field of applicability on fMRI data. By using sparsity together with time-frequency methods, we will develop new source separation algorithms and will demonstrate their robustness on both simulated and real data.

The investigators address the mathematical underpinnings of compressing large data sets using sparse representations over rich dictionaries and develop a foundation for classifying these problems in terms of their algorithmic complexity. The investigators also find efficient algorithms for computing high-quality sparse representations of data over sophisticated, commonly used dictionaries that provably perform as claimed with respect to both efficiency and correctness of output and are particularly well-suited for massive data set applications. The research proceeds at multiple levels of abstraction. It considers general factors of a representation class that guarantee or preclude such algorithms, it considers algorithms for specific common representation classes, and it finds algorithms for representation classes adapted to specific common (and diverse) applications, such as solutions of partial differential equations, image processing, and database query optimization.

Over the past ten years there has been a dramatic increase in data gathering mechanisms, as well as an ever-increasing demand for finer data analysis in applications that rely on scientific and geometric modeling. Each day, literally millions of large data sets are generated in medical imaging, surveillance, and scientific acquisition. In addition, the internet has become a communication medium with vast capacity, generating massive traffic data sets. The usefulness of these data sets rests on our ability to process them efficiently, whether it be for storage, transmission, visual display, fast on-line graphical query, correlation, or registration against data from other modalities. The current state of the art in data processing is far from providing the efficient and faithful representations required in emerging applications. With few exceptions, previous work has not provided algorithms whose efficiency or output quality, though typically validated experimentally, has been analyzed rigorously and thoroughly. The investigators carry out fundamental mathematical and algorithmic research to significantly increase our capacity to process and manage large data sets. The research makes significant mathematical progress in providing rigorous algorithmic results that are of great need in this field. The research also makes significant improvements through highly efficient algorithms in the sizes of data sets that are analyzable and in the types of data processing tasks that can be carried out. Finally, the investigators create a library of software for massive data processing applications.

The Department of Mathematics and Program in Applied and Computational Mathematics proposes to purchase a computational cluster which will be dedicated to support computational research in mathematical sciences. This research will be concentrated in particular in the following areas: (1) new algorithms for the separation of independent components in magnetic imaging data to study brain function, (2) the dynamics of how bio-molecules acquire and move between different conformations, (3) study of the analytic rank in connection with the Goldfeld conjecture on elliptic curves (a well-known conjecture in number theory), and (4) computer-assisted enumeration of cusped hyperbolic 3-manifolds.

Each of these projects require dedicated facilities that Fine Hall does not have currently. From a scientific and educational point of view, the proposed projects lie at the interfaces between different disciplines: signal processing, statistics and psychology for the fMRI project; applied mathematics and biochemistry for the second project; topology and geometry for the 3-manifold project. Progress on these projects will impact several communities. In addition, these projects will be part of the PIs' continuing effort on bringing frontier research to science education in the classrooms, as well as attracting women and other under-represented groups to the area of mathematics. New courses and discussion sessions will be organized so that a much larger part of the mathematical and scientific community will have access to these research projects through the proposed facility.

The project concerns the application of various so-called time-frequency (although in this context rather spatial localization/spatial frequency) techniques to seismic tomography, in order to capture both broad, smooth features and well-localized abrupt transitions or spiky features. In a first stage, the PIs plan to make a careful, stepwise study of the mathematical intricacies of the problem. They will construct appropriate wavelets or wavelet-like bases, and take advantage of the presently emerging understanding of how to characterize effectively data or structures that are sparse with respect to these bases. They expect that recent mathematical progress that shows simple, non-adaptive methods can give results comparable to fancier, adaptive techniques, at the cost of a logarithmic factor in the "size" of the problem, will help them in building a good approach in the next stage of the project, to attack first the direct, and then the inverse problem. In a second stage they hope to couple this with the ultrafast algorithms that are being developed by Gilbert, Muthukrishnan, Strauss and co-workers, and/or with the graph-diffusion technique and the associated multiresolution structure developed by Coifman, Laffont and Maggioni. The new techniques will be applied in ongoing global seismic tomography research projects as they are developed. Finally, they will develop the integral kernels for the inversion of seismic waveforms (as opposed to travel times) into a condensed wavelet basis. This is a crucial step in the partitioning of the three-dimensional problem of waveform tomography. It should allow them to split the (unmanageably) large and nonlinear inverse problem for N seismograms into N nonlinear optimization problems of manageable size.

In seismic tomography, geophysicists seek to obtain information about hidden features of the Earth from a mathematical study of seismic waves excited by earthquakes or explosions, and recorded by a network of seismographs. This is to some extent similar to the more familiar CAT-scan tomography, in which doctors seek information on the inside of the body of a patient by taking transmitted X-ray pictures from many angles. Problems of this nature are called "inverse problems". Another inverse problem is the deblurring of images; for this problem, the wavelet transform, a recently developed mathematical tool, has shown to be particularly well adapted when the object one seeks to "reconstruct" can have sharp boundaries between regions that are otherwise smooth. Structures inside the Earth, such as subducting ocean floors or phase transitions, can likewise have sharp boundaries, whereas other variations in the physical properties may be distributed more smoothly. Wavelet techniques may therefore be particularly useful in seismic tomography as well. However, it is impossible to just transpose the image deblurring techniques to seismic tomography, because of the typically much larger size and greater complexity of the geophysical inverse problems, in which data can not be collected on a nice rectangular grid and large gaps in station coverage usually exist. The whole project will combine cutting edge applied mathematical techniques with new developments in the young field of finite frequency seismic tomography. The PIs expect that this collaboration between geophysical and mathematical investigators will eventually lead to sharper and more accurate images of the Earth's deep structure.

Digital data is the driving force behind much of our modern technology. Cellular phones and compact discs are ubiquitous examples of the need to handle information accurately, efficiently, and robustly. This research addresses these three criteria by introducing finite frames and coarse quantization ideas (providing redundancy and precision, respectively) so that together they minimize information loss in the case of noisy environments and machine imperfections, as well as ensuring numerical stability. The combination of frames and coarse quantization, as envisioned in this research, will generally produce small energy error differences between given signals and their quantized versions, which are constructed by higher order Sigma-Delta recursion schemes. The exceptions to the proposed general theory lead to a host of arithmetic-geometric problems. The technology for the theory requires a careful study of invariant sets closely connected with delicate tilings of Euclidean space. The first order Sigma-Delta analysis by the researchers proves its superiority over pulse code modulation methods for many applications. Further, the error estimates arising in this research will be analyzed in the case of the multidimensional discrete Fourier transform, which is a workhorse in any spectral analysis. In this setting, number theoretic problems, associated with residue number system processors, arise.

A major goal of this research is to develop algorithms that provide reliable transmission of data over so-called erasure channels such as the internet. The methods that we are developing will also be used for multiple antenna code design that will guarantee clear, steady reception of messages in mobile wireless communications. Further, our proposed finite frame Sigma-Delta quantization methodology is a natural component in the emerging multifunction environment technology associated with the unified treatment of radar and communications. A natural application is to reduce a ship's signature in a hostile environment. Other applications of the methods to be developed, especially for the research dealing directly with finite frames, are of a geometric and number theoretic nature. For example, the vertices of the Platonic solids are finite frames with very desirable properties associated with sphere packing problems and spherical codes.

This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5).

Computational Mathematics has been central to the Program in Applied and Computational Mathematics(PACM) since its inception in the mid 1970s. This tradition is rooted in the traditional, in uential and powerful fields of computational fluid dynamics, control theory and operations research, fields in which PACM is committed to continue to invest energy and resources, and in which it is well represented by dynamic and top-level researchers branching out into quantum chemistry, materials science and nanotechnology. Parallel to these traditional computational mathematics elds, recent years have seen exciting new developments in mathematics and computer science, which have opened up new domains of application for computational mathematics. These come with their own challenges, for which new approaches and tools must be and are being developed. Machine learning and compressive sensing are two typical examples; they draw not only from traditional linear-algebra-based numerical analysis or approximation theory, but also from information theory, graph theory, the geometry of Banach spaces, probability theory, and more. This proposal seeks to fund the research of three PACM faculty drawn to these new computational challenges, who are also finding increasingly that their different fields of expertise all contribute to the development of dramatically more effective tools. This contiuence of interests, and the conviction that joining their efforts will produce a whole that exceeds the sum of its parts, constitute the engine that drives the approaches proposed here. The PIs will bring to bear harmonic analysis, combinatorial group theory and statistical data analysis approaches on the construction of algorithms that address large-scale computational problems not yet solved by traditional approaches.


Whereas acquiring a sufficient amount of data used to be the main preoccupation of scientists and engineers, they now often find themselves deluged with massive amounts of often unstructured data, of which much more can be saved than was possible before. Faced with an enormous mass of unstructured, noisy data, the challenge is then to identify and study the hidden structures within the data (often much lower dimensional than the data set itself). This is like searching for needles in haystacks, when one doesn't even know how many (if any!) needles are hidden among the hay. In a very real sense, this is similar to the learning task accomplished by babies, who, in a few years' time, learn to make sense of the overwhelming amount of information provided to them by their senses, and succeed in learning many skills, including language, from identifying the structure in these data. The PIs will study how to discover such hidden structure in several applications. These include the determination of the geometric structure of biological molecules for which standard X-ray Crystallography doesn't work because the substance cannot be crystallized; the study of masters' paintings to learn how to better distinguish original from fakes or copies; the identification of the structure in very large data arrays for which only a small percentage of the entries are known, so that the others can be inferred; the detection of anomalies in internet or other network traffic.

The focus of this project is on inverse problems in seismography.
Inferring undergound structure from seismic measurements is a nonlinear problem that is also notoriously ill-posed. The PIs will tackle this problem in its full nonlinearity via the adjoint method, by iteratively minimizing a variational functional in which, at each iteration step, the nonlinear effects of the approximate solution are fully taken into account for the computations in the next iteration.
To deal with the ill-posedness of the problem, they will use a regularization method that incorporates efficient modeling of spatial distributions that can exhibit discontinuities as well as smooth behavior between discontinuous transitions. More precisely, they will model the distribution as a sparse superposition of wavelets and curvelets, and add the sum of the absolute values of the corresponding expansion coefficients as a penalty term to the variational functional to be minimized. The inclusion of such a term enforces the sparseness of the expansion, thus expressing the smoothness of the model between discontinuous transitions, and has been proved to be regularizing. Computational resources have reached the speed and scale at which it is now feasible to use this approach for realistic problems.

Seismology seeks to gain insight into underground geological structure by measurements done at the surface. When vibrational signals are sent into the ground (whether by earthquakes, carefully tailored explosions or specially constructed vibrators), they propagate at different speeds through layers of different constitution, and are reflected at the often abrupt transitions between different layers. The goal of seismology is to reconstruct the underground structure traversed by these seismic waves from the complex signals, registered by seismographs, that result from the multiple reflections and their interaction. The corresponding numerical problem is of such great complexity that it has been necessary, in the past, to simplify it so as to keep the problem feasible; this led, of necessity, to approximate solutions. The PIs will make use of recent mathematical advances that make it possible to model more effectively heterogeneous underground structures, and of the continuing progress in speed of computational resources to tackle the problem without having to introduce some of the restrictive simplifications used previously. This is expected to result in more accurate maps of underground structure.

The Program for Women and Mathematics is an annual two-week program organized at the Institute for Advanced Study (IAS), co-sponsored by Princeton University. The program takes place each spring and is organized by senior women in mathematics; it centers around a mathematical theme that changes from year-to-year. The participants span different levels; they include undergraduates, graduate students, postdoctoral fellows and senior women. The goals of the program are to enhance the mathematics education of talented women mathematicians through a rigorous and intense academic program, and to retain these women in the field by providing mentoring and by establishing an extensive network of women mathematicians. Program activities include an undergraduate-to-beginning-graduate course in an area related to the research subject of the year, an advanced graduate course, usually divided into two separate short courses, intended to be an introduction to state-of- the-art research in that year's chosen field of mathematics; research seminars in which reports from postdoctoral level participants; problem and review sessions; and women-in-science seminars that include interviews with senior women in the field, panel discussions on topics of interest and organized discussions on subjects which range from how to set up a Noetherian Ring to interviewing for a job.

The Program for Women and Mathematics has been running for more than 15 years. It consistently receives rave reviews. The program is not only praised for its intense scientific curriculum, it is also unique in representing different mathematical professional paths and different stages in such a path. Participants establish strong professional relationships that far outlast the ten-day academic program. The establishment of a network of women at various levels, who can (and do!) support and mentor one another through difficult transition points, has been a well-cultivated outcome of the program, and is something that expands and becomes stronger as the program continues.

SWIM -- Women in Mathematics -- Summer Workshop for High School Students is a 10-day workshop seeking to retain talented female students, and to encourage them to pursue a career in science and mathematics, at the crucial transition point from high school to college. The SWIM program brings together talented students in an intense workshop in which they learn, earlier than is typically the case, advanced mathematical topics, and work on their own research project. It aims to showcase mathematics as a "living discipline", to stimulate the intellectual curiosity of the participants, and to convey enthusiasm for the subject. By bringing together as a group female high school students with a strong talent for mathematics, to study and work together, and introducing them to female role models at further stages in a mathematical career, the SWIM program encourages these students to consider such a mathematical career for themselves.

Participants in the program are predominantly "rising seniors". They are recruited countrywide, and selected on the basis of their mathematical talent. The morning sessions of the workshop consist of two courses, which are more advanced and of a different nature than typical high school courses. In the afternoon, groups of two to three participants work together on small research projects based on the material of the courses. At the end of each afternoon all the participants meet for a "Women in Mathematics" seminar, introducing the participants to a variety of women who chose to pursue a career in mathematics, and discussing a wide range of issues with them. Throughout the workshop the participants interact with undergraduate students, graduate students and faculty of the Mathematics Department; they are housed in one of the colleges on campus and thus get a glimpse of life as an undergraduate student.

In the past decade, the analysis of massive, high-dimensional, time-varying data sets has become a critical issue for a large number of scientists and engineers. Observations across several disciplines, by researchers studying dramatically different problems, suggest the existence of geometrical and topological structures in many data sets, and much current research is devoted to modeling and exploiting these structures to aid in prediction and information extraction. Recent work by the investigators, among others, has shown that integrating statistical methodologies with ideas derived from computational topology and diffusion geometry often leads to strikingly superior results than by conventional means. The investigators now propose to bring these methods into the mathematics/statistics curriculum and departmental structure in a formal way, by establishing a vertically integrated program of undergraduate and graduate research and education. This activity has broad support from programs within the Division of Mathematical Sciences, including Applied Mathematics, Computational Mathematics, Statistics and Topology programs, as well as Division of Mathematical Sciences Workforce Program.
This involves new undergraduate courses in the core theoretical areas, graduate topics courses, an extensive summer research program for undergraduates, as well as year long seminars aimed at both graduate and undergraduate students. In addition, the investigators will disseminate their ideas via summer workshops aimed at small-college faculty, and methodology workshops directed to faculty from other large research institutions.



The need to analyze massive, complex data arises in a wide variety of scientific areas of national importance, including for example satellite image analysis, medical genomics, and internet security.
The investigators propose a program of training future mathematical scientists to attack these new types of problems. The program will be vertically integrated, fostering extensive collaboration between post-docs, undergraduate and graduate students, and senior faculty, and will comprise a dynamic mixture of theoretical coursework and hands-on research activity. Participants in the program will gain valuable professional experience to distinguish them in the industrial and academic job-market.

We will develop novel techniques for the multi-resolution analysis of high-resolution images, to obtain novel efficient and information representations. These representations will take into account natural invariances in images, and will lead to novel dictionary learning constructions and algorithms for images and in signal processing in general. These representations will then be used to analyze, search, and recognize similar objects or features in collections of (scans of) paintings, in particular a large collection by the baroque artist Jan Brueghel. The distances between images and portions thereof, the features learned by the extensions of dictionary learning we will construct, and the associated statistical similarities, together with labels provided by experts to be used to train classifiers and algorithms that learn similarities among items to match those provided by expert, will enable us to enrich the current set of capabilities in building these large networks of paintings, to search through them more easily and with more general search patterns, and to visualize them according to different metrics by using dimensionality reduction techniques.

The automatic learning of templates and patterns, and their statistical relationships, in images and signals in general is crucial in a wide variety of applications, such as automating object recognition, and in defining visually meaningful similarities between images, needed to enable searches in large image databases. We will both develop novel techniques for automatically learning good templates for images, that incorporate natural invariances such as translations and scalings, and novel ways of exploiting these templates for analyzing large collections images, measuring the similarities between then, and finding and characterizing recurrent patterns in them. These novel techniques will be applied to the data on the Jan Brueghel Research site, that allows scholars to investigate and conceptualize a very different notion of old master pictures. Instead of creating absolute categories of genuine and not-genuine, the team will be drawing a map of interconnections between the thousands of paintings produced in the workshops of early modern Antwerp. These pictures were made over several generations, in the shops of masters ranging from world-famous (Pieter Brueghel, Rubens) to utterly obscure. The website will chart how ideas were generated, exchanged, reused and retooled by different artists, mapping networks of creation and production well beyond those traceable through archival documents.

This research project concerns mathematical and algorithmic developments for image analysis (image compression, and the like). To compress or analyze images, it is useful to decompose them into elementary building blocks that are especially effective - in other words, it pays to use mathematical decomposition tools that achieve high accuracy with relatively few coefficients. For instance, in the transition from the JPEG standard to JPEG2000, the wavelet transform replaced the discrete cosine transform because it provided a sparser representation for images and because its performance degrades more gracefully when bandwidth is variable. This project aims to develop methods for improved sparse representation of images.

Curvelets and shearlets constitute a variant on the wavelet approach that can be shown, mathematically, to lead to even sparser representations for images. So far, they have not lived up to this promise in practice -- the only implementations in existence have a high overhead and a large redundancy factor. The Principal Investigator and her collaborators have identified several approaches that they expect will provide better basis constructions, which in turn will give better implementations, with great potential for applications. These will be developed in this project.

Recent advances in deep learning have led to many disruptive technologies: from automatic speech recognition systems, to automated supermarkets, to self-driving cars. However, the complex and large-scale nature of deep networks makes them hard to analyze and, therefore, they are mostly used as black-boxes without formal guarantees on their performance. For example, deep networks provide a self-reported confidence score, but they are frequently inaccurate and uncalibrated, or likely to make large mistakes on rare cases. Moreover, the design of deep networks remains an art and is largely driven by empirical performance on a dataset. As deep learning systems are increasingly employed in our daily lives, it becomes critical to understand if their predictions satisfy certain desired properties. The goal of this NSF-Simons Research Collaboration on the Mathematical and Scientific Foundations of Deep Learning is to develop a mathematical, statistical and computational framework that helps explain the success of current network architectures, understand its pitfalls, and guide the design of novel architectures with guaranteed confidence, robustness, interpretability, optimality, and transferability. This project will train a diverse STEM workforce with data science skills that are essential for the global competitiveness of the US economy by creating new undergraduate and graduate programs in the foundations of data science and organizing a series of collaborative research events, including semester research programs and summer schools on the foundations of deep learning. This project will also impact women and underrepresented minorities by involving undergraduates in the foundations of data science.

Deep networks have led to dramatic improvements in the performance of pattern recognition systems. However, the mathematical reasons for this success remain elusive. For instance, it is not clear why deep networks generalize or transfer to new tasks, or why simple optimization strategies can reach a local or global minimum of the associated non-convex optimization problem. Moreover, there is no principled way of designing the architecture of the network so that it satisfies certain desired properties, such as expressivity, transferability, optimality and robustness. This project brings together a multidisciplinary team of mathematicians, statisticians, theoretical computer scientists, and electrical engineers to develop the mathematical and scientific foundations of deep learning. The project is divided in four main thrusts. The analysis thrust will use principles from approximation theory, information theory, statistical inference, and robust control to analyze properties of deep networks such as expressivity, interpretability, confidence, fairness and robustness. The learning thrust will use principles from dynamical systems, non-convex and stochastic optimization, statistical learning theory, adaptive control, and high-dimensional statistics to design and analyze learning algorithms with guaranteed convergence, optimality and generalization properties. The design thrust will use principles from algebra, geometry, topology, graph theory and optimization to design and learn network architectures that capture algebraic, geometric and graph structures in both the data and the task. The transferability thrust will use principles from multiscale analysis and modeling, reinforcement learning, and Markov decision processes to design and study data representations that are suitable for learning from and transferring to multiple tasks.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.