BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Fast Algorithms for Structured Sparsity
DTSTART:20160623T111500
DTEND:20160623T121500
DTSTAMP:20260407T110837Z
UID:f80db76994b0cd3219286b0c9223996567d4a7baffb909927be36b58
CATEGORIES:Conferences - Seminars
DESCRIPTION:Piotr Indyk\, MIT\nAbstract: \nSparse representations of sign
 als (i.e.\, representations that have only few non-zero or large coefficie
 nts) have emerged as powerful tools in signal processing theory\, algorith
 ms\, machine learning and other applications. However\, real-world signals
  often exhibit rich structure beyond mere sparsity. For example\, a natura
 l image\, once represented in the wavelet domain\, often has the property 
 that its large coefficients occupy a subtree of the wavelet hierarchy\, as
  opposed to arbitrary positions. A general approach to capturing this type
  of additional structure is to model the support of the signal of interest
  (i.e.\, the set of indices of large coefficients) as belonging to a parti
 cular family of sets. Computing a sparse representation of the signal then
  corresponds to the problem of finding the support from the family that ma
 ximizes the sum of the squares of the selected coefficients. Such a modeli
 ng approach has proved to be beneficial in a number of applications includ
 ing compression\, de-noising\, compressive sensing and machine learning. H
 owever\, the resulting optimization problem is often computationally diffi
 cult or intractable\, which is undesirable in many applications where larg
 e signals and datasets are commonplace.\nIn this talk\, I will outline som
 e of the past and more recent algorithms for finding structured sparse rep
 resentations of signals\, including piecewise constant approximations\, tr
 ee-sparse approximations and graph-sparse approximations. The algorithms b
 orrow several techniques from combinatorial optimization (e.g.\, dynamic p
 rogramming)\, graph theory\, and approximation algorithms. For many proble
 ms the algorithms run in (nearly) linear time\, which makes them applicabl
 e to very large datasets.\nJoint work with Chinmay Hegde and Ludwig Schmid
 t.​\nBio: \nPiotr Indyk is a Professor of Electrical Engineering and Co
 mputer Science at MIT. He joined MIT in 2000\, after earning PhD from Stan
 ford University. Earlier\, he received Magister degree from Uniwersytet Wa
 rszawski in 1995. Piotr’s research interests lie in the design and analy
 sis of efficient algorithms. Specific interests include: high-dimensional 
 computational geometry\, sketching and streaming algorithms\, sparse recov
 ery and compressive sensing. He has received the Sloan Fellowship (2003)\,
  the Packard Fellowship (2003) and the Simons Investigator Award (2013). H
 is work on sparse Fourier sampling has been named to Technology Review “
 TR10” in 2012\, while his work on locality-sensitive hashing has receive
 d the 2012 ACM Kanellakis Theory and Practice Award.​ 
LOCATION:BC 01 https://plan.epfl.ch/?room==BC%2001
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR