CS: A Thesis on Analog-to-Information Converter using Random Demodulation, a talk, Jacket GPU, Inverse problems in acoustic tomography

Following up on a previous entry, Valerio Cambareri, a reader of this blog, just received his Bachelor of Engineering in Italy. This corresponds to a level of end of Junior year in the U.S. and Bac + 3 in France. He produced an undergraduate thesis (at the Junior level) on Compressive Sampling. The thesis is entitled:

Conversione Analog-To-Information Tramite Architettura Random Modulation Preintegration

Additional figures can be found here. It is in Italian, but if you have been reading about CS for a while, most of it is understandable. This work is based on a previous paper: Theory and Implementation of an Analog-to-Information Converter using Random Demodulation of Jason Laska, Sami Kirolos, Marco F. Duarte, Tamer Ragheb, Richard Baraniuk and Yehia Massoud. It uses newer solvers to reconstruct the signal.

In other news:

•  Stephane Chretien will talk about Lagrangian relaxation of the compressed sensing problem, at Boston University in the Statistics Department seminar, on November 4th, 2008 from 4 to 5 pm. The abstract of the talk reads: 

  Lagrangian relaxation is a general methodology for approximating hard combinatorial problems and has been applied with success to various instances such as the Max-Cut problem. The compressed sensing problem of recovering the sparsest solution to a system of linear equations is known to be NP-hard and is often relaxed by means of l1 minimization, i.e. a simple linear program. The goal of this talk is to present an approximate Lagrangian relaxation of the compressed sensing problem leading to a better relaxation scheme than l1 minimization. The resulting iterative algorithm is called Alternating l1. One of the standard features of the Lagrangian approach for hard combinatorial problems is to provide provably efficient approximation schemes. In the case of l1 minimization, E. Cands, T. Tao and their collaborators were able to to show that with high probability, l1 minimization does in fact better in that it recovers the solution of the original sparsest recovery problem exactly. We will show that the Alternating l1 algorithm allows to recover the sparsest solution with fewer observations than l1 norm minimization. As many recent proposals for the compressed sensing problem, an additional parameter has to be tuned in order to obtain signicant improvements over the plain l1 strategy. A nice feature of our approach is that this additional parameter is nothing but a Lagrange multiplier and the best value is simply the one that optimizes the dual function. We will also show how to circumvent the dicult task of computing the dual optimizer exactly by proposing a meaningful value of this parameter allowing for signicant improvements in the first two steps of the method, hence avoiding fastidious empirical tuning as is usually done in the case of other methods such as the Reweighted l1 algorithm.

• The SLIM blog has a summary entry on Compressed sensing versus sparse recovery
  
• In light of the reconstruction hardware from UCLA, I found out about Jacket: a GPU engine for Matlab. You may want to download the beta version before it becomes a paid product, and 
• Ivana Jovanovic at EPFL just released her Ph.D thesis entitled Inverse problems in acoustic tomography, where Compressed Sensing and Finite Rate of Innovation are compared. The abstract of the thesis reads:
  

Acoustic tomography aims at recovering the unknown parameters that describe a field of interest by studying the physical characteristics of sound propagating through the considered field. The tomographic approach is appealing in that it is non-invasive and allows to obtain a significantly larger amount of data compared to the classical one-sensor one-measurement setup. It has, however, two major drawbacks which may limit its applicability in a practical setting: the methods by which the tomographic data are acquired and then converted to the field values are computationally intensive and often ill-conditioned. This thesis specifically addresses these two shortcomings by proposing novel acoustic tomography algorithms for signal acquisition and field reconstruction. The first part of our exposition deals with some theoretical aspects of the tomographic sampling problems and associated reconstruction schemes for scalar and vector tomography. We show that the classical time-of-flight measurements are not sufficient for full vector field reconstruction. As a solution, an additional set of measurements is proposed. The main advantage of the proposed set is that it can be directly computed from acoustic measurements. It thus avoids the need for extra measuring devices. We then describe three novel reconstruction methods that are conceptually quite different. The first one is based on quadratic optimization and does not require any a priori information. The second method builds upon the notion of sparsity in order to increase the reconstruction accuracy when little data is available. The third approach views tomographic reconstruction as a parametric estimation problem and solves it using recent sampling results on non-bandlimited signals. The proposed methods are compared and their respective advantages are outlined. The second part of our work is dedicated to the application of the proposed algorithms to three practical problems: breast cancer detection, thermal therapy monitoring, and temperature monitoring in the atmosphere. We address the problem of breast cancer detection by computing a map of sound speed in breast tissue. A noteworthy contribution of this thesis is the development of a signal processing technique that significantly reduces the artifacts that arise in very inhomogeneous and absorbent tissue. Temperature monitoring during thermal therapies is then considered. We show how some of our algorithms allow for an increased spatial resolution and propose ways to reduce the computational complexity. Finally, we demonstrate the feasibility of tomographic temperature monitoring in the atmosphere using a custom-built laboratory-scale experiment. In particular, we discuss various practical aspects

