Here is the crop of new and very interesting papers this week:
Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
(Submitted on 18 Jun 2012)
Compressed sensing is a signal processing method that acquires data directly in a compressed form. This allows one to make less measurements than what was considered necessary to record a signal, enabling faster or more precise measurement protocols in a wide range of applications. Using an interdisciplinary approach, we have recently proposed in [arXiv:1109.4424] a strategy that allows compressed sensing to be performed at acquisition rates approaching to the theoretical optimal limits. In this paper, we give a more thorough presentation of our approach, and introduce many new results. We present the probabilistic approach to reconstruction and discuss its optimality and robustness. We detail the derivation of the message passing algorithm for reconstruction and expectation max- imization learning of signal-model parameters. We further develop the asymptotic analysis of the corresponding phase diagrams with and without measurement noise, for different distribution of signals, and discuss the best possible reconstruction performances regardless of the algorithm. We also present new efficient seeding matrices, test them on synthetic data and analyze their performance asymptotically.The aspics solver is here.The next paper is an improvement over one we featured six months ago:
Compressive Fluorescence Microscopy for Biological and Hyperspectral Imaging
(Submitted on 3 Jan 2012 (v1), last revised 16 Jun 2012 (this version, v2))
The mathematical theory of compressed sensing (CS) asserts that one can acquire signals from measurements whose rate is much lower than the total bandwidth. Whereas the CS theory is now well developed, challenges concerning hardware implementations of CS-based acquisition devices---especially in optics---have only started being addressed. This paper presents an implementation of compressive sensing in fluorescence microscopy and its applications to biomedical imaging. Our CS microscope combines a dynamic structured wide-field illumination and a fast and sensitive single-point fluorescence detection to enable reconstructions of images of fluorescent beads, cells and tissues with undersampling ratios (between the number of pixels and number of measurements) up to 32. We further demonstrate a hyperspectral mode and record images with 128 spectral channels and undersampling ratios up to 64, illustrating the potential benefits of CS acquisition for higher dimensional signals which typically exhibits extreme redundancy. Altogether, our results emphasize the interest of CS schemes for acquisition at a significantly reduced rate and point out to some remaining challenges for CS fluorescence microscopy.
Compressed Sensing of EEG for Wireless Telemonitoring with Low Energy Consumption and Inexpensive Hardware
(Submitted on 13 Jun 2012)
Telemonitoring of electroencephalogram (EEG) through wireless body-area networks is an evolving direction in personalized medicine. Among various constraints in designing such a system, three important constraints are energy consumption, data compression, and device cost. Conventional data compression methodologies, although effective in data compression, consumes significant energy and cannot reduce device cost. Compressed sensing (CS), as an emerging data compression methodology, is promising in catering to these constraints. However, EEG is non-sparse in time domain and also non-sparse in transformed domains (such as wavelet domains). Therefore, it is extremely difficult for current CS algorithms to recover EEG with the quality that satisfies the requirements of clinical diagnosis and engineering applications. Recently, block Sparse Bayesian Learning (bSBL) was proposed as a new CS framework. This study introduces the technique to telemonitoring of EEG. Experimental results show that its recovery quality is better than other typical CS algorithms, and high enough to be of practical use. These results suggest that bSBL can be successfully used in telemonitoring of EEG and other non-sparse physiological signals.
Analysis of Inpainting via Clustered Sparsity and Microlocal Analysis
(Submitted on 12 Jun 2012)
Recently, compressed sensing techniques in combination with both wavelet and directional representation systems have been very effectively applied to the problem of image inpainting. However, a mathematical analysis of these techniques which reveals the underlying geometrical content is completely missing. In this paper, we provide the first comprehensive analysis in the continuum domain utilizing the novel concept of clustered sparsity, which besides leading to asymptotic error bounds also makes the superior behavior of directional representation systems over wavelets precise. First, we propose an abstract model for problems of data recovery and derive error bounds for two different recovery schemes, namely l1 minimization and thresholding. Second, we set up a microlocal model for an image governed by edges with a particular focus on seismic data as well as a mask to model the missing data. Applying the abstract estimate in the case of wavelets and of shearlets we prove that - provided the size of the missing part is comparable to the size of the analyzing functions - asymptotically precise inpainting can be obtained. Finally, we show that shearlets can fill strictly larger gaps than wavelets.
PRISMA: PRoximal Iterative SMoothing Algorithm
(Submitted on 11 Jun 2012)
Motivated by learning problems including max-norm regularized matrix completion and clustering, robust PCA and basis pursuit, we propose a novel optimization algorithm for minimizing a convex objective which decomposes into three parts: a smooth part, a simple non-smooth Lipschitz part, and a simple non-smooth non-Lipschitz part. Our algorithm combines the methodology of forward-backward splitting, smoothing, and accelerated proximal methods.
Communications-Inspired Projection Design with Application to Compressive Sensing
(Submitted on 9 Jun 2012)
We consider the recovery of an underlying signal x \in C^m based on projection measurements of the form y=Mx+w, where y \in C^l and w is measurement noise; we are interested in the case l < m. It is assumed that the signal model p(x) is known, and w CN(w;0,S_w), for known S_W. The objective is to design a projection matrix M \in C^(l x m) to maximize key information-theoretic quantities with operational significance, including the mutual information between the signal and the projections I(x;y) or the Renyi entropy of the projections h_a(y) (Shannon entropy is a special case). By capitalizing on explicit characterizations of the gradients of the information measures with respect to the projections matrix, where we also partially extend the well-known results of Palomar and Verdu from the mutual information to the Renyi entropy domain, we unveil the key operations carried out by the optimal projections designs: mode exposure and mode alignment. Experiments are considered for the case of compressive sensing (CS) applied to imagery. In this context, we provide a demonstration of the performance improvement possible through the application of the novel projection designs in relation to conventional ones, as well as justification for a fast online projections design method with which state-of-the-art adaptive CS signal recovery is achieved.
Dynamic Iterative Pursuit
(Submitted on 12 Jun 2012)
For compressive sensing of dynamic sparse signals, we develop an iterative pursuit algorithm. A dynamic sparse signal process is characterized by varying sparsity patterns over time/space. For such signals, the developed algorithm is able to incorporate sequential predictions, thereby providing better compressive sensing recovery performance, but not at the cost of high complexity. Through experimental evaluations, we observe that the new algorithm exhibits a graceful degradation at deteriorating signal conditions while capable of yielding substantial performance gains as conditions improve.
Sparse Distributed Learning Based on Diffusion Adaptation
(Submitted on 14 Jun 2012)
This article proposes diffusion LMS techniques for distributed estimation over adaptive networks that are able to exploit sparsity in the underlying system model. The approach relies on convex regularization, common in compressive sensing, to enhance the detection of sparsity via a diffusive process over the network. The resulting algorithms endow networks with learning abilities and allow them to learn the sparse structure from the incoming data in real-time, and also to track variations in the sparsity of the model. We provide convergence and mean-square performance analysis of the proposed method and show under what conditions it outperforms the unregularized diffusion version. We also show how to adaptively select the regularization parameter. Simulation results illustrate the advantage of the proposed filters for sparse data recovery.
Compressive neural representation of sparse, high-dimensional probabilities
(Submitted on 8 Jun 2012)
This paper shows how sparse, high-dimensional probability distributions could be represented by neurons with exponential compression. The representation is a novel application of compressive sensing to sparse probability distributions rather than to the usual sparse signals. The compressive measurements correspond to expected values of nonlinear functions of the probabilistically distributed variables. When these expected values are estimated by sampling, the quality of the compressed representation is limited only by the quality of sampling. Since the compression preserves the geometric structure of the space of sparse probability distributions, probabilistic computation can be performed in the compressed domain. Interestingly, functions satisfying the requirements of compressive sensing can be implemented as simple perceptrons. If we use perceptrons as a simple model of feedforward computation by neurons, these results show that the mean activity of a relatively small number of neurons can accurately represent a high-dimensional joint distribution implicitly, even without accounting for any noise correlations. This comprises a novel hypothesis for how neurons could encode probabilities in the brain.
Abstract: We propose a novel method as called compressed sensing with linear-in-wavenumber sampling (k-linear CS) to retrieve image for spectral domain optical coherence tomography (SD-OCT). An array of points that is evenly spaced in wavenumber domain is sampled from an original interferogram by a pre-set k-linear mask. Then the compressed sensing based on l1 norm minimization is applied on these points to reconstruct an A-scan data. To get an OCT image this method uses less than 20% of the total data as required in typical process and gets rid of the spectral calibration with numerical interpolation in traditional CS-OCT. Therefore k-linear CS is favorable for high speed imaging. It is demonstrated that the k-linear CS has the same axial resolution performance with ~30dB higher signal-to-noise ratio (SNR) as compared with the numerical interpolation. Imaging of bio-tissue by SD-OCT with k-linear CS is also demonstrated.DPCM for Quantized Block-Based Compressed Sensing of Images by Sungkwang Mun and James Fowler. The abstract:reads:
Differential pulse-code modulation is coupled with uniform scalar quantization to provide block-based quantized compressed sensing of images. Experimental results demonstrate significant improvement in rate-distortion performance as compared scalar quantization used alone in several block-based compressed-sensing reconstruction algorithms. Additionally, rate-distortion performance superior to that of alternative quantized-compressed-sensing techniques relying on optimized quantization or reconstruction is observed.
The BCS-SPL—Block Compressed Sensing with Smooth Projected Landweber Reconstruction website is here.
A COMPRESSIVE PHASE-LOCKED LOOP by Stephen R. Schnelle, J. P. Slavinsky, Petros T. Boufounos, Mark A. Davenport, Richard G. Baraniuk. The abstract reads:
We develop a new method for tracking narrowband signals acquired via compressive sensing. The compressive sensing phase-locked loop (CS-PLL) enables one to track oscillating signals in very large bandwidths using sub-Nyquist sampling. A key feature of the approach is the fact that we perform the frequency tracking directly on the compressive measurements without ever recovering the signal. The CS-PLL has a wide variety of potential applications, including communications, phase tracking, and robust control.
Estimation of missing RTTs in computer networks: Matrix completion vs compressed sensing by Ziqian Dong, Santhanakrishnan Anand, Rajarathnam Chandramouli
We estimate the missing round trip time (RTT) measurements in computer networks using doubly non-negative (DN) matrix completion and compressed sensing. The major contributions of this paper are the following: (i) an iterative DN matrix completion that minimizes the mean square estimation error; (ii) mathematical conditions for the convergence of the algorithm; (iii) systematic and detailed experimental comparison of DN matrix completion and compressed sensing for estimating missing RTT estimation in computer networks. To our knowledge, this is the first work that compares the pros and cons of compressed sensing and DN matrix completion for RTT estimation using actual Internet measurement data. Results indicate that compressed sensing provides better estimation in networks with sporadic missing values while DN completion of matrices is more suitable for estimation in networks which miss blocks of measurements. Our proposed DN matrix completion method is one of the first approaches to matrix completion, that minimizes the estimation error.
Energy-efficient collaborative scheme for compressed sensing-based spectrum detection in cognitive radio networks
An, Chunyan
Due to the potential detection error caused by information loss in sampling process, collaborative scheme is especially important for compressed sensing-based spectrum detection to improve the detection accuracy. In this paper, a novel energy-efficient low-complexity collaborative scheme is proposed for cognitive radio networks. In the proposed scheme, based on the prediction results of signal sparsity level by Lempel-Ziv-based prediction algorithm, the number of detection devices for spectrum detection is evaluated with the aim of minimizing the objective function, which takes into account both the detection accuracy and energy consumption. Finally, extensive simulation results are presented to show the effectiveness of our proposed collaborative scheme by comparing with the existing ones.
Finally, there is an MS thesis at Chalmers
M.SC. THESIS: RECOVERY GUARANTEE AND RECONSTRUCTION ALGORITHMS FOR 1-BIT COMPRESSIVE SENSING
2012-06-12 10:00
Master thesis presentation by Amin Movahed.
Examiner: Giuseppe Durisi
Abstract:
Compressive sensing is an emerging method for signal acquisition in which the number of samples ensuring exact reconstruction of the signal to be acquired is far less than the one in the conventional Nyquist sampling approach. In compressive sensing, the signal is acquired by means of few linear non-adaptive measurements, and then reconstructed by finding the sparsest solution via an l1-minimization.
In the classic compressive sensing setup, each measurement outcome is described by a real value. In practice, for further processing and storage purposes, often the real-valued measurements need to be converted to infinite precision numbers. 1-bit compressive sensing refers to the extreme case where the quantizer is a simple sign comparator and each measurement is represented using one bit only, i.e., +1 or -1.
Several algorithms have been introduced in the literature for solving efficiently the reconstruction problem in the 1-bit compressive sensing setting, e.g., renormalized fixed point iteration (RFPI) and binary iterative hard thresholding (BIHT). However, these algorithms cannot reconstruct the signal accurately when there is noise, i.e., bit flips, in the binary measurements. Adaptive outlier pursuit (AOP) is an algorithm which reconstructs the signal robustly against bit flips in the binary measurements. AOP requires the sparsity level of the signal to be reconstructed as an input. In many practical cases, however, the sparsity level of the signal is unknown and time variant.
In this thesis, we address reconstruction problem in 1-bit compressive sensing. We introduce a new algorithm for 1-bit compressive sensing which reconstructs the signal robustly from the noisy binary measurements. This new reconstruction algorithm does not require the sparsity level of the signal as an input. Therefore, our algorithm can be applied in the most practical scenarios in which the sparsity level of the signal is unknown.
In the classic compressive sensing setup, each measurement outcome is described by a real value. In practice, for further processing and storage purposes, often the real-valued measurements need to be converted to infinite precision numbers. 1-bit compressive sensing refers to the extreme case where the quantizer is a simple sign comparator and each measurement is represented using one bit only, i.e., +1 or -1.
Several algorithms have been introduced in the literature for solving efficiently the reconstruction problem in the 1-bit compressive sensing setting, e.g., renormalized fixed point iteration (RFPI) and binary iterative hard thresholding (BIHT). However, these algorithms cannot reconstruct the signal accurately when there is noise, i.e., bit flips, in the binary measurements. Adaptive outlier pursuit (AOP) is an algorithm which reconstructs the signal robustly against bit flips in the binary measurements. AOP requires the sparsity level of the signal to be reconstructed as an input. In many practical cases, however, the sparsity level of the signal is unknown and time variant.
In this thesis, we address reconstruction problem in 1-bit compressive sensing. We introduce a new algorithm for 1-bit compressive sensing which reconstructs the signal robustly from the noisy binary measurements. This new reconstruction algorithm does not require the sparsity level of the signal as an input. Therefore, our algorithm can be applied in the most practical scenarios in which the sparsity level of the signal is unknown.
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.
No comments:
Post a Comment