CSJob: Signal processing summer internship Computational Sensing and Imaging Group, Rambus Labs, Sunnyvale, CA

You probably recall Patrick Gill from these entries:

• Calibrating and Enhancing the Planar Fourier Capture Array ?
• The In-Crowd Algorithm for Fast Basis Pursuit Denoising
• Calibration and Compressive Sensing Sensor Implementations

Well Patrick, is now at Rambus and he just sent me this awesome opportunity:

Hi Igor,

Thanks again for coordinating the Nuit Blanche blog, which continues to be a great way to keep up with the state of the art in compressive sensing. I have been continuing my research into tiny optical sensors at Rambus. We have had some big ideas recently, and we're looking for an algorithm and signal processing expert to spend a summer working with us. While the ad below targets Ph.D. students, we are also open to the possibility of an intern who already has their Ph.D. Compensation is very competitive; we would like to attract the best of the best. If you think Nuit Blanche readers might be interested, please feel free to post about this ad.

Best wishes,

Patrick R. Gill

Thanks Patrick , here is the announcement

Signal processing summer internship

Computational Sensing and Imaging Group

Rambus Labs

Sunnyvale, CA

The Computational Sensing and Imaging Group within Rambus Labs continues to develop new classes of optical sensors.  We are seeking a highly qualified signal processing engineer to assist an active research team in the invention and implementation of numerically-efficient algorithms for image processing, computer vision and optical sensing based on the measurements these devices make.  This summer internship position affords the opportunity of patenting as well as publishing new mathematics and algorithms related to our research.

Candidates should have the following qualifications:

• BS or MS degree in mathematics, electrical engineering, physics, computer science or a closely-related discipline and current enrollment in a relevant graduate program or substantial, relevant, outstanding work experience
• Facility implementing numerically-efficient solutions to inverse problems in MATLAB, C or C++, including multicore and networked environments
• Innovation in numerically-efficient methods of implementing sparse priors for image reconstruction would be an asset
• Experience in generalized convolution and deconvolution with spatially-varying kernels desirable
• Strong knowledge of algorithms in computer vision, image processing and pattern recognition
• Strong verbal and mathematical communication skills
• Experience with cluster computing and GPGPU programming
• Legal permission to work in the USA

Rambus Inc., is located in Silicon Valley/Bay Area, near cultural centers such as San Jose and San Francisco, academic centers such as Stanford University and U. C. Berkeley, and many spectacular natural destinations such as Yosemite National Park, Lake Tahoe, Big Sur, Marin Headlands, Sonoma Valley, Napa Valley, ….

To apply:  Go to this link.

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

That Netflix RMSE is way too low or is it ? ( Clustering-Based Matrix Factorization - implementation -)

