Enhanced joint sparsity via iterative support detection. (English) Zbl 1435.94065
Summary: Joint sparsity has attracted considerable attention in recent years in many fields including sparse signal recovery in compressive sensing, statistics, and machine learning. Traditional convex models with joint sparsity suffer from the suboptimal performance though enjoying tractable computation. In this paper, we propose a new non-convex joint sparsity model, and develop a corresponding multi-stage adaptive convex relaxation algorithm. This method extends the idea of iterative support detection (ISD) from the single vector estimation to the multi-vector estimation by considering the joint sparsity prior. We provide some preliminary theoretical analysis including convergence analysis and a sufficient recovery condition. Numerical experiments from both compressive sensing and multi-task feature learning show the better performance of the proposed method in comparison with several state-of-the-art alternatives. Moreover, we demonstrate that the extension of ISD from the single vector to multi-vector estimation is not trivial. While ISD does not well reconstruct the single channel sparse Bernoulli signal, it does achieve significantly improved performance when recovering the multi-channel sparse Bernoulli signal thanks to its ability of natural incorporation of the joint sparsity structure.
MSC:
| 94A12 | Signal theory (characterization, reconstruction, filtering, etc.) |
| 90C26 | Nonconvex programming, global optimization |
Keywords:
iterative support detection; joint sparsity; \(\ell_{2,1}\)-norm minimization; nonconvex optimization; compressive sensing; multi-task feature learningReferences:
| [1] | Beck, A.; Teboulle, M., A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2, 1, 183-202 (2009) · Zbl 1175.94009 |
| [2] | Candes, E.; Wakin, M.; Boyd, S., Enhancing sparsity by reweighted \(ℓ_1\) minimization, J. Fourier Anal. Appl., 14, 5, 877-905 (2008) · Zbl 1176.94014 |
| [3] | Canny, J., A computational approach to edge detection, IEEE Trans. Pattern Anal. Mach. Intell., 6, 679-698 (1986) |
| [4] | Chang, W.-L.; Zeng, D.; Chen, R.-C.; Guo, S., An artificial bee colony algorithm for data collection path planning in sparse wireless sensor networks, Int. J. Mach. Learn. Cybern., 6, 3, 375-383 (2015) |
| [5] | Chartrand, R., Exact reconstruction of sparse signals via nonconvex minimization, IEEE Signal Process. Lett., 14, 10, 707-710 (2007) |
| [6] | Chartrand, R.; Yin, W., Iteratively reweighted algorithms for compressive sensing, Proceedings of the International Conference on Acoustics, Speech and Signal Processing, 3869-3872 (2008), IEEE |
| [7] | Cotter, S.; Rao, B.; 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 |
| [8] | Deng, W.; Yin, W.; Zhang, Y., Group sparse optimization by alternating direction method, Proceedings of the Conference on SPIE Optical Engineering + Applications, 88580R (2013), International Society for Optics and Photonics |
| [9] | Duarte, M.; Sarvothamand, S.; Wakin, M.; Baron, D.; Baraniuk, R., Joint sparsity models for distributed compressed sensing, Proceedings of the Workshop on Signal Processing with Adaptative Sparse Structured Representations (2005), IEEE |
| [10] | Eldar, Y.; Rauhut, H., Average case analysis of multichannel sparse recovery using convex relaxation, IEEE Trans. Inf. Theory, 56, 1, 505-519 (2010) · Zbl 1366.94095 |
| [11] | Fan, Y.-R.; Huang, T.-Z.; Liu, J.; Zhao, X.-L., Compressive sensing via nonlocal smoothed rank function, PLoS ONE, 11, 9, e0162041 (2016) |
| [12] | Fan, Y.-R.; Huang, T.-Z.; Ma, T.-H.; Zhao, X.-L., Cartoon-texture image decomposition via non-convex low-rank texture regularization, J. Frankl. Inst., 354, 7, 3170-3187 (2017) · Zbl 1364.94093 |
| [13] | Fang, Y.; Gui-fa, T., Visual music score detection with unsupervised feature learning method based on k-means, Int. J. Mach. Learn. Cybern., 6, 2, 277-287 (2015) |
| [14] | Gonçalves, A.; Das, P.; Chatterjee, S.; Sivakumar, V.; Zuben, F. V.; Banerjee, A., Multi-task sparse structure learning, Proceedings of the Twenty-Third ACM International Conference on Conference on Information and Knowledge Management, 451-460 (2014), ACM |
| [15] | Gong, P.; Ye, J.; Zhang, C., Multi-stage multi-task feature learning, Proceedings of the Advances in Neural Information Processing Systems, 1988-1996 (2012) |
| [16] | Gribonval, R.; Mailhe, B.; Rauhut, H.; Schnass, K.; Vandergheynst, P., Average case analysis of multichannel thresholding, Proceedings of the International Conference on Acoustics, Speech and Signal Processing, 2, II-853 (2007), IEEE |
| [17] | Heckel, R.; Bolcskei, H., Joint sparsity with different measurement matrices, Proceedings of the Fiftieth Annual Allerton Conference on Communication, Control, and Computing (Allerton), 698-702 (2012), IEEE |
| [18] | Hu, Y.; Liu, J.; Leng, C.; An, Y.; Zhang, S.; Wang, K., \(L_p\) regularization for bioluminescence tomography based on the split Bregman method, Mol. Imaging Biol., 18, 6, 830-837 (2016) |
| [19] | Hyder, M.; Mahata, K., A robust algorithm for joint-sparse recovery, IEEE Signal Process. Lett., 16, 12, 1091-1094 (2009) |
| [20] | Ince, T.; Nacaroglu, A.; Watsuji, N., Nonconvex compressed sensing with partially known signal support, Signal Process., 93, 1, 338-344 (2013) |
| [21] | Jiang, B.; Liu, Y.-F.; Wen, Z., \(L_p\)-norm regularization algorithms for optimization over permutation matrices, SIAM J. Optim., 26, 4, 2284-2313 (2016) · Zbl 1353.65055 |
| [22] | Kim, J.; Lee, O.; Ye, J., Improving noise robustness in subspace-based joint sparse recovery, IEEE Trans. Signal Process., 60, 11, 5799-5809 (2012) · Zbl 1393.94688 |
| [23] | Lai, M.-J.; Liu, Y., The null space property for sparse recovery from multiple measurement vectors, Appl. Comput. Harmon. Anal., 30, 3, 402-406 (2011) · Zbl 1228.65057 |
| [24] | Lee, K.; Bresler, Y.; Junge, M., Subspace methods for joint sparse recovery, IEEE Trans. Inf. Theory, 58, 6, 3613-3641 (2012) · Zbl 1365.94179 |
| [25] | Liu, J.; Ji, S.; Ye, J., Multi-task feature learning via efficient \(ℓ_{2,1}\)-norm minimization, Proceedings of the Twenty-fifth Conference on Uncertainty in Artificial Intelligence, 339-348 (2009), AUAI Press |
| [26] | Lu, H.; Long, X.; Lv, J., A fast algorithm for recovery of jointly sparse vectors based on the alternating direction methods., Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics (AISTATS), 461-469 (2011) · Zbl 1412.94059 |
| [27] | Meng, J.; Yin, W.; Li, H.; Hossain, E.; Han, Z., Collaborative spectrum sensing from sparse observations in cognitive radio networks, IEEE J. Sel. Areas Commun., 29, 2, 327-337 (2011) |
| [28] | Obozinski, G.; Taskar, B.; Jordan, M., Joint covariate selection for grouped classification, Technical Report (2007), Statistics Department, UC Berkeley |
| [29] | Qin, Z.; Scheinberg, K.; Goldfarb, D., Efficient block-coordinate descent algorithms for the group lasso, Math. Program. Comput., 5, 2, 143-169 (2013) · Zbl 1275.90059 |
| [30] | Saleh, A.; Alajaji, F.; Chan, W.-Y., Compressed sensing with non-gaussian noise and partial support information, IEEE Signal Process. Lett., 22, 10, 1703-1707 (2015) |
| [31] | Sanders, T.; Gelb, A.; Platte, R., Composite SAR imaging using sequential joint sparsity, J. Comput. Phys., 338, 357-370 (2017) · Zbl 1415.65050 |
| [32] | Singh, A.; Dandapat, S., Block sparsity-based joint compressed sensing recovery of multi-channel ecg signals, Healthc. Technol. Lett., 4, 2, 50-56 (2017) |
| [33] | Tropp, J.; Gilbert, A.; Strauss, M., Algorithms for simultaneous sparse approximation. part I: greedy pursuit, Signal Process., 86, 3, 572-588 (2006) · Zbl 1163.94396 |
| [34] | Wang, Y.; Yin, W., Sparse signal reconstruction via iterative support detection, SIAM J. Imaging Sci., 3, 3, 462-491 (2010) · Zbl 1206.68340 |
| [35] | Wen, Z.; Hou, B.; Jiao, L., Joint sparse recovery with semisupervised MUSIC, IEEE Signal Process. Lett., 24, 5, 629-633 (2017) |
| [36] | Wimalajeewa, T.; Varshney, P., OMP based joint sparsity pattern recovery under communication constraints, IEEE Trans. Signal Process., 62, 19, 5059-5072 (2014) · Zbl 1394.94636 |
| [37] | Yang, J.; Zhang, Y., Alternating direction algorithms for \(ℓ_1\)-problems in compressive sensing, SIAM J. Sci. Comput., 33, 1, 250-278 (2011) · Zbl 1256.65060 |
| [38] | Yang, X.; Kim, S.; Xing, E., Heterogeneous multitask learning with joint sparsity constraints, Proceedings of the Advances in Neural Information Processing Systems, 2151-2159 (2009) |
| [39] | Yang, Y.; Deng, C.; Gao, S.; Liu, W.; Tao, D.; Gao, X., Discriminative multi-instance multitask learning for 3d action recognition, IEEE Trans. Multimedia, 19, 3, 519-529 (2017) |
| [40] | Yang, Z.; Xie, L., Exact joint sparse frequency recovery via optimization methods, IEEE Trans. Signal Process., 64, 19, 5145-5157 (2016) · Zbl 1414.94707 |
| [41] | Zhang, X.; Liu, C., A one-dimensional slope detection approach, Springerplus, 2, 1, 474 (2013) |
| [42] | Zhou, J.; Chen, J.; Ye, J., MALSAR: Multi-task Learning Via Structural Regularization, Arizona State University, 21 (2011) |
| [43] | Zhu, X.; Grohnfeldt, C.; Bamler, R., Exploiting joint sparsity for pansharpening: the J-sparseFI algorithm, IEEE Trans. Geosci. Remote Sens., 54, 5, 2664-2681 (2016) |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
