CS: Sparse Approximation and Atomic Decomposition, SPARS'09 program, Counter Braids, trending in the stock market, L_0 reconstruction

Bob Sturm, a reader of this blog, just released his recently defended Ph.D. thesis entitled Sparse Approximation and Atomic Decomposition: Considering Atom Interactions in Evaluating and Building Signal Representations. The attendant slides of that defense can be found here. The abstract of the thesis reads:

This dissertation makes contributions to the sparse approximation and efficient representation of complex signals, e.g., acoustic signals, using greedy iterative descent pursuits and overcomplete dictionaries. As others have noted before, peculiar problems arise when a signal model is mismatched to the signal content, and a pursuit makes bad selections from the dictionary. These result in models that contain several atoms having no physical significance to the signal, and instead exist to correct the representation through destructive interference. These ``spurious'' terms greatly diminish the efficiency of the generated signal model, and hinder the useful application of sparse approximation to signal analysis (e.g., source identification), visualization (e.g., source selection), and modification (e.g., source extraction). While past works have addressed these problems by reformulating a pursuit to avoid them, such as adding restrictions to the content of a dictionary, in this dissertation we use these corrective terms to learn about the signal, the pursuit algorithm, the dictionary, and the created model. Our thesis is essentially that a better signal model results when a pursuit builds it considering the interaction between the atoms. We formally study these effects and propose novel measures of them to quantify the interaction between atoms in a model, and to illuminate the role of each atom in representing a signal. We then propose and study three different ways of incorporating these new measures into the atom selection criteria of greedy iterative descent pursuits, and show analytically and empirically that these interference-adaptive pursuits can produce models with increased efficiency and meaningfulness, e.g., the direct correspondence between an atom and specific signal content. Finally, we propose creating a higher-level model of the decomposed signal by agglomerating the atoms of a representation into molecules based on a set of similarity criteria, and compare this method with a previous pursuit that builds molecules simultaneously with the decomposition process. In both cases, we find that the resulting molecules have a more clear relationship with the signal content.

One can note that he is going to have to continue his postdoc in Paris. Life ain't fair :-)

The SPARS'09 conference has just released the list of the talks that will be featured there. It is here. It looks like a very interesting and worthy program.

Laurent Gosse, a trader it seems, writes about the trend of the CAC-40, the french local stock index using what he calls Compressed Sensing. I am not quite sure but it looks like detrending using l1 regularization.

There is also a new version of the presentation entitled Toward 0-norm Reconstruction, and a Nullspace Technique for Compressive Sampling by Christine Law and Gary Glover.

Finally, Yi Lu  and Balaji Prabhakar continue investigating their counter braid work with  Robust Counting via Counter Braids: An Error-Resilient Network Measurement Architecture. The abstract reads:

A novel counter architecture, called Counter Braids, has recently been proposed for accurate per-flow measurement on high-speed links. Inspired by sparse random graph codes, Counter Braids solves two central problems of per-flow measurement: one-to-one flow-to-counter association and large amount of unused counter space. It eliminates the one-to-one association by randomly hashing a flow label to multiple counters and minimizes counter space by incrementally compressing counts as they accumulate. The random hash values are reproduced offline from a list of flow labels, with which flow sizes are decoded using a fast message passing algorithm. The decoding of Counter Braids introduces the problem of collecting flow labels active in a measurement epoch. An exact solution to this problem is expensive. This paper complements the previous proposal with an approximate flow label collection scheme and a novel error-resilient decoder that decodes despite missing flow labels. The approximate flow label collection detects new flows with variable-length signature counting Bloom filters in SRAM, and stores flow labels in high-density DRAM. It provides a good trade-off between space and accuracy: more than 99 percent of the flows are captured with very little SRAM space. The decoding challenge posed by missing flow labels calls for a new algorithm as the original message passing decoder becomes error-prone. In terms of sparse random graph codes, the problem is equivalent to decoding with graph deficiency, a scenario beyond coding theory. The error-resilient decoder employs a new message passing algorithm that recovers most flow sizes exactly despite graph deficiency. Together, our solution achieves a 10-fold reduction in SRAM space compared to hash-table based implementations, as demonstrated with Internet trace evaluations.

Credit & Copyright: Eric J. Zbinden, Space Station in the Moon (via astronomy picture of the day)

CS: Efficient and Guaranteed Rank Minimization by Atomic Decomposition, Sparse time-frequency distributions of chirps from CS, un sujet de these.

The Rice Compressive Sensing Resource page has changed its presentation. Check it out. I think they also have gone through the pain of updating where preprints have been eventually published. Kudos to them!

We also have two papers and an annoucement for a thesis (in french).

Efficient and Guaranteed Rank Minimization by Atomic Decomposition by Kiryung Lee and Yoram Bresler. The abstract reads:

Recht, Fazel, and Parrilo provided an analogy between rank minimization and ℓ0-norm minimization. Subject to a generalized restricted isometry property, nuclear norm minimization is a guaranteed heuristic for rank minimization. The resulting semidefinite formulation is a convex problem but in practice the algorithms for it do not scale well to large instances. Instead, we explore missing terms in the analogy and propose a new heuristic which is computationally efficient and also has a performance guarantee. The heuristic is based on the atomic decomposition of the matrix variable and extends the idea in the CoSaMP algorithm for ℓ0-norm minimization. The correlation maximization rule for CoSaMP is generalized to derive a new selection rule. Combined with the recent fast low rank approximation of matrices based on randomization, the proposed algorithm can efficiently handle large scale rank minimization problems.

