CS: A Single-letter Characterization of Optimal Noisy Compressed Sensing, Low-rank Matrix Completion, Uniqueness of Low-Rank Matrix Completion

Today, we have a potentially far reaching article and two other papers on matrix completion. Enjoy!

Dongning Guo, Dror Baron, and Shlomo Shamai, introduce us to A Single-letter Characterization of Optimal Noisy Compressed Sensing. The abstract reads:

Compressed sensing deals with the reconstruction of a high-dimensional signal from far fewer linear measurements, where the signal is known to admit a sparse representation in a certain linear space. The asymptotic scaling of the number of measurements needed for reconstruction as the dimension of the signal increases has been studied extensively. This work takes a fundamental perspective on the problem of inferring about individual elements of the sparse signal given the measurements, where the dimensions of the system become increasingly large. Using the replica method, the outcome of inferring about any fixed collection of signal elements is shown to be asymptotically decoupled, i.e., those elements become independent conditioned on the measurements. Furthermore, the problem of inferring about each signal element admits a single-letter characterization in the sense that the posterior distribution of the element, which is a sufficient statistic, becomes asymptotically identical to the posterior of inferring about the same element in scalar Gaussian noise. The result leads to simple characterization of all other elemental metrics of the compressed sensing problem, such as the mean squared error and the error probability for reconstructing the support set of the sparse signal. Finally, the single-letter characterization is rigorously justified in the special case of sparse measurement matrices where belief propagation becomes asymptotically optimal.

Low-rank Matrix Completion with Noisy Observations: a Quantitative Comparison by Raghunandan Keshavan, Andrea Montanari and Sewoong Oh. The abstract reads: 

We consider a problem of significant practical importance, namely, the reconstruction of a low-rank data matrix from a small subset of its entries. This problem appears in many areas such as collaborative filtering, computer vision and wireless sensor networks. In this paper, we focus on the matrix completion problem in the case when the observed samples are corrupted by noise. We compare the performance of three state-of-the-art matrix completion algorithms (OptSpace, ADMiRA and FPCA) on a single simulation platform and present numerical results. We show that in practice these efficient algorithms can be used to reconstruct real data matrices, as well as randomly generated matrices, accurately.

The software is here while the slides of the presentation are here.

Finally, we have: Uniqueness of Low-Rank Matrix Completion by Rigidity by Amit Singer and Mihai Cucuringu. The abstract reads:

The problem of completing a low-rank matrix from a subset of its entries is often encountered in the analysis of incomplete data sets exhibiting an underlying factor model with applications in collaborative filtering, computer vision and control. Most recent work had been focused on constructing efficient algorithms for exact or approximate recovery of the missing matrix entries and proving lower bounds for the number of known entries that guarantee a successful recovery with high probability. A related problem from both the mathematical and algorithmic point of view is the distance geometry problem of realizing points in a Euclidean space from a given subset of their pairwise distances. Rigidity theory answers basic questions regarding the uniqueness of the realization satisfying a given partial set of distances. We observe that basic ideas and tools of rigidity theory can be adapted to determine uniqueness of low-rank matrix completion, where inner products play the role that distances play in rigidity theory. This observation leads to efficient randomized algorithms for testing necessary and sufficient conditions for local completion and for testing sufficient conditions for global completion. Crucial to our analysis is a new matrix, which we call the completion matrix, that serves as the analogue of the rigidity matrix.

Credit: NASA, This image was taken with the LCROSS visible light context camera Aug. 17, 2009, from a distance of approximately 323,296 miles (520,294 km) from the Earth and 547,335 miles (880,850 km) from the moon. In this view, the Earth and moon are separated by approximately 4.8 degrees. The red/blue speckled pixels within the VIS camera are caused by cosmic ray radiation in space, and are not stars. The Centaur part of LCROSS will be smashing the moon in full force on October 9th, 3 days from now. It's going to be a nice show at 5:30 Central time.

CS: Sequential Sparse Matching Pursuit, Compressed Blind De-convolution

Here is an extension of the previous SMP code available here. The new algorithm called SSMP is introduced in  Sequential Sparse Matching Pursuit by Piotr Indyk and Radu Berinde. The abstract reads:

