## Thursday, April 30, 2009

### CS:Video rate spectral imaging, Photon-limited hyperspectral, MRI Bregman l_p, TVL1, Irregular sampling, Data streams, meetings and talks.

Today we have some interesting hyperspectral work from Duke as well as other contributions found through the interwebs:

We have previously reported on coded aperture snapshot spectral imagers (CASSI) that can capture a full frame spectral image in a snapshot. Here we describe the use of CASSI for spectral imaging of a dynamic scene at video rate. We describe significant advances in the design of the optical system, system calibration procedures and reconstruction method. The new optical system uses a double Amici prism to achieve an in-line, direct view configuration, resulting in a substantial improvement in image quality. We describe NeAREst, an algorithm for estimating the instantaneous three-dimensional spatio-spectral data cube from CASSI’s two-dimensional array of encoded and compressed measurements. We utilize CASSI’s snapshot ability to demonstrate a spectral image video of multi-colored candles with live flames captured at 30 frames per second.

A nice figure shows how the transfer function between a point of light and camera is not translation invariant which I think complicates many issues when one is performing this light multiplexing.

This paper studies photon-limited, hyperspectral intensity estimation and proposes a spatially- and spectrally adaptive, nonparametric method to estimate hyperspectral intensities from Poisson observations. Specifically, our method searches over estimates defined over a family of recursive dyadic partitions in both the spatial and spectral domains, and finds the one that maximizes a penalized log likelihood criterion. The key feature of this approach is that the partition cells are anisotropic across the spatial and spectral dimensions so that the method adapts to varying degrees of spatial- and spectral-smoothness, even when the respective degrees of smoothness are not known apriori. The proposed approach is based on the key insight that the spatial boundaries and singularities exist in the same locations in every spectral band, even though the contrast or perceptibility of these features may be very low in some bands. The incorporation of this model into the reconstruction results in significant performance gains. Furthermore, for hyperspectral intensities that belong to the anisotropic H¨older-Besov function class, the proposed approach is shown to be near-minimax optimal. The upper bounds on the risk function, which is the expected squared Hellinger distance between the true intensity and the estimate obtained using the proposed approach, matches the best possible lower bound up to a log factor for certain degrees of spatial- and spectral-smoothness. Experiments conducted on realistic data sets show that the proposed method can reconstruct the spatial- and the spectral- inhomogeneities very well even when the observations are extremely photon-limited (i.e, less than 0.1 photon per voxel).

Wow, "less than 0.1 photon per voxel".

We now also have Bregman solver for l_p as introduced in Fast algorithms for nonconvex compressive sensing: MRI reconstruction from very few data" by Rick Chartrand. The abstract reads:

Compressive sensing is the reconstruction of sparse images or signals from very few samples, by means of solving a tractable optimization problem. In the context of MRI, this can allow reconstruction from many fewer k-space samples, thereby reducing scanning time. Previous work has shown that nonconvex optimization reduces still further the number of samples required for reconstruction, while still being tractable. In this work, we extend recent Fourier-based algorithms for convex optimization to the nonconvex setting, and obtain methods that combine the reconstruction abilities of previous nonconvex approaches with the computational speed of state-of-the-art convex methods.

Here is an interesting geometric characterization of the TV solver using L1: The TVL1 Model: a Geometric Point of View by Vincent Duval, Jean-François Aujol, Yann Gousseau. The abstract reads:

The aim of this paper is to investigate the geometrical behavior of the TVL1 model used in image processing, by making use of the notion of Cheeger sets. This mathematical concept was recently related to the celebrated Rudin-Osher-Fatemi image restoration model, yielding important advances in both fields. We provide the reader with a geometrical characterization of the TVL1 model. We show that, in the convex case, exact solutions of the TVL1 problem are given by an opening followed by a simple test over the ratio perimeter/area. Shapes remain or suddenly vanish depending on this test. As a result of our theoritical study, we suggest a new and efficient numerical scheme to apply the model to digital images. As a by-product, we justify the use of the TVL1 model for image decomposition, by establishing a connection between the model and morphological granulometry. Eventually, we propose an extension of TVL1 into an adaptive framework, in which we derive some theoretical results.
Finally, of connex interest to CS we have: Irregular and multi-channel sampling of operators by Yoon Mi Hong, Götz E. Pfander. The abstract reads:

The classical sampling theorem for bandlimited functions has recently been generalized to apply to so-called bandlimited operators, that is, to operators with band-limited Kohn-Nirenberg symbols. Here, we discuss operator sampling versions of two of the most central extensions to the classical sampling theorem. In irregular operator sampling, the sampling set is not periodic with uniform distance. In multi-channel operator sampling, we obtain complete information on an operator by multiple operator sampling outputs.
and Revisiting Norm Estimation in Data Streams by Daniel M. Kane, Jelani Nelson, David P. Woodruff. The abstract reads:

The problem of estimating the pth moment F_p (p nonnegative and real) in data streams is as follows. There is a vector x which starts at 0, and many updates of the form x_i -- x_i + v come sequentially in a stream. The algorithm also receives an error parameter 0 \lt eps \lt 1. The goal is then to output an approximation with relative error at most eps to F_p = ||x||_p^p. Previously, it was known that polylogarithmic space (in the vector length n) was achievable if and only if p \le 2. We make several new contributions in this regime, including: (*) An optimal space algorithm for 0 \lt p \lt 2, which, unlike previous algorithms which had optimal dependence on 1/eps but sub-optimal dependence on n, does not rely on a generic pseudorandom generator.
(*) A near-optimal space algorithm for p = 0 with optimal update and query time.
(*) A near-optimal space algorithm for the "distinct elements" problem
(p = 0 and all updates have v = 1) with optimal update and query time.
(*) Improved L_2 to L_2 dimensionality reduction in a stream.
(*) New 1-pass lower bounds to show optimality and near-optimality of our algorithms, as well as of some previous algorithms (the "AMS sketch" for p = 2, and the L_1-difference algorithm of Feigenbaum et al.). As corollaries of our work, we also obtain a few separations in the complexity of moment estimation problems: F_0 in 1 pass vs. 2 passes, p = 0 vs. p \gt 0, and F_0 with strictly positive updates vs. arbitrary updates.

Laurent Jacques mentions that the Poster presentation at ICASSP'09 of the work about CMOS Compressed Imaging by Random Convolution, by Laurent Jacques, Pierre Vandergheynst, vAlexandre Bibet, Vahid Majidzadeh, Alexandre Schmid, and Yusuf Leblebici is now available.

Holger Rauhut is organizing a special session on mathematical aspects of compressed sensing atSampTA09, May 18 - 22, 2009. He is also giving a short course on "Compressive sensing and structured random matrices" at the Summer School on "Theoretical Foundations and Numerical Methods for Sparse Recovery", Linz, August 31-September 4, 2009.

At Rice, James H. McClellan will talk about

Compressive Sensing Data Acquisition and Imaging for GPRs

on Monday, May 11, 2009
at 3:00 PM to 4:00 PM
1070 Duncan Hall
Rice University
6100 Main St
Houston, Texas, USA

New data acquisition and imaging strategies are presented for ground penetrating radars (GPRs) used in subsurface imaging. Both stepped-frequency continuous-wave (SFCW) and impulse GPRs are considered. When the target space is sparse, i.e., a small number of point like targets, the theory of compressive sensing (CS) tells us that making measurements at only a small number of random frequencies (or times) is sufficient to construct an image of the target space by solving a convex optimization problem which enforces sparsity through L1 minimization. Random spatial sampling of the synthetic aperture can also be performed as part of this data acquisition method, which greatly reduces the GPR acquisition time at the expense of higher computational costs. Imaging results for both simulated and experimental GPR data exhibit less clutter and better resolution than the standard migration and backprojection methods.

## Monday, April 27, 2009

### CS: Minimum Sum of Distances Estimator, Iterative reweighted L1, CS with quantized measurements, GPU, Missing Data Imputation, Duke Workshop Posters

Here is a very nice approach to navigation in autonomous robots:
Minimum Sum of Distances Estimator: Robustness and Stability by Yariv Sharon, John Wright and Yi Ma. The abstract reads:

