Sunday, February 07, 2010

CS: This week's longest entry. New Preprints, a Job and two Talks.

I know, I know... for most of you today is Sunday, but for those readers close to the International Date line, it's already Monday and it's in the middle of the night, so what better way than to start this week now by reading Nuit Blanche and all the good stuff that comes with it. Enjoy!

Once again some goodness coming out Rice, today it's Spectral Compressive Sensing by Marco Duarte, and Rich Baraniuk. The abstract reads:
Compressive sensing (CS) is a new approach to simultaneous sensing and compression of sparse and compressible signals. A great many applications feature smooth or modulated signals that can be modeled as a linear combination of a small number of sinusoids; such signals are sparse in the frequency domain. In practical applications, the standard frequency domain signal representation is the discrete Fourier transform (DFT). Unfortunately, the DFT coefficients of a frequency-sparse signal are themselves sparse only in the contrived case where the sinusoid frequencies are integer multiples of the DFT's fundamental frequency. As a result, practical DFT-based CS acquisition and recovery of smooth signals does not perform nearly as well as one might expect. In this paper, we develop a new spectral compressive sensing (SCS) theory for general frequency-sparse signals. The key ingredients are an over-sampled DFT frame, a signal model that inhibits closely spaced sinusoids, and classical sinusoid parameter estimation algorithms from the field of spectrum estimation. Using peridogram and eigen-analysis based spectrum estimates (e.g., MUSIC), our new SCS algorithms significantly outperform the current state-of-the-art CS algorithms while providing provable bounds on the number of measurements required for stable recovery.
The attendant toolbox is available at: http://dsp.rice.edu/scs


The Google webcrawler just found the following postdoc position at EPFL. I'll add it to the compressive sensing jobs page. Here is the ad:

In the context of a new ERC award, several PhD and Post-Doc positions are available in the field of mathematical signal processing at the Laboratory of Audiovisual Communications, Ecole Polytechnique Fédérale de Lausanne (EPFL) http://lcavwww.epfl.ch/.

Abstract of project: The subject of signal representations with Fourier and wavelet bases is central to signal processing and communications. Non-linear approximation methods in such bases are key for problems like denoising, compression and inverse problems.
Recently, the idea that signals that are sparse in some domain can be acquired at low sampling density has generated strong interest, under various names like compressed sensing, compressive sampling and sparse sampling.
We aim to study the central problem of acquiring continuous-time signals for discrete-time processing and reconstruction using the methods of sparse sampling. Solving this involves developing theory and algorithms for sparse sampling, both in continuous and discrete time. In addition, in order to acquire physical signals, we plan to develop a sampling theory for signals obeying physical laws, like the wave and diffusion equation, and light fields.
Together, this will lead to a sparse sampling theory and framework for signal processing and communications, with applications from analog-to-digital conversion to new compression methods, to super-resolution data acquisition and to inverse problems in imaging. In sum, we aim to develop the theory and algorithms for sparse signal processing, with impact on a broad range of applications.

Please send applications with a CV, list of publications, and the names of 3 references for
Post-doctoral positions to :
EPFL/IC/LCAV
Jacqueline Aeberhard
Station 14
1015 Lausanne
jacqueline.aeberhard@epfl.ch
Before March15th, 2010
Phd positions to :
http://phd.epfl.ch/page57750-en.html
Before April 15th, 2010


Laurent Duval just mentioned to me this announcement for a seminar in Paris this coming week:
Le prochaine exposé du séminaire d'analyse et probabilités de Paris-Dauphine aura lieu ce

mardi 9 février.

Josselin Garnier, de l'Université de Paris 7, parlera de "Passive sensor imaging using cross correlations of ambient noise signals / Imagerie passive par exploitation du bruit de fond". Le séminaire a lieu à 11h en salle A 707 (7e étage de la nouvelle aile).
It reminds me a lot of the Imaging with Nature concept (that I should add to the list of Technologies that do not Exist). While Laurent Daudet mentioned to me this other seminar (still in Paris):
Maxime Dahan
Le Jeudi 11 Février 2010 de 14h30 à 15h30 (Amphithéâtre Boreau, ESPCI)
Fluorescence imaging using compressed sensing
Which brings us back to the concept of Spectral Compressive Sensing by Marco Duarte, and Rich Baraniuk as introduced at the beginning of this entry. Thanks Laurent and Laurent.


There are three new papers on the Rice Compressed Sensing Repository:

Collaborative spectrum sensing from sparse observations using matrix completion for cognitive radio networks by Jia (Jasmine) Meng, Wotao Yin, Husheng Li, Ekram Houssain, , Zhu HanThe abstract reads:

In cognitive radio, spectrum sensing is a key component to detect spectrum holes (i.e., channels not used by any primary users). Collaborative spectrum sensing among the cognitive radio nodes is expected to improve the ability of checking complete spectrum usage states. Unfortunately, due to power limitation and channel fading, available channel sensing information is far from being sufficient to tell the unoccupied channels directly. Aiming at breaking this bottleneck, we apply recent matrix completion techniques to greatly reduce the sensing information needed. We formulate the collaborative sensing problem as a matrix completion subproblem and a joint-sparsity reconstruction subproblem. Results of numerical simulations that validated the effectiveness and robustness of the proposed approach are presented. In particular, in noiseless cases, when number of primary user is small, exact detection was obtained with no more than 8% of the complete sensing information, whilst as number of primary user increases, to achieve a detection rate of 95.55%, the required information percentage was merely 16.8%.
Ahah! here is something that is bound to have an impact into making compressive mainstream. As you recall, the connection between normal coded aperture and compressive sensing coded aperture was made clear through the use of Toeplitz matrices (see this entry and this one), today we have the following Practical compressive sensing with Toeplitz and circulant matrices by Wotao Yin, Simon Morgan, Junfeng Yang, Yin Zhang. The abstract reads:
Compressive sensing encodes a signal into a relatively small number of incoherent linear measurements. In theory, the optimal incoherence is achieved by completely random measurement matrices. However, such matrices are difficult and/or costly to implement in hardware realizations. After summarizing recent results of how random Toeplitz and circulant matrices can be easily (or even naturally) realized in various applications, we introduce fast algorithms for reconstructing signals from incomplete Toeplitz and circulant measurements. We present computational results showing that Toeplitz and circulant matrices are not only as effective as random matrices for signal encoding, but also permit much faster signal decoding.
The full site hosting the soon to be available code but also most of the paper in a visually attractive fashion is at:


I'll keep you posted as to when the code gets to be available.
Accurate edge information can significantly improve image recovery quality and speed, but such information is encoded in the CS measurements of an image. To take advantage of edge information in CS recovery, EdgeCS alternatively performs CS reconstruction and edge detection in a way that each benefits from the latest solution of the other. EdgeCS is fast and returns high-quality images. It exactly recovers the 256 × 256 Shepp-Logan phantom from merely 7 radial lines (or 3.03% k-space), which is impossible for most existing algorithms. It accurately reconstructs a 512×512 magnetic resonance image from 21% noisy samples. Moreover, it is also able to reconstruct complex-valued images. Each took about 30 seconds on an ordinary laptop. The algorithm can be easily ported to GPUs for a speedup of more than 10 folds.
My webcrawler found also the following three papers: Compressive through-focus imaging by Oren Mangoubi and Edwin A. Marengo. The abstract reads:
Optical sensing and imaging applications often suffer from a combination of low resolution object reconstructions and a large number of sensors (thousands), which depending on the frequency can be quite expensive or bulky. A key objective in optical design is to minimize the number of sensors (which reduces cost) for a given target resolution level (image quality) and permissible total sensor array size (compactness). Equivalently, for a given imaging hardware one seeks to maximize image quality, which in turn means fully exploiting the available sensors as well as all priors about the properties of the sought-after objects such as sparsity properties, and other, which can be incorporated into data processing schemes for object reconstructions. In this paper we propose a compressive-sensing-based method to process through-focus optical field data captured at a sensor array. This method applies to both two-dimensional (2D) and three-dimensional (3D) objects. The proposed approach treats in-focus and out-of-focus data as projective measurements for compressive sensing, and assumes that the objects are sparse under known linear transformations applied to them. This prior allows reconstruction via familiar compressive sensing methods based on 1-norm minimization. The proposed compressive throughfocus imaging is illustrated in the reconstruction of canonical 2D and 3D objects, using either coherent or incoherent light. The obtained results illustrate the combined use of through-focus imaging and compressive sensing techniques, and also shed light onto the nature of the information that is present in in-focus and out-of-focus images.

