Search

The 17th of the problems proposed by Steve Smale for the 21st century asks for the existence of a deterministic algorithm computing an approximate solution of a system of n complex polynomials in n unknowns in time polynomial, on the average, in the size N of the input system. A partial solution to this problem was given by Carlos Beltr an and Luis Miguel Pardo who exhibited a randomized algorithm doing so. In this paper we further extend this result in several directions. Firstly, we exhibit a linear homotopy algorithm that eciently implements a nonconstructive idea of

The theory of computation is the newest and longest segment of Steve Smale’s mathematical career. It is still evolving and, thus, it is difficult to evaluate and isolate the more important of Smale’s contributions. I think they will be as important as his contributions to differential topology and dynamical systems. He has firmly grounded himself in the mathematics of practical algorithms, Newton’s method, and the simplex method of linear programming, inventing the tools and methodology for their analysis. With the experience gained, he is laying foundations for the theory of computation which have a unifying effect on the diverse subjects of numerical analysis, theoretical computer science, abstract mathematics, and mathematical logic. I will try to capture some of the points in this long-term project. Of course, the best thing to do is to read Smale’s original papers; I have not done justice to any of them.

The work of Steve Smale and his colleagues on average case analysis of algorithms [30, 31] and modeling real computations [3, 32] introduced methods and models not previously used in numerical analysis and complexity theory. In particular, the use of integral geometry to bound the sizes of sets of problems where algorithms “go bad” and the introduction of a model of real computation to clearly formulate complexity questions have inspired a great deal of other work. In this chapter, we will survey past results and open problems in three areas: the probability that a random numerical problem is difficult, the complexity of condition estimation, and the use of regularization to solve ill-posed or ill-conditioned problems; we will define all these terms below.

This large format book is described by the author as a coffee table art book; however, it is much more like a labor of love for Steve Smale. Smale not only describes the early difficulties of trying to publish such a mineral “art” volume, but also his efforts to develop the talent of photographing his own specimens, some of which are published here. You can understand his passion for mineral specimens and the development of this eye-candy book from the fact that he decided to enlist the talents of Jeff Scovil (a renowned mineral photographer) to provide the remainder of the color plate images. In total, there are 101 exquisite mineral color photographs. Beside the magnificent photos, Smale also provides a very valuable discourse on his (and his wife Clara’s) personal collecting criteria. Among the many characteristics he discusses, three elements are paramount: beauty, balance, and economy. Beauty is self evident to him; the specimen should be attractive from all angles and all components (matrix and main crystal) should enhance the …

In the period 1960–1965, geometric mechanics was “in the air.” Some key papers were available, such as Arnold’s work on KAM theory and a little had made it into textbooks, such as Mackey’s book on quantum mechanics and Sternberg’s book on differential geometry. In this period, Steve was working on his dynamical systems program. His survey article (Smale [1967]) contained important remarks on how geometric mechanics (specifically Hamiltonian systems on symplectic manifolds) fits into the larger dynamical systems framework. In 1966 at Princeton, Abraham ran a seminar using a preprint of the survey article and it was through this paper that I first encountered Smale’s work. After he visited the seminar, the importance of what he was doing was obvious; also, it became evident that there was great power in asking simple, penetrating, and sometimes even seemingly naive questions. I should add that in the mathematical physics seminar at Princeton that I also had the good fortune of attending, Eugene Wigner had a remarkably similar aura.

Summary: Genome architecture has emerged as a critical element of transcriptional regulation, although its role in the control of cell identity is not well understood. Here we use transcription factor (TF)-mediated reprogramming to examine the interplay between genome architecture and transcriptional programs that transition cells into the myogenic identity. We recently developed new methods for evaluating the topological features of genome architecture based on network centrality. Through integrated analysis of these features of genome architecture and transcriptome dynamics during myogenic reprogramming of human fibroblasts we find that significant architectural reorganization precedes activation of a myogenic transcriptional program. This interplay sets the stage for a critical transition observed at several genomic scales reflecting definitive adoption of the myogenic phenotype. Subsequently, TFs within the myogenic transcriptional program participate in entrainment of biological rhythms. These findings reveal a role for topological features of genome architecture in the initiation of transcriptional programs during TF-mediated human cellular reprogramming. : Molecular Structure; Integrative Aspects of Cell Biology; Systems Biology; Omics Subject Areas: Molecular Structure, Integrative Aspects of Cell Biology, Systems Biology, Omics

