×

A non-convex regularization approach for compressive sensing. (English) Zbl 1415.90088

Summary: Compressive sensing (CS) aims at reconstructing high dimensional data from a small number of samples or measurements. In this paper, we propose the minimization of a non-convex functional for the solution of the CS problem. The considered functional incorporates information on the self-similarity of the image by measuring the rank of some appropriately constructed matrices of fairly small dimensions. However, since the rank minimization is a NP hard problem, we consider, as a surrogate function for the rank, a non-convex, but smooth function. We provide a theoretical analysis of the proposed functional and develop an iterative algorithm to compute one of its stationary points. We prove the convergence of such algorithm and show, with some selected numerical experiments, that the proposed approach achieves good performances, even when compared with the state of the art.

MSC:

90C26 Nonconvex programming, global optimization
65K10 Numerical optimization and variational techniques
94A12 Signal theory (characterization, reconstruction, filtering, etc.)

Software:

NESTA
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Adcock, B., Hansen, A.C.: Generalized sampling and infinite-dimensional compressed sensing. Found. Comput. Math. 16(5), 1263-1323 (2016) · Zbl 1379.94026 · doi:10.1007/s10208-015-9276-6
[2] Adcock, B., Hansen, A.C., Poon, C., Roman, B.: Breaking the Coherence Barrier: a New Theory for Compressed Sensing. In: Forum of Mathematics, Sigma, Vol. 5. Cambridge University Press (2017) · Zbl 1410.94030
[3] Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences 2(1), 183-202 (2009) · Zbl 1175.94009 · doi:10.1137/080716542
[4] Becker, S., Bobin, J., Candes, E.J.: Nesta: A fast and accurate first-order method for sparse recovery. SIAM Journal on Imaging Sciences 4(1), 1-39 (2011) · Zbl 1209.90265 · doi:10.1137/090756855
[5] Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3(1), 1-122 (2011). https://doi.org/10.1561/2200000016 · Zbl 1229.90122 · doi:10.1561/2200000016
[6] Cai, J., Candès, E.J., Shen, Z.: A singular value thresholding algorithm for matrix completion. SIAM J. Optim. 20(4), 1956-1982 (2010) · Zbl 1201.90155 · doi:10.1137/080738970
[7] Cai, J.F., Osher, S., Shen, Z.: Linearized bregman iterations for frame-based image deblurring. SIAM Journal on Imaging Sciences 2(1), 226-252 (2009) · Zbl 1175.94010 · doi:10.1137/080733371
[8] Cai, J.F., Osher, S., Shen, Z.: Split Bregman methods and frame based image restoration. Multiscale modeling & simulation 8(2), 337-369 (2009) · Zbl 1189.94014 · doi:10.1137/090753504
[9] Candes, E., Romberg, J.: ℓ1-Magic: Recovery of sparse signals via convex programming. https://statweb.stanford.edu/ candes/l1magic/
[10] Candes, E.J., Plan, Y.: A probabilistic and ripless theory of compressed sensing. IEEE Trans. Inf. Theory 57(11), 7235-7254 (2011) · Zbl 1365.94174 · doi:10.1109/TIT.2011.2161794
[11] Candès, E.J., Romberg, J., Tao, T.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory 52(2), 489-509 (2006) · Zbl 1231.94017 · doi:10.1109/TIT.2005.862083
[12] Candès, E.J., Romberg, J., Tao, T.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory 52(2), 489-509 (2006) · Zbl 1231.94017 · doi:10.1109/TIT.2005.862083
[13] Chartrand, R.: Exact reconstruction of sparse signals via nonconvex minimization. IEEE Signal Processing Letters 14(10), 707-710 (2007) · doi:10.1109/LSP.2007.898300
[14] Dabov, K., Foi, A., Katkovnik, V., Egiazarian, K.: Image denoising by sparse 3-D transform-domain collaborative filtering. IEEE Trans. Image Process. 16(8), 2080-2095 (2007) · doi:10.1109/TIP.2007.901238
[15] Dai, Y.H., Yuan, Y.: A nonlinear conjugate gradient method with a strong global convergence property. SIAM J. Optim. 10(1), 177-182 (1999) · Zbl 0957.65061 · doi:10.1137/S1052623497318992
[16] Dong, W., Shi, G., Li, X., Ma, Y., Huang, F.: Compressive sensing via nonlocal low-rank regularization. IEEE Trans. Image Process. 23(8), 3618-3632 (2014) · Zbl 1374.94085 · doi:10.1109/TIP.2014.2329449
[17] Donoho, D.L.: Compressed sensing. IEEE Trans. Inf. Theory 52(4), 1289-1306 (2006) · Zbl 1288.94016 · doi:10.1109/TIT.2006.871582
[18] Engl, H.W., Hanke, M., Neubauer, A.: Regularization of inverse problems, vol. 375 Springer Science & Business Media (1996) · Zbl 0859.65054
[19] Fan, Y.R., Huang, T.Z., Liu, J., Zhao, X.L.: Compressive sensing via nonlocal smoothed rank function. PloS one 11(9), e0162,041 (2016) · doi:10.1371/journal.pone.0162041
[20] Gehm, M., John, R., Brady, D., Willett, R., Schulz, T.: Single-shot compressive spectral imaging with a dual-disperser architecture. Optics Express 15 (21), 14,013-14,027 (2007) · doi:10.1364/OE.15.014013
[21] Grippof, L., Sciandrone, M.: Globally convergent block-coordinate techniques for unconstrained optimization. Optimization methods and software 10(4), 587-637 (1999) · Zbl 0940.65070 · doi:10.1080/10556789908805730
[22] Gu, S., Zhang, L., Zuo, W., Feng, X.: Weighted nuclear norm minimization with application to image denoising. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 2862-2869 (2014)
[23] He, B., Tao, M., Yuan, X.: Alternating direction method with Gaussian back substitution for separable convex programming. SIAM J. Optim. 22(2), 313-340 (2012) · Zbl 1273.90152 · doi:10.1137/110822347
[24] Hu, Y., Ongie, G., Ramani, S., Jacob, M.: Generalized higher degree total variation (HDTV) regularization. IEEE Trans. Image Process. 23(6), 2423-2435 (2014) · Zbl 1374.94148 · doi:10.1109/TIP.2014.2315156
[25] Huang, G., Lanza, A., Morigi, S., Reichel, L., Sgallari, F.: Majorization – minimization generalized krylov subspace methods for ℓp − ℓq optimization applied to image restoration. BIT Numer. Math. 57(2), 351-378 (2017) · Zbl 1369.65073 · doi:10.1007/s10543-016-0643-8
[26] Lustig, M., Donoho, D., Pauly, J.M.: Sparse MRI: the application of compressed sensing for rapid MR imaging. Magn. Reson. Med. 58(6), 1182-1195 (2007) · doi:10.1002/mrm.21391
[27] Lustig, M., Donoho, D.L., Santos, J.M., Pauly, J.M.: Compressed sensing MRI. IEEE Signal Process. Mag. 25(2), 72-82 (2008) · doi:10.1109/MSP.2007.914728
[28] Ma, T.H., Huang, T.Z., Zhao, X.L.: Group-based image decomposition using 3-D cartoon and texture priors. Inform. Sci. 328, 510-527 (2016) · doi:10.1016/j.ins.2015.08.039
[29] Mairal, J., Bach, F., Ponce, J., Sapiro, G., Zisserman, A.: Non-local Sparse models for image restoration. In: 2009 IEEE 12th International Conference on Computer Vision, pp. 2272-2279 (2009), https://doi.org/10.1109/ICCV.2009.5459452
[30] Sarvotham, S., Baron, D., Wakin, M., Duarte, M.F., Baraniuk, R.G.: Distributed compressed sensing of jointly sparse signals. In: Asilomar Conference on Signals, Systems, and Computers, pp. 1537-1541 (2005)
[31] Takhar, D., Laska, J.N., Wakin, M.B., Duarte, M.F., Baron, D., Sarvotham, S., Kelly, K.F., Baraniuk, R.G.: A new compressive imaging camera architecture using optical-domain compression. In: International Society for Optics and Photonics Electronic Imaging 2006, pp. 606,509-606,509 (2006)
[32] Wang, Z., Bovik, A.C., Sheikh, H.R., Simoncelli, E.P.: Image quality assessment: from error visibility to structural similarity. IEEE Trans. Image Process. 13(4), 600-612 (2004) · doi:10.1109/TIP.2003.819861
[33] Zhang, X., Burger, M., Bresson, X., Osher, S.: Bregmanized nonlocal regularization for deconvolution and sparse reconstruction. SIAM Journal on Imaging Sciences 3(3), 253-276 (2010) · Zbl 1191.94030 · doi:10.1137/090746379
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.