Mathematics, Systems and Robotics Seminar 

In this talk we discuss some stochastic optimal control problems and its applications to classical mechanics, turbulence and fluid mechanics.

Um corpo move-se num meio rarefeito (podemos imaginar um satélite artificial no espaço ou um plano (Shuttle?) na estratosfera). É preciso encontrar a forma do corpo que minimize a resistência do meio ao seu movimento. Este problema foi inicialmente posto pelo I. Newton em 1686 e hoje em dia é o objecto de estudos intensivos. Outro problema, proposto pelo G. Monge em anos 1780, é o seguinte: Há um aterro e uma cavidade de mesmo volume; é preciso efectuar o deslocamento da terra do aterro para a cavidade com esforço mínimo. Ambas teorias estão agora na fase de desenvolvimento rápido; ambas têm aplicações práticas. Vai ser dado um resumo breve dos resultados obtidos recentemente nestas áreas (em particular, pelo autor) e vai ser explicada interligação entre estas áreas.

The aim of this talk is to show how simple concepts of number theory can lead to powerful tools of cryptology. First the principles of public key encryption systems are introduced. After that we turn to the needed mathematics – we shortly repeat the congruence arithmetics mod N leading to the problem of discrete logarithms and the theorem of Euler. Based on that the famous algorithms of Diffie-Hellman and Rivest-Shamir-Adleman (RSA) are introduced and their reliability is discussed.

Todos nós, portugueses, seguimos com atenção o concurso de colocação dos docentes dos ensinos pré-escolar, básico e secundário, ano lectivo de 2004/2005. Pelo que na altura veio a público, ficou claro que no âmago da questão encontrava-se um problema de natureza técnica, matemática, que não fora devidamente valorizado pelo Ministério da Educação. Nesta palestra, pretendemos identificar as questões de índole matemática que se levantam num concurso para colocação de docentes. Em primeiro lugar, iremos perceber como é que da legislação vigente se passa para uma especificação formal. Identificaremos duas especificações possíveis, ambas conformes com a lei, chamando óptima localmente verificável a uma e lexicograficamente óptima à outra. Estas duas especificações têm propriedades diferentes e resultam em colocações diferentes. Em segundo lugar, indicaremos algoritmos para cumprir cada uma das duas especificações. E, em terceiro lugar, enquadraremos o problema da colocação de docentes no contexto dos emparelhamentos estáveis e de peso mínimo, tão queridos dos matemáticos.

Local stationarity is a necessary condition to design passive detectors of transient signals robust to shift errors. It allows for a significant reduction of their computational cost and performance loss. This talk relates the second-order statistics of $L^2(R)$ processes with the sampling theorem and local stationarity of a stochastic process. It is shown how local stationarity can be observed either in the time-frequency plane (Wigner distribution) or the $2$-dimensional power spectrum. A simple method to design locally stationary covariance matrices from data is presented. Real data examples illustrate the advantages of such processors in situations of interest.

We will present a computational method in Commutative Algebra, together with its applications to some interesting problems in Geometry and Robotics, which require no more than the basic operations with multivariate polynomials. According to the theory of Gröbner basis, one can replace any system of n polynomial equations in m variables, by an equivalent system where variables can be 'eliminated' in succession, thereby greatly simplifying its resolution. In fact, this method generalizes the Gaussian elimination method for linear systems of equations. Some problems in Robotics and Systems Theory, as well as in Algebraic Geometry, require the consideration of systems of polynomial equations. Therefore, the algorithms to compute Gröbner bases, implemented nowadays in almost every symbolic manipulation computer system, can be especially useful.

Let $E \subseteq \mathbb{R}$ be an abstract space and $k: I^2 \to \mathbb{C}$ be a reproducing kernel on $E$. By the Moore-Aronszajn theorem, every finite matrix $k(x_i,x_j)$ is positive semidefinite. If $E= \mathbb{R}^n$ or $E= \mathbb{C}^n$ then if $k(x,y)$ is appropriately differentiable it satisfies a 2-parameter family of differential inequalities of which the classic triangle inequality is the order $0$ case. The generality of this result probably means it has a wealth of consequences in different contexts where reproducing kernels are relevant. As an example we point out an application to kernels of positive integral operators, which yields optimal Sobolev norm bounds.

After recalling the Empirical Mode Decomposition (EMD) principle, we will provide this entirely data-driven signal decomposition introduced by Huang et al. (1998) a filter bank interpretation from two complementary perspectives. First, a stochastic approach operating in the frequency domain evidences the spontaneous emergence of an equivalent dyadic filter bank structure when applying EMD to the versatile class of fractional Gaussian noise processes. Second, a similar structure is observed when operating in the time domain on a deterministic pulse. A detailed statistical analysis of the reported behaviour is carried out on the basis of extensive numerical simulations, allowing for a number of applications. New EMD-based approaches are outlined in different directions, namely estimating scaling exponents in the case of self-similar processes, performing a fully data-driven spectrum analysis and denoising-detrending signal + noise mixtures.

