CS: Dic learning, Accelerated Dense Random Projections, MCA and more.

We have several papers today. Many are not directly related to compressive sensing but are still part of the same themes, especially when it comes to dictionary learning. Here we go:

Parametric Dictionary Design for Sparse Coding by Mehrdad Yaghoobi Laurent Daudet, Mike Davies, The abstract reads:

This paper introduces a new dictionary design method for sparse coding of a class of signals. It has been shown that one can sparsely approximate some natural signals using an overcomplete set of parametric functions, e.g. [1], [2]. A problem in using these parametric dictionaries is how to choose the parameters. In practice these parameters have been chosen by an expert or through a set of experiments. In the sparse approximation context, it has been shown that an incoherent dictionary is appropriate for the sparse approximation methods. In this paper we first characterize the dictionary design problem, subject to a constraint on the dictionary. Then we briefly explain that equiangular tight frames have minimum coherence. The complexity of the problem does not allow it to be solved exactly. We introduce a practical method to approximately solve it. Some experiments show the advantages one gets by using these dictionaries.

Edo Liberty's thesis entitled Accelerated Dense Random Projections is here. The defense slides are here.

Jalal Fadili has just updated his webpage with new papers this week-end. Here the new ones I have not covered yet. The last two are for a French audience. Asa general observation,I have always found it fascinating that greedy got translated into "glouton" (glutton) even though both of them are cardinal sins :-). Anyway, here we go:

Image decomposition and separation using sparse representations: an overview by M. Jalal Fadili, Jean-Luc Starck, Jerome Bobin, Yassir Moudden. The abstract reads:

This paper gives essential insights into the use of sparsity and morphological diversity in image decomposition and source separation by overviewing our recent work in this field. The idea to morphologically decompose a signal into its building blocks is an important problem in signal processing and has far-reaching applications in science and technology. Starck et al. [1], [2] proposed a novel decomposition method - Morphological Component Analysis (MCA) - based on sparse representation of signals. MCA assumes that each (monochannel) signal is the linear mixture of several layers, the so-called Morphological Components, that are morphologically distinct, e.g. sines and bumps. The success of this method relies on two tenets: sparsity and morphological diversity. That is, each morphological component is sparsely represented in a specific transform domain, and the latter is highly inefficient in representing the other content in the mixture. Once such transforms are identified, MCA is an iterative thresholding algorithm that is capable of decoupling the signal content. Sparsity and morphological diversity have also been used as a novel and effective source of diversity for blind source separation (BSS), hence extending the MCA to multichannel data. Building on these ingredients, we will overview the Generalized MCA (GMCA) introduced by the authors in [3], [4] as a fast and efficient BSS method. We will illustrate the application of these algorithms on several real examples. We conclude our tour by briefly describing our software toolboxes made available for download on the Internet for sparse signal and image decomposition and separation.

MCALab: Reproducible Research in Signal and Image Decomposition and Inpainting by M. Jalal Fadili, Jean-Luc Starck, Michael Elad, David Donoho. The abstract reads:

Morphological Component Analysis (MCA) of signals and images is an ambitious and important goal in signal processing; successful methods for MCA have many far-reaching applications in science and technology. Because MCA is related to solving underdetermined systems of linear equations it might also be considered, by some, to be problematic or even intractable. Reproducible research is essential to to give such a concept a firm scientific foundation and broad base of trusted results. MCALab has been developed to demonstrate key concepts of MCA and make them available to interested researchers and technologists. MCALab is a library of Matlab routines that implement the decomposition and inpainting algorithms that we previously proposed in [1], [2], [3], [4]. The MCALab package provides the research community with open source tools for sparse decomposition and inpainting and is made available for anonymous download over the Internet. It contains a variety of scripts to reproduce the figures in our own articles, as well as other exploratory examples not included in the papers. One can also run the same experiments on one’s own data or tune the parameters by simply modifying the scripts. The MCALab is under continuing development by the authors; who welcome feedback and suggestions for further enhancements, and any contributions by interested researchers

