CS: Compressive Sensing Workshop, ANR Memoire, CS of a phantom, Counter Braids on FPGAs, l_0 reconstruction, RIP-1 table, two talks and some humor

One could only wish Louis Armstrong was right.

From the Rice repository, Larry Carin and the other folks at Duke and AFRL are organizing a Compressive Sensing Workshop:

Compressive-Sensing Workshop

February 25 & 26, 2009

Location: Duke University

Sponsored by the AFRL ATR Center

Co-sponsored by AFOSR, ARO, DARPA, NGA and ONR

This workshop will bring together leading experts in the new field of compressive sensing (CS). The meeting will focus on new theory, algorithms and applications of CS. The format of the meeting will include formal talks, panel discussions and group interaction, as well as poster sessions. In addition to having talks from many of the leading CS researchers from academia, there will be talks from the members of the US government and industry, on directions for this new technology, including future research directions and programs.

The meeting is jointly organized by Lawrence Carin (Duke) and Gregory Arnold (AFRL), who are affiliated with the AFRL ATR Center in Dayton, Ohio.

The local Duke hosts for the workshop are Lawrence Carin, David Brady, Mauro Maggioni, Xiaobai Sun, and Rebecca Willet.

The following members of the academic community have accepted invitations to present talks:

• Rich Baraniuk, Rice
  
• Thomas Blumensath, University of Edinburgh (England)
  
• Rob Calderbank, Princeton
  
• Ronald Coifman, Yale
  
• Ronald Devore, U South Carolina
  
• Yonina Eldar, Technion (Israel)
  
• Donald Goldfarb, Columbia
  
• Mario Figueiredo, Instituto Superior Tecnico (Portugal)
  
• Kevin Kelly, Rice
  
• Jian Li, U Florida
  
• James McClellan, Georgia Tech
  
• Kevin Murphy, UBC (Canada)
  
• Mark Neifeld, U Arizona
  
• Rob Nowak, U Wisconsin
  
• Stanley Osher, UCLA
  
• George Papanicolaou, Stanford
  
• Lee Potter, Ohio State
  
• Justin Romberg, Georgia Tech
  
• Guillermo Sapiro, U Minnesota
  
• Matthias Seeger, Max Planck Institute for Informatics (Germany)
  
• Joel Tropp, Caltech
  
• Martin Wainwright, UC Berkeley
  
• David Wipf, UC San Francisco
  

There will also be talks from members of the US government, including DARPA and NGA, as well as talks from members of industry.

Participation: The meeting is open to all who wish to participate. If interested in being considered for a contributed talk or poster, please contact Lawrence Carin, at lcarin@ece.duke.edu

Student presentations: There will be a session dedicated to talks by graduate students. The presentation deemed to be of highest technical content, and presented best, will receive a $500 prize. Please contact Lawrence Carin at lcarin@ece.duke.edu if you would like to participate in the grad-student session.

Schedule: The detailed agenda is being finalized, and will be posted soon. Talks will start at 8am on February 25, and end on February 26 at 5pm. The hotel room block is for the evenings of February 24 and 25, and the hotel is offering a special rate for February 26 for those who wish to stay an additional night.

Registration: There will be a $250 registration fee, which covers all meeting participation, as well as breakfast and lunch on Feb. 25 and 26, and dinner on Feb. 25. The registration fee will be collected at the meeting. For members of the AFRL ATR Center as well as graduate students with valid student ID, the registration fee will be half-priced.

Location and housing: The meeting will be held at the Washington Duke Inn and Golf Club. Room reservations may be made by calling 800-443-3853; when making reservations, mention the group name "AFRL" to get the special rates that have been negotiated. For government personnel, the government per-diem rate of $95/night will be honored; for non-government guests the rate is $125/night. To get these rates, reservations must be completed by February 6, 2009. We have negotiated a very special rate for this meeting, so please make reservations by this date; nightly rates are much higher after that date.

Banquet: A dinner will be held on February 25, with this included in the registration fee. There will be a performance by The Pitchforks.

Travel: The Raleigh-Durham airport (RDU) is a short distance from Duke University. It is recommended that guests take a cab ride from the airport, as there will be no need for transportation on the Duke campus

It was added to the calendar.

The French Agence Nationale de la Recherche just came out with a new RFP entitled DOMAINES ÉMERGENTS ET PROGRAMME PHARE «MEMOIRE». I  note the mention of Compressed Sensing:

Une problématique liée à la fusion et la représentation de grand volume de données ainsi qu’à la possibilité d’acquérir des données de plus en plus résolues, doivent conduire à repenser la problématique de l’échantillonnage ainsi que celle de la compression. De nouvelles voies, à l’image des techniques de compressed sensing doivent être proposées et développées.

Proposals are due February 26th, 2009. More information can be found here.

