COSC 49.11 Metric Embedding and Sketching

In data analysis we can often assume the input is drawn from a metric space associated with some well-behaved distance function. In such scenario one can hope to find an alternative representation — an embedding — of the input data without sacrificing the distance information too much. To our surprise, not only this is possible, but often times one can also perform a sketching to reduce the size and amount of the data required. This seminar-style course is aimed to introduce the various ways to encode metric spaces in a succinct fashion with minimal distortion, suitable for their algorithmic purposes. Naturally, due to the vast amount of work and literature in the area, the topics covered in this class will be biased towards the interest and expertise of the instructor.

Prerequisite

COSC 30, COSC 31, and at least one course in probability (i.e. Math 20 or COSC 49.10). COSC 36 is recommended.

Degree Requirement Attributes

Dist:QDS

The Timetable of Class Meetings contains the most up-to-date information about a course. It includes not only the meeting time and instructor, but also its official distributive and/or world culture designation. This information supersedes any information you may see elsewhere, to include what may appear in this ORC/Catalog or on a department/program website. Note that course attributes may change term to term therefore those in effect are those (only) during the term in which you enroll in the course.