Skip to main navigation
Skip to Content
Computer Science
University of Toronto
U of T Portal
Student Support
Contact
About
Why Study CS at U of T
Career Options
History of DCS
Giving to DCS
Computer Science at UofT Mississauga
Computer Science at UofT Scarborough
Contact
Employment Opportunities for Faculty/Lecturers
How to Find Us
Undergraduate
Prospective Undergraduates
Current Undergraduates
Graduate
Prospective Graduate students
Current Graduate students
Research
Research Areas
Partner with us
People
Faculty
Staff
In Memoriam
Alumni and Friends
Honours & Awards
Women in Computer Science
Graduate Student Society
Undergraduate Student Union
Undergraduate Artificial Intelligence Group
Undergraduate Theory Group
News & Events
News
Events
Newsletter: @DCS Update
Alumni
Donate
You are viewing: >
Home
>
News & Events
>
Events
> NOV 20: Theory CS Seminar
About
Undergraduate
Graduate
Research
People
News & Events
NOV 20: Theory CS Seminar
Event date: Friday, November 20, 2009, at 11:00 AM
Location: Galbraith Bldg, Rm. 244
Speaker: Petros Drineas
Rensselaer Polytechnic Institute
Title: Sampling algorithms for L2 regression and applications
Abstract: L2 regression, also known as the least squares approximation problem, and more generally Lp regression, are fundamental problems that have numerous applications in mathematics and statistical data analysis. Recall that the over-constrained L2 regression problem takes as input an n x d matrix A, where n > d, and an n-vector b, and it returns as output a d-vector x such that ||Ax-b||_2 is minimized. Several randomized algorithms for this problem, each of which provides a relative-error approximation to the exact solution, are described. The first algorithm applies novel ``subspace sampling'' probabilities to randomly sample constraints and thus construct a coreset for the L2 regression problem. The second algorithm applies a random projection and uses a ``fast'' version of the Johnson-Lindenstrauss lemma to obtain an efficient approximation to the L2 regression problem. In this talk we will also discuss how such ideas can be applied to the Column Subset Selection Problem (CSSP).
This is joint work with C. Boutsidis, M.W. Mahoney, S. (Muthu) Muthukrishnan, and Tamas Sarlos.