MCALab is here.

Sparsity and morphological diversity for hyperspectral data analysis by Jerome Bobin, Yassir Moudden, Jean-Luc Starck, M. Jalal Fadili. The abstract reads:

Recently morphological diversity and sparsity have emerged as new and effective sources of diversity for Blind Source Separation. Based on these new concepts, novelmethods such as Generalized Morphological Component Analysis have been put forward. The latter takes advantage of the very sparse representation of structured data in large overcomplete dictionaries, to separate sources based on their morphology. Building on GMCA, the purpose of this contribution is to describe a new algorithm for hyperspectral data processing. Large-scale hyperspectral data refers to collected data that exhibit sparse spectral signatures in addition to sparse spatial morphologies, in specified dictionaries of spectral and spatial waveforms. Numerical experiments are reported which demonstrate the validity of the proposed extension for solving source separation problems involving hyperspectral data.

I could not find GMCA-lab on the net.

An overview of inverse problem regularization using sparsity by Jean-Luc Starck, M. Jalal Fadili. The abstract reads:

Sparsity constraints are now very popular to regularized inverse problems. We review several approaches which have been proposed in the last ten years to solve inverse problems such as inpainting, deconvolution or blind source separation. We will focus especially on iterative thresholding methods.

Monotone operator splitting for optimization problems in sparse recovery by M. Jalal Fadili, Jean-Luc Starck. The abstract reads:

This work focuses on several optimization problems involved in recovery of sparse solutions of linear inverse problems. Such problems appear in many fields including image and signal processing, and have attracted even more interest since the emergence of the compressed sensing (CS) theory. In this paper, we formalize many of these optimization problems within a unified framework of convex optimization theory, and invoke tools from convex analysis and maximal monotone operator splitting. We characterize all these optimization problems, and to solve them, we propose fast iterative convergent algorithms using forward-backward and/or Peaceman/Douglas-Rachford splitting iterations. With nondifferentiable sparsity-promoting penalties, the proposed algorithms are essentially based on iterative shrinkage. This makes them very competitive for large-scale problems. We also report some experiments on image reconstruction in CS to demonstrate the applicability of the proposed framework.

Une exploration numérique des performances de l'echantillonnage compressé by Charles Dossal, Gabriel Peyré, M. Jalal Fadili. The asbtract reads:

Cet article explore numériquement l’efficacité de la minimisation ℓ1 pour la restauration de signaux parcimonieux depuis des mesures compressées, dans le cas sans bruit. Nous proposons un algorithme glouton qui calcule des vecteurs parcimonieux difficiles à retrouver par minimisation ℓ1. Cet algorithme est inspiré par des critères topologiques d’identifiabilité ℓ1. Nous évaluons numériquement l’analyse théorique sans avoir à utiliser un échantillonnage de Monte-Carlo, qui tend à éviter les cas pathologiques. Ceci permet de mettre à l’épreuve les critères d’identifiabilité exploitant des projections de polytopes et de la propriété d’isométrie restreinte.

Algorithmes de premier ordre pour la projection sur une contrainte de variation totale by Gabriel Peyré, M. Jalal Fadili. The abstract reads:

Cet article propose un nouvel algorithme pour calculer la projection sur l’ensemble des images dont la variation totale est bornée par une constante. La projection est calculée à l’aide d’une formulation duale qui est résolue par des méthodes d’optimisation non-lisse du premier ordre. Ceci donne naissance à un algorithme calculant des seuillages doux itérés du champ de vecteurs dual. Cet algorithme de projection peut ensuite être utilisé comme un maillon pour la résolution d’un problème inverse sous contrainte de variation totale. Des résultats numériques montrent que notre algorithme est plus efficace que l’état de l’art pour résoudre les problèmes de débruitage, d’inpainting et de déconvolution par projection de variation totale.

Credit: NASA/GSFC/Arizona State University, First photo of LRO from the Moon.