Time & Place

• Lectures : Tuesday, 9-11 @ IFW B42.


• Exercises : Tuesday, 11-12 @ IFW B42.

Instructors

Lecturers: Bernd Gärtner, Joachim Giesen, Emo Welzl

Assistant: Andreas Razen

IFW B48.2 / Tel: (044) 632 74 22. e-mail: arazen@inf.ethz.ch

Course description

The course is concerned with approximate geometric methods for the analysis of large data sets represented by point clouds.

Data is being collected in order to draw conclusions from it, i.e. to discover relations, make extrapolations into the future, etc. More often than not, data comes as a set or sequence of points describing objects, with each coordinate representing some quantification of some feature. On a computer such data is just a sequence of 0's and 1's; the need to analyze and "understand" it calls for means to support the process. One way is to visualize the data. For example, a data set representing a number of people by their respective heights and weights can be drawn as a point set in the plane, and this drawing may reveal some correlation that could be approximated by a linear function.

For a wide range of applications (brain research, robotics, statistics, bioinformatics, character and speech recognition, computer graphics etc.) this approach is too simplistic, for various reasons. First of all, the size of the data may be huge (in the millions and billions, and sometimes so huge that we cannot even store it). And secondly, objects may have many features, giving rise to sets of dimension in the hundreds - and we know that simple visualization methods tend to fail starting in dimension 4. (Many features may in fact be redundant, but it is part of the endeavor to find out which ones.)

Many of the arising problems appear to be too hard to be solved exactly in an efficient fashion. The course discusses several approximate methods for the analysis of large high-dimensional data sets that have been developed over the last years in response to the issues indicated above. While we have applications in mind for the questions we address, we emphasize theoretical aspects in the solutions.

Methods we cover are random sampling, grid structures, core-sets, well separated pair decomposition, low distortion low-dimensional embeddings. Applications we address are shape and dimension analysis, nearest neighbor search, clustering etc.

Examples for specific questions arising in these applications are the following: for some point in d-space, what is its closest neighbor in the point cloud? What is the closest pair in the point cloud? What is the "best" grouping of the points in the cloud into k groups? Which subset of the point set of size k provides the "best" description of the point cloud? What is the dimensionality of the point cloud and what does dimensionality mean here? Can the point cloud be embedded into a lower-dimensional space while preserving many of its characteristics?

Procedures, Testat, Exercises

There is no obligation for you to solve the homework exercises, but we highly recommend that you do so. Writing the solutions up also teaches you to precisely formulate your ideas and communicate them such that others understand them. This ability is beneficial not just in mathematics but in (almost) any discipline.
Whatever you write up we will read and comment on.
Solving the exercises also helps you to prepare for the exam at the end of the course. Grading will solely be based on this oral exam (which will take place in fall 2005).

Language

English

Course material

(Updated Lecture Notes will be available soon!! --- Old version: [PDF] [PS])

Lectures	Lecture Notes (Handout)	Problems	Solutions
Lecture 1 March 29 (Introduction - ANN)	(See literature)	[No homework]	[No homework]
	(Apr 04)	(Apr 04)	(Apr 04)
Lecture 2 April 05 (ANN - Basic Geometry)	[PDF] [PS]	[PDF] [PS]
	(Apr 19)	(Apr 04)	(Apr 12)
Lecture 3 April 12 (Bounding volumes)	[PDF] [PS]	[PDF] [PS]
	(Apr 19)	(Apr 12)	(Apr 19)
Lecture 4 April 19 (Miniball-Approx.-Alg.)	[PDF] [PS]	[PDF] [PS]
	(Apr 19)	(Apr 19)	(Apr 26)
Lecture 5 April 26 (Quadratic Programming)	[PDF] [PS]	[PDF] [PS]
	(Apr 26)	(Apr 26)	(May 03)
Lecture 6 May 03 (Cuboids & Ellipsoids)	[PDF] [PS]	[PDF] [PS]
	(May 03)	(May 03)	(May 10)
Lecture 7 May 10 (Support Vector Machines)	[PDF] [PS]	[PDF] [PS]
	(May 31)	(May 11)	(May 25)
Lecture 8 May 17 (Quadtrees)	(See literature)	[PDF] [PS]	[discussed on May 24]
	(May 17)	(May 18)	(May 24)
Lecture 9 May 24 (WSPD)	(See literature)	[PDF] [PS]
	(May 24)	(May 24)	(May 31)
Lecture 10 May 31 (Applications of WSPD)	(See literature)	[PDF] [PS]
	(May 31)	(May 31)	(Jun 07)
Lecture 11 June 07 (ε-Nets and VC-Dimension)	(Material covered by Notes	[No homework]	[No homework]
	distributed on June 14)	(Jun 07)	(Jun 07)
Lecture 12 June 14 (Size of ε-Nets)	(Handout of Lecture Notes)	[PDF] [PS]
	(Jun 14)	(Jun 13)	(Jun 21)
Lecture 13 June 21 (ε-Nets - Directional width)	(Material covered by Notes	[PDF] [PS]
	below from June 28)	(Jun 21)	(Jun 28)
Lecture 14 June 28 (Core sets for direct. width)	[PDF] [PS]	[No homework]	[No homework]
	(Jun 28)	(Jun 28)	(Jun 28)

Further Literature

Sariel Har-Peled, Approximation Algorithms in Geometry , Lecture Notes.

For ANN (approximate the nearest neighbor) see chapter 2 and chapter 5.
For quadtrees see chapter 3.
For WSPD (well separated pairs decomposition) and its applications see chapter 4.

Applications and data sets

• Computer graphics

  A fundamental problem in computer graphic rendering is modeling how light is reflected from surfaces. A class of functions called bi-directional reflectance distribution functions (BRDFs) characterize the light transport at an idealized surface point. Traditionally researchers in graphics tried to model BRDFs by taking the physics of light transport for real materials into account. Another approach taken is to interpolate sample points measured from the real BRDF for some material. Notice that this means one either has to model or measure a BRDF for all materials involved in the scene that is to be rendered. Matusik, Pfister, Brand and McMillan took the sampling approach one step further. Firstly, they sample several real BRDFs such that each measured BRDF is represented by a high dimensional vector. The entirety of these vectors is a point cloud in some high dimensional Euclidean space. Then Matusik et al. apply linear and non-linear dimension reduction techniques to this point cloud in order to obtain a low dimensional representation that allows them to parameterize the space (manifold?) of all BRDFs. That is, they are able to synthesize BRDFs that never were sampled by interpolation from sampled BRDFs. Practically, they sampled BRDFs for more then 100 materials. For every material they had more than 20 million sample points that they compressed into a vector with roughly four million components. The data model generated from these vectors, i.e. from the point cloud consisting of roughly one hundred points in a space with more than four million dimensions, was a 15 dimensional non-linear manifold representation of the BRDF space. The data allowed to reconstruct the measured BRDFs very accurately (actually ten dimensions would have been sufficient for that) and to synthesize sufficiently many new BRDFs. The experimentally found dimension (around ten) of the BRDF space is in good accordance with the number free parameters in BRFD models based on the physics of light transport in media.
  Reference. W. Matusik, H. Pfister, M. Brand and L. McMillan. A Data-Driven Reflectance Model. In Proceedings of SIGGRAPH 2003.

• Visual speech recognition

  In visual speech recognition pioneered by Bregler and Omohundro a video of the speaker is used as a cue in addition to the traditional acoustic cues. Therefore a polygon with a fixed number of nodes is fitted to the lips of the speaker in each frame of the video. Every node of the polygon has has coordinates which gives rise to vector whose number of components is twice the number of nodes. These vectors form a point cloud that sample the so called "lip space" which has to be learned. The learned manifold is then used for tracking and extracting the lips, for interpolating between frames in an image sequence and for providing features for speech recognition. In their experiments Bregler and Omohundro fitted a polygon with 40 nodes to the lips, i.e., every polygon was represented by an 80 dimensional vector. It turned out that the point cloud sampled from the lip space (manifold?) could be described by a non-linear five dimensional model. The cues derived from this model significantly improved the performance of acoustic speech recognizers in degraded environments and was also tested on a purely visual lip reader.
  Reference. C. Bregler and S. M. Omohundro. Nonlinear manifold learning for visual speech recognition In Proceedings of ICCV 1995.

• Bioinformatics

  The genetic code can be decomposed into codon sequences which are triplets of bases (U,A,G,T). Some of the 64 different triplets are used to encode amino acids form which proteins are synthesized and some serve other purposes. The genetic code associates a set of sibling codons to the same amino acid, and some codons occur more frequently than others in gene sequence. Biased codon usage seems to be property of highly expressed genes which tend to use only a limited number of codons. Such a bias was for example observed in fast growing prokaryotes and eukaryotes. With every gene in a genome one can associate a 64 dimensional vector of relative codon usage. A genome that consists of n genes is then represented by a point cloud in 64 dimensional space. Biologist when given a genome which exhibits a codon bias are interested in getting reference sets of genes that characterize the bias. Carbone, Zinoyev and Kepes devised a simple algorithm to find such reference sets from the point cloud representing a genome.
  Reference. A. Carbone, A. Zinovyev and F. Kepes. Condon adaptation index as a measure of dominating codon bias In Bioinformatics 19(16).

• Neuroscience

  The brain is composed of large numbers of individual cells (neurons) that communicate among themselves to solve tasks parsing image or speech or generate accurate motor movements. Understanding how populations of cells work together is one of the paramount problems in neuroscience. Using new methods the activity pattern of large populations of cells can measured on millisecond time scales. Giving rise of a stream of 512 times 512 pixel images. Every image can be considered as a point in 512 times 512 dimensional space. Thus the stream gives rise to a point cloud. Kenet et al. discovered that the recorded images of activity generated in the visual cortex, without visual stimulation, resemble images of activity evoked by oriented patterns. This observation can quantified by analyzing the corresponding point clouds using dimension reduction techniques.
  Reference. T. Kenet, D. Bibitchkov, M. Tsodyks, A. Grinvald and A. Arieli. Spontaneously emerging cortical representations of visual attributes In Nature 425, 2003.
  (See also: Point Clouds in Imaging Science In SIAM News 37(7), 2004.)