Mathematics, Systems and Robotics Seminar 

The autoregressive (AR) process is fundamental to linear signal processing and is commonly used to model the behaviour of an object evolving on Euclidean space. In real life, there are myriad examples of objects evolving not on flat spaces but on curved spaces such as the surface of a sphere. For instance, wind-direction studies in meteorology and the estimation of relative rotations of tectonic plates based on observations on the Earth's surface deal with spherical data, while subspace tracking in signal processing is actually inference on the Grassmann manifold. In this talk, we extend the AR concept to objects evolving on a curved space, or in a general, a manifold. Doing so is non-trivial, and in fact, several different extensions are proposed, along with their advantages and disadvantages. Algorithms for estimating the parameters of these generalized AR processes are also discussed.

In this talk we will describe some recent techniques to obtain solutions to nonlinear evolution equations of dispersive type, specially for low regularity data.

Image restoration is usually formulated as the minimization of the sum of two convex functions: A quadratic data term and a nonquadratic regularizer (prior in the Bayesian framework). In recent work, a class of iterative denoising algorithms has been proposed. The denoising operator depends on the regularizer (prior). Popular regularizers are the

1. Total Variation (isotropic and nonisotropic),
2. the $l^p$ norm, and
3. the $p$-th power of an $l^p$ norm (both 2 and 3 with $p$ greater or equal to one).

The first two classes are usually formulated in the image domain, whereas the former is often formulated in the wavelet domain in applications involving sparse representations.

The iterative denoising approach is well suited to large scale problems. Its convergence rate is, however, overly slow when the linear operator associated with the data term is ill-conditioned or ill-posed. In this talk I will review this class of algorithms and present two-step (also known as second order) versions of the original ones that exhibit a much faster convergence rate. The underlying motivation behind the two-step versions parallels that of two-step linear methods to solve linear systems of equations.

We show that the proposed two-step iterative scheme converges to a minimum of the underlying optimization problem, for a wide range of regularizers, including those mentioned above. We also give the optimal setting of the parameters that define the algorithm. The effectiveness of our scheme is illustrated with TV and wavelet-based image restoration examples.

Gamma-convergence is a notion of convergence for functionals very useful to study the asymptotic behaviour of families of minimization problems, namely, given a familly of functionals F_h, under very mild conditions we can identify a limit F and get the convergence of minimizers of F_h to minimizers of F. In this talk we discuss the main ideas and refer some applications of this variational convergence.

Measuring a similarity between two strings is a fundamental step in many applications in areas such as text classification and information retrieval. Lately, kernel-based methods have been proposed for this task, both for text and biological sequences. Since kernels are inner products in a feature space, they naturally induce similarity measures. Information-theoretical approaches have also been subject of recent research. The goal is to classify finite sequences without explicit knowledge of their statistical nature: sequences are considered similar if they are likely to be generated by the same source. There is experimental evidence that relative entropy (albeit not being a true metric) yields high accuracy in several classification tasks. Compression-based techniques, such as variations of the Ziv-Lempel algorithm for text, or GenCompress for biological sequences, have been used to estimate the relative entropy. Algorithmic concepts based on the Kolmogorov complexity provide theoretic background for these approaches. We describe some string kernels and information theoretic methods, and evaluate the performance of both kinds of methods in text classification tasks, namely in the problems of authorship attribution, language detection, and cross-language document matching.

Consideramos um processo evolutivo simples: a cada rodada um indiviudo de uma populacao de tamanho fixo composta por dois tipos de indivíduos é escolhido aleatóriamente para morrer e é substituído por uma cópia de um dos sobreviventes, desta vez com pobabilidade associada ao "fitness". Os "fitness" são obtidos a partir de considerações de teoria de jogos. Obtemos um limite para populações infinitas, após um "re-scaling" tanto dos pay-offs como do intervalos de tempo. Esta é uma equação com derivadas parciais do tipo "drift-diffusion" (Fokker-Planck) onde seus coeficientes sao degenerados (iguais a zero) na fronteira. Analisaremos esta equação e compararemos nossos resultados com equações ja conhecidas.

In this talk I will address the state estimation of systems modeled by nonlinear equations using the minimum energy and the H-infinity filtering approaches. In particular for a class of systems with implicit outputs we show that, under appropriate observability assumptions, the optimal estimate converges globally asymptotically to the true value of the state in the absence of noise and disturbance. In the presence of noise, the estimate converges to a neighborhood of the true value of the state. We apply these results to the estimation of position and attitude of an autonomous vehicle using measurements from an inertial measurement unit (IMU) and a monocular charged-coupled-device (CCD) camera attached to the vehicle. In our formulation we take directly into account that the measurements arrive at discrete-time instants, are time-delayed, and may not be complete. In this way, we can deal with usual problems in vision systems such as noise as well as latency and intermittency of observations.

In this talk we discuss an entropy penalization discrete scheme in relation with approximate solutions of Hamilton-Jacobi equations. This scheme is convergent for suitable choices of the parameters and it is linked to a linear evolution equation scheme by an exponential transformation. The fixed points of the scheme are related to the construction of entropy penalized Mather measures.

The seminar addresses the problem of computing the Riemannian centroid of a constellation of points in a locally symmetric connected manifold, particularly ones with a naturally reductive homogeneous space structure. Note that many interesting manifolds used in engineering (such as the special orthogonal group, Grassman, sphere, positive definite matrices) possess this structure. An intrinsic Newton scheme for the centroid computation is thus made available. Some results of finding the centroid of a constellation of points in these spaces are presented, which evidences the quadratic convergence of the Newton method derived herein. These computer simulation results show that, as expected, the Newton method has a faster convergence rate than the usual gradient-based approaches.

