Paper Info
Title
A derandomization approach to recovering bandlimited signals across a wide range of random sampling rates.
Abstract
Reconstructing bandlimited functions from random sampling is an important problem in signal processing. Strohmer and Vershynin obtained good results for this problem by using a randomized version of the Kaczmarz algorithm (RK) and assigning to every equation a probability weight proportional to the average distance of the sample from its two nearest neighbors. However, their results are valid only for moderate to high sampling rates; in practice, it may not always be possible to obtain many samples. Experiments show that the number of projections required by RK and other Kaczmarz variants rises seemingly exponentially when the equations/variables ratio (EVR) falls below 5. CGMN, which is a CG acceleration of Kaczmarz, provides very good results for low values of EVR and it is much better than CGNR and CGNE. A derandomization method, based on an extension of the bit-reversal permutation, is combined with the weights and shown to improve the performance of CGMN and the regular (cyclic) Kaczmarz, which even outperforms RK. A byproduct of our results is the finding that signals composed mainly of high-frequency components are easier to recover.
Year
DOI
Venue
2018
https://doi.org/10.1007/s11075-017-0356-3
Numerical Algorithms
Keywords
Field
DocType
Bandlimited functions,Bit-reversal,CGMN,Derandomization,Extended bit-reversal,Low sampling rates,Randomized Kaczmarz,RK,Signal processing
Signal processing,Mathematical optimization,Bandlimiting,Permutation,Algorithm,Acceleration,Sampling (statistics),Mathematics,Exponential growth
Journal
Volume
Issue
ISSN
77
4
1017-1398
Citations 
PageRank 
References 
0
0.34
7
Authors
1
Name
Order
Citations
PageRank
Dan Gordon121021.44