Quick links

Finding structure with randomness

Date and Time
Tuesday, March 29, 2016 - 12:30pm to 1:30pm
Computer Science Small Auditorium (Room 105)
CS Department Colloquium Series
Elad Hazan

Computer scientists have long known that randomness can be used to improve the performance of algorithms. A familiar application is the process of dimension reduction, in which a random map transports data from a high-dimensional space to a lower-dimensional space while approximately preserving some geometric properties. By operating with the compact representation of the data, it is possible to produce approximate solutions to certain large problems very efficiently.

It has been observed that dimension reduction has powerful applications in numerical linear algebra and numerical analysis. This talk will discuss randomized techniques for constructing standard matrix factorizations, such as the truncated singular value decomposition. In practice, the algorithms are so effective that they compete with—or even outperform—classical algorithms. These methods are already making a significant impact in large-scale scientific computing and learning systems.

Joint work with P.-G. Martinsson and N. Halko.

Follow us: Facebook Twitter Linkedin