×

CGIHT: conjugate gradient iterative hard thresholding for compressed sensing and matrix completion. (English) Zbl 1380.94045

Summary: We introduce the conjugate gradient iterative hard thresholding (CGIHT) family of algorithms for the efficient solution of constrained underdetermined linear systems of equations arising in compressed sensing, row-sparse approximation and matrix completion. CGIHT is designed to balance the low per iteration complexity of simple hard thresholding algorithms with the fast asymptotic convergence rate of employing the conjugate gradient method. We establish provable recovery guarantees and stability to noise for variants of CGIHT with sufficient conditions in terms of the restricted isometry constants of the sensing operators. Extensive empirical performance comparisons establish significant computational advantages for CGIHT both in terms of the size of problems, which can be accurately approximated and in terms of overall computation time.

MSC:

94A12 Signal theory (characterization, reconstruction, filtering, etc.)

Software:

CoSaMP; TwIST; PDCO; ADMiRA; SPGL1
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Amelunxen, D.; Lotz, M.; McCoy, M. B.; Tropp, J. A., Living on the edge: a geometric theory of phase transitions in convex optimization, Inf. Inference: J. IMA, 3, 294, (2014) · Zbl 1339.90251 · doi:10.1093/imaiai/iau005
[2] Bah, B.; Tanner, J., Improved bounds on restricted isometry constants for Gaussian matrices, SIAM J. Matrix Anal., 31, 2898, (2010) · Zbl 1208.60026 · doi:10.1137/100788884
[3] Beck, A.; Teboulle, M., A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2, 202, (2009) · Zbl 1175.94009 · doi:10.1137/080716542
[4] Beck, A.; Teboulle, M., A fast dual proximal gradient algorithm for convex minimization and applications, Oper. Res. Lett., 42, 6, (2014) · Zbl 1408.90232 · doi:10.1016/j.orl.2013.10.007
[5] Berg, E. V. D.; Friedlander, M. P., Probing the Pareto frontier for basis pursuit solutions, SIAM J. Sci. Comput., 31, 912, (2008) · Zbl 1193.49033 · doi:10.1137/080714488
[6] Bioucas-Dias, J. M.; Figueiredo, M. A. T., A new TwIST: two-step iterative shrinkage/thresholding algorithms for image restoration, IEEE Trans. Image Process., 16, 3004, (2007) · doi:10.1109/TIP.2007.909319
[7] Blanchard, J. D.; Cartis, C.; Tanner, J., Compressed sensing: how sharp is the restricted isometry property?, SIAM Rev., 53, 125, (2011) · Zbl 1214.41008 · doi:10.1137/090748160
[8] Blanchard, J. D.; Cartis, C.; Tanner, J.; Thompson, A., Phase transitions for greedy sparse approximation algorithms, Appl. Comput. Harmon. Anal., 30, 203, (2011) · Zbl 1229.94003 · doi:10.1016/j.acha.2010.07.001
[9] Blanchard, J. D.; Cermak, M.; Hanle, D.; Jing, Y., Greedy algorithms for joint sparse recovery, IEEE Trans. Sig. Proc., 62, 1704, (2014) · Zbl 1394.94082 · doi:10.1109/TSP.2014.2301980
[10] Blanchard, J. D.; Tanner, J., (2013a)
[11] Blanchard, J. D.; Tanner, J., GPU accelerated greedy algorithms for compressed sensing, Math. Prog. Comput., 5, 304, (2013b) · Zbl 1300.65038 · doi:10.1007/s12532-013-0056-5
[12] Blanchard, J. D.; Tanner, J., Performance comparisons of greedy algorithms in compressed sensing, Num. Linear Algebr. Appl, 22, 282, (2015) · Zbl 1363.94017 · doi:10.1002/nla.v22.2
[13] Blanchard, J. D.; Tanner, J.; Wei, K., Conjugate gradient iterative hard thresholding: observed noise stability for compressed sensing, IEEE Trans. Signal Process., 63, 537, (2015) · Zbl 1394.94083 · doi:10.1109/TSP.2014.2379665
[14] Blumensath, T., Accelerated iterative hard thresholding, Signal Process., 92, 756, (2012) · doi:10.1016/j.sigpro.2011.09.017
[15] Blumensath, T.; Davies, M. E., Iterative hard thresholding for compressed sensing, Appl. Comput. Harmon. Anal., 27, 274, (2009) · Zbl 1174.94008 · doi:10.1016/j.acha.2009.04.002
[16] Blumensath, T.; Davies, M. E., Normalised iterative hard thresholding; guaranteed stability and performance, IEEE Sel. Top. Signal Process., 4, 309, (2010) · doi:10.1109/JSTSP.2010.2042411
[17] Bruckstein, A. M.; Donoho, D. L.; Elad, M., From sparse solutions of systems of equations to sparse modeling of signals and images, SIAM Rev., 51, 81, (2009) · Zbl 1178.68619 · doi:10.1137/060657704
[18] Cai, J.-F.; Candès, E. J.; Shen, Z., A singular value thresholding algorithm for matrix completion, SIAM J. Optim., 20, 1982, (2010) · Zbl 1201.90155 · doi:10.1137/080738970
[19] Candès, E. J., Compressive sampling, International Congress of Mathematicians, III, 1452, (2006) · Zbl 1130.94013
[20] Candès, E.; Recht, B., Exact matrix completion via convex optimization, Found. Comput. Math., 9, 772, (2009) · Zbl 1219.90124 · doi:10.1007/s10208-009-9045-5
[21] Candès, E. J.; Romberg, J.; Tao, T., Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inform. Theory, 52, 509, (2006) · Zbl 1231.94017 · doi:10.1109/TIT.2005.862083
[22] Candès, E. J.; Tao, T., Decoding by linear programming, IEEE Trans. Inform. Theory, 51, 4215, (2005) · Zbl 1264.94121 · doi:10.1109/TIT.2005.858979
[23] Candès, E. J.; Tao, T., Near-optimal signal recovery from random projections: universal encoding strategies?, IEEE Trans. Inform. Theory, 52, 5425, (2006) · Zbl 1309.94033 · doi:10.1109/TIT.2006.885507
[24] Cartis, C.; Thompson, A., A new and improved quantitative recovery analysis for iterative hard thresholding algorithms in compressed sensing, IEEE Trans. Inform. Theory, 61, 24, (2015) · Zbl 1359.94071 · doi:10.1109/TIT.2015.2399919
[25] Cevher, V., An ALPS view of sparse recovery, 5811, (2011)
[26] Chandar, V.; Shah, D.; Wornell, G. W., A simple message-passing algorithm for compressed sensing, 1972, (2010)
[27] Chen, S. S.; Donoho, D. L.; Saunders, M. A., Atomic decomposition by basis pursuit, SIAM Rev., 43, 159, (2001) · Zbl 0979.94010 · doi:10.1137/S003614450037906X
[28] Dai, W.; Milenkovic, O., Subspace pursuit for compressive sensing signal reconstruction, IEEE Trans. Inform. Theory, 55, 2249, (2009) · Zbl 1367.94082 · doi:10.1109/TIT.2009.2016006
[29] Dai, W.; Milenkovic, O.; Kerman, E., Subspace evolution and transfer (SET) for low-rank matrix completion, IEEE Trans Signal Process., 59, 3132, (2011) · Zbl 1392.94167 · doi:10.1109/TSP.2011.2144977
[30] Devolder, O.; Glineur, F.; Nesterov, Y., First-order methods of smooth convex optimization with inexact oracle, Math. Program. Ser. A, 146, 75, (2014) · Zbl 1317.90196 · doi:10.1007/s10107-013-0677-5
[31] Donoho, D. L., (2004)
[32] Donoho, D. L., Compressed sensing, IEEE Trans. Inform. Theory, 52, 1306, (2006a) · Zbl 1288.94016 · doi:10.1109/TIT.2006.871582
[33] Donoho, D. L., High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension, Discrete Comput. Geom., 35, 652, (2006b) · Zbl 1095.52500 · doi:10.1007/s00454-005-1220-0
[34] Donoho, D. L.; Gavish, M., Minimax risk of matrix denoising by singular value thresholding, Ann. Statist., 42, 2440, (2014) · Zbl 1310.62014 · doi:10.1214/14-AOS1257
[35] Donoho, D. L.; Gavish, M.; Montanari, A., The phase transition of matrix recovery from Gaussian measurements matches the minimax MSE of matrix denoising, Proc. Natl Acad. Sci. USA, 110, 8410, (2013) · Zbl 1292.94004 · doi:10.1073/pnas.1306110110
[36] Donoho, D. L.; Johnstone, I.; Montanari, A., Accurate prediction of phase transitions in compressed sensing via a connection to minimax denoising, IEEE Trans. Inform. Theory, 59, 3433, (2013) · Zbl 1364.94092 · doi:10.1109/TIT.2013.2239356
[37] Donoho, D. L.; Maleki, A., Optimally tuned iterative thresholding algorithms for compressed sensing, IEEE Sel. Top. Signal Process., 4, 341, (2010) · doi:10.1109/JSTSP.2009.2039176
[38] Donoho, D. L.; Maleki, A.; Montanari, A., Message-passing algorithms for compressed sensing, Proc. Natl Acad. Sci. USA, 106, 18919, (2009) · doi:10.1073/pnas.0909892106
[39] Donoho, D. L.; Maleki, A.; Montanari, A., Message passing algorithms for compressed sensing: I. Motivation and construction, (2010a)
[40] Donoho, D. L.; Maleki, A.; Montanari, A., Message passing algorithms for compressed sensing: II. Analysis and validation, (2010b)
[41] Donoho, D. L.; Tanner, J., Sparse non-negative solution of underdetermined linear equations by linear programming, Proc. Natl Acad. Sci. USA, 102, 9451, (2005) · Zbl 1135.90368 · doi:10.1073/pnas.0502269102
[42] Donoho, D. L.; Tanner, J., Counting faces of randomly projected polytopes when the projection radically lowers dimension, J. Amer. Math. Soc., 22, 53, (2009) · Zbl 1206.52010 · doi:10.1090/S0894-0347-08-00600-0
[43] Eldar, Y. C.; Kutyniok, G., Compressed Sensing: Theory and Applications, (2012)
[44] Figueiredo, M. A. T.; Nowak, R. D.; Wright, S. J., Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems, IEEE Sel. Top. Signal Process., 1, 597, (2007) · doi:10.1109/JSTSP.2007.910281
[45] Foucart, S., Hard thresholding pursuit: an algorithm for compressive sensing, SIAM J. Numer. Anal., 49, 2563, (2011a) · Zbl 1242.65060 · doi:10.1137/100806278
[46] Foucart, S., (2011b)
[47] Foucart, S., (2012)
[48] Foucart, S.; Rauhut, H., A Mathematical Introduction to Compressive Sensing, (2013) · Zbl 1315.94002
[49] Garg, R.; Khandekar, R., Gradient descent with sparsification: an iterative algorithm for sparse recovery with restricted isometry property, 344, (2009)
[50] Goldstein, T.; Setzer, S., (2004)
[51] Greenbaum, A., Iterative Methods for Solving Linear Systems, (1997) · Zbl 0883.65022
[52] Guo, C.; Davies, M. E., Near optimal compressed sensing without priors: parametric SURE approximate message passing, IEEE Trans. Signal Process., 63, 2141, (2015) · Zbl 1394.94215 · doi:10.1109/TSP.2015.2408569
[53] Haldar, J. P.; Hernando, D., Rank-constrained solutions to linear matrix equations using PowerFactorization, IEEE Signal Process. Lett., 16, 587, (2009) · doi:10.1109/LSP.2009.2018223
[54] Hestenes, M. R.; Stiefel, E., Methods of conjugate gradients for solving linear systems, J. Res. Natl. Bur. Stand., 49, 436, (1952) · Zbl 0048.09901 · doi:10.6028/jres.049.044
[55] Horn, R. A.; Johnson, C. R., Matrix Analysis, (1990) · Zbl 0704.15002
[56] Jain, P.; Meka, R.; Dhillon, I., Guaranteed rank minimization via singular value projection, Adv. Neural Inform. Process. Syst., 23, 945, (2010)
[57] Keshavan, R. H.; Montanari, A.; Oh, S., Matrix completion from a few entries, IEEE Trans. Inform. Theory, 56, 2998, (2010) · Zbl 1366.62111 · doi:10.1109/TIT.2010.2046205
[58] Kyrillidis, A.; Cevher, V., Matrix ALPS: accelerated low rank and sparse matrix reconstruction, 188, (2012)
[59] Kyrillidis, A.; Cevher, V., Matrix recipes for hard thresholding methods, J. Math. Imaging Vis., 48, 265, (2014) · Zbl 1311.90141 · doi:10.1007/s10851-013-0434-7
[60] Lee, K.; Bresler, Y., ADMiRA: atomic decomposition for minimum rank approximation, IEEE Trans. Inform. Theory, 56, 4416, (2010) · Zbl 1366.94112 · doi:10.1109/TIT.2010.2054251
[61] Leviatan, D.; Temlyakov, V. N., Simultaneous approximation by greedy algorithms, Adv. Comput. Math., 25, 90, (2006) · Zbl 1096.41026 · doi:10.1007/s10444-004-7613-4
[62] Lewis, A. S.; Malick, J., Alternating projections on manifolds, Math. Oper. Res., 33, 234, (2008) · Zbl 1163.65040 · doi:10.1287/moor.1070.0291
[63] Lutoborski, A.; Temlyakov, V. N., Vector greedy algorithms, J. Complexity, 19, 473, (2003) · Zbl 1234.41024 · doi:10.1016/S0885-064X(03)00026-8
[64] Ma, S. Q.; Goldfarb, D.; Chen, L. F., Convergence of fixed-point continuation algorithms for matrix rank minimization, Found. Comput. Math., 11, 210, (2011a) · Zbl 1219.90195 · doi:10.1007/s10208-011-9084-6
[65] Ma, S. Q.; Goldfarb, D.; Chen, L. F., Fixed point and Bregman iterative methods for matrix rank minimization, Math. Program. Ser. A., 128, 353, (2011b) · Zbl 1221.65146 · doi:10.1007/s10107-009-0306-5
[66] Maleki, A., Coherence analysis of iterative thresholding algorithms, 243, (2009)
[67] Meyer, G.; Bonnabel, S.; Sepulchre, R., Linear regression under fixed-rank constraints: a Riemannian approach, (2011)
[68] Natarajan, B. K., Sparse approximate solutions to linear systems, SIAM J. Comput., 24, 234, (1995) · Zbl 0827.68054 · doi:10.1137/S0097539792240406
[69] Needell, D.; Tropp, J. A., CoSaMP: iterative signal recovery from incomplete and inaccurate samples, Appl. Comp. Harm. Anal., 26, 321, (2009) · Zbl 1163.94003 · doi:10.1016/j.acha.2008.07.002
[70] Nesterov, Y., Introductory Lectures on Convex Optimization: A Basic Course, (2004) · Zbl 1086.90045
[71] Nesterov, Y., (2007)
[72] Powell, M. J. D., Some convergence properties of the conjugate gradient method, Math. Program., 11, 49, (1976) · Zbl 0356.65056 · doi:10.1007/BF01580369
[73] Rauhut, H.; Romberg, J.; Tropp, J. A., Restricted isometries for partial random circulant matrices, Appl. Comput. Harmon. Anal., 32, 254, (2012) · Zbl 1245.15040 · doi:10.1016/j.acha.2011.05.001
[74] Recht, B.; Fazel, M.; Parrilo, P. A., Guaranteed minimum rank solutions to linear matrix equations via nuclear norm minimization, SIAM Rev., 52, 501, (2010) · Zbl 1198.90321 · doi:10.1137/070697835
[75] Recht, B.; Xu, W.; Hassibi, B., Null space conditions and thresholds for rank minimization, Math. Program. Ser. B, 127, 211, (2011) · Zbl 1211.90172 · doi:10.1007/s10107-010-0422-2
[76] Rudelson, M.; Vershynin, R., On sparse reconstruction from Fourier and Gaussian measurements, Comm. Pure Appl. Math., 61, 1045, (2008) · Zbl 1149.94010 · doi:10.1002/(ISSN)1097-0312
[77] Tanner, J.; Wei, K., Normalized iterative hard thresholding for matrix completion, SIAM J. Scientfic Comput., 35, S125, (2013) · Zbl 1282.65043 · doi:10.1137/120876459
[78] Temlyakov, V. N., A remark on simultaneous greedy approximation, East J. Approx., 10, 25, (2004) · Zbl 1113.41026
[79] Toh, K.-C.; Yun, S., An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems, Pac. J. Optim., 6, 640, (2010) · Zbl 1205.90218
[80] Tropp, J. A., Algorithms for simultaneous sparse approximation. Part II: Convex relaxation, Signal Process., 86, 602, (2006) · Zbl 1163.94395 · doi:10.1016/j.sigpro.2005.05.031
[81] Tropp, J. A.; Gilbert, A. C.; Strauss, M. J., Algorithms for simultaneous sparse approximation. Part I: Greedy pursuit, Signal Process., 86, 588, (2006) · Zbl 1163.94396 · doi:10.1016/j.sigpro.2005.05.030
[82] Tropp, J. A.; Wright, S. J., Computational methods for sparse solution of linear inverse problems, Proc. IEEE, 98, 958, (2010) · doi:10.1109/JPROC.2010.2044010
[83] Wei, K., (2014)
[84] Wright, S. J.; Nowak, R. D.; Figueiredo, M. A. T., Sparse reconstruction by separable approximation, (2008)
[85] Xu, W.; Hassibi, B., Precise stability phase transitions for \[ℓ_1\] minimization: a unified geometric framework, IEEE Trans. Inform. Theory, 57, 6919, (2008) · Zbl 1365.94089 · doi:10.1109/TIT.2011.2165825
[86] Yin, W.; Osher, S.; Goldfarb, D.; Darbon, J., Bregman iterative algorithms for \[ℓ^1\]-minimization with applications to compressed sensing, SIAM J. Imaging Sci., 1, 168, (2008) · Zbl 1203.90153 · doi:10.1137/070703983
[87] Yuan, Y. X., Analysis of conjugate gradient method, Optim. Methods Softw., 2, 29, (1993) · doi:10.1080/10556789308805532
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.