This work gives a mathematical foundation for bifurcation from a stable equilibrium in the genome. We construct idealized dynamics associated with the genome. For this dynamics, we investigate the two main bifurcations from a stable equilibrium. Finally, we give mathematical proofs of existence and points of bifurcation for the repressilator and the toggle gene circuits.

Significance A basic problem in biology is understanding how information from a single genome gives rise to function in a mature multicellular tissue. Genome dynamics stabilize to give rise to a protein distribution in a given cell type, which in turn gives rise to the identity of a cell. We build a highly idealized mathematical foundation that combines the genome (within cell) and the diffusion (between cell) dynamical forces. The trade-off between these forces gives rise to the emergence of function. We define emergence as the coordinated effect of individual components that establishes an objective not possible for an individual component. Our setting of emergence may further our understanding of normal tissue function and dysfunctional states such as cancer.

I first met Rene at the well-known 1956 meeting on topology in Mexico City. He then came to the University of Chicago, where I was starting my job as instructor for the fall of 1956. He, Suzanne, Clara and I became good friends and saw much of each other for many decades, especially at IHES in Paris. Thom’s encouragement and support were important for me, especially in my first years after my Ph.D. I studied his work in cobordism, singularities of maps, and transversality, gaining many insights. I also enjoyed listening to his provocations, for example his disparaging remarks on complex analysis, 19th century mathematics, and Bourbaki. There was also a stormy side in our relationship. Neither of us could hide the pain that our public conflicts over “catastrophe theory” caused. Rene Thom was a great mathematician, leaving his impact on a wide part of mathematics. I will always treasure my memories of him. Steve Smale

In previous work, with Bartholdi and Schick [1], the authors developed a Hodge–de Rham theory for compact metric spaces, which defined a cohomology of the space at a scale α. Here, in the case of Riemannian manifolds at a small scale, we construct explicit chain maps between the de Rham complex of differential forms and the L2 complex at scale α, which induce isomorphisms on cohomology. We also give estimates that show that on smooth functions, the Laplacian of [1], when appropriately scaled, is a good approximation of the classical Laplacian.

Learning theory studies data structures from samples and aims at understanding unknown function relations behind them. This leads to interesting theoretical problems which can be often attacked with methods from Approximation Theory. This workshop - the second one of this type at the MFO - has concentrated on the following recent topics: Learning of manifolds and the geometry of data; sparsity and dimension reduction; error analysis and algorithmic aspects, including kernel based methods for regres- sion and classification; application of multiscale aspects and of refinement algorithms to learning.

In this paper, we take a topological view of unsupervised learning. From this point of view, clustering may be interpreted as trying to find the number of connected components of any underlying geometrically structured probability distribution in a certain sense that we will make precise. We construct a geometrically structured probability distribution that seems appropriate for modeling data in very high dimensions. A special case of our construction is the mixture of Gaussians where there is Gaussian noise concentrated around a finite set of points (the means). More generally we consider Gaussian noise concentrated around a low dimensional manifold and discuss how to recover the homology of this underlying geometric core from data that do not lie on it. We show that if the variance of the Gaussian noise is small in a certain sense, then the homology can be learned with high confidence by an algorithm that has a weak (linear) dependence on the ambient dimension. Our algorithm has a natural interpretation as a spectral learning algorithm using a combinatorial Laplacian of a suitable data-derived simplicial complex.

Partial differential equations and the Laplacian operator on domains in Euclidean spaces have played a central role in understanding natural phenomena. However, this avenue has been limited in many areas where calculus is obstructed, as in singular spaces, and in function spaces of functions on a space X where X itself is a function space. Examples of the latter occur in vision and quantum field theory. In vision it would be useful to do analysis on the space of images and an image is a function on a patch. Moreover, in analysis and geometry, the Lebesgue measure and its counterpart on manifolds are central. These measures are unavailable in the vision example and even in learning theory in general.

This paper attempts to give an extension of learning theory to a setting where the assumption of i.i.d. data is weakened by keeping the independence but abandoning the identical restriction. We hypothesize that a sequence of examples (xt, yt) in X × Y for t = 1, 2, 3,… is drawn from a probability distribution ρt on X × Y. The marginal probabilities on X are supposed to converge to a limit probability on X. Two main examples for this time process are discussed. The first is a stochastic one which in the special case of a finite space X is defined by a stochastic matrix and more generally by a stochastic kernel. The second is determined by an underlying discrete dynamical system on the space X. Our theoretical treatment requires that this dynamics be hyperbolic (or "Axiom A") which still permits a class of chaotic systems (with Sinai–Ruelle–Bowen attractors). Even in the case of a limit Dirac point probability, one needs the measure theory to be defined using Hölder spaces. Many implications of our work remain unexplored. These include, for example, the relation to Hidden Markov Models, as well as Markov Chain Monte Carlo methods. It seems reasonable that further work should consider the push forward of the process from X × Y by some kind of observable function to a data space.

We provide a model (for both continuous and discrete time) describing the evolution of a flock. Our model is parameterized by a constant beta capturing the rate of decay-which in our model is polynomial-of the influence between birds in the flock as they separate in space. Our main result shows that when beta

We consider the regression problem and describe an algorithm approximating the regression function by estimators piecewise constant on the elements of an adaptive partition. The partitions are iteratively constructed by suitable random merges and splits, using cuts of arbitrary geometry. We give a risk bound under the assumption that a "weak learning hypothesis" holds, and characterize this hypothesis in terms of a suitable RKHS. Two examples illustrate the general results in two particularly interesting cases.

The regression problem in learning theory is investigated with least square Tikhonov regularization schemes in reproducing kernel Hilbert spaces (RKHS). We follow our previous work and apply the sampling operator to the error analysis in both the RKHS norm and the L2 norm. The tool for estimating the sample error is a Bennet inequality for random variables with values in Hilbert spaces. By taking the Hilbert space to be the one consisting of Hilbert-Schmidt operators in the RKHS, we improve the error bounds in the L2 metric, motivated by an idea of Caponnetto and de Vito. The error bounds we derive in the RKHS norm, together with a Tsybakov function we discuss here, yield interesting applications to the error analysis of the (binary) classification problem, since the RKHS metric controls the one for the uniform convergence.

We describe a setting where convergence to consensus in a population of autonomous agents can be formally addressed and prove some general results establishing conditions under which such convergence occurs. Both continuous and discrete time are considered and a number of particular examples, notably the way in which a population of animals move together, are considered as particular instances of our setting.

We continue our study [S. Smale, D.X. Zhou, Shannon sampling and function reconstruction from point values, Bull. Amer. Math. Soc. 41 (2004) 279–305] of Shannon sampling and function reconstruction. In this paper, the error analysis is improved. Then we show how our approach can be applied to learning theory: a functional analysis framework is presented; dimension independent probability estimates are given not only for the error in the L 2 spaces, but also for the error in the reproducing kernel Hilbert space where the learning algorithm is performed. Covering number arguments are replaced by estimates of integral operators.

In this paper, we study an online learning algorithm in Reproducing Kernel Hilbert Spaces (RKHSs) and general Hilbert spaces. We present a general form of the stochastic gradient method to minimize a quadratic potential function by an independent identically distributed (i.i.d.) sample sequence, and show a probabilistic upper bound for its convergence.

Let B be a Banach space and (ℋ,‖·‖ℋ) be a dense, imbedded subspace. For a ∈ B, its distance to the ball of ℋ with radius R (denoted as I(a, R)) tends to zero when R tends to infinity. We are interested in the rate of this convergence. This approximation problem arose from the study of learning theory, where B is the L2 space and ℋ is a reproducing kernel Hilbert space. The class of elements having I(a, R) = O(R-r) with r > 0 is an interpolation space of the couple (B, ℋ). The rate of convergence can often be realized by linear operators. In particular, this is the case when ℋ is the range of a compact, symmetric, and strictly positive definite linear operator on a separable Hilbert space B. For the kernel approximation studied in Learning Theory, the rate depends on the regularity of the kernel function. This yields error estimates for the approximation by reproducing kernel Hilbert spaces. When the kernel is smooth, the convergence is slow and a logarithmic convergence rate is presented for analytic kernels in this paper. The purpose of our results is to provide some theoretical estimates, including the constants, for the approximation error required for the learning theory.

whereA is an differential operator and L2 is the Hilbert space of square integrable functions on X with measure ρX on X defined via ρ. This minimization is well-conditioned and solved by straightforward finite dimensional least squares linear algebra to yield fγ,z : X → Y . The problem is posed: How good an approximation is fγ,z to fρ, or measure the error ∫ X(fγ,z − fρ)? and What is the best choice of γ to minimize this error? Our goal in this talk is to give some answers to these questions.

We present the development of a new theory of the pitchfork bifurcation, which removes the perspective of the third derivative and a requirement of symmetry.