We propose a new algorithm, called Sequential Sparse Matching Pursuit (SSMP), for solving sparse recovery problems. The algorithm provably recovers a k-sparse approximation to an arbitrary n-dimensional signal vector x from only O(k log(n/k)) linear measurements of x. The recovery process takes time that is only near-linear in n. Preliminary experiments indicate that the algorithm works well on synthetic and image data, with the recovery quality often outperforming that of more complex algorithms, such as l_1 minimization.

Piotr just lets me know that it should be available soon. Thanks Piotr ! On the topic of blind deconvolution we talked about before, here is Compressed Blind De-convolution by Venkatesh Saligrama, Manqi Zhao. The abstract reads:

Suppose the signal x is realized by driving a k-sparse signal u through an arbitrary unknown stable discrete-linear time invariant system H. These types of processes arise naturally in Reflection Seismology. In this paper we are interested in several problems: (a) Blind-Deconvolution: Can we recover both the filter $H$ and the sparse signal $u$ from noisy measurements? (b) Compressive Sensing: Is x compressible in the conventional sense of compressed sensing? Namely, can x, u and H be reconstructed from a sparse set of measurements. We develop novel L1 minimization methods to solve both cases and establish sufficient conditions for exact recovery for the case when the unknown system H is auto-regressive (i.e. all pole) of a known order. In the compressed sensing/sampling setting it turns out that both H and x can be reconstructed from O(k log(n)) measurements under certain technical conditions on the support structure of u. Our main idea is to pass x through a linear time invariant system G and collect O(k log(n)) sequential measurements. The filter G is chosen suitably, namely, its associated Toeplitz matrix satisfies the RIP property. We develop a novel LP optimization algorithm and show that both the unknown filter H and the sparse input u can be reliably estimated.

CS: Lower Bounds for Sparse Recovery, Mathematics and Images Analysis Conference

Sometimes, the same word means different things:


Sometimes, different words mean the same thing,

• Statistics vs. Machine Learning, fight!

Sometimes, we don't know if the big O notation means the thing we think it means :-)

• From the internets, I found the following abstract from the upcoming SODA conference: Lower Bounds for Sparse Recovery by Khanh Do Ba, Piotr Indyk, Eric Price. The abstract reads:

  Over the recent years, a new *linear* method for compressing high-dimensional data has been discovered. For an n-dimensional vector x, its *sketch* is equal to Ax, where A is an m x n matrix, possibly chosen at random. Although typically the sketch length m is much smaller than the number of dimensions n, the sketch often contains plenty of information about x. A particularly useful and well-studied problem is that of sparse recovery: given Ax, recover a k-sparse vector x* (with at most k non-zeros) such that ||x-x*||_p <= C min_{k-sparse x'} ||x-x'||_q for some norm parameters p and q and an approximation factor C=C(k). Sparse recovery has numerous applications to areas such as data stream computing and compressed sensing. It is known that there exist matrices A that achieve the above guarantee with p=q=1 and constant C (in fact, even somewhat stronger bounds), with sketch length m=O(k log (n/k)). However, perhaps surprisingly, it is not known if this bound can be improved any further, even though matching lower bounds are known for specific *algorithms*, specific *matrix types*, or other recovery scenarios (e.g., involving measurement noise). The lack of tight lower bounds represents a major gap in our understanding of the problem. In this paper we make significant progress on this issue. In particular we show that: - in the deterministic case, where we require one matrix A to work for all signals x, we show a tight lower bound of Omega(k log (n/k)), thus resolving the issue completely - in the randomized case, where we require that a matrix A chosen at random from some distribution should work for a *fixed* vector x with probability at least 1-1/n, we show a lower bound of Omega(log n / log log n)

Sometimes, we think a term means something when in fact it means to the opposite:

• The Mathematics and Images Analysis (M.I.A.) Conference 2009 will be held on December 14-16 at IHP in Paris, and will feature several sparsity and compressed sensing related talks. The program is here.

CS: ExRIP, Expected RIP: Conditioning of The Modulated Wideband Converter

Ahah! Linking one of the sufficient condition for l_1 recovery to actual hardware here is something that is VERY interesting. You do recall the Technion Modulated Wideband Converter (the page is now here)? well, Moshe Mishali, Yonina C. Eldar are deriving a computable RIP-like condition to evaluate their hardware. The paper is: Expected RIP: Conditioning of The Modulated Wideband Converter by Moshe Mishali, Yonina Eldar. The abstract reads:

The sensing matrix of a compressive system impacts the stability of the associated sparse recovery problem. In this paper, we study the sensing matrix of the modulated wideband converter, a recently proposed system for sub-Nyquist sampling of analog sparse signals. Attempting to quantify the conditioning of the converter sensing matrix with existing approaches leads to unreasonable rate requirements, due to the relatively small size of this matrix. We propose a new conditioning criterion, named the expected restricted isometry property, and derive theoretical guarantees for the converter to satisfy this property. We then show that applying these conditions to popular binary sequences, such as maximal codes or Gold codes, leads to practical rate requirements.

Credit: NASA/Johns Hopkins University Applied Physics Laboratory/Carnegie Institution of Washington, One of the few photos taken by the spacecraft Messenger yesterday on its Gravity assist around Mercury. It was taken at an altitude of 15,600 kilometers (9750 miles). Closer photographs could not be taken as the spacecraft went into a safe mode.

CS: Some basic CS examples, C-SALSA, Distributed Sensing, Dictionary learning, Replica Method and Applications to CS, SLEP

Alejandro Weinstein a PhD student in the Engineering Department at the Colorado School of Mines sent me the following:

I just wrote some Matlab code with basic CS examples, using L1-Magic and CVX. I also wrote a document describing the code. They are both available at

http://control.mines.edu/mediawiki/index.php/CS_sample_code

I think they might be useful for people new to CS, so it will be great if you can mention this in your blog....

The four examples are described below:

Matlab Files Description

• ex1.m: Sensing matrix phi is random, the representation basis Psi is the canonical basis (the signal is sparse in the time domain). The recovery is done using L1-magic.

• ex2.m: Same signal and measurement as ex1.m, but the recovery is done using cvx.

• ex3.m: Same signal as ex2, but the measurement is done using the Fourier basis.

• ex4.m: Sensing matrix phi is random, the representation basis Phi is the Fourier basis (the signal is sparse in the frequency domain). The recovery is done using CVX.

Thank you Alejandro !

It looks we have a contender to SPGL1 in the shape of C-SALSA as witnessed in this paper: A fast algorithm for the constrained formulation of compressive image reconstruction and other linear inverse problems by Manya V. Afonso, J. Bioucas-Dias, and Mario Figueiredo. The abstract reads:

Ill-posed linear inverse problems (ILIP), such as restoration and reconstruction, are a core topic of signal/image processing. A standard approach to deal with ILIP uses a constrained optimization problem, where a regularization function is minimized under the constraint that the solution explains the observations sufficiently well. The regularizer and constraint are usually convex; however, several particular features of these problems (huge dimensionality, non-smoothness) preclude the use of off-the-shelf optimization tools and have stimulated much research. In this paper, we propose a new efficient algorithm to handle one class of constrained problems (known as basis pursuit denoising) tailored to image recovery applications. The proposed algorithm, which belongs to the category of augmented Lagrangian methods, can be used to deal with a variety of imaging ILIP, including deconvolution and reconstruction from compressive observations (such as MRI). Experiments testify for the effectiveness of the proposed method.

Mario let me know that the code should be made available online, within a few weeks. Thanks Mario !

I also found the following on the interwebs:

Distributed Sensing of Signals under a Sparse Filtering Model, by Ali Hormati , Olivier Roy , Yue M. Lu and 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.

Dictionary learning and sparse coding for unsupervised clustering by Pablo Sprechmann and Guillermo Sapiro. The abstract reads:

A clustering framework within the sparse modeling and dictionary learning setting is introduced in this work. Instead of searching for the set of centroid that best fit the data, as in k-means type of approaches that model the data as distributions around discrete points, we optimize for a set of dictionaries, one for each cluster, for which the signals are best reconstructed in a sparse coding manner. Thereby, we are modeling the data as the of union of learned low dimensional subspaces, and data points associated to subspaces spanned by just a few atoms of the same learned dictionary are clustered together. Using learned dictionaries makes this method robust and well suited to handle large datasets. The proposed clustering algorithm uses a novel measurement for the quality of the sparse representation, inspired by the robustness of the l_1 regularization term in sparse coding. We first illustrate this measurement with examples on standard image and speech datasets in the supervised classification setting, showing with a simple approach its discriminative power and obtaining results comparable to the state-of-the-art. We then conclude with experiments for fully unsupervised clustering on extended standard datasets and texture images, obtaining excellent performance.

I also found some news from the Rice Compressive Sensing repository:

Asymptotic Analysis of MAP Estimation via the Replica Method and Applications to Compressed Sensing by Sundeep Rangan, Alyson K. Fletcher, Vivek K Goyal. The abstract reads:

The replica method is a non-rigorous but widely-accepted technique from statistical physics used in the asymptotic analysis of large, random, nonlinear problems. This paper applies the replica method to non-Gaussian maximum a posteriori (MAP) estimation. It is shown that with random linear measurements and Gaussian noise, the asymptotic behavior of the MAP estimate of an n-dimensional vector decouples as n scalar MAP estimators. The result is a counterpart to Guo and Verdu's replica analysis of minimum mean-squared error estimation.
The replica MAP analysis can be readily applied to many estimators used in compressed sensing, including basis pursuit, lasso, linear estimation with thresholding, and zero norm-regularized estimation. In the case of lasso estimation the scalar estimator reduces to a soft-thresholding operator, and for zero norm-regularized estimation it reduces to a hard threshold. Among other benefits, the replica method provides a computationally-tractable method for exactly computing various performance metrics including mean-squared error and sparsity pattern recovery probability.

and a software code: SLEP: A Sparse Learning Package

CS: Compressive Sensing for Spectroscopy and Polarimetry, Q&A with Andres Asensio Ramos, Some news from HERSCHEL/PACS

Andres Asensio Ramos from the Instituto de Astrofísica de Canarias mentioned to me his recent preprint entitled; Compressive Sensing for Spectroscopy and Polarimetry by Andres Asensio Ramos and Arturo Lopez Ariste. The abstract reads:

We demonstrate through numerical simulations with real data the feasibility of using compressive sensing techniques for the acquisition of spectro-polarimetric data. This allows us to combine the measurement and the compression process into one consistent framework. Signals are recovered thanks to a sparse reconstruction scheme from projections of the signal of interest onto appropriately chosen vectors, typically noise-like vectors. The compressibility properties of spectral lines are analyzed in detail. The results shown in this paper demonstrate that, thanks to the compressibility properties of spectral lines, it is feasible to reconstruct the signals using only a small fraction of the information that is measured nowadays. We investigate in depth the quality of the reconstruction as a function of the amount of data measured and the influence of noise. This change of paradigm also allows us to define new instrumental strategies and to propose modifications to existing instruments in order to take advantage of compressive sensing techniques.

After reading his paper we started an impromptu discussion that I am editing and copying with permission. I initially asked:

...While you are discussing CS techniques as applied to spectrographs and spectropolarimeters, I did not see a deep discussion on the reason as to why a CS hardware would provide an edge as opposed to a simple hardware. Can you enlighten me on this ? Are you and your co-author currently designing hardware or is it just an exercise in evaluating potential CS technologies ?...

Andres replied with:

...It is true that there is not a deep discussion on why CS techniques can be of interest because I think it is clear in our community that going fast when acquiring data is good. So, any improvement leading to faster instruments without compromising too much (or even not compromising at all) spectral and spatial resolution will be welcomed (once they understand the maths behind CS techniques). At least in solar physics, it is impossible to measure 2D images with spectro-polarimetric information in each pixel with a spectral resolution of, say, 20 mA per pixel, and a polarimetric sensitivity of 10^-5 (detect one polarized photon per 100000). Either long integration times have to be used (very poor temporal resolution) or reduce the polarimetric sensitivity (weak magnetic fields cannot be detected). In my opinion, CS can lead to an improvement in this field because the acquisition times can be reduced by a large factor, thus leading to a boost in time resolution.

The main concern I have encountered in our community (I'm referring to solar and stellar physics) is more philosophical than practical. I have given some talks introducing to my colleagues the ideas of CS and how novel instruments can be built under this framework and I always find the same response: "I don't believe it. Of course, if you put a prior on the signal you measure, you will never find 'surprises' " (surprises in the sense of strange signals that do not follow the main trend). That's the main reason why my colleague and myself decided to publish a paper presenting the potential of CS for spectroscopy and spectropolarimetry, showing that signals are compressible and that 'surprises' can be, in principle, found if you measure enough times and propose a sufficiently complete basis set.

Concerning the development of the ideas we propose, we are now working on a modification to an instrument existing in the french telescope THEMIS (http://www.themis.iac.es/). This instrument is a high-spectral-resolution spectro-imager (it measures 2D images of the solar surface with each column of the image at a slightly different wavelength) but using multiplexing techniques. Our plans include doing l1 reconstructions of the multiplexed measurements and our first numerical tests indicate a good behavior. I'm discussing with other colleagues on applying CS techniques to the Fabry-Perot interferometer of Solar Orbiter, but this is still in a very initial phase. With our paper I hope to convince our instrumental colleagues that it is worth pushing towards this new measuring paradigm....

Igor:

...With regards to THEMIS, you said "..This instrument is a high-spectral-resolution spectro-imager (it measures 2D images of the solar surface with each column of the image at a slightly different wavelength) but using multiplexing techniques...". Does that mean that it doesn't use multiplexing right now but that you will try multiplexing, now that you interested in CS, to see if there is a better way of acquiring signals that way ?...

Andres:

...At the moment, it is working in "single wavelength" mode, meaning that there is only one wavelength per column in the image. The wavelength information is recovered by scanning either moving a slit or moving a grating. Our idea is to multiplex many wavelengths in each column, so that, assuming sparsity, we can recover the signal with a reduced amount of scan steps as compared with the single wavelength mode....

Igor:

...Have you considered instrumentation that could provide superresolution ?...

Andres:

...Not in the CS framework. I have considered doing Bayesian superresolution taking advantage of the natural jittering of some telescopes (like the Sunrise balloon and some wind-exposed coelostats) or inducing this jittering mechanically. Unfortunately, I haven't had time to push this approach to an end and the analytical calculations are still in my notebooks and some working numerical codes in my laptop. Are you aware of applications of CS to superresolution?...

Igor:

With regards to superresolution yes: check the blog for work by Roummel Marcia an Rebecca Willett at Duke on performing superresolution with coded aperture and also the work of Justin Romberg ... you should find trace of his imagers on the blog and the CS hardware page.... I am interested in hearing about how you guys would try to perform the (cheap) multiplexing in hardware so that you provide much better resolution than the current cameras you currently have. I think it is an extremely hard sell to say that CS can provide faster acquisition at the cost of some accuracy when most people publish papers with accuracy in mind. Hence, CS has to go beyond providing the same data in order to become something that people want as opposed to something would like to have because it is the new fad :-)

Andres:

I have to disagree :) For us doing solar physics time resolution is crucial for detecting events happening at very short timescales. If these events happen in less than 1 second, we cannot spend 5 seconds integrating to gain signal-to-noise. Therefore, reducing a factor 5-10 the integration time while maintaining the spectral resolution and the polarimetric sensitivity at similar levels opens up the possibility of studying very fast events.....Obviously, it would be great to be able to go beyond the resolution imposed by the cameras, although our resolution is almost always limited by the atmospheric stability. Some present telescopes are equipped with adaptive optics systems so that diffraction limited images can be obtained in some moments of good atmospheric stability. Of course, I can imagine systems that could carry out superresolution during these moments of good stability, but they also need to be fast and accurate doing spectroscopy at a resolution of 10 mA per pixel and polarimetry better than 10^-4, something that I doubt can be done presently. If you tell me to choose between superresolution and accuracy, I clearly prefer to see things at a lower spatial resolution (limited by my telescope) but be able to follow fast events with great precision. That's my opinion and I'm sure if you ask other colleagues, you'll find a panoply of different opinions :)

Igor:

....Adaptive optics to me is like fighting nature not measuring with it....I have some views on this and this is why I recently mentioned this issue of imaging with nature...

Andres:

Yes, I've read the[se entries]. I have been thinking on the possibility of taking advantage of the atmosphere to improve the quality of our solar images, but I find it difficult mainly because we don't know the "atmospheric sensing matrix".

Igor:

Yes I absolutely agree but I think we need to be inventive on that front. Specifically:

• Right now some people are using turbulence to perform what they call Lucky imaging or Turbulence aided micro-lensing, can we used that phenomenon effect to our advantage especially in the context of time multiplexing ?
  
• Do we have the means of figuring out atmospheric turbulences using other instruments/cameras not used for that purpose (specifically cameras on-board current satellites)
• Since the Moon is a known object, can we probe the atmospheric turbulence by evaluating what the Moon should look like and what it looks like on the sensor of interest. What about doing that type of studies with inter star angles ?
  
• Should we use interrogative means such as laser beams as the ones used for computing the distance between the Moon and the earth.
• Others.....

Andres:

....Some colleagues at the IAC have imaged stellar systems using lucky imaging cameras. Although the concept is simple, I have always considered that it is a waste of photons and something smarter can be found....The atmosphere's PSF varies typically on the order of milliseconds. Perhaps it's possible to estimate how good the atmosphere behaves for reconstructions of sparse signals... More things to do for the future...

Igor:

Absolutely, [in particular with regards to Lucky imaging], I think it is a waste to let the unfocused part of the image go to waste. Connecting lucky imaging and the atmospheric PSF lead back to something called blind deconvolution, I mentioned something about it recently...

The discussion went on a little further. Thank you very much Andres for this thoughful and insightful discussion!

For information, the Planetary Society blog has a small description of the difference between an image taken by the Hubble and adaptive optics on the Keck Observatory. If you want to know more about the Hubble, you may want to go to Rice University tomorrow for a presentation on "Servicing the Hubble Space Telescope" by Michael Massimino, one of the astronauts who did the recent retrofitting of the Space Telescope. Finally, Jean-Luc Starck tells me that unlike HIFI, PACS (IAC site)works wonderfully, that it is in a calibration mode and that the CS mode should be tried in October. Woohoo, thanks Jean-Luc !


Finally, as an aside, I am glad that I am now on Andres' e-mail list because if the La Palma Volcano slides into the ocean and triggers a mega-tsunami, I am sure he'll send an e-mail to all his E-mail contacts warning them about not being anywhere near a coast in Africa, Europe, the U.S., the Carribean or South America.

CS: A Compressive Sensing Newsletter ?

I was watching the stats of the blog recently and here is what I found:

One would think that starting 2009, interest stabilized except for the localized interest due to the SPARS'09 meeting and the Duke Workshop. Appearances are deceiving though as the readership of the blog turned to using the blog's feed. Here are the stats from feedburner (one third of the full RSS readership):


The 200 mark on the left hand side refers to the number of readers per day. Since I generally post during the week, this translate into 200 x 22 = 4400 hits per month for Feedreader or about 10,000 hits per months from the feed readers. This is on top of the stats shown above of 10,000 hits per months. In all about 20,000 hits per month (or a potential 20,000/22 = 900 readers/post). This number does not include the 214 people receiving every posts by e-mail.

In all, while the hits on the blog are probably newcomers (half of the traffic comes from search engine), I am more concerned about the generic number of committed readers (feed or e-mail): This number is currently at 764 and I will refer to this one number from now on instead of hits/months which in the end does not mean much.

After more than 500 posts on the subject, I am concerned that there is an information overload (see the result of the poll in the I-can't-keep-up post) and I am wondering if, strike that, I am certain that there is an interest for a monthly or bi-monthly (?) newsletter. It would be a subscription based newsletter (you'd have to pay to get it) and here is the pitch: there would be absolutely nothing new in that newsletter. However, it would NOT be a newsletter about nothing a la Seinfeld :-)



Rather the newsletter would provide some sort of version control and some context about the current investigations/ideas happening in the field. Nothing in the newsletter would be new in the sense that the blog, the attendant pages (CS big picture, CS Jobs, CS Online Talks/Videos, CS Hardware) would function in exactly the same manner and remain open to everybody. The newsletter would provide some sorts of summary to the folks who, for different reasons, cannot keep up with the daily flow of information in the field. Do you think there is an interest ? Please come to the site and let me know by answering the following poll (see below).

Thanks!

CS: ISD, A New Compressed Sensing Algorithm via Iterative Support Detection (and NSP vs RIP)

Some of you may recall my description of the DUMBEST algorithm. Well, it looks like Yilun Wang and Wotao Yin had a more powerful idea along similar lines of thoughts four months earlier and implemented it. Woohoo! This is likely to be going to be an important line of work in Compressive Sensing as it focuses on the idea that once some data has been gathered and your reconstruction algorithm fails there is still hope to recover something. Wotao Yin mentioned to me that they released ISD, A New Compressed Sensing Algorithm via Iterative Support Detection. From the website introduction:

ISD is as fast as L1-minimization but requires fewer measurements. ISD addresses wrong solutions of L1 construction due to insufficient measurements. It will learn from such wrong solutions and solve new minimization problems that return a perfect or a better solution. A demo is given on Pages 4 and 5 of our report.

