CS: A Q&A with Felix Herrmann, SMALLbox

I took the opportunity of Felix Herrmann sending me the job opportunities for graduate studentship and postdocs to ask a question destined for people on the applied side of things:.

Felix,

The question applies specifically to the applied folks. In most systems that are being solved, we somehow hope that the RIP or some such property holds for our system so we can get on the solving of actual problems. It's all great and fun to pretend that but in the end nobody is really convince of the matter.

So here are my questions: In order to be more convincing, have you tried to show that your systems followed the Donoho-Tanner phase transition ? in the negative, is it because of time constraints or something else ?

Felix kindly responded with:

Hi Igor,

....

I have always been a fan of the phase diagram by Donoho/Tanner because they capture the recovery conditions for typical sparse vectors and acquisition matrices. This means they are less pessimistic and they reflect practical situations better.

However, in my field we are confronted with problem sizes that make it impossible to compute complete phase diagrams. In addition, we are typically relying on redundant sparsifying transformations for which the theory is relatively under developed.

Having said this, I looked in a recent paper at the "oversampling ratio" between the percentage of coefficients required to get a particular nonlinear approximation error and the degree subsampling required to get the same error. I borrowed this idea from Mallat's book and adapted it to the seismic problem. In principle, this sort of thing is somewhat similar to phase diagrams and it gives some assurances but I am afraid maybe not the type of assurances acquisition practitioners are looking for.

While useful, the method I presented in the paper is expensive to compute and does not really lead to a workflow that would provide practical principles to design acquisition scenarios based on compressive sampling. For instance, I am not aware of practical (read computationally feasible and doable in the field) ways to do QC etc. So in summary, while CS provides beautiful insights I think we still have a long way to go to bring this technology into the main stream.

Thanks Felix !
 
The paper is: Randomized sampling and sparsity: getting more information from fewer samples by Felix Herrmann. The abstract reads:

Many seismic exploration techniques rely on the collection of massive data volumes that are subsequently mined for information during processing. While this approach has been extremely successful in the past, current efforts toward higher resolution images in increasingly complicated regions of the Earth continue to reveal fundamental shortcomings in our workflows. Chiefly amongst these is the so-called “curse of dimensionality” exemplified by Nyquist’s sampling criterion, which disproportionately strains current acquisition and processing systems as the size and desired resolution of our survey areas continues to increase. In this paper, we offer an alternative sampling method leveraging recent insights from compressive sensing towards seismic acquisition and processing for data that are traditionally considered to be undersampled. The main outcome of this approach is a new technology where acquisition and processing related costs are no longer determined by overly stringent sampling criteria, such as Nyquist. At the heart of our approach lies randomized incoherent sampling that breaks subsampling related interferences by turning them into harmless noise, which we subsequently remove by promoting transform-domain sparsity. Now, costs no longer grow significantly with resolution and dimensionality of the survey area, but instead depend on transform-domain sparsity only. Our contribution is twofold. First, we demonstrate by means of carefully designed numerical experiments that compressive sensing can successfully be adapted to seismic exploration. Second, we show that accurate recovery can be accomplished for compressively sampled data volumes sizes that exceed the size of conventional transform-domain data volumes by only a small factor. Because compressive sensing combines transformation and encoding by a single linear encoding step, this technology is directly applicable to acquisition and to dimensionality reduction during processing. In either case, sampling, storage, and processing costs scale with transform-domain sparsity. We illustrate this principle by means of number of case studies.

On a different note, the SMALLbox toolbox was announced at the LVA conference. From the twitter feed:

SMALLbox provides a common API for various sparsity toolboxes like sparco, sparselab, etc.

From the website:

Sparse Models, Algorithms, and Learning for

Large-scale data (SMALL)

SMALL will develop a new foundational framework for processing signals, using adaptive sparse structured representations.
A key discriminating feature of sparse representations, which opened up the horizons to new ways of thinking in signal processing including compressed sensing, has been the focus on developing reliable algorithms with provable performance and bounded complexity.

Yet, such approaches are simply inapplicable in many scenarios for which no suitable sparse model is known. Moreover, the success of sparse models heavily depends on the choice of a "dictionary" to reflect the natural structures of a class of data, but choosing a dictionary is currently something of an "art", using expert knowledge rather than automatically applicable principles. Inferring a dictionary from training data is key to the extension of sparse models for new exotic types of data.

SMALL will explore new generations of provably good methods to obtain inherently data-driven sparse models, able to cope with large-scale and complicated data much beyond state-of-the-art sparse signal modelling. The project will develop a radically new foundational theoretical framework for the dictionary-learning problem, and scalable algorithms for the training of structured dictionaries. SMALL algorithms will be evaluated against state-of-the art alternatives and we will demonstrate our approach on a range of showcase applications. We will organise two open workshops to disseminate our results and get feedback from the research community.

The framework will deeply impact the research landscape since the new models, approaches and algorithms will be generically applicable to a wide variety of signal processing problems, including acquisition, enhancement, manipulation, interpretation and coding. This new line of attack will lead to many new theoretical and practical challenges, with a potential to reshape both the signal processing research community and the burgeoning compressed sensing industry.

Credit: SpaceX, Test firing of a Merlin 1C regeneratively cooled rocket engine on a single engine vertical test stand at the SpaceX test facility in McGregor, Texas. The next Falcon flight will occur no earlier than November 8th.

CS: Hackaday and La Recherche

My submission to Hackaday on the EPFL ECG system caught on only because of the iPhone aspect of it.  It would not be so bad if somehow this explanation had not been inserted in the summary:

....Oh, and why the iPhone? The device that displays the data makes little difference. In this case they’re transmitting via Bluetooth for a real-time display (seen in the video after the break). This could be used for a wide variety of devices, or monitored remotely via the Internet....

Not only that, but since the explanation about compressed sensing was somehow removed from the description of the hardware, many commenters seem to think that the prototype was built only to appeal to the latest shiny new iPhone story. As Pierre confirmed last night on Twitter, the iPhone performs a full l_1 minimization with wavelet frames in real time! wow ! As far as I could understand from the presentaiton, the encoding is following that of Piotr and Radu). The comments in the Hackaday entry are generally very instructive on how to communicate with a technical crowd that has not been exposed to compressive sensing before..The trolls are part of that game. 

