A NEW SUFFICIENT CONDITION FOR SPARSE RECOVERY WITH MULTIPLE ORTHOGONAL LEAST SQUARES

doi:10.1007/s10473-022-0308-4

数学物理学报(英文版) ›› 2022, Vol. 42 ›› Issue (3): 941-956.doi: 10.1007/s10473-022-0308-4

A NEW SUFFICIENT CONDITION FOR SPARSE RECOVERY WITH MULTIPLE ORTHOGONAL LEAST SQUARES

李海锋, 张静

Henan Engineering Laboratory for Big Data Statistical Analysis and Optimal Control, College of Mathematics and Information Science, Henan Normal University, Xinxiang, 453007, China

收稿日期:2020-09-02 修回日期:2021-05-28 发布日期:2022-06-24
通讯作者: Haifeng Li,E-mail:lihaifengxx@126.com E-mail:lihaifengxx@126.com
基金资助:
This work was partially supported by the National Natural Science Foundation of China (61907014, 11871248, 11701410, 61901160), Youth Science Foundation of Henan Normal University (2019QK03).

A NEW SUFFICIENT CONDITION FOR SPARSE RECOVERY WITH MULTIPLE ORTHOGONAL LEAST SQUARES

Haifeng LI, Jing ZHANG

Henan Engineering Laboratory for Big Data Statistical Analysis and Optimal Control, College of Mathematics and Information Science, Henan Normal University, Xinxiang, 453007, China

Received:2020-09-02 Revised:2021-05-28 Published:2022-06-24
Contact: Haifeng Li,E-mail:lihaifengxx@126.com E-mail:lihaifengxx@126.com
Supported by:
This work was partially supported by the National Natural Science Foundation of China (61907014, 11871248, 11701410, 61901160), Youth Science Foundation of Henan Normal University (2019QK03).

摘要/Abstract

摘要： A greedy algorithm used for the recovery of sparse signals, multiple orthogonal least squares (MOLS) have recently attracted quite a big of attention. In this paper, we consider the number of iterations required for the MOLS algorithm for recovery of a $K$-sparse signal $\mathbf{x}\in\mathbb{R}^n$. We show that MOLS provides stable reconstruction of all $K$-sparse signals $\mathbf{x}$ from $\mathbf{y}=\mathbf{A}\mathbf{x}+\mathbf{w}$ in $\lceil\frac{6K}{M}\rceil$ iterations when the matrix $\mathbf{A}$ satisfies the restricted isometry property (RIP) with isometry constant $\delta_{7K}\leq0.094$. Compared with the existing results, our sufficient condition is not related to the sparsity level $K$.

关键词: Sparse signal recovery, multiple orthogonal least squares (MOLS), sufficient condition, restricted isometry property (RIP)

Abstract: A greedy algorithm used for the recovery of sparse signals, multiple orthogonal least squares (MOLS) have recently attracted quite a big of attention. In this paper, we consider the number of iterations required for the MOLS algorithm for recovery of a $K$-sparse signal $\mathbf{x}\in\mathbb{R}^n$. We show that MOLS provides stable reconstruction of all $K$-sparse signals $\mathbf{x}$ from $\mathbf{y}=\mathbf{A}\mathbf{x}+\mathbf{w}$ in $\lceil\frac{6K}{M}\rceil$ iterations when the matrix $\mathbf{A}$ satisfies the restricted isometry property (RIP) with isometry constant $\delta_{7K}\leq0.094$. Compared with the existing results, our sufficient condition is not related to the sparsity level $K$.

Key words: Sparse signal recovery, multiple orthogonal least squares (MOLS), sufficient condition, restricted isometry property (RIP)

中图分类号:

94A12

李海锋, 张静. A NEW SUFFICIENT CONDITION FOR SPARSE RECOVERY WITH MULTIPLE ORTHOGONAL LEAST SQUARES[J]. 数学物理学报(英文版), 2022, 42(3): 941-956.

Haifeng LI, Jing ZHANG. A NEW SUFFICIENT CONDITION FOR SPARSE RECOVERY WITH MULTIPLE ORTHOGONAL LEAST SQUARES[J]. Acta mathematica scientia,Series B, 2022, 42(3): 941-956.

参考文献

