Ky Vu (École Polytechnique, France)

Using random projections for dimension reduction in optimization
Wednesday 18 May 2016 at 15.00, JCMB 6206

Abstract

Random projection is a very useful technique for reducing data dimension and has been used widely in numerical linear algebra, text and image processing, computer science, machine learning and so on. A random projection is often defined as a random matrix constructed in certain ways such that it preserves many important features, such as distances, inner products, volumes, of the data set. One of the most famous examples is the Johnson-Lindenstrauss lemma, in which a set of m points can be projected by a random projection, to an Euclidean space of dimension O(log n) whilst still ensures that the inner distances between them approximately unchanged.

In this talk, I will use random projections to study a number of important optimization problems such as linear and integer programming, convex membership problems and derivative-free optimization. We will try to convince that random projection is a very promising tools for many other problems as well.

Seminars by year

Current 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996