For our french readers, the October edition of La Recherche has a piece on Compressive Sensing on page 20-21 entitled "Des signaux comprimés à l'enregistrement" with an interview of Emmanuel. The MRI photo is from Pierre's lab. The article points to the Big Picture as a reference document, woohoo! 

CS: LVA 2010 on Twitter, More ECG, CS on Manifolds, Bayesian PCA, Job Postings at SLIM

Prasad Sudhakar just sent me the following:

Dear Igor,

I am writing to inform you that the 9th international conference on latent variable analysis and signal separation is kicking off today at St. Malo, France.

Here is the conference website: http://lva2010.inria.fr/

There are two sessions on sparsity: Wednesday morning and afternoon.

Also, I will try to tweet the highlights of the proceedings (mostly the sparsity sessions and plenary talks) at http://twitter.com/lva2010

Could you please mention this on your blog?

Best regards,
Prasad Sudhakar

Thanks Prasad, I am now following @LVA2010 on the the Twitter. @LVA2010 is also, now, on the compressed-sensing list on Twitter as well (let me know if you want to be added to it).

Following up on the The EPFL Real-Time Compressed Sensing-Based Personal Electrocardiogram Monitoring System here is: Implementation of Compressed Sensing in Telecardiology Sensor Networks by Eduardo Correia Pinheiro , Octavian Adrian Postolache, and Pedro Silva Girão. The abstract reads:

Mobile solutions for patient cardiac monitoring are viewed with growing interest, and improvements on current implementations are frequently reported, with wireless, and in particular, wearable devices promising to achieve ubiquity. However, due to unavoidable power consumption limitations, the amount of data acquired, processed, and transmitted needs to be diminished, which is counterproductive, regarding the quality of the information produced.
Compressed sensing implementation in wireless sensor networks (WSNs) promises to bring gains not only in power savings to the devices, but also with minor impact in signal quality. Several cardiac signals have a sparse representation in some wavelet transformations. The compressed sensing paradigm states that signals can be recovered from a few projections into another basis, incoherent with the first. This paper evaluates the compressed sensing paradigm impact in a cardiac monitoring WSN, discussing the implications in data reliability, energy management, and the improvements accomplished by in-network processing.

Compressive Sensing on Manifolds Using a Nonparametric Mixture of Factor Analyzers: Algorithm and Performance Bounds by Minhua Chen, Jorge Silva, John Paisley Chunping Wang, David Dunson, and Lawrence Carin. The abstract reads:

Nonparametric Bayesian methods are employed to constitute a mixture of low-rank Gaussians, for data x 2 RN that are of high dimension N but are constrained to reside in a low-dimensional subregion of RN. The number of mixture components and their rank are inferred automatically from the data. The resulting algorithm can be used for learning manifolds and for reconstructing signals from manifolds, based on compressive sensing (CS) projection measurements. The statistical CS inversion is performed analytically. We derive the required number of CS random measurements needed for successful reconstruction, based on easily computed quantities, drawing on block–sparsity properties. The proposed methodology is validated on several synthetic and real datasets.

Bayesian Robust Principal Component Analysis by Xinghao Ding, Lihan He, and Lawrence Carin. The abstract reads:

A hierarchical Bayesian model is considered for decomposing a matrix into low-rank and sparse
components, assuming the observed matrix is a superposition of the two. The matrix is assumed
noisy, with unknown and possibly non-stationary noise statistics. The Bayesian framework infers an approximate representation for the noise statistics while simultaneously inferring the low-rank and sparse-outlier contributions; the model is robust to a broad range of noise levels, without having to change model hyperparameter settings. In addition, the Bayesian framework allows exploitation of additional structure in the matrix. For example, in video applications each row (or column) corresponds to a video frame, and we introduce a Markov dependency between consecutive rows in the matrix (corresponding to consecutive frames in the video). The properties of this Markov process are also inferred based on the observed matrix, while simultaneously denoising and recovering the low-rank and sparse components. We compare the Bayesian model to a state-of-the-art optimization-based implementation of robust PCA; considering several examples, we demonstrate competitive performance of the proposed model.

The code implementing this Bayesian PCA is here.

I usually don't post about graduate studentships but the sheer size of this announcement makes it worthwhile for a post. Felix Herrmann just sent me this announcement for three postdocs and ten graduate studentships at UBC. The jobs are posted in the compressive sensing jobs page. They are also listed below:

• September 27th, 2010, Three postdoctoral positions at the Seismic Laboratory for Imaging and Modeling (SLIM) of the University of British Columbia, Vancouver, BC, Canada
  
  
  
  
  
  Project:
  DNOISE is a 5-year NSERC and industry-funded project for research in seismic data acquisition, processing, and imaging. Our interdisciplinary approach builds on recent developments in compressive sensing, large-scale optimization, and full-waveform inversion from severely sub-sampled data. The project includes 10 graduate students, 3 postdocs, and a research associate. The postdoctoral positions, under supervision Felix J. Herrmann (Earth and Ocean Sciences), Ozgur Yilmaz (Mathematics), and Michael P. Friedlander (Computer Science), are available immediately. 
  
  
  Description:
  The aim of the DNOISE project is to design the next generation of seismic imaging technology to address fundamental issues related to the quality and cost of seismic data acquisition, the ability to invert exceedingly large data volumes, and the capacity to mitigate non-uniqueness of full-waveform inversion.
  
  
  You will be part of a dynamic interdisciplinary research group and will present your research at international conferences and to industry. You will also be involved in industry collaborations that include internships and projects on real field data. You will have extensive contact with graduate students, fellow postdocs, and faculty. We seek excellence in any of a wide variety of areas, spanning from theory, algorithm design, to concrete software implementations to be applied to field data. SLIM has state-of-the-art resources, including a 288 CPU cluster, Parallel Matlab, and seismic data-processing software.
  
  
  Successful candidates will have a PhD degree obtained in 2008 or later in geophysics, mathematics, computer science, electrical engineering, or a related field, with a strong achievement record in at least one of the following areas: seismic imaging, inverse problems, PDE-constrained optimization, signal processing, sparse approximation and compressed sensing, convex optimization, and stochastic optimization. Earlier PhDs will be considered where the research career has been interrupted by circumstances such as parental responsibilities or illness. UBC hires on the basis of merit, and is committed to employment equity. Positions are open to individuals of any nationality.
  
  
  Compressive seismic-data acquisition. Development of practical seismic acquisition scenarios, sigma-delta quantization, and experimental design for seismic inversion.
  Full-waveform inversion. Development of PDE-constrained optimization algorithms that deal with large data volumes and that remedy the non-uniqueness problem.
  Large-scale optimization. Development of optimization algorithms and software for sparse approximation and problems with PDE-constraints.
  
  
  About UBC and Vancouver:
  The University of British Columbia, established in 1908, educates a student population of 50,000 and holds an international reputation for excellence in advanced research and learning. Our campus is 30 minutes from the heart of downtown Vancouver, a spectacular campus that is a 'must-see' for any visitor to the city -- where snow-capped mountains meet ocean, and breathtaking vistas greet you around every corner. 
  
  
  How to apply: Applicants should submit a CV, a list of all publications, and a statement of research, and arrange for three or more letters of recommendation to be sent to Manjit Dosanjh (MDOSANJH@eos.ubc.ca). All qualified candidates are encouraged to apply; however, Canadians and Permanent Residents will be given priority. For more information, see: http://slim.eos.ubc.ca
• September 27th, 2010, Ten graduate students at the Seismic Laboratory for Imaging and Modeling (SLIM) of the University of British Columbia
  
  
  
  
  
  Project:
  DNOISE is a 5-year NSERC and industry-funded project for research in seismic data acquisition, processing, and imaging. Our interdisciplinary approach builds on recent developments in compressive sensing, large-scale optimization, and full-waveform inversion from severely sub-sampled data. The project includes 10 graduate students, 3 postdocs, and a research associate. Subject to admission by the faculty of graduate studies, prospective students can start as early January 1st, 2011 under supervision of Felix J. Herrmann (Earth and Ocean Sciences), Ozgur Yilmaz (Mathematics), or Michael P. Friedlander (Computer Science).
  
  
  Description:
  
  
  The aim of the DNOISE project is to design the next generation of seismic imaging technology to address fundamental issues related to the quality and cost of seismic data acquisition, the ability to invert exceedingly large data volumes, and the capacity to mitigate non-uniqueness of full-waveform inversion.
  
  
  You will be part of a dynamic interdisciplinary research group and will present your research at international conferences and to industry. You will also be involved in industry collaborations that include internships and projects on real field data. 
  You will have extensive contact with fellow graduate students, postdocs, and faculty. We seek excellence in any of a wide variety of areas, spanning theoretical, algorithmic, and software development. A good background in mathematics is important.
  
  
  The graduate funding is for two years for MSc students and four years for PhD students and includes generous funding for travel. PhD student funding includes a tuition waiver. 
  
  
  Successful candidates will join the PhD or MSc programs in one of the following departments at UBC: Earth and Ocean Sciences, Mathematics, or Computer Science. At SLIM you will have state-of-the art resources available, including a 288 CPU cluster, Parallel Matlab, and seismic data-processing software. 
  
  
  About UBC and Vancouver:
  The University of British Columbia, established in 1908, educates a student population of 50,000 and holds an international reputation for excellence in advanced research and learning. Our campus is 30 minutes from the heart of downtown Vancouver, a spectacular campus that is a 'must-see' for any visitor to the city -- where snow-capped mountains meet ocean, and breathtaking vistas greet you around every corner. 
  
  
  How to apply: Please send a CV, cover letter, and  academic transcripts to Manjit Dosanjh (MDOSANJH@eos.ubc.ca). For more information, see: http://slim.eos.ubc.ca

Liked this entry ? subscribe to the Nuit Blanche feed, there's more where that came from

CS: The EPFL Real-Time Compressed Sensing-Based Personal Electrocardiogram Monitoring System

I previously mentioned the presentation of  Pierre Vandergheynst on the EPFL Compressive Sensing ECG system (check also the Q&A on the matter).. Pierre sent me more in the form of a webpage featuring the project A Real-Time Compressed Sensing-Based Personal Electrocardiogram Monitoring System by Hossein Mamaghanian, Karim Kanoun, and  Nadia Khaled 

From the website:

OUR APPROACH

Capitalizing on the sparsity of ECG signals, we propose to apply the emerging compressed sensing (CS) approach for a low-complexity, real-time and energy-aware ECG signal compression on WBSN motes. This is motivated by the observation that this new signal acquisition/compression paradigm is particularly well suited for low-power implementations because it dramatically reduces the need for resource- (both processing and storage) intensive DSP operations on the encoder side. The price to pay for these advantages however, is a more complex decoder. In general, reconstruction algorithms for CS recovery are computationally expensive, because they involve large and dense matrix operation, which prevents their real-time implementation on embedded platforms.

This project has developed a real time, energy-aware wireless ECG monitoring system. The main contributions of this work are: (1) a novel CS approach that precludes large and dense matrix operations both at compression and recovery, and (2) several platform-dependent optimizations and parallelization techniques to achieve real-time CS recovery. To the best of our knowledge, this work is the first to demonstrate CS as an advantageous real-time and energyefficient ECG compression technique, with a computationally light and energy-efficient ECG encoder on the state-of-the-art ShimmerTM wearable sensor node and a real-time decoder running on an iPhone as a representative of compact embedded (CE) device (acting as a WBSN coordinator).

OnlineVersionOfCSMonitoring.pdf

This information has been added to the Compressive Sensing Hardware page.

Orphan Technologies redux ...

Alejandro pointed out to me the recent book from David McKay on sustainable energy. I haven't read the whole book but all the things he says on sustainability and Nuclear power are right on. Since David is not an insider, read work/has worked/worked for a nuclear utility or government entity dedicated to the use of nuclear materials, I'd say he is a pretty good source to rely on. What's disconcerting is that nobody in our political landscape can relate to enabling a power source beyond a five year schedule. The book is here. It is also available from the Amazon - Nuit Blanche Bookstore (Kindle version). Maybe David's new position as Chief Scientific Advisor to the Department of Energy and Climate Change will change some of that (at least in the U.K.)

Compressed Sensing Business Edition

From the ever great PetaPixel blog, here is the first Plenoptic cameras on the market. from Raytrix. This was unearthed from Photorumors which featured a presentation by Adobe on using GPU to reconstruct images from Plenoptic cameras:

David Salesin and Todor Georgiev are the presenters. Looking at Todor's page, I noticed among many interesting tidbits:

Adobe Tech Report, April 2007 Lightfield Capture by Frequency Multiplexing. Careful theoretical derivation of what MERL authors call "Dappled Photography" and "Heterodyning". Proving that frequency multiplexing works for both mask-based and microlens-based cameras. This is a new result. It shows that the approach is truly universal: It's not a special "heterodyning" type of camera, but a "heterodyning" method of processing the data, applicable to any camera! Also, proposing a new "mosquito net" camera. And much more (wave artifact removal, F/number analysis). Examples.

Of related interest is this page: 100 Years Light-Field featuring the work of Lippman ( I did not know the connection between Marie Curie and Gabriel Lippman ). Sure this is about computational photography an area which include compressive sensing and shows that at least some hardware is considering having a two-step process. The GPU aspect is something that we are all convinced about since our solvers  probably need this type of computational power. The main aspect for compressive sensing is whether it can bring another dimension to the data being reconstructed. In other words, could a plenoptic camera be hacked into doing something entirely new ?  In other news, David Brady let us know that Hasselblad is releasing a 200 MP camera. Also,  T-Ray Science, Inc. Files US Non Provisional Patent. From MarketWire:

VANCOUVER, BRITISH COLUMBIA--(Marketwire - Sept. 21, 2010) - T-Ray Science, Inc. (TSX VENTURE:THZ) announces it has filed a non provisional patent with the U.S. Patent and Trade Mark Office on a Unified Sensing Matrix for a Single Pixel Detector Based on Compressive Sensing (USPTO Serial No. 61/243,559).

T-Ray's Patent covers a particular process of acquiring a 2D image that allows for higher quality and faster scanning from a Terahertz beam. The Company is anticipating using the patented process in the development of its portable Skin Cancer Imager.

"T-Ray recognizes the importance of strengthening our patent portfolio," says T-Ray President and CEO Thomas Braun. "The signal process covered by this patent complements our existing intellectual property recently licensed from the BC Cancer Agency."

I don't have much time today as I have to fill my invention disclosure forms...

If you think this blog provides a service, please support it by ordering through the Amazon - Nuit Blanche Reference Store

Orphan Technologies ...

There is an entry in this blog that keeps on getting some attention, it features two technologies that, because they are complex, have become orphan (at least in the U.S.), some would called them rudderless at the policy level:

• Nuclear Energy: As usual, MIT is, once again, used as a cover for a backward and hurtful policy.
• Space: The last Shuttle to ever fly will take off No Earlier than November 1, 2010.

While reading the interview of James Bagian I was reminded that both of these technologies use Probabilistic Rsik Assessments (PRA), maybe it's a sign that when you begin to use Monte Carlo techniques, you are doomed.  Both sets of technologies are in that state because most political stakeholders have no interest in developing them. Take for instance the case of reprocessing nuclear materials after they have gone through one core use: the Left which has, for years, built its political credentials on fighting earlier projects , cannot but be extremely negative about any development on some ideological level while the Right cannot think of a market where building one plant results in putting billions of dollars in some government escrow account for years during the plant construction while the stock market has 2 to 15% returns. On a longer time scale, reprocessing is the only way we can buy some time but the political landscape does not allow for this type of vision. It just buggles the mind that we ask people to waste energy in creating and recycling glass [see note in the comment section] but throw away perfectly usable plutonium. On the other end of the spectrum timewise, maybe we should not care so much about nonproliferation as much as dealing with ETFs. Maybe a way to make ETFs less a problem is getting people to use Monte Carlo techniques there.. oh wait they do, we're screwed. But the interview also pointed out to issues in health care where even getting people to follow a check list is a matter that seems to involve lawyers. As it turns out John Langford just had a posting on Regretting the dead about making tiny changes in our way of thinking to map better the expectations in the Health care sector. It would seem to me that we ought to have similar undertaking from the Theoretical Computer Science community as well. For instance, the Stable Marriage Problem could be extended a little further so that we could eventually get to know why certain traits, conditions or diseases stay endemic at a low level in the population. I certainly don't hold my breath on having algorithms changing some landscape as exemplified by the inability for industry to include ART or better algorithms in current CT technology even with the stick of  the radiation burden [1]. In a somewhat different direction,  Jason Moore has a post on Machine Learning Prediction of Cancer Susceptibility. From his grant renewal, I note:

This complex genetic architecture has important implications for the use of genome-wide association studies for identifying susceptibility genes. The assumption of a simple architecture supports a strategy of testing each single-nucleotide polymorphism (SNP) individually using traditional univariate statistics followed by a correction for multiple tests. However, a complex genetic architecture that is characteristic of most types of cancer requires analytical methods that specifically model combinations of SNPs and environmental exposures. While new and novel methods are available for modeling interactions, exhaustive testing of all combinations of SNPs is not feasible on a genome-wide scale because the number of comparisons is effectively infinite.

I am sure that some of you already see the connection between this problem and some of the literature featured here. As Seth Godin stated recently:

You can add value in two ways:

* You can know the answers.
* You can offer the questions.

Relentlessly asking the right questions is a long term career, mostly because no one ever knows the right answer on a regular basis.

I certainly don't know the answers but if you think this blog offers the right questions please support it by ordering through the Amazon - Nuit Blanche Reference Store

Reference:

[1] Xiaochuan Pan, Emil Sidky and Michael Vannier , Why do commercial CT scanners still employ traditional, filtered back-projection for image reconstruction?.

Credit: NASA

CS: Around the blogs in 80 hours, Sudocodes, HPT code, Volumetric OCT and more...

Here are some of the blog entries that caught my eyes recently:

• Andrew SODA Accepts
• Bob: Comparing Audio Signals in a Sparse Domain, A Successful HAID 2010!
  
• Gonzalo: Spectral Sensing at CIP 2010
• Terry: A second draft of a non-technical article on universality, 245A, prologue: The problem of measure
• Frank: Earth mover distance,
• Sarah: Johnson-Lindenstrauss and RIP
• Mademoiselle CyberGi: Compressed sensing e representação esparsa

Dror Baron , now at NC State, has new  talk on sudocodes - a fast compressed sensing reconstruction approach that uses a hybrid dense/sparse measurement matrix and two corresponding algorithms (joint work with I. Poltorak and Deanna Needell)

Simon Foucart, now at Drexel, released the Hard Thresholding Pursuit (HPT) code that was described back in August in Hard thresholding pursuit: an algorithm for Compressive Sensing. The code is here. I have added it to the reconstruction solver section of the Big Picture.

On the LinkedIn group, Marc asked the following question:

Dear all,

I've started my Master Thesis and it's about CS for Electron Microscopy Data. We have the common problem of the "missing cone", the specimen which we want to capture the 3D-model makes a shadow when we turn it. This shadow in the Fourier Domain is a cone, and the data is not useful. In pixel domain we obtain an elongated image, so none of the two representations is sparse.

So the question is: do you think that it's possible to find any basis where the data is Sparse??? Or can we modified the data to obtain a Sparse Signal, apply CS and then revert the modifications??? Or can we force to obtain a sparse signal in the EM???

Any suggestion will be welcome.

Thank you everybody.

Now let us see the publication and preprints that just showed up on my radar screen:

Rapid Volumetric OCT Image Acquisition Using Compressive Sampling (abstract is here) by Evgeniy Lebed, Paul J. Mackenzie, Marinko V. Sarunic, and Faisal M. Beg. The abstract reads:

Acquiring three dimensional image volumes with techniques such as Optical Coherence Tomography (OCT) relies on reconstructing the tissue layers based on reflection of light from tissue interfaces. One B-mode scan in an image is acquired by scanning and concatenating several A-mode scans, and several contiguous slices are acquired to assemble a full 3D image volume. In this work, we demonstrate how Compressive Sampling (CS) can be used to accurately reconstruct 3D OCT images with minimal quality degradation from a subset of the original image. The full 3D image is reconstructed from sparsely sampled data by exploiting the sparsity of the image in a carefully chosen transform domain. We use several sub-sampling schemes, recover the full 3D image using CS, and show that there is negligible effect on clinically relevant morphometric measurements of the optic nerve head in the recovered image. The potential outcome of this work is a significant reduction in OCT image acquisition time, with possible extensions to speeding up acquisition in other imaging modalities such as ultrasound and MRI.

Analyzing Weighted $\ell_1$ Minimization for Sparse Recovery with Nonuniform Sparse Models by M. Amin Khajehnejad, Weiyu Xu, A. Salman Avestimehr, Babak Hassibi. The abstract reads:

In this paper we introduce a nonuniform sparsity model and analyze the performance of an optimized weighted $\ell_1$ minimization over that sparsity model. In particular, we focus on a model where the entries of the unknown vector fall into two sets, with entries of each set having a specific probability of being nonzero. We propose a weighted $\ell_1$ minimization recovery algorithm and analyze its performance using a Grassmann angle approach. We compute explicitly the relationship between the system parameters-the weights, the number of measurements, the size of the two sets, the probabilities of being nonzero- so that when i.i.d. random Gaussian measurement matrices are used, the weighted $\ell_1$ minimization recovers a randomly selected signal drawn from the considered sparsity model with overwhelming probability as the problem dimension increases. This allows us to compute the optimal weights. We demonstrate through rigorous analysis and simulations that for the case when the support of the signal can be divided into two different subclasses with unequal sparsity fractions, the optimal weighted $\ell_1$ minimization outperforms the regular $\ell_1$ minimization substantially. We also generalize the results to an arbitrary number of classes.

A Lower Bound on the Estimator Variance for the Sparse Linear Model by Sebastian Schmutzhard, Alexander Jung, Franz Hlawatsch, Zvika Ben-Haim, Yonina C. Eldar. The abstract reads:

We study the performance of estimators of a sparse nonrandom vector based on an observation which is linearly transformed and corrupted by additive white Gaussian noise. Using the reproducing kernel Hilbert space framework, we derive a new lower bound on the estimator variance for a given differentiable bias function (including the unbiased case) and an almost arbitrary transformation matrix (including the underdetermined case considered in compressed sensing theory). For the special case of a sparse vector corrupted by white Gaussian noise-i.e., without a linear transformation-and unbiased estimation, our lower bound improves on previously proposed bounds.

The Predictive Lasso by Minh-Ngoc Tran, David Nott, Chenlei Leng. The abstract reads:

We propose a shrinkage procedure for simultaneous variable selection and estimation in generalized linear models (GLMs) with an explicit predictive motivation. The procedure estimates the coefficients by minimizing the Kullback-Leibler divergence of a set of predictive distributions to the corresponding predictive distributions for the full model, subject to an $l_1$ constraint on the coefficient vector. This results in selection of a parsimonious model with similar predictive performance to the full model. Thanks to its similar form to the original lasso problem for GLMs, our procedure can benefit from available $l_1$-regularization path algorithms. Simulation studies and real-data examples confirm the efficiency of our method in terms of predictive performance on future observations.

Bayesian Adaptive Lasso by Chenlei Leng, Minh-Ngoc Tran, David Nott. The abstract reads:

We propose the Bayesian adaptive Lasso (BaLasso) for variable selection and coefficient estimation in linear regression. The BaLasso is adaptive to the signal level by adopting different shrinkage for different coefficients. Furthermore, we provide a model selection machinery for the BaLasso by assessing the posterior conditional mode estimates, motivated by the hierarchical Bayesian interpretation of the Lasso. Our formulation also permits prediction using a model averaging strategy. We discuss other variants of this new approach and provide a unified framework for variable selection using flexible penalties. Empirical evidence of the attractiveness of the method is demonstrated via extensive simulation studies and data analysis.

If you think this blog provides a service, please support it by ordering through the Amazon - Nuit Blanche Reference Store

CS: The long post of the week (Remarks, Noisy Group Testing, Streaming Compressive Sensing and more)

Echoing an entry on why we should not care about P vs NP when discussing compressed sensing issues, and rather focus on the Donoho-Tanner phase transition, I was reminded (after re-reading one of Suresh's entry "...Remember that exponential might be better than n^100 for many values of n." )  that Dick Lipton pointed out to this issue as well  Is P=NP an Ill Posed Problem?, albeit more eloquently. If last week's scammer (P = NP, "It's all about you, isn't it ?") had even bothered to answer half seriously the question, I think I would have sent some money, really...So maybe it's not such good idea to use the same subject to fight the next scammer, they might get good at answering P vs NP questions :-)

Dick Lipton mentioned on his blog that he has new book out. Giuseppe also mentioned his intention on buying Understanding Complex Datasets: Data Mining with Matrix Decompositions. Both of them are in the Nuit Blanche bookstore.

Talking about the bookstore, some commenter summarized some of my thoughts in the entry about the store's introduction.

The Nikon camera having a projector built-in makes it possible to project on the object various pseudo-random matrix masks, for 3d reconstruction, dual-photography or various CS uses. Does the software allow to use the projector at the same time as the main camera module ? Some hacking might be needed to open these cool possibilities...

You bet! I might add that a similar stance should be taken for this FujiFilm Finpix camera, the 3D AIPTEK camcorder or the Minoru 3Dwebcam albeit more along the lines of MIT's random lens imager.

In a different direction, Kerkil Choi has a post on his website where he is trying to clear up some statement on his recent paper:

Compressive holography and the restricted isometry property

posted Sep 8, 2010 4:34 PM by Kerkil Choi   [ updated Sep 13, 2010 11:21 AM ]
I have received a surge of emails asking why our compressive holography necessarily works in the context of compressive sensing.
 
One intuitional explanation is that the hologram (after removing the signal autocorrelation and the twin image terms) may be interpreted as a slice of the 3D Fourier transform according to the Fourier diffraction slice theorem developed in diffraction tomography. A Fourier transform measurement matrix is called an incoherent measurement matrix in the compressive sensing literature. Our measurement is quite structured, but it may be thought of as an instance or realization of such random sets of samples.
 
A more rigorous argument relies on the work of Justin Romberg at Georgia Tech. Justin proved that a random convolution matrix built by multiplying an inverse Fourier transform matrix, a diagonal with random phase entries with unit magnitudes, and a Fourier transform matrix satisfies the restricted isometry property (RIP), which is an essential (but sufficient) condition for compressive sensing to work. Amusingly, such a matrix can be interpreted as a free space propagation matrix in the context of physics, which is often used in holography and interferometry - a free space propagation matrix has an identical form to that proven by Romberg. Again, the matrix is structured, but it may be viewed as a realization of such a class of random convolution matrices.
 
Here is Justin's paper:
Compressive Sensing by Random Convolution, Justin Romberg, SIAM J. Imaging Sci. 2, 1098 (2009), DOI:10.1137/08072975X 
He proved that a random convolution matrix constructed as he suggests satisfies a concentration inequality similar to what is shown in the Johnson-Lindenstrauss Lemma (JL lemma). This fascinating link, which now shows in almost every CS literature, between the JL lemma and the RIP has been beautifully elucidated by Baraniuk et al - here is the paper:
R. G. Baraniuk, M. A. Davenport, R. A. DeVore and M. B. Wakin, "A simple proof of the restricted isometry property for random matrices," Constructive Approximation, 2007.

If this response is not enough to convince y'all that if you have a physical system your main job is to focus on getting a Donoho-Tanner phase transition diagram then I don't know what can sway you. I mean making a statement on RIP and then not broaching the subject afterwards in the paper when it comes to the actual realization of this property by the hardware is simply asking the reviewers to beat you up with a large and mean stick!. 

Of interest this week on the long post are the following papers:

Group Testing with Probabilistic Tests: Theory, Design and Application by Mahdi Cheraghchi, Ali Hormati, Amin Karbasi, Martin Vetterli. The abstract reads:

Identification of defective members of large populations has been widely studied in the statistics community under the name of group testing. It involves grouping subsets of items into different pools and detecting defective members based on the set of test results obtained for each pool.

In a classical noiseless group testing setup, it is assumed that the sampling procedure is fully known to the reconstruction algorithm, in the sense that the existence of a defective member in a pool results in the test outcome of that pool to be positive. However, this may not be always a valid assumption in some cases of interest. In particular, we consider the case where the defective items in a pool can become independently inactive with a certain probability. Hence, one may obtain a negative test result in a pool despite containing some defective items. As a result, any sampling and reconstruction method should be able to cope with two different types of uncertainty, i.e., the unknown set of defective items and the partially unknown, probabilistic testing procedure. In this work, motivated by the application of detecting infected people in viral epidemics, we design non-adaptive sampling procedures that allow successful identification of the defective items through a set of probabilistic tests. Our design requires only a small number of tests to single out the defective items. In particular, for a population of size N and at most K defective items with activation probability p, our results show that M = O(K^2 log(N/K)/p^2) tests is sufficient if the sampling procedure should work for all possible sets of defective items, while M = O(K log(N)/p^2) tests is enough to be successful for any single set of defective items. Moreover, we show that the defective members can be recovered using a simple reconstruction algorithm with complexity of O(MN).

Extending Group Testing to include noisy measurements, I like it a lot!

Streaming compressive sensing for high-speed periodic videos, by M. Salman Asif, Dikpal Reddy, Petros Boufounos and Ashok Veeraraghavan. The abstract reads:

The ability of Compressive Sensing (CS) to recover sparse signals from limited measurements has been recently exploited in computational imaging to acquire high-speed periodic and near periodic videos using only a low-speed camera with coded exposure and intensive off-line processing. Each low-speed frame integrates a coded sequence of high-speed frames during its exposure time. The high-speed video can be reconstructed from the low-speed coded frames using a sparse recovery algorithm. This paper presents a new streaming CS algorithm specifically tailored to this application. Our streaming approach allows causal on-line acquisition and reconstruction of the video, with a small, controllable, and guaranteed buffer delay and low computational cost. The algorithm adapts to changes in the signal structure and, thus, outperforms the off-line algorithm in realistic signals.

The attendant videos are here. I note from the introduction:

In this paper we significantly enhance this work in several ways:

• We develop a streaming reconstruction algorithm, the Streaming Greedy Pursuit (SGP) [9], which enables on-line reconstruction of the high-speed video. The CoSaMP-based SGP is specifically designed for streaming CS scenarios, with explicit guarantees on the computational cost per sample and on the input-output delay. 
• We formulate a signal model to incorporate the similarities in the sparsity structure of nearby pixels in the reconstruction algorithm using the principles of joint sparsity and model-based CS [10, 11]. 
• We combat matrix-conditioning problems that arise due to the non-negative nature of imaging measurements by revisiting the minimum variance (or Capon) beamformer from the array processing literature [12] and re-introducing it in the context of CS. Our work significantly improves the reconstruction performance of coded strobing video and, more importantly, enables on-line reconstruction of the acquired video.

Decentralized Sparse Signal Recovery for Compressive Sleeping Wireless Sensor Networks by Qing Ling and Zhi Tian. The abstract reads:

This paper develops an optimal decentralized algorithm for sparse signal recovery and demonstrates its application in monitoring localized phenomena using energy-constrained large-scale wireless sensor networks. Capitalizing on the spatial sparsity of localized phenomena, compressive data collection is enforced by turning off a fraction of sensors using a simple random node sleeping strategy, which conserves sensing energy and prolongs network lifetime. In the absence of a fusion center, sparse signal recovery via decentralized in-network processing is developed, based on a consensus optimization formulation and the alternating direction method of multipliers. In the proposed algorithm, each active sensor monitors and recovers its local region only, collaborates with its neighboring active sensors through low-power one-hop communication, and iteratively improves the local estimates until reaching the global optimum. Because each sensor monitors the local region rather than the entire large field, the iterative algorithm converges fast, in addition to being scalable in terms of transmission and computation costs. Further, through collaboration, the sensing performance is globally optimal and attains a high spatial resolution commensurate with the node density of the original network containing both active and inactive sensors. Simulations demonstrate the performance of the proposed
approach.

Sparse nonnegative matrix approximation: new formulations and algorithms by Rashish Tandon and Suvrit Sra. The abstract reads:

We introduce several new formulations for sparse nonnegative matrix approximation. Subsequently, we solve these formulations by developing generic algorithms. Further, to help selecting a particular sparse formulation, we briefly discuss the interpretation of each formulation. Finally, preliminary experiments are presented to illustrate the behavior of our formulations and algorithms.

Also in a somewhat different direction there is the presentation: Scalable Tensor Factorizations with Incomplete Data by Tamara G. Kolda, Daniel M. Dunlavy, Evrim Acar , Morten Mørup.

As stated earlier, (CS: Compressive Sensing on Cleve's corner), Cleve Moler, the founder of Mathworks (Matlab) has an article on Compressed Sensing. An interesting tidbit shows up at the very end:

Compressed Sensing

Compressed sensing promises, in theory, to reconstruct a signal or image from surprisingly few samples. Discovered just five years ago by Candès and Tao and by Donoho, the subject is a very active research area. Practical devices that implement the theory are just now being developed. It is important to realize that compressed sensing can be done only by a compressing

sensor, and that it requires new recording technology and file formats. The MP3 and JPEG files used by today’s audio systems and digital cameras are already compressed in such a way that exact reconstruction of the original signals and images is impossible. Some of the Web postings and magazine articles about compressed sensing fail to acknowledge this fact.

Looks like somebody has been, at the very least, reading the wikipedia page on the subject. Good!

Finally, we have behind a paywall:

A compressive sensing approach to perceptual image coding by Mark R. Pickering, Junyong You, Touradj Ebrahimi. The abstract reads:

There exist limitations in the human visual system (HVS) which allow images and video to be reconstructed using fewer bits for the same perceived image quality. In this paper we will review the basis of spatial masking at edges and show a new method for generating a just-noticeable distortion (JND) threshold. This JND threshold is then used in a spatial noise shaping algorithm using a compressive sensing technique to provide a perceptual coding approach for JPEG2000 coding of images. Results of subjective tests show that the new spatial noise shaping framework can provide significant savings in bit-rate compared to the standard approach. The algorithm also allows much more precise control of distortion than existing spatial domain techniques and is fully compliant with part 1 of the JPEG2000 standard.

If you think this blog provides a service, please support it by ordering through the Amazon - Nuit Blanche Reference Store

Credit: NASA/JPL/Space Science Institute,

W00065463.jpg was taken on September 18, 2010 and received on Earth September 20, 2010. The camera was pointing toward SATURN at approximately 1,963,182 kilometers away, and the image was taken using the MT3 and IRP90 filters.

CS: 1-bit Fest

I don't know if this was a local expression or just something known in the language of students, but back when I was one, some times, we would unplug and do crazy things for a little while. We would generally call that period of time: 'name-of-person-involved-in-the-crazy-partying'-Fest. Today we have something that might not be that wild but is amazing nonetheless; so I am going to call it: 1-Bit Fest and it comes in the shape of three papers. Maybe I should have a static page on the subject after all. Enjoy.

Sample Complexity for 1-bit Compressed Sensing and Sparse Classification by Ankit Gupta, Robert Nowak, Benjamin Recht. The abstract reads:

This paper considers the problem of identifying the support set of a high-dimensional sparse vector, from noise corrupted 1-bit measurements. We present passive and adaptive algorithms for this problem, both requiring no more than O(d log(D)) measurements to recover the unknown support. The adaptive algorithm has the additional benefit of robustness to the dynamic range of the unknown signal.

Trust, but Verify: Fast and Accurate Signal Recovery from 1-bit Compressive Measurements by Jason  Laska, Zaiwen Wen, Wotao Yin, and Richard Baraniuk. The abstract reads:

The recently emerged compressive sensing (CS) framework aims to acquire signals at reduced sample rates compared to the classical Shannon-Nyquist rate. To date, the CS theory has assumed primarily real-valued measurements; it has recently been demonstrated that accurate and stable signal acquisition is still possible even when each measurement is quantized to just a single bit. This property enables the design of simplified CS acquisition hardware based around a simple sign comparator rather than a more complex analog-to-digital converter; moreover, it ensures robustness to gross non-linearities applied to the measurements. In this paper we introduce a new algorithm — restricted-step shrinkage (RSS) — to recover sparse signals from 1-bit CS measurements. In contrast to previous algorithms for 1-bit CS, RSS has provable convergence guarantees, is about an order of magnitude faster, and achieves higher average recovery signal-to-noise ratio. RSS is similar in spirit to trust-region methods for non-convex optimization on the unit sphere, which are relatively unexplored in signal processing and hence of independent interest.

I have seen this trust but verify term used before, all y'all are reading too much Nuit Blanche and something sticks...

Universal Rate-Efficient Scalar Quantization by Petros T. Boufounos. The abstract reads:

Scalar quantization is the most practical and straightforward approach to signal quantization. However, it has been shown that scalar quantization of oversampled or Compressively Sensed signals can be inefficient in terms of the rate-distortion trade-off, especially as the oversampling rate or the sparsity of the signal increases. In this paper, we modify the scalar quantizer to have discontinuous quantization regions. We demonstrate that with this modification it is possible to achieve exponential decay of the quantization error as a function of the oversampling rate instead of the quadratic decay exhibited by current approaches. We further demonstrate that it is possible to further reduce the quantization error by incorporating side information on the acquired signal, such as sparse signal models or signal similarity with known signals. Our approach is universal in the sense that prior knowledge of the signal model is not necessary in the quantizer design.

From the conclusion I note the following interesting tidbit:

Last, we should note that this quantization approach has very tight connections with locality-sensitive hashing (LSH) and `2 embeddings under the hamming distance (e.g., see [46] and references within). Specifically, our quantization approach effectively constructs such an embedding, some of the properties of which are examined in [47], although not in the same language. A significant difference is on the objective. Our goal is to enable reconstruction, whereas the goal of LSH and randomized embeddings is to approximately preserve distances with very high probability. A rigorous treatment of the connections on the connections of quantization and LSH is quite interesting and deserves a publication of its own. A preliminary attempt to view LSH as a quantization problem is performed in [48].

If you think this blog provides a service, please support it by ordering through the Amazon - Nuit Blanche Reference Store

P = NP, "It's all about you, isn't it ?"

[Check the update at the end of this entry]

While the P=NP proof is taking some time to be digested by the community, I wondered if the time spent in understanding its implication would weed out the wrong people. Case in point: here is another person who doesn't care about Deolalikar's proof, the scammer who took over Hadi Zayyani's yahoo email account.

The first message came to me yesterday:

I Hope you get this on time,sorry I didn't inform you about my trip in Spain for a program, I'm presently in Madrid and am having some difficulties here because i misplaced my wallet on my way to the hotel where my money and other valuable things were kept.I want you to assist me with a loan of 2500Euros to sort-out my hotel bills and to get myself back home.I have spoken to the embassy here but they are not responding to the matter effectively,I will appreciate whatever you can afford to assist me with,I'll Refund the money back to you as soon as i return, let me know if you can be of any help. I don't have a phone where i can be reached. Please let me know immediately.

With best regards

Hadi Zayyani

At that point, I know this is a scam since you just need to take the whole text and feed it to the Google and see the results. It is however perplexing because the e-mail header really shows it has been sent from Hadi's account. I then responded with the following with the intent on figuring out if this was a live scam or just one of those spam e-mails:

M:

I need a phone number to let you know where I can wire the money.

The scammer is interested it seems, S:

Thanks for your response and also for your concern towards my present situation. Kindly send the money to me Using Western Union Money Transfer.I will be  able to get the money in minutes after you transfer fund with ease. Here is the information you need.

Receivers Names:Hadi Zayyani
Receivers Address: Calle Vereda Norte 3,La Moraleja, Madrid, 28109, Spain

Please scan and forward the receipt of the transfer to me or write out the details on the receipt and send to me,it will enable me to pick up the money from here.i will be waiting for your positive response.

Thanks

hadi zayyani

Ok so now we are getting more personal and so I have to make up something because I really don't like people using other people's e-mail account for scamming:

Hadi,

You never responded to my query as to whether you think the recent P = NP proof will be important with regards to your reconstruction solver ?

I look forward to hearing from you on this matter.

PS: I have sent the money

S:

Kindly forward me the transfer details for picking up the money at the Western union outlet.

M:

Hadi,

You will get the details of the transfer only if you tell me if you think the recent P = NP proof will be important with regards to your reconstruction solver ? Thanks.

S:

No there's no need for P =NP prof concerning my present situation down here.I will refund the money back to you as soon as i get back home.

M:

It may be the case for your situation, but what about the recent P = NP proof as it pertains specifically to your reconstruction solver ? Thanks.

S:

I want you to know that all this you were asking me is not so important for me right now.Please i want you to understand me and do this for me so that i can get out of trouble here in Spain.

M:

It's all about you, isn't it ?

I haven't heard from that person since.

[Update: To give some background to our new readers: in Compressive Sensing, we solve what was thought  to be an NP-hard problem however a simple additional constraint (sparsity) has put our problem in the P territory. In the past few years, reconstruction solvers ( in the P class) and have steadily improved numerically (as opposed to just asymptotically.) Our main concern these days is figuring out the Donoho-Tanner border] 

If you think this blog provides a service, please support it by ordering through the Amazon - Nuit Blanche Reference Store

CS: I don't really care what you call it, Samsung is planning on doing compressed sensing!

Image Sensor World, a very good blog on what is happening in the imaging sensors area, just featured the following tidbits:

Samsung Plans 3D Cameras with Single Sensor

Korea Times quoted Park Sang-jin, president of Samsung’s digital imaging division, saying "As the issue with 3D televisions is providing a glass-free viewer experience, 3D cameras has a similar challenge for achieving a one-lens, one-imaging sensor approach. The two-lens, two-sensor 3D camera released by Fuji is still too expensive and inconvenient for users."

Park also said that the company may produce a camera capable of taking three-dimensional (3D) images sometime next year, but admitted that it will be a digital guinea pig, saying that the "real" 3D cameras that are suited for conventional use won’t probably be available until after 2012.

In the comment section, I guessed that the process involved in this technology would include some of Ramesh Raskar et al work/ideas. The blog owner also mentioned a Kodak patent. Either way, light from different views is superimposed on the same chip, i.e. several views are multiplexed together. Irrespective to the reconstruction method that might take advantage of the particulars of the hardware, this is compressed sensing in that information is being multiplexed (and compressed) to eventually be produced back to the user (in 3D format). Now the question of interest is really whether the demultiplexing operation will use a sparsity argument. Some people might take the view that if this is not the case, then it is not what we all call compressed sensing. However, one should always be very circumstantial on the matter: Demultiplexing your information through some known engineering does not means that you are not implicitly using the sparsity assumption.

Of note, one of the commenter is none other than Eric Fossum, the inventor of the CMOS Active Pixel Technology.

By the way, Ramesh let me know that the Camera Culture Lab has now a page on Facebook. Another Facebook page is of interest is Yes, CSI Image Processing is Science ( Fiction! )