Phase estimation is the process of recovering the phase (the so-called absolute phase) from noisy and modulo $2\pi$ (the so-called wrapped phase) observations. The need for determining absolute phase is common to many classes of signal/image applications. For example, interferometric synthetic aperture radar uses two or more antennas to measure the phase difference between the antennas and the terrain; the topography is then inferred from the difference between those phases. In magnetic resonance imaging, phase is used to measure flow and temperature temperature, to visualize veins in the tissue (venography), to map the principal magnetic field, which is the basis for several correction techniques, and to separate water and fat. In optical interferometry, phase measurements are used to detect objects shape, deformation, and vibration. In this talk I introduce the absolute phase estimation problem and present a Bayesian approach aimed at to the computation of the "maximum a posteriori estimate" (MAP). The heaviest step in computing the MAP estimate is an integer optimization problem of an $L^p$ type norm. For $p\ge 1$, we solve this optimization in polinomial time by mapping the initial problem onto a series of graph-cuts on given graph. For $p\ge 1$, the proposed method also solves any of the so-called "minimum $L^p$" approaches to phase unwrapping (i.e., absolute phase estimation without noise), to which solutions were know only for $p=1$. A set of experimental results illustrates the effectiveness of the proposed approach.

Taking the Maxwell equations as a point of departure, we will describe some exciting ideas from modern fundamental physics and will mention part of their mathematical significance. Way beyond Maxwell theory, we will find that large random matrices appear on the scene. Surprisingly, the same mathematical object also seems to find many applications in engineering and we will (very) briefly mention a few.

The problem of inferring the 3D position and orientation of a camera that acquires a video sequence is of most interest in Computer Vision. Most approaches require an intermediate step where image features (edges, corners, etc) are detected at each frame and then corresponded among consecutive frames through tracking algorithms. This step is seen as the main bottleneck of those approaches.

We propose a new 3D orientation estimation method for urban (indoor and outdoor) environments, which avoids correspondences between frames. The basic scene property exploited by our method is that many edges are oriented along three orthogonal directions; this is the recently introduced Manhattan world (MW) assumption. We use the octohedral group of symmetries of a cube to derive equivalence classes for the orientation, thus achieving a considerable reduction in the search space.

In addition to the novel adoption of the MW assumption for video analysis, we introduce the small rotation (SR) assumption, that expresses the fact that the video camera undergoes a smooth 3D motion.

From these assumptions, we build a probabilistic estimation approach and demonstrate the performance of our method using real video sequences.

A zero-sum differential game is a dynamical system controlled by two players, coupled with a cost functional that one player wants to minimize and the other player seeks to maximize. If the value function of the game is defined appropriately, the classical dynamic programming approach leads to a Hamilton-Jacobi partial differential equation with nonconvex Hamiltonian, called Isaacs' equation. I will survey the results of various authors on the well-posedness of these equations in the framework of viscosity solutions, and on the use of PDE methods for the sinthesis of approximate optimal feedbacks for both players.

• Paulo Mateus - An overview of quantum computation
  
  Abstract: Its believed that with the present rate of miniaturization of computer chips the size of a memory unit will reach the quantum bound near the year 2020. This means that we will be dealing with a bit as small as an atom, the two states of which may be among other possibilities, the two directions of its spin. However, such (quantum) bits reveal several interesting properties. Capitalizing on such properties, P. Shor devised a quantum algorithm that is able to factor integers in (probabilistic) polynomial-time. Since no efficient classical factoring algorithm is known, this is a clear indication that quantum computers are exponentially faster than their classical counterparts.
  
  The main purpose of this talk is to give an overview of the main concepts involving quantum computation. We start from the postulates of quantum mechanics and end with Shor algorithm. We conclude the talk with some open problems and future research work.
  
  
• António M. Pascoal- Dynamical Systems and Marine Robotics: From theory to practice
  
  Abstract: Worldwide, there is widespread interest in bridging the gap between marine science and technology by exploring fruitful collaboration links among engineers and marine scientists, namely biologists, geologists, and oceanographers. This symbiosis is instrumental in providing engineers with complex, challenging problems in the field of marine robotics. Conversely, it will afford marine scientists increasingly complex tools to explore the ocean frontier, specially in hazardous conditions. This talk will focus on the interplay between theory and practice in marine robotics. The first part of the talk will provide a quick overview of the marine robotics field and highlight scientific and commercial applications. This will be followed by the description of challenging problems in Navigation, Guidance, and Control (NGC) that arise in the process of developing marine robots that must perform reliably at sea. Key concepts and classical as well as newly emerging design techniques in NGC will be summarized. Examples will be given of problems that are rooted in yet unsolved questions in mathematical system theory. The final part of the talk will provide the bridge between concept and practice. Hardware and software architectures for algorithm implementation on existing prototypes of surface and underwater robots developed at the Institute for Systems and Robotics (ISR, pole of Lisbon) will be briefly described. Videos will show actual operations at sea.

