CS: Eureqa: a solution, PSF determination, L_0 quantum chip?, Greedy dictionary, CS for MRI, CS MIMO radar , low rank matrix.

Andrew Gelman has finally found a solution but he had to provide some help to Eureqa.

If you recall, one of the big issue of compressive sensing imaging system is the need to go through a lengthy calibration process to find the system's PSF. This is not just a problem in Compressive Sensing as witnessed in this latest paper entitled: Accurate photometry with adaptive optics in the presence of anisoplanatic effects with a sparsely sampled PSF by Rainer Schodel.

Olivier Grisel mentioned an Efficient L0-norm regularization with Adiabatic Quantum Computing by some of the folks at Google. From their entry:

The theory paper on which the demonstration is based can be found on the arXiv and a report describing the details of the implementation is here.

I'd have to look at it deeper. If the chip can actually perform l_0 search, then Compressive Sensing becomes even more relevant as we could now focus on how to acquire data incoherently without having to care too much about the reconstruction solvers.


Volkan Cevher let me know about his recent paper entitled: Greedy Dictionary Selection for Sparse Representation by himself and Andreas Krause. The abstract reads:

We discuss how to construct a dictionary by selecting its columns from multiple candidate bases to allow sparse representation of signals. By sparse representation, we mean that only a few dictionary elements, compared to the ambient signal dimension, can be used to well-approximate the signals. We formulate both the selection of the dictionary columns and the sparse representation of signals as a joint combinatorial optimization problem. The proposed combinatorial objective maximizes variance reduction over the set of signals by constraining the size of the dictionary as well as the number of dictionary columns that can be used to represent each signal. We show that if the columns of the candidate bases are incoherent, our objective function satisfies approximate submodularity. We exploit this property to develop efficient greedy algorithms with well-characterized theoretical performance. Applications of dictionary selection include denoising, inpainting, and compressive sensing. We evaluate our approach to reconstruct dictionaries from sparse samples, and also apply it to an image inpainting problem.

I found the following on the interwebs and arxiv, enjoy:

Spread spectrum for compressed sensing techniques in magnetic resonance imaging by Yves Wiaux, Gilles Puy, R. Gruetter, J-P. Thiran , D. Van De Ville, and Pierre Vandergheynst.

We advocate the use of a chirp modulation for magnetic resonance imaging (MRI) in the perspective of defining the best possible imaging techniques for sparse or compressible signals in the context of the recent theory of compressed sensing. We analyze the related spread spectrum phenomenon and we prove its effectiveness in enhancing the overall quality of image reconstruction. We also study its impact at each scale of decomposition in a wavelet sparsity basis. Our preliminary results rely both on theoretical considerations related to the mutual coherence between the sparsity and sensing bases, as well as on numerical simulations from synthetic signals.

Reduced Complexity Angle-Doppler-Range Estimation for MIMO Radar That Employs Compressive Sensing by Yao Yu, Athina Petropulu, H. Vincent Poor, H. Vincent Poor. The abstract reads:

The authors recently proposed a MIMO radar system that is implemented by a small wireless network. By applying compressive sensing (CS) at the receive nodes, the MIMO radar super-resolution can be achieved with far fewer observations than conventional approaches. This previous work considered the estimation of direction of arrival and Doppler. Since the targets are sparse in the angle-velocity space, target information can be extracted by solving an l1 minimization problem. In this paper, the range information is exploited by introducing step frequency to MIMO radar with CS. The proposed approach is able to achieve high range resolution and also improve the ambiguous velocity. However, joint angle-Doppler-range estimation requires discretization of the angle-Doppler-range space which causes a sharp rise in the computational burden of the l1 minimization problem. To maintain an acceptable complexity, a technique is proposed to successively estimate angle, Doppler and range in a decoupled fashion. The proposed approach can significantly reduce the complexity without sacrificing performance.

Sparse and Low-Rank Matrix Decomposition Via Alternating Direction Methods by Xiaoming Yuan, Junfeng Yang. The abstract reads:

The problem of recovering the sparse and low-rank components of a matrix captures a broad spectrum of applications. Authors in [4] proposed the concept of "rank-sparsity incoherence" to characterize the fundamental identifiability of the recovery, and derived practical sufficient conditions to ensure the high possibility of recovery. This exact recovery is achieved via solving a convex relaxation problem where the L1 norm and the nuclear norm are utilized for being surrogates of the sparsity and low-rank. Numerically, this convex relaxation problem was reformulated into a semi-definite programming (SDP) problem whose dimension is considerably enlarged, and this SDP reformulation was proposed to be solved by generic interior-point solvers in [4]. This paper focuses on the algorithmic improvement for the sparse and low-rank recovery. In particular, we observe that the convex relaxation problem generated by the approach of [4] is actually well-structured in both the objective function and constraint, and it fits perfectly the applicable range of the classical alternating direction method (ADM). Hence, we propose the ADM approach for accomplishing the sparse and low-rank recovery, by taking full exploitation to the high-level separable structure of the convex relaxation problem. Preliminary numerical results are reported to verify the attractive efficiency of the ADM approach for recovering sparse and low-rank components of matrices.

Finally, Stephane Mallat is giving a course entitled: A Sparse Wavelet Tour of Signal Processing. The slides are as follows:

• 1. Sparse Representations in Signal and Image Processing.
• 2. Redundant Dictionaries and Pursuit Algorithms.
• 3. Super-Resolution for Inverse Problems with Sparsity.
• 4. Compressed Sensing.
• 5. Dictionary Learning and Source Separation.

Of note, one can also read Super-resolution Bandlet Upconversion for HDTV.