Here is an extension of the previous SMP code available here. The new algorithm called SSMP is introduced in Sequential Sparse Matching Pursuit by Piotr Indyk and Radu Berinde. The abstract reads:We propose a new algorithm, called Sequential Sparse Matching Pursuit (SSMP), for solving sparse recovery problems. The algorithm provably recovers a k-sparse approximation to an arbitrary n-dimensional signal vector x from only O(k log(n/k)) linear measurements of x. The recovery process takes time that is only near-linear in n. Preliminary experiments indicate that the algorithm works well on synthetic and image data, with the recovery quality often outperforming that of more complex algorithms, such as l_1 minimization.
Piotr just lets me know that it should be available soon. Thanks Piotr ! On the topic of blind deconvolution we talked about before, here is Compressed Blind De-convolution by Venkatesh Saligrama, Manqi Zhao. The abstract reads:
Suppose the signal x is realized by driving a k-sparse signal u through an arbitrary unknown stable discrete-linear time invariant system H. These types of processes arise naturally in Reflection Seismology. In this paper we are interested in several problems: (a) Blind-Deconvolution: Can we recover both the filter $H$ and the sparse signal $u$ from noisy measurements? (b) Compressive Sensing: Is x compressible in the conventional sense of compressed sensing? Namely, can x, u and H be reconstructed from a sparse set of measurements. We develop novel L1 minimization methods to solve both cases and establish sufficient conditions for exact recovery for the case when the unknown system H is auto-regressive (i.e. all pole) of a known order. In the compressed sensing/sampling setting it turns out that both H and x can be reconstructed from O(k log(n)) measurements under certain technical conditions on the support structure of u. Our main idea is to pass x through a linear time invariant system G and collect O(k log(n)) sequential measurements. The filter G is chosen suitably, namely, its associated Toeplitz matrix satisfies the RIP property. We develop a novel LP optimization algorithm and show that both the unknown filter H and the sparse input u can be reliably estimated.
I tried reimplementing this algorithm(SSMP) from SMP package. My results have some significant difference to the authors'. Particularly, My codes gave better in number of measurement but the recovery time was worse.
ReplyDeletehere my resutls:
http://i193.photobucket.com/albums/z55/ngocminhnguyen/SMP_GPRSvsMySSMP.png
http://i193.photobucket.com/albums/z55/ngocminhnguyen/sparse_experiments-ssmp-countmin8-p.jpg
- Another problem I'm concerning now is with a sparse matrix A, how can it measures natural images if I intend use model single pixel cameras ?
Dear Ngoc,
ReplyDeletehave you tried to contact the authors ?
As for your second question, I am not sure I understand it. Can oyu be more precise ?
Cheers,
Igor.
I has sent prof. Indyk my question but not be replied.
ReplyDeleteIn the second question, My mean is:
To Gaussian/Bernoulli Random Measurement Matrix(MM), we can catch sparse components of signal x and use linear or convex programming or greedy algorithms to recover it. Otherwise,in case of signal is sparse in some basis i.e. Fourier/Wavelets basis matrix B,so we need to change basis. But the size of MM is inefficient. Then, we change to Sparse Matrix A with an expectation that with a neighbor matrix built from expander graph, we can reduce storage.
However, in my understand, if we use sparse matrix to catch signal which is sparse in some basis, it requires we need to store A*B^(-1).Is that right ?
Now we turn to model of Single Pixel Camera. In my imagine, it used Bernoulli matrix to control DMD flip m times to get m measurements of real images. Each flip correspond one line of Bernoulli matrix. But I don't know where the component of basis matrix are stored ?
I hope you give me a good explain, thank you !