In many applications, one may acquire a composition of several signals that may be corrupted by noise, and it is a challenging problem to reliably separate the components from one another without sacrificing significant details. Adding to the challenge, in a compressive sensing framework, one is given only an undersampled set of linear projections of the composite signal. In this study, the authors propose using the Dantzig selector model incorporating an overcomplete dictionary to separate a noisy undersampled collection of composite signals, and present an algorithm to efficiently solve the model. The Dantzig selector is a statistical approach to finding a solution to a noisy linear regression problem by minimising the ℓ₁ norm of candidate coefficient vectors while constraining the scope of the residuals. The Dantzig selector performs well in the recovery and separation of an unknown composite signal when the underlying coefficient vector is sparse. They propose a proximity operator-based algorithm to recover and separate unknown noisy undersampled composite signals using the Dantzig selector. They present numerical simulations comparing the proposed algorithm with the competing alternating direction method, and the proposed algorithm is found to be faster, while producing similar quality results. In addition, they demonstrate the utility of the proposed algorithm by applying it in various applications including the recovery of complex-valued coefficient vectors, the removal of impulse noise from smooth signals, and the separation and classification of a composition of handwritten digits.

References

1. 1)
  - 16. Donoho, D.L., Elad, M., Temlyakov, V.N.: ‘Stable recovery of sparse overcomplete representations in the presence of noise’, IEEE Trans. Inf. Theory, 2006, 52, pp. 6–18 (doi: 10.1109/TIT.2005.860430).
2. 2)
  - 9. James, G., Radchenko, P., Lv, J.: ‘DASSO: connections between the Dantzig selector and LASSO’, J. R. Stat. Soc. B, 2009, 71, pp. 127–142 (doi: 10.1111/j.1467-9868.2008.00668.x).
3. 3)
  - M. Elad , A. Bruckstein . A generalized uncertainty principle and sparse representation in pairs of bases. IEEE Trans. Inf. Theory , 9 , 2558 - 2567
4. 4)
  - 8. Ritov, Y.: ‘Discussion: the Dantzig selector: statistical estimation when p is much larger than n', Ann. Stat., 2007, 35, (6), pp. 2370–2372 (doi: 10.1214/009053607000000451).
5. 5)
  - E.J. Candes , T. Tao . Decoding by linear programming. IEEE Trans. Inf. Theory , 12 , 4203 - 4215
6. 6)
  - 29. ‘Data for MATLAB hackers’. http://www.cs.nyu.edu/roweis/data.html. Accessed 05/16/14.
7. 7)
  - 6. Friedlander, M.P., Saunders, M.A.: ‘Discussion: the Dantzig selector: statistical estimation when p is much larger than n’, Ann. Stat., 2007, 35, (6), pp. 2385–2391 (doi: 10.1214/009053607000000479).
8. 8)
  - 33. Candès, E.J., Eldar, Y.C., Needel, D., Randall, P.: ‘Compressed sensing with coherent and redundant dictionaries’, Appl. Comput. Harmon. Anal., 2011, 31, (1), pp. 59–73 (doi: 10.1016/j.acha.2010.10.002).
9. 9)
  - 28. Lu, Z., Zhang, Y.: ‘An augmented Lagrangian approach for sparse principal component analysis’, Math. Program. A, 2012, 135, (1–2), pp. 149–193 (doi: 10.1007/s10107-011-0452-4).
10. 10)
  - E. Candes , J. Romberg , T. Tao . Stable signal recovery from incomplete and inaccurate measurements. Commun. Pure Appl. Math. , 8 , 1207 - 1223
11. 11)
  - J.A. Tropp . Greed is good: algorithmic results for sparse approximation. IEEE Trans. Inf. Theory , 10 , 2231 - 2242
12. 12)
  - 29. Rauhut, H., Schnass, K., Vandergheynst, P.: ‘Compressed sensing and redundant dictionaries’, IEEE Trans. Inf. Theory, 2008, 54, (5), pp. 2210–2219 (doi: 10.1109/TIT.2008.920190).
13. 13)
  - 12. Donoho, D., Huo, X.: ‘Uncertainty principles and ideal atomic decomposition’, IEEE Trans. Inf. Theory, 2001, 47, (7), pp. 2845–2862 (doi: 10.1109/18.959265).
14. 14)
  - 5. Efron, B., Hastie, T., Tibshirani, R.: ‘Discussion: the Dantzig selector: statistical estimation when p is much larger than n', Ann. Stat., 2007, 35, (6), pp. 2358–2364 (doi: 10.1214/009053607000000433).
15. 15)
  - 26. Birgin, E.G., Martínez, J.M., Marcos, R.: ‘Nonmonotone spectral projected gradient methods on convex sets’, SIAM J. Optim., 2000, 10, (4), pp. 1196–1211 (doi: 10.1137/S1052623497330963).
16. 16)
  - 7. Meinshausen, N., Rocha, G., Yu, B.: ‘Discussion: the Dantzig selector: statistical estimation when p is much larger than n’, Ann. Stat., 2007, 35, (6), pp. 2373–2384 (doi: 10.1214/009053607000000460).
17. 17)
  - 27. Lu, Z., Pong, T.P., Zhang, Y.: ‘An alternating direction method for finding Dantzig selectors’, Comput. Stat. Data Anal., 2012, 56, pp. 4037–4046 (doi: 10.1016/j.csda.2012.04.019).
18. 18)
  - R.G. Baraniuk . Compressive sensing [lecture notes]. IEEE Signal Process. Mag. , 4 , 118 - 121
19. 19)
  - 4. Candès, E., Tao, T.: ‘Rejoinder: the Dantzig selector: statistical estimation when p is much larger than n’, Ann. Stat., 2007, 35, (6), pp. 2392–2404 (doi: 10.1214/009053607000000532).
20. 20)
  - 51. Chambolle, A., Pock, T.: ‘A first-order primal-dual algorithm for convex problems with applications to Imaging’, J. Math. Imag. Vis., 2011, 40, (1), pp. 120–145 (doi: 10.1007/s10851-010-0251-1).
21. 21)
  - 18. King, E.J., Kutyniok, G., Zhuang, X.: ‘Analysis of data separation and recovery problems using clustered sparsity’. Proc. of SPIE 8138, Wavelets and Sparsity XIV, 2011.
22. 22)
  - 10. Zheng, S., Liu, W.: ‘An experimental comparison of gene selection by Lasso and Dantzig selector for cancer classification’, Comput. Biol. Med., 2011, 41, pp. 1033–1040 (doi: 10.1016/j.compbiomed.2011.08.011).
23. 23)
  - 25. Li, Q., Micchelli, C., Shen, L., Xu, Y.: ‘A proximity algorithm accelerated by Gauss-Seidel iterations for L1/TV denoising models’, Inverse Probl., 2012, 28, (9), pp. 1–20 (doi: 10.1088/0266-5611/28/9/095003).
24. 24)
  - 16. Donoho, D.L., Elad, M.: ‘Optimally sparse representation in general (non-orthogonal) dictionaries via ℓ1 minimization’. Proc. Natl. Acad. Sci. USA 100 2197–2202, 2003.
25. 25)
  - E. Candes , T. Tao . The Dantzig selector: statistical estimation when p is much larger than n. Annals Stat. , 6 , 2313 - 2351
26. 26)
  - 2. Bickel, P.J.: ‘Discussion: the Dantzig selector: statistical estimation when p is much larger than n', Ann. Stat., 2007, 35, (6), pp. 2352–2357 (doi: 10.1214/009053607000000424).
27. 27)
  - 3. Cai, T.T., Lv, J.: ‘Discussion: the Dantzig selector: statistical estimation when p is much larger than n’, Ann. Stat., 2007, 35, (6), pp. 2365–2369 (doi: 10.1214/009053607000000442).
28. 28)
  - 23. Abolghasemi, V., Jarchi, D., Sanei, S.: ‘A robust approach for optimization of the measurement matrix in compressed sensing’. Second Int. Workshop on Cognitive Information Processing, 2010.
29. 29)
  - E.J. Candes , T. Tao . Near-optimal signal recovery from random projections: universal encoding strategies?. IEEE Trans. Inf. Theory , 12 , 5406 - 5425

Separation of undersampled composite signals using the Dantzig selector with overcomplete dictionaries

References

Related content