Wednesday, February 20, 2013

Adaptive Outlier Pursuit: Robust 1-bit Compressive Sensing and Matrix Completion - implementation -

Tackling sparse noise in 1-bit compressive sensing and matrix completion, we have two implementations today, in the compressive sensing case, AOP is compared to BIHT while in the Matrix Completion case, it is compared to GRASTA and SpaRCS. Here they are: Robust 1-bit compressive sensing using adaptive outlier pursuit by Ming Yan, Yi YangStanley Osher. The abstract reads:
In compressive sensing (CS), the goal is to recover signals at reduced sample rate compared to the classic ShannonNyquist rate. However, the classic CS theory assumes the measurements to be real-valued and have infinite bit precision. The quantization of CS measurements has been studied recently and it has been shown that accurate and stable signal acquisition is possible even when each measurement is quantized to only one single bit. There are many algorithms proposed for 1- bit compressive sensing and they work well when there is no noise in the measurements, e.g., there are no sign flips, while the performance is worsened when there are a lot of sign flips in the measurements. In this paper, we propose a robust method for recovering signals from 1-bit measurements using adaptive outlier pursuit. This method will detect the positions where sign flips happen and recover the signals using “correct” measurements. Numerical experiments show the accuracy of sign flips detection and high performance of signal recovery for our algorithms compared with other algorithms.

Recovering a low-rank matrix from some of its linear measurements is a popular problem in many areas of science and engineering. One special case of it is the matrix completion problem, where we need to reconstruct a low-rank matrix from incomplete samples of its entries. A lot of efficient algorithms have been proposed to solve this problem and they perform well when Gaussian noise with a small variance is added to the given data. But they can not deal with the sparse random-valued noise in the measurements. In this paper, we propose a robust method for recovering the low-rank matrix with adaptive outlier pursuit when part of the measurements are damaged by outliers. This method will detect the positions where the data is completely ruined and recover the matrix using correct measurements. Numerical experiments show the accuracy of noise detection and high performance of matrix completion for our algorithms compared with other algorithms.
From the page:

Adaptive Outlier Pursuit

1-bit Compressive Sensing

1-bit compressive sensing was firstly introduced and studied by Boufounos and Baraniuk in 2008, and the framework is as follows:
 y=A(x):=mbox{sign}(Phi x)  
where A(cdot) is a mapping from mathbf{R}^N to the Boolean cube mathcal{B}^M:={-1,1}^M. We have to recover signals xin sum_K^*:={xin S^{N-1}:|x|_0leq K} where S^{N-1}:={xinmathbf{R}^N:|x|_2=1} is the unit hyper-sphere of dimension N. See more details about 1-bit compressive sensing, please go to http://dsp.rice.edu/1bitCS.
The implementations for both 1-bit compressive sensing and matrix completion can be downloaded from this page. All entries related to 1-bit compressive sensing in general are listed under thwe 1bit tag.

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.

No comments:

Printfriendly