Distilled Sensing: Adaptive Sampling for Sparse Detection and Estimation by Jarvis Haupt, Rui Castro and Robert Nowak. The abstract reads:
Adaptive sampling results in dramatic improvements in the recovery of sparse signals in white Gaussian noise. A sequential adaptive sampling-and-refinement procedure called distilled sensing (DS) is proposed and analyzed. DS is a form of multi-stage experimental design and testing. Because of the adaptive nature of the data collection, DS can detect and localize far weaker signals than possible from non-adaptive measurements. In particular, reliable detection and localization (support estimation) using non-adaptive samples is possible only if the signal amplitudes grow logarithmically with the problem dimension. Here it is shown that using adaptive sampling, reliable detection is possible provided the amplitude exceeds a constant, and localization is possible when the amplitude exceeds any arbitrarily slowly growing function of the dimension.

We consider the problem of deciding whether a highly incomplete signal lies within a given subspace. This problem, Matched Subspace Detection, is a classical, well studied problem when the signal is completely observed. Highdimensional testing problems in which it may be prohibitive or impossible to obtain a complete observation motivate this work. The signal is represented as a vector in Rn, but we only observe m much less than n of its elements.We show that reliable detection is possible, under mild incoherence conditions, as long as m is slightly greater than the dimension of the subspace in question.

The next papers are a compilation of several papers that were presented at SAMPTA'09. I do not think I have covered all of them before ( I maybe wrong) but here they are for completeness:

Quantization for Compressed Sensing Reconstruction by John Z. Sun, Vivek K. Goyal. The abstract reads:
Quantization is an important but often ignored consideration in discussions about compressed sensing. This paper studies the design of quantizers for random measurements of sparse signals that are optimal with respect to mean-squared error of the lasso reconstruction. We utilize recent results in high-resolution functional scalar quantization and homotopy continuation to approximate the optimal quantizer. Experimental results compare this quantizer to other practical designs and show a noticeable improvement in the operational distortion-rate performance.

Analysis of HighDimensional Signal Data by Manifold Learning and Convolutions by Mijail Guillemard, Armin Iske. The abstract reads:
A novel concept for the analysis of high-dimensional signal data is proposed. To this end, customized techniques from manifold learning are combined with convolution transforms, being based on wavelets. The utility of the resulting method is supported by numerical examples concerning low-dimensional parameterizations of scale modulated signals and solutions to the wave equation at varying initial conditions.

Linear Signal Reconstruction from Jittered Sampling by Alessandro Nordio, Carla-Fabianna Chiasserini, Emanuele Viterbo. The abstract reads:
This paper presents an accurate and simple method to evaluate the performance of AD/DA converters affected by clock jitter, which is based on the analysis of the mean square error (MSE) between the reconstructed signal and the original one. Using an approximation of the linear minimum MSE (LMMSE) filter as reconstruction technique, we derive analytic expressions of the MSE. Through asymptotic analysis, we evaluate the performance of digital signal reconstruction as a function of the clock jitter, number of quantization bits, signal bandwidth and sampling rate.

Finite Range Scalar Quantization for Compressive Sensing by Jason Laska, Petros Boufounos, Richard Baraniuk. The abstract reads:
Analog-to-digital conversion comprises of two fundamental discretization steps: sampling and quantization. Recent results in compressive sensing (CS) have overhauled the conventional wisdom related to the sampling step, by demonstrating that sparse or compressible signals can be sampled at rates much closer to their sparsity rate, rather than their bandwidth. This work further overhauls the conventional wisdom related to the quantization step by demonstrating that quantizer overflow can be treated differently in CS and by exploiting the tradeoff between quantization error and overflow. We demonstrate that contrary to classical approaches that avoid quantizer overflow, a better finite-range scalar quantization strategy for CS is to amplify the signal such that the finite range quantizer overflows at a pre-determined rate, and subsequently reject the overflowed measurements from the reconstruction. Our results further suggest a simple and effective automatic gain control strategy which uses feedback from the saturation rate to control the signal gain.

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

The Generalized Annihilation Property: A Tool For Solving Finite Rate of Innovation Problems by Thierry Blu. The abstract reads:
We describe a property satisfied by a class of nonlinear systems of equations that are of the form F(Omega)X = Y. Here F(Omega) is a matrix that depends on an unknown K-dimensional vector Omega, X is an unknown K-dimensional vector and Y is a vector of N \ge K) given measurements. Such equations are encountered in superresolution or sparse signal recovery problems known as “Finite Rate of Innovation” signal reconstruction. We show how this property allows to solve explicitly for the unknowns Omega and X by a direct, non-iterative, algorithm that involves the resolution of two linear systems of equations and the extraction of the roots of a polynomial and give examples of problems where this type of solutions has been found useful.


Distributed Sensing of Signals Under a Sparse Filtering Model by Ali Hormati, Olivier Roy, Yue M. Lu, Martin Vetterli. The abstract reads:
We consider the task of recovering correlated vectors at a central decoder based on fixed linear measurements obtained by distributed sensors. Two different scenarios are considered: In the case of universal reconstruction, we look for a sensing and recovery mechanism that works for all possible signals, whereas in the case of almost sure reconstruction, we allow to have a small set (with measure zero) of unrecoverable signals. We provide achievability bounds on the number of samples needed for both scenarios. The bounds show that only in the almost sure setup can we effectively exploit the signal correlations to achieve effective gains in sampling efficiency. In addition, we propose an efficient and robust distributed sensing and reconstruction algorithm based on annihilating filters.

An “algebraic” reconstruction of piecewise-smooth functions from integral measurements by Dima Batenkov, Niv Sarig, Yosef Yomdin. The abstract reads:
This paper presents some results on a well-known problem in Algebraic Signal Sampling and in other areas of applied mathematics: reconstruction of piecewise-smooth functions from their integral measurements (like moments, Fourier coefficients, Radon transform, etc.). Our results concern reconstruction (from the moments) of signals in two specific classes: linear combinations of shifts of a given function, and “piecewise D-finite functions” which satisfy on each continuity interval a linear differential equation with polynomial coefficients.


Average Case Analysis of Multichannel Basis Pursuit by Holger Rauhut, Yonina Eldar. The abstract reads:
We consider the recovery of jointly sparse multichannel signals from incomplete measurements using convex relaxation methods. Worst case analysis is not able to provide insights into why joint sparse recovery is superior to applying standard sparse reconstruction methods to each channel individually. Therefore, we analyze an average case by imposing a probability model on the measured signals. We show that under a very mild condition on the sparsity and on the dictionary characteristics, measured for example by the coherence, the probability of recovery failure decays exponentially in the number of channels. This demonstrates that most of the time, multichannel sparse recovery is indeed superior to single channel methods.


Orthogonal Matching Pursuit with random dictionaries by Pawel Bechler, Przemyslaw Wojtaszczyk. The abstract reads:
In this paper we investigated the efficiency of the Orthogonal Matching Pursuit for random dictionaries. We concentrate on dictionaries satisfying Restricted Isometry Property. We introduce a stronger Homogenous Restricted Isometry Property which is satisfied with overwhelming probability for random dictionaries used in compressed sensing. We also present and discuss some open problems about OMP.


A short note on non-convex compressed sensing by Rayan Saab, Özgür Yilmaz. The abstract reads:
In this note, we summarize the results we recently proved in [14] on the theoretical performance guarantees of the decoders l_p. These decoders rely on `p minimization with p element of (0; 1) to recover estimates of sparse and compressible signals from incomplete and inaccurate measurements. Our guarantees generalize the results of [2] and [16] about decoding by l_p minimization with p = 1, to the setting where p 2 (0; 1) and are obtained under weaker sufficient conditions. We also present novel extensions of our results in [14] that follow from the recent work of DeVore et al. in [8]. Finally, we show some insightful numerical experiments displaying the trade-off in the choice of p element of (0; 1] depending on certain properties of the input signal.

Credit: Figure from the paper Practical compressive sensing with Toeplitz and circulant matrices by Wotao Yin, Simon Morgan, Junfeng Yang, Yin Zhang. The site hosting this figure is at:

Saturday, February 06, 2010

CS: Compressive Sensing Linear Algebra 101

nasa_iss_stream

Do you think about Lapack when you perform your average matrix inversion. Sure you don't, you expect that it works and you expect that your main problem is filling up the numbers in that matrix you are about to invert. The rest is known. For those of you using Matlab it's about using inv or \ and that's it. It turns out that we need to build a framework so that eventually folks at Matlab overload operators like inv or \ when the system is underdetermined so that Compressive Sensing becomes as obvious as any operations using Lapack.

Today, we are going to look at an algorithm that is used in the calibration of the Random Lens Imager. Why ? because it is the sort of capability that any engineer, physicist or chemist should be able to do without having to KNOW compressive sensing or read this blog for weeks or immersed herself in all the papers at the Rice Repository. Let us state the problem:

Suppose you have a specific physical set up that transforms elements x into elements y. You know the physical transform is linear. The problem can be stated as:

y = A x

where y and x are vectors of size n and A is matrix of size m x n. The goal of the maneuver is to find A i.e. one is looking to fill up a matrix of unknown coefficients while having access to both x and y. Sounds simple enough. You form n vectors x equal to the vectors of the canonical basis. You physically perform n times the product A x with the same n canonical vectors and obtain the y as your physical response. Because you are using canonical vector, the y's are just the columns of A. You may also notice that in this case, m could be different from n but this is not important This is basic Algebra 101 taught in high school.

What happens if you know that A is sparse and but is also very large ? [Update: you do not know the sparsity pattern of A] if you have followed the thread but don't know about compressive sensing, a naive answer would be to say: well, Igor, it doesn't matter, I'll just go for a larger number of canonical vectors, it'll take longer but that's it. In other words, knowing in advance that A is sparse is irrelevant.

Compressive Sensing is a technique that allows one to take this statement into account and by the same token reduces the number of times you will perform these matrix vector multiplications. How much reduction are we talking about ? let us say you know the sparsity of A is roughly k, instead of performing n matrix-vector operations (or n measurements in your physical system), compressive sensing guarantees under certain conditions that the number of operations will be in the realm of k log(n).

Let us appreciate some orders of magnitude here: If n = 10^7 (10 million), then for a sparsity k = 1000, the number of operations is reduced by 10^7/(10^3log(10^7)) = 620 or between 2 to three orders of magnitude. If making one measurement takes a second, then instead of taking 115 days to perform the full characterization of A, you are looking at finishing up this whole thing within 5 hours. Did I get your attention ? Good.

How do we solve this then ?

Let us first define other matrices first:

Y = A X
where
  • X is a matrix of size n x n1, in the naive approach stated above, its columns each represent the n1 first canonical vectors.
  • A is a matrix of size m x n of unknown coefficients
  • Y is a matrix of size m x n1, in the naive approach stated above, its columns represent the first n1 columns of A

In the naive approach, when n1 reaches n, one fully knows A. The statement can be put in the following form:

Yt = Xt At

where the t index represent the transpose and where
  • Xt is a matrix of size n1 x n, in the naive approach stated above, its rows each represent the n1 first canonical vectors.
  • At is a matrix of size n x m of unknown coefficients
  • Yt is a matrix of size n1 x m, in the naive approach stated above, its rows represent the first n1 columns of A
The statement can also be put in the following form:

yt_i = Xt at_i

where
  • at_i is the i-th column vector of size n x 1 of unknown coefficients of At. This statement stands for i=1 to m.
  • yt_i is the i-th column vector of size n1 x 1 of unknown coefficients of At. This statement stands for i=1 to m and as before,
  • Xt is a matrix of size m1 x n, in the naive approach stated above, its rows each represent the n1 first canonical vectors.
Each of these at_i vectors are sparse or very sparse and we are solving for all of them. In order for compressive sensing to work, we are not going to be using canonical vectors (the rows of Xt) but we are going to use random vectors. Also, since we don't know the sparsity k of A, we are going through an iterative process.

  1. Start with an empty matrix X (the size of X will be n x n1 for the remainder of the algorithm)
  2. Produce a random vector of size n x 1 that will be added as one the column of X,
  3. Increase n1 by 1
  4. Physically compute the response y = A x (x is an n x 1 vector, y is an m x 1 vector)
  5. Add the new found y to the columns of Y ( an m x n1 matrix)
  6. Solve for all vectors at_i (i goes from 1 to m) in yt_i = Xt at_i where yt_i is an n1 x 1 vector, Xt is an n1 x n matrix, at_i is an n x 1 vector. You may have noticed that Xt is underdetermined, i.e. too few rows compared to the number of columns, but there are many different solvers that solve this system of equation.
  7. If convergence is observed for At (i.e. for all the columns at_i) then stop, if not go to step 2.
Obviously, you probably don't want to start with an empty matrix first. Like in the ISD or DUMBEST algorithm, you could finesse around and instead of adding new columns of X pick only the ones of interest. This could really look good as Monday Morning Algorithm and whoever wants to implement it and make it available to the world will get this blog full attention :-)


Credit: Phil Plait, Bad Astronomy Blog, you can watch this webcam live from Space Station.

Friday, February 05, 2010

1010


Wow. If I add the stats on the right hand side of the blog, about 1010 people read Nuit Blanche with a feed reader or by E-mail. The compressive sensing study group on LinkedIn comprises 246 members. The site has had a PageRank of 6 for the past few months.

Thursday, February 04, 2010

CS: Single-letter Characterization of Signal Estimation, The Gelfand widths of $\ell_p$-balls, K-Dimensional Coding Schemes, A CS-EEG for BCI X-Prize

Today, we have an upcoming presentation and three preprints with a mathematical and information theory flavor. The more applied part comes at the end. The presentation is by Dongning Guo, Dror Baron, and Shlomo Shamai entitled Single-letter Characterization of Signal Estimation from Linear Measurements. More on that later.

The following preprints showed up on Arxiv:

The Gelfand widths of $\ell_p$-balls for $0 \lt p\leq 1$ by Simon Foucart, Alain Pajor, Holger Rauhut, Tino Ullrich. The abstract reads:
We provide sharp lower and upper bounds for the Gelfand widths of $\ell_p$-balls in the $N$-dimensional $\ell_q^N$-space for $0 \lt p\le 1$ and $p \lt q \le 2$ and Such estimates are highly relevant to the novel theory of compressive sensing, and our proofs rely on methods from this area.
K-Dimensional Coding Schemes in Hilbert Spaces by Andreas Maurer and Massimiliano Pontil. The abstract reads:
This paper presents a general coding method where data in a Hilbert space are represented by finite dimensional coding vectors. The method is based on empirical risk minimization within a certain class of linear operators, which map the set of coding vectors to the Hilbert space. Two results bounding the expected reconstruction error of the method are derived, which highlight the role played by the codebook and the class of linear operators. The results are specialized to some cases of practical importance, including K-means clustering, nonnegative matrix factorization and other sparse coding methods.
and of related interest:
Dominated concentration by Andreas Maurer. The abstract reads:
The concentration properties of one random variable may be governed by the values of another random variable which is concentrated and more easily analyzed. We present a general concentration inequality to handle such cases and apply it to the eigenvalues of the Gram matrix for a sample of independent vectors distributed in the unit ball of a Hilbert space. For large samples the deviation of the eigenvalues from their mean is shown to scale with the largest eigenvalue.


It looks like there is going to be an X-prize for BCI. For those who don't know what an X-prize is, it's really the equivalent of the DARPA grand challenge but more dedicated to civilian approaches and it is non-governemental making it likely to not have restrictions on citizenship. The most recent X-prize was won by Burt Rutan when he built and flew twice the Spaceship one into space. Well this time, Peter Diamandis (hey Peter, what's up with this picture of you in microgravity in a Russian plane, I thought you were floating in your own 737 :-)), the originator of the X-prize is building some "steam" to get people to pitch in some money for the BCI X-prize. Can a Compressive Sensing-EEG system compete ? Time will tell :-). In the meantime, here is Ray Kurzweil view on the prize:




Credit: NASA, ESA, David Jewitt, Hubble captures picture of asteroid collision! (via the Bad Astronomy blog).

Wednesday, February 03, 2010

CS: A longer post!


I lied yesterday. Today's entry is the longest one. On MathOverflow, I found a question related to Compressive sensing: Sparse approximate representation of a collection of vectors and was impressed by the quality of the crowd responding to the questions. One of them is Suresh Venkatasubramanian the author among other things of the now famous Geomblog. Suresh as it happens was the person introducing Emmanuel Candes at SODA in Austin last week. After much thoughts about the text of the introduction, he decided to go with a limerick.

I just found the following MS Thesis entitled Compressive Sampling for PPM and FSK Modulated Signals by Shahzad Sarwar Gishkori. The abstract of thesis reads:
Efficiency of the Analog to Digital Converters (ADCs) has always been an issue of concern, especially, when it comes to sampling wide band signals which require extremely high sampling rates. As the systems with wide band signals are gaining the front position in digital communications, the need to find ways to reduce the sampling rates of ADCs but still maintaining exact reconstruction, is becoming ever more resurgent. In this thesis we present the utilization of a newly discovered technique to reduce the sampling rates much below the Nyquist rates. We explore the combination of Compressive Sampling (CS) with Pulse Position Modulation (PPM) and Frequency Shift Keying (FSK) modulation schemes. CS has been suggested for 'sparse signals'. Sparsity helps represent the signal in much less dimensions. We evaluate the suitability of this technique for PPM and FSK modulated signals in multipath fading environments so as to reduce the complexity at the receiver side. We detect the signals without having to first estimate the channel. We present scenarios where we can achieve the most from the combination of CS and PPM/FSK. We extend this frame work to Ultra Wide Band (UWB) applications. We also give theoretical expressions for the error probabilities of our signal models. The real challenge, with regard to using CS, is to reconstruct the signal from its reduced dimensions. In this respect, we have opted for the Orthogonal Matching Pursuit (OMP) algorithm for most of the cases, nonetheless, we elaborate on other available reconstruction methods as well.


I believe I did not link to these SAMPTA papers. Here they are now: Compressed sensing signal models - to infinity and beyond? by Thomas Blumensath, Mike Davies. The abstract reads:
Compressed sensing is an emerging signal acquisition technique that enables signals to be sampled well below the Nyquist rate, given a finite dimensional signal with a sparse representation in some orthonormal basis. In fact, sparsity in an orthonormal basis is only one possible signal model that allows for sampling strategies below the Nyquist rate. We discuss some recent results for more general signal models based on unions of subspaces that allow us to consider more general structured representations. These include classical sparse signal models and finite rate of innovation systems as special cases. We consider the dimensionality conditions for two aspects of the compressed sensing inverse problem: the existence of one-to-one maps to lower dimensional observation spaces and the smoothness of the inverse map. On the surface Lipschitz smoothness of the inverse map appears to limit the applicability of compressed sensing to infinite dimensional signal models. We therefore discuss conditions where smooth inverse maps are possible even in infinite dimensions. Finally we conclude by mentioning some recent work which develops the these ideas further allowing the theory to be extended beyond exact representations to structured approximations.

Sampling of Sparse Signals in Fractional Fourier Domain by Ayush Bhandari, Pina Marziliano. The abstract reads:
In this paper, we formulate the problem of sampling sparse signals in fractional Fourier domain. The fractional Fourier transform (FrFT) can be seen as a generalization of the classical Fourier transform. Extension of Shannon's sampling theorem to the class of signals which are fractional bandlimited shows its association to a Nyquist-like bound. Thus proving that signals that have a non-bandlimited representation in FrFT domain cannot be sampled. We prove that under suitable conditions, it is possible to sample sparse (in time) signals by using the Finite Rate of Innovation (FRI) signal model. In particular, we propose a uniform sampling and reconstruction procedure for a periodic stream of Diracs, which have a nonbandlimited representation in FrFT domain. This generalizes the FRI sampling and reconstruction scheme in the Fourier domain to the FrFT domain.

As an example of the concept of rate of innovation, signals that are linear combinations of a finite number of Diracs per unit time can be acquired by linear filtering followed by uniform sampling. However, in reality, samples are not noiseless. In a recent paper, we introduced a novel stochastic algorithm to reconstruct a signal with finite rate of innovation from its noisy samples. Even though variants of this problem has been approached previously, satisfactory solutions are only available for certain classes of sampling kernels, for example kernels which satisfy the Strang–Fix condition. In our paper, we considered the infinite-support Gaussian kernel, which does not satisfy the Strang–Fix condition. Other classes of kernels can be employed. Our algorithm is based on Gibbs sampling, a Markov chain Monte Carlo (MCMC) method. This paper summarizes the algorithm and provides numerical simulations that demonstrate the accuracy and robustness of our algorithm.

In a different direction, introducing us to the Random Coordinate Descent Method and its convergence property, we have: Efficiency of coordinate descent methods on huge-scale optimization problems by Yurii Nesterov. The abstract reads:
In this paper we propose new methods for solving huge-scale optimization problems.
For problems of this size, even the simplest full-dimensional vector operations are very expensive. Hence, we propose to apply an optimization technique based on random partial update of decision variables. For these methods, we prove the global estimates for the rate of convergence. Surprisingly enough, for certain classes of objective functions, our results are better than the standard worst-case bounds for deterministic algorithms. We present constrained and unconstrained versions of the method, and its accelerated variant. Our numerical test confirms a high efficiency of this technique on problems of very big size.
in the same issue we also have:A Fast Algorithm for Total Variation Image Reconstruction from Random Projections by Yunhai Xiao, Junfeng Yang. The abstract:
Total variation (TV) regularization is popular in image restoration and reconstruction due to its ability to preserve image edges. To date, most research activities on TV models concentrate on image restoration from blurry and noisy observations, while discussions on image reconstruction from random projections are relatively fewer. In this paper, we propose, analyze, and test a fast alternating minimization algorithm for image reconstruction from random projections via solving a TV regularized least-squares problem. The per-iteration cost of the proposed algorithm involves a linear time shrinkage operation, two matrix-vector multiplications and two fast Fourier transforms. Convergence, certain finite convergence and $q$-linear convergence results are established, which indicate that the asymptotic convergence speed of the proposed algorithm depends on the spectral radii of certain submatrix. Moreover, to speed up convergence and enhance robustness, we suggest an accelerated scheme based on an inexact alternating direction method. We present experimental results to compare with an existing algorithm, which indicate that the proposed algorithm is stable, efficient and competitive with TwIST \cite{TWIST} --- a state-of-the art algorithm for solving TV regularization problems.
A Pure L1-norm Principal Component Analysis by J.P. Brooks, Jose H. Dula, E.L. Boone. The abstract:
The $L_1$ norm has been applied in numerous variations of principal component analysis (PCA). $L_1$-norm PCA is an attractive alternative to traditional $L_2$-based PCA because it can impart robustness in the presence of outliers and is indicated for models where standard Gaussian assumptions about the noise may not apply. Of all the previously-proposed PCA schemes that recast PCA as an optimization problem involving the $L_1$ norm, none provide globally optimal solutions in polynomial time. This paper proposes an $L_1$-norm PCA procedure based on the efficient calculation of the optimal solution of the $L_1$-norm best-fit hyperplane problem. We present a procedure called $L_1$-PCA$^*$ based on the application of this idea that fits data to hyperplanes of successively smaller dimension, the orthogonal vectors of which are successive directions of minimum variation. The procedure is implemented and tested on a diverse problem suite. Our tests establish conditions for which $L_1$-PCA$^*$ is suitable.
I also found the following on Arxiv today:

Regularized Modified-BPDN for compressive sensing with partially known support by Wei Lu, Namrata Vaswani. The abstract reads:
We study the problem of reconstructing a sparse signal from a limited number of noisy measurements, when a part of its support and the signal estimate on it are known. The support and signal estimate can be obtained from prior knowledge, e.g., in a real-time dynamic MRI application, they could be the support and signal estimate from the previous time instant. We propose regularized Modified Basis Pursuit Denoising (regularized modified-BPDN) and bound its reconstruction error. Since the bounds are computable, we are able to use Monte Carlo to compare our average bounds with those for modified-BPDN and for LS-CS under various conditions, and show that (a) the regularized modified-BPDN bounds are always smaller than or equal to those of the others and (b) they are much smaller when the available number of measurements is small.
While we were just talking about quantization the other day ( see Q&A with Esther Rodriguez-Villegas on a Compressive Sensing EEG), here is some help on that front: Sobolev Duals for Random Frames and Sigma-Delta Quantization of Compressed Sensing Measurements by Sinan Güntürk, Alex Powell, Rayan Saab, Özgur Yilmaz. The abstract reads:
Quantization of compressed sensing measurements is typically justified by the robust recovery results of Cand\`es, Romberg and Tao, and of Donoho. These results guarantee that if a uniform quantizer of step size $\delta$ is used to quantize $m$ measurements $y = \Phi x$ of a $k$-sparse signal $x \in \R^N$, where $\Phi$ satisfies the restricted isometry property, then the approximate recovery $x^#$ via $\ell_1$-minimization is within $O(\delta)$ of $x$. The simplest and commonly assumed approach is to quantize each measurement independently. In this paper, we show that if instead an $r$th order $\Sigma\Delta$ quantization scheme with the same output alphabet is used to quantize $y$, then there is an alternative recovery method via Sobolev dual frames which guarantees a reduction of the approximation error by a factor of $(m/k)^{(r-1/2)\alpha}$ for any $0 \lt \alpha \lt 1$, if $m \gtrsim_r k (\log N)^{1/(1-\alpha)}$. The result holds with high probability on the initial draw of the measurement matrix $\Phi$ from the Gaussian distribution, and uniformly for all $k$-sparse signals $x$ that satisfy a mild size condition on their supports.
I also found a series of courses, summary and upcoming meetings:

Ben Recht is teaching Convex Geometry inHigh-Dimensional Data Analysis, CS838 Topics In Optimization. His interesting introduction slides are here. They make a notable mention of recommender systems.

Here is a small summary on Compressed Sensing: Basic results and self contained proofs by Shai Shalev-Shwartz. The abstract reads:

Compressed sensing is a linear dimensionality reduction technique which utilizes a prior assumption that the original vector is (approximately) sparse in some basis. In this note we summarize some of the known results and provide self contained, easy to follow, proofs.

The Banff International Research Station for Mathematical Innovation and Discovery is organizing a meeting on:

Sparse and Low Rank Approximation
Arriving Sunday, March 6 and departing Friday, March 11, 2011

Organizers: Gitta Kutyniok (University of Osnabrueck), Holger Rauhut (University of Bonn), Joel Tropp (California Institute of Technology), Ozgur Yilmaz (University of British Columbia).

Confirmed Participants

Information for Participants

Objectives

The workshop will focus on the following three subtopics.

Sparse Approximation

The field of sparse approximation is concerned with the problem of representing a target vector using a short linear combination of vectors drawn from a large, fixed collection called a dictionary. The earliest applications arose in approximation theory for functions and operators. A closely related classical problem is variable selection in regression. Modern applications include machine learning, signal and image processing, and numerical analysis.

Although sparse approximation is computationally hard in the general case, contemporary research has identified situations where tractable algorithms can provably solve sparse approximation problems. Some of the most interesting recent advances concern dictionary learning and sparse approximation of random signals.

Compressed Sensing

Compressed sensing is a new field which has seen enormous interest and growth. Quite surprisingly, it predicts that sparse high-dimensional signals can be recovered from what was previously considered highly incomplete measurements (information) by using efficient algorithms: convex relaxation methods, such as $ell_1$-minimization and greedy algorithms. This discovery has led to a fundamentally new approach to certain signal and image recovery problems. Applications include signal acquisition, A/D conversion, radar, astronomy and more.

Current research focuses on efficient algorithms as well as to providing recovery guarantees for certain measurement matrices. So far mainly random constructions for good measurement matrices in this context are known, and for this reason mathematical research in compressive sensing exploits many tools from probability theory and geometry of Banach spaces.

The workshop shall initiate a fertile discussion between the different groups of mathematicians, statisticians, and computer scientists, and experts from application areas, on the one hand to advance research in this highly topical area by combining different techniques, and on the other hand to bring problems from application areas to the attention of more theoretical oriented researchers.

Matrix identification: rank minimization, algorithms, and recovery results

Rank minimization has its roots in image compression algorithms, learning theory, and collaborative filtering. In a nutshell, collaborative filtering is the task of making automatic predictions about the interests of a user by collecting taste information from many users. A simple mathematical model for this setup can be described by the matrix completion problem where one has only a few observations of the entries of a low-rank matrix and tries to complete the missing entries. More generally, one may consider the problem of minimizing the rank of a matrix subject to some general linear constraint. A quite surprising recent result due to Candès and Tao in this direction shows that many $ntimes n$ matrices of rank $r$ can be recovered from only ${cal O} (nr log(n) )$ observations of its entries via nuclear norm minimization (the $ell_1$-norm of the singular values). It turns out that many of the ideas and techniques from compressive sensing can be transferred to the rank-minimization problem or other matrix recovery problems.

This direction is currently in its beginning stage and far more developments can be expected in the near future. Therefore, such a workshop would be a unique opportunity to discuss the most recent results, stimulate new research in the interplay between sparse approximation, compressed sensing and low rank matrix recovery problems, and, in particular, formulate open questions, and thereby significantly influence the research in this field in the future.

Application Areas

We would like to put a focus on the following applications of sparse approximation.

- Astronomical image and signal processing

- Radar imaging

- Wireless communication

- Seismology

We will invite experts from these application fields in order to stimulate discussions between practitioners and mathematicians, and thereby initiating new research directions and new research collaborations.


There will also be a Workshop on Pseudo-randomness in Mathematical Structures at the IAS

June 14 - 18, 2010

Organizers: Jean Bourgain, Russell Impagliazzo, Peter Sarnak and Avi Wigderson

A common theme in many seemingly disjoint mathematical areas is to quantify the extent to which natural deterministic mathematical objects have properties similar to those of random objects. For example, is the variance of the distribution of primes approximately that expected for a random set of the same density? When are multiplication and addition over fields ``uncorrelated''? When do the Cayley graphs for groups have the expansion of random graphs? How random are the orbits of natural dynamical systems?

On the other side, computer science applications often require deterministic mathematical structures with such pseudo-random properties. For example, graphs with random-like expansion are used for applications ranging from distributed protocols for leader selection to network routing to sorting. In fact, the central question of computational complexity can be viewed as deterministically constructing a function that is random-like with respect to the ability of small circuits to compute it.

This workshop will aim to highlight parallels and connections between approaches to pseudo-randomness in different areas of mathematics, and between the mathematical and computational approaches to pseudo-randomness. Invited speakers will be eminent researchers in such areas as additive number theory, algorithm design, analysis, combinatorics, computational complexity, cryptography, dynamical systems, ergodic theory, group theory, number theory, and statistical mechanics. The first two days of the workshop will be devoted to tutorials giving an overview of the role of pseudo-randomness in some of the areas mentioned. These tutorials will not require knowledge of any particular disciplines, and will be accessible to graduate students in all areas of mathematics and computer science. The subsequent three days will highlight exciting related research developments, but will also be accessible to a mixed audience of computer scientists and mathematicians. A list of confirmed speakers and a tentative schedule may be found at http://www.math.ias.edu/tentative program.

The workshop will take place at the Institute from June 14-18, 2010. Most events will be held in Wolfensohn Hall. Researchers in all related areas are welcome to participate, and we will have some funding to support graduate students.

The workshop is funded by the National Science Foundation grant DMS-0835373, ``Pseudo-randomness in mathematics and computer science''.

Inquires should be addressed to: pseudo.workshop@gmail.com.


Credit photo: Original for Marie Claire Magazine cover as uncovered by Photoshopdisasters, and the same photo analyzed by the error level analyzer software. The site is at: http://www.errorlevelanalysis.com/. I wonder if there would be a more obvious way to do this with random projections.

Tuesday, February 02, 2010

CS: This week's long post.

The Arxiv experimental search is broken and this is a problem for those of us interested in cross-cutting fields such as compressive sensing. Case in point, there is currently no way to find out if a certain paper has been mentioned in later preprints. In my case, the papers in question are the ones about opaque lenses by Ivo Vellekoop et al such as Measuring the Transmission Matrix in Optics : An Approach to the Study and Control of Light Propagation in Disordered Media by Sebastien Popoff, Goeffroy Lerosey, Remi Carminati, Mathias Fink, A. Claude Boccara, Sylvain Gigan. The abstract reads:
We introduce a method to experimentally measure the monochromatic transmission matrix of a complex medium in optics. This method is based on a spatial phase modulator together with a full-field interferometric measurement on a camera. We determine the transmission matrix of a thick random scattering sample. We show that this matrix exhibits statistical properties in good agreement with random matrix theory and allows light focusing and imaging through the random medium. This method might give important insights into the mesoscopic properties of complex medium.
I'll come back to this paper later. One of the author Mathias Fink, has some interesting views on disordered media.
I am sure that not relying on random matrix theory and svd regularization but on compressive sensing and l1/l0 regularization might prove worth it. In a different direction, I was intringued by these Random Lasers.

The following popped up on the interwebs:

Closed-Form Reconstruction of Sparse Signals from Limited Numbers of Irregular Frequencies by Andrew Yagle. The abstract reads:

The goal is to reconstruct a sparse signal or image from some, but not all, of its discrete Fourier transform (DFT) values. We derive a condition that ensures the sparse solution can be computed in closed form by thresholding the inverse DFT of the known DFT values, with unknown DFT values set to zero.

Hosein Mohimani just let me know that there is a new paper on SL0 entitled: Sparse Recovery using Smoothed $\ell^0$ (SL0): Convergence Analysis by Hosein Mohimani, Massoud Babaie-Zadeh, Irina Gorodnitsky, Christian Jutten. The abstract reads:
Finding the sparse solution of an underdetermined system of linear equations has many applications, especially, it is used in Compressed Sensing (CS), Sparse Component Analysis (SCA), and sparse decomposition of signals on overcomplete dictionaries. We have recently proposed a fast algorithm, called Smoothed $\ell^0$ (SL0), for this task. Contrary to many other sparse recovery algorithms, SL0 is not based on minimizing the $\ell^1$ norm, but it tries to directly minimize the $\ell^0$ norm of the solution. The basic idea of SL0 is optimizing a sequence of certain (continuous) cost functions approximating the $\ell^0$ norm of a vector. However, in previous papers, we did not provide a complete convergence proof for SL0. In this paper, we study the convergence properties of SL0, and show that under a certain sparsity constraint in terms of Asymmetric Restricted Isometry Property (ARIP), and with a certain choice of parameters, the convergence of SL0 to the sparsest solution is guaranteed. Moreover, we study the complexity of SL0, and we show that whenever the dimension of the dictionary grows, the complexity of SL0 increases with the same order as Matching Pursuit (MP), which is one of the fastest existing sparse recovery methods, while contrary to MP, its convergence to the sparsest solution is guaranteed under certain conditions which are satisfied through the choice of parameters.
The SL0 algorithm can be found here.


We consider the Linear Programming (LP) solution of the Compressed Sensing (CS) problem over reals, also known as the Basis Pursuit (BasP) algorithm. The BasP allows interpretation as a channel-coding problem, and it guarantees error-free reconstruction with a properly chosen measurement matrix and sufficiently sparse error vectors. In this manuscript, we examine how the BasP performs on a given measurement matrix and develop an algorithm to discover the sparsest vectors for which the BasP fails. The resulting algorithm is a generalization of our previous results on finding the most probable error-patterns degrading performance of a finite size Low-Density Parity-Check (LDPC) code in the error-floor regime. The BasP fails when its output is different from the actual error-pattern. We design a CS-Instanton Search Algorithm (ISA) generating a sparse vector, called a CS-instanton, such that the BasP fails on the CS-instanton, while the BasP recovery is successful for any modification of the CS-instanton replacing a nonzero element by zero. We also prove that, given a sufficiently dense random input for the error-vector, the CS-ISA converges to an instanton in a small finite number of steps. The performance of the CS-ISA is illustrated on a randomly generated $512\times120$ matrix. For this example the CS-ISA outputs the shortest instanton (error vector) pattern of length 11.
Some new items from the Rice repository:

Sparse Sensing DNA Microarray-Based Biosensor: Is It Feasible? by Mojdeh Mohtashemi. The asbtract reads:

Conventional microarray-based biosensors can only detect a limited number of organisms, and adding sensor capabilities requires re-engineering of reagents and devices to detect the presence of a novel microbial organism. To overcome these limitations, the size of the microarray may need to be prohibitively large, an impractical proposition, cost-wise, using current technology. We hypothesized that a relatively small number of oligomers is sufficient to design a microarray capable of differentiating between the genomic signatures of multiple organisms. To test this hypothesis, we designed a sparse, pseudorandom prototype microarray-based biosensor by generating 12,600 25bp oligomer probes derived from a mathematical model based on random selection of DNA sequences from seven pathogenic prokaryotic genomes. To enable identification of novel organisms, a reference library of pure genomic DNA was generated from three simulant organisms that are known to be phylogenetically distant from the seven base species used to generate the probes. These simulants were combined to produce complex DNA samples meant to mimic the uncertainty and complexity of an unknown environmental genomic background. A mathematical model was then developed to capture the signature of each simulant organism. The model detected the presence of all three simulant organisms in the mixed DNA samples with high accuracy.


Compressed Least-Squares Regression by Odalric-Ambrym Maillard, Rémi Munos. The abstract reads:
We consider the problem of learning, from K data, a regression function in a linear space of high dimension N using projections onto a random subspace of lower dimension M. From any algorithm minimizing the (possibly penalized) empirical risk, we provide bounds on the excess risk of the estimate computed in the projected subspace (compressed domain) in terms of the excess risk of the estimate built in the high-dimensional space (initial domain). We show that solving the problem in the compressed domain instead of the initial domain reduces the estimation error at the price of an increased (but controlled) approximation error. We apply the analysis to Least-Squares (LS) regression and discuss the excess risk and numerical complexity of the resulting ``Compressed Least Squares Regression'' (CLSR) in terms of N, K, and M. When we choose M=O(\sqrt{K}), we show that CLSR has an estimation error of order O(\log K / \sqrt{K}).



Beyond alias hierarchical scale curvelet interpolation of regularly and irregularly sampled seismic data by Mostafa Naghizadeh and Mauricio D. Sacchi. The abstract reads:

We propose a robust interpolation scheme for aliased regularly sampled seismic data that uses the curvelet transform. In a first pass, the curvelet transform is used to compute the curvelet coefficients of the aliased seismic data. The aforementioned coefficients are divided into two groups of scales: alias-free and alias-contaminated scales. The alias-free curvelet coefficients are upscaled to estimate a mask function that is used to constrain the inversion of the alias-contaminated scale coefficients. The mask function is incorporated into the inversion via a minimum norm least squares algorithm that determines the curvelet coefficients of the desired alias free data. Once the aliasfree coefficients are determined, the curvelet synthesis operator is used to reconstruct seismograms at new spatial positions. The proposed method can be used to reconstruct both regularly and irregularly sampled seismic data. We believe that our exposition leads to a clear unifying thread between f-x Spitz (1991) and f-k Gulunay (2003) beyond-alias interpolation methods and curvelet reconstruction. Likewise in f-x and f-k interpolation, we stress the necessity of examining seismic data at different scales (frequency bands) in order to come up with viable and robust interpolation schemes. Synthetic and real data examples are used to illustrate the performance of the proposed curvelet interpolation method.

Sunday, January 31, 2010

Going Hollywood with Compressive Sensing

As some of you know, Justin Romberg has been an advisor to the Numb3rs television series. Well it looks like the screenwriters of the new Battlestar Galactica TV series could have used a scientific advisor of that caliber (by the way, I did not mean to say that screenwriters for Numb3rs actually used all of Justin's inputs). Chris Bilder points out how performing Group Testing to detect Cylons could have helped the script and change the storyboard (I mentioned this study before). First, let us give some context about what the Cylons are:


Then let us introduce Chris Bilder's presentation (first 10 minutes of the presentation) on the subject:



Chris Bilder's page on his Chance paper is here. The full video of the talk is here. Let us recall that group testing is connected to compressive sensing in that it solves the same problem, finding a sparse element in a large batch of elements with the fewest number of tests (measurements). As it turns out, my webcrawler found Mark Iwen's latest presentation on the subject entitled Interpolation with Sparsity Assumptions: From Syphilis Testing to Sparse Fourier Transforms.

But coming back to the title of this entry, wouldn't it be neat if one could use a random lens imager in one of those CSI plots ?

Saturday, January 30, 2010

CS: Q&A with Esther Rodriguez-Villegas on a Compressive Sensing EEG

[I have updated this entry after some thoughts]

In Thursday's entry, I mentioned the paper by Amir Abdulghani, Alexander Casson and Esther Rodriguez-Villegas entitled Quantifying the Feasibility of Compressive Sensing in Portable Electroencephalography Systems where the authors look at an EEG compressive sensing system. Then, I stated the following:

....The result for 20 channels springs from applying a compressed sensing design such as the one shown above. The question I have is really how can we change this design entirely: For instance, instead of applying a simple \phi measurement to the signals after they have been amplified and digitized, what about providing some randomness in the reference voltage ? what about removing entirely both the Op-amps ?...

I had a small conversation with Esther Rodriguez-Villegas and here is her response to the question above republished with her permission (-as usual-)

Dear Igor,

Thanks for your email. We've heard of your blog before. It is very interesting.

....

On a different note we found the EEG discussion on your blog interesting. I personally don't think that the randomness in the reference voltage would work though. The latter would somehow be equivalent to "downsampling the signal with dither", or in different words, the randomness in the reference voltage would create a similar effect to the input noise already introduced by the amplifiers themselves and then I presume one would be downsampling. However I don't think this would be possible because the minimum sampling rate was determined to be what it is for different applications considering the existing amplifiers noise, so I doubt it would be viable to further reduce this sampling rate after adding a signal which, from the circuit point of view, would play a similar role to this noise. The other alternative of switching on and off the reference would not be a practical option either because of slew-rate limitations of the amplifiers, which could only be overcome by pumping otherwise unnecessary biasing currents.

At the same time, eliminating the amplifiers is not an option because they are needed to "adjust" the already very weak signal levels to the ones required by the A/D converters, and in some cases also act as filters for, for example, the offset drift introduced by the electrodes, as well as high frequency noise. One could argue that having a better converter to cope with an increased range may do the job, but the problem with that would be that converters themselves require considerable amount of power, and as the number of bits of resolution they provide increases they become much more power hungry (apart from considerably more difficult to design). Also, if one thinks of a system that ideally should be operated on small batteries which provide a very limited voltage, this on its own represents a limitation for the converter range. So in the end, in the context of a low power portable system, for the front end, having an amplifier followed by a lower resolution converter is going to be the best option as long as the blocks are intelligently designed and customised, which from the circuit designer perspective is not a simple issue at all.

Now, your overall suggestion is interesting because even if those two options are not possible, there may be alternative ones that are. Fundamentally, I would say that thinking of a system in which part of the processing which is now thought of at a digital level, is "transferred back" to the front end and carried out in the analog domain may potentially significantly reduce both, the "requirements" of the converter and also the overall power consumption of the approach. This is because analog can offer a massively better tradeoff in terms of computational complexity versus power than digital, as long as speed of the operations is not a major issue and we are not trying to deal with resolutions of more than about 10 bits. So as a conclusion, I would say that I definitely agree with you in the fact that we should "think out of the box" and make an effort to redefine the system. I would go further than that to say that most probably that "redefinition" should follow an approach in which part of the compression algorithm is implemented earlier on in the "system chain" possibly following an analog based approach.

Anyway, to this end, we have a paper under review at the moment showing the performance of a straightforward CS application to EEG, tailored to establish a baseline performance of the approach to aid future EEG designers to make system level decisions. From that paper I would say that in general better performance is needed, although it is left to the application specific designer to decide. Certainly however there is a lot of potential here for EEG-tailored system level oriented compressive sensing research.

Best regards,

Esther

I did not realize that the op-amp was also acting as a filter, this is good to know. From this description, it seems obvious that at some point one should investigate an electrode based solution. While roaming through the openEEG list, I was made aware of the fact that there are two types of electrodes : active and passive. The passive ones require that they be wetted with eye drops in order to make a good contact with the scalp. In case, they are not wetted, there seems to be an extreme sensitivity of the electrode to the environmental EMI coming from your everyday appliances. In that case, one could conceive the use of shielded electrodes. The active electrodes remove the need for this eye drop liquid agent but there is the danger of having a "live" electrode. With this in mind, one could probably think of the' early in the chain' comment that Esther suggests, whereby a very low voltage active electrode could provide some type of random modulation.

Since we are thinking outside the box and we are dealing with amplifiers (or their potential removal) there is also the possibility of extreme quantization of the signal. Work along those lines include that of Petros Boufounos and Richard Baraniuk in 1-Bit Compressive Sensing and that of Laurent Jacques, David Hammond and Jalal Fadili, as featured here.

Finally, with regards to Esther's other comment on the reference voltage, it seems that the concept of Garbage in, Garbage out does not really apply in compressive sensing when done right. I am making a particular reference to an early paper by Joel Tropp, Michael Wakin, Marco Duarte, Dror Baron, and Richard Baraniuk entitled Random Filters For Compressive Sampling And Reconstruction where one can read the following sentence:
At first glance, one might think this method would convert a signal into garbage.
As I said before, you don't often see that type of assessment in publications. I tried these random filters, and it worked for the limited case I computed.

Finally, to give some perspective with regards to low cost EEGs used in BCI-like systems, a current low cost commercially available Emotiv EEG system, with 14 electrodes, is limited by its battery capability of about 12 hours. It also uses passive electrodes and therefore liquid drops as the liquid needed to make good contact with the scalp. One can expect this liquid to evaporate over a 12 hour time period.

Thanks Esther for sharing your views!

Credit Photo: Emotiv, Emotiv Headset.

Friday, January 29, 2010

CS: On Low Rank Matrix Approximations with Applications to Synthesis Problem in CS, Learning Sparse Systems, ADM for NMF, Proximal Splitting Methods,

To finish this week, here are several papers directly or not so directly related to compressive sensing. Enjoy!

On Low Rank Matrix Approximations with Applications to Synthesis Problem in Compressed Sensing by Anatoli Juditsky, Fatma Kilinc Karzan, Arkadii S. Nemirovski. The abstract reads:
We consider the synthesis problem}of Compressed Sensing - given s and an MXn matrix A, extract from it an mXn submatrix A', certified to be s-good, with m as small as possible. Starting from the verifiable sufficient conditions of s-goodness, we express the synthesis problem as the problem of approximating a given matrix by a matrix of specified low rank in the uniform norm. We propose randomized algorithms for efficient construction of rank k approximation of matrices of size mXn achieving accuracy bounds O(1)sqrt({ln(mn)/k) which hold in expectation or with high probability. We also supply derandomized versions of the approximation algorithms which does not require random sampling of matrices and attains the same accuracy bounds. We further demonstrate that our algorithms are optimal up to the logarithmic in m and n factor. We provide preliminary numerical results on the performance of our algorithms for the synthesis problem.

We propose a novel algorithm for sparse system identification in the frequency domain. Key to our result is the observation that the Fourier transform of the sparse impulse response is a simple sum of complex exponentials, whose parameters can be efficiently determined fromonly a narrowfrequency band. From this perspective, we present a sub-Nyquist sampling scheme, and show that the original continuous-time system can be learned by considering an equivalent low-rate discrete system. The impulse response of that discrete system can then be adaptively obtained by a novel frequency-domain LMS filter, which exploits the parametric structure of the model. Numerical experiments confirm the effectiveness of the proposed scheme for sparse system identification tasks.

An Alternating Direction Algorithm for Nonnegative Matrix Factorization by Yin Zhang, The abstract reads:
We extend the classic alternating direction method for convex optimization to solving the non-convex, nonnegative matrix factorization problem and conduct several carefully designed numerical experiments to compare the proposed algorithms with the most widely used two algorithms for solving this problem. In addition, the proposed algorithm is also briefly compared with two other more recent algorithms. Numerical evidence shows that the alternating direction algorithm tends to deliver higher-quality solutions with faster computing times on the tested problems. A convergence result is given showing that the algorithm converges to a Karush-Kuhn-Tucker point whenever it converges.

Proximal Splitting Methods in Signal Processing by Patrick L. Combettes, and Jean-Christophe Pesquet. The abstract reads:
The proximity operator of a convex function is a natural extension of the notion of a projection operator onto a convex set. This tool, which plays a central role in the analysis and the numerical solution of convex optimization problems, has recently been introduced in the arena of signal processing, where it has become increasingly important. In this paper, we review the basic properties of proximity operators which are relevant to signal processing and present optimization methods based on these operators. These proximal splitting methods are shown to capture and extend several well-known algorithms in a unifying framework. Applications of proximal methods in signal recovery and synthesis are discussed.

Piotr Indyk has a talk on Sparse Recovery Using Sparse Matrices, given in various forms in various places.

Holger Rauhut has some lecture notes entitled Compressive sensing and structured random matrices. These lecture Notes are still under construction. If you have comments of any sort, he would be happy to receive them.

Thursday, January 28, 2010

CS: CS for Missing Data Imputation and Digit Recognition, CS EEG, CS 60 GHz UWB, Training Over Sparse Multipath Channels, CFP


Jort Gemmeke just sent me the following:
Hi Igor,

I finally found time to update my website (www.amadana.nl). There are two new papers which are probably of interest for this community. The first is "Compressive Sensing for Missing Data Imputation in Noise Robust Speech Recognition", which is a more detailed description of my work on compressive sensing for imputing missing data in speech.

In "Noise robust exemplar-based connected digit recognition" we use the same concept of representing speech as a sparse linear combination of exemplars, but in this work we model the noisy speech as a linear combination of both speech and noise exemplars. Rather than use the activations to do source seperation, we do classification directly on the clean speech exemplar activations. Interestingly, although not discussed in detail in the paper, we obtained better (much) results using a sparse solver which minimizes the Kulback-Leibler divergence than the customary sparse solvers which minimize the Euclidean distance.

Cheers,

Jort
The emphasis was mine, I am sure that at some point, we will see more of these KL based solvers. The two papers are: Compressive Sensing for Missing Data Imputation in Noise Robust Speech Recognition by Jort Florent Gemmeke, Hugo Van hamme, Bert Cranen, Lou Boves.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), and to replace (impute) the missing ones by clean speech estimates. Conventional imputation techniques employ parametric models and impute the missing features on a frame-by-frame basis. At low SNR’s these techniques fail, because too many time frames may contain few, if any, reliable features. In this paper we introduce a novel non-parametric, exemplar based method for reconstructing clean speech from noisy observations, based on techniques from the field of Compressive Sensing. The method, dubbed sparse imputation, can impute missing features using larger time windows such as entire words. Using an overcomplete dictionary of clean speech exemplars, the method finds the sparsest combination of exemplars that jointly approximate the reliable features of a noisy utterance. That linear combination of clean speech exemplars is used to replace the missing features. Recognition experiments on noisy isolated digits show that sparse imputation outperforms conventional imputation techniques at SNR = −5 dB when using an ideal ‘oracle’ mask. With error-prone estimated masks sparse imputation performs slightly worse than the best conventional technique.
and Noise robust exemplar-based connected digit recognition by Jort Gemmeke and Tuomas Virtanen. The abstract reads:
This paper proposes a noise robust exemplar-based speech recognition system where noisy speech is modeled as a linear combination of a set of speech and noise exemplars. The method works by finding a small number of labeled exemplars in a very large collection of speech and noise exemplars that jointly approximate the observed speech signal. We represent the exemplars using melenergies, which allows modeling the summation of speech and noise, and estimate the activations of the exemplars by minimizing the generalized Kullback-Leibler divergence between the observations and the model. The activations of the speech exemplars are directly being used for recognition. This approach proves to be promising, achieving up to 55.8% accuracy at signal-to-noise ratio −5 dB on the AURORA-2 connected digit recognition task.

You probably recall this paper entitled Sparse Event Detection in Wireless Sensor Networks using Compressive Sensing, now there is a video presentation by one of the author and it is in Chinese.

The EEG for use in augmented cognition produces large amounts of compressible data from multiple electrodes mounted on the scalp. This huge amount of data needs to be processed, stored and transmitted and consumes large amounts of power. In turn this leads to physically large EEG units with limited lifetimes which limit the ease of use, and robustness and reliability of the recording. This work investigates the suitability of compressive sensing, a recent development in compression theory, for providing online data reduction to decrease the amount of system power required. System modeling which incorporates a review of state-of-the-art EEG suitable integrated circuits shows that compressive sensing offers no benefits when using an EEG system with only a few channels. It can, however, lead to significant power savings in situations where more than approximately 20 channels are required. This result shows that the further investigation and optimization of compressive sensing algorithms for EEG data is justified.
The result for 20 channels springs from applying a compressed sensing design such as the one shown above. The question I have is really how can we change this design entirely: For instance, instead of applying a simple \phi measurement to the signals after they have been amplified and digitized, what about providing some randomness in the reference voltage ? what about removing entirely both the Op-amps ?


In other news, the googlebot found the following paper:

60 GHz ultra wide-band (UWB) communication is an emerging technology for high speed short range communications. However, the requirement of high-speed sampling increases the cost of receiver circuitry such as analog-to-digital converter (ADC). In this paper, we propose to use a compressive sensing framework to achieve a significant reduction of sampling rate. The basic idea is based on the observation that the received signals are sparse in the time domain due to the limited multipath effects at 60 GHz wireless transmission. According to the theory of compressive sensing, by carefully designing the sensing scheme, sub-Nyquist rate sampling of the sparse signal still enables exact recovery with very high probability. We discuss an implementation for a low-speed A/D converter for 60 GHz UWB received signal. Moreover, we analyze the bit error rate (BER) performance for BPSK modulation under RAKE reception. Simulation results show that in the single antenna pair system model, sampling rate can be reduced to 2.2% with 0.3dB loss of BER performance if the input sparsity is less than 1%. Consequently, the implementation cost of ADC is significantly reduced.

I also found the following preprints on Arxiv: Training Over Sparse Multipath Channels in the Low SNR Regime by Elchanan Zwecher, Dana Porrat. The abstract reads:
Training over sparse multipath channels is explored. The energy allocation and the optimal shape of training signals that enable error free communications over unknown channels are characterized as a function of the channels' statistics. The performance of training is evaluated by the reduction of the mean square error of the channel estimate and by the decrease in the uncertainty of the channel. A connection between the entropy of the wideband channel and the required energy for training is shown. In addition, there is a linkage between the sparsity and the entropy of the channel to the number of required channel measurements when the training is based on compressed sensing. The ability to learn the channel from few measurements is connected to the low entropy of sparse channels that enables training in the low SNR regime.

We present a computationally-efficient method for recovering sparse signals from a series of noisy observations, known as the problem of compressed sensing (CS). CS theory requires solving a convex constrained minimization problem. We propose to transform this optimization problem into a convex feasibility problem (CFP), and solve it using subgradient projection methods, which are iterative, fast, robust and convergent schemes for solving CFPs. As opposed to some of the recently-introduced CS algorithms, such as Bayesian CS and gradient projections for sparse reconstruction, which become prohibitively inefficient as the problem dimension and sparseness degree increase, the newly-proposed methods exhibit a marked robustness with respect to these factors. This renders the subgradient projection methods highly viable for large-scale compressible scenarios.
The code implementing the CFP is here. Thanks Jort.

Credit: NASA, Spirit, Navigation Camera, Sol 2156. As you all know the big news tuesday was that Spirit is likely not moving any time soon.

Printfriendly