Uniform RIP Bounds for Recovery of Signals with Partial Support Information by Weighted $ \ell_{p} $-Minimization

Abstract

In this paper, we consider signal recovery in both noiseless and noisy cases via weighted ${\mathcal{l}}_{p}(0<p\le 1)$ minimization when some partial support information on the signals is available. The uniform sufficient condition based on restricted isometry property (RIP) of order tk for any given constant t>d ( $\ge 1$ is determined by the prior support information) guarantees the recovery of all k-sparse signals with partial support information. The new uniform RIP conditions extend the state-of-the-art results for weighted ${\mathcal{l}}_{p}$-minimization in the literature to a complete regime, which fill the gap for any given constant t>2d on the RIP parameter, and include the existing optimal conditions for the ${\mathcal{l}}_{p}$-minimization and the weighted ${\mathcal{l}}_{1}$-minimization as special cases.

Keywords

Compressed sensing / weighted $ \ell_{p} $ minimization / stable recovery / restricted isometry property

References

[1] R. Baraniuk, M. Davenport, R. DeVore, and M. Wakin, A simple proof of the restricted isometry property for random matrices, Constr. Approx., 28:253-263, 2008.

[2] R. V. Borries, C. Miosso, and C. Potes, Compressed sensing using prior information, in: 2nd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, 121-124, 2007.

[3] T. T. Cai and A. Zhang, Sharp RIP bound for sparse signal recovery and low-rank matrix recovery, Appl. Comput. Harmon. Anal., 35:74-93, 2013.

[4] T. T. Cai and A. Zhang, Sparse representation of a polytope and recovery of sparse signals and low-rank matrices, IEEE Trans. Inf. Theory, 60:122-132, 2014.

[5] E. J. Candès, J. Romberg, and T. Tao, Stable signal recovery from incomplete and inaccurate measurements, Comm. Pure Appl. Math., 59:1207-1223, 2006.

[6] B. Chen, and A. Wan, General RIP bounds of ${\delta }_{tk}$ for sparse signal recovery by ${\mathcal{l}}_{p}$ minimization. Neurocomputing, 363:306-312, 2019.

[7] W. Chen and Y. Li, Recovery of signals under the condition on RIC and ROC via prior support information, Appl. Comput. Harmon. Anal., 46:417-430, 2019.

[8] W. Chen, Y. Li, and G. Wu, Recovery of signals under the high order RIP condition via prior support information, Signal Process., 153:83-94, 2018.

[9] M. P. Friedlander, H. Mansour, R. Saab, and O. Yilmaz, Recoverying compressively sampled signals using partial support information, IEEE Trans. Inf. Theory, 58(2):1122-1134, 2012.

[10] H. Ge, W. Chen, and M.K. Ng, New RIP bounds for recovery of sparse signals with partial support information via weighted ${\mathcal{l}}_{p}$-minimization, IEEE Trans. Inf. Theory, 66:3914-3928, 2020.

[11] N. Ghadermarzy, H. Mansour, and O. Yilmaz, Non-convex compressed sensing using partial support information, Sampl. Theory Signal Image Process., 13:251-272, 2014.

[12] S. He, Y. Wang, J. Wang, and Z. Xu, Block-sparse compressed sensing with partially known signal support via non-convex minimisation, IET Signal Process., 10:717-723, 2016.

[13] T. Ince, A. Nacaroglu, and N. Watsuji, Nonconvex compressed sensing with partially known signal support, Signal Process., 93(1):338-344, 2013.

[14] L. Jacques, A short note compressed sensing with partially known signal support, Signal Process., 90:3308-3312, 2010.

[15] M. A. Khajehnejad, W. Xu, A. S. Avestimehr, and B. Hassibi, Weighted ${\mathcal{l}}_{1}$-minimization for sparse recovery with prior information, in: IEEE International Symposium on Information Theory, 483-487, 2009.

[16] W. Lu and N. Vaswani, Exact reconstruction conditions and error bounds for regularized modified basis pursuit, in:Conference Record of the Forty Fourth Asilomar Conference on Signals, Systems and Computers, 763-767, 2010.

[17] D. Needell R. Saab, and T. Woolf, Weighted ${\mathcal{l}}_{1}$-minimization for sparse recovery under arbitrary prior information, Information and Inference: A Journal of the IMA, 6(3):284-309, 2017.

[18] A. A. Saleh, F. Alajaji, and W. Y. Chan, Compressed sensing with non-Gaussian noise and partial support information, IEEE Signal Process. Lett., 20:1703-1707, 2015.

[19] N. Vaswani and W. Lu, Modified-CS: Modifying compressive sensing for problems with partially known support, in: IEEE International Symposium on Information Theory, 488-492, 2009.

[20] N. Vaswani and W. Lu, Modified-CS: Modifying compressive sensing for problems with partially known support, IEEE Trans. Signal Process., 58:4595-4607, 2010.

[21] A. Wan, Uniform RIP conditions for recovery of sparse signals by $\ell_{p}(0<p \leq 1)$ minimization, IEEE Trans. Signal Process., 68:5379-5394, 2020.

[22] G. Xu and Z. Xu, On the $ \ell_{1} $-norm invariant convex k-sparse decomposition of signals, J. Oper. Res. Soc. China, 1:537-541, 2013.

[23] R. Zhang and S. Li, Optimal RIP bounds for Sparse signals recovery via $ \ell_{p} $-minimization, Appl. Comput. Harmon. Anal., 47:566-584, 2019.