of time-of-flight measurement using cheap, off-the-shelf sensing devices.

Image Credit: NASA/JPL/Space Science Institute, W00050373.jpg was taken on October 21, 2008 and received on Earth October 22, 2008. The camera was pointing toward SATURN-RINGS at approximately 1,114,766 kilometers away.

CS: A singular thresholding algorithm for matrix completion, Bayesian Compressive Sensing update, Compressive Sensing Hardware

This is a first for me, the three authors of a preprint have updated their own webpage the same day of the preprint's release. Jainfeng Cai, Emmanuel Candès and Zuowei Shen just made available A singular thresholding algorithm for matrix completion. (One can also find it also here, here, or here on ArXiv). The abstract reads:

This paper introduces a novel algorithm to approximate the matrix with minimum nuclear norm among all matrices obeying a set of convex constraints. This problem may be understood as the convex relaxation of a rank minimization problem, and arises in many important applications as in the task of recovering a large matrix from a small subset of its entries (the famous Netflix problem). Off-the-shelf algorithms such as interior point methods are not directly amenable to large problems of this kind with over a million unknown entries. This paper develops a simple first-order and easy-to-implement algorithm that is extremely efficient at addressing problems in which the optimal solution has low rank. The algorithm is iterative and produces a sequence of matrices {X_k;Y_k} and at each step, mainly performs a soft-thresholding operation on the singular values of the matrix Y_k. There are two remarkable features making this attractive for low-rank matrix completion problems. The first is that the soft-thresholding operation is applied to a sparse matrix; the second is that the rank of the iterates {X_k} is empirically nondecreasing. Both these facts allow the algorithm to make use of very minimal storage space and keep the computational cost of each iteration low. On the theoretical side, we provide a convergence analysis showing that the sequence of iterates converges. On the practical side, we provide numerical examples in which 1,000 x1,000 matrices are recovered in less than a minute on a modest desktop computer. We also demonstrate that our approach is amenable to very large scale problems by recovering matrices of rank about 10 with nearly a billion unknowns from just about 0.4% of their sampled entries. Our methods are connected with the recent literature on linearized Bregman iterations for l_1 minimization, and we develop a framework in which one can understand these algorithms in terms of well-known Lagrange multiplier algorithms.

It is not strictly related to compressive sensing but improves on a previous paper and on another concept that sought to make the parallel between rank minimization and nuclear norm minimization using random linear combination of the unknown matrix (a la CS). In a similar vein, Thong Do, Yi Chen, Nam Nguyen, Lu Gan and Trac Tran recently presented a way to do this with Struturally Random Matrices. The main difference between these two latter approaches and that taken by the present paper is that in this paper by Jainfeng Cai, Emmanuel Candès and Zuowei Shen, one has a direct access to specific elements of the matrix. In the latter approaches, using either gaussian or SRM matrices, one has access to only a linear combination of the unknown elements of the matrix. In generic cases of interest, one has generally access to single elements of the otherwise unknown matrix, which makes this paper very interesting. I for one keep wondering in the back of my mind how the gaussian or SRM linear mapping could have an equivalent in the physical world.


My webcrawler noticed that in the Bayesian Compressive Sensing website. There is a mention of the fact that the BCS code was updated on Aug. 03, 2008 as a bug was fixed in MT_CS.m for the cases where signals were dramatic undersampled.

Finally, I have tried my best to make a compilation of most of the hardware implementation developed with compressive sensing in mind. It is here:

http://igorcarron.googlepages.com/compressedsensinghardware

Sometimes, off-the shelf hardware can be used to do compressed sensing with no hardware change but with a different mode of operation (case of the Herschel observatory or the Chinese Chang'e probe), otherwise there is hardware developed to perform sampling in a different kind of way but is not specifically using compressed sensing ( like the hardware developed in computational photography or the coded aperture work) but should !. For the time being, I am not adding the latter equipment but soon will and I don't know how to address the former. I am also trying to categorize each of these technologies with regards to their respective Technology Readiness Level (also mentioned here in a french entry). Some way to do is by using the Excel spreadsheet of the latest TRL Calculator.

CS: Sparse Recovery Experiments: RIP-1 matrices, Sparse Matching Pursuit and Countmin compared to L1-magic and GPSR.

Piotr Indyk and Radu Berinde just made live a wiki on Sparse Recovery Experiments. As noted in the introduction:

This page contains the Matlab/C toolkit we used to get experimental results for sparse recovery using sparse matrices, reported in ^BGIKS08,^BIR08 and ^BI08. The code provides the following functionality: 

(i) given an n-dimensional vector x, compute its m-dimensional sketch Ax, where A is an mxn sketch matrix, m much less than n, and 

(ii) given a sketch Ax, recover a k-sparse approximation x* of x. In addition, the code provides subroutines for generating test vectors x and sparse matrices A.

The toolkit supports the following recovery algorithms: Sparse Matching Pursuit (SMP), Countmin and L1 minimization (although one needs to download either l1-magic or GPSR to use the last option).

These are important experiments as they show the capability of RIP-1 measurement matrices and the attendant specific recovery algorithms (Sparse Matching Pursuit and Countmin). I am adding the link to the measurement matrix section as well as the reconstruction section of the big picture. One of the findings is that the recovery might be much faster for a dedicated matching pursuit algorithm but one needs a higher number of measurements to have the same probability of reconstruction as compared to other algorithms like GPSR and l1-magic. And so while this finding may look like a bad thing, let us also look at the positive side of things: If implemented on hardware, these sparse RIP-1 matrices would seem to provide an advantage in terms of a small dynamic range.

CS: Provide feedback to the CS part of Mallat's "A Wavelet Tour of Signal Processing"

Gabriel Peyre just released a set of matlab experiments to illustrate the 3rd edition of the "A Wavelet Tour of Signal Processing, Third Edition: The Sparse Way" book of Stephane Mallat, which will feature chapters about sparse representations and compressive sensing.

A "beta version" of the experiments is available at:

http://www.ceremade.dauphine.fr/~peyre/wavelet-tour/

Gabriel also mentions to me that he "will be happy to have some feedback from readers of your blog."

A girl and a clown talk about the restricted isometry property

[ Update: the servers at xtranormal.com seem to be very slow sometimes, I am eagerly waiting for them to allow the transfer of these movies on Youtube. For those of you reading this from an RSS feed reader, you may want to come to the site directly to see the video ].



One of the nice things we used in our DARPA car was a simple text-to-speech module so that when in the car, the computer would tell us what it was doing (as opposed to having to read that from a screen). It was very handy in the trials we went through. It looks like we can now do this for the web. I am pretty sure we can use this type of tool for instructional purposes. I, for one, recall more often discussions than items mentioned in papers. Any thoughts ?

CS: Euclidean sections of l^N_1 and EC over the reals, Post-doc, CCA, CC, Renyi Entropy, IHT, l_1 norm sparse Bayesian learning

Terry Tao mentions Compressed Sensing in his latest entry on Small samples, and the margin of error. I guess it must have to do with the concept of concentration of measure.

Venkatesan Guruswami, James R. Lee, and Avi Wigderson just released Euclidean sections of l^N_1 with sublinear randomness and error-correction over the reals. The abstract reads:

It is well-known that R^N has subspaces of dimension proportional to N on which the l_1 and l_2 norms are uniformly equivalent, but it is unknown how to construct them explicitly. We show that, for any |delta above 0, such a subspace can be generated using only N^(\delta) random bits. This improves over previous constructions of Artstein-Avidan and Milman, and of Lovett and Sodin, which require O(N logN), and O(N) random bits, respectively. Such subspaces are known to also yield error-correcting codes over the reals and compressed sensing matrices. Our subspaces are de¯ned by the kernel of a relatively sparse matrix (with at most N^(\delta) non-zero entries per row), and thus enable compressed sensing in near-linear O(N^(1+\delta) ) time. As in the work of Guruswami, Lee, and Razborov, our construction is the continuous analog of a Tanner code, and makes use of expander graphs to impose a collection of local linear constraints on vectors in the subspace. Our analysis is able to achieve uniform equivalence of the l_1 and l_2 norms (independent of the dimension). It has parallels to iterative decoding of Tanner codes, and leads to an analogous near-linear time algorithm for error-correction over reals.

The SISYPH (Signals, Systems and Physics) research group, at the Physics Department of Ecole Normale Superieure de Lyon, offers a 12-months post doctoral position, starting any time after December, 1st 2008. One of the subject of interestof the group is Compressed Sensing. More information can be found here. This job was added to the CS Job list.

Yves Lucet just released the Computation Convex Analysis Library. The succint description reads:

The Computational Convex Analysis numerical library contains efficient algorithms to manipulate convex functions, and to compute fundamental convex analysis transforms. The library is coded using Scilab version 4.1.2 (available here), a numerical software freely available.

List of functions available can be found here. Let us note that Scilab can map directly into Matlab.

On top of the abstract, Ping Li also provided a summary to the SODA conference as to how his latest Compressed Counting paper brings new insight:

Our contributions include:

1) Compressed Counting (CC) is the first proposal of using skewed projections in data stream computations. We also show that maximally-skewed projections can achieve the best performance.

2) CC is the first algorithm which captures the intuition that, when $\alpha =1$ a simple counter suffices, and when $\alpha = 1\pm\Delta$ with small $\Delta$, the sample complexity should be low. We show the sample complexity of a proposed estimator $= \frac{G}{\epsilon^2}\log\left(\frac{2}{\delta}\right)$, where $G= O\left(\epsilon\right)$ as $\Delta\rightarrow 0$. In other words, for small $\Delta$, CC has the complexity $=O\left({1}/{\epsilon}\right)$. Previous results only achieved $O\left(1/\epsilon^2\right)$ (even for $\alpha =1$), which in general is expected and can not be improved, according to the central limit theorem.

3) We show, when $\alpha = 1\pm\Delta$, the asymptotic variance of a proposed estimator is $\propto \Delta$. As $\alpha \rightarrow 1$, CC achieves ``an infinite improvement'' over the previous results, in terms of the asymptotic variances.

4) Our results (especially when $\alpha=1\pm\Delta\approx 1$) have important applications. In some situation, $\Delta$ might be interpreted as the ``decay rate'' or ``interest rate,'' which is usually small. The method of moments is popular for statistical inference, which requires computing frequency moments. Also, some important summary statistics such as Renyi entropy and Tsallis entropy are functions of frequency moments and hence CC naturally provides an efficient algorithm to compute them. Very importantly, CC may serve the basic building element for developing other algorithms, for example, approximating the Shannon entropy using Renyi entropy and Tsallis entropy with $\alpha\approx 1$.

4) Our results enrich the fundamental theory of skewed stable distributions.

Talking about Renyi entropy, Jean-Francois Berger provides us with an understanding of the Renyi entropy in 'Possible rationales for Renyi-Tsallis entropy maximization. The abstract of the paper reads:

Distributions derived from the maximization of Renyi-Tsallis entropy are often called Tsallis’ distributions. We first indicate that these distributions can arise as mixtures, and can be interpreted as the solution of a standard maximum entropy problem with fluctuating constraints. Considering that Tsallis’ distributions appear for systems with displaced or fluctuating equilibriums, we show that they can be derived in a standard maximum entropy setting, taking into account a constraint that displace the standard equilibrium and introduce a balance between several distributions. In this setting, the Renyi entropy arises as the underlying entropy.

