BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/575
DTSTAMP:20230914T125930Z
SUMMARY:Fast and Efficient Algorithms for Sparse Recovery: A General Framew
 ork
DESCRIPTION:Speaker: Mayank Bakshi (The Chinese University of Hong Kong\nIn
 stitute of Network Coding\nShatin\, NT\nHong Kong SAR China)\n\nAbstract: 
 \nAbstract: Sparse Recovery refers to a broad collection of techniques tha
 t aim to exploit sparsity to dramatically reduce the "cost" of reconstruct
 ing a low dimensional "sparse" dataset embedded in a prohibitively high di
 mensional space. While sparse recovery techniques have been around for a l
 ong time\, the seminal works on Compressive Sensing by Candes\, Tao\, and 
 Donoho\, have renewed interest in this area -- especially among informatio
 n theorists. Formally\, consider an unknown  "k-sparse vector" 'x'\, i.e.
 \, a 'n'-length vector with at most 'k' non-zero coordinates. A typical Sp
 arse Recovery problem involves performing m measurements on 'x' to obtain 
 a vector 'y=A(x)'.  The goal is to be able to minimize 'm' while being ab
 le to reconstruct 'x' from 'y' efficiently. The function 'A(x)' may be lin
 ear (e.g. compressive sensing) or non-linear (e.g. phase retrieval).\n\nIn
  this talk\, we will discuss a new framework -- "picking and peeling" -- f
 or fast and efficient algorithms for four important sparse recovery proble
 ms -- compressive sensing\, compressive phase retrieval\, group testing\, 
 and network tomography. We will begin the exposition through a small puzzl
 e and use it to explain the key ideas of picking and peeling. Building upo
 n this insight\, we will next describe our compressive sensing algorithm S
 HO-FA (for SHOrt and FAst) which achieves a decoding complexity of O(k) wh
 ile using only O(k) measurements (this is the fastest possible performance
  in the order sense). Next\, we will briefly describe our algorithms for t
 he other three problems. For each of these problems\, our algorithms are e
 ither order-optimal or near-optimal both in terms of two metrics - the num
 ber of measurements and the time complexity of decoding. Finally\, we will
  examine another metric for performance - the energy required by the circu
 it that implements these algorithms. Surprisingly\, even algorithms that a
 re efficient in terms of time complexity are no longer efficient in terms 
 of decoding energy. We derive a novel lower bound on the decoding energy r
 equired in compressive sensing and outline a new algorithm that matches th
 is bound upto a constant factor (this talk is based on joint works with Si
 dharth Jaggi\, Minghua Chen\, Pulkit Grover\, Sheng Cai\, Tongxin Li\, and
  Mohammad Jahangoshahi).\n\nBio: Prof Mayank Bakshi is affiliated with the
  Institute of Network Coding (INC) at the Chinese University of Hong Kong.
  He finished his PhD from California Institute of Technology in 2011 and w
 as a Postdoctoral Scholar at INC from 2012 to 2014. Prior to this\, he did
  his B. Tech and M.Tech from IIT Kanpur in 2003 and 2005 respectively. He 
 is interested in a variety of Information Theoretic problems including Spa
 rse Recovery\, Secure Network Coding\, and Network Data Compression.\n
URL:https://www.tcs.tifr.res.in/web/events/575
DTSTART;TZID=Asia/Kolkata:20150219T113000
DTEND;TZID=Asia/Kolkata:20150219T123000
LOCATION:D-405 (D-Block Seminar Room)
END:VEVENT
END:VCALENDAR