[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

THEORY SEMINAR
 
 
Tuesday, April 2, 2013
3:00 p.m.
Ryerson 251
 
Vladimir Temlyakov
University of South Carolina    
www.math.sc.edu/people/temlyakov.html
 
Title:  Greedy algorithms in compressed sensing
 
Abstract: We study sparse representations and sparse approximations with respect to incoherent dictionaries. We address the problem of designing and analyzing greedy methods of approximation. A key question in this regard is: How to measure efficiency of a specific algorithm? Answering this question we prove the Lebesgue-type inequalities for algorithms under consideration. A very important new ingredient of the talk is that we perform our analysis in a Banach space instead of a Hilbert space. It is known that in many numerical problems users are satisfied with a Hilbert space setting and do not consider a more general setting in a Banach space. There are known arguments that justify interest in Banach spaces. In this talk we give one more argument in favor of consideration of greedy approximation in Banach spaces. We introduce a concept of M-coherent dictionary in a Banach space which is a generalization of the corresponding concept in a Hilbert space. We analyze the Quasi-Orthogonal Greedy Algorithm (QOGA), which is a generalization of the Orthogonal Greedy Algorithm (Orthogonal Matching Pursuit) for Ba-nach spaces. It is known that the QOGA recovers exactly S-sparse signals after S iterations provided S < (1 + 1/M)/2. This result is well known for the Orthogonal Greedy Algorithm in Hilbert spaces. The following question is of great importance: Are there dictionaries in Rn such that their coherence in `np is less than their coherence in `n2 for some p 2 (1;1)? We show that the answer to the above question is "yes". Thus, for such dictionaries, replacing the Hilbert space `n2 by a Banach space `np we improve an upper bound for sparsity that guarantees an exact recovery of a signal.
 
Refreshments will be served prior to the talk in Ry. 255 at 2:30 p.m.
 
Host: Prof. Alexander Razborov and Statistics
 
*Refreshments will be served prior to the talk at 2:30 in Ryerson 255*

ALSO:


Tuesday, April 2, 2013
4:15 p.m.
Ryerson 251
 
Boris Kashin
Steklov Math. Inst.
www.mi.ras.ru/~kashin/
 
Title: “Dirichlet polynomials in connection with widths and compressed sensing”
 
Abstract:
Let  Φ= {φi} be a system of elements of Banach space X. We define Φ-width of order N of the set A c X as a value of the optimal approximation (with respect to norm in X) of the set A by the subspace generated by N arbitrary elements of the system Φ. This notion in the case when Φ is a trigonometric system was introduced in the 1974 by R. Ismagilov. The talk is devoted to the Φ-width estimates, their connections with “compressed sensing” and their application to the investigations of polynomials with respect to the system 
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20130328/e790b9b8/attachment.htm