Topics in High Dimensional Geometry
Math 582D Winter 2016
- Instructor:
Hari Narayanan
-
E-mail:
harin@math.washington.edu
-
Office: B301 Padelford
-
Office Hours: After class
or by appointment
- Syllabus: [pdf]
This course will revolve around the following two topics.
1. Fitting low dimensional manifolds to high dimensional data:
The field of manifold learning is based on the hypothesis that high dimensional data
often lie in the vicinity of a low dimensional submanifold having controlled curvature
and volume. We will develop the theory behind an algorithm for testing this hypothesis
with statistical guarantees and bounds on the run-time, which do not depend on the
dimension of the ambient space.
Topics covered will include work on Whitney interpolation, random
projections and the Johnson-Lindenstrauss Lemma, material on Dudley’s entropy
integral and some of
Federer’s work on the reach of subsets of Euclidean space.
2. High dimensional convex bodies:
Let K be a convex body in R^n
be a convex body containing the unit ball, and contained in a ball of radius
R. Suppose there is an oracle, which when presented with a point x outputs whether or
not x belongs to K. Given such an oracle, we would like to do the following:
i. Produce a random sample from K from a distribution that is close to the uniform
distribution in total variation distance.
ii. Produce an approximation of the volume of K that holds with high probability.
iii. Optimize a convex function f (given by an oracle) over K.
We will discuss a number of Markov Chain algorithms for i. above, including Ball
walk introduced by Lovasz and Simonovits and Hit-and-Run developed by Lovasz and
Vempala. We will discuss Markov Chain Monte Carlo algorithms for ii. above. We will
use sampling from distributions that are more and more peaked around the optimum as
a method of addressing iii.
Prerequisites: Comfort with probability, linear algebra and analysis.
- Optional Texts: Elias Stein, Singular Integrals and Differentiability Properties of Functions.
- Keith Ball, An Elementary Introduction to Modern Convex Geometry. [pdf]
- Raghavan Narasimhan, Lectures on Topics in Analysis, Tata Institute of Fundamental research (1965), [pdf]
- Grading: One Midterm Proposal and one Final Report
- Course Materials:
- Laszlo Lovász and Miklos Simonovits, Random walks in a convex body and an improved volume algorithm, Random Structures and Alg. 4 (1993), 359-412. [pdf]
- Laszlo Lovász, Hit-and-run mixes fast [Math. Programming, series A 86 (1999), 443-461.] [pdf]
- Dimitris Bertsimas and Santosh Vempala, Solving Convex Programs by Random Walks J. ACM (2004) [pdf]
- Ravindran Kannan and Hariharan Narayanan, Random Walks on Polytopes and an Affine Interior Point Method for Linear Programming,
Math. of OR. (2012) [pdf]
- Hariharan Narayanan, Randomized Interior Point Methods for Sampling and Optimization,
To appear in Ann. of Appl. Prob. (2016) [arxiv link]
- Herbert Federer, Curvature Measures, Trans. Amer. Math. Soc. 93 (1959), 418-491,
[pdf]
- Charles Fefferman, Sanjoy Mitter and Hariharan Narayanan, Testing the Manifold Hypothesis, to appear in Journal of the AMS (2016),
[pdf]
,