Second Workshop on High-dimensional Approximation

Portfolio Construction with Asymmetric Dependence Structures
Jamie Alcock University of Queensland

We outline a method of portfolio selection incorporating asymmetric dependency structures using copula functions. Assuming normally distributed marginal returns, we illustrate how asymmetric return correlations affect the efficient frontier and subsequent portfolio performance under a dynamic rebalancing framework. Implementing this methodology within the context of tactically allocating a set of market indices, we demonstrate several key findings. First we establish the manner by which the efficient frontier constructed under asymmetric dependence differs from a Mean-Variance frontier. By establishing a paper portfolio based upon these differences, we find that asymmetric correlation structures do have real economic value. The primary source of this economic value is the ability to better protect portfolio value and reduce the size of any erosion in return relative to the normal portfolio when asymmetric return correlations are accounted for.

A superposition model for function reconstruction
Presentation (PDF)

Jürgen Braun Universität Bonn

Kolmogorov showed in 1957 that any multivariate function f can be represented as a superposition of one-dimensional functions. The proof of this fact, however, was not constructive and it was not clear how to choose the inner and outer functions respectively. The objective of our work is to use a constructive proof of this representation theorem which was basically given by Sprecher in 1996, to obtain a model for the reconstruction of higher dimensional functions. This model then requires only the determination of the one-dimensional outer functions, since the inner functions are defined explicitly and independent of f. This talk will first review the basic facts of the Kolmogorov superposition theorem in the version of Sprecher including the definition of the inner functions. Based on the exact representation of f a spline model will be introduced that approximates the objective function. Since function reconstruction from given data points is an ill posed problem, we use Tikhonov regularisation which leads to a regularisation network. Because of the special structure of the inner functions and the superposition of inner and outer functions, however, some attention has to be paid on the choice of the regularisation term. Finally some numerical results will be presented.

The myth of equidistribution for high-dimensional simulation
Presentation (PDF)
Richard Brent Australian National University
A pseudo-random number generator (RNG) might be used to generate w-bit random samples in d dimensions if the number of state bits is at least dw. Some RNGs perform better than others and the concept of equidistribution has been introduced in the literature in order to rank different RNGs. In this talk I shall define what it means for a RNG to be (d,w)-equidistributed, and then argue that equidistribution is not necessarily a desirable property. In other words, when comparing RNGs, the concept of equidistribution is a red herring.

Multi-scale modelling of biochemical systems by the chemical master equation
Presentation (PDF)

Kevin Burrage University of Queensland

Biochemical reactions underlying genetic regulation are often modelled as a continuous-time, discrete-state, Markov process, and the evolution of the associated probability density is described by the so-called chemical master equation (CME). However the CME is typically difficult to solve, since the state-space involved can be very large or even countably infinite. Until now this has meant that the direct computation of the probability density function (pdf) associated with chemical kinetics that takes into account intrinsic noise has not been computationally feasible. Recently a finite state projection method (FSP) that truncates the state-space has been suggested by Munsky and Khammash and shown to be effective on small scale problems. Presented in this talk is a Krylov FSP algorithm based on a combination of state-space truncation and inexact matrix-vector product routines. This allows larger-scale models to be studied and solutions for larger final times to be computed in a realistic execution time. We compare the efficiency of this technique with trajectorial approaches such as the Stochastic Simulation Algorithm and also show how a strong trajectory can be computed directly from the pdf computed by the CME. Numerical results indicate that this new approach can be fast and is extendable to large biological models.

This is joint work with MARKUS HEGLAND (ANU), SHEV MACNAMARA (UQ), AND ROGER B. SIDJE (UQ)

Concentration of measure in nonlinear filters
Presentation (PDF)

Fred Daum Raytheon Company

Nonlinear filtering is an important application of approximation theory in high dimensions. In particular, we must approximate the conditional probability density of a high dimensional state vector in real time. Nonlinear filters generally suffer from the curse of dimensionality, but for many practical problems the conditional probability density enjoys concentration of measure similar to a Gaussian density, and thus particle filters can beat the curse of dimensionality by using a good proposal density. We show numerical experiments to illustrate this phenomenon for dense problems with dimension d = 1 to 20, and we derive a simple formula to explain the computational complexity of particle filters using good proposal densities. In contrast, without a good proposal density, the computational complexity of particle filters is exponential in dimension, as predicted by Oh's formula. Most of the research on approximation theory attempts to beat the curse of dimensionality by exploiting smoothness or sparseness or low effective dimension, but none of these features is evident in the nonlinear filter problems considered here. We also show how to reduce computational complexity for nonlinear filtering problems that enjoy concentration of measure but which do not have a good proposal density available; in particular, we use the adjoint method both for solving the Fokker-Planck equation, as well as to implement Bayes' rule turned into an ODE using a homotopy.

Filtering complex information in financial markets
Presentation (PDF)

Tiziana Di Matteo Australian National University
In [Tumminello et al. PNAS vol. 102, n. 30 (2005) 10421] we introduced a novel method to filter relevant information from complex systems of several interacting elements generating correlation-based skeleton networks. In this talk we will introduce this filtering correlation procedure, its application to different financial data sets and we will demonstrate how this procedure is efficient in filtering relevant information about the clustering of the system and its hierarchical structure. By investigating topological properties such as the average length of shortest paths, the betweenness and degree on different networks at different time horizons we will show that the market is progressively structured as a function of the time. [joint work with T. Aste, M. Tumminello, and R. N. Mantegna]

An Efficient Sparse Grid Method for the high dimensional Fokker-Planck-Equation
Presentation (PDF)

Christian Feuersänger Universität Bonn

Numerical methods to solve the high-dimensional fokker-planck-equation are limited by the so called "curse of dimension", which restricts applications to three, maybe four space dimensions. We propose a sparse grid method for higher dimensions in order to benefit from the reduced grid complexity O(N log^d-1 N) instead of O(N^d) for classical methods. We employ timestepping schemes with variable step-size control in time and a sparse grid galerkin method in space for each time step. New matrix-vector-product algorithms for the semi-orthogonal prewavelet basis reduce the typically required 2^d grid traversals to just a constant number. We present efficient hash-based storage techniques which allow to solve the linear systems without influence of the dimension to storage requirements. While the number of iterations is known to be independent of the mesh width, its dependence on the problem dimension is discussed based on numerical experiments. The accuracy of the method is analysed by means of higher dimensional model problems. Numerical results for an application in finance demonstrate the usefulness of the method.

An optimised sparse grid combination technique for eigenvalue problems
Presentation (PDF)

Jochen Garcke Technische Universität Berlin

Recently an optimised combination technique for regression applications was introduced. The original combination technique employs solutions on a certain sequence of (small) grids, the sparse grid solution is then obtained by addition of these partial solutions with combination coefficients which depend on the involved grids. For regression this approach shows instabilities in certain situations and is not guaranteed to converge with higher discretisation levels. In the case of the optimised combination technique the coefficients also depend on the function to be representend, a nonlinear approach, with this approach the instabilities disappear. In this talk I will transfer the idea of an optimised sparse grid combination technique to eigenvalue problems. When solving eigenvalue problems it is not obvious which eigenfunctions out of the partial eigenspaces to combine, i.e. how to normalise the partial eigenfunctions. Using the approach of an optimised combination technique, where the combination coefficients depend on the underlying problem as well, this problem is rectified. Numerical results for the Schrödinger equation in the case of hydrogen are shown.

Fair and Efficient Valuation of Executive Stock Options
Presentation (PDF)

Thomas Gerstner Universität Bonn

Many companies offer their executives a conditional amount of shares if they stay with the company for a prescribed period of time. Typically, the exact amount of shares is determined by a performance criterion such as the company's gain over the period or its ranking among the competition. Such bonus programs induce uncertain future costs for the company. The fair value of these programs can be determined using financial derivatives which include the performance criterion in their payoff, so-called performance-dependent options. By the martingale approach, the fair price of such options is given as a high-dimensional integral. Usually, the integrand is discontinuous, though, which makes accurate solutions difficult to achieve by numerical approaches. In this talk, we derive a representation of the price of performance-dependent options which only involves the evaluation of several multivariate normal distributions. This solution uses novel tools from computational geometry which facilitate the fast enumeration of all cells in a hyperplane arrangement and its orthant decomposition. We show that the arising normal distributions can be efficiently computed using sparse grid quadrature methods. This way, the complexity and the dimensionality of the integration problem can be significantly reduced which allows the efficient pricing of performance-dependent options even for large benchmarks, which is illustrated in several numerical examples.

