Sparse decomposition by iterating Lipschitzian-type mappings. (English) Zbl 1361.65013
Summary: This paper provides the analysis of a fast iterative method for finding sparse solutions to underdetermined linear systems. It is based on a fixed-point iteration scheme which combines nonconvex Lipschitzian-type mappings with canonical orthogonal projectors. The former are aimed at uniformly enhancing the sparsity level by shrinkage effects, the latter are used to project back onto the space of feasible solutions. The iterative process is driven by an increasing sequence of a scalar parameter that mainly contributes to approach the sparsest solutions. It is shown that the minima are locally asymptotically stable for a specific smooth \(\ell_0\)-norm. Furthermore, it is shown that the points yielded by this iterative strategy are related to the optimal solutions measured in terms of a suitable smooth \(\ell_1\)-norm. Numerical simulations on phase transition show that the performances of the proposed technique overcome those yielded by well known methods for sparse recovery.
MSC:
| 65F10 | Iterative numerical methods for linear systems |
| 65F50 | Computational methods for sparse matrices |
| 90C27 | Combinatorial optimization |
Keywords:
underdetermined linear systems; sparse recovery; Lipschitzian mappings; smooth \(\ell_0\)-norm; smooth \(\ell_1\)-norm; fixed-point iteration scheme; combinatorial optimization; numerical examples; fast iterative method; sparse solutionsReferences:
| [1] | Donoho, D. L., For most large underdetermined systems of linear equations the minimal \(\ell^1\)-norm solution is also the sparsest solution, Comm. Pure Appl. Math., 59, 797-829 (2004) · Zbl 1113.15004 |
| [2] | Chen, S. S.; Donoho, D. L.; Saunders, Michael A., Atomic decomposition by basis pursuit, SIAM J. Sci. Comput., 20, 1, 33-61 (1998) · Zbl 0919.94002 |
| [3] | Candès, E.; Tao, T., Decoding by linear programming, IEEE Trans. Inform. Theory, 52, 5406-5425 (2006) · Zbl 1309.94033 |
| [4] | Natarajan, B. K., Sparse approximate solutions to linear systems, SIAM J. Comput., 24, 227-234 (1995) · Zbl 0827.68054 |
| [5] | Mallat, S.; Zhang, Z., Matching pursuit with time-frequency dictionaries, IEEE Trans. Signal Process., 41, 3397-3415 (1993) · Zbl 0842.94004 |
| [6] | Needell, D.; Tropp, J. A., Cosamp: iterative signal recovery from incomplete and inaccurate samples, Appl. Comput. Harmon. Anal., 26, 3, 301-321 (2009) · Zbl 1163.94003 |
| [7] | Tropp, J.; Gilbert, A., Signal recovery from random measurements via orthogonal matching pursuit, IEEE Trans. Inform. Theory, 53, 12, 4655-4666 (2007) · Zbl 1288.94022 |
| [8] | Mohimani, H.; Babaie-Zadeh, M.; Jutten, C., A fast approach for overcomplete sparse decomposition based on smoothed \(\ell^0\) norm, IEEE Trans. Signal Process., 57, 1, 289-301 (2009) · Zbl 1391.94325 |
| [9] | Elad, M., Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing (2010), Springer · Zbl 1211.94001 |
| [10] | Trevor, B. E.; Hastie, T.; Johnstone, I.; Tibshirani, R., Least angle regression, Ann. Stat., 32, 407-499 (2002) · Zbl 1091.62054 |
| [11] | Hale, E. T.; Yin, W.; Zhang, Y., Fixed-point continuation for l1-minimization: methodology and convergence, SIAM J. Optim., 19, 3, 1107-1130 (2008) · Zbl 1180.65076 |
| [12] | Yin, W.; Osher, S.; Goldfarb, D.; Darbon, J., Bregman iterative algorithms for l1-minimization with applications to compressed sensing, SIAM J. Imaging Sci., 1, 1, 143-168 (2008) · Zbl 1203.90153 |
| [13] | 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, 1, 34-81 (2009) · Zbl 1178.68619 |
| [14] | Tropp, J.; Wright, S., Computational methods for sparse solution of linear inverse problems, Proc. IEEE, 98, 6, 948-958 (2010) |
| [15] | Zhao, Y.; Li, D., Computational methods for sparse solution of linear inverse problems, SIAM J. Optim., 22, 3, 1065-1088 (2012) · Zbl 1261.65042 |
| [16] | Donoho, D.; Elad, M., Optimality sparse representation in general (non-orthogonal) dictionaries via l1 minimization, Proc. Natl. Acad. Sci. USA, 100, 2197-2202 (2003) · Zbl 1064.94011 |
| [17] | Elad, M.; Bruckstein, A., A generalized uncertainty principle and sparse representation in pairs of bases, IEEE Trans. Inform. Theory, 48, 2558-2567 (2002) · Zbl 1062.15001 |
| [18] | Candès, E.; Romberg, J.; Tao, T., Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inform. Theory, 52, 489-509 (2006) · Zbl 1231.94017 |
| [19] | Candès, E.; Romberg, J.; Tao, T., Stable signal recovery from incomplete and inaccurate measurements, Comm. Pure Appl. Math., 59, 8, 1207-1223 (2006) · Zbl 1098.94009 |
| [20] | Candès, E., Compressive sampling, (Proc. Int. Congr. of Mathematicians, vol. III. Proc. Int. Congr. of Mathematicians, vol. III, Madrid, Spain (2006)), 1433-1452 · Zbl 1130.94013 |
| [21] | Cohen, A.; Dahmen, W.; Devore, R., Compressed sensing and best k-term approximation, J. Amer. Math. Soc., 22, 211-231 (2009) · Zbl 1206.94008 |
| [22] | Adamo, A.; Grossi, G., A fixed-point iterative schema for error minimization in k-sparse decomposition, (2011 IEEE Int. Symp. on Signal Processing and Information Technology. 2011 IEEE Int. Symp. on Signal Processing and Information Technology, ISSPIT (2011)), 167-172 |
| [23] | Adamo, A.; Grossi, G.; Lanzarotti, R., Local features and sparse representation for face recognition with partial occlusions, (2013 IEEE Int. Conf. on Image Processing. 2013 IEEE Int. Conf. on Image Processing, ICIP (2013)), 3008-3012 |
| [24] | Adamo, A.; Grossi, G.; Lanzarotti, R.; Lin, J., ECG compression retaining the best natural basis k-coefficients via sparse decomposition, Biomed. Signal Process. Control, 15, 11-17 (2015) |
| [25] | Benyamini, Y.; Lindenstrauss, J., Geometric Nonlinear Functional Analysis, vol. 1, Amer. Math. Soc. Colloq. Publ., vol. 48 (1998), American Mathematical Soc. |
| [26] | Wiggins, S., Introduction to Applied Nonlinear Dynamical Systems and Chaos (2003), Springer · Zbl 1027.37002 |
| [27] | Chen, P.-Y.; Selesnick, I. W., Translation-invariant shrinkage/thresholding of group sparse signals, Signal Process., 94, 476-489 (2014) |
| [28] | Chartrand, R., Shrinkage mappings and their induced penalty functions, (IEEE Int. Conf. on Acoustics, Speech and Signal Processing. IEEE Int. Conf. on Acoustics, Speech and Signal Processing, ICASSP 2014, Florence, Italy, May 4-9, 2014 (2014), IEEE), 1026-1029 |
| [29] | Donoho, D. L.; Johnstone, I. M., Ideal spatial adaptation by wavelet shrinkage, Biometrika, 81, 3, 425-455 (1994) · Zbl 0815.62019 |
| [30] | Banach, S., Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales, Fund. Math., 3, 1, 133-181 (1922) · JFM 48.0201.01 |
| [31] | Donoho, D. L., De-noising by soft-thresholding, IEEE Trans. Inform. Theory, 41, 3, 613-627 (1995) · Zbl 0820.62002 |
| [32] | Mallat, S., A Wavelet Tour of Signal Processing: The Sparse Way (2008), Academic Press |
| [33] | Gribonval, R.; Nielsen, M., Highly sparse representations from dictionaries are unique and independent of the sparseness measure, Appl. Comput. Harmon. Anal., 22, 3, 335-355 (2007) · Zbl 1133.94011 |
| [34] | Brent, R.; Zimmermann, P., Modern Computer Arithmetic (2010), Cambridge University Press: Cambridge University Press New York, NY, USA |
| [35] | Donoho, D. L.; Tunner, J., Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing, Philos. Trans. A Math. Phys. Eng. Sci., 367, 1906, 4273-4293 (2009) · Zbl 1185.94029 |
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.
