PalBOMP/PolBOMP: Compressive Parameter Estimation for Sparse Translation-Invariant Signals Using Polar Interpolation - implementation -

Karsten Fyhn just let me know of their recent article and attendant code repository. 

Compressive Parameter Estimation for Sparse Translation-Invariant Signals Using Polar Interpolation by Karsten Fyhn, Marco F. Duarte and Søren H. Jensen

We propose new compressive parameter estimation algorithms that make use of polar interpolation to improve the estimator precision. Moreover, we evaluate six algorithms for estimation of parameters in sparse translation-invariant signals, exemplified with the time delay estimation problem. The evaluation is based on three performance metrics: estimator precision, sampling rate and computational complexity. We use compressive sensing with all the algorithms to lower the necessary sampling rate and show that it is still possible to attain good estimation precision and keep the computational complexity low. The proposed algorithms are based on polar interpolation and our numerical experiments show that they outperform existing approaches that either leverage polynomial interpolation or are based on a conversion to an frequency-estimation problem followed by a super-resolution algorithm. The algorithms studied here provide various tradeoffs between computational complexity, estimation precision and necessary sampling rate. The work shows that compressive sensing for the class of sparse translation-invariant signals allows for a lower sampling rate and that the use of polar interpolation increases the estimation precision.

The MATLAB code for the paper is available at www.sparsesampling.com/cpe

Thanks Karsten


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.

Travelling salesman-based compressive sampling

The issue of random sampling in compressive sensing was made more clear, in my view, by the work of Ben Adcock and Anders Hansen ( see A Q&A with Ben Adcock and Anders Hansen: Infinite Dimensional Compressive Sensing, Generalized Sampling, Wavelet Crimes, Safe Zones and the Incoherence Barrier. ). In short, the whole random sampling story has some problems at low frequencies. In MRI, the field at the leading edge of compressive sensing, several sampling techniques have been evaluated to corner this issue down. What is most interesting in this whole story is the connection with the hardware: We are here seeing a direct connection between actual hardware constraints (sampling authorized by the hardware) and the mathematics of sampling. One needs to realize that this connection between those two fields is rare. Here is another example of the connection between mathematics of sampling and hardware constraints:

Travelling salesman-based compressive sampling by Nicolas Chauffert, Philippe CIUCIU, Jonas Kahn, Pierre Weiss. The abstract reads:

Compressed sensing theory indicates that selecting a few measurements independently at random is a near optimal strategy to sense sparse or compressible signals. This is infeasible in practice for many acquisition devices that acquire samples along \textit{continuous} trajectories. Examples include magnetic resonance imaging (MRI), radio-interferometry, mobile-robot sampling, ... In this paper, we propose to generate continuous sampling trajectories by drawing a small set of measurements independently and joining them using a travelling salesman problem solver. Our contribution lies in the theoretical derivation of the appropriate probability density of the initial drawings. Preliminary simulation results show that this strategy is as efficient as independent drawings while being implementable on real acquisition systems.

If somebody were to explain to me why they have pi^2 as opposed to pi^(1/2), I'd really appreciate it. 

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.

Around the Blogs in 78 hours

Since the last Around the Blogs in 78 hours, we saw some announcements for GraphLab as a company, some calls for SPARC 2013 and GlobalSIP. All of these news in listed below. It even looks like some of you took advantage of the different groups set up for that purpose. Good! To recap, we now have the Google+ Community (384), the CompressiveSensing subreddit (115), the LinkedIn Compressive Sensing group (2273) or the Matrix Factorization (660). With these numbers, it would be a wise choice to directly pitch to these crowds when you want to talk about a new meeting, or a job or anything else for that matter.

Laurent

• Gas chromatography and 2D-gas chromatography for petroleum industry: The race for selectivity
• Signal Processing for Chemical Sensing: ICASSP 2013 Special session

Suresh

• Coding, Complexity and Sparsity 2013 (SPARC) 2013.
• On GPU algorithms

Fabian

• Numerical optimizers for Logistic Regression

Danny

• An Overview of Graph Processing Frameworks
• Kaggle Titanic Contest
• Funding for the next generation of GraphLab
• Bond Percolation in GraphLab

Larry

• STEIN’S PARADOX
• Aaronson, COLT, Bayesians and Frequentists

Dirk

• Open PhD position in applied analysis, mathematical imaging, inverse problems
• Existence of minimizers for the Horn-Schunck functional for optical flow

Hein

• “Randomized Numerical Linear Algebra (RandNLA): Theory and Practice”

Tianyi

• Our DMKD paper is selected as Top 5 Editor’s Choice Article for Free Reading

Josh

• ITAR Craziness in the News

Vladimir

• Gesture Recognition Startup Wins MIT $100K Entrepreneurship Competition

Andrew

• SPARC 2013

Christian

• i-like workshop [talk]
• i-like[d the] workshop

John

• Efficiency vs. Robustness

Machine Learning

• Noisy Time Series V: Mean Reverting Processes

Sebastien

• The aftermath of ORF523 and the final
• ORF523: Optimization with bandit feedback
• ORF523: Acceleration by randomization for a sum of smooth and strongly convex functions

Anand

• CFP : GlobalSIP 2013 Deadline Extended to June 15

Cam

• 21st Century Problems
• Multi-Armed Bandits
• Machine Learning counter-examples
• How to solve the Price is Right's Showdown
• An algorithm to sort "Top" Comments

Brian

• Seeing the potential in 3D

While on Nuit Blanche, we had:

• Ghost Imaging does 3D and multispectral Imaging
• Sparse FFT implementations
• Another day at the Big Data: Theoretical and Practical Challenges Workshop
• A day at the Big Data: Theoretical and Practical Challenges Workshop
• Please take the time to nominate somebody or something today
• Sunday Morning Insight: Computational Cooking, you won't see food the same way anymore.
• The OSTP is seeking an Outstanding “Open Science” Champion of Change
• Saturday Morning Videos (part II)
• Saturday Morning Videos

Credit: ESA/NASA

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.

Ghost Imaging does 3D and multispectral Imaging

Sylvain Gigan (also in Science) let me know of the following paper that is also making the rounds in Science. If you recall, it was shown earlier that compressive sensing was speeding up the process of acquiring the data. The physics itself is not changed and revolves around this formula:

3D Computational Ghost Imaging by Baoqing Sun, Matthew P. Edgar, Richard Bowman, Liberty E. Vittert,Stephen S. Welsh, Ardrian Bowman, Miles J. Padgett

Computational ghost imaging retrieves the spatial information of a scene using a single pixel detector. By projecting a series of known random patterns and measuring the back reflected intensity for each one, it is possible to reconstruct a 2D image of the scene. In this work we overcome previous limitations of computational ghost imaging and capture the 3D spatial form of an object by using several single pixel detectors in different locations. From each detector we derive a 2D image of the object that appears to be illuminated from a different direction, using only a single digital projector as illumination. Comparing the shading of the images allows the surface gradient and hence the 3D form of the object to be reconstructed. We compare our result to that obtained from a stereo- photogrammetric system utilizing multiple high resolution cameras. Our low cost approach is compatible with consumer applications and can readily be extended to non-visible wavebands.

The 3D of this paper has little to do with the 2D extraction from Three-dimensional ghost imaging ladar and we measure reflectance difference here as opposed to time of flight information. Here is the multispectral paper:

Multi-wavelength compressive computational ghost imaging by Stephen S. Welsh, Matthew P. Edgar, Phillip Jonathan, Baoqing Sun, Miles. J. Padgett

The field of ghost imaging encompasses systems which can retrieve the spatial information of an object through correlated measurements of a projected light eld, having spatial resolution, and the associated reflected or transmitted light intensity measured by a photodetector. By employing a digital light projector in a computational ghost imaging system with multiple spectrally fi ltered photodetectors we obtain high-quality multi-wavelength reconstructions of real macroscopic objects. We compare di erent reconstruction algorithms and reveal the use of compressive sensing techniques for achieving sub-Nyquist performance. Furthermore, we demonstrate the use of this technology in non-visible and fluorescence imaging applications.

Thanks Sylvain !





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.

Sparse FFT implementations

Dmitry Savostyanov pointed me to the location of an implementation of the other super Fast FFT we mentioned last September. It is on GitHub here as part of the very promising TT-Toolbox. 

Let us note that the sparse FFT "looks" slower than MIT's sFFT and that the MIT sFFT has currently only version 1 and 2 while Piotr mentioned results for version 3 and 4 on Wednsday at the "Big data: theoretical and practical challenges" workshop.

We are waiting for the Berkeley implementation mentioned previously for the end of the summer. The Ann Arbor FFT (AAFFT) is here.  

With regards to the comparison between sFFT [2] and the TT_toolbox version [1]

It looks like sFFT version 3.0 scales better for K sparse signals than the TT_toolvox one which scales as K^3. But I wouldn't mind seeing comparison for compressible signals (I think it is version 4.0 for sFFT) and the TT_toolbox one. An interesting comparison should eventually entail not integer frequencies and higher dimensions as well. 

Of relevance to all this, all the Slides of the recent Workshop on Sparse Fourier Transform organized by Piotr are here. 

[1] Superfast Fourier Transform Using QTT Approximation by Sergey Dolgov, Boris Khoromskij and Dmitry Savostyanov.
[2] http://groups.csail.mit.edu/netmit/sFFT/results.html

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.