# zbMATH — the first resource for mathematics

Greedy subspace pursuit for joint sparse recovery. (English) Zbl 07042028
Summary: In the joint sparse recovery, where the objective is to recover a signal matrix $$X_0$$ of size $$n \times l$$ or a set $$\Omega$$ of its nonzero row indices from incomplete measurements, subspace-based greedy algorithms improving MUSIC such as subspace-augmented MUSIC and sequential compressive MUSIC have been proposed to improve the reconstruction performance of $$X_0$$ and $$\Omega$$ with a computational efficiency even when $$\mathrm{rank}(X_0) \leq k := | \Omega |$$. However, the main limitation of the MUSIC-like methods is that they most likely fail to recover the signal when a partial support estimate of $$k - \mathrm{rank}(X_0)$$ indices for their input is not fully correct. We proposed a computationally efficient algorithm called two-stage iterative method to detect the remained support (T-IDRS), its special version termed by two-stage orthogonal subspace matching pursuit (TSMP), and its variant called TSMP with sparse Bayesian learning (TSML) by exploiting more than the sparsity $$k$$ to estimate the signal matrix. They improve on the MUSIC-like methods such that these are guaranteed to recover the signal and its support while the existing MUSIC-like methods will fail in the practically significant case of MMV when $$\mathrm{rank}(X_0) / k$$ is sufficiently small. Numerical simulations demonstrate that the proposed schemes have low complexities and most likely outperform other related methods. A condition of the minimum $$m$$ required for TSMP to recover the signal matrix is derived in the noiseless case to be applicable to a wide class of the sensing matrix.
##### MSC:
 94A12 Signal theory (characterization, reconstruction, filtering, etc.) 65F22 Ill-posedness and regularization problems in numerical linear algebra
SPGL1
Full Text:
##### References:
 [1] Donoho, D. L., Compressed sensing, IEEE Trans. Inform. Theory, 52, 4, 1289-1306, (2006) · Zbl 1288.94016 [2] Davies, M. E.; Eldar, Y. C., Rank awareness in joint sparse recovery, IEEE Trans. Inform. Theory, 58, 2, 1135-1146, (2012) · Zbl 1365.94175 [3] Eldar, Y. C.; Mishali, M., Robust recovery of signals from a structured union of subspaces, IEEE Trans. Inform. Theory, 55, 11, 5302-5316, (2009) · Zbl 1367.94087 [4] Eldar, Y. C.; Rauhut, H., Average case analysis of multichannel sparse recovery using convex relaxation, IEEE Trans. Inform. Theory, 56, 1, 505-519, (2010) · Zbl 1366.94095 [5] Foucart, S., Recovering jointly sparse vectors via hard thresholding pursuit, Proc. Sampl. Theory Appl., (2011) [6] Zhang, Z.; Rao, B. D., Sparse signal recovery with temporally correlated source vectors using sparse bayesian learning, IEEE J. Sel. Top. Sign. Proces., 5, 5, 912-926, (2011) [7] Tang, G.; Nehorai, A., Performance analysis for sparse support recovery, IEEE Trans. Inform. Theory, 56, 3, 1383-1399, (2010) · Zbl 1366.94129 [8] Tropp, J. A.; Gilbert, A. C.; Strauss, M. J., Algorithms for simultaneous sparse approximation. part I: Greedy pursuit, Signal Process., 86, 3, 572-588, (2006) · Zbl 1163.94396 [9] Schmidt, R. O., Multiple emitter location and signal parameter estimation, IEEE Trans. Antennas and Propagation, 34, 3, 276-280, (1986) [10] Feng, P.; Bresler, Y., Spectrum-blind minimum-rate sampling and reconstruction of multiband signals, International Conference on Acoustics, Speech, and Signal Processing, Vol. 3, 1688-1691, (1996), IEEE [11] Kim, J. M.; Lee, O. K.; Ye, J. C., Compressive MUSIC: Revisiting the link between compressive sensing and array signal processing, IEEE Trans. Inform. Theory, 58, 1, 278-301, (2012) · Zbl 1365.94079 [12] Lee, K.; Bresler, Y.; Junge, M., Subspace methods for joint sparse recovery, IEEE Trans. Inform. Theory, 58, 6, 3613-3641, (2012) · Zbl 1365.94179 [13] Kim, J. M.; Lee, O.; Ye, J. C., Improving noise robustness in subspace-based joint sparse recovery, IEEE Trans. Signal Process., 60, 11, 5799-5809, (2012) · Zbl 1393.94688 [14] Ye, J. C.; Kim, J. M.; Bresler, Y., Improving M-SBL for joint sparse recovery using a subspace penalty, IEEE Trans. Signal Process., 63, 24, 6595-6605, (2015) · Zbl 1395.94185 [15] Tipping, M. E., Sparse Bayesian Learning and the relevance vector machine, J. Mach. Learn. Res., 1, Jun, 211-244, (2001) · Zbl 0997.68109 [16] Wipf, D. P.; Rao, B. D., Sparse Bayesian learning for basis selection, IEEE Trans. Signal Process., 52, 8, 2153-2164, (2004) · Zbl 1369.94318 [17] Wipf, D. P., Bayesian Methods for Finding Sparse Representations, (2006), UC San Diego, (Ph.D. thesis) [18] Wen, Z.; Hou, B.; Jiao, L., Joint sparse recovery with semisupervised MUSIC, IEEE Signal Process. Lett., 24, 5, 629-633, (2017) [19] Chen, J.; Huo, X., Theoretical results on sparse representations of multiple-measurement vectors, IEEE Trans. Signal Process., 54, 12, 4634-4643, (2006) · Zbl 1375.94051 [20] van den Berg, E.; Friedlander, M. P., Probing the pareto frontier for basis pursuit solutions, SIAM J. Sci. Comput., 31, 2, 890-912, (2008) · Zbl 1193.49033 [21] Cotter, S. F.; Rao, B. D.; Engan, K.; Kreutz-Delgado, K., Sparse solutions to linear inverse problems with multiple measurement vectors, IEEE Trans. Signal Process., 53, 7, 2477-2488, (2005) · Zbl 1372.65123 [22] Blanchard, J. D.; Cermak, M.; Hanle, D.; Jing, Y., Greedy Algorithms for Joint Sparse Recovery, IEEE Trans. Signal Process., 62, 7, 1694-1704, (2014) · Zbl 1394.94082 [23] Wang, J.; Kwon, S.; Shim, B., Generalized Orthogonal Matching Pursuit, IEEE Trans. Signal Process., 60, 12, 6202-6216, (2012) · Zbl 1393.94479 [24] Needell, D.; Vershynin, R., Uniform Uncertainty Principle and Signal Recovery via Regularized Orthogonal Matching Pursuit, Found. Comput. Math., 9, 3, 317-334, (2009) · Zbl 1183.68739 [25] Donoho, D. L.; Huo, X., Uncertainty principles and ideal atomic decomposition, IEEE Trans. Inform. Theory, 47, 7, 2845-2862, (2001) · Zbl 1019.94503 [26] Bajwa, W. U.; Calderbank, R.; Mixon, D. G., Two are better than one: fundamental parameters of frame coherence, Appl. Comput. Harmon. Anal., 33, 1, 58-78, (2012) · Zbl 1246.42026 [27] Foucart, S.; Rauhut, H., A Mathematical Introduction to Compressive Sensing, (2013), Springer · Zbl 1315.94002 [28] Bhatia, R., Matrix Analysis, Vol. 169, (2013), Springer Science & Business Media [29] Tropp, J., Greed is good: algorithmic results for sparse approximation, IEEE Trans. Inform. Theory, 50, 10, 2231-2242, (2004) · Zbl 1288.94019 [30] Kreyszig, E., Introductory Functional Analysis with Applications, Vol. 81, (1989), wiley New York [31] Laurent, B.; Massart, P., Adaptive estimation of a quadratic functional by model selection, Ann. Statist., 1302-1338, (2000) · Zbl 1105.62328 [32] Haupt, J.; Bajwa, W. U.; Raz, G.; Nowak, R., Toeplitz compressed sensing matrices with applications to sparse channel estimation, IEEE Trans. Inform. Theory, 56, 11, 5862-5875, (2010) · Zbl 1366.62110
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.