[Colloquium] 11/18 Distinguished Lecture Series: Piotr Indyk, Massachusetts Institute of Technology

[Mary Marre via Colloquium]

*Distinguished Lecture Series:  *


*Piotr Indyk, Massachusetts Institute of Technology* ​
[image: Inline image 2]

Friday, November 18, 2016 at 11:00 am

*Toyota Technological Institute at Chicago*

*6045 S. Kenwood Avenue*

*Room #526**​*
*/530**Piotr Indyk* <https://people.csail.mit.edu/indyk/>
Professor,
Computer Science and Artificial Intelligence Lab,

Massachusetts Institute of Technology


------------------------------


*Title:* Fast Algorithms for Structured Sparsity

*Abstract:* Sparse representations of signals (i.e., representations that
have only few non-zero or large coefficients) have emerged as powerful
tools in signal processing theory, algorithms, machine learning and other
applications. However, real-world signals often exhibit rich structure
beyond mere sparsity. For example, a natural 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
popular 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 particular family of sets. Computing a
sparse representation of the signal then corresponds to the problem of
finding the support from the family that maximizes the sum of the squares
of the selected coefficients. Such a modeling approach has proved to be
beneficial in a number of applications including compression, de-noising,
compressive sensing and machine learning. However, the resulting
optimization problem is often computationally difficult or intractable,
which is undesirable in many applications where large signals and datasets
are commonplace.

In this talk, I will outline some of the past and more recent algorithms
for finding structured sparse representations of signals, including
piecewise constant approximations, tree-sparse approximations and
graph-sparse approximations. If time allows, I will also mention our recent
work that generalizes  sparse supports to arbitrary subspace
approximations, enabling applications such as  low-rank approximation of
matrices. The algorithms borrow several techniques from combinatorial
optimization (e.g., dynamic programming), graph theory, and approximation
algorithms. For many problems the algorithms run in (nearly) linear time,
which makes them applicable to very large datasets.

Joint work with Chinmay Hegde and Ludwig Schmidt.

*Bio:* Piotr joined MIT in September 2000, after earning PhD from Stanford
University. Earlier, he received Magister degree from Uniwersytet
Warszawski in 1995. As of July 2010, he holds the title of Professor in the
Department of Electrical Engineering and Computer Science.

Piotr's research interests include algorithms for high-dimensional
geometric problems, algorithms using sublinear time and/or space and
streaming algorithms.


*Host:* Julia Chuzhoy <http://ttic.uchicago.edu/~cjulia>, *cjulia at ttic.edu*
<cjulia at ttic.edu>




Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 504*
*Chicago, IL  60637*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20161111/6546da00/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image.png
Type: image/png
Size: 59527 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20161111/6546da00/attachment-0001.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: TTIC_Distinguished Lecture Series 2016.pdf
Type: application/pdf
Size: 1019591 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20161111/6546da00/attachment-0001.pdf>