×

Reconstruction of jointly sparse vectors via manifold optimization. (English) Zbl 1418.90204

Summary: In this paper, we consider the challenge of reconstructing jointly sparse vectors from linear measurements. Firstly, we show that by utilizing the rank of the output data matrix we can reduce the problem to a full column rank case. This result reveals a reduction in the computational complexity of the original problem and enables a simple implementation of joint sparse recovery algorithms for full-rank setting. Secondly, we propose a new method for joint sparse recovery in the form of a non-convex optimization problem on a non-compact Stiefel manifold. In our numerical experiments our method outperforms the commonly used \(\ell_{2, 1}\) minimization in the sense that much fewer measurements are required for accurate sparse reconstructions. We postulate this approach possesses the desirable rank aware property, that is, being able to take advantage of the rank of the unknown matrix to improve the recovery.

MSC:

90C26 Nonconvex programming, global optimization
53C15 General geometric structures on manifolds (almost complex, almost product structures, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Absil, P. A.; Mahony, R.; Sepulchre, R., Optimization Algorithms on Matrix Manifolds (2009), Princeton University Press · Zbl 1147.65043
[2] Van den Berg, E.; Friedlander, M., Sparse optimization with least-squares constraints, SIAM J. Optim., 21, 1201-1229 (2011) · Zbl 1242.49061
[3] van den Berg, E.; Friedlander, M. P., Probing the Pareto frontier for basis pursuit solutions, SIAM J. Sci. Comput., 31, 890-912 (2008) · Zbl 1193.49033
[4] Boumal, N.; Mishra, B.; Absil, P. A.; Sepulchre, R., Manopt, a Matlab toolbox for optimization on manifolds, J. Mach. Learn. Res., 15, 1455-1459 (2014) · Zbl 1319.90003
[5] Candès, E.; Romberg, J.; Tao, T., Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory, 52, 489-509 (2006) · Zbl 1231.94017
[6] Chen, J.; Huo, X., Theoretical results on sparse representations of multiple-measurement vectors, IEEE Trans. Signal Process., 54, 4634-4643 (2006) · Zbl 1375.94051
[7] Chen, Y.; Nasrabadi, N. M.; Tran, T., Hyperspectral image classification using dictionary-based sparse representation, IEEE Trans. Geosci. Remote Sens., 49, 3973-3985 (2011)
[8] Dal Maso, G., An Introduction to Γ-Convergence, vol. 8 (2012), Springer Science & Business Media
[9] Dalalyan, A. S.; Hebiri, M.; Lederer, J., On the prediction performance of the lasso, Bernoulli, 23, 552-581 (2017) · Zbl 1359.62295
[10] Davies, M. E.; Eldar, Y. C., Rank awareness in joint sparse recovery, IEEE Trans. Inf. Theory, 58, 1135-1146 (2012) · Zbl 1365.94175
[11] Donoho, D. L., Compressed sensing, IEEE Trans. Inf. Theory, 52, 1289-1306 (2006) · Zbl 1288.94016
[12] Esser, E.; Lou, Y.; Xin, J., A method for finding structured sparse solutions to non-negative least squares problems with applications, SIAM J. Imaging Sci., 6, 2010-2046 (2013) · Zbl 1282.90239
[13] Fang, L.; Li, S.; Kang, X.; Benediktsson, J., Spectral – spatial hyperspectral image classification via multiscale adaptive sparse representation, IEEE Trans. Geosci. Remote Sens., 52, 7738-7749 (2014)
[14] Feng, P., Universal Minimum-Rate Sampling and Spectrum-Blind Reconstruction for Multiband Signals (1998), University of Illinois: University of Illinois Urbana-Champaign, Ph.D. thesis
[15] Feng, P.; Bresler, Y., Spectrum-blind minimum-rate sampling and reconstruction of multiband signals, Proc. ICASSP, 3, 1688-1691 (1996)
[16] Harjek, B., Cooling schedules for optimal annealing, Math. Oper. Res., 13, 311-329 (1988) · Zbl 0652.65050
[17] Hoyer, P., Non-negative matrix factorization with sparseness constraints, J. Mach. Learn. Res., 12, 1457-1469 (2004) · Zbl 1222.68218
[18] Huang, W.; Absil, P. A.; Gallivan, K. A.; Hand, P., Roptlib: an object-oriented c++ library for optimization on Riemannian manifolds, ACM Trans. Math. Softw., 44, 43 (2018) · Zbl 1484.65142
[19] Iordache, M. D.; Bioucas-Dias, J. M.; Plaza, A., Collaborative sparse regression for hyperspectral unmixing, IEEE Trans. Geosci. Remote Sens., 52, 341-354 (2014)
[20] Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 671-680 (1983) · Zbl 1225.90162
[21] Krishnan, D.; Tay, T.; Fergus, R., Blind deconvolution using a normalized sparsity measure, (Proc. of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (2011))
[22] Lai, M. J.; Liu, Y., The null space property for sparse recovery from multiple measurement vectors, Appl. Comput. Harmon. Anal., 30, 402-406 (2011) · Zbl 1228.65057
[23] Lederer, J.; Müller, C., Don’t fall for tuning parameters: tuning-free variable selection in high dimensions with the trex, (Twenty-Ninth AAAI Conference on Artificial Intelligence (2015))
[24] Lee, K.; Bresler, Y.; Junge, M., Subspace methods for joint sparse recovery, IEEE Trans. Inf. Theory, 58, 3613-3641 (2012) · Zbl 1365.94179
[25] Malioutov, D.; Cetin, M.; Willsky, A., A sparse signal reconstruction perspective for source localization with sensor arrays, IEEE Trans. Signal Process., 53, 3010-3022 (2005) · Zbl 1370.94191
[26] Mishali, M.; Eldar, Y. C., Reduce and boost: recovering arbitrary sets of jointly sparse vectors, IEEE Trans. Signal Process., 56, 4692-4702 (2008) · Zbl 1390.94306
[27] Natarajan, B. K., Sparse approximate solutions to linear systems, SIAM J. Comput., 24, 227-234 (1995) · Zbl 0827.68054
[28] Noferini, V., A formula for the fréchet derivative of a generalized matrix function, SIAM J. Matrix Anal. Appl., 38, 434-457 (2017) · Zbl 1367.65071
[29] Rahimi, Y.; Wang, C.; Dong, H.; Lou, Y., A scale invariant approach for sparse signal recovery (2018), arXiv preprint
[30] Schmidt, R. O., Multiple emitter location and signal parameter estimation, Proc. RADC Spectr. Estim. Workshop, 243-258 (1979)
[31] Townsend, J.; Koep, N.; Weichwald, S., Pymanopt: a python toolbox for optimization on manifolds using automatic differentiation, J. Mach. Learn. Res., 17, 1-5 (2016) · Zbl 1416.65580
[32] Tran, H.; Webster, C., Unified sufficient conditions for uniform recovery of sparse signals via nonconvex minimizations (2017)
[33] Udriste, C., Convex Functions and Optimization Methods on Riemannian Manifolds, Mathematics and Its Applications, vol. 297 (1994), Springer: Springer Netherlands · Zbl 0932.53003
[34] Vandereycken, B., Low-rank matrix completion by Riemannian optimization, SIAM J. Optim., 23, 1214-1236 (2013) · Zbl 1277.15021
[35] Wang, Z.; Liu, J.; Xue, J., Joint sparse model-based discriminative k-svd for hyperspectral image classification, Signal Process., 133, 144-155 (2017)
[36] Yin, P.; Esser, E.; Xin, J., Ratio and difference of \(\ell_1\) and \(\ell_2\) norms and sparse representation with coherent dictionaries, Commun. Inf. Syst., 14, 87-109 (2014) · Zbl 1429.94037
[37] Zhu, F.; Wang, Y.; Xiang, S.; Fan, B.; Pan, C., Structured sparse method for hyperspectral unmixing, ISPRS J. Photogramm. Remote Sens., 88, 101-118 (2014)
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.