CS: Compressed Sensing for Fusion Frames, Combinatorial Compressed Sensing, The Geometry of Generalized Binary Search, Ranging Imager,TCS and finance.

Here are a few papers of related interest for the week-end.

Compressed Sensing for Fusion Frames by Petros Boufounos, Gitta Kutyniok, and Holger Rauhut. The abstract reads:

Compressed Sensing (CS) is a new signal acquisition technique that allows sampling of sparse signals using significantly fewer measurements than previously thought possible. On the other hand, a fusion frame is a new signal representation method that uses collections of subspaces instead of vectors to represent signals. This work combines these exciting new fields to introduce a new sparsity model for fusion frames. Signals that are sparse under the new model can be compressively sampled and uniquely reconstructed in ways similar to sparse signals using standard CS. The combination provides a promising new set of mathematical tools and signal models useful in a variety of applications. With the new model, a sparse signal has energy in very few of the subspaces of the fusion frame, although it needs not be sparse within each of the subspaces it occupies. We define a mixed `1/`2 norm for fusion frames. A signal sparse in the subspaces of the fusion frame can thus be sampled using very few random projections and exactly reconstructed using a convex optimization that minimizes this mixed `1/`2 norm. The sampling conditions we derive are very similar to the coherence and RIP conditions used in standard CS theory.

Then there is a presentation by Mark Iwen on Combinatorial Compressed Sensing: Fast algorithms with Recovery Guarantees. Of noted interest is the application section at the very end where one considers learning a function with multiple parameters:


A situation that is also the subject of much interest in calibration or machine learning in general. Let us note that another way of performing some type of function learning is through the Experimental Probabilistic Hypersurface (more details can be found here). Not really related to compressive sensing but of interest nonetheless since it deals with learning functions:

The Geometry of Generalized Binary Search by Robert Nowak. The abstract reads:

This paper investigates the problem of determining a binary-valued function through a sequence of strategically selected queries. The focus is an algorithm called Generalized Binary Search (GBS). GBS is a well-known greedy algorithm for determining a binary-valued function through a sequence of strategically selected queries. At each step, a query is selected that most evenly splits the hypotheses under consideration into two disjoint subsets, a natural generalization of the idea underlying classic binary search and Shannon-Fano coding. GBS is used in many applications including channel coding, experimental design, fault testing, machine diagnostics, disease diagnosis, job scheduling, image processing, computer vision, and machine learning. This paper develops novel incoherence and geometric conditions under which GBS achieves the information-theoretically optimal query complexity; i.e., given a collection of N hypotheses, GBS terminates with the correct function in O(logN) queries. Furthermore, a noise tolerant version of GBS is developed that also achieves the optimal query complexity. These results are applied to learning multidimensional threshold functions, a problem arising routinely in image processing and machine learning.

And here are two architectures for cameras to determine ranges:

• Annular folded optic imager (paper)
• Coded Aperture Photography

They are interesting in that they don't have your usual Point Spread Function (or transfer function).

Finally, I have always been impressed by some results in TCS (Theoretical Computer Science) and always wonders what type of impact they will have in the civil society, here are two in particular:

• The security of knowing nothing by Bernard Chazelle
• Computational Complexity and Information Asymmetry in Financial Products by Sanjeev Arora, Boaz Barak, Markus Brunnermeier and Rong Ge. Of note, the excellent blog entry by Dick Lipton entitled: Helping Wall Street Cheat With Theory explaining the paper. One may be interested in the FAQ for the paper.
  

At some point, I am sure we'll also see some application of Compressive Sensing in the area of low latent trading or high or ultra-high frequency trading as it is called these days.