Geodesic
Perturbation Analysis of Orthogonal Least Squares
Canadian mathematical bulletin, Tome 62 (2019) no. 4, pp. 780-797

Voir la notice de l'article provenant de la source Cambridge University Press

The Orthogonal Least Squares (OLS) algorithm is an efficient sparse recovery algorithm that has received much attention in recent years. On one hand, this paper considers that the OLS algorithm recovers the supports of sparse signals in the noisy case. We show that the OLS algorithm exactly recovers the support of $K$-sparse signal $\boldsymbol{x}$ from $\boldsymbol{y}=\boldsymbol{\unicode[STIX]{x1D6F7}}\boldsymbol{x}+\boldsymbol{e}$ in $K$ iterations, provided that the sensing matrix $\boldsymbol{\unicode[STIX]{x1D6F7}}$ satisfies the restricted isometry property (RIP) with restricted isometry constant (RIC) $\unicode[STIX]{x1D6FF}_{K+1}<1/\sqrt{K+1}$, and the minimum magnitude of the nonzero elements of $\boldsymbol{x}$ satisfies some constraint. On the other hand, this paper demonstrates that the OLS algorithm exactly recovers the support of the best $K$-term approximation of an almost sparse signal $\boldsymbol{x}$ in the general perturbations case, which means both $\boldsymbol{y}$ and $\boldsymbol{\unicode[STIX]{x1D6F7}}$ are perturbed. We show that the support of the best $K$-term approximation of $\boldsymbol{x}$ can be recovered under reasonable conditions based on the restricted isometry property (RIP).
DOI : 10.4153/S0008439519000134
Mots-clés : orthogonal least square (OLS), sparse signal, restricted isometry property (RIP), general perturbation 
Geng, Pengbo; Chen, Wengu; Ge, Huanmin. Perturbation Analysis of Orthogonal Least Squares. Canadian mathematical bulletin, Tome 62 (2019) no. 4, pp. 780-797. doi: 10.4153/S0008439519000134
@article{10_4153_S0008439519000134,
     author = {Geng, Pengbo and Chen, Wengu and Ge, Huanmin},
     title = {Perturbation {Analysis} of {Orthogonal} {Least} {Squares}},
     journal = {Canadian mathematical bulletin},
     pages = {780--797},
     year = {2019},
     volume = {62},
     number = {4},
     doi = {10.4153/S0008439519000134},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/S0008439519000134/}
}
TY  - JOUR
AU  - Geng, Pengbo
AU  - Chen, Wengu
AU  - Ge, Huanmin
TI  - Perturbation Analysis of Orthogonal Least Squares
JO  - Canadian mathematical bulletin
PY  - 2019
SP  - 780
EP  - 797
VL  - 62
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.4153/S0008439519000134/
DO  - 10.4153/S0008439519000134
ID  - 10_4153_S0008439519000134
ER  - 
%0 Journal Article
%A Geng, Pengbo
%A Chen, Wengu
%A Ge, Huanmin
%T Perturbation Analysis of Orthogonal Least Squares
%J Canadian mathematical bulletin
%D 2019
%P 780-797
%V 62
%N 4
%U http://geodesic.mathdoc.fr/articles/10.4153/S0008439519000134/
%R 10.4153/S0008439519000134
%F 10_4153_S0008439519000134

[1] Blumensath, T. and Davies, M., Compressed sensing and source separation . In: Int. Conf. on Independent Component Analysis and Signal Separation , Springer-Verlag Berlin, Heidelberg, 2007, pp. 341–348. Google Scholar

[2] Candès, E. J. and Tao, T., Decoding by linear programming . IEEE Trans. Inform. Theory 51(2005), no. 12, 4203–4215. Google Scholar | DOI

[3] Candès, E. J. and Tao, T., Near-optimal signal recovery from random projections: Universal encoding strategies . IEEE Trans. Inform. Theory 52(2006), no. 12, 5406–5425. Google Scholar | DOI

[4] Candès, E. J., Romberg, J., and Tao, T., Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information . IEEE Trans. Inform. Theory 52(2006), no. 2, 489–509. Google Scholar | DOI

[5] Chen, S., Billings, S. A., and Luo, W., Orthogonal least squares methods and their application to non-linear system identification . Internat. J. Control. 50(1989), no. 5, 1873–1896. Google Scholar | DOI

[6] Chen, S. S., Donoho, D. L., and Saunders, M. A., Atomic decomposition by basis pursuit . SIAM J. Sci. Comput. 20(1998), 33–61. Google Scholar | DOI

[7] Chen, W. and Ge, H., A sharp bound on RIC in generalized orthogonal maching pursuit . Canad. Math. Bull. 61(2017), no. 1, 40–54. Google Scholar | DOI