• Andrés García - The concept of Controlled Eigenvectors for Affine Non-Linear Systems Applied to Vehicle Formations Control

  Abstract: Affine non-linear control systems arise naturally in vehicle formation control as a result of the formulation of the requirements for the formation goals (keeping formation, initialization, reach the target location). One alternative approach to describe the desired requirements for a formation control framework is to express non-holonomic constraints in an Analytical Mechanics framework. These two related technics yield a novel methodology to control a vehicle formation similar to pole placement in linear control systems, which we call eigenvector placement, through the calculation of one additional constraint, allowing the analysis of stability issues as well. The methodology is directly exploited for non-linear affine control systems and it is presented together with some representative examples for single vehicles and multivehicle formations.

• Diogo Gomes - Optimal Control and Viscosity Solutions

  Abstract: We present the theory of viscosity solutions of Hamilton-Jacobi equations as a tool to study optimal control problems even when Halmilton-Jacobi equations fail to have smooth solutions.

• Gabriel Pires - Partial Differential Equations and Image Processing

  Abstract: A complete classification of image multiscale transforms, satisfying a list of formal requirements, will be given. The classical models and new ones, which all are partial differential equations, will be characterized namely in terms of invariance properties.

• Mário Figueiredo - Iterative Algorithms for Wavelet-based Image Restoration

  Abstract: Wavelet-based methods had a strong impact on the field of image processing, especially in coding and denoising. Wavelet-based image denoising methods yield state-of-the-art performance at very low computational cost. However, image restoration (deconvolution) is a more challenging problem than denoising, and applying wavelets to it has proved to be a non-trivial task. The crux of the difficulty lies in the fact that deconvolution is most easily dealt with in the Fourier domain, while image modelling is best handled in the wavelet domain.

  In this talk, after briefly reviewing wavalet-based image modelling and denoising, I will describe recently proposed algorithms for wavelet-based image deconvolution. These algorithms provide maximum penalized likelihood (MPL) estimates, under wavelet-based penalties, for which there are no closed-form solutions. I will show how such iterative algorithms can be derived from two different approaches. In the first approach, the observation model is re-written by inserting auxiliary latent variables which open the door to the use of the expectation-maximization (EM) algorithm. In the second approach, the iterative algorithm is derived directly in a bound optimization framework. In both cases, the resulting algorithms, which are very simple, alternate between a Fourier-based step and a wavelet-based step. Experimental results show that these algorithms achieve state-of-the-art performance on benchmark image deconvolution problems.

• Paulo Gonçalves - Diverging moments and parameter estimation

  Abstract: When dealing with finite size data sets of an unknown heavy tailed distributions, standard empirical estimators of moments will typically fail to reflect the theoretical divergence of moments and provide finite estimates for all order moments. We propose a wavelet-based estimator for the characteristic exponents $(C^{-},C^{+})$ of a random variable, which bound the interval of all orders $C^{-}<r<C^{+}$ with finite moment. This objective is achieved by deriving a theoretical equivalence between finiteness of moments and the local Holder regularity of the characteristic function at the origin, and by deriving a wavelet based estimation scheme which is particularly suited to characteristic functions.

• Jorge Silva - Wavelets and Applications

  Abstract: In this presentation we give a short overview of the theory of wavelets trying to compare it with the classical theory of Fourier series. We discuss the advantages of this approach pointing out some applications.

• Waldyr Oliva - A sphere rolling on a surface of revolution

  Abstract: Equations of motion for the problem. Reduction of the phase space using symmetries. Some geometric properties of the constraints.

• João Paulo Costeira - Correspondence problems in computer vision

  Abstract: Image-to-Image and Image-to-model (point) matching is a key issue in Computer Vision. It can be bluntly posed as the search problem of finding corresponding points in 2 images (ex. stereo vision) or in one image and a 2D or 3D model (object recognition). The main issues here are those of "typical problems of everyday life": high (huge) dimensionality, "high" nonlinearity. We will introduce one particular approach which casts the problem within an integer programming framework to motivate the discussion about the representation and algorithmic issues.

• João Xavier - Lower Bound on Intrinsic Variance of Estimators in Riemannian Manifolds

  Abstract: The well-known Cramér-Rao inequality places a lower bound on the variance of any unbiased estimator for a given parametric estimation problem. In the original formulation, the parameter set is an open set of a (flat) Euclidean space. Here, we discuss a generalization of the $\mathrm{CR}$-bound for the case where the parameter set is a Riemannian manifold $M$ and the variance of the estimators is computed with respect to the geodesic distance on $M$. The derived bound depends on the curvature of the manifold $M$ and differential-geometric generalizations of both the estimator bias and the Fisher information matrix of the parametric model. Numerical examples are presented to illustrate the tightness of the bound.

• Diogo Gomes - Optimal Mass Transport

  Abstract: We present the optimal transport problem and discuss several of its applications to image identification, shape optimization and nonlinear diffusions.