You can download an efficient implementation of ISD, called threshold-ISD, for recovering signals with fast decaying distributions of nonzeros from compressive measurements. The package includes numerical experiments showing that ISD has significant overall advantages over the classical L1 minimization approach, as well as two other state-of-the-art algorithms: the iterative reweighted L1 minimization algorithm (IRL1) and the iterative reweighted least--squares algorithm (IRLS).

The technical report is Compressed Sensing via Iterative Support Detection by Yilun Wang and Wotao Yin. The astract reads:

We present a new compressive sensing reconstruction method "ISD", aiming to achieve fast reconstruction and a reduced requirement on the number of measurements compared to the classical l_1 minimization approach. ISD addresses failed cases of l_1 based construction due to insufficient measurements, in which the returned signals are not equal or even close to the true signals. ISD will learn from such signals and solve new minimization problems that return a perfect or a better signal. Specifically, given an incorrect signal, ISD detects an index set I that includes components most likely to be true nonzeros and solves minf P i62I jxij : Ax = bg for a new signal x, and it iterates these two steps alternatively using latest x and I from one another until convergence. ISD differs from the orthogonal matching pursuit (OMP) method, as well as its variants, in two aspects. First, although both methods generate index sets iteratively, the index set I in ISD is not necessarily nested or increasing over the iterations. Second, the OMP family methods at each of their iterations x xi, i 2 I, and update the remaining components of x, but the ISD minimization problem above updates all the components of x. To analyze the performance of ISD, we generalize the Null Space Property to Truncated Null Space Property and present our analysis on the latter. We introduce an efficient implementation of ISD, called threshold-ISD, for recovering signals with fast decaying distributions of nonzeros from compressive measurements. Numerical experiments show that threshold-ISD has signicant overall advantages over the classical l_1 minimization approach, as well as two other state-of-the-art algorithms such as the iterative reweighted l_1 minimization algorithm (IRL1) and the iterative reweighted least-squares algorithm (IRLS). MATLAB code is available for download from http://www.caam.rice.edu/~optimization/L1/ISD/.

From the paper:

ISD enhances sparse and compressible signal reconstruction by learning from failed BP-based reconstructions that arise when the number of linear measurements is not sufficient. In a failed reconstruction, the solution of BP is not equal or even close to the true signal x. One would normally give up, but ISD learns from the incorrect signal and solves a new optimization problem that returns a perfect or a better solution, requiring no additional measurements.

This is great. As a sub-issue, I also noticed the somewhat detailed discussion about NSP and RIP based sufficient conditions for recovery:

....We start with introducing the truncated null space property (t-NSP), a generalization of the null space property (NSP) studied in [35, 36, 17, 11, 13]. The NSP is used in slightly different forms and difference names in these papers....

and

...With \gamma \lt 1, the NSP says that any nonzero vector \eta in the null space of A cannot have an l_1-mass concentrated on any set of L or fewer elements. [12] proposes a semidedefinite relaxation to test the NSP for general matrices. A sufficient exact reconstruction condition for BP is given in [13] based on the NSP: the true k-sparse signal x^bar is the unique solution of BP if A has the NSP of order L \ge k and 0 \llt \gamma \lt 1. The more widely known restricted isometry property (RIP) is more restricted than the NSP for establishing recoverability and stability results for BP [8, 7]. .... The NSP is more relaxed than the RIP. ....

Ah! I recoiled from this statement since it looks to me that an opposite statement was made earlier (see my comment in this entry). I fired up an e-mail out to Wotao stating the following:

In your paper you mentioned that the NSP is more relaxed than the RIP-based sufficient property. Does this mean that there are cases where either:

1. The NSP-based sufficient property can be fulfilled while at the same time the RIP-base sufficient property is not fulfilled OR
2. The RIP-based sufficient property can be fulfilled while at the same time the NSP-base sufficient property is not fulfilled.

To what Wotao kindly responded with:

*1. The NSP-based sufficient property can be fulfilled while at the same time the
* RIP-base sufficient property is not fulfilled

This holds!

Suppose that A has both NSP and RIP (with certain parameters). Let B = PA where P is a non-singular matrix. Then, B has the same NSP but it is not clear whether it has RIP or not.

Thanks Wotao !

CS: CS related ICML'09 videos, Distributed Spatio-Temporal Sampling of Diffusion Fields from Sparse Instantaneous Sources, Smart-Sample

The ICML'09 videos are out . Out of the ones relevant to some aspect of compressive sensing here is a sample:

• Online Dictionary Learning for Sparse Coding by Julien Mairal
• Gradient Descent with Sparsification: An Iterative Algorithm for Sparse Recovery with Restricted Isometry Property by Rahul Garg
• Convex Variational Bayesian Inference for Large Scale Generalized Linear Models by Hannes Nickisch
• An Efficient Sparse Metric Learning in High-Dimensional Space via L1-Penalized Log-Determinant Regularization by Guo-Jun Qi
• Convex Sparse Methods for Feature Hierarchies by Francis R. Bach
• Unsupervised Discovery of Structure, Succinct Representations and Sparsity by Andrew Y. Ng
• Reinforcement Learning, Apprenticeship Learning and Robotic Control by Andrew Y. Ng

