CS: The long post of the week.

Let us start today's post with two presentation made at the latest Netsci workshop:

• Group Testing and Graph Constrained Group Testing by Venkatesh Saligrama
• Exploiting parsimony: finding sparse vectors and low-rank matrices by Maryam Fazel

The following three papers just appeared on arxiv (by the way does anybody know how to use arxiv trackbacks and Blogger ?)

Data Stream Algorithms for Codeword Testing by Atri Rudra, Steve Uurtamo. The abstract reads:

Motivated by applications in storage systems and property testing, we study data stream algorithms for local testing and tolerant testing of codes. Ideally, we would like to know whether there exist asymptotically good codes that can be local/tolerant tested with one-pass, poly-log space data stream algorithms. We show that for the error detection problem (and hence, the local testing problem), there exists a one-pass, log-space data stream algorithm for a broad class of asymptotically good codes, including the Reed-Solomon (RS) code and expander codes. In our technically more involved result, we give a one-pass, $O(e\log^2{n})$-space algorithm for RS (and related) codes with dimension $k$ and block length $n$ that can distinguish between the cases when the Hamming distance between the received word and the code is at most $e$ and at least $a\cdot e$ for some absolute constant $a>1$. For RS codes with random errors, we can obtain $e\le O(n/k)$. For folded RS codes, we obtain similar results for worst-case errors as long as $e\le (n/k)^{1-\eps}$ for any constant $\eps>0$. These results follow by reducing the tolerant testing problem to the error detection problem using results from group testing and the list decodability of the code. We also show that using our techniques, the space requirement and the upper bound of $e\le O(n/k)$ cannot be improved by more than logarithmic factors.

A Sparse Johnson--Lindenstrauss Transform by Anirban Dasgupta, Ravi Kumar, Tamás Sarlós. The abstract reads:

Dimension reduction is a key algorithmic tool with many applications including nearest-neighbor search, compressed sensing and linear algebra in the streaming model. In this work we obtain a {\em sparse} version of the fundamental tool in dimension reduction --- the Johnson--Lindenstrauss transform. Using hashing and local densification, we construct a sparse projection matrix with just $\tilde{O}(\frac{1}{\epsilon})$ non-zero entries per column. We also show a matching lower bound on the sparsity for a large class of projection matrices. Our bounds are somewhat surprising, given the known lower bounds of $\Omega(\frac{1}{\epsilon^2})$ both on the number of rows of any projection matrix and on the sparsity of projection matrices generated by natural constructions.
Using this, we achieve an $\tilde{O}(\frac{1}{\epsilon})$ update time per non-zero element for a $(1\pm\epsilon)$-approximate projection, thereby substantially outperforming the $\tilde{O}(\frac{1}{\epsilon^2})$ update time required by prior approaches. A variant of our method offers the same guarantees for sparse vectors, yet its $\tilde{O}(d)$ worst case running time matches the best approach of Ailon and Liberty.

Segmented compressed sampling for analog-to-information conversion: Method and performance analysis by Omid Taheri, Sergiy A. Vorobyov. The abstract reads:

A new segmented compressed sampling method for analog-to-information conversion (AIC) is proposed. An analog signal measured by a number of parallel branches of mixers and integrators (BMIs), each characterized by a specific random sampling waveform, is first segmented in time into $M$ segments. Then the sub-samples collected on different segments and different BMIs are reused so that a larger number of samples than the number of BMIs is collected. This technique is shown to be equivalent to extending the measurement matrix, which consists of the BMI sampling waveforms, by adding new rows without actually increasing the number of BMIs. We prove that the extended measurement matrix satisfies the restricted isometry property with overwhelming probability if the original measurement matrix of BMI sampling waveforms satisfies it. We also show that the signal recovery performance can be improved significantly if our segmented AIC is used for sampling instead of the conventional AIC. Simulation results verify the effectiveness of the proposed segmented compressed sampling method and the validity of our theoretical studies.

Pooling Design and Bias Correction in DNA Library Screening by Takafumi Kanamori, Hiroaki Uehara, Hiroaki Uehara. The abstract reads:

We study the group test for DNA library screening based on probabilistic approach. Group test is a method of detecting a few positive items from among a large number of items, and has wide range of applications. In DNA library screening, positive item corresponds to the clone having a specified DNA segment, and it is necessary to identify and isolate the positive clones for compiling the libraries. In the group test, a group of items, called pool, is assayed in a lump in order to save the cost of testing, and positive items are detected based on the observation from each pool. It is known that the design of grouping, that is, pooling design is important to %reduce the estimation bias and achieve accurate detection. In the probabilistic approach, positive clones are picked up based on the posterior probability. Naive methods of computing the posterior, however, involves exponentially many sums, and thus we need a device. Loopy belief propagation (loopy BP) algorithm is one of popular methods to obtain approximate posterior probability efficiently. There are some works investigating the relation between the accuracy of the loopy BP and the pooling design. Based on these works, we develop pooling design with small estimation bias of posterior probability, and we show that the balanced incomplete block design (BIBD) has nice property for our purpose. Some numerical experiments show that the bias correction under the BIBD is useful to improve the estimation accuracy.

Sparsity Pattern Recovery in Bernoulli-Gaussian Signal Model by Subhojit Som, Lee C Potter. The abstract reads:

In compressive sensing, sparse signals are recovered from underdetermined noisy linear observations. One of the interesting problems which attracted a lot of attention in recent times is the support recovery or sparsity pattern recovery problem. The aim is to identify the non-zero elements in the original sparse signal. In this article we consider the sparsity pattern recovery problem under a probabilistic signal model where the sparse support follows a Bernoulli distribution and the signal restricted to this support follows a Gaussian distribution. We show that the energy in the original signal restricted to the missed support of the MAP estimate is bounded above and this bound is of the order of energy in the projection of the noise signal to the subspace spanned by the active coefficients. We also derive sufficient conditions for no misdetection and no false alarm in support recovery.

This one paper is about compressed counting: On Practical Algorithms for Entropy Estimation and the Improved Sample Complexity of Compressed Counting with Ping Li. The abstract reads:

Estimating the p-th frequency moment of data stream is a very heavily studied problem. The problem is actually trivial when p = 1, assuming the strict Turnstile model. The sample complexity of our proposed algorithm is essentially O(1) near p=1. This is a very large improvement over the previously believed O(1/eps^2) bound. The proposed algorithm makes the long-standing problem of entropy estimation an easy task, as verified by the experiments included in the appendix.

I also found the following on the interwebs: An improved approach in applying compressed sensing in parallel MR imaging by Wu, B., Watts, R., Millane, R., Bones, P. The abstract reads:

Both parallel MRI (pMRI, [1]) and compressed sensing (CS, [2]) allow image reconstruction from an under-sampled data set. The former exploits data redundancy in a sparse transform domain representation whereas the latter exploits the redundancy in multiple receiver data sets. Some success has already been reported in combining the two methods directly [3]. We report a new approach in which conventional pMRI and CS are cascaded to better exploit the individual strengths of the two methods.

and finally we have Jinwei Gu's thesis entitled: Measurement, Modeling, and Synthesis of Time-Varying Appearance of Natural Phenomena. It is 22MB large. The abstract reads:

Many natural phenomena evolve over time — often coupled with a change in their reflectance and geometry — and give rise to dramatic effects in their visual appearance. In computer graphics, such time-varying appearance phenomena are critical for synthesizing photo-realistic images. In computer vision, understanding the formation of time-varying appearance is important for image enhancement and photometric-based reconstruction. This thesis studies time-varying appearance for a variety of natural phenomena — opaque surfaces, transparent surfaces, and participating media — using captured data. We have two main goals: (1) to design efficient measurement methods for acquiring time-varying appearance from the real world, and (2) to build compact models for synthesizing or reversing the appearance effects in a controllable way. We started with time-varying appearance for opaque surfaces. Using a computer controlled dome equipped with 16 cameras and 160 light sources, we acquired the first database (with 28 samples) of time-and-space-varying reflectance, including a variety of natural processes — burning, drying, decay and corrosion. We also proposed a space time appearance factorization model which disassembles the high-dimensional appearance phenomena into components that can be independently modified and controlled for rendering. We then focused on time-varying appearance of transparent objects. Real-world transparent objects are seldom clean — over time their surfaces will gradually be covered by a variety of contaminants, which produce the weathered appearance that is essential for photorealism. We derived a physically-based analytic reflectance model for recreating the weathered appearance in real time, and developed single-image based methods to measure contaminant texture patterns from real samples.
The understanding of the weathered appearance of transparent surfaces was also used
for removing image artifacts caused by dirty camera lenses. By incorporating priors on natural images, we developed two fully-automatic methods to remove the attenuation and scattering artifacts caused by dirty camera lenses. These image enhancement methods can be used for post-processing existing photographs and videos as well as for recovering clean images for automatic imaging systems such as outdoor security cameras.
Finally, we studied time-varying appearance of volumetric phenomena, such as smoke and liquid. For generating realistic animations of such phenomena, it is critical to obtain the time-varying volume densities, which requires either intensive modeling or extremely high speed cameras and projectors. By using structured light and exploring the sparsity of such natural phenomena, we developed an acquisition system to recover the time-varying volume densities, which is about 4 to 6 times more efficient than simple scanning. From the perspective of computer vision, our method provides a way to extend the applicable domain of structured light methods from 2D opaque surfaces to 3D

I could not find a copy of the following articles but I wish I did (from here):

• Zhu X, Bamler R (2010):Compressive Sensing for High Resolution Differential SAR Tomography.
• Zhu X, Bamler R (2010): Super-resolution for 4-D SAR Tomography via Compressive Sensing.
• Zhu X, Bamler R (2010): Tomographic SAR Inversion by L1 Norm Regularization - The Compressive Sensing Approach.

In this section of the ISMRM-ESMRMB meeting in Stockholm, we have the following abstracts:

k-T Group Sparse Reconstruction Method for Dynamic Compressed MRI
Muhammad Usman1, Claudia Prieto1, Tobias Schaeffter1, Philip G. Batchelor1
1King's College London, London, United Kingdom

Up to now, besides sparsity, the standard compressed sensing methods used in MR do not exploit any other prior information about the underlying signal. In general, the MR data in its sparse representation always exhibits some structure. As an example, for dynamic cardiac MR data, the signal support in its sparse representation (x-f space) is always in compact form. In this work, exploiting the structural properties of sparse representation, we propose a new formulation titled ‘k-t group sparse compressed sensing’. This formulation introduces a constraint that forces a group structure in sparse representation of the reconstructed signal. The k-t group sparse reconstruction achieves much higher temporal and spatial resolution than the standard L1 method at high acceleration factors (9-fold acceleration).

Parallel Imaging Technique Using Localized Gradients (PatLoc) Reconstruction Using Compressed Sensing (CS)
Fa-Hsuan Lin1, Panu Vesanen2, Thomas Witzel, Risto Ilmoniemi, Juergen Hennig3
1A. A. Martinos Center, Charlestown, MA, United States; 2Helsinki University of Technology, Helsinki, Finland; 3University Hospital Freiburg, Freiburg, Germany

The parallel imaging technique using localized gradients (PatLoc) system has the degree of freedom to encode spatial information using multiple surface gradient coils. Previous PatLoc reconstructions focused on acquisitions at moderate accelerations. Compressed sensing (CS) is the emerging theory to achieve imaging acceleration beyond the Nyquist limit if the image has a sparse representation and the data can be acquired randomly and reconstructed nonlinearly. Here we apply CS to PatLoc image reconstruction to achieve further accelerated image reconstruction. Specifically, we compare the reconstructions between PatLoc and traditional linear gradient systems at acceleration rates in an under-determined system.

Here is an announcement for a Workshop on Novel Reconstruction Strategies in NMR and MRI 2010

Göttingen, September 9-11, 2010
Aims and Scope

Several decades after the fundamental discoveries which opened the fields of nuclear magnetic resonance (NMR) spectroscopy and magnetic resonance imaging (MRI), both the underlying instrumentation and respective applications advanced to a fairly mature state, rendering NMR spectroscopy a key method for structural analysis of biomolecules and MRI one of the most important modalities for diagnostic imaging. For MRI, recent developments indicate that further progress can rather be expected from novel mathematical reconstruction techniques than from further advances in technology. At the same time, the application of new mathematical approaches facilitates the recording of NMR spectra with higher spectral resolution and at less measurement time, especially for multi-dimensional NMR spectroscopy. As NMR and MRI share the same physical principles, there are many similarities between the mathematical tools used for their analysis.

The aim of this workshop is to foster interaction of researchers working in NMR, MRI, and regularization of ill-posed problems, starting with tutorials in each of these fields.

Topics include parallel imaging, undersampling strategies, compressed sensing, non-quadratic regularization, nonlinear inversion methods, diffusion-weighted imaging and fiber tractography, parametric as well as nonparametric reconstruction of spectra, and non-uniform sampling in the indirect time domain.

On a different note here is an offer for thesis work in French

Poste Etude dun schéma Compressive sensing applicable aux dispositifs d’acquisition tridimensionnels
Tags: job, phd, research position

Etude d’un schéma Compressive sensing applicable aux dispositifs d’acquisition tridimensionnels
Post-Doc
DeadLine: 31/05/2010
christophe.stolz@u-bourgogne.fr
http://www.le2i.com

Contexte : A l’heure actuelle, les systèmes d’acquisition 3D commerciaux misent sur les performances en vitesse et en résolution. Le résultat est une description 3D qui peut se révéler très redondante en fonction des caractéristiques locales ou globales de l’objet et de l’attente en résolution. Telle surface plane de l’objet sera représentée par des milliers de points qu’il sera nécessaire de réduire à un certain nombre en fonction du maillage choisi a priori.

Objectifs : Nous proposons dans ce projet de valider l’approche dite «compressive sensing» introduite par Candès[1] et Donoho[2] qui révolutionne actuellement le monde des capteurs et où l’on mise plutôt sur la «qualité» de la représentation plutôt que sur la quantité. Cette qualité est obtenue à l’aide de capteurs à transformée: dans notre cas par exemple, ce n’est plus l’information «position d’un point» qui est mesurée mais plutôt une contribution de plusieurs points pondérés par une fonction bien choisie. L’information 3D n’est donc plus obtenue par une simple triangulation 3D point par point. L’application d’un tel procédé trouve par exemple naturellement une application dans le domaine de l’holographie connu comme un principe d’enregistrement basé sur les interférences permettant de “compresser” l’information 3D sous forme d’une information 2D et dont la base de Fourier[3] est un support adapté.

Nous disposons de divers capteurs destinés à l’acquisition 3D : l’un basé sur de l’imagerie polarimétrique, un second basé sur le defocused light (reconstruction 3D à partir d’un pattern lumineux défocalisé), et un dispositif d’holographie numérique.
Nous souhaiterions dans un premier temps étudier à partir des données issues de ces capteurs en quoi celles-ci peuvent ou non être représentées sous forme parcimonieuse afin de reconstituer le signal d’origine. Le travail sera fait à partir des images issues de ces dispositifs.
Il sera ensuite envisagé l’adaptation des principes du compressive sensing à certains de ces dispositifs. Dans le cas du prototype de defocused light par exemple, la difficulté se situe dans le choix de la transformée (réalisée à l’aide d’un motif lumineux particulier) et dans la reconstruction 3D à partir des données acquises qui fera appel à un algorithme non linéaire.

1. E.J. Candes et T. Tao, “Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?” Information Theory, IEEE Transactions on 52 (12), 5406-5425 (2006).
2. D.L. Donoho, “Compressed sensing”, Information Theory, IEEE Transactions on 52 (4), 1289-1306 (2006).
3. D.J. Brady, K. Choi, D.L. Marks, R. Horisaki et S. Lim, “Compressive Holography”, Opt. Express 17 (15), 13040-13049 (2009).

Encadrant : Olivier LALIGANT
Co-encadrant : Christophe STOLZ, Akram ALDROUBI (Université de Vanderbilt)
Financement : Région Bourgogne
Début du post doc : octobre 2010 pour une durée de 1 an.