Past Numerical Analysis Group Internal Seminar

31 January 2017
14:30
Mihai Cucuringu
Abstract

We consider the classic problem of establishing a statistical ranking of a set of n items given a set of inconsistent and incomplete pairwise comparisons between such items. Instantiations of this problem occur in numerous applications in data analysis (e.g., ranking teams in sports data), computer vision, and machine learning. We formulate the above problem of ranking with incomplete noisy information as an instance of the group synchronization problem over the group SO(2) of planar rotations, whose usefulness has been demonstrated in numerous applications in recent years. Its least squares solution can be approximated by either a spectral or a semidefinite programming (SDP) relaxation, followed by a rounding procedure. We perform extensive numerical simulations on both synthetic and real-world data sets (Premier League soccer games, a Halo 2 game tournament and NCAA College Basketball games) showing that our proposed method compares favorably to other algorithms from the recent literature.

We propose a similar synchronization-based algorithm for the rank-aggregation problem, which integrates in a globally consistent ranking pairwise comparisons given by different rating systems on the same set of items. We also discuss the problem of semi-supervised ranking when there is available information on the ground truth rank of a subset of players, and propose an algorithm based on SDP which recovers the ranks of the remaining players. Finally, synchronization-based ranking, combined with a spectral technique for the densest subgraph problem, allows one to extract locally-consistent partial rankings, in other words, to identify the rank of a small subset of players whose pairwise comparisons are less noisy than the rest of the data, which other methods are not able to identify. 
 

  • Numerical Analysis Group Internal Seminar
31 January 2017
14:00
Nick Trefethen
Abstract

The trigonometric interpolants to a periodic function in equispaced points converge if is Dini-continuous, and the associated quadrature formula, the trapezoidal rule, converges if is continuous.  What if the points are perturbed?  Amazingly little has been done on this problem, or on its algebraic (i.e. nonperiodic) analogue.  I will present new results joint with Anthony Austin which show some surprises.

 

  • Numerical Analysis Group Internal Seminar
24 January 2017
14:30
Behnam Hashemi
Abstract


Using a variational approach applied to generalized Rayleigh functionals, we extend the concepts of singular values and singular functions to trivariate functions defined on a rectangular parallelepiped. We also consider eigenvalues and eigenfunctions for trivariate functions whose domain is a cube. For a general finite-rank trivariate function, we describe an algorithm for computing the canonical polyadic (CP) decomposition, provided that the CP factors are linearly independent in two variables. All these notions are computed using Chebfun. Application in finding the best rank-1 approximation of trivariate functions is investigated. We also prove that if the function is analytic and two-way orthogonally decomposable (odeco), then the CP values decay geometrically, and optimal finite-rank approximants converge at the same rate.
 

  • Numerical Analysis Group Internal Seminar
29 November 2016
14:30
Dmitry Belyaev
Abstract


There are several classes of random function that appear naturally in mathematical physics, probability, number theory, and other areas of mathematics. I will give a brief overview of some of these random functions and explain what they are and why they are important. Finally, I will explain how I use chebfun to study these functions.
 

  • Numerical Analysis Group Internal Seminar

Pages