On the numerical solution of the master equations with sparse grids
Presentation (PDF)

Markus Hegland Australian National University

The understanding of complex biological pathways faces the challenge of many randomly interacting components. The evolving probability distributions describing populations of such systems are modelled by the Chapman/Kolmogorov or chemical master equations. These probability distributions are used to describe the location and range of clusters of the population. They are also used for maximum likelihood methods for the determination of model parameters describing the propensities. However, the representation of these models does have to address the curse of dimensionality. In this talk we will discuss ways how this curse can be dealt with using sparse grid approximation techniques, and, in general, discuss numerical approximations used to solve the chemical master equations.

Filling in the Gaps - Local Data Approximation in Geodesy
Presentation (PDF)

Kerstin Hesse University of New South Wales

In the first part of this talk, I will discuss (local) data approximation in geodesy, and we will consider the particular example of modelling the earth's gravitational potential (at the earth's surface) from satellite data. This part of the talk relates to work done in my Ph. D. Thesis and provides an introduction to local data approximation on the sphere. In the second part of my talk, I will discuss (local) data approximation on the sphere with radial basis functions. I will present some recent joint results with Ian H. Sloan and Quoc Thong Le Gia about local radial basis function approximation on a spherical cap. - This talk is aimed at a general audience and does not assume any prior knowledge about radial basis functions or approximation on the sphere.

Sobol' sequences with `good' two-dimensional projections
Presentation (PDF)

Stephen Joe University of Waikato

