Following up on the recent entries about the "compressibility" of the realizations of the Gaussian noise (see also here), Ori Shental who started me into writing about this with his paper, sent me the following:
Dear Igor,
Following your recent post about the WGN simulation:Please note that according to Claim #3, stating the marginal achieving distribution (and its illustration in Fig. 2), the SPARSEST representation of WGN (i.e., on the threshold curve itself) consists of *infinite* spikes (namely uniform distribution in the +/- infinity) for the non-zero entries. According to the derived marginal distribution of the non-zero entries of the sparse WGN representation there is a *gap*, or a dead-zone, in the values taken by those non-zero entries, which increases to infinite as you get closer to the threshold curve (please look at the example Gaussian tails on Figure 2).Hence in the limit of large systems, the sparsest representation is composed of infinite values, a picture which is difficult to reproduce in practical simulation. However Claim 3, gives us a hint on how to threshold the simulation results in order to grasp the entire "compressibility" (i.e. get the full "belly" beyond the trivial \alpha=\kappa line): According to eq. (23) any non-zero value *below* (in absolute value) the standard deviation (multiplied by some auxiliary scalar \xi) of the Gaussian, described also in eq. (23), should be discarded and set to 0. This STD can be inferred from the histogram of the results obtained by SL0, IRLS or any other approximation to L0. This thresholding should allow us to imitate the workings in the limit of large systems, based on finite-size simulation data.Cheers,Ori
Thanks Ori !
I also got an Email from Greg Charvat. If you remember him, he is the one who gets his students to write a blog about how their class assignment on SARs radar using aluminum (pringle?) cans.
Thanks Greg !Hi Igor,
Thought your readers might find this interesting:
I am collaborating with Prof. Staelin at MIT to offer a 1-week MIT Professional Education course on radar systems, where each student actually builds their own radar set then takes it into the field to perform experiments, including SAR imaging of urban terrain. The course is open to any professional in the field, details here:
This course will be based on our IAP radar course taught at MIT this past January:
Cheers,Greg
PS. I am collaborating with Prof. Mark Richards from Georgia Tech to post some of my rail SAR phase data on the web so that students can use it. Mark tells me it is tough to get raw data, or pretty much impossible without lots of restrictions. So i figured it would be good to let the compressed sensing community know this when it happens because you guys might want to play around with actual radar phase data. Hope this helps.
Dick Gordon just wrote an entry on Breast Cancer Wars: Delaying The TKO? while Zhilin Zhang made a comparison and wrote about it in his blog on two reconstruction algorithms in Is MMV more suitable for dynamic environment (time-varying sparsity) than KF-CS and LS-CS?
Of note, Rich Baraniuk has switched his webpage into a blog. One of his recent entry is an abstract of a recent Nature article entitled: Data Deluge in Science. The positions for his lab are here.
Even thought it is also on Rich's blog, Laurent Jacques was the first to send something about this new 1-bit sensing paper entitled: Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors by Laurent Jacques, Jason N. Laska, Petros T. Boufounos, and Richard Baraniuk . The abstract reads:
The Compressive Sensing (CS) framework aims to ease the burden on analog-to-digital converters (ADCs) by reducing the sampling rate required to acquire and stably recover sparse signals. Practical ADCs not only sample but also quantize each measurement to a finite number of bits; moreover, there is an inverse relationship between the achievable sampling rate and the bit depth. In this paper, we investigate an alternative CS approach that shifts the emphasis from the sampling rate to the number of bits per measurement. In particular, we explore the extreme case of 1-bit CS measurements, which capture just their sign. Our results come in two flavors. First, we consider ideal reconstruction from noiseless 1-bit measurements and provide a lower bound on the best achievable reconstruction error. We also demonstrate that a large class of measurement mappings achieve this optimal bound. Second, we consider reconstruction robustness to measurement errors and noise and introduce the Binary -Stable Embedding (B SE) property, which characterizes the robustness measurement process to sign changes. We show the same class of matrices that provide optimal noiseless performance also enable such a robust mapping. On the practical side, we introduce the Binary Iterative Hard Thresholding (BIHT) algorithm for signal reconstruction from 1-bit measurements that offers state-of-the-art performance.
From an e-mail conversation I had with Laurent, Jason, and Rich and Gabriel Peyre, it looks like a demo will shortly be available on the interwebs. thanks guys, I know somebody who's looking at the Earth Hum who wants to test this thing.
Through Mark Davenport's twitter stream, I learned about an extensive course entitled "An Introduction to Compressive Sensing" written by Richard Baraniuk, Mark Davenport, Marco Duarte, Chinmay Hegde now available from cnx.org. wow, I'll add it shortly to both the big picture and the Teaching Compressive Sensing page.
Finally, I found the following papers on the interwebs:
Compressive Sampling of Multiple Sparse Signals Having Common Support Using Finite Rate of Innovation Principles by Ali Hormati, and Martin Vetterli. The abstract reads:
In sensor networks and communication systems, one is often confronted with sampling multiple sparse signals having a common support set. Multipath channels in a multiple-input multiple-output (MIMO) wireless communication setting is an interesting example where one generally needs to perform channel estimation for each transmit-receive antenna pair. MIMO multipath channels are usually (approximately) sparse and satisfy the common-support property whenever the distances between the antennas are small compared to the distance the electromagnetic wave can travel in the time corresponding to the inverse bandwidth of the communication system. This assumption is satisfied by small and medium bandwidth communication systems like OFDM and CDMA. This leads us to extend the finite rate of innovation sampling and reconstruction scheme to the sparse common-support scenario (SCS-FRI), in which input signals contain Diracs with common locations but arbitrary weights. The goal is to efficiently reconstruct the input signals from a set of uniform samples, making use of the common-support property to improve robustness. We first find the best theoretical performance for the SCS-FRI setup by deriving the Cram´er-Rao lower bound. Our results show that for a set of well-separated Diracs, it is the total energy of the Diracs at each common position which determines the bound. We then propose a multi-channel reconstruction algorithm and compare its performance with the Cram´er-Rao lower bound. Numerical results clearly demonstrate the effectiveness of our proposed sampling and reconstruction scheme in low SNR regimes
SPARSE SPECTRAL FACTORIZATION: UNICITY AND RECONSTRUCTION ALGORITHMS by Yue M. Lu and Martin Vetterli. The abstract reads:
Spectral factorization is a classical tool in signal processing and communications. It also plays a critical role in X-ray crystallography, in the context of phase retrieval. In this work, we study the problem of sparse spectral factorization, aiming to recover a one-dimensional sparse signal from its autocorrelation. We present a sufficient condition for the recovery to be unique, and propose an iterative algorithm that can obtain the original signal (up to a sign change, time-shift and time-reversal). Numerical simulations verify the effectiveness of the proposed algorithm.
ESTIMATING SPARSE MIMO CHANNELS HAVING COMMON SUPPORT by Yann Barbotin, Ali Hormati, Sundeep Rangan, Martin Vetterli. The abstract reads:
We propose an algorithm (SCS-FRI) to estimate multipath channels with Sparse Common Support (SCS) based on Finite Rate of Innovation (FRI) sampling. In this setup, theoretical lower-bounds are derived, and simulation in a Rayleigh fading environment shows that SCS-FRI gets very close to these bounds. We show how to apply SCS-FRI to OFDM and CDMA downlinks. Recovery of a sparse common support is, among other, especially relevant for channel estimation in a multiple output system or beam-forming from multiple input. The present algorithm is based on a multi-output extension of the Cadzow denoising/annihilating filter method [1, 2].
The present paper proposes and studies an algorithm to estimate channels with a sparse common support (SCS). It is a generalization of the classical sampling of signals with Finite Rate of Innovation (FRI) [1] and thus called SCS-FRI. It is applicable to OFDM and WalshHadamard coded (CDMA downlink) communications since SCS-FRI is shown to work not only on contiguous DFT pilots but also uniformly scattered ones. The support estimation performances compare favorably to theoretical lower-bounds, and importantly this translates into a substantial equalization gain at the receiver compared to the widely used spectrum lowpass interpolation method.
Image frames from dynamic MRI can be abstracted as the superposition of the background component, which is temporally coherent, and the motion component, which is spatially sparse, up to the proper basis. Inspired by their distinct characterizations, we introduce the divide-and-conquer spatiotemporal matrix decomposition approach, namely Prior Rank, Intensity and Sparsity Model (PRISM). Here the temporal coherence of the background component is enforced by the rank regularization and the spatial sparsity of the motion component is promoted by the sparsity regularization in framelets. The validation with both synthetic and experimental cardiac data and the comparison with the state-of-art reconstruction methods show that PRISM is feasible for maintaining the reconstruction quality with much fewer samples. The consequent reduction of data acquisition time can relax the breath-holding constraint with possibly less respiratory motion artifact and more regular heart rate in cardiac cine imaging, and enable the imaging of patients with faster heart rate in real-time cardiac cine imaging.
Image Credit: NASA/Johns Hopkins University Applied Physics Laboratory/Carnegie Institution of Washington, Mercury, as Seen in High Resolution As the MESSENGER spacecraft sped over Mercury's north polar region, the NAC captured this image in very high resolution. This area is located north of Hokusai.
Congratulations for this 1000th entry Igor! This is amazing. Laurent
ReplyDelete