[[ Update: this paper has been removed from ArXiv. For more info check This Week's Guardians of Science: Zeno Gantner and Peyman Milanfar ]

We've seen this type of occurrence on Nuit Blanche before. This one is either a bombshell or a dud. Early on in a discussion in the Advanced Matrix Factorization group, Nima Mirbakhsh shared his thought and a interesting and potentially mind blowing implementation, here is what he said:

Helping to evaluate my proposed extension on matrix factorization.

Hello eveyone,

I have a new extension of matrix factorization named "Clustering-Based Matrix Factorization". I apply it on many datasets including "Netflix", "Movielens", "Epinions", "Flixter", and it acheives very good results. For the last three data sets the RMSE result is good and realizable, but for Netflix dataset it acheives very interestng result. As we all know the RMSE result of the Netflix prize winner was 0.8567, now my method achieves the RMSE of 0.8122.

I know that the Netflix prize winner's method includes fusion of lots of different algorithm's result, and it is hard to believe that one algorithm can reach such a good result. It has been my concern in the last couple of months too. Thus, I check my source code and my setup several time but cannot find any bug there. I also submit the paper in ICML but except a weak acceptation all other reviewers said that my method actually make sense but they all reject my work just because of the extraordinary result!

That is why I decide to put the paper and my source code online that everyone can evaluate it. Now, I am going to ask you to kindly joining me to evaluate the paper and the source code more accurately. Lets say if my method works fine, it is going to be a new experience on recommendation systems and may show us that they are still opportunities to improve the RMSE results.

Here is the paper's link following by source code's link:

http://arxiv.org/abs/1301.6659 

source code: http://goo.gl/Az0lS 

Thanks everyone in advance.

We recently saw some improvement of the Netflix RMSE (Linear Bandits in High Dimension and Recommendation Systems) but this time, the code is shared for everybody to kick the tires on it. As a reminder, we featured that paper earlier:

Clustering-Based Matrix Factorization by Nima Mirbakhsh, Charles X. Ling

Recommender systems are emerging technologies that nowadays can be found in many applications such as Amazon, Netflix, and so on. These systems help users find relevant information, recommendations, and their preferred items. Matrix Factorization is a popular method in Recommendation Systems showing promising results in accuracy and complexity. In this paper we propose an extension of matrix factorization that uses the clustering paradigm to cluster similar users and items in several communities. We then establish their effects on the prediction model then. To the best of our knowledge, our proposed model outperforms all other published recommender methods in accuracy and complexity. For instance, our proposed method's accuracy is 0.8122 on the Netflix dataset which is better than the Netflix prize winner's accuracy of 0.8567.

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Coded Hyperspectral Imaging and Blind Compressive Sensing

Now we're getting to the heart of calibration of compressive imagers by extending dictionary learning to blind Compressive Sensing using the CASSI imager. I love it and look forward to the attendant algorithm.

Coded Hyperspectral Imaging and Blind Compressive Sensing by Ajit Rajwade, David Kittle, Tsung-Han Tsai, David Brady and Lawrence Carin. The abstract reads:

Blind compressive sensing (CS) is considered for reconstruction of hyperspectral data imaged by a coded aperture camera. The measurements are manifested as a superposition of the coded wavelengthdependent data, with the ambient three-dimensional hyperspectral datacube mapped to a two-dimensional measurement. The hyperspectral datacube is recovered using a Bayesian implementation of blind CS. Several demonstration experiments are presented, including measurements performed using a coded aperture snapshot spectral imager (CASSI) camera. The proposed approach is capable of efficiently reconstructing large hyperspectral datacubes. Comparisons are made between the proposed algorithm and other techniques employed in compressive sensing, dictionary learning and matrix factorization.

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

InView Announces Compressive Sensing Workstation

I don't have any stakes in InView. Here is their latest press release:

InView Expands Compressive Sensing Workstations Series with Two New Products

Austin, TX, January 31, 2013: InView Technology Corporation, the world leader in Compressive Sensing (CS) imaging products, has expanded its family of CS Workstations with the release of two new systems, the InView222 Compressive Sensing Workstation and the InView223 Spatial Light Modulator. Both systems allow researchers to prototype and test innovative computational imaging algorithms.

The InView222 builds upon the successful InView220 Compressive Sensing Workstation that was introduced by InView in 2012. The InView222 enables researchers to demonstrate novel CS algorithms on a complete hardware imaging platform. It allows researchers to apply measurement bases using a high-speed, spatial light modulator (SLM) sub-system, and to process the modulated image in a measurement sub-system. The measurement sub-system includes a single-diode CMOS detector, followed by an amplifier and analog-to-digital converter. 

The InView223 provides a SLM sub-system and is coupled to user’s own measurement sub-system, allowing bench-top experiments in fields of research including computational imaging, computational photography, compressive sensing, and other fields requiring high-speed custom optical modulation.

Both the InView222 and InView223 give researchers an unprecedented ability to apply novel 1024x768 pixel modulation patterns at rates of up to 32,000 patterns per second using a digital micro-mirror device. Both systems accept externally-generated SLM patterns streamed from an external source over an eight lane, PCI Express 2.0 bus, which has sufficient speed to allow the SLM to run at full speed. The user does not need to buffer patterns in development system memory as is required by other micromirror-based products.

Both products leverage an objective lens optimized for visual light and use a standard M42 lens mount.

“InView’s Compressive Sensing Workstation Family allows researchers to easily demonstrate their advanced imaging algorithms on easy-to-use hardware,” stated Dr. Bob Bridge, InView’s founder and CEO. “These new products are a welcome addition to the Workstation launched last year.”

About InView

InView specializes in the design, development and manufacturing of imaging products based upon Compressive Sensing technology, including low-cost shortwave infrared (SWIR) cameras. Leveraging its patents in Compressive Sensing, InView’s InGaAs-based SWIR solutions can achieve superior results at dramatically reduced prices, and provide leadership price-performance for microscopy, security, surveillance, maritime navigation, military and other applications.

# # #

For more information on the products, please contact:

info@InViewCorp.com

For more information on InView, please contact:

bob.bridge@InViewCorp.com

(512) 243-8751 x 104

Note to editors: InView and the InView logo are trademarks of InView Technology Corporation. Other trademarks or brand names mentioned herein are trademarks of their respective holders.

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Correcting Camera Shake by Incremental Sparse Approximation - implementation -

[ Update: there is a new version of the paper here. For more info check This Week's Guardians of Science: Zeno Gantner and Peyman Milanfar ]

Paul Shearer just sent me the following:

"Dear Igor,

I've recently submitted a paper on sparsity-based blind deconvolution that I thought might be of interest to some Nuit Blanche readers. The arXiv link is

http://arxiv.org/abs/1302.0439

and a MATLAB implementation (with data reproducing the claimed results) is available on my website:

http://sitemaker.umich.edu/shearerp/home

The abstract is below my signature.

Cheers,

Paul Shearer

PhD candidate, Applied Mathematics

University of Michigan, Ann Arbor

shearerp@umich.edu"

Thank you Paul  !

Correcting Camera Shake by Incremental Sparse Approximation by Paul Shearer, Anna C. Gilbert, Alfred O. Hero III

The problem of deblurring an image when the blur kernel is unknown remains challenging after decades of work. Recently there has been rapid progress on correcting irregular blur patterns caused by camera shake, but there is still much room for improvement. We propose a new blind deconvolution method using incremental sparse edge approximation to recover images blurred by camera shake. We estimate the blur kernel first from only the strongest edges in the image, then gradually refine this estimate by allowing for weaker and weaker edges. Our method matches the benchmark deblurring performance of the state-of-the-art while being significantly faster and easier to generalize.

Previous featured papers on Blind Deconvolution can be found here.



Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Call for Interest in a CubeSat experiment

If you are in a European University or an Engineering school and think you want to fly something into space on board a CubeSat, such as, for instance, some sorts of compressive imager or some sorts of crazy imaging with nature  (and plenty of ground based smartphones). I can help. ESA also wants to hear from you in the form of a CubeSat proposal by March 1st. Contact me and let us have a discussion ( I have done a few things in space ).


Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Breaking the coherence barrier: asymptotic incoherence and asymptotic sparsity in compressed sensing

Let's put this in context, in optical imaging we had this scheme by Justin Romberg featured in "Imaging via CS", the issue of bicubic interpolation articulated by Leslie Smith, the failure of any CS reconstruction scheme to do well on the Matlab programming contest, the rise of variable density schemes in MRI (see the work of Miki Lustig), This mismatch between reality and the theory is why we need more math not less (see Negative reviews and the weak minded). You also probably recall these recent discussions

• A Q&A with Ben Adcock and Anders Hansen: Infinite Dimensional Compressive Sensing, Generalized Sampling, Wavelet Crimes, Safe Zones and the Incoherence Barrier.
• Additional insights on the Q&A with Ben Adcock and Anders Hansen

If those issues have been bothering you, you might very much like this new paper by Ben Adcok, Anders Hansen, Clarice Poon and Bogdan Roman. First Ben introduced the subject as follows:

Dear Igor, 

I hope you are well. I very much enjoyed our discussion a few months ago on infinite-dimensional compressed sensing. I'm very pleased that you're taking an interest in our work.

This email is to let you know about our new paper. When we spoke in December Anders mentioned that we were about to launch some new stuff on how to break the coherence barrier. Well, it's now finished:

http://www.math.purdue.edu/~adcock/Papers/BreakingCoherence.pdf

We think it will be of broad interest to the CS community. A brief description is as follows:

In the paper we show how to overcome the coherence barrier in compressed sensing by introducing a mathematical framework where the traditional pillars of CS theory, namely sparsity, incoherence and uniform random subsampling, are replaced by three new concepts: asymptotic sparsity, asymptotic incoherence and multilevel random sampling. These assumptions are more relevant for many problems, in particular, imaging. As a result, our main theorems bridge a gap between existing CS theory and its current use in applications such as MRI. In particular, our theory explains the abundance of numerical evidence demonstrating the advantage of so-called variable density sampling strategies.

Our theory and experiments also allow us to draw some important conclusions. First, the success of CS in applications such as these is highly dependent on the problem resolution. Second, the optimal sampling strategy is completely dependent on signal structure. We refer to such structure as asymptotic sparsity in levels. And third, the RIP, whilst a standard tool in CS theory, is of little relevance in such problems. In other words, for realistic parameter choices (resolution, subsampling percentage, sparsity) the corresponding matrices do not satisfy the RIP. Our results are based solely on coherence (or, more precisely, local coherence), and in that sense are RIPless theories.

In addition to the paper we are about to launch a website:

www.subsample.org

It should be up and running soon. It will contain numerical experiments in addition to those found in the paper, and will soon be populated with matlab code, test images, descriptions of the project and various other things.

Anyway, if you have any comments or suggestions, then please do let me know.

Best wishes,

Ben

Thanks Ben ! He talso tells me that the site is not yet running but I will keep you posted when it is. Breaking the coherence barrier: asymptotic incoherence and asymptotic sparsity in compressed sensing by Ben Adcok, Anders Hansen, Clarice Poon and Bogdan Roman. The introduction starts with:

1 Introduction

In this paper we bridge the substantial gap between existing compressed sensing theory and itscurrent use in real-world applications.

1 We do so by introducing a new mathematical framework for overcoming the so-called coherence barrier. Our framework generalizes the three traditional pillars of compressed sensing|namely, sparsity, incoherence and uniform random subsampling|to three new concepts: asymptotic sparsity, asymptotic incoherence and multilevel random subsampling. As we explain, asymptotic sparsity and asymptotic incoherence are more representative of real-world problems|e.g. imaging| than the usual assumptions of sparsity and incoherence. For instance, problems in Magnetic Resonance Imaging (MRI) are both asymptotically sparse and asymptotically incoherent, and hence amenable to our framework.

The second important contribution of the paper is an analysis of a novel and intriguing e ect that occurs in asymptotically sparse and asymptotically incoherent problems. Namely, the success of compressed sensing is resolution dependent.

As suggested by their names, asymptotic incoherence and asymptotic sparsity are only truly witnessed for reasonably large problem sizes. When the problem size is small, there is little to be gained from compressed sensing over classical linear reconstruction techniques. However, as we show in this paper, once the resolution of the problem is su fficiently large, compressed sensing can and will o er a substantial advantage. This is so-called resolution dependence. This phenomenon has the following two important consequences, which are also summarized in Figure 1:

(i) Suppose one considers a compressed sensing experiment where the sampling device, the object to be recovered, the sampling strategy and subsampling percentage are all fixed, but the resolution is allowed to vary. Resolution dependence means that a compressed sensing reconstruction done at high resolutions (e.g. 2048 2048) will yield much higher quality when compared to full sampling than one done at a low resolution (e.g. 256 256). This phenomenon has an important consequence for practitioners investigating the usefulness of compressed sensing algorithms. A scientist carrying out an experiment at low resolution may well conclude that compressed sensing imparts limited bene ts. However, a markedly dfferent conclusion would be reached if the same experiment were to be performed at higher resolution.

(ii) Suppose we conduct a similar experiment, but we now use the same total number of samples N (instead of the same percentage) at low resolution as we take at high resolution. Intriguingly, the above result still holds: namely, the higher resolution reconstruction will yield substantially better results. This is true because the multilevel random sampling strategy successfully exploits asymptotic sparsity and asymptotic incoherence. Thus, with the same amount of total effort, i.e. the number of measurements, compressed sensing with multilevel sampling works as a resolution enhancer : it allows one to recover the ne details of an image in a way that is not possible with the lower resolution reconstruction.

On a broader note, resolution dependence and its consequences suggest the following advisory for practitioners: it is critical that simulations with compressed sensing be carried out with a careful understanding of the influence of the problem resolution. Na ve simulations with standard, low-resolution test images may very well lead to incorrect conclusions about the efficacy of compressed sensing as a tool for image reconstruction.

An important application of our work is the problem of MRI, which turns out to be a highly coherent problem. MRI served as one of the original motivations for compressed sensing, and continues to be a topic of substantial research. Some of the earliest work on this problem| in particular, the research of Lustig et al. [33, 34, 35]|demonstrated that, due to the high coherence, the standard random sampling strategies of compressed sensing theory lead to highly substandard reconstructions. On the other hand, random sampling according to some nonuniform density was shown empirically to lead to substantially improved reconstruction quality. Since the work of Lustig et al. these observations have been confirmed in numerous other investigations [34, 35, 38, 39, 45], and it is now standard in MR applications to use some sort of variable density strategy to overcome the coherence barrier.

This work has culminated in the extremely successful application of compressed sensing to MRI. However, a mathematical theory addressing these sampling strategies is largely lacking. Despite some recent work [31] (see Section 8 for a discussion), a substantial gap exists between the standard theorems of compressed sensing and its implementation in such problems.

The purpose of this paper is to introduce a mathematical foundation for compressed sensing for coherent problems and to rigorously show that the coherence barrier can be broken. In doing so, we provide a rm theoretical basis for the above empirical studies demonstrating the success of nonuniform density sampling. In addition, our main results give insight into how to design e fficient subsampling techniques based on multi-level strategies.

Whilst the MR problem will serve as our main application, we stress that our theory is extremely general in that it holds for almost arbitrary sampling and sparsity systems. As we demonstrate, standard compressed sensing results, such as those of Cand es, Romberg & Tao [14], Cand es & Plan [12], are specifi c instances of our main theorems.

Another facet to our work is that we shall present theorems that cover not only the case of signals and images modelled as vectors in fi nite-dimensional vector spaces, but also elements of 2 separable Hilbert spaces. This continues the work of Adcock & Hansen [2] on in nite-dimensional compressed sensing. In Section 2.2 we explain the importance of this generalisation.

Now let's make the next leap forwaed: what are the hardware architecture enabled or changed by this new understanding ?

Join the CompressiveSensing subreddit or the Google+ Community and post there !

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Negative reviews and the weak minded

Negative reviews should be the exception not the norm. Why ? Take for example the recent press release by MIT on compressive sensing. (Toward practical compressed sensing). In particular, I am a little annoyed by this statement:

"...But it’s been slow to catch on commercially, in part because of a general skepticism that sophisticated math ever works as well in practice as it does in theory...."

Sophisticated math ? No, the real issue ? compressive sensing is simply not a mature field and if there is one thing it is probably that the math is not sophisticated enough.

• How many people still ask questions about RIP as being an important consideration ?
• How many people still describe compressive sensing as an inpainting scheme ?
• How many people don't realize that the single pixel camera can be made to work in a raster mode ?

Too many if you ask me, I have even heard a story where a PI had to go through the extra mile to convince a postdoc to just try compressive sensing. In the end, based solely on reading papers, the postdoc was adamantly convinced that a Thikonov reconstruction was the best thing on earth.  Here is an instance of another negative review described by Pierre Vandergheynst in a post on his Google+ stream which had a real impact on a potentially useful project: 

"....Two years ago, I submitted a project to the Swiss SNF proposing to extend our early work on compressed sensing for sensing ECG for low power applications. The application was rejected based on a review that cited a paper, from MIT, where authors had "... mathematically proved that CS would never be a good alternative for low power applications... " of the type we were considering. Now another MIT paper proves just the opposite.

The original paper was quite theoretical and making very strong assumptions on what hardware does. It was unrealistic but it's OK. The paper was studying asymptotic regimes. But in order to have a good impact I suppose it was making strong claims, and it was not backed up by any experiment. This paper also makes hypothesis and it is also OK. I'll tell you what is not OK. What is not OK is when reviewers scan papers, grant proposals at the level of PR and then singlehandedly destroy 6 or 9 months of serious work.

In the end, our project was delayed. We filed and obtained a rather large EU grant, but had to make a lot of compromises. We will never explore low power CS for ECG in depth the way we proposed in the original grant unfortunately. Because it was "mathematically proved" to be a bad idea, before it was proved to be a good one .... ..."

I think he may refer to a specific result which might be part of that book.

The take away from this ? Published negative reviews provide a great mechanism for the weak minded gatekeepers be they your own postdocs or your average grant reviewers. Publish one at your own peril. Tomorrow, we'll feature a new paper that will bring down all the mental barriers that keep us from the only thing we should be doing: exploration. There, you will be able to read:

"...However, since the RIP-based techniques are well established, it is worth posing the following question: is the RIP relevant for imaging problems? ... It is our belief that the answer to this is no...In view of this, the third conclusion of our work is that the RIP is of limited value in analysing compressive imaging strategies."

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Nuit Blanche in Review (January 2013 edition)

After the year in review [17, 38],  we had a list of implementations [18-26], a set of meetings [27-30], some hardware implementations [31-33], some meeting videos and papers [34-35], a job [36], some blog etiquette [37] as well as miscellaneous entries [38-41]. 

We also got a sense as to when compressive imaging might be an advantage over simpler systems [3] but the study did not take into account the technology. When CMOS doesn't work, you're back to square one. 

We had a few entries featuring improvement over "older" technology (MRI [7]). One of the surprising finding this past month was the fact that some deterministic approaches seem to be doing as well as random multiplexings [16]. This and the finding with metamaterials [33] might change computational imaging altogether. The whole investigation could use blind deconvolution [4] for random systems. Among the implementations that were made available [18-26] we had a system that mixes matrix factorization and random forest [15] and was the winner of the KDDCup two years in a row [23], an analog sparse recovery solver [22], and a parallel algorithm for solving linear equations that really seems to be O(n^3) unless you have O(n) cores (Thanks Danny) in which cases it becomes O(n^2)..

Adaptive sensing also called Linear Bandits [6] in this recommender systems approach showed up on the radar screen. Randomization brought us some new results in large scale function evaluation [10, 12] and potentially some faster belief propagation (AMP) algorithms [15]. Some conversation on bad reconstruction and error metrics [8, 11, 12] and low rank approaches in the tensor domain [5] provided some depth to the field. It's not just about vectors or sparsity.  

Finally, we had two long entries of papers [1,2] and some entries relevant our continuous exploration [9] . A new approach to using compressive sensing outside of the generally well known fields [14], I like it very much! What will February bring ?

The previous Nuit Blanche reviews can be found here.

References:

1. This (Past) Month in Compressive Sensing and Matrix Factorization
2. Part Deux: This (Past) Month in Compressive Sensing and Matrix Factorization
3. When Does Computational Imaging Improve Performance?
4. Phase Diagram and Approximate Message Passing for Blind Calibration and Dictionary Learning
5. Tensor completion based on nuclear norm minimization for 5D seismic data reconstruction
6. Linear Bandits in High Dimension and Recommendation Systems
7. Spread spectrum compressed sensing MRI using chirp radio frequency pulses
8. Signal reconstruction in linear mixing systems with additive error metrics (video introduction)
9. Around the blogs in 80 summer hours
10. Fast Food: Approximating Kernel Expansion in Loglinear Time
11. All hopes may not be crushed all at once
12. It's not a bad reconstruction, just the end of an illusion...
13. Fast Functions via Randomized Algorithms: Linear Regression with Random Projections
14. A Computational model for compressed sensing RNAi cellular screening
15. Recent Algorithms Development and Faster Belief Propagation algorithms
16. Deterministic matrices matching the compressed sensing phase transitions of Gaussian random matrices
17. A gut feeling review of 2012.
18. Structure-Based Bayesian Sparse Reconstruction - implementation -
19. Improving Dictionary Learning: Multiple Dictionary Updates and Coefficient Reuse - implementation -
20. A Randomized Parallel Algorithm with Run Time $O(n^2)$ for Solving an $n \times n$ System of Linear Equations - 
21. Compressed Sensing with Correlation Between Measurements and Noise - implementation -
22. Convergence Speed of a Dynamical System for Sparse Recovery - implementation -
23. SVDFeature: A Toolkit for Feature-based Collaborative Filtering - implementation -
24. A Probabilistic Approach to Robust Matrix Factorization - implementation -
25. Heliometric Stereo: Shape from Sun Position - implementation 
26. AMP: Assembly Matching Pursuit, Metagenomic units (MGUs) discovery through sequence-based dictionary learning - implementation -
27. ROKS 2013 International Workshop on Advances in Regularization, Optimization, Kernel Methods and Support Vector Machines:
28. Phased Array 2013 announcement
29. SPARS'13 deadlines approaching soon ! #spars13 and #Spars13 announcements and clarifications
30. Fête Parisienne in Computation, Inference and Optimization: A Young Researchers' Forum
31. Three-dimensional ghost imaging ladar 
32. Correspondence Differential Ghost Imaging 
33. Metamaterial Apertures for Computational Imaging
34. The #NIPS2012 Videos are out 
35. Pacific Symposium on Biocomputing papers
36. CSJob: Faculty at University of Wisconsin-Madison
37. Welcome back to the Jungle
38. Where are we now ?
39. Agents of Change
40. The Technical Side of the Nuclear Rockets Option
41. Sudoku, Compressive Sensing and Thermodynamics

Image Credit: NASA/JPL-Caltech
This image was taken by Navcam: Left A (NAV_LEFT_A) onboard NASA's Mars rover Curiosity on Sol 176 (2013-02-03 00:25:21 UTC) .
Full Resolution


Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Part Deux: This (Past) Month in Compressive Sensing and Matrix Factorization

In the previous entry ( This (Past) Month in Compressive Sensing and Matrix Factorization ) I did not include other papers/preprints that showed up on my other radar screen this january. Here they are:

Think commenting on a blog is useless, let me present to you the trillion dollar blog comment. 

Hein Hundal and Carl Cotner discovered the Predicting the Future blog entry, Galaxy Phones have barometers, the possibility are near endless and Raspberry Pi can enble Camera With Pan and Tilt capabilties. In other news, Keck Foundation awards $1 million to team of UCLA scientists. Anaïs Tamalet has updated the mindmaps on compressive sensing at SLIM. There are here and Dan Reetz pointed me to this patent on  Image Acquisition Using Oversampled One-Bit Poisson Statistics. The abstract reads: 

In an image sensor pixels in an array of binary pixels are sampled with a first oversampling factor during a first frame interval, and then sampled with a second oversampling factor during a second frame interval, the second oversampling factor exceeding the first oversampling factor.

The list of talks at ITA2013 us here. Preprints and Papers of interest this past month also include the following: Robust Subspace Clustering by Mahdi Soltanolkotabi, Ehsan Elhamifar and Emmanuel J. Cand es. The abstract reads:

Subspace clustering refers to the task of fi nding a multi-subspace representation that best fi ts a collection of points taken from a high-dimensional space. This paper introduces an algorithm inspired by sparse subspace clustering (SSC) [15] to cluster noisy data, and develops some novel theory demonstrating its correctness. In particular, the theory uses ideas from geometric functional analysis to show that the algorithm can accurately recover the underlying subspaces under minimal requirements on their orientation, and on the number of samples per subspace. Synthetic as well as real data experiments complement our theoretical study, illustrating our approach and demonstrating its e ffectiveness.

ACCURATE DETECTION OF MOVING TARGETS VIA RANDOM SENSOR ARRAYS AND KERDOCK CODES by THOMAS STROHMER AND HAICHAO WANG. The abstract reads:

Abstract. The detection and parameter estimation of moving targets is one of the most important tasks in radar. Arrays of randomly distributed antennas have been popular for this purpose for about half a century. Yet, surprisingly little rigorous mathematical theory exists for random arrays that addresses fundamental question such as how many targets can be recovered, at what resolution, at which noise level, and with which algorithm. In a different line of research in radar, mathematicians and engineers have invested significant effort into the design of radar transmission waveforms which satisfy various desirable properties. In this paper we bring these two seemingly unrelated areas together. Using tools from compressive sensing we derive a theoretical framework for the recovery of targets in the azimuth-range-Doppler domain via random antennas arrays. In one manifestation of our theory we use Kerdock codes as transmission waveforms and exploit some of their peculiar properties in our analysis. Our paper provides two main contributions: (i) We derive the first rigorous mathematical theory for the detection of moving targets using random sensor arrays. (ii) The transmitted waveforms satisfy a variety of properties that are very desirable and important from a practical viewpoint. Thus our approach does not just lead to useful theoretical insights, but is also of practical importance. Various extensions of our results are derived and numerical simulations confirming our theory are presented.

Imagerie acoustique par approximations parcimonieuses des sources by Antoine Peillot

La description parcimonieuse des sources permet une approche nouvelle de l'analyse des champs acoustiques. Durant ce projet, nous avons appliqué ce principe à plusieurs scénarios classiques : l'holographie acoustique de champ proche, la localisation de sources simples ou complexes et l'identification de directivité de sources. Ces méthodes d'imagerie exigent la résolution de problèmes inverses, souvent mal posés, qui nécessitent l'utilisation conjointe de techniques de régularisation. De plus, pour capter l'information utile et assurer de bonnes performances de reconstruction, les techniques traditionnelles d'antennerie nécessitent le déploiement d'un grand nombre de microphones. Dans ces travaux, nous avons envisagé une approche originale de l'analyse des champs acoustiques basée sur l'approximation parcimonieuse des sources, ce qui agit comme un principe de régularisation. Cette formulation permet en outre de tirer profit de la méthode de "compressive sampling" (CS), qui permet de restreindre le nombre de mesures utiles à la résolution du problème inverse si la source à reconstruire admet une représentation suffisamment parcimonieuse. On montre que l'application du CS à l'holographie en champ proche de plaques homogènes et isotropes permet non seulement de mieux régulariser le problème par rapport aux techniques génériques classiques, mais également de diminuer fortement le nombre de microphones en sous-échantillonnant l'hologramme au-delà de la limite imposée par la théorie de Shannon. Le problème de localisation de sources, envisagée comme un problème parcimonieux, permet la localisation avec une haute résolution de sources corrélés, en champ proche comme en champ lointain. Les méthodes de reconstruction parcimonieuse permettent de structurer la base de parcimonie en l'enrichissant avec un modèle de décomposition des sources en harmoniques sphériques pour localiser et identifier la directivité de sources complexes. Ces études ont finalement nécessité le développement de techniques rapides de calibration en position et en gain d'antennes composées d'un grand nombre de microphones.

Acoustic sources imaging in the sparsity framework

In this work the principle of sparsity-based techniques have been applied to acoustic imaging issues. It includes nearfield acoustic holography (NAH), complex sources localization and directivity pattern identification. These techniques consist in the inversion of ill-posed problems which involve the use of regularization schemes. Moreover, standard regularization methods often require a huge number of microphones in order to oversample the acoustic field and therefore avoiding aliasing effects. To overcome these problems, we investigate sparse regularization principles and/or compressive sampling (CS) for the analysis of acoustic fields. CS states that, under the sparsity assumption of the source to recover, it is possible to significantly reduce the number of measurements (i.e., microphones), even well below spatial Nyquist rates. It is shown that sparsity-based NAH techniques lead to significant improvements over standard NAH techniques. A sub-Nyquist random sampling combined with sparse regularization allows the precise source reconstruction. The problem of source localization can be recast in a sparse framework. It acts as a high-resolution localisation method for correlated and uncorrelated sources that lie in the near field or in the far field. The use of sparsity-promoting algorithms allows the localization of complex sources by improving the sparse model with a spherical harmonic dictionary. This method is applied to the identification of sources directivity pattern. Finally, microphone position self-calibration methods are investigated to experimentally manage large microphone arrays.

Robust Late Fusion With Rank Minimization by Guangnan Ye, Dong Liu, I-Hong Jhuo, Shih-Fu Chang

In this paper, we propose a rank minimization method to fuse the predicted confidence scores of multiple models, each of which is obtained based on a certain kind of feature. Specifically, we convert each confidence score vector obtained from one model into a pairwise relationship matrix, in which each entry characterizes the comparative relationship of scores of two test samples. Our hypothesis is that the relative score relations are consistent among component models up to certain sparse deviations, despite the large variations that may exist in the absolute values of the raw scores. Then we formulate the score fusion problem as seeking a shared rank-2 pairwise relationship matrix based on which each original score matrix from individual model can be decomposed into the common rank-2 matrix and sparse deviation errors. A robust score vector is then extracted to fit the recovered low rank score relation matrix. We formulate the problem as a nuclear norm and 1 norm optimization objective function and employ the Augmented Lagrange Multiplier (ALM) method for the optimization. Our method is isotonic (i.e., scale invariant) to the numeric scales of the scores originated from different models. We experimentally show that the proposed method achieves significant performance gains on various tasks including object categorization and video event detection.

$S_{0.5}$ Regularization and Fixed Point Algorithm for Low-Rank Matrix Recovery by Peng Dingtao, Xiu Naihua, Yu Jian

Abstract: The low-rank matrix recovery is mathematically matrix rank minimization problem under linear constraints. It has many applications in various areas such as statistics, control, system identification and machine learning. Unlike the literatures which use nuclear norm to approximate the rank of matrices, in this paper we use Schatten 1/2 norm approximation which leads to a better approximation but a nonconvex, nonsmooth, and non-Lipschitz optimization problem. Through developing a fixed point theory associated with the singular value half thresholding operator for $S_{1/2}$ regularization solutions, we propose a fixed point algorithm for solving the $S_{1/2}$ regularization problem and prove the convergence of the iterative sequence. By discussing the location of the optimal regularization parameter and its setting as well as using an approximate singular value decomposition procedure, we get an efficient algorithm for $S_{1/2}$ regularization which we call HalfnormFPA algorithm (half norm fixed point algorithm with an approximate SVD). Large numbers of numerical experiments on randomly generated and real matrix completion problems are demonstrated for HalfnormFPA together with several state-of-the-art solvers such as SVT, FPC and FPCA. The numerical results clearly show that HalfnormFPA is very fast, robust and powerful, and that it provides much better recoverability than all above state-of-the-art solvers.

Energy-guided learning approach to compressive FD-OCT
by Shimon Schwartz, Chenyi Liu, Alexander Wong, David A. Clausi,Paul Fieguth, and Kostadinka Bizheva (pdf is here)

High quality, large size volumetric imaging of biological tissue with optical coherence tomography (OCT) requires large number and high density of scans, which results in large data acquisition volume. This may lead to corruption of the data with motion artifacts related to natural motion of biological tissue, and could potentially cause conflicts with the maximum permissible exposure of biological tissue to optical radiation. Therefore, OCT can benefit greatly from different approaches to sparse or compressive sampling of the data where the signal is recovered from its sub-Nyquist measurements. In this paper, a new energy-guided compressive sensing approach is proposed for .

Compressed sensing subtracted rotational angiography with multiple sparse penalty by Hélène Langet , C. Riddell , Y. Trousset, Arthur Tenenhaus, Elisabeth Lahalle, Gilles Fleury 1, Nikos Paragios

Digital Subtraction Rotational Angiography (DSRA) is a clinical protocol that allows three-dimensional (3D) visualization of vasculature during minimally invasive procedures. C-arm systems that are used to generate 3D reconstructions in interventional radiology have limited sampling rate and thus, contrast resolution. To address this particular subsampling problem, we propose a novel iterative reconstruction algorithm based on compressed sensing. To this purpose, we exploit both spatial and temporal sparsity of DSRA. For computational efficiency, we use a proximal implementation that accommodates multiple '1-penalties. Experiments on both simulated and clinical data confirm the relevance of our strategy for reducing subsampling streak artifacts. 

Novel signal separation algorithm based on compressed sensing for wideband spectrum sensing in cognitive radio networks by Shoutao Lv and Jian Liu, 

Optimal Detection For Sparse Mixtures by Tony Cai and Yihong Wu

Abstract: Detection of sparse signals arises in a wide range of modern scientific studies. The focus so far has been mainly on Gaussian mixture models. In this paper, we consider the detection problem under a general sparse mixture model and obtain an explicit expression for the detection boundary. It is shown that the fundamental limits of detection is governed by the behavior of the log-likelihood ratio evaluated at an appropriate quantile of the null distribution. We also establish the adaptive optimality of the higher criticism procedure across all sparse mixtures satisfying certain mild regularity conditions. In particular, the general results obtained in this paper recover and extend in a unified manner the previously known results on sparse detection far beyond the conventional Gaussian model and other exponential families.

An Improved Compressive Sensing Reconstruction Algorithm Using Linear/Non-Linear Mapping by Xinyu Zhang, Jiangtao Wen, Yuxing Han and John Villasenor

Abstract— We describe an improved algorithm for signal reconstruction based on the Orthogonal Matching Pursuit (OMP) algorithm. In contrast with the traditional implementation of OMP in compressive sensing (CS) we introduce a preprocessing step that converts the signal into a distribution that can be more easily reconstructed. This preprocessing introduces negligible additional complexity, but enables a significant performance improvement in the reconstruction accuracy

Vectorial Phase Retrieval of 1-D signals by Oren Raz, Nirit Dudovich and Boaz Nadler

Abstract—Reconstruction of signals from measurements oftheir spectral intensities, also known as the phase retrieval problem, is of fundamental importance in many scientific fields.In this paper we present a novel framework, denoted as vectorial phase retrieval, for reconstruction of pairs of signals from spectral intensity measurements of the two signals and of the interference. We show that this new framework can alleviate some of the theoretical and computational challenges associated with classical phase retrieval from a single signal. First, we prove that for compactly supported signals, in the absence of measurement noise, this new setup admits a unique solution. Next,we present a statistical analysis of vectorial phase retrieval and derive a computationally efficient algorithm to solve it. Finally,we illustrate via simulations, that our algorithm can accurately reconstruct signals even at considerable noise levels.

Phase retrieval combined with digital holography by Eliyahu Osherovich, Michael Zibulevsky, and Irad Yavneh

We present a new method for real- and complex-valued image reconstruction from two intensity measurements made in the Fourier plane: the Fourier magnitude of the unknown image, and the intensity of the interference pattern arising from superimposition of the original signal with a reference beam. This approach can provide signi cant advantages in digital holography since it poses less stringent requirements on the reference beam. In particular, it does not require spatial separation between the sought signal and the reference beam. Moreover, the reference beam need not be known precisely, and in fact, may contain severe errors, without leading to a deterioration in the reconstruction quality. Numerical simulations are presented to demonstrate the speed and quality of reconstruction.

Combining Factorization Model and Additive Forest for Collaborative Followee Recommendation by Tianqi Chen, Linpeng Tang, Qin Liu, Diyi Yang, Saining Xie, Xuezhi Cao, Chunyang Wu, Enpeng Yao, Zhengyang Liu, Zhansheng Jiang, Cheng Chen, Weihao Kong, Yong Yu

Social networks have become more and more popular in recent years. This popularity creates a need for personalization services to recommend tweets, posts (information) and celebrities organizations (information sources) to users according to their potential interest. Tencent Weibo (microblog) data in KDD Cup 2012 brings one such challenge to the researchers in the knowledge discovery and data mining community. Compared to traditional scenarios in recommender systems, the KDD Cup 2012 Track 1 recommendation task raises several challenges: (1) Existence of multiple, heterogeneous data sources; (2) Fast growth of the social network with a large number of new users, which causes a severe user cold-start problem; (3) Rapid evolution of items’ popularity and users’ interest. To solve these problems, we combine feature-based factorization models with additive forest models. Specifically, we first build factorization models that incorporate users’ social network, action, tag/keyword, profile and items’ taxonomy information. Then we develop additive forest models to capture users’ activity and sequential patterns. Because of the additive nature of such models, they allow easy combination of the results from previous factorization models. Our modeling approach is able to utilize various side information provided by the challenge dataset, and thus alleviates the cold-start problem. The new temporal dynamics model we have proposed using an additive forest can automatically adjust the splitting time points to model popularity evolution more accurately. Our final solution obtained an MAP@3 of 0:4265 on the private leader board, giving us the first place in Track 1 of KDD Cup 2012. 

Join the CompressiveSensing subreddit or the Google+ Community and post there !

  Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.