×

Enhancing sparsity by reweighted \(\ell _{1}\) minimization. (English) Zbl 1176.94014

In this nice paper, the authors study a new method for sparse signal recovery that outperforms (unweighted) \(\ell_1\)minimization in the sense that substantially fewer measurements are needed for exact recovery. Let \(\Phi\) be a real \(m\times n\) matrix with \(m<n\). The authors would want to recover a (sparse) signal \(x_0 \in {\mathbb R}^n\) from given data \(y = \Phi x_0\) by solving a weighted \(\ell_1\) minimization problem \[ \min_{x\in {\mathbb R}^n} \sum_{i=1}^n w_i\,|x_i| \;\mathrm{subject to}\; y=\Phi x\,, \] where \(w_i\) are positive weights and \(x = (x_i)_{i=1}^n\in {\mathbb R}^n\). The authors propose a simple iterative algorithm that alternates between estimating \(x_0\) and redefining the weights. The weights are stepwise computed from the current solution. The number of iterations is typically very low. This iterative algorithm falls in the general class of majorization-minimization algorithms. Numerous experiments demonstrate the performance and applicability of this algorithm in sparse signal recovery, compressive sensing, statistical estimation, error correction, and magnetic resonance imaging. This paper closes with discussions of related work and possible future directions.

MSC:

94A12 Signal theory (characterization, reconstruction, filtering, etc.)
65K10 Numerical optimization and variational techniques
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory

Software:

PDCO
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004) · Zbl 1058.90049
[2] Taylor, H.L., Banks, S.C., McCoy, J.F.: Deconvolution with the 1 norm. Geophysics 44(1), 39–52 (1979) · doi:10.1190/1.1440921
[3] Claerbout, J.F., Muir, F.: Robust modeling with erratic data. Geophysics 38(5), 826–844 (1973) · doi:10.1190/1.1440378
[4] Santosa, F., Symes, W.W.: Linear inversion of band-limited reflection seismograms. SIAM J. Sci. Stat. Comput. 7(4), 1307–1330 (1986) · Zbl 0602.73113 · doi:10.1137/0907087
[5] Donoho, D.L., Stark, P.B.: Uncertainty principles and signal recovery. SIAM J. Appl. Math. 49(3), 906–931 (1989) · Zbl 0689.42001 · doi:10.1137/0149053
[6] Donoho, D.L., Logan, B.F.: Signal recovery and the large sieve. SIAM J. Appl. Math. 52(2), 577–591 (1992) · Zbl 0768.42001 · doi:10.1137/0152031
[7] Tibshirani, R.: Regression shrinkage and selection via the lasso. J. R. Stat. Soc. B 58(1), 267–288 (1996) · Zbl 0850.62538
[8] Chen, S., Donoho, D., Saunders, M.: Atomic decomposition by basis pursuit. SIAM J. Sci. Comput. 20(1), 33–61 (1998) · Zbl 0919.94002 · doi:10.1137/S1064827596304010
[9] Rudin, L.I., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physica D 60(1–4), 259–268 (1992) · Zbl 0780.49028 · doi:10.1016/0167-2789(92)90242-F
[10] Blomgren, P., Chan, T.F.: Color TV: total variation methods for restoration of vector-valued images. IEEE Trans. Image Process. 7, 304–309 (1998) · doi:10.1109/83.661180
[11] Vandenberghe, L., Boyd, S., El Gamal, A.: Optimal wire and transistor sizing for circuits with non-tree topology. In: Proceedings of the 1997 IEEE/ACM International Conference on Computer Aided Design, pp. 252–259 (1997)
[12] Vandenberghe, L., Boyd, S., El Gamal, A.: Optimizing dominant time constant in RC circuits. IEEE Trans. Comput.-Aided Des. 2(2), 110–125 (1998) · Zbl 05449967 · doi:10.1109/43.681261
[13] Hassibi, A., How, J., Boyd, S.: Low-authority controller design via convex optimization. AIAA J. Guid. Control Dyn. 22(6), 862–872 (1999) · doi:10.2514/2.4464
[14] Dahleh, M., Diaz-Bobillo, I.: Control of Uncertain Systems: A Linear Programming Approach. Prentice-Hall, Englewood Cliffs (1995) · Zbl 0838.93007
[15] Lobo, M., Fazel, M., Boyd, S.: Portfolio optimization with linear and fixed transaction costs. Ann. Oper. Res. 152(1), 341–365 (2006) · Zbl 1132.91474 · doi:10.1007/s10479-006-0145-1
[16] Ghosh, A., Boyd, S.: Growing well-connected graphs. In: Proceedings of the 45th IEEE Conference on Decision and Control, December 2006, pp. 6605–6611
[17] Sun, J., Boyd, S., Xiao, L., Diaconis, P.: The fastest mixing Markov process on a graph and a connection to a maximum variance unfolding problem. SIAM Rev. 48(4), 681–699 (2006) · Zbl 1109.60324 · doi:10.1137/S0036144504443821
[18] Kim, S.-J., Koh, K., Boyd, S., Gorinevsky, D.: 1 trend filtering. SIAM Rev. (2008, to appear); available at www.stanford.edu/\(\sim\)boyd/l1_trend_filter.html · Zbl 1171.37033
[19] Donoho, D.L., Huo, X.: Uncertainty principles and ideal atomic decomposition. IEEE Trans. Inf. Theory 47(7), 2845–2862 (2001) · Zbl 1019.94503 · doi:10.1109/18.959265
[20] Elad, M., Bruckstein, A.M.: A generalized uncertainty principle and sparse representation in pairs of bases. IEEE Trans. Inf. Theory 48(9), 2558–2567 (2002) · Zbl 1062.15001 · doi:10.1109/TIT.2002.801410
[21] Gribonval, R., Nielsen, M.: Sparse representations in unions of bases. IEEE Trans. Inf. Theory 49(12), 3320–3325 (2003) · Zbl 1286.94032 · doi:10.1109/TIT.2003.820031
[22] Tropp, J.A.: Just relax: convex programming methods for identifying sparse signals in noise. IEEE Trans. Inf. Theory 52, 1030–1051 (2006) · Zbl 1288.94025 · doi:10.1109/TIT.2005.864420
[23] 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
[24] Candès, E.J., Tao, T.: Near optimal signal recovery from random projections: Universal encoding strategies? IEEE Trans. Inf. Theory 52(12), 5406–5425 (2006) · Zbl 1309.94033 · doi:10.1109/TIT.2006.885507
[25] Donoho, D.: Compressed sensing. IEEE Trans. Inf. Theory 52(4) (2006) · Zbl 1288.94016
[26] Donoho, D.L., Tanner, J.: Counting faces of randomly-projected polytopes when the projection radically lowers dimension. J. Am. Math. Soc. 22, 1–53 (2009) · Zbl 1206.52010 · doi:10.1090/S0894-0347-08-00600-0
[27] Candès, E.J., Romberg, J., Tao, T.: Stable signal recovery from incomplete and inaccurate measurements. Commun. Pure Appl. Math. 59(8), 1207–1223 (2006) · Zbl 1098.94009 · doi:10.1002/cpa.20124
[28] Donoho, D., Tsaig, Y.: Extensions of compressed sensing. Signal Process. 86(3), 533–548 (2006) · Zbl 1163.94329 · doi:10.1016/j.sigpro.2005.05.027
[29] Takhar, D., Bansal, V., Wakin, M., Duarte, M., Baron, D., Kelly, K.F., Baraniuk, R.G.: A compressed sensing camera: New theory and an implementation using digital micromirrors. In: Proceedings of Comp. Imaging IV at SPIE Electronic Imaging, San Jose, California, January 2006
[30] Lustig, M., Donoho, D., Pauly, J.M.: Sparse MRI: The application of compressed sensing for rapid MR imaging. Preprint (2007)
[31] Candès, E.J., Tao, T.: Decoding by linear programming. IEEE Trans. Inf. Theory 51(12), 4203–4215 (2005) · Zbl 1264.94121 · doi:10.1109/TIT.2005.858979
[32] Candès, E.J., Randall, P.A.: Highly robust error correction by convex programming. Available on the ArXiV preprint server ( cs/0612124 ) (2006)
[33] Healy, D.L.: Analog-to-information (A-to-I). DARPA/MTO Broad Agency Announcement BAA 05-35 (July 2005)
[34] Bajwa, W., Haupt, J., Sayeed, A., Nowak, R.: Compressive wireless sensing. In: Proceedings of Fifth Int. Conf. on Information Processing in Sensor Networks, pp. 134–142 (2006)
[35] Baron, D., Wakin, M.B., Duarte, M.F., Sarvotham, S., Baraniuk, R.G.: Distributed compressed sensing. Preprint (2005)
[36] Lange, K.: Optimization, Springer Texts in Statistics. Springer, New York (2004)
[37] Fazel, M.: Matrix rank minimization with applications. Ph.D. thesis, Electrical Engineering Department, Stanford University (2002)
[38] Lobo, M.S., Fazel, M., Boyd, S.: Portfolio optimization with linear and fixed transaction costs. Ann. Oper. Res. 152(1), 341–365 (2007) · Zbl 1132.91474 · doi:10.1007/s10479-006-0145-1
[39] Fazel, M., Hindi, H., Boyd, S.: Log-det heuristic for matrix rank minimization with applications to Hankel and Euclidean distance matrices. In: Proceedings of Am. Control Conf., June 2003
[40] Figueiredo, M.A.T., Nowak, R.D.: A bound optimization approach to wavelet-based image deconvolution. In: Proceedings of IEEE Int. Conf. on Image Processing (ICIP), vol. 2 (2005)
[41] Figueiredo, M., Bioucas-Dias, J.M., Nowak, R.D.: Majorization–minimization algorithms for wavelet-based image restoration. IEEE Trans. Image Process. 16(12), 2980–2991 (2007) · Zbl 05516504 · doi:10.1109/TIP.2007.909318
[42] Wipf, D.P., Nagarajan, S.: A new view of automatic relevance determination. In: Proceedings on Neural Information Processing Systems (NIPS), vol. 20 (2008)
[43] Zou, H.: The adaptive Lasso and its oracle properties. J. Am. Stat. Assoc. 101(476), 1418–1429 (2006) · Zbl 1171.62326 · doi:10.1198/016214506000000735
[44] Zou, H., Li, R.: One-step sparse estimates in nonconcave penalized likelihood models. Ann. Stat. 36(4), 1509–1533 (2008) · Zbl 1142.62027 · doi:10.1214/009053607000000802
[45] Schlossmacher, E.J.: An iterative technique for absolute deviations curve fitting. J. Am. Stat. Assoc. 68(344), 857–859 (1973) · Zbl 0287.62038 · doi:10.2307/2284512
[46] Holland, P., Welsch, R.: Robust regression using iteratively reweighted least-squares. Commun. Stat. Theor. Methods A6, 813–827 (1977) · Zbl 0376.62035 · doi:10.1080/03610927708827533
[47] Huber, P.J.: Robust Statistics. Wiley-Interscience, New York (1981) · Zbl 0536.62025
[48] Yarlagadda, R., Bednar, J.B., Watt, T.L.: Fast algorithms for p deconvolution. IEEE Trans. Acoust. Speech Signal Process. 33(1), 174–182 (1985) · doi:10.1109/TASSP.1985.1164508
[49] Yin, W., Osher, S., Goldfarb, D., Darbon, J.: Bregman iterative algorithms for 1-minimization with applications to compressed sensing. SIAM J. Imaging Sci. 1(1), 143–168 (2008) · Zbl 1203.90153 · doi:10.1137/070703983
[50] Candès, E.J., Tao, T.: The Dantzig selector: Statistical estimation when p is much larger than n. Ann. Stat. 35(6), 2313–2351 (2007) · Zbl 1139.62019 · doi:10.1214/009053606000001523
[51] Goldfarb, D., Yin, W.: Second-order cone programming methods for total variation-based image restoration. SIAM J. Sci. Comput. 27(2), 622–645 (2005) · Zbl 1094.68108 · doi:10.1137/040608982
[52] Chartrand, R.: Exact reconstruction of sparse signals via nonconvex minimization. Signal Process. Lett. 14(10), 707–710 (2007) · doi:10.1109/LSP.2007.898300
[53] Starck, J.-L., Elad, M., Donoho, D.L.: Redundant multiscale transforms and their application for morphological component analysis. Adv. Imaging Electron. Phys. 132, 288–348 (2004)
[54] Elad, M., Milanfar, P., Rubinstein, R.: Analysis versus synthesis in signal priors. Inverse Probl. 23(3), 947–968 (2007) · Zbl 1138.93055 · doi:10.1088/0266-5611/23/3/007
[55] Gorodnitsky, I.F., Rao, B.D.: Sparse signal reconstruction from limited data using FOCUSS: A re-weighted minimum norm algorithm. IEEE Trans. Signal Process. 45(3), 600–616 (1997) · doi:10.1109/78.558475
[56] Chartrand, R., Yin, W.: Iteratively reweighted algorithms for compressive sensing. In: Proceedings of Int. Conf. on Acoustics, Speech, Signal Processing (ICASSP), pp. 3869–3872 (2008)
[57] Wipf, D.P.: Personal communication (January 2008)
[58] Harikumar, G., Bresler, Y.: A new algorithm for computing sparse solutions to linear inverse problems. In: Proceedings of Int. Conf. on Acoustics, Speech, Signal Processing (ICASSP). IEEE, New York (1996)
[59] Delaney, A.H., Bresler, Y.: Globally convergent edge-preserving regularized reconstruction: An application to limited-angle tomography. IEEE Trans. Image Process. 7(2), 204–221 (1998) · doi:10.1109/83.660997
[60] Saab, R., Chartrand, R., Yilmaz, O.: Stable sparse approximations via nonconvex optimization. In: 33rd International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2008
[61] Black, M.J., Sapiro, G., Marimont, D.H., Heeger, D.: Robust anisotropic diffusion. IEEE Trans. Image Process. 7(3), 421–432 (1998) · doi:10.1109/83.661192
[62] Boyd, S.: Lecture notes for EE364B: convex optimization II. Available at www.stanford.edu/class/ee364b/ (2007)
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.