[8] Ding, J., Chen, L., and Gu, Y., Perturbation analysis of orthogonal matching pursuit . IEEE Trans. Signal Process. 61(2013), no. 2, 398–410. Google Scholar | DOI

[9] Donoho, D. L., Compressed sensing . IEEE Trans. Inform. Theory 56(2006), no. 4, 1289–1306. Google Scholar | DOI

[10] Fannjiang, A. C., Strohmer, T., and Yan, P., Compressed remote sensing of sparse objects . SIAM J. Imaging Sci. 3(2010), no. 3, 595–618. Google Scholar | DOI

[11] Foucart, S., Stability and robustness of weak orthogonal matching pursuits . In: Recent advances in harmonic analysis and applications , Springer Proc. Math. Stat., 25, Springer, New York, 2013. Google Scholar | DOI

[12] Herman, M. A. and Needell, D., Mixed operators in compressed sensing . In: Proceedings IEEE 44th Ann. Conf. Inf. Sci. Syst. , Princeton, NJ, 2010, pp. 1–6. Google Scholar

[13] Herman, M. A. and Strohmer, T., High-resolution radar via compressed sensing . IEEE Trans. Signal Process. 57(2009), no. 6, 2275–2284. Google Scholar | DOI

[14] Herman, M. A. and Strohmer, T., General deviants: An analysis of perturbations in compressed sensing . IEEE J. Sel. Topics Signal Process. 4(2010), no. 2, 342–349. Google Scholar

[15] Herzet, C., Soussen, C., Idier, J., and Gribonval, R., Exact recovery conditions for sparse representations with partial support information . IEEE Trans. Inform. Theory 59(2013), no. 11, 7509–7524. Google Scholar

[16] Li, H. and Liu, G., An improved analysis for support recovery with orthogonal matching pursuit under general perturbations . IEEE Access. 99(2018), no. 6, 18856–18867. Google Scholar

[17] Mo, Q., A sharp restricted isometry constant bound of orthogonal matching pursuit. 2015. arxiv:1501.01708 Google Scholar

[18] Needell, D. and Troop, J. A., CoSaMP: Iterative signal recovery from incomplete and inaccurate samples . Appl. Comput. Harmon. Anal. 26(2009), no. 3, 301–321. Google Scholar | DOI

[19] Shen, Y., Li, B., Pan, W., and Li, J., Analysis of generalized orthogonal matching pursuit using restricted constant . Electron. Lett. 50(2014), no. 14, 1020–1022. Google Scholar

[20] Soussen, C., Gribonval, R., Idier, J., and Herzet, C., Joint k-step analysis of orthogonal matching pursuit and orthogonal least squares . IEEE Trans. Inform. Theory 59(2013), no. 5, 3158–3174. Google Scholar | DOI

[21] Tropp, J. A. and Gilbert, A. C., Signal recovery from random measurements via orthogonal matching pursuit . IEEE Trans. Inform. Theory 53(2007), no. 12, 4655–4666. Google Scholar | DOI

[22] Wang, J., Support recovery With orthogonal matching pursuit in the presence of noise . IEEE Trans. Signal Process. 63(2015), no. 21, 5868–5877. Google Scholar | DOI

[23] Wang, J., Kwon, S., Li, P, and Shim, B., Recovery of sparse signals via generalized orthogonal matching pursuit: a new analysis . IEEE Trans. Signal Process. 64(2015), no. 4, 1076–1089. Google Scholar | DOI

[24] Wang, J., Kwon, S., and Shim, B., Generalized orthogonal matching pursuit . IEEE Trans. Singnal Process. 60(2012), no. 12, 6202–6216. Google Scholar

[25] Wang, J. and Li, P., Recovery of sparse signals using multiple orthogonal least squares . IEEE Trans. Signal Process. 65(2017), no. 8, 2049–2062. Google Scholar | DOI

[26] Wang, J. and Shim, B., On the recovery limit of sparse signals using orthogonal matching pursuit . IEEE Trans. Signal Process. 60(2012), no. 9, 4973–4976. Google Scholar | DOI

[27] Wen, J., Zhou, Z., Li, D., and Tang, X., A novel sufficient condition for generalized orthogonal matching pursuit . IEEE Comm. Lett. 21(2017), no. 4, 805–808. Google Scholar

[28] Wen, J., Zhou, Z., Wang, J., Tang, X., and Mo, Q., A sharp condition for exact support recovery of sparse signals with orthogonal matching pursuit . IEEE Trans. Signal Process. 65(2017), 1370–1382. Google Scholar | DOI

[29] Wen, J., Wang, J., and Zhang, Q., Nearly optimal bounds for orthogonal least squares . IEEE Trans. Signal Proces. 65(2017), no. 20, 5347–5356. Google Scholar | DOI

Cité par Sources :