[1] Chen S, Billings S, Luo W. Orthogonal least squares methods and their application to non-linear system identification. Int J Control, 1989, 50(5):1873-1896
[2] Foucart S. Stability and robustness of weak orthogonal matching pursuits//Recent Adv Harmonic Anal and App. Springer, 2013:395-405
[3] Geng P, Chen W, Ge H. Perturbation analysis of orthogonal least squares. Canadian Mathematical Bulletin, 2019, 62(4):780-797
[4] Herzet C, Soussen C, Idier J, Gribonval R. Exact recovery conditions for sparse representations with partial support information. IEEE Trans Inform Theory, 2013, 59(11):7509-7524
[5] Herzet C, Drémeau A, Soussen C. Relaxed recovery conditions for OMP/OLS by exploiting both coherence and decay. IEEE Transactions on Information Theory, 2015, 62(1):459-470
[6] Wang J, Li P. Recovery of sparse signals using multiple orthogonal least squares. IEEE Trans. Signal Process, 2017, 65(8):2049-2062
[7] Li H, Zhang J, Zou J. Improving the bound on the restricted isometry property constant in multiple orthogonal least squares. IET Signal Processing, 2018, 12(5):666-671
[8] Kim J, Shim B. A Near-Optimal Restricted Isometry Condition of Multiple Orthogonal Least Squares. IEEE Access, 2019, 7:46822-46830
[9] Wen J, Wang J, Zhang Q. Nearly optimal bounds for orthogonal least squares. IEEE Trans Signal Process, 2017, 65(20):5347-5356
[10] Chen W, Li Y. Stable recovery of signals with the high order D-RIP condition. Acta Matematica Scientia, 2016, 36(6):1721-1730
[11] Abdillahi-Ali D, Azzaout N, Guillin A, Le Mailloux G, Matsui T. Penalized least square in sparse setting with convex penalty and non Gaussian errors. Acta Matematica Scientia, 2021, 41(6):2198-2216
[12] Li H, Liu G. An improved analysis for support recovery with orthogonal matching pursuit under general perturbations. IEEE Access, 2018, 6:18856-18867
[13] Pati Y, Rezaiifar R, Krishnaprasad P. Orthogonal matching pursuit:Recursive function approximation with applications to wavelet decomposition//Proc 27th Annu. Asilomar Conf Signals, Systems, and Computers. IEEE, Pacific Grove, CA, 1993, 1:40-44
[14] Chen W, Ge H. A sharp recovery condition for block sparse signals by block orthogonal multi-matching pursuit. Science China Mathematics, 2017, 60(7):1325-1340
[15] Dan W, Wang R. Robustness of orthogonal matching pursuit under restricted isometry property. Science China Mathematics, 2014, 57(3):627-634
[16] Zhang T. Sparse recovery with orthogonal matching pursuit under RIP. IEEE Transactions on Information Theory, 2011, 57(9):6215-6221
[17] Wang J, Li P, Shim B. Exact recovery of sparse signals using orthogonal matching pursuit:How many iterations do we need?. IEEE Transactions on Signal Processing, 2016, 64(16):4194-4202
[18] Candes E, Tao T. Decoding by linear programming. IEEE Trans Inf Theory, 2005, 51(12):4203-4215
[19] Baraniuk R, Davenport M, DeVore R, Wakin M. A simple proof of the restricted isometry property for random matrices. Construct Approx, 2008, 28(3):253-263
[20] Blumensath T, Davies M. On the difference between orthogonal matching pursuit and orthogonal least squares//Technical Report. Southampton:University of Southampton, 2007. https://eprints.soton.ac.uk/142469/1/BDOMPvsOLS07.pdf.
[21] Soussen C, Gribonval R, Idier J, Herzet C. Joint k-step analysis of orthogonal matching pursuit and orthogonal least squares. IEEE Trans Inf Theory, 2013, 59(5):3158-3174
[22] Wang J, Kwon S, Li P, Shim B. Recovery of sparse signals via generalized orthogonal matching pursuit:A new analysis. IEEE Transactions on Signal Process, 2016, 64(4):1076-1089
[23] Kim J, Wang J, Nguyen L, Shim B. Joint sparse recovery using signal space matching pursuit. IEEE Transactions on Information Theory, 2020, 66(8):5072-5096
[24] Kim J, Wang J, Shim B. Optimal restricted isometry condition of normalized sampling matrices for exact sparse recovery with orthogonal least squares. IEEE Transaction on Signal Processing, 2021, 69(1):1521-1536

A NEW SUFFICIENT CONDITION FOR SPARSE RECOVERY WITH MULTIPLE ORTHOGONAL LEAST SQUARES

A NEW SUFFICIENT CONDITION FOR SPARSE RECOVERY WITH MULTIPLE ORTHOGONAL LEAST SQUARES

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

Metrics

本文评价

推荐阅读 0

[1]	周立芳. ON THE BOUNDEDNESS AND THE NORM OF A CLASS OF INTEGRAL OPERATORS[J]. 数学物理学报(英文版), 2015, 35(6): 1475-1482.
[2]	李永群, 王仙桃. A SUFFICIENT CONDITION OF CONVERGENCE FOR CLIFFORD CONTINUED FRACTIONS[J]. 数学物理学报(英文版), 2011, 31(1): 8-14.