BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Sparse recovery using sparse matrices  
DTSTART:20090625T151500
DTSTAMP:20260502T005428Z
UID:16bd5f26e88181ec44abbc0cbf1e3af7227254c753e60b9b9eddfcfd
CATEGORIES:Conferences - Seminars
DESCRIPTION:Prof. Piotr Indyk\, MIT\nOver the recent years\, a new *linear
 * method for compressing high-dimensional data has been discovered. For an
 y high-dimensional vector x\, its *sketch* is equal to Ax\, where A is a c
 arefully designed m x n matrix (possibly chosen at random). Although typic
 ally the sketch length m is much smaller than the number of dimensions n\,
  the sketch often contains enough information to recover a *sparse approxi
 mation* to x. At the same time\, the linearity of the sketching method is 
 very convenient for many applications\, such as data stream computing and 
 compressed sensing. The major sketching approaches can be classified as ei
 ther combinatorial (using sparse sketching matrices) or geometric (using d
 ense sketching matrices). Traditionally they have achieved different trade
 -offs\, notably between the compression rate and the running time. In this
  talk we show that\, in a sense\, the combinatorial and geometric approach
 es are based on different manifestations of the same phenomenon. This conn
 ection will enable us to obtain several novel algorithms and constructions
 \, including the first known algorithm that provably achieves the optimal 
 measurement bound and near-linear recovery time. Prof. Indyk's homepage
LOCATION:BC 01 https://plan.epfl.ch/?room==BC%2001
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR