Monday, April 06, 2009

CS: Compressive Sensing VLBI, Finding Significant Fourier Transform Coefficients, Challenging Restricted Isometry Constants with GP, FBMP, Utar's blog

Andriyan Suksmono just released a Compressive Sensing paper on VLBI entitled: Deconvolution of VLBI Images Based on Compressive Sensing. The abstract reads:
Direct inversion of incomplete visibility samples in VLBI (Very Large Baseline Interferometry) radio telescopes produces images with convolutive artifacts. Since proper analysis and interpretations of astronomical radio sources require a non-distorted image, and because filling all of sampling points in the uv-plane is an impossible task, image deconvolution has been one of central issues in the VLBI imaging. Up to now, the most widely used deconvolution algorithms are based on least-squares-optimization and maximum entropy method. In this paper, we propose a new algorithm that is based on an emerging paradigm called compressive sensing (CS). Under the sparsity condition, CS capable to exactly reconstructs a signal or an image, using only a few number of random samples. We show that CS is well suited with the VLBI imaging problem and demonstrate that the proposed method is capable to reconstruct a simulated image of radio galaxy from its incomplete visibility samples taken from elliptical trajectories in the uv-plane. The effectiveness of the proposed method is also demonstrated with an actual VLBI measured data of 3C459 asymmetric radiogalaxy observed by the VLA (Very Large Array).

he talks about it on his blog but in Indonesian, the paper is in English.

I mentioned her video talk before here is the paper: Finding Significant Fourier Transform Coefficients Deterministically and Locally by Adi Akavia.The abstract reads:

Computing the Fourier transform is a basic building block used in numerous applications. For data intensive applications, even the O(N logN) running time of the Fast Fourier Transform (FFT) algorithm may be too slow, and sub-linear running time is necessary. Clearly, outputting the entire Fourier transform in sub-linear time is infeasible, nevertheless, in many applications it suffices to find only the t-significant Fourier transform coefficients, that is, the Fourier coefficients whose magnitude is at least t-fraction (say, 1%) of the energy (i.e., the sum of squared Fourier coefficients). We call algorithms achieving the latter SFT algorithms. In this work we present a deterministic algorithm that finds the t-significant Fourier coefficients of functions f over any finite abelian group G in time polynomial in log jGj, 1=t and L1( bf ) (for L1( bf ) denoting the sum of absolute values of the Fourier coefficients of f ). Our algorithm is robust to random noise.
Our algorithm is the first deterministic and efficient (i.e., polynomial in logjGj) SFT algorithm to handle functions over any finite abelian groups, as well as the first such algorithm to handle functions over ZN that are neither compressible nor Fourier-sparse. Our analysis is the first to show robustness to noise in the context of deterministic SFT algorithms. Using our SFT algorithm we obtain (1) deterministic (universal and explicit) algorithms for sparse Fourier approximation, compressed sensing and sketching; (2) an algorithm solving the Hidden Number Problem with advice, with cryptographic bit security implications; and (3) an efficient decoding algorithm in the random noise model for polynomial rate variants of Homomorphism codes and any other concentrated & recoverable codes.

Following up on their A Numerical Exploration of Compressed Sampling Recovery here is Challenging Restricted Isometry Constants with Greedy Pursuit by Charles Dossal, Gabriel Peyré and Jalal Fadili.. The abstract reads:
This paper proposes greedy numerical schemes to compute lower bounds of the restricted isometry constants that are central in compressed sensing theory. Matrices with small restricted isometry constants enable stable recovery from a small set of random linear measurements. We challenge this compressed sampling recovery using greedy pursuit algorithms that detect ill-conditionned sub-matrices. It turns out that these sub-matrices have large isometry constants and hinder the performance of compressed sensing recovery.

This is great as this is one more tool for hardware designers to use when confronted with the physics of the multiplexing device.

Laurent Duval tells me that Phil Schnitter will give a talk in Marne La Vallee on the 8th. While we are on the subject, the FBMP package is now at Version 1.1.

Here is a blog entry by Utar on Compressive Sensing reconstruction in 3D. There are other equally interesting entries in his blog:

No comments: