Tuesday, May 21, 2013

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:

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.


Anonymous said...

I think any MR physicist will tell you that doing this kind of random walk for the k-space trajectory is either impossible or the MRI scanner will just explode. However the paper is wrong when saying the random scheme (figure a) is not realistic, it is possible to sample like this by using 3D acquisition.

Unknown said...

Actually, such schemes can be done in actual MR device, but require that the speed in the k-space is zero for each angular point. These trajectories are thus not optimal (regarding the time of acquisition), but our work will be extended to more smooth trajectories.

2D random schemes + acquisition of the orthogonal lines are indeed realistic, but not optimal. Our method can be extended to 3D (we implemented this), which allows us to exploit both the increased sparsity using 3D wavelet transforms and the optimality of the (3D!) distribution.

Pierre Weiss said...

If despite the last comment, you still believe this sampling scheme is not realistic, we are very interested in knowing why.

At least we took into account the slew rate and limited acceleration. These are the standard constraints taken into account in MRI, see e.g. the paper by Lustig, Kim Pauly

Best regards,
Pierre Weiss