A box constrained gradient projection algorithm for compressed sensing. (English) Zbl 1217.94036
Summary: A new algorithm is presented which aims to solve problems from compressed sensing - under-determined problems where the solution vector is known a priori to be sparse. Upper bounds on the solution vector are found so that the problem can be reformulated as a box-constrained quadratic programme. A sparse solution is sought using a Barzilai-Borwein type projection algorithm. New insight into the choice of step length is provided through a study of the special structure of the underlying problem together with upper bounds on the step length. Numerical experiments are conducted and results given, comparing this algorithm with a number of other current algorithms.
MSC:
| 94A12 | Signal theory (characterization, reconstruction, filtering, etc.) |
Software:
L1-MAGICReferences:
| [1] | Barzilai, J.; Borwein, J. M.: Two-point step size gradient methods, IMA journal of numerical analysis 8, 141-148 (1988) · Zbl 0638.65055 · doi:10.1093/imanum/8.1.141 |
| [2] | Beck, A.; Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM journal of imaging sciences 2, No. 1, 183-202 (2009) · Zbl 1175.94009 · doi:10.1137/080716542 |
| [3] | Boyd, S.; Vandenberghe, L.: Convex optimization, (2004) · Zbl 1058.90049 |
| [4] | Candès, E.: The restricted isometry property and its implications for compressed sensing, Comptes rendus mathematique 346, 9-10 (2008) · Zbl 1153.94002 · doi:10.1016/j.crma.2008.03.014 |
| [5] | E. Candès, J. Romberg, l1-magic: recovery of sparse signals via convex programming, Technical Report, California Institute of Technology, October 2005. |
| [6] | Candès, E.; Romberg, J.; Tao, T.: Stable signal recovery from incomplete and inaccurate measurements, Communications on pure and applied mathematics 59, No. 8, 1207-1223 (2006) · Zbl 1098.94009 · doi:10.1002/cpa.20124 |
| [7] | E.J. Candès, Compressive sampling, in: Proceedings of the International Congress of Mathematics (Madrid, Spain), European Mathematical Society, 2006, pp. 1433–1452. · Zbl 1130.94013 |
| [8] | Candès, E. J.; Tao, T.: Near-optimal signal recovery from random projections and universal encoding strategies, IEEE transactions on information theory 52, No. 12, 5406-5425 (2006) · Zbl 1309.94033 |
| [9] | R. Chartrand, Nonconvex compressive sensing and reconstruction of gradientsparse images: random vs. tomographic Fourier sampling, in: IEEE Conference on Image Processing, vol. 15, 2008, pp. 2624–2627. |
| [10] | Claerbout, J.; Muir, F.: Robust modelling of erratic data, Geophysics 38, No. 5, 826-844 (1973) |
| [11] | Dai, Y. H.; Fletcher, R.: Projected barzilai–Borwein methods for large-scale box-constrained quadratic programming, Numerische Mathematik 100, 21-47 (2005) · Zbl 1068.65073 · doi:10.1007/s00211-004-0569-y |
| [12] | Dai, Y. H.; Hager, W. W.; Schittkowski, K.; Zhang, H.: The cyclic barzilai-Borwein method for unconstrained optimization, IMA journal of numerical analysis 26, 604-627 (2006) · Zbl 1147.65315 · doi:10.1093/imanum/drl006 |
| [13] | Dai, Y. H.; Liao, L. Z.: R-linear convergence of the barzilai and Borwein gradient method, IMA journal of numerical analysis 22, No. 1, 1-10 (2002) · Zbl 1002.65069 · doi:10.1093/imanum/22.1.1 |
| [14] | M.A.T. Figueiredo, J.M. Bioucas-Dias, M.V. Afonso, Fast frame-based image deconvolution using variable splitting and constrained optimization, in: IEEE Workshop on Statistical Signal Processing, 2009, pp. 109–112. |
| [15] | Figueiredo, M. A. T.; Nowak, R. D.; Wright, S. J.: Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems, IEEE journal of selected topics in signal processing 1, No. 4, 586-597 (2007) |
| [16] | Fletcher, R.: Practical methods of optimization, (March 1991) · Zbl 0905.65002 |
| [17] | Fletcher, R.: On the barzilai–Borwein method, numerical analysis report, (October 2001) |
| [18] | R. Garg, R. Khandekar, Gradient descent with sparsification: an iterative algorithm for sparse recovery with restricted isometry property, in: Proceedings of the 26th International Conference on Machine Learning 2009, pp. 337–344. |
| [19] | Golub, G.; Hansen, P. C.; O’leary, D.: Tikhonov regularization and total least squares, SIAM journal on matrix analysis and applications 21, No. 1, 185-194 (1999) · Zbl 0945.65042 · doi:10.1137/S0895479897326432 |
| [20] | Hale, E. T.; Yin, W.; Zhang, Y.: Fixed-point continuation applied to compressed sensing: implementation and numerical experiments, Journal of computational mathematics 28, No. 2, 170-194 (2010) · Zbl 1224.65153 · doi:10.4208/jcm.2009.10-m1007 |
| [21] | Hansen, P. C.: Rank-deficient and discrete ill-posed problems, (1998) |
| [22] | S.J. Kim, K. Koh, M. Lustig, S. Boyd, An efficient method for compressed sensing, in: IEEE International Conference on Image Processing, 2007, pp. 117–120. |
| [23] | Kim, S. J.; Koh, K.; Lustig, M.; Boyd, S.; Gorinevsky, D.: An interior-point method for large-scale l1-regularized least squares, IEEE journal of selected topics in signal processing 1, No. 4, 606-617 (2007) |
| [24] | Loris, I.; Bertero, M.; De Mol, C.; Zanella, R.; Zanni, L.: Accelerating gradient projection methods for l1-constrained signal recovery by steplength selection rules, Applied and computational harmonic analysis 27, No. 2, 247-254 (2009) · Zbl 1170.65318 · doi:10.1016/j.acha.2009.02.003 |
| [25] | Luengo, F.; Raydan, M.: Gradient method with dynamical retards for large-scale optimization problems, Electronic transactions on numerical analysis 16, 186-193 (2003) · Zbl 1134.90496 |
| [26] | Nocedal, J.; Wright, S. J.: Numerical optimization. Springer series in operations research and financial engineering, (2006) |
| [27] | Baraniuk, R.; Davenport, M.; Devore, R.; Wakin, M.: A simple proof of the restricted isometry property for random matrices, Constructive approximation 28, No. 3, 253-263 (2008) · Zbl 1177.15015 · doi:10.1007/s00365-007-9003-x |
| [28] | Raydan, M.: On the barzilai and Borwein choice of steplength for the gradient method, IMA journal of numerical analysis 13, No. 3, 321-326 (1993) · Zbl 0778.65045 · doi:10.1093/imanum/13.3.321 |
| [29] | Raydan, M.: The barzilai and Borwein gradient method for the large scale unconstrained minimization problem, SIAM journal of optimization 7, No. 1, 26-33 (1997) · Zbl 0898.90119 · doi:10.1137/S1052623494266365 |
| [30] | Raydan, M.; Svaiter, B. F.: Relaxed steepest descent and Cauchy–barzilai–Borwein method, Computational optimization and applications 21, No. 2, 155-167 (2002) · Zbl 0988.90049 · doi:10.1023/A:1013708715892 |
| [31] | Wang, Y.; Ma, S.: Projected barzilai–Borwein method for large-scale non-negative image restoration, Inverse problems in science and engineering 15, No. 6, 559-583 (2007) · Zbl 1202.94077 · doi:10.1080/17415970600881897 |
| [32] | S.J. Wright, R.D. Nowak, M.A.T. Figueiredo, Sparse reconstruction by separable approximation, in: IEEE International Conference on Acoustics, Speech and Signal Processing, 2008, pp. 3373–3376. |
| [33] | Wright, S. J.; Nowak, R. D.; Figueiredo, M. A. T.: Sparse reconstruction by separable approximation, IEEE transactions on signal processing 57, No. 7, 2479-2493 (2009) · Zbl 1391.94442 |
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.