(1) A main theme of this report is the relationship of approximation to learning and the primary role of sampling (inductive inference). We try to emphasize relations of the theory of learning to the mainstream of mathematics. In particular, there are large roles for probability theory, for algorithms such as least squares, and for tools and ideas from linear algebra and linear analysis. An advantage of doing this is that communication is facilitated and the power of core mathematics is more easily brought to bear. We illustrate what we mean by learning theory by giving some instances. (a) The understanding of language acquisition by children or the emergence of languages in early human cultures. (b) In Manufacturing Engineering, the design of a new wave of machines is anticipated which uses sensors to sample properties of objects before, during, and after treatment. The information gathered from these samples is to be analyzed by the machine to decide how to better deal with new input objects (see [43]). (c) Pattern recognition of objects ranging from handwritten letters of the alphabet to pictures of animals, to the human voice. Understanding the laws of learning plays a large role in disciplines such as (Cognitive) Psychology, Animal Behavior, Economic Decision Making, all branches of Engineering, Computer Science, and especially the study of human thought processes (how the brain works). Mathematics has already played a big role towards the goal of giving a universal foundation of studies in these disciplines. We mention as examples the theory of Neural Networks going back to McCulloch and Pitts [25] and Minsky and Papert [27], the PAC learning of Valiant [40], Statistical Learning Theory as developed by Vapnik [42], and the use of reproducing kernels as in [17] among many other mathematical developments. We are heavily indebted to these developments. Recent discussions with a number of mathematicians have also been helpful. In

This paper has two agendas. One is to develop the foundations of round-off in computation. The other is to describe an algorithm for deciding feasibility for polynomial systems of equations and inequalities together with its complexity analysis and its round-off properties. Each role reinforces the other.

V. I. Arnold, on behalf of the International Mathematical Union has written to a number of mathematicians with a suggestion that they describe some great problems for the next century. This report is my response. Arnold's invitation is inspired in part by Hilbert's list of 1900 (see e.g. [Browder, 1976]) and I have used that list to help design this essay. I have listed 18 problems, chosen with these criteria

Complexity theory of numerical analysis is the study of the number of arithmetic operations required to pass from the input to the output of a numerical problem.

Antigenic peptides presented to T cells by MHC molecules are essential for T or B cells to proliferate and eventually differentiate into effector cells or memory cells. MHC binding prediction is an active research area. Reliable predictors are demanded to identify potential vaccine candidates. The recent kernel-based algorithm KernelRLSpan (Shen et al., 2013) shows promising power on MHC II binding prediction. Here, KernelRLSpan is modified and applied to MHC I binding prediction, which we refer to as KernelRLSpanI. Besides this, we develop a novel consensus method to predict naturally processed peptides through integrating KernelRLSpanI with two state-of-the-art predictors NetMHCpan and NetMHC. The consensus method achieved top performance in the Machine Learning in Immunology (MLI) 2012 Competition, 3 group 2. We also introduce our progress of improving our MHC II binding prediction method KernelRLSpan by diffusion map.

Understanding how the brain works and reproducing its central capabilities in computers is arguably one of the greatest problems in science and engineering. This project directly contributes to this challenge from both a mathematical and an applied point of view. In particular, we have developed a mathematical description of a family of hierarchical architectures for learning, comprised of a collection of definitions, lemmas and theorems which collectively highlight important and salient properties of such architectures. Most important among these properties is the notion of invariance. The theory we have developed characterizes how and why a hierarchical architecture can offer better generalization from few examples in terms capturing and exploiting symmetries in the physical world by way of learning invariances. A comprehensive suite of distributed, GPU-enabled software tools was developed to quickly test hypotheses and validate the theory on large-scale, real-world datasets.

This chapter delves more deeply into the qualitative aspects of solutions of planar linear systems. The first types of systems considered include those with real and distinct eigenvalues. Here the phase planes include sinks, saddles, and sources. When the eigenvalues are complex, other phase planes arise: spiral sinks, spiral sources, and centers. The more difficult case of repeated real eigenvalues is introduced. Then the canonical form of a matrix is introduced, and it is shown how one can change coordinates to put systems into this form. The notion of an invertible matrix is necessary to explain this process.

Unlike the previous chapter, which focused on local techniques for nonlinear systems, this chapter introduces global ideas to understand the behavior of these systems. In particular, nullclines are used to partition the phase space into regions where the vector field points in certain directions. This allows us to understand heteroclinic bifurcations. A further notion of stability, Liapunov stability, is introduced. The phase plane for the ideal pendulum is described using the total energy function. Finally, two special types of systems are introduced: gradient systems and Hamiltonian systems.

