Sparse Signal Reconstruction using Weight Point Algorithm
DOI:
https://doi.org/10.5614/itbj.ict.res.appl.2018.12.1.3Keywords:
compressive sampling, convex combination, convex polytope, sparse reconstruction, l1-norm, weight point.Abstract
In this paper we propose a new approach of the compressive sensing (CS) reconstruction problem based on a geometrical interpretation of l1-norm minimization. By taking a large l1-norm value at the initial step, the intersection of l1-norm and the constraint curves forms a convex polytope and by exploiting the fact that any convex combination of the polytope's vertexes gives a new point that has a smaller l1-norm, we are able to derive a new algorithm to solve the CS reconstruction problem. Compared to the greedy algorithm, this algorithm has better performance, especially in highly coherent environments. Compared to the convex optimization, the proposed algorithm has simpler computation requirements. We tested the capability of this algorithm in reconstructing a randomly down-sampled version of the Dow Jones Industrial Average (DJIA) index. The proposed algorithm achieved a good result but only works on real-valued signals.
Downloads
References
Dohono, D., Compressed Sensing, IEEE Transactions on Information Theory, 52(4), pp. 1289-1306, 2006.
Candes, E. & Wakin, M.B., Compressive Sampling, Proceedings of the International Congress of Mathematicians, 25(2), pp. 21-30, 2008.
Candes, E. & Tao, T., Decoding by Linear Programming, IEEE Transactions on Information Theory, 51(12), pp. 4203-4215, 2005.
Baraniuk, R., Compressive Sensing, IEEE Signal Processing Magazine, 24(4), pp. 118-121, Jul, 2007.
Donoho, D. & Stark, P. B., Uncertainty Principles and Signal Recovery, Siam J. Appl. Math., 49(3), pp. 906-931, Jun, 1989.
Chen, S. S., Donoho, D. & Saunders, M.A., Atomic Decomposition by Basis Pursuit, SIAM Review, Society for Industrial and Applied Mathematics, 43(1), pp. 129-159, 2001.
Mallat, S.G. & Zhang, Z., Matching Pursuits with Time-Frequency Dictionaries, IEEE Transactions on Signal Processing, 41(12), 1993.
Chen, Y., Huang, J. & He, C., High Resolution Direction-of-Arrival Estimation Based on Compressive Sensing with Noval Compression Matrix, IEEE International Conference on Signal Processing, Communication, and Computing, 2012.
Kim, J.M., Lee, O.K. & Ye, J.C., Compressive MUSIC: Revisiting the Link Between Compressive Sensing and Array Signal Processing, IEEE Transactions on Information Theory, 58(1), 2012.
Usman, K., Gunawan, H. & Suksmono, A.B., Uniform Non-Exhaustive Search on Sparse Reconstruction for Direction of Arrival Estimation, IEEE APWiBob, 2015.
Xenakia, A., Gerstoft, P. & Mosegaard, K., Compressive Beamforming, J. Acoust. Soc. America, 136(1), Jul, 2014.
Edelmann, G.F. & Gaumond, C.F., Beamforming using Compressive Sensing, J. Acoust. Soc. America, 130(4), 2011.
Lustig, M., Donoho, D., Santos, J. & Pauly, J., Compressed Sensing MRI, IEEE Signal Processing Magazine, 25(2), pp. 72-82, 2008.
Suksmono, A. B., Interpolation of PSF based on Compressive Sampling and Its Application in Weak Lensing Survey, Monthly Notices of the Royal Astronomical Society, 443(1), pp.919-926, 2014.
Wahidah, I., Hendrawan, T., Mengko, T.L.R. & Suksmono, A.B. Parameter Estimation for Coefficient Thresholding in Block-based Compressive Video Coding, International Journal of Imaging and Robotics, 15(3), pp. 66-72, 2015.
Elad, M. & Bruckstein A.M., A Generalized Uncertainty Principle and Sparse Representation in Pairs of Bases, IEEE Transactions on Information Theory, 48(9), pp. 2558-2567, 2002.
Donoho. D.L. & Huo, X., Uncertainty Principles and Ideal Atomic Decomposition, IEEE Transactions on Information Theory, 47(7), 2001.
Candes, E. & Romberg, J., l1-Magic: Recovery of Sparse Signals via Convex Programming, Retrieved on 2 November 2016 from http://users.ece.gatech.edu/~justin/l1magic/, 2005.
Boyd, S. & Vandenberghe, L., Convex Optimization, Cambridge University Press, 2004.
Chen, S., Billings, S.A. & Luo, W., Orthogonal Least Squares Methods and Their Application to Non-linear System Identification, International Journal on Control, 50(5), pp. 1873-1896, 1989.
Pati, Y.C., Rezahfar, R. & Krishnaprasad, P.S., Orthogonal Matching Pursuit: Recursive Function Approximation with Applications to Wavelet Decomposition, Annual Asilomar Conference on Signals Systems and Computers, 1(3), 1993.
Needell, D. & Vershynin, R., Signal Recovery from Incomplete and Inaccurate Measurements Via Regularized Orthogonal Matching Pursuit, IEEE Journal of Selected Topics in Signal Processing, 4(2), pp. 310-316, 2010.
Donoho, D., Tsaig, Y., Drori, I. & Starck, J.L., Sparse Solution of underdetermined Linear Equations by Stagewise Orthogonal Matching Pursuit (StOMP), IEEE Transactions on Information Theory, 58(2), 2012
Needell, D. & Tropp, J.A., CoSaMP: Iterative Signal recovery from Incomplete and Inaccurate Samples, Appl. Comput. Harmon. Anal., 26, pp. 301-321, 2008.
Tropp, J.A. & Gilbert, A.C., Signal Recovery from Random Measurements Via Orthogonal Matching Pursuit, IEEE Transactions on Information Theory, 53(12), pp. 4655-4666, 2007.
DeVore, R.A. & Temlyakov, V.N., Some Remarks on Greedy Algorithms, Advances in Computational Mathematics, 5, pp. 173-187, 1996.
Cohen, A., Approximation by Greedy Algorithms, Siam News, 40(8), 2007.
Golub, G.H. & Loan, C.V., Matrix Computation, 3rd Edition, The Johns Hopkins University Press, Baltimore, United States, 1996.
Suksmono, A.B., Reconstruction of Fractional Brownian Motion Signals From Its Sparse Samples Based on Compressive Sampling, ICEEI, Bandung, Indonesia, July 2011.