Thales has two internships for people coming from french engineering schools in the area of compressed sensing. I hesitate to put them in the jobs section as it seems to be very narrow in terms of the type of people they are looking for. The announcements are here and here.

Jon Dattorro tells me that the article mentioned here  is now available at:

http://meboo.convexoptimization.com/Meboo.html

on the right hand side of the side in Revision History, one can see: Latest electronic version: v2008.11.03 (756 pages). Click on this document and search for "Compressive sampling of a phantom". The associated Matlab code is here.

For those of you not reading the blog directly, I have updated yesterday's entry to reflect on an inaccurate statement I made on Leo Grady's upcoming presentation. Thanks Leo for the correction!

While we are on the subject of l_0 reconstruction, I noticed an updated presentation in wikimization by Christine Law and Gary Glover entitled Toward 0-norm Reconstruction, and a Nullspace Technique for Compressive Sampling. Since the earlier version, I note a fuller presentation and the appearance of a reference to Stephane Chretien's work.

Also in the same wikimization page, I note an expanded version of Anna Gilbert's talk entitled Combining Geometry and Combinatorics: A Unified Approach to Sparse Signal Recovery. Namely the famous table showing the progress over time of the matrices found the combinatorial approach:

As a visual person, I like simpleton color coding scheme. Thanks Anna! There is also more in the application side of the presentation.

With the recent mention of Counter Braids and their connection to CS, I forgot to mention its implementation on hardware in Prototyping Counter Braids on NetFPGA by Jianying Luo, Yi Lu  and Balaji Prabhakar. The abstract reads:

We recently proposed Counter Braids, an SRAM-only counter architecture for high-speed per-flow counting. Accurate per-flow counting was deemed complex and expensive because of the need for large arrays of counters operating at very high link speed (e.g. 40 Gbps). A naive algorithm needs an infeasible amount of SRAM to store both the counters and a flow-to-counter association rule, so that arriving packets can update corresponding counters at link speed. Counter Braids avoids the storage of flow-to-counter association by using random graphs generated on-the fly with hash functions. The counts of all flows remain compressed in SRAM at all times and incoming packets update directly the compressed counts, that is, no decompressing is necessary for updates. The compressed counts are transferred to software at the end of a measurement epoch and almost all flows are recovered exactly with a message passing decoding algorithm. One significant advantage of Counter Braids is the ease of implementation in hardware and the simplicity of updates. By prototyping Counter Braids on a NetFPGA board, we prove these claims in this paper. This particular implementation of Counter Braids achieves a 30-fold reduction in space compared to a naive hash-table based implementation.

It looks we may just have to wait for three years before we have those on our desk as new FPGAs are coming out with some new technology developement promising to make them cheaper (Memristors Make Chips Cheaper).

And finally, two talks and some humor:

Midwest Theory Day,  Dec. 6, 2008, 10am-5:00pm, Fine Barr Forum, Allen Center, Northwestern U., Evanston IL.Guangwu Xu (U. of Wiscconsin, Milwaukee), "Restricted Isometry Properties and Compressed Sensing":

In this talk, I will discuss constrained $\ell_1$ minimization methods in a unified framework for the recovery of high dimensional sparse signals in three settings: noiseless, bounded error and Gaussian noise. I will describe some improvements to the existing results in the literature by weakening the RIP conditions and tightening the error bounds. The improvement on the conditions shows that signals with larger support can be recovered accurately. I will also discuss connections between restricted isometry property and the mutual incoherence property, and present some extensions to the results of Candes, Romberg and Tao, and Donoho, Elad, and Temlyakov.

Joint work with Tony Cai and Jun Zhang

Maryam Fazel, University of Washington, Parsimonious Models and Matrix Rank Minimization, December 2 , 2008, 10:30am - 11:20am, Room 125 EEB

Abstract

In many engineering applications, notions such as order or dimension of a model can be expressed as the rank of an appropriate matrix. To choose simple models, we seek low-rank matrices. The matrix rank minimization problem arises in linear system identification, statistical modeling of random processes, and data dimensionality reduction.

The rank minimization problem is known to be computationally intractable. 

This talk discusses a convex relaxation based on semidefinite programming, and presents recent results in understanding under what conditions the relaxation is guaranteed to work. We discuss connections with the field of Compressed Sensing, which has demonstrated that sparse signals and images can be recovered from apparently incomplete sets of measurements. We ask what other objects or structures might also be recovered from incomplete, limited measurements, and present results on recovering matrices from partial information. Such problems are generally underdetermined, but when the matrix is known to be low rank or approximately low rank, the search for solutions becomes feasible. Applications arise in machine learning, system identification, and signal processing.

Laurent Jacques is looking for some input on how to catch a Lion with compressed sensing. You are welcome to add your solution!

Credit video: Igor Carron. Credit Song: Louis Armstrong.