We present different graph cut-based approaches for exact optimization of some Markovian energies. We reformulate these energies as binary Markov random fields asscotiated with each level sets of an image. First we consider the case where data fidelity terms are convex functions and where the prior is the total variation. Then we generalize this approach to the case of "levelable" energies. A second generalization, different from the first one, consider the case where priors are convex functions. Finally, we present an efficient minimization algorithm for energies where both data fidelities and priors are convex functions. Numerical experiments are presented for each case.

This will be the third (and final) of a series of introductory talks on the modern theory of Partial Differential Equations both for engineers and (non-PDE) mathematicians. In this last lecture of this series we will discuss how ideas from probability arise in the study of elliptic and parabolic equations, stochastic control and Hamilton-Jacobi equations, as well as in certain models in fluid mechanics.

In this talk we will present our current research about a network formation game among a set of Internet Service Providers (ISPs) that interconnect to transport IP traffic across a set cities. The research includes: (i) the definition and study of a non-cooperative game among ISPs facing exogenous demand for the transport of traffic; ii) the computational simulation of the ISPs behavior as a way to find the set of Nash Equilibrium of this game; (iii) the analysis of equilibrium networks in terms of topology, cost and industry structure; (iv) the design of interconnection incentives aimed at reducing provisioning costs. This talk will focus primarily on the definition of the network formation game and on the main theoretical findings obtained so far about its properties. Challenges faced while trying to simulate such a game will be briefly discussed, along with the approaches used. Finally, orientations and ideas for future work will be outlined.

In this lecture we will survey several connections between calculus of variations (including control theory as a subset of CV) and PDEs. We will discuss a typical problems in calculus of variations: the Dirichlet integral and Laplace's equation, control theory and Hamilton-Jacobi equations, gradient-flows and dissipative equations, and the role of symmetries and conservation laws in other classes of equations such as wave or KdV.

The Theory of Queuing Networks (TQN), like many other areas, is built from knowledge and intuition gained with simple models. The M/M/1 queue is the first basic block. Many others were developed and studied over the years, namely the Scheduling Problem, defined for two classes of customers and one single server, and the Routing Problem, defined for one class of customers and two parallel servers.

The majority, if not all, of the basic building blocks defined for the TQN is such that the optimal decision policy is /Non-Idling/. That is, servers only stop when there are no clients waiting for processing. The consequences of this fact are significant and profound in the research conducted for decades in this area. However, as it is the thesis of this presentation, they are misleading and harmful.

A basic building block will be presented, for which the optimal policy will be *shown* to be /Idling/. That is, there are states for which a given server remains idle in the presence of customers waiting for its service. This block, entitled as the Entangled Scheduling and Routing Problem, may become a fundamental tool in the analysis of networks of queues.

In the talk, the problem will be formulated as a Markov Decision Problem and its optimal policy will be presented, as it is numerically produced for some instances of the problem.

It is now necessary to formally characterize the optimal policy as well as *to prove* its idling characteristic. The talk aims at motivating the participants into engaging such formal characterization exercise. Clues and intuition derived from the numerical results will be provided as guides for potential solution paths.

A new geometrical formulation of the theoretical foundations of classical electrodynamics is presented. This new geometrical approach is simultaneously based on Cartan's exterior calculus of differential forms and on the (Clifford) geometric algebra developed by David Hestenes (among others). However, instead of adopting the graded algebra of multivectors commonly used in geometric algebra, an alternative framework using a graded algebra of differential forms is introduced. Accordingly, such powerful tools as the exterior derivative and the (generalized) Stokes theorem can be used throughout. Within this framework a clear separation between even and odd (or pseudo) differential forms is then established from the beginning.

This will be the first of a series of introductory talks on the modern theory of Partial Differential Equations both for engineers and (non-PDE) mathematicians. The plan of the first three talks is as follows:

1. Formulas, Examples and Counterexamples

   We will discuss general methods for constructing solutions of PDEs (First-order, Laplace, Heat, and wave equations), present several examples concerning existence, uniqueness or regularity of solutions, which, we hope, motivate the need for considering weak solutions, study existence, uniqueness and regularity issues for those weak solutions.

2. Calculus of Variations and PDE

   In this lecture we will survey several connections between calculus of variations (including control theory as a subset of CV) and PDEs. We will discuss a typical problems in calculus of variations: the Dirichlet integral and Laplace's equation, control theory and Hamilton-Jacobi equations, gradient-flows and dissipative equations, and the role of symmetries and conservation laws in other classes of equations such as wave or KdV.

3. Probability and PDE

   In the last lecture of this series we will discuss how ideas from probability arise in the study of elliptic and parabolic equations, stochastic control and Hamilton-Jacobi equations, as well as in certain models in fluid mechanics. Hopefully, at this point, other(s) speaker(s) will take over, and in this second part other we will consider (also depending on the speaker) topics such as:

4. Functional analysis methods

   Abstract results for solutions of linear equations such as Lax-Milgram theorem (elliptic equations) or semigroup theory (evolution equations).

5. Harmonic Analysis and PDE

   Introduction to Fourier transform methods and the modern theory of dispersive non-linear equations.