Another interest of Tsallis distributions, in many physical systems, is that they can exhibit heavy-tails and model power-law phenomena. We note that Tsallis’ distributions are similar to Generalized Pareto distributions, which are widely used for modeling the tail of distributions, and appear as the limit distribution of excesses over a threshold. This suggests that they can arise in many contexts if the system at hand or the measurement device introduces some threshold. We draw a possible asymptotic connection with the solution of maximum entropy. This view gives a possible interpretation for the ubiquity of Tsallis’ (GPD) distributions in applications and an argument in support to the use of Renyi-Tsallis entropies.

Thomas Blumensath and Mike Davies have just released their ICASSP '09 talk featuring their Iterated Hard Thresholding solver in A Simple, Efficient and Near Optimal Algorithm for Compressed Sensing by Thomas Blumensath and Mike Davies. The abstract reads:

When sampling signals below the Nyquist rate, efficient and accurate reconstruction is nevertheless possible, whenever the sampling system is well behaved and the signal is well approximated by a sparse vector. This statement has been formalised in the recently developed theory of compressed sensing, which developed conditions on the sampling system and proved the performance of several efficient algorithms for signal reconstruction under these conditions. In this paper, we prove that a very simple and efficient algorithm, known as Iterative Hard Thresholding, has near optimal performance guarantees rivalling those derived for other state of the art approaches.

Finally, the Ph.D thesis of Yuanqing Lin entitled l(1)-norm sparse Bayesian learning: Theory and applications is now available.

Image Credit: NASA/JPL/Space Science Institute, view of Enceladus from the Cassini spacecraft, photo taken on october 9th, 2008.

CS: PPPA, A Predual Proximal Point Algorithm solving a Non Negative Basis Pursuit Denoising model

François Malgouyres and Tieyong Zeng, have released a newer version of A Predual Proximal Point Algorithm solving a Non Negative Basis Pursuit Denoising model. The abstract reads:

This paper develops an implementation of a Predual Proximal Point Algorithm (PPPA) solving a Non Negative Basis Pursuit Denoising model. The model imposes a constraint on the l2 norm of the residual, instead of penalizing it. The PPPA solves the predual of the problem with a Proximal Point Algorithm (PPA). Moreover, the minimization that needs to be performed at each iteration of PPA is solved with a dual method. We can prove that these dual variables converge to a solution of the initial problem. Our analysis proves that we turn a constrained non differentiable convex problem into a short sequence of nice concave maximization problems. By nice, we mean that the functions which are maximized are differentiable and their gradient is Lipschitz. The algorithm is easy to implement, easier to tune and more general than the algorithms found in the literature. In particular, it can be applied to the Basis Pursuit Denoising (BPDN) and the Non Negative Basis Pursuit Denoising (NNBPDN) and it does not make any assumption on the dictionary. We prove its convergence to the set of solutions of the model and provide some convergence rates. Experiments on image approximation show that the performances of the PPPA are at the current state of the art for the BPDN.

They also have made available the code here. It features Matlab codes, scripts and results (30 MB). Scripts are adapted to the SPARCO toolbox so that it can be compared to other algorithms (GPSR, PCD, IT). This is a great initiative that deserves much praise.

CS: The EPFL CMOS CS Imager, Compressive Sampling of Pulse Trains : Spread the Spectrum !

Today, we have two papers from EPFL in Switzerland. Both papers have been submitted to ICASSP '09. One of the author also provided me some context. Since I am very much interested in hardware development, I couldn't help myself from asking questions. I know it's a bad habit but there is a cure: it's called an answer and the authors were kind enough to provide one. woohoo.

The first paper is CMOS Compressed Imaging by Random Convolution (also here) by Laurent Jacques, Pierre Vandergheynst, Alexandre Bibet, Vahid Majidzadeh, Alexandre Schmid, Yusuf Leblebici. The abstract reads:

We present a CMOS imager with built-in capability to perform Compressed Sensing. The adopted sensing strategy is the random Convolution due to J. Romberg. It is achieved by a shift register set in a pseudo-random configuration. It acts as a convolutive filter on the imager focal plane, the current issued from each CMOS pixel undergoing a pseudo-random redirection controlled by each component of the filter sequence. A pseudo-random triggering of the ADC reading is finally applied to complete the acquisition model. The feasibility of the imager and its robustness under noise and non-linearities have been confirmed by computer simulations, as well as the reconstruction tools supporting the Compressed Sensing theory.

Laurent puts the paper in context:

The first paper is about the design of a CMOS imager embedding random measurements, i.e. in the electronic analog processing of the signal. The sensing strategy used is the recent Random Convolution of J. Romberg (working without Fourier however).
We have noticed that this sensing simplifies not only the decoding/reconstruction process (where any sensing matrix-vector multiplication is resumed to some FFTs) but is is also straightforward to implement in the electronics of an imager. The convolutive filter is provided here by a simple shift-register (SR) set in a pseudo-random (LFSR controlled) configuration. This shift register results simply from the linking of 1-bit memories, one per pixel, and the convolution is reached by shifting (in few clock signals) the SR pseudo-random configuration. The random filter acts on the light gathered by the CMOS photodiodes by flipping the direction of the output current according to the stored bit. Kirchoff's law allows then to gather the measurements by summing the currents on wires (here, column by column to limit the current value). There are of course similarities between our imager and other projects as the "one pixel camera" of Rice's group, or the Georgia Tech Imager. Our architecture is however characterized by its specialization to the convolutive aspect of the selected sensing.

I then asked Laurent the following:

In the CMOS imager paper, do I understand correctly that the \phi x operation is the one given under the figure 1.

[the reason I asked is that I feel it is important for the folks involved with hardware development to give as much detail as possible to the theoretical/applied community in order to maybe push some other boundaries].

To which Laurent responded:

Yes. A random convolution is random in two aspects : in the filter used in the convolution, and in the random sampling of the final convolution to provide M

In furthering this thought, I then asked if they thought that the RIP-1 random matrices of Indyk, Gilbert
et al could also be easily implemented in this technology (an implementation is here but there are others)

Laurent replied with:

Well. I'm not sufficiently familiar with this kind of sparse random matrices.
I'm not sure we could implement as simply with a shift-register as we do for the random convolution.
If big storage are needed for the sensing matrix, i.e. bigger than the number of pixels, then the Georgia Tech Analog imager is for me better (they included for instance the Noiselet sensing).
If this storage is smaller than N bits, e.g. if two rows of the sensing matrix are connected by a known permutation, then perhaps a particular SR configuration is possible. A careful study has to be done.

However, our system is very easily adaptable to Toeplitz sensing matrix (see Jarvis Haupt,Waheed Bajwa, Gil Raz and Robert Nowak , Toeplitz compressed sensing matrices with applications to sparse channel estimation). To reach that, it is sufficient to generate a pseudo-random sequence larger than the number of pixels, i.e. using a LFSR with a looping period larger than 2N (with N pixels).

Let us note that this Toeplitz matrix has also been used in the context of Coded aperture by Roummel Marcia and Rebecca Willett in Compressive Coded Aperture Superresolution Image Reconstruction (additional information can be found here)

Finally, I asked:

How can one map the trade study performed by the Rice folks on their camera to your camera ?
( http://nuit-blanche.blogspot.com/2007/12/compressed-sensing-single-pixel-imaging.html
) In other words, do you have issues with dynamical range since you seem to have limit on the current, etc...

Laurent responded with the following insight:

BTW, I think that Georgia Tech imager met the same issue and this is probably one reason they use a 16x16 block separation (This is not the only reason for such block: the basis functions stored in their imager take also less memory). However, we are currently in discussion with our collaborators in the EPFL Microelectronic lab (LSM) to see how to increase the number of summed pixels (this will be mandatory for a new prototype with a larger number of pixels, e.g. 256x256)

For the rest, we haven't yet realized a deep trade study of this CS imager. What we can say however :

* this CS imager is definitely **not** the kind of imager that will be put inside an end-user device (e.g. mobile phone). CS cannot fight with imaging device able to embed a coder like JPEG2K.

* following the key principles of CS and the conclusions arose by other groups, we foresee that such a camera will be perfect for devices with low CPU power and targeting low energy consumption. I have in mind applications like a small "camera pill" designed to visualize the whole digestive system (see [1]), or flying robotic system that need a very light camera (e.g. for egomotion analysis)

* the system we use is very flexible in the sense that it could be translated to other 2-D grid of sensors currently limited in resolution because of each "pixel" circuitry. For instance, as mentionned in our paper, in collaboration with the LSM lab, we are going to apply this system to a grid of biosensors recording the electrical signal produced by a network of neuronal cells grown on the grid. Some studies proves that the signal to record will be both sparse in space and time [2]. Current CMOS biosensors recording such signals are limited in their resolution since each pixel needs a very complex electronic. A "CS analog electronic" could give access to higher resolution by reducing this complexity, i.e. a kind of economy of scale by working on a group of pixels, using random linear combinations of currents, instead of duplicating the same circuitry for each pixels.


References :

[1] : http://query.nytimes.com/gst/fullpage.html?res=9C00E6DC163CF933A05756C0A9669C8B63&sec=&spon=&pagewanted=1

[2] : M Jenkner, M Tartagni, A Hierlemann, and R Thewes, “Cell-based cmos sensor and actuator arrays,” IEEE Journ. Solid-State Circuits, vol. 39, no. 12, pp. 2431 – 2437, Dec 2004.

This hardware is now listed in the Compressive Sensing Hardware page.

The second paper is Compressive Sampling of Pulse Trains : Spread the Spectrum ! (also here) by Farid Naini, Rémi Gribonval, Laurent Jacques and Pierre Vandergheynst. The abstract reads:

In this paper we consider the problem of sampling far below the Nyquist rate signals that are sparse linear superpositions of shifts of a known, potentially wide-band, pulse. This signal model is key for applications such as Ultra Wide Band (UWB) communications or neural signal processing. Following the recently proposed Compressed Sensing methodology, we study several acquisition strategies and show that the approximations recovered via minimization are greatly enhanced if one uses Spread Spectrum modulation prior to applying random Fourier measurements. We complement our experiments with a discussion of possible hardware implementation of our technique.

To give some context, Laurent points out the following:

The second paper aims at showing how the use of a simple spread spectrum method can lead to good compressive measurements of Ultra WideBand Signals (UWB). Our study is restricted to the model of a pulse train signal, i.e. sparse in a shift-invariant dictionary generated by a short pulse. We show experimentally that, for this signal model, a SS strategy combined with the random selection of Fourier frequencies is as good as a Gaussian random sensing when the reconstruction quality is expressed in the signal domain (rather than in the dictionary coefficients). In addition, replacing the Fourier matrix by a Walsh-Hadamard transform reduces only slightly the performance and the robustness of the method, while this alternative is more appealing for the building of an analog UWB sensor (for which we provide also an idealized electronic scheme). On the theoretical side, it seems that our approach is very similar to the one of T. Do et al. about "Fast compressive sampling with structurally random matrices" (ICASSP'08), recently quoted on NB. Unfortunately, we were not aware of this work at the writing of our ICASSP paper and we will add for sure a reference to it in the revision.

On top what was kindly said about the utility of this blog, I note the use of SPARCO and SPGL1.

Finally, the Terahertz imaging technique devised at Rice and using the one pixel camera ( we mentioned it here ) has hit the wires here and here.

CS: Fast Bayesian Marching Pursuit Code, a Talk and the CS Calendar.

Lee Potter, Phil Schniter, and Justin Ziniel just released version 1.0 of the code implementing the Fast Bayesian Marching Pursuit algorithm that was featured before here and here. The code is located here. The link is in the reconstruction section of the Big Picture. Thank you Justin for the heads-up.

Also, at NIPS'08, Emmanuel Candes will give a tutorial on Compressed Sensing. The abstract of the talk reads:

One of the central tenets of signal processing and data acquisition is the Shannon/Nyquist sampling theory: the number of samples needed to capture a signal is dictated by its bandwidth. This tutorial surveys a novel sampling or sensing theory which goes somewhat against this conventional wisdom. This theory now known as ''Compressed Sensing'' or ''Compressive Sampling'' allows the faithful recovery of signals and images from what appear to be highly incomplete sets of data, i.e. from far fewer measurements or data bits than traditional methods use. We will present the key ideas underlying this new sampling or sensing theory, will survey some of the most important results, and discuss some of the most exciting current developments. We will emphasize the practicality and the broad applicability of this technique, and discuss what we believe are far reaching implications; e.g. procedures for sensing and compressing data simultaneously and much faster. Finally, there are already many ongoing efforts to build a new generation of sensing devices based on compressed sensing and we will discuss remarkable recent progress in this area as well.

Thank you Sina for the heads-up. This talk has been added to the Calendar. Talking about the calendar, for those of you not coming to the site to see this entry, the calendar is also listed on the right side of the blog in an agenda form and it looks like this:



If you know of specific events related to CS that are not featured on the calendar, please let know.

Image Credit: NASA/JPL/Space Science Institute, Looking at the stars from Enceladus, a moon of Saturn on October 9th.

CS: Fast and Efficient Dimensionality Reduction Using Structurally Random Matrices, SAMP code, Nuclear Norm Minimization using SRMs

Following last week's entry that mentioned the connection between Random Projections used in CS and the ones used in Dimensionality Reduction based on the Johnson-Lindenstrauss Lemma, Thong Do pointed out to me his recently submitted paper entitled:

Fast and Efficient Dimensionality Reduction Using Structurally Random Matrices by Thong Do, Lu Gan , Yi Chen, Nam Nguyen and Trac Tran. The abstract reads:

Structurally Random Matrices (SRM) are first proposed in [1] as fast and highly efficient measurement operators for large scale compressed sensing applications. Motivated by the bridge between compressed sensing and the Johnson-Lindenstrauss lemma [2] , this paper introduces a related application of SRMs regarding to realizing a fast and highly efficient embedding. In particular, it shows that a SRM is also a promising dimensionality reduction transform that preserves all pairwise distances of high dimensional vectors within an arbitrarily small factor ², provided that the projection dimension is on the order of O(\epsilon^(-2) log^3 N), where N denotes the number of d-dimensional vectors. In other words, SRM can be viewed as the suboptimal Johnson-Lindenstrauss embedding that, however, owns very low computational complexity O(d log d) and highly efficient implementation that uses only O(d) random bits, making it a promising candidate for practical, large scale applications where efficiency and speed of computation are highly critical.

He is also hosting a webpage on the subject of Structurally Random Matrices (SRMs) I am now changing the attendant link of the Big Picture to that page.



Sariel Har-Peled shows in ex 3.1 of this manuscript on the Johnson-Lindenstrauss lemma that one can also conserve angles as well as distance. Angle preservation was also the subject of interest of Jarvis Haupt and Robert Nowak in A generalized restricted isometry property. One wonders if the SRMs can do the same.

We mentioned SAMP before, Thong Do has released the attendant matlab code of the SAMP algorithm. It is listed in the reconstruction section of the Big Picture.

In a different area, Thong Do, Yi Chen, Nam Nguyen, Lu Gan and Trac Tran have also released A Fast and Efficient Heuristic Nuclear Norm Algorithm for Rank Minimization. The abstract reads:

The problem of affine rank minimization seeks to find the minimum rank matrix that satisfies a set of linear equality constraints. Generally, since affine rank minimization is NP-hard, a popular heuristic method is to minimize the nuclear norm that is a sum of singular values of the matrix variable [1]. A recent intriguing paper [2] shows that if the linear transform that defines the set of equality constraints is nearly isometrically distributed and the number of constraints is at least O(r(m + n) logmn), where r and m £ n are the rank and size of the minimum rank matrix, minimizing the nuclear norm yields exactly the minimum rank matrix solution. Unfortunately, it takes a large amount of computational complexity and memory buffering to solve the nuclear norm minimization problem with known nearly isometric transforms. This paper presents a fast and efficient algorithm for nuclear norm minimization that employs structurally random matrices [3] for its linear transform and a projected subgradient method that exploits the unique features of structurally random matrices to substantially speed up the optimization process. Theoretically, we show that nuclear norm minimization using structurally random linear constraints guarantees the minimum rank matrix solution if the number of linear constraints is at least O(r(m+n) log3 mn). Extensive simulations verify that structurally random transforms still retain optimal performance while their implementation complexity is just a fraction of that of completely random transforms, making them promising candidates for large scale applications.

Credit: NASA/Johns Hopkins University Applied Physics Laboratory/Carnegie Institution of Washington, The First Image After Closest Approach of Fly-By 2 of Messenger at 200 kilometers above the surface, Release Date: October 8, 2008