This chapter moves on to higher-dimensional linear algebra. The concepts of linear independence, subspace, and spanning set arise.

This chapter investigates the different types of limit sets that occur for nonlinear systems. The notions of α -limit sets and ω -limit sets are introduced. The most important such limit set is a limit cycle. Local sections and flow boxes are used to characterize these sets. This brings up a higher-dimensional version of the Poincare map.

This chapter tackles higher-dimensional linear systems of differential equations. Here the system involves an n × n matrix, so all of the linear algebra of the previous chapter comes into play.

Various examples of differential equations that arise in biology are discussed in this section. The first is a model for infectious diseases known as the SIRS model (susceptible, infected, and recovered). The second is the predator–prey system in which it is shown that all solutions lie on closed orbits. This changes when the model is modified to account for limited growth of the population. The third model is a competitive species model where it is shown that all solutions now tend to one of a finite number of equilibria. Previously introduced techniques such as linearization, nullclines, and the Poincare-Bendixson Theorem are used to investigate these models. Later explorations include a competition and harvesting model and a SIRS model using zombies.

Planar linear systems of differential equations are the subject of this chapter. These are introduced via second-order differential equations such as Newton's equation (force = mass × acceleration) and the RLC circuit equation. The phase plane provides the qualitative pictures for solutions of these types of equations.

The trace–determinant plane is introduced to provide a summary of all possible behaviors of linear systems of differential equations. This is the analogue of the bifurcation diagram used for first-order equations. A dynamical classification is also given for linear systems. Here the notion of conjugacy provides a mechanism for determining when two linear systems have the same behavior. It is shown that two matrices yield conjugate linear systems if one eigenvalue is positive and the other negative, if both have negative real parts, or if both have positive real parts. Specific conjugacies are created in these cases.

Various differential equations that arise in circuit theory are investigated in this chapter. The first example is the RLC circuit equation. A more general type of system is the Lienard equation. The final example is the van der Pol equation. Here we show that all nonzero solutions tend to a periodic solution. Again the associated Poincare map is the tool that provides this result. A Hopf bifurcation often arises in circuit equations, and these new types of bifurcations are described in this chapter. A final exploration involves a system from neurodynamics, the Fitzhugh–Nagumo equations.

The goal of this chapter is to introduce the concept of linearization near an equilibrium point of a nonlinear system. This process substitutes a linear system for a nonlinear system, at least near an equilibrium point. An equilibrium point is hyperbolic if all of the eigenvalues of the linearized system have nonzero real parts. In the hyperbolic case, the flow of the nonlinear system is locally conjugate to the flow of the linearized system near the equilibrium point. In particular, this allows us to prove the Stable Curve Theorem, which produces solution curves tending to and from an equilibrium in the saddle case. This also introduces the notion of stability. We describe the notion of asymptotic stability of equilibria and then investigate bifurcations that occur near equilibria, specifically the saddle-node bifurcation.

In this final chapter the Existence and Uniqueness Theorem is proved. The criterion for continuous dependence on initial conditions is also proved. Further results involving the extendibility of solutions, differentiability of the flow, and the behavior of nonautonomous systems are described.

This chapter delves into some systems of differential equations arising in mechanics. The first is the famous Newton's second law, force = mass × acceleration. This leads to the more general type of systems known as conservative systems, which are special examples of Hamiltonian systems as described in Chapter 9 . The main example here is given by central force fields and, specifically, the Newtonian central force system. Specific examples treated include Kepler's first law and the two-body problem from celestial mechanics. A new technique called blowing up the singularity provides a tool for understanding these systems near places where the system is undefined–that is, collisions between the various bodies. Explorations include classical limits of quantum mechanical systems and the motion of a glider.

This chapter describes the behavior of first-order differential equations. The first example is the most basic differential equation—namely, the unlimited population growth model. Later models include the logistic population growth model. Where it is assumed that there is a carrying capacity for the given population. Then harvesting is introduced into the model. This leads to the concept of bifurcation. To understand these bifurcations, numerous qualitative techniques are introduced, including slope field, solution graphs, phase line, and bifurcation diagram. Then the logistic model is modified to allow for periodic harvesting, which leads to a nonautonomous differential equation. Periodic solutions are introduced via this model. The Poincare map is then used to prove the existence of these types of solutions and to understand the nearby behavior.