Sparse time-frequency distributions of chirps from a compressed sensing perspective by Patrick Flandrin, Pierre Borgnat. The abstract reads:

Considering that multicomponent chirp signals are sparse in the time-frequency domain, it is possible to attach to them highly localized distributions thanks to a compressed sensing approach based on very few measurements in the ambiguity plane. The principle of the technique is described, with emphasis on the choice of the measurement subset for which an optimality criterion is proposed.

And this one annoucement for a thesis in French, let us note hte use of sensor development for UAVs.

 

Proposition de sujet de these a l'Office National d’Études et de Recherches Aérospatiales a Chatillon. Sujet: Conception conjointe optique/traitement pour imageurs compacts

Laboratoire d’accueil à l’ONERA :

Branche : TIS

Département : DTIM

Unité : EVS

Lieu (centre ONERA) : Châtillon

Responsable ONERA : Frédéric Champagnat (EVS)

Directeur de thèse universitaire envisagé:

RÉSUMÉ :

Les dernières années ont vu se développer de nouveaux concepts de capteurs optroniques [1] qui remettent en cause les compromis de prise d’image classiques (par exemple, temps de pause/ouverture [2]), en couplant une optique non standard (par exemple, une optique multi-voies de type oeil à facettes ou une optique de type axicon diffractif) à un traitement dédié, effectué le cas échéant au vol. Corrélativement, une intense réflexion est en cours dans la communauté du traitement de signal et de l’image sur des modes d’acquisition assurant une compacité optimale du signal délivré par le capteur, activité identifiée sous l’appellation « compressed sensing » [3]. Ces évolutions sont à l’origine du projet de recherche fédérateur ONERA SPIDER, portant sur la conception de composants de perception (capteur + traitement) embarquables par exemple sur des petits drones, pour l’interprétation dynamique d’événements et de situations en milieu urbain.

Le développement de tels composants remet en cause les cloisonnements classiques entre opticiens d'une part et traiteurs d'image d'autre part, et appelle à l'optimisation conjointe capteur+traitement. Cette thèse s'inscrit dans le projet SPIDER et se déroulera dans une équipe de traitement d’image du Département de Traitement de L’information et de Modélisation (DTIM) en collaboration avec une équipe d’opticiens du Département d’Optique Théorique et Appliquée (DOTA).

L’objectif de la thèse est de contribuer à l’étude de plusieurs de ces concepts et de leur apport éventuel pour les fonctionnalités nécessaires à un système autonome comme un petit drone d’observation (reconnaissance d’objets, interprétation de scène, ego-localisation, évitement d’obstacles). A moyen terme, les concepts les plus prometteurs seront retenus pour la réalisation d’un protoype capteur+traitement et sa démonstration....

Image Credit: NASA/JPL/Space Science Institute, photo of Titan taken three days ago by Cassini.

CS: a job, Golden Ratio Radial Imaging, Model-based CS MRI, Rate Distortion Behavior of Sparse Sources, MP Shrinkage in Hilbert Spaces

Mike Davies just let me know of a job announcement for a research Fellow at the University of Edinburgh,UK for three years starting March 1, 2009. I am adding it to Compressive Sensing jobs section. Looks like The Google has not indexed it yet, woohoo ... we are going faster than The Google.

The sampling approach of the first paper/poster strangely ressembles the result by Yves Meyer, Basarab Matei featured in A variant on the compressed sensing of Emmanuel Candes (I talked about it here, here and here in reference to MRI). The paper is entitled: Highly Undersampled 3D Golden Ratio Radial Imaging with Iterative Reconstruction by Mariya Doneva, Holger Eggers , J. Rahmer , Peter Börnert and Alfred Mertins. The introduction reads:

Compressed Sensing (CS) [1,2] suggests that using nonlinear reconstruction algorithms based on convex optimization an accurate signal reconstruction can be obtained from a number of samples much lower than required by the Nyquist limit. Recently, CS was demonstrated for MR imaging from undersampled data [3, 4]. Prerequisites for a good image reconstruction are the image compressibility and the incoherence of the sampling scheme. To exploit the full potential of CS, measurement samples should be acquired at random. However, random sampling of the k-space is generally impractical. Variable density sampling schemes (radial, spiral) lead to incoherent aliasing and are also advantageous because of their higher sampling density about the k-space origin, where most of the signal energy is contained. 3D variable density sampling is potentially appropriate for CS, because the noise-like aliasing is distributed within the complete volume, allowing high undersampling factors. Image reconstruction from a low number of measurements could be very useful for dynamic 3D imaging, to reduce the often long acquisition times and thus improve temporal resolution in 3D MRI. In this work, we demonstrate the applicability of CS for 3D dynamic imaging using highly undersampled 3D radial acquisition with golden ratio profile ordering [5,6].

and from the same group of folks we also have: Model-based Compressed Sensing reconstruction for MR parameter mapping by Mariya Doneva, Christian Stehning, Peter Börnert, Holger Eggers and Alfred Mertins. The introduction reads:

Compressed Sensing [1-4] suggests that compressible signals can be reconstructed from far less samples than required by the Nyquist-Shannon sampling theorem. Signal recovery is achieved by Basis Pursuit (BP) [2] or greedy algorithms like Orthogonal Matching Pursuit (OMP) [4]. The latter has weaker performance guarantees, but it is often faster and is thus an attractive alternative to BP. Most commonly, orthonormal bases are applied as a sparsifyingtransform. However, allowing the signal to be sparse with respect to an overcomplete dictionary adds a lot of flexibility with regard to the choice of the transform and could improve the transform sparsity. MR parameter mapping measurements of relaxation times T1 and T2, diffusion coefficients, etc. require the acquisition of multiple images of the same anatomy at varying parameters, which is associated with long acquisition times. These data are described by a model with only few parameters, which could be used to design a model-based overcomplete dictionary for CS reconstruction. In this work we demonstrate this approach for the acceleration of T1 mapping data acquisition.

I also found: Rate Distortion Behavior of Sparse Sources by Claudio Weidmann, Martin Vetterli. The abstract reads:

The rate distortion behavior of sparse memoryless sources is studied. Such sources serve as models for sparse representations and can be used for the performance analysis of "sparsifying" transforms like the wavelet transform, as well as nonlinear approximation schemes. Under the Hamming distortion criterion, R(D) is shown to be almost linear for sources emitting sparse binary vectors. For continuous random variables, the geometric mean is proposed as a sparsity measure and shown to lead to upper and lower bounds on the entropy, thereby characterizing asymptotic R(D) behavior. Three models are analyzed more closely under the mean squared error distortion measure: continuous spikes in random discrete locations, power laws matching the approximately scale-invariant decay of wavelet coefficients, and Gaussian mixtures. The latter are versatile models for sparse data, which in particular allow to bound the suitably defined coding gain of a scalar mixture compared to that of a corresponding unmixed transform coding system. Such a comparison is interesting for transforms with known coefficient decay, but unknown coefficient ordering, e.g. when the positions of highest-variance coefficients are unknown. The use of these models and results in distributed coding and compressed sensing scenarios is also discussed.

Martin Vetterli also made a video presentation at ECTV'08. It is entitled Sparse Sampling: Variations on a Theme by Shannon. Other videos of the conference can be found here.

Finally, Matching Pursuit Shrinkage in Hilbert Spaces by Tieyong Zeng, and Francois Malgouyes. The abstract reads:

This paper contains the research on a hybrid algorithm combining the Matching Pursuit (MP) and the wavelet shrinkage. In this algorithm, we propose to shrink the scalar product of the element which best correlates with the residue before modifying. The study concerns a broad family of shrinkage functions. Using weak properties of these shrinkage functions, we show that the algorithm converges towards the orthogonal projection of the data on the linear space generated by the dictionary, modulo a precision characterized by the shrinkage function. In the deterministic settings, under a mild assumption on the shrinkage function (for instance, the hard shrinkage satisfies this assumption), this algorithm converges in a finite time which can be estimated from the properties of the shrinkage function. Experimental results show that in the presence of noise, the new algorithm does not only outperform the regular MP, but also behaves better than some other classical Greedy methods and Basis Pursuit Denoising model when used for detection.

Image Credit: NASA/JPL/Space Science Institute. Dione as seen by Cassini last friday.

CS: A review, Efficient Encoding of Audio Signals, Greedy Algorithms Comparison, Randomized algo, l1 solvers, Quality is Number 1 again!

Weren't Friday's papers interesting or what ? Today we have a batch of six. 

From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images by Alfred Bruckstein, David Donoho, Michael Elad. The abstract.

A full-rank matrix A element of R^(n×m) with n less than m generates an underdetermined system of linear equations Ax = b having infinitely many solutions. Suppose we seek the sparsest solution, i.e., the one with the fewest nonzero entries. Can it ever be unique? If so, when? As optimization of sparsity is combinatorial in nature, are there efficient methods for finding the sparsest solution? These questions have been answered positively and constructively in recent years, exposing a wide variety of surprising phenomena, in particular the existence of easily verifiable conditions under which optimally sparse solutions can be found by concrete, effective computational methods. Such theoretical results inspire a bold perspective on some important practical problems in signal and image processing. Several well-known signal and image processing problems can be cast as demanding solutions of undetermined systems of equations. Such problems have previously seemed, to many, intractable, but there is considerable evidence that these problems often have sparse solutions. Hence, advances in finding sparse solutions to underdetermined systems have energized research on such signal and image processing problems—to striking effect. In this paper we review the theoretical results on sparse solutions of linear systems, empirical results on sparse modeling of signals and images, and recent applications in inverse problems and compression in image processing. This work lies at the intersection of signal processing and applied mathematics, and arose initially from the wavelets and harmonic analysis research communities. The aim of this paper is to introduce a few key notions and applications connected to sparsity, targeting newcomers interested in either the mathematical aspects of this area or its applications.

Efficient Encoding of a Sinusoidally-Modelled Audio Signal Using Compressed Sensing by Anthony Griffin, Christos Tzagkarakis, Toni Hirvonen, Athanasios Mouchtaris and Panagiotis Tsakalidesthe abstract reads:

In this paper, the compressed sensing (CS) methodology is applied to the harmonic part of sinusoidally- modelled audio signals. As this part of the model is sparse by definition in the frequency domain, we investigate whether CS can be used for encoding this signal at low bitrates, instead of encoding the sinusoidal parameters (amplitude, frequency, phase) as current state-of-the-art methods do. CS samples signals at a much lower rate than the Nyquist rate if they are sparse in some basis, thus it is a natural choice in this context. This also has the potential benefit of moving the computational burden from the encoder to the decoder. Previous work presented an initial investigation into the performance of this scheme, and this paper demonstrates how the performance can be further improved to rival that of a state-of-the-art encoder.

A Comparative Study of Some Greedy Pursuit Algorithms for Sparse Approximation by Gagan Rath and Arabinda Sahoo. The abstract reads:

Solving an under-determined system of equations for the sparsest solution has attracted considerable attention in recent years. Among the two well known approaches, the greedy algorithms like matching pursuits (MP) are simpler to implement and can produce satisfactory results under certain conditions. In this paper, we compare several greedy algorithms in terms of the sparsity of the solution vector and the approximation accuracy. We present two new greedy algorithms based on the recently proposed complementary matching pursuit (CMP) and the sensing dictionary framework, and compare them with the classical MP, CMP, and the sensing dictionary approach. It is shown that in the noise-free case, the complementary matching pursuit algorithm performs the best among these algorithms.

In a fascinating area I briefly mentioned a year ago, here is Randomized Kaczmarz Solver for Noisy Linear Systems by Deanna Needell. The abstract reads:

The Kaczmarz method is an iterative algorithm for solving systems of linear equations Ax = b. Theoretical convergence rates for this algorithm were largely unknown until recently when work was done on a randomized version of the algorithm. It was proved that for overdetermined systems, the randomized Kaczmarz method converges with expected exponential rate, independent of the number of equations in the system. Here we analyze the case where the system Ax = b is corrupted by noise, so we consider the system Ax ≈ b + r where r is an arbitrary error vector. We prove that in this noisy version, the randomized method reaches an error threshold dependent on the matrix A with the same rate as in the error-free case. We provide examples showing our results are sharp in the general context.

Olivier Grisel pointed out the following two papers while on Twitter. they are relevant to new schemes devised for solving l1 and related reconstructions. Now the question is whether they are any faster than the current ones we already have:

An interior-point stochastic approximation method and an L1-regularized delta rule by Peter Carbonetto, Mark Schmidt and Nando de Freitas. The abstract reads:

The stochastic approximation method is behind the solution to many important, actively-studied problems in machine learning. Despite its far-reaching application, there is almost no work on applying stochastic approximation to learning problems with general constraints. The reason for this, we hypothesize, is that no robust, widely-applicable stochastic approximation method exists for handling such problems. We propose that interior-point methods are a natural solution. We establish the stability of a stochastic interior-point approximation method both analytically and empirically, and demonstrate its utility by deriving an on-line learning algorithm that also performs feature selection via L1 regularization.

and Online and Batch Learning using Forward Looking Subgradients by John Duchi, Yoram Singer. The abstract reads:

We describe, analyze, and experiment with a new framework for empirical loss minimization with regularization. Our algorithmic framework alternates between two phases. On each iteration we first perform an unconstrained gradient descent step. We then cast and solve an instantaneous optimization problem that trades off minimization of a regularization term while keeping close proximity to the result of the first phase. This view yields a simple yet effective algorithm that can be used for batch penalized risk minimization and online learning. Furthermore, the two phase approach enables sparse solutions when used in conjunction with regularization functions that promote sparsity, such as ℓ1. We derive concrete and very simple algorithms for minimization of loss functions with ℓ1, ℓ2, ℓ2^2, and ℓ1 regularization. We also show how to construct efficient algorithms for mixed-norm ℓ1/ℓq regularization. We further extend the algorithms and efficient implementations for very high-dimensional data with sparsity. We demonstrate the potential of the proposed framework in a series of experiments with synthetic datasets.

Credit photo 1: NASAWatch, the Satellite in this photo is the NOAA-N Prime satellite. I talked about the incident here. Five years later, the satellite was launched on Friday and is currently in orbit. Woohoo.

Credit photo 2: NASA/Carleton Bailie, ULA 

You keep using that word. I do not think it means what you think it means.

Tomorrow's photos reminded me of yet another entry on the same subject.

Credit for the title of this entry: Imdb, script of the Princess Bride.

CS: The Restricted Isometry Property and l_q-Regularization: Phase transition for Sparse Approximation, Decay Properties of RIC

Here are two much expected analyses,I am sure I'll come back to these later:

The Restricted Isometry Property and l_q-Regularization: Phase transition for Sparse Approximation by Jeffery Blanchard, Coralia Cartis, and Jared Tanner. The abstract reads:

Consider a measurement matrix A of size n×N, with n less than N, y a signal in R^N, and b = Ay the observed measurement of the vector y. From knowledge of (b,A), compressed sensing seeks to recover the k-sparse x, k less than n, which minimizes ||b − Ax||. Using various methods of analysis — convex polytopes, geometric functional analysis, and the restricted isometry property (RIP) — it has been proven that x can be reconstructed via l_q-regularization (q element of (0, 1]) provided A satisfies conditions dictated by the method of analysis. This article focuses on the RIP approach and A with entries drawn i.i.d. from the Gaussian distribution N(0, 1/sqrt(n)), developing more precise bounds on the restricted isometry constants, and using these bounds in an asymmetric RIP formulation to quantify the region of ( n/N , k/n ) in which RIP implies that l_q-regularization will typically recover all k-sparse signals. Letting n/N go to \delta and k/n go to \rho as n go to \infinity, the aforementioned recoverability region is characterized by all \rho lss than < (1 − \epsilon)rho^RIP_S (\delta; q) for any epsilon above 0, where rho^RIP_S (\delta; q) is a lower bound of the true phase transition below which l_q-regularization will typically recover all k-sparse signals. This phase transition framework, proposed in this context by Donoho (2005), is applied to compressed sensing results obtained by the analysis techniques of centro-symmetric polytope theory (Donoho), geometric functional analysis (Rudelson and Vershynin), and the RIP (Candes, Romberg and Tao; Foucart and Lai; Chartrand). Recasting the results from different methods of analysis into a common phase transition framework allows for the direct comparison of the efficacy of the respective results.

and Decay Properties of Restricted Isometry Constants by Jeffery Blanchard, Coralia Cartis, and Jared Tanner. The abstact reads:

The restricted isometry property (RIP) is an important technique of analysis in sparse approximation. Many sparse approximation algorithms accurately capture the sparsest solution provided the restricted isometry constants satisfy certain bounds. There are no known sufficiently large deterministic matrices that satisfy the desired RIP bounds; however, many random matrix ensembles satisfy RIP bounds with high probability on the draw of the matrix. Here we construct matrices whose RIP constants behave in a markedly different fashion from those of classical random matrix ensembles. In particular, the RIP constants can satisfy desirable bounds and also take on values in a narrow range.

Image Credit: NASA/JPL/Space Science Institute, image of Saturn taken on January 23, 2009

CS: Automatic Code Generation for Real-Time Convex Optimization, OFDM Channel Estimation, rate distortion, Jacket Webinar.

This entry has a "fast" flavor and is sometimes peripherically related to CS:

Automatic Code Generation for Real-Time Convex Optimization by Jacob Mattingley and Stephen Boyd. The abstract reads:

This chapter concerns the use of convex optimization in real-time embedded systems, in areas such as signal processing, automatic control, real-time estimation, real-time resource allocation and decision making, and fast automated trading. By ‘embedded’ we mean that the optimization algorithm is part of a larger, fully automated system, that executes automatically with newly arriving data or changing conditions, and without any human intervention or action. By ‘real-time’ we mean that the optimization algorithm executes much faster than a typical or generic method with a human in the loop, in times measured in milliseconds or microseconds for small and medium size problems, and (a few) seconds for larger problems. In real-time embedded convex optimization the same optimization problem is solved many times, with different data, often with a hard real-time deadline. In this chapter we propose an automatic code generation system for real-time embedded convex optimization. Such a system scans a description of the problem family, and performs much of the analysis and optimization of the algorithm, such as choosing variable orderings used with sparse factorizations and determining storage structures, at code generation time. Compiling the generated source code yields an extremely efficient custom solver for the problem family. We describe a preliminary implementation, built on the Python-based modeling framework CVXMOD, and give some timing results for several examples.

Just found on arxiv:

OFDM Channel Estimation Based on Adaptive Thresholding for Sparse Signal Detection by Mahdi Soltanolkotabi, Arash Amini and Farokh Marvasti. The abstract reads:

Wireless OFDMchannels can be approximated by a time varying filter with sparse time domain taps. Recent achievements in sparse signal processing such as compressed sensing have facilitated the use of sparsity in estimation, which improves the performance significantly. The problem of these sparse-based methods is the need for a stable transformation matrix which is not fulfilled in the current transmission setups. To assist the analog filtering at the receiver, the transmitter leaves some of the subcarriers at both edges of the bandwidth unused which results in an ill-conditioned DFT submatrix. To overcome this difficulty we propose Adaptive Thresholding for Sparse Signal Detection (ATSSD). Simulation results confirm that the proposed method works well in time-invariant and specially time-varying channels where other methods may not work as well.

From the text, one can read:

As a result, linear-programming-based algorithms used in compressed sensing, similar to the ones introduced in [?] can be applied to OFDM channel estimation. However, the authors of [?] did not consider zero-padding at the endpoints of the bandwidth in their scenario, which is an essential part of current OFDMstandards. This assumption, causes the matrix Fp,CP to contradict the Restricted Isometric Property (RIP) defined in [?] and thus the use of Compressive Sensing (CS) algorithms as described in [?], unpractical.

I am not quite sure about this and this is not the first time that such wording is being used. The Restricted Isometry Property is just a sufficient condition. Not fulfilling the RIP, doesn't mean that CS algorithms cannot work.

and On the rate distortion function of Bernoulli Gaussian sequences by Cheng Chang. The abstract reads:

In this paper, we study the rate distortion function of the i.i.d sequence of multiplications of a Bernoulli p random variable and a gaussian random variable = N(0, 1). We use a new technique in the derivation of the lower bound in which we establish the duality between channel coding and lossy source coding in the strong sense. We improve the lower bound on the rate distortion function over the best known lower bound by p log_2 (1/p) if distortion D is small. This has some interesting implications on sparse signals where p is small since the known gap between the lower and upper bound is H(p). This improvement in the lower bound shows that the lower and upper bounds are almost identical for sparse signals with small distortion because lim p 0 plog_2 (1/p)/ H(p) = 1.

Finally, there is a webinar today about jacket:
Jacket: Accelerating MATLAB using CUDA-Enabled GPUs, February 5, 2009, 11am PST / 2pm EST. Are you looking for ways to improve your productivity by accelerating MATLAB functions? Now you can with the unprecedented performance of GPU computing. By attending this webinar, you will learn:

• What is GPU computing
• What is NVIDIA CUDA parallel computing architecture
• What is the Jacket engine for MATLAB from AccelerEyes
• How to get 10x to 50x speed-up for several MATLAB functions

Date: Thursday, February 5, 2009
Time: 11:00am PST / 2:00pm EST
Duration: 45 Minute Presentation, 15 Minute Q&A
Register Here
Presented By: Sumit Gupta, Ph.D., Sr Product Manager of Tesla GPU Computing at NVIDIA and John Melonakos, Ph.D., CEO at AccelerEyes LLC

CS: Beyond Nyquist, Domain decomposition methods for CS, an internship, CS workshop on Youtube and Optical Imaging and Spectroscopy book and blog

Today, we have two papers, an internship offer, some news from Duke and a new blog:

Beyond Nyquist: Efficient Sampling of Sparse Bandlimited Signals by Joel Tropp, Jason Laska, Marco Duarte, Justin Romberg, and Richard Baraniuk. The abstract reads:

Wideband analog signals push contemporary analog-to-digital conversion systems to their performance limits. In many applications, however, sampling at the Nyquist rate is inefficient, because the signals of interest contain only a small number of significant frequencies relative to the bandlimit, although the locations of the frequencies may not be known a priori. For this type of sparse signal, other sampling strategies are possible. This paper describes a new type of data acquisition system, called a random demodulator, that is constructed from robust, readily available components. Let K denote the total number of frequencies in the signal, and let W denote its bandlimit in Hz. Simulations show that the random demodulator requires just O(K log(W=K)) samples per second to stably reconstruct the signal. This sampling rate is exponentially lower than the Nyquist rate of W Hz. In contrast with Nyquist sampling, one must use nonlinear methods, such as convex programming, to recover the signal from the samples taken by the random demodulator. Finally, the paper provides a theoretical analysis of the system’s performance.

Domain decomposition methods for compressed sensing by Massimo Fornasier, Andreas Langer, Carola-Bibiane Schönlieb. The abstract reads:

We present several domain decomposition algorithms for sequential and parallel minimization of functionals formed by a discrepancy term with respect to data and total variation constraints. The convergence properties of the algorithms are analyzed. We provide several numerical experiments, showing the successful application of the algorithms for the restoration 1D and 2D signals in interpolation/inpainting problems respectively, and in a compressed sensing problem, for recovering piecewise constant medical-type images from partial Fourier ensembles.

Amit Agrawal is looking for interns at MERL this summer: Summer Internship (2009) at Mitsubishi Electric Research Labs (MERL)

Starting May 2009 We are looking for a student with experience and interest in one or more of the following topics Computational Imaging/Photography Active illumination LightFields and Applications Motion Deblurring Coded Aperture Techniques Project details are at http://www.merl.com/people/agrawal/index.html
* The student research background should include computer vision and image processing projects.
* Programming experience in Matlab, C/C++
* The student may also submit his/her own proposal for a research project.
* Competitive pay, fun working environment. Please send email to agrawal at merl dot com with resume, dates of availability and area of interest.

While there is no obvious relation to Compressive Sensing, work like the one performed by Roummel Marcia, Zachary Harmany, and Rebecca Willett in their latest paper entitled Compressive Coded Aperture Imaging should be a clue that much work can expand in that area with CS provinding much solid theoretical underpinnings. I have added this announcement to the Compressive Sensing Jobs list.

Rebecca Willett just mentioned to me that the upcoming Compressive Sensing Workshop will be videoed and is expected to be put on the Youtube channel of the meeting. I need to buy myself some popcorn. If somebody wants to be a reporter for NB, it would be nice if you could also have photos of the numerous posters of the poster session. I'll feature each and every one of them on the blog, promise.

Also from Duke, if you recall I mentioned earlier that David Brady would have a book out in 2009 entitled: Optical Imaging and Spectroscopy. Looks like the book already has an attendant website with Matlab and Mathematica codes for each chapter. Chapter 8 featuring some CS reconstruction. The website is at: http://opticalimaging.org/. More Importantly, the book also has an attendant blog: http://opticalimaging.org/OISblog/


Credit Photo: NASA/JPL/Space Science Institute, Saturn rings taken on February 01, 2009

CS: KGG presentation, Jacket, pystream, a paradigm shift in signal processing, 3D CS for Dynamic MRI

I mentioned her yesterday, but the links were all wrong. So here we are again: Svetlana Avramov-Zamurovic presented a tutorial on Compressive Sensing in a course at the USNA. She also made a video of it. It is here. The slides and attendant paper by Richard Baraniuk on which the presentation is based. It is added to the Compressive Sensing Videos page.

Also found on the interwebs:

Compressive Sensing Theory and L1-Related Optimization Algorithms by Yin Zhang. Of interest is the mention of a recoverability proof without the use of the RIP argument.

A presentation by Albert Cohen entitled Near optimal recovery of arbitrary signals from highly incomplete measurements.

There is a summary of the Frames for the finite world: Sampling, coding and quantization workshop organized by Sinan Gunturk, Goetz Pfander, Holger Rauhut, and Ozgur Yilmaz

Jacket v1.0, a Matlab to GPU software is now available. It's not free but heavily discounted for academics it seems. There is also pystream from the project page:

PyStream combines the power and convenience of Python with the high performance of modern Graphics Processing Units (GPUs). The focus of PyStream is on NVIDIA GPUs, such as the GeForce 8800 and Tesla series, that support the Compute Unified Device Architecture (CUDA) toolkit. With PyStream, the CUDA libraries, including the CUDA BLAS and FFT libraries, can be called from directly from Python. Data can be moved back and forth seamlessly between the GPU and Python objects (NumPy arrays) on the CPU. Initial development of PyStream was done by Tech-X Corporation. Tech-X Corporation has shifted its efforts to a new GPU related project, called GPULib, that has a higher level API than PyStream and also supports other languages other than Python. Because of this change, PyStream is no longer being actively developed. However, PyStream will remain available under the BSD license.

Also found on Arxiv, Compressive sensing: a paradigm shift in signal processing by Olga V. Holtz.

The abstract reads:We survey a new paradigm in signal processing known as "compressive sensing". Contrary to old practices of data acquisition and reconstruction based on the Shannon-Nyquist sampling principle, the new theory shows that it is possible to reconstruct images or signals of scientific interest accurately and even exactly from a number of samples which is far smaller than the desired resolution of the image/signal, e.g., the number of pixels in the image. This new technique draws from results in several fields of mathematics, including algebra, optimization, probability theory, and harmonic analysis. We will discuss some of the key mathematical ideas behind compressive sensing, as well as its implications to other fields: numerical analysis, information theory, theoretical computer science, and engineering.

There is an attendant presentation entitled An Introduction to Compressive Sensing by the same author.

Finally, Three-Dimensional Compressed Sensing for Dynamic MRI by Ali Bilgin, Ted Trouard, Maria Altbach, and Natarajan Raghunand. The introduction reads:

Dynamic contrast enhanced (DCE) magnetic resonance imaging (MRI) is a valuable tool used in a number of clinical applications. However, imaging of time-varying objects is a challenging task when both high spatial resolution and high temporal resolution is desired. It has been demonstrated that radial imaging techniques can yield increased temporal resolution without sacrificing spatial resolution and are less susceptible to motion [1,2]. However, highly undersampled radial trajectories result in increased streaking artifacts and low SNR. The recently introduced Compressed Sensing (CS) theory illustrates that a small number of linear measurements can be sufficient to reconstruct sparse or compressible signals [3,4] and has the potential to significantly accelerate data acquisition in MRI [5,6,7]. In this work, we introduce a CS theory based method for reconstruction of time-varying radial k-space data by exploiting the spatio-temporal sparsity of DCE-MRI images.

Credit: NASA/JPL/Space Science Institute,Saturn's ring taken on January 28th, 2009.

CS: Twitter, Several news and findings, A Non-Iterative Procedure for Undetermined Systems, Molecular imaging, Super-resolution X-ray

For those of who know what this is, I am on Twitter.

Thomas Blumensath sent me a kind e-mail :

As an avid reader of your blog, I thought I clarify the following points raised in one of your previous entries regarding the OLS algorithm.

Firstly, we did not propose the method in our paper. This method has been around with many names and in many guises. Our paper actually gives a good historical overview (which was its main purpose). A better reference for the OLS algorithm would be:

S. Chen, S. A. Billings, and W. Luo, “Orthogonal least squares methods and their application to non-linear system identification.,” International Journal of Control, vol. 50, no. 5, pp. 1873–1896, 1989.

Secondly, I would like to point out that ols is also available in my Sparsify toolbox (greed_ols).

Thanks Thomas for the clarification.


Svetlana Avramov-Zamurovic presented a tutorial on Compressive Sensing in a course at the USNA. She also made a video of it. It is here. The slides and attendant paper by Richard Baraniuk on which the presentation is based. I'll add it to the Compressive Sensing Videos page.

Jort Gemmeke let me know that the schedule and list of presentation of the Compressive Sensing Workshop is now available here. Lots of goodies.

Andryian Suksmono has just released a draft e-book on Compressive Sensing. The mild caveat is that it is in Indonesian. No worry, Google Translate now has Indonesian to English translation services.

Felix J. Herrmann, Yogi Erlangga, Tim Lin have released a new version of Compressive simultaneous full-waveform simulation.

A passing thought: when you hear about an imaging system that is diffraction-limited, you are really hearing that the analog way of combining light rays together to form an image has limits. If you have read the previous entry on compressive phase retrieval featuring Ab Initio Compressive Sensing Phase retrieval by Stefano Marchesini and Compressed Sensing Phase Retrieval by Matthew Moravec, Justin Romberg and Richard Baraniuk, you know by now that every time you hear about an indirect measurement system or have the ability to engineer the PSF (Point Spread Function), it is likely you should be able to use the strength of compressive sensing to perform measurements.

Here are three papers that I think are interesting in different respect:

Sparse image reconstruction for molecular imaging by Michael Ting, Raviv Raichand, Alfred O. Hero III. The abstract reads:

The application that motivates this paper is molecular imaging at the atomic level. When discretized at subatomic distances, the volume is inherently sparse. Noiseless measurements from an imaging technology can be modeled by convolution of the image with the system point spread function (psf). Such is the case with magnetic resonance force microscopy (MRFM), an emerging technology where imaging of an individual tobacco mosaic virus was recently demonstrated with nanometer resolution. We also consider additive white Gaussian noise (AWGN) in the measurements. Many prior works of sparse estimators have focused on the case when H has low coherence; however, the system matrix H in our application is the convolution matrix for the system psf. A typical convolution matrix has high coherence. The paper therefore does not assume a low coherence H. A discrete-continuous form of the Laplacian and atom at zero (LAZE) p.d.f. used by Johnstone and Silverman is formulated, and two sparse estimators derived by maximizing the joint p.d.f. of the observation and image conditioned on the hyperparameters. A thresholding rule that generalizes the hard and soft thresholding rule appears in the course of the derivation. This so-called hybrid thresholding rule, when used in the iterative thresholding framework, gives rise to the hybrid estimator, a generalization of the lasso. Unbiased estimates of the hyperparameters for the lasso and hybrid estimator are obtained via Stein’s unbiased risk estimate (SURE). A numerical study with a Gaussian psf and two sparse images shows that the hybrid estimator outperforms the lasso.

a related (older) presentation can be found in A. O. Hero, R. Raich, and M. Ting, Finding dust in space: localizing atoms from noisy projections.

Here is another interesting and somewhat surprising paper: A Non-Iterative Procedure for Computing Sparse and Sparsifiable Solutions to Slightly Underdetermined Linear Systems of Equations by Andrew Yagle. The abstract reads:

We consider the problem of reconstructing a sparse image from a few of its 2-D DFT frequency values. A sparse image has pixel values that are mostly zero, with a few non-zero values at unknown locations. The number of known 2-D DFT values must exceed four times the number of non-zero pixel values. We unwrap the 2-D problem to a 1-D problem using the Good-Thomas FFT, and apply Prony's method to compute the non-zero pixel value locations. Thus we reformulate the problem as a dual 2-D harmonic retrieval problem. Our solution has three advantages over direct application of 2-D ESPRIT: (1) Instead of solving a huge generalized eigenvalue problem, we compute the roots on the unit circle of a huge polynomial; (2) the locations of the known 2-D DFT values need not form a centrosymmetric region; and (3) there are no matching issues. Our algorithm is also applicable to 2-D beamforming.

and New Atomicity-Exploiting Algorithms for Super-Resolution X-Ray Crystallography by Andrew Yagle. The abstract reads:

The X-ray crystallography problem is to reconstruct a crystalline structure from the Fourier magnitude of its diffracted scattering data. This has three major difficulties: (1) Only Fourier magnitude (not phase) data are known; (2) There is no support constraint (since the crystal is periodic); and (3) only low-wavenumber scattering data are available. But it also has two major advantages: (1) the crystal is sparse (atomicity) since it consists of isolated atoms; and (2) the crystal structure often has even symmetry. We exploit atomicity to show that the crystal can be reconstructed easily from only low wavenumber Fourier data. We also propose new algorithms for reconstruction of crystals with even or no symmetry from low-wavenumber Fourier magnitude data using two or one isomorphic replacements (4 algorithms). Small numerical examples illustrate the algorithms.

Sparse Imputation for Noise Robust Speech Recognition Using Soft Masks by Jort Gemmeke, Bert Cranen. The abstract reads:

In previous work we introduced a new missing data imputation method for ASR, dubbed sparse imputation. We showed that the method is capable of maintaining good recognition accuracies even at very low SNRs provided the number of mask estimation errors is sufficiently low. Especially at low SNRs, however, mask estimation is difficult and errors are unavoidable. In this paper, we try to reduce the impact of mask estimation errors by making soft decisions, i.e., estimating the probability that a feature is reliable. Using an isolated digit recognition task (using the AURORA-2 database), we demonstrate that using soft masks in our sparse imputation approach yields a substantial increase in recognition accuracy, most notably at low SNRs.

Credit: NASA/JPL/Space Science Institute, Photo of Saturn's rings taken by Cassini the day before yesterday.