A numerical technique for approximating integrals over the s-dimensional unit cube is to make use of quadrature points from Sobol' sequences. An implementation of such a technique may be found in Algorithm 659 in the Collected Algorithms of the ACM. The original implementation was extended by Joe and Kuo in 2003 to go from 40 dimensions to 1111 dimensions. This involved using more primitive polynomials and finding more so-called `direction numbers'. This extended implementation did not guarantee that all the two-dimensional projections were `good'. Since there are certain applications in which the integrands are of low effective dimension, it would be useful to have Sobol' sequences with better two-dimensional projections. This talk gives an outline of our ideas for finding new direction numbers which attempt to achieve this. This is based on treating Sobol' sequences as a special case of (t,s)-sequences in base b. This is joint work with Frances Kuo of the University of New South Wales.

Diagonal plus Upper or Lower Triangular Semiseparable Matrices and Fast Gegenbauer Polynomial Transforms
Presentation (PDF)

Jens Keiner University of New South Wales
We develop an efficient algorithm for computing the eigendecomposition of diagonal plus upper or lower triangular semiseparable matrices for which the eigenvalues are always known a-priori. By using fast summation techniques, we obtain an O(n²) algorithm for computing the eigenvectors explicitly and an O(n log n) algorithm for applying the eigenvector matrix, or optionally its inverse, to an arbitrary vector. Both algorithms are approximate, i.e. accurate up to a prefixed accuracy epsilon. This extends an existing divide-and-conquer algorithm for symmetric diagonal plus semiseparable matrices. As an application, we develop a fast algorithm for converting expansion coefficients between different representations in terms of Gegenbauer polynomials.

Classification and Prediction with Supervised Independent Component Regression
Presentation (PDF)

Inge Koch University of New South Wales

For high-dimensional data the number of variables needs to be reduced before conventional classification and regression techniques can be applied. Principal Component Regression selects a reduced number of predictors from the original variables, but these predictors can be unrelated to the outcome variables, as they are chosen merely by their contribution to variance. We propose a method which combines variable ranking with a selection of the best reduced subset of predictors. Variable ranking is achieved by canonical correlation analysis, and the selection of the best subset is accomplished with independent component analysis. The method is applicable to classification and regression problems with multivariate response variables. We demonstrate the performance of the method on real data and simulation studies and show that it compares favourably with recent supervised classification and prediction techniques.

Multivariate approximation over reproducing kernel Hilbert spaces
Presentation (PDF)

Frances Kuo University of New South Wales

This talk aims to give a taste of the analysis of Multivariate Approximation in the Information Based Complexity (IBC) framework. No prior knowledge is assumed. I will touch on different theoretical settings (the worst case, the average case, and the randomised settings), and the connection between errors measured in various norms (the L₂ norm, the L_∞ norm, and the general L_p norm). In some cases optimal or near-optimal algorithms have been known for some time, while in others new results are still being developed. There are also many open problems waiting to be explored. The talk will embrace new results from joint works with Ian Sloan, Grzegorz Wasilkowski and Henryk Woźniakowski.

Local approximation on the sphere using shifts of a positive definite kernel
Presentation (PDF)

Quoc Thong Le Gia University of New South Wales

In this talk, we consider the local interpolation problem on the unit sphere Sⁿ ⊂ Rⁿ⁺¹ using scattered data inside a spherical cap of small angular radius. The interpolant is constructed using shifts of a positive definite kernel on the unit sphere. Error estimates in terms of Sobolev norms H^s(Sⁿ) of the target function and the local mesh norm of the scattered data sets will be discussed. This is joint work with Kerstin Hesse and Ian Sloan.

Generating well distributed and well separated points on higher dimensional spheres
Presentation (PDF)

Paul Leopardi University of Sydney

One subproblem in approximation, interpolation and quadrature on high dimensional spheres is to generate a finite set of points (a spherical code) with prescribed geometrical properties, such as mesh norm, packing radius, energy, etc. The centre points of the Recursive Zonal Equal Area Sphere Partition are both well distributed and well separated and therefore have a well behaved energy. Some aspects of the generation and the properties of these points are described in this talk.

Lattice sequences: from fast construction to rapid application
Presentation (PDF)

Dirk Nuyens K.U. Leuven

For high dimensional numerical integration, lattice rules have long been seen as point sets with a predetermined number of points which had to be used all at once. This is highly impractical when one does not know in advance how many points are needed. Recently a lot of work has been done to overcome this problem and theoretical results have shown that it is possible to construct a lattice rule which is extensible in the number of points as well as in the number of dimensions. In a recent paper with Ronald Cools and Frances Y. Kuo a fast construction algorithm was presented which can construct a lattice sequence in time O(s n (log(n))2), where n is the number of points and s is the number of dimensions (n is a prime power). Such a lattice sequence can be used point by point and guarantees near optimal point distributions for intermediate powers of the prime base. The point set can actually be looked at as a collection of smaller lattice rules, starting at and spanning powers of the base, similar to a (t, m, s)-net. In another recent paper by Josef Dick, Friedrich Pillichshammer and Ben Waterhouse an alternative construction method is presented and more theoretical results are obtained. This talk will present an overview on the fast construction of lattice rules in different shift-invariant weighted spaces, leading to the construction of lattice sequences. Because of the fast construction it has become possible to construct a rule for any suitable weighted space that one might need, without having to rely on stored tables. We will therefore not only argue that, because of the sequence usage, lattice rules are now on par with, e.g., Sobol' points, but that they are indeed a sophisticated tool for the approximation of high dimensional integrals which can even be fine tuned to the problem area itself. On the practical side there are also a lot of points in favour of lattice rules. E.g., the long forgotten trick of periodisation can be used to speed up convergence from O(n^-1) to O(n^-a), a > 1, if the number of dimensions is only moderately high. This will be shown for the approximation of the multivariate normal distribution in 5 dimensions, which can then be directly used for the pricing of, e.g., lookback options and outperformance options. An extra benefit of lattice sequences is that they are easy to program and generation of the points is almost as fast as generating just pseudo random numbers.

Simulation of High-dimensional Models in Finance
Presentation (PDF)

Eckhard Platen University of Technology Sydney

This presentation will describe a generalised no-arbitrage setting for the modelling of financial markets. In the case of multi-factor jump diffusion models it will discuss the tasks of scenario simulation and Monte Carlo simulation. Challenges for the computation of option prices, hedge ratios and risk measures in high-dimensional multi-factor models will be highlighted. Higher order numerical methods for the solution of stochastic differential equations with jumps will be systematically described. Finally, Markov chain approximations for multi-factor financial market models will be investigated.

Valuation of multi-asset credit derivatives
Presentation (PDF)

Marek Rutkowski University of New South Wales

The goal of the talk is to present some methods and results related to the valuation of basket credit derivatives in the general framework of multiple credit ratings for reference credit instruments. We are thus concerned with the modelling of dependent credit migrations, in particular, with modelling of dependent defaults. We first give an overview of the most liquid credit derivatives: credit default swaps (CDS), first-to-default swaps (FTDS), CDS indices, collateralized debt obligations (CDO) and CDO squared (CDO2). It is worth noting that some of these contracts refer to a large number (between 100 and 1000, say) of reference credit names. Next, we briefly present the market approach to basket credit derivatives, based on the industry standard one-factor Gaussian copula model. It is well known, however, that this simplistic model is not capable of fitting the market data for CDOs. We then discuss a fairly general Markovian model that, in principle, nests several models previously studied in the literature. In particular, this framework covers jump-diffusion processes, as well as some classes of Levy processes. The model allows us to incorporate several credit names and thus it is suitable for valuation of basket credit products in the multiple credit ratings environment.

Inexact uniformisation for computing transient distributions of Markov chains. Application to solving the chemical master equation modelling biochemical reactions
Presentation (PDF)

Roger B. Sidje University of Queensland

The uniformisation method (also known as randomisation) is a numerically stable algorithm for computing transient distributions of a continuous time Markov chain. When the solution is needed after a long run or when the convergence is slow, the uniformisation method involves a large number of matrix-vector products. Despite this, the method remains very popular due to its ease of implementation and its reliability in many practical circumstances. Because the matrix-vector product is the most time consuming part of the method, its overall efficiency in solving large-scale problems can be significantly enhanced if the matrix-vector product is made more economical. This talk will describe how to incorporate a new relaxation strategy in the uniformisation method to compute the matrix-vector products only approximately. We analyse the error introduced by these inexact matrix-vector products, and discuss strategies to refine the accuracy of the relaxation while reducing the execution cost. Numerical experiments drawn from computer systems and biochemical systems are given to show that significant computational savings are achieved in practical applications.

Ups and downs of lattice rules for high dimensional integration
Presentation (PDF)

Ian Sloan University of New South Wales

This talk will briefly describe some recent successes of lattice rules for high dimensional integration problems, including the ability to construct (by the fast component-by-component, or CBC, algorithm) lattice rules of good quality that model particular problems by the choice of suitable "weights". On the other hand, the last part of the talk will show that the use of so-called "finite-order" weights can lead to unsatisfactory results, including convergence to the wrong answer.

Direct Optimisation of Ranking Measures

Alex Smola National ICT Australia

Web page ranking and collaborative filtering require the optimisation of sophisticated performance measures. Current Support Vector approaches are unable to optimise them directly and focus on pairwise comparisons instead. We present a new approach which allows direct optimisation of the relevant loss functions. This is achieved via structured estimation in Hilbert spaces. It is most related to Max-Margin-Markov networks optimisation of multivariate performance measures. Key to our approach is that during training the ranking problem can be viewed as a linear assignment problem, which can be solved by the Hungarian Marriage algorithm. At test time, a sort operation is sufficient, as our algorithm assigns a relevance score to every (document, query) pair. Experiments show that the our algorithm is fast and that it works very well.

Mathematical modelling of the MAP kinase signal transduction pathway

Tianhai Tian University of Queensland

The mitogen-activated protein (MAP) kinase pathway transmits signals from externally activated receptors into the nuclear to regulate a wide range of physiological responses, including cell proliferation, apoptosis, cell differentiation, and tissue development. This signal transmission module consists of a three-tiered kinase cascade: an input node (MAP kinase kinase kinase or Raf) phosphorylates and activates an internal node (MAP kinase kinase or MEK), which in turn phosphorylates and activates the output node (a MAP kinase or ERK). Activated ERK proteins translocate into nuclear to generate biological outputs by phosphorylating and regulating a wide array of substrates, including transcription factors, kinases and phosphatases. Although the principal hierarchy of this signal pathway and its activation sequence is well known, recent experimental discoveries provide more and more information for the protein-protein interactions and positive/negative regulatory loops. The kinetic property of the MAP kinase network is much more complicated than previously thought. In recent years, a number of mathematical models have been developed for providing testable predictions and insights into signalling events. However, the vast majority of existing models are based on the assumption of spatial homogeneity and biochemical reactions are assumed to occur in the cytosol only. In this talk we will discuss the mathematical modelling of the MAP kinase pathway based on the most recently experimental discoveries indicating that the cascade reactions fire in a spatially heterogeneous reactor.

Don't bank on Monte Carlo!
Presentation (PDF)

Ben Waterhouse University of New South Wales

In recent years there has been an explosion in the number and complexity of derivative contracts being actively traded around the world. These contracts are based on the underlying movements of interest rates, foreign exchange rates, as well as commodity and equity prices. The pricing of such derivatives is an important problem in mathematical finance. The problems usually take the form of an integral, where a pay-off function is integrated over all possible asset price paths under some probability distribution. While there are analytical solutions to a limited number of these pricing problems, most problems in practice must be solved numerically. One of the most popular ways of numerically solving these problems is by way of the Monte Carlo (MC) method. This involves simulating random asset prices and the corresponding value of the pay-off function. As the number of random samples taken increases, the approximation should converge to the true solution. The MC method has proved to be very popular because the convergence of the error is independent of the dimension of the problem. Many problems in the financial sector involve very high dimensional integrals. A key weakness of the MC method is the relatively slow rate of convergence. Quasi-Monte Carlo (QMC) methods are methods which are very similar to MC methods, except that the paths are chosen deterministically, rather than randomly. Historically, QMC methods have performed poorly on problems where the dimension was large, known often as the "curse of dimensionality". However, it is possible to re-formulate many of the standard high-dimensional problems as a problem of very low effective dimension which can be easily handled by the QMC methods. We will see that by using techniques such as the Brownian Bridge construction, or the Principal Components Analysis construction, that QMC can massively outperform MC. Further new ideas for the improvement of QMC performance will be discussed.

Smoothness and Tractability of Multivariate Approximation
Presentation (PDF)

Henryk Woźniakowski Columbia University, University of Warsaw, University of Jena

We consider multivariate approximation for smooth classes of d variate functions. Let n(ε ,d) denote the minimal number of linear functionals that is necessary for solving the d variate approximation problem to within ε. Typically, n(ε ,d) goes to infinity as ε goes to zero but the speed of convergence of n(ε ,d) decreases with the increased smoothness of functions. For example, for infinitely differentiable functions, for any positive r we have n(ε ,d)=o(ε ^-r). Tractability means that n(ε ,d) does not depend exponentially on d. Does large or infinite smoothness imply tractability? This is the question we address in our talk. It turns out that the answer depends on the norm of the target space and in many cases is negative. That is, we have the curse of dimensionality even for infinite smoothness since n(ε ,d) depends exponentially on d. The talk is based on joint work with Erich Novak.

Regularity properties and the sparse grid approximation of electronic wavefunctions
Presentation (PDF)

Harry Yserentant Technische Universität Berlin

With the work of Schrödinger and Heisenberg in 1926, quantum mechanics found its final form and the complete mathematical description of atoms and molecules had become possible. Dirac commented this with the words "The underlying physical laws necessary for the mathematical theory of a large part of physics and the whole chemistry are thus completely known, and the difficulty is only that the exact application of these laws leads to equations much too complicated to be soluble." The reason is the high dimensionality of the Schrödinger equation. Its solutions depend on 3N variables for a system consisting of N particles, three spatial coordinates for each particle. Although very sophisticated and highly successful simplified models accessible to a numerical treatment have been developed during the last decades forming the basis of a whole branch of chemistry, from a mathematical point of view the situation has not much changed since Dirac's time. It is shown in this talk how a refined regularity theory for the electronic Schrödinger equation and modern principles of approximation theory and numerical analysis could help to change this situation and why the construction of true numerical methods for the Schrödinger equation could come into reach now.

A GMP-based implementation of Schoenhage-Strassen's large integer multiplication algorithm
Presentation (PDF)

Paul Zimmermann INRIA

Schoenhage-Strassen's algorithm is one of the best known algorithms for multiplying large integers. Implementing it is a challenging task, since many other algorithms rely on it as a subroutine. We present here a new implementation based on the GMP library. The following ideas and techniques were used: faster arithmetic modulo 2ⁿ+1, improved cache locality, Mersenne transforms, Chinese Remainder Reconstruction, the sqrt(2) trick, Harley's and Granlund's tricks, improved tuning. We also discuss some ideas we tried but which did not yield any improvement. [joint work with Torbjorn Granlund, Alexander Kruppa, Pierrick Gaudry]