ARC Colloquium: Luis Rademacher: Ohio State University

*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************

Event Details
  • Date/Time:
    • Tuesday September 7, 2010 - Wednesday September 8, 2010
      11:00 am - 10:59 am
  • Location: Klaus 1116W, Georgia Tech, Atlanta GA
  • Phone:
  • URL:
  • Email:
  • Fee(s):
    N/A
  • Extras:
Contact

Elizabeth Ndongi

Summaries

Summary Sentence: Efficient volume sampling for row/column subset selection

Full Summary: No summary paragraph submitted.

Abstract:

We give efficient algorithms for volume sampling, i.e., for picking k-subsets of the rows of any given matrix with probabilities proportional to the squared volumes of the simplices defined by them and the origin (or the squared volumes of the parallelepipeds defined by these subsets of rows). This solves an open problem from the monograph on spectral algorithms by Kannan and Vempala. Our first algorithm for volume sampling k-subsets of rows from an m-by-n matrix runs in O(kmn^\omega \log n) arithmetic operations and a second variant of it for (1+\epsilon)-approximate volume sampling runs in O(mn \log m k^2/\epsilon^2 + m \log^{\omega} m k^{2\omega+1}/\epsilon^{2\omega} \log(k \epsilon^{-1} \log m)) arithmetic operations, which is almost linear in the size of the input (i.e., the number of entries) for small k. Our efficient volume sampling algorithms imply several interesting results for low-rank matrix approximation.

Additional Information

In Campus Calendar
No
Groups

ARC

Invited Audience
No audiences were selected.
Categories
No categories were selected.
Keywords
No keywords were submitted.
Status
  • Created By: Elizabeth Ndongi
  • Workflow Status: Published
  • Created On: Nov 16, 2011 - 6:44am
  • Last Updated: Oct 7, 2016 - 9:56pm