The talk will discuss recent literature on randomized algorithms
for finding low-rank approximations to matrices. One typical result
says that we can get an get an approximation to any matrix from just a
random subset of rows and a random subset of columns [for a careful
choice of sampling probabilities], where the error is measured in the
standard norms.

Besides traditional numerical applications, many combinatorial
applications of low-rank approximations have been developed
recently. For graph problems, the matrices involved are the adjacency
matrices of graphs. Similar techniques have been used also for Boolean
Satisfiability and other Constraint satisfaction problems, where
instead of matrices, we have tensors in general and one does not
have recourse to Linear Algebra.

Lecture #10812

Need help? Visit our help pages at http://www.msri.org/communications/vmath/hints

Streaming Video

This is a high quality streaming video encoded with MPEG-4 and with 640x480 resolution.

Windows and Mac users, QuickTime 6.5 or later required
Linux users, please see our Linux Help Page on how to view our streaming videos

Follow this link to --- Watch the Video Now Via Streaming Video ---

Download QuickTime File

You can download the QuickTime file here. Right click on the link and "Save As..." to save to your local computer.

• 10812-10812-QuickTime.mov (564 MB)

Download MPEG File

You can download the MPEG file here. Right click on the link and "Save As..." to save to your local computer.

• 10812-10812-MPEG-1 DVD.mpg (635 MB)

Create a DVD

You can download the video and audio files here. Please note that you need both files to create a DVD. Right click on the link and "Save As..." to save to your local computer. You can find instructions on how to create a DVD on our help page at http://www.msri.org/communications/vmath/author

• 10812-10812-DVD PCM Audio.aiff (465 MB - Audio Only)
• 10812-10812-MPEG-2 120min High Quality Encode.m2v (1060 MB - Video Only)

Buy the DVD

If none of the options work for you, you can always buy the DVD of this lecture. The videos are sold at cost for $20USD (shipping included).

See more of our video archive on our main VMath - Streaming Video page.