I am sure I am missing some. If so please do let me know. In the meantime, I'll add them to the Compressive Sensing Videos/Online Talks page. I also found two papers of interest:Distributed Spatio-Temporal Sampling of Diffusion Fields from Sparse Instantaneous Sources by Yue M. Lu and Martin Vetterli. The abstract reads:

We study the spatio-temporal sampling of a diffusion field driven by K unknown instantaneous source distributions. Exploiting the spatio-temporal correlation offered by the diffusion model, we show that it is possible to compensate for insufficient spatial sampling densities (i.e. sub-Nyquist sampling) by increasing the temporal sampling rate, as long as their product remains roughly a constant. Combining a distributed sparse sampling scheme and an adaptive feedback mechanism, the proposed sampling algorithm can accurately and efficiently estimate the unknown sources and reconstruct the field. The total number of samples to be transmitted through the network is roughly equal to the number of degrees of freedom of the field, plus some additional costs for in-network averaging.

and Smart-Sample: An Ecient Algorithm for Clustering Large High-Dimensional Datasets by Dudu Lazarov, Gil David, Amir Averbuch. The abstract reads:

Finding useful related patterns in a dataset is an important task in many interesting applications. In particular, one common need in many algorithms, is the ability to separate a given dataset into a small number of clusters. Each cluster represents a subset of data-points from the dataset, which are considered similar. In some cases, it is also necessary to distinguish data points that are not part of a pattern from the other data-points. This paper introduces a new data clustering method named smart-sample and compares its performance to several clustering methodologies. We show that smart-sample clusters successfully large high-dimensional datasets. In addition, smart-sample out-performs other methodologies in terms of running-time.

A variation of the smart-sample algorithm, which guarantees eciency in terms of I/O, is also presented. We describe how to achieve an approximation of the in-memory smart-sample algorithm using a constant number of scans with a single sort operation on the disk.

CS: Adaptive feature-specific imaging for recognition of non-Gaussian classes.

Pawan Baheti now at Qualcomm jusst mentioned to me his latest paper on the Feature specific imager we covered before (see the compressive sensing hardware 1.1.3 item). The paper is behind a paywall but you can ask Pawan directly for a preprint. Here it is:

Adaptive feature-specific imaging for recognition of non-Gaussian classes by Pawan K. Baheti, Jun Ke, and Mark A. Neifeld. The abstract reads:

We present an adaptive feature-specific imaging (AFSI) system for application to an M-class recognition task. The proposed system uses nearest-neighbor-based density estimation to compute the (non-Gaussian) class-conditional densities. We refine the density estimates based on the training data and the knowledge from previous measurements at each step. The projection basis for the AFSI system is also adapted based on the previous measurements at each step. The decision-making process is based on sequential hypothesis testing. We quantify the number of measurements required to achieve a specified probability of error (Pe) and we compare the AFSI system with an adaptive-conventional (ACONV) system. The AFSI system exhibits significant improvement compared to the ACONV system at low signal-to-noise ratio (SNR), and it is shown that, for an M=4 hypotheses, SNR=−10 dB, and a desired Pe=10−2, the AFSI system requires 30 times fewer measurements than the ACONV system. Experimental results validating the AFSI system are presented.

They use an SLM to provide differet random measurements and use their ability to change the SLM to devise an adaptive strategy. Nice. Thanks Pawan!