We consider the problem of estimating a state x from noisy and corrupted linear measurements y = Ax + z + e, where z is a dense vector of small-magnitude noise and e is a relatively sparse vector whose entries can be arbitrarily large. We study the behavior of the l1 estimator x^ = argmin_x ||y - Ax||_1, and analyze its breakdown point with respect to the number of corrupted measurements ||e||_0. We show that the breakdown point is independent of the noise. We introduce a novel algorithm for computing the breakdown point for any given A, and provide a simple bound on the estimation error when the number of corrupted measurements is less than the breakdown point. As a motivational example we apply our algorithm to design a robust state estimator for an autonomous vehicles, and show how it can significantly improve performance over the Kalman filter.
They actually show an improvement over a non-linear Kalman filter. We observed this issue of the GPS error during our entry in DARPA's grand challenge.

Compressed sensing has shown that it is possible to reconstruct sparse high dimensional signals from few linear measurements. In many cases, the solution can be obtained by solving an ℓ1-minimization problem, and this method is accurate even in the presence of noise. Recent a modified version of this method, reweighted ℓ1-minimization, has been suggested. Although no provable results have yet been attained, empirical studies have suggested the reweighted version outperforms the standard method. Here we analyze the reweighted ℓ1-minimization method in the noisy case, and provide provable results showing an improvement in the error bound over the standard bounds.
Still in the robotics area here a new use for GPU: learning dictionariesin Large-scale Deep Unsupervised Learning using Graphics Processors by Rajat Raina, Anand Madhavan, Andrew Y. Ng. The abstract reads:
The promise of unsupervised learning methods lies in their potential to use vast amounts of unlabeled data to learn complex, highly nonlinear models with millions of free parameters. We consider two well-known unsupervised learning models, deep belief networks (DBNs) and sparse coding, that have recently been applied to a flurry of machine learning applications (Hinton & Salakhutdinov, 2006; Raina et al., 2007). Unfortunately, current learning algorithms for both models are too slow for large-scale applications, forcing researchers to focus on smaller-scale models, or to use fewer training examples. In this paper, we suggest massively parallel methods to help resolve these problems. We argue that modern graphics processors far surpass the computational capabilities of multicore CPUs, and have the potential to revolutionize the applicability of deep unsupervised learning methods. We develop general principles for massively parallelizing unsupervised learning tasks using graphics processors. We show that these principles can be applied to successfully scaling up learning algorithms for both DBNs and sparse coding. Our implementation of DBN learning is up to 70 times faster than a dual-core CPU implementation for large models. For example, we are able to reduce the time required to learn a four-layer DBN with 100 million free parameters from several weeks to around a single day. For sparse coding, we develop a simple, inherently parallel algorithm, that leads to a 5 to 15-fold speedup over previous methods.
We have had different papers on 1-bit or several-bit Compressive Sensing, here is a new one: Compressed sensing with quantized measurements by Argyrios Zymnis, Stephen Boyd, and Emmanuel Candes. The abstract reads:
We consider the problem of estimating a sparse signal from a set of quantized, Gaussian noise corrupted measurements, where each measurement corresponds to an interval of values. We give two methods for (approximately) solving this problem, each based on minimizing a differentiable convex function plus an regularization term. Using a first order method developed by Yin et al, we demonstrate the performance of the methods through numerical simulation. We find that, using these methods, compressed sensing can be carried out even when the quantization is very coarse, e.g., 1 or 2 bits per measurement.
and finally, we have: Missing Data Imputation using Compressive Sensing techniques for connected digit recognition by Jort Gemmeke and Bert Cranen. The abstract reads:
An effective way to increase the noise robustness of automatic speech recognition is to label noisy speech features as either reliable or unreliable (missing) prior to decoding, and to replace the missing ones by clean speech estimates. We present a novel method based on techniques from the field of Compressive Sensing to obtain these clean speech estimates. Unlike previous imputation frameworks which work on a frame-by-frame basis, our method focuses on exploiting information from a large time-context. Using a sliding window approach, denoised speech representations are constructed using a sparse representation of the reliable features in an overcomplete dictionary of clean, fixed-length speech exemplars. We demonstrate the potential of our approach with experiments on the AURORA-2 connected digit database.

Larry Carin has updated the Duke Workshop page and included the abstract of the posters shown there, here is the list, lots of goodies, whished I had been there:

## Poster Abstracts

UCLA

### Anwei Chai - Compressed Sensing and Imaging: a Comparative Study

Stanford University

Compressed sensing is a robust method for recovering sparse signals that can also be used in array imaging. In this work we present a framework to assess the results of imaging using compressed sensing and other previously developed approaches. We will show various numerical simulations and interpret those results with analytical ones.

### Haojun Chen - Bayesian Group LASSO for Compressive Sensing

Duke University

We introduce a probabilistic formulation of group LASSO and employ it as a block-sparse prior for Bayesian compressive sensing (CS). The resulting Bayesian group LASSO algorithm retains the robustness of Bayesian CS and, in addition, exploits the inter-dependency between the sparse coefficients to achieve accurate signal reconstruction based on a smaller number of measurements. The algorithm effectively reduces the signal dimensionality by squeezing strongly dependent coefficients into a group, and achieves computational efficiency by performing calculation at the level of groups versus individual coefficients. We compare the proposed algorithm, in terms of reconstruction performance as well as time complexity, to state-of-the-art CS algorithms.

## Friday, April 24, 2009

### Sparsity In Everything: Ah-hah moments, Insight

How many times have you had one of these ah-hah moments ? Not so many times I am sure. How many times have your students gotten it! Insight sure qualifies as one of these sparse events for most people.

A collection of entries featuring Sparsity In Everything examples can be found here. The reason of this collection of entries is to foster the case that techniques, such as compressive sensing, devised to acquire signals/event that are rare in large datasets are needed in a wide variety of everyday life examples.

Reference: The video for this entry came from this entry. The idea for this entry came from a comment made by Leon Palafox in a previous entry. Thanks Leon!

## Thursday, April 23, 2009

### CS: Clustered Sparse Signals, Matrix Completion code, FRI, Deterministic CS, Union of Frame

Here is thhe new batch today. most were found on the interwebs while others come from Rice,

Recovery of Clustered Sparse Signals from Compressive Measurements by Volkan Cevher, Piotr Indyk, Chinmay Hegde and Richard G. Baraniuk. The abstract reads:

We introduce a new signal model, called (K,C)-sparse, to capture K-sparse signals in N dimensions whose nonzero coefficients are contained within at most C clusters, with C \lt K \lt \lt N. In contrast to the existing work in the sparse approximation and compressive sensing literature on block sparsity, no prior knowledge of the locations and sizes of the clusters is assumed. We prove that O (K + C log(N/C))) random projections are sufficient for (K,C)-model sparse signal recovery based on subspace enumeration. We also provide a robust polynomial time recovery algorithm for (K,C)-model sparse signals with provable estimation guarantees

I mentioned this paper earlier: Matrix Completion from a Few Entries by Raghunandan Keshavan, Andrea Montanari, and Sewoong Oh. The software is now available here.

A Method for Generalized Sampling and Reconstruction of Finite-Rate-of-Innovation Signals by Chandra Sekhar Seelamantula, Michael Unser. The abstract reads:
We address the problem of generalized sampling and reconstruction of finite-rate-of-innovation signals. Specifically, we consider the problem of sampling streams of Dirac impulses and propose a two-channel method that enables fast, local reconstruction under some suitable conditions. We also specify some acquisition kernels and give the associated reconstruction formulas. It turns out that these kernels can also be combined into one kernel, which can be employed in the single-channel sampling scenario. The single-kernel approach carries over all the advantages of the two-channel counterpart. Simulation results are presented to validate the theoretical calculations.

Structured Variable Selection with Sparsity-Inducing Norms by Rodolphe Jenatton, Jean-Yves Audibert, Francis Bach. The abstract reads:

We consider the empirical risk minimization problem for linear supervised learning, with regularization by structured sparsity-inducing norms. These are defined as sums of Euclidean norms on certain subsets of variables, extending the usual $\ell_1$-norm and the group $\ell_1$-norm by allowing the subsets to overlap. This leads to a specific set of allowed nonzero patterns for the solutions of such problems. We first explore the relationship between the groups defining the norm and the resulting nonzero patterns, providing both forward and backward algorithms to go back and forth from groups to patterns. This allows the design of norms adapted to specific prior knowledge expressed in terms of nonzero patterns. We also present an efficient active set algorithm, and analyze the consistency of variable selection for least-squares linear regression in low and high-dimensional settings.

