Tata Institute of Fundamental Research
Dyadic Rounding
Seminar
Speaker:
Amit Deshpande
Microsoft Research Lab.,
“Scientiaâ€
196/36 2nd Main
Sadashivnagar
Bangalore 560 080
Date:
Thursday, 21 Apr 2011 (all day)
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
`Dyad' means a pair, `dyadic' means binary, and in this talk I'll present some simple algorithms for rounding real vectors to 0-1 vectors without losing much. In particular, we can round eigenvectors of real matrices to 0-1 vectors with only a small log-factor loss. This leads to interesting decompositions of real matrices into a small number of cut matrices -- each of which looks like a block of ones with zeroes all around (up to some multiple) -- and can be thought of as rounding the singular value decomposition (joint work with Ravindran Kannan and Nikhil Srivastava).
The talk will be elementary and all are encouraged to attend.
| Speaker: | Amit Deshpande Microsoft Research Lab., “Scientia†196/36 2nd Main Sadashivnagar Bangalore 560 080 |
| Date: | Thursday, 21 Apr 2011 (all day) |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
`Dyad' means a pair, `dyadic' means binary, and in this talk I'll present some simple algorithms for rounding real vectors to 0-1 vectors without losing much. In particular, we can round eigenvectors of real matrices to 0-1 vectors with only a small log-factor loss. This leads to interesting decompositions of real matrices into a small number of cut matrices -- each of which looks like a block of ones with zeroes all around (up to some multiple) -- and can be thought of as rounding the singular value decomposition (joint work with Ravindran Kannan and Nikhil Srivastava).
The talk will be elementary and all are encouraged to attend.
The talk will be elementary and all are encouraged to attend.