Found the Rice Compressive Sensing repository:

Compressed Sensing aims to capture attributes of a sparse signal using very few measurements. Candes and Tao showed that random matrices satisfy the Restricted Isometry Property or RIP property with high probability. They showed that this condition is sufficient for sparse reconstruction and that random matrices, where the entries are generated by an iid Gaussian or Bernoulli process, satisfy the RIP with high probability. This approach treats all k-sparse signals as equally likely, in contrast to mainstream signal processing where the filtering is deterministic, and the signal is described probabilistically. This paper provides weak conditions that are sufficient to show that a deterministic sensing matrix satisfies the Statistical Restricted Isometry Property (StRIP), and to guarantee the uniqueness of k-sparse representations. The columns of the sensing matrix are required to form a group under pointwise multiplication, and it is this property that provides the concentration inequalities of McDiarmid and Bernstein with the leverage necessary to guarantee uniqueness of sparse representations. We provide a large class of deterministic sensing matrices for which Basis Pursuit is able to recover sparse Steinhaus signals. The new framework encompasses many families of deterministic sensing matrices, including those formed from discrete chirps, Delsarte-Goethals codes, and Extended BCH codes. In these cases it provides theoretical guarantees on the performance of nonlinear reconstruction algorithms with complexity that is only quadratic in the dimension of the measurement domain.

Sampling in a union of frame generated subspaces by Magali Anastasio and Carlos Cabrelli. The abstract reads:
A new paradigm in Sampling theory has been developed recently by Lu and Do. In this new approach the classical linear model is replaced by a non-linear, but structured model consisting of a union of subspaces. This is the natural approach for the new theory of compressed sampling, representation of sparse signals and signals with finite rate of innovation. In this article we extend the theory of Lu and Do, for the case that the subspaces in the union are shift-invariant spaces. We describe the subspaces by means of frame generators instead of orthonormal bases. We show that, the one to one and stability conditions for the sampling operator, are valid for this more general case.

Image Credit: NASA/JPL/Space Science Institute, Saturn as seen two days ago by Cassini.

## Tuesday, April 21, 2009

### CS: Compressive Diffraction Tomography for Weakly Scattering, On Streaming, a course and some ML python code

The good stuff keeps on coming, this is very interesting:

Compressive Diffraction Tomography for Weakly Scattering by Lianlin Li, Wenji Zhang, Fang Li. The abstract reads:
An appealing requirement from the well-known diffraction tomography (DT) exists for success reconstruction from few-view and limited-angle data. Inspired by the well-known compressive sensing (CS), the accurate super-resolution reconstruction from highly sparse data for the weakly scatters has been investigated in this paper. To realize the compressive data measurement, in particular, to obtain the super-resolution reconstruction with highly sparse data, the compressive system which is realized by surrounding the probed obstacles by the random media has been proposed and empirically studied. Several interesting conclusions have been drawn: (a) if the desired resolution is within the range from to, the K-sparse N-unknowns imaging can be obtained exactly by measurements, which is comparable to the required number of measurement by the Gaussian random matrix in the literatures of compressive sensing. (b) With incorporating the random media which is used to enforce the multi-path effect of wave propagation, the resulting measurement matrix is incoherence with wavelet matrix, in other words, when the probed obstacles are sparse with the framework of wavelet, the required number of measurements for successful reconstruction is similar as above. (c) If the expected resolution is lower than, the required number of measurements of proposed compressive system is almost identical to the case of free space. (d) There is also a requirement to make the tradeoff between the imaging resolutions and the number of measurements. In addition, by the introduction of complex Gaussian variable the kind of fast sparse Bayesian algorithm has been slightly modified to deal with the complex-valued optimization with sparse constraints.

The approach parallel the Random Lens Imager of Bill Freeman et al [2] or the In-situ Random Medium scattering of Larry Carin et al [1]. I'll add this new technique to the Compressive Sensing Hardware page.

Angshul Majumdar has modifed my implementation of the re-weighted L_p algorithm of Rick Chartrand and Wotao Yin [3] so that " it can handle operators instead of explicit matrices. It requires Sparco." It is here. Thanks Angshul !

Muthu Muthukrishnan has a post up on the release of some of the slides of the recent DIMACS workhop on Streaming, they are:

Laurent Duval pointed out to me that Ron DeVore will give a course in Paris. From the flyer:

High Dimensional Approximation: Theory and Algorithms

Ronald DeVore
Chaire d'excellence de la Fondation Sciences Mathmatiques de Paris

Horaires : mardi 16 Juin de 10h30 12h30, jeudi 18, mardi 23 et jeudi 25 Juin, de 10h 12h30.

Lieu: salle 2E1, Laboratoire Jacques-Louis Lions, 175 rue du Chevaleret, 75013 Paris.

This course will study scienti c problems that are challenged by the fact that they live naturally in a Euclidean space RN with N very large. We mention three settings which will be considered in this short course.

Broad-banded signals: It is well known that a bandlimited signal (function on R) can be captured exactly from its equispaced time samples taken at the Nyquist rate. However when the bandwidth of the signal is large then the sampling rate cannot be implemented accurately in circuitry. This leads us to consider other models for signals which are still realistic but enable capturing the signal with much fewer measurements. We shall study one such setting called Compressed Sensing (CS) which models signals as having a sparse or compressible representation in a suitably chosen basis of waveforms. We shall develop the mathematical foundations of compressed sensing culminating with a derivation of the optimal rate/distortion that can be achieved with CS and a discussion of the encoder/decoders which achieve this optimality.
Mathematical learning: The mathematical theory of data tting in a stochastic setting is known as learning. Many interesting learning problems are set in high dimension and must engage the problem of approximating functions of a large number of variables. Classical approaches of approximation in several variables su er from the curse of dimensionality: the approximation rate severely su ers as the dimension increases. We shall consider possible ways to avoid the curse of dimensionality through variable reduction and sparsity.
Stochastic PDEs: The classical approach to solving stochastic PDEs is Monte Carlo methods. While these methods are robust they have severe limits in terms of their rate/distortion bounds. We shall study alternatives to Monte Carlo methods which utilize Wiener chaos expansions to convert the stochastic PDE to a deterministic parametric PDE. The number of parameters in this approach is in finite and therefore its success depends capturing a function of an in finite number of variables in a numerically realistic way. We shall derive properties of the solutions to such parametric problems in the elliptic case that show these solutions have highly accurate sparse approximations. We shall then derive potential numerical approaches to capturing these sparse approximants. Theory and algorithms for high dimensional problems are in their infancy and so this course will expose many interesting open questions.
Thanks Laurent !

On a different note, the python codes implementing the examples of the new book Machine Learning: An Algorithmic Perspective by Stephen Marsland are here.

Reference:
[1] Lawrence Carin, Dehong Liu, Wenbin Lin and Bin Guo, Compressive Sensing for Numerical Multi-Static Scattering Analysis.
[2] Random Lens Imaging, Fergus, Rob; Torralba, Antonio; Freeman, William T.
[3] Rick Chartrand and Wotao Yin, Iteratively Reweighted Algorithms for Compressive Sensing

## Monday, April 20, 2009

### CS: NESTA, CS with Known Spectral Energy Density, CS based interior tomography, CS-UWB Comm system, a Summer School,.

Here is the new batch of Compressive Sensing related papers:
NESTA: a fast and accurate first-order method for sparse recovery by Stephen Becker, Jerome Bobin, and Emmanuel Candès. The abstract reads:
Accurate signal recovery or image reconstruction from indirect and possibly under-
sampled data is a topic of considerable interest; for example, the literature in the recent field of compressed sensing is already quite immense. Inspired by recent breakthroughs in the development of novel first-order methods in convex optimization, most notably Nesterov's smoothing technique, this paper introduces a fast and accurate algorithm for solving common recovery problems in signal processing. In the spirit of Nesterov's work, one of the key ideas of this algorithm is a subtle averaging of sequences of iterates, which has been shown to improve the convergence properties of standard gradient-descent algorithms. This paper demonstrates that this approach is ideally suited for solving large-scale compressed sensing reconstruction problems as 1) it is computationally efficient, 2) it is accurate and returns solutions with several correct digits, 3) it is flexible and amenable to many kinds of reconstruction problems, and 4) it is robust in the sense that its excellent performance across a wide range of problems does not depend on the fine tuning of several parameters. Comprehensive numerical experiments on realistic signals exhibiting a large dynamic range show that this algorithm compares favorably with recently proposed state-of-the-art methods. We also apply the algorithm to solve other problems for which there are fewer alternatives, such as total-variation minimization, and convex programs seeking to minimize the l_1 norm of Wx under constraints, in which W is not diagonal.

I like the fact that they address point 4) which seems to be an issue with other methods (see this entry). I am looking forward to an implementation of this new scheme.

Compressive Sampling with Known Spectral Energy Density by Andriyan Suksmono. The abstract reads:
A method to improve L1 performance of the CS (Compressive Sampling) for signals with known spectral energy density is proposed. Instead of random sampling, the proposed method selects the location of samples to follow the distribution of the spectral energy. Samples collected from three different measurement methods; the uniform sampling, random sampling, and energy equipartition sampling, are used to reconstruct a given UWB (Ultra Wide Band) signal whose spectral energy density is known. Objective performance evaluation in term of PSNR (Peak Signal to Noise Ratio) indicates that the CS reconstruction of random sampling outperform the uniform sampling, while the energy equipartition sampling outperforms both of them. These results suggest that similar performance improvement can be achieved for CS-based devices, such as the compressive SFCW (Stepped Frequency Continuous Wave) radar and the compressive VLBI (Very Large Baseline Interferometry) imaging, allowing even higher acquisition speed or better reconstruction results.

From the good folks at Rice we have:

Compressed sensing based interior tomography by Hengyong Yu and Ge Wang. The abstract reads:
While conventional wisdom is that the interior problem does not have a unique solution, by analytic continuation we recently showed that the interior problem can be uniquely and stably solved if we have a known sub-region inside a region of interest (ROI). However, such a known sub-region is not always readily available, and it is even impossible to find in some cases. Based on compressed sensing theory, herewe prove that if an object under reconstruction is essentially piecewise constant, a local ROI can be exactly and stably reconstructed via the total variation minimization. Because many objects in computed tomography (CT) applications can be approximately modeled as piecewise constant, our approach is practically useful and suggests a new research direction for interior tomography. To illustrate the merits of our finding, we develop an iterative interior reconstruction algorithm that minimizes the total variation of a reconstructed image and evaluate the performance in numerical simulation.

Compressive Sensing Based Ultra-wideband Communication System by Peng Zhang, Zhen Hu, Robert C. Qiu and Brian M. Sadler. The abstract reads:
UWB) communication. Our major contribution is to exploit the channel itself as part of compressed sensing, through waveformbased pre-coding at the transmitter. We also have demonstrated a UWB system baseband bandwidth (5 GHz) that would, if with the conventional sampling technology, take decades for the industry to reach. The concept has been demonstrated, through simulations, using real-world measurements. Realistic channel estimation is also considered.
the attendant conference paper is here: Compressive Sensing Based Ultra-wideband Communication System by Peng Zhang, Zhen Hu, Robert C. Qiu and Brian M. Sadler. The abstract reads:
Sampling is the bottleneck for ultra-wideband (UWB) communication. Our major contribution is to exploit the channel itself as part of compressive sampling, through
waveform-level pre-coding at the transmitter. We also have demonstrated a UWB system baseband bandwidth (5 GHz) that would, if with the conventional sampling technology, take decades for the industry to reach. The concept has been demonstrated, through simulations, using real-world measurements. Realistic channel estimation is also considered.
and a presentation on the subject is here: Peng Zhang, "Compressive Sensing Based UWB System," Presentation on Compressive Sensing.

I'll be adding this to the compressive sensing hardware page.

There is also a Summer School: Theoretical Foundations and Numerical Methods for Sparse Recovery at RICAM in Linz, Austria on Aug. 31 - Sept. 4. I'll add it to the compressive sensing calendar.

Of related interest we also have:

EM type algorithms for likelihood optimization with non-differentiable penalties by Stephane Chretien, Alfred O. Hero and Herve Perdry. The abstract reads:
The EM algorithm is a widely used methodology for penalized likelihood estimation. Provable monotonicity and convergence are the hallmarks of the EM algorithm and these properties are well established for smooth likelihood and smooth penalty functions. However, many relaxed versions of variable selection penalties are not smooth. The goal of this paper is to introduce a new class of Space Alternating Penalized Kullback Proximal extensions of the EM algorithm for nonsmooth likelihood inference. We show that the cluster points of the new method are stationary points even when on the boundary of the parameter set. Special attention has been paid to the construction of component-wise version of the method in order to ease the implementation for complicated models. Illustration for the problems of model selection for finite mixtures of regression and to sparse image reconstruction is presented.

and in arxiv: An alternating $\ell_1$ relaxation for compressed sensing by Stephane Chretien. I already talked about it before. The scilab and python codes are here

Image Credit: NASA/JPL/Space Science Institute, Saturn rings as seen by Cassini five days ago.

## Sunday, April 19, 2009

### Sparsity In Everything: The Skyline of Paris

At different points in time, public policies and construction materials did not allow for buildings higher than about 16 meters high. In other periods of time, experiments were attempted where this limit was raised and subsequently dropped. The result: a sparse collection of tall buildings in a sea of 4 or 5 stories high buildings.

A collection of entries featuring Sparsity In Everything examples can be found here.

Credit photo: me, photo taken from one of the tallest building at 210 meters high: Tour Montparnasse.

## Saturday, April 18, 2009

### CS: Compressive Sensing in the Dark ?

I was reading the following summary of the following paper: The Nucleus Inside Out - Through a Rod Darkly by Tobias Ragoczy and and Mark Groudine which abstract is:

In the nuclei of eukaryotic cells, euchromatin is located at the center, whereas heterochromatin is found at the periphery and is interspersed in the nucleoplasm. Solovei et al. (2009) now reveal that this normal pattern is reversed in the retinal rod cells of mice. This inversion might serve to maximize light transmission to photoreceptors in nocturnal mammals.

In the paper (see the summary), the researchers did a computation showing how the DNA location is acting as a focusing element as in a fiber optics (as shown in the figure above). What triggered my interest in this figure is the following: In the focusing case, a pencil of light coming in gets to be transferred as two peaks with the underlying assumption that two large peaks will trigger some type of clean response. In the case of mammals, the pencil of light coming in gets to be spread around with the underlying assumption that it will be drowned in noise and will not be detectable.

Here is my stupid question: You and I can see in the dark after some accommodation. Does this mean that our vision system switches to a compressive sensing system when in the dark ? It would give a new meaning to the name of this blog!

## Friday, April 17, 2009

### CS: Herschel, Toeplitz Random Encoding for Reduced Acquisition Using Compressed Sensing

Following up on yesterday's entry (Godspeed Herschel), I went ahead and talked to the initiators of the CS scheme for this project on Herschel. Jean-Luc Starck mentioned to me that the initial study with the compressive sensing encoding was made from some idealized star fields but that they now have access to a real sky simulator which should improve their confidence in the scheme. Utlimately, the proof will be in the pudding with the real data from the spacecraft. We will only know then if the CS scheme was a good solution to transfer data to the ground. Data should stream from the spacecraft (with no encoding/compression) within the first three months of the launch. A trial period will then take place to check the CS scheme. Eventually the hope is for the CS encoding scheme to be the one preferred to download data from the spacecraft. May 6th is our next date and then they should go in this trial mode at the beginning of August.

In other news, Muthu's arms are up :-)

In a different area, I think this is the first time we have this sort of encoding in MRI:

Considerable attention has been paid to compressed sensing (CS) in the MRI community recently (1,2). CS theory allows exact recovery of a sparse signal from a highly incomplete set of samples (3,4), and thus has the potential for significant reduction in MRI scan time. While most existing work has focused on Fourier encoding, non-Fourier encoding has shown some promise (5,6). In this abstract, we design a pulse sequence to implement the Toeplitz random encoding method proposed earlier (6). The experimental results show that Toeplitz random encoding can be realized in practice as an alternative method for CS MRI.

The attendant poster is here.