Piecewise-polynomial signal segmentation using convex optimization

Pavel Rajmic; Michaela Novosadová; Marie Daňková

Kybernetika (2017)

  • Volume: 53, Issue: 6, page 1131-1149
  • ISSN: 0023-5954

Abstract

top
A method is presented for segmenting one-dimensional signal whose independent segments are modeled as polynomials, and which is corrupted by additive noise. The method is based on sparse modeling, the main part is formulated as a convex optimization problem and is solved by a proximal splitting algorithm. We perform experiments on simulated and real data and show that the method is capable of reliably finding breakpoints in the signal, but requires careful tuning of the regularization parameters and internal parameters. Finally, potential extensions are discussed.

How to cite

top

Rajmic, Pavel, Novosadová, Michaela, and Daňková, Marie. "Piecewise-polynomial signal segmentation using convex optimization." Kybernetika 53.6 (2017): 1131-1149. <http://eudml.org/doc/294464>.

@article{Rajmic2017,
abstract = {A method is presented for segmenting one-dimensional signal whose independent segments are modeled as polynomials, and which is corrupted by additive noise. The method is based on sparse modeling, the main part is formulated as a convex optimization problem and is solved by a proximal splitting algorithm. We perform experiments on simulated and real data and show that the method is capable of reliably finding breakpoints in the signal, but requires careful tuning of the regularization parameters and internal parameters. Finally, potential extensions are discussed.},
author = {Rajmic, Pavel, Novosadová, Michaela, Daňková, Marie},
journal = {Kybernetika},
keywords = {signal segmentation; denoising; sparsity; piecewise-polynomial signal model; convex optimization},
language = {eng},
number = {6},
pages = {1131-1149},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Piecewise-polynomial signal segmentation using convex optimization},
url = {http://eudml.org/doc/294464},
volume = {53},
year = {2017},
}

TY - JOUR
AU - Rajmic, Pavel
AU - Novosadová, Michaela
AU - Daňková, Marie
TI - Piecewise-polynomial signal segmentation using convex optimization
JO - Kybernetika
PY - 2017
PB - Institute of Information Theory and Automation AS CR
VL - 53
IS - 6
SP - 1131
EP - 1149
AB - A method is presented for segmenting one-dimensional signal whose independent segments are modeled as polynomials, and which is corrupted by additive noise. The method is based on sparse modeling, the main part is formulated as a convex optimization problem and is solved by a proximal splitting algorithm. We perform experiments on simulated and real data and show that the method is capable of reliably finding breakpoints in the signal, but requires careful tuning of the regularization parameters and internal parameters. Finally, potential extensions are discussed.
LA - eng
KW - signal segmentation; denoising; sparsity; piecewise-polynomial signal model; convex optimization
UR - http://eudml.org/doc/294464
ER -

References

top
  1. Angelosante, D., Giannakis, G. B., 10.1186/1687-6180-2012-70, EURASIP J. Advances Signal Process. 2012 (2012), 1, 1-16. DOI10.1186/1687-6180-2012-70
  2. Bleakley, K., Vert, J. P., The group fused Lasso for multiple change-point detection., Technical Report. 
  3. Bruckstein, A. M., Donoho, D. L., Elad, M., 10.1137/060657704, SIAM Rev.51 (2009), 1, 34-81. MR2481111DOI10.1137/060657704
  4. Candes, E. J., Wakin, M. B., 10.1109/msp.2007.914731, IEEE Signal Process. Magazine 25 (2008), 2, 21-30. DOI10.1109/msp.2007.914731
  5. Candes, E. J., Wakin, M. B., Boyd, S. P., 10.1007/s00041-008-9045-x, J. Fourier Analysis Appl. 14 (2008), 877-905. MR2461611DOI10.1007/s00041-008-9045-x
  6. Chambolle, A., Pock, T., 10.1007/s10851-010-0251-1, J. Math. Imaging Vision 40 (2011), 1, 120-145. MR2782122DOI10.1007/s10851-010-0251-1
  7. Chartrand, R., 10.1109/icassp.2014.6853752, In: IEEE International Conference on Acoustics, Speech, and Signal Processing 2014. DOI10.1109/icassp.2014.6853752
  8. Combettes, P., Pesquet, J., 10.1007/978-1-4419-9569-8_10, In: Fixed-Point Algorithms for Inverse Problems in Science and Engineering 2011, pp. 185-212. MR2858838DOI10.1007/978-1-4419-9569-8_10
  9. Condat, L., 10.1109/lsp.2014.2322123, Signal Process. Lett., IEEE 21 (2014), 8, 985-989. DOI10.1109/lsp.2014.2322123
  10. Donoho, D. L., Elad, M., 10.1073/pnas.0437847100, Proc. National Acad. Sci. 100 (2003), 5, 2197-2202. MR1963681DOI10.1073/pnas.0437847100
  11. Elad, M., Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing., Springer 2010. MR2677506
  12. Fornasier, M., ed., 10.1515/9783110226157, De Gruyter, Berlin, Boston 2010. MR2731598DOI10.1515/9783110226157
  13. Frecon, J., Pustelnik, N., Abry, P., Condat, L., 10.1109/tsp.2016.2516962, IEEE Trans. Signal Process. 64 (2016), 9, 2355-2364. MR3480014DOI10.1109/tsp.2016.2516962
  14. Giryes, R., Elad, M., Bruckstein, A. M., 10.1137/140998585, SIAM J. Imaging Sci. 8 (2015), 3, 2133-2159. MR3402782DOI10.1137/140998585
  15. Nettest, GN, Understanding OTDR., GN Nettest (2000). 
  16. Golub, G. H., Loan, C. F. V., Matrix Computations. Third edition., Johns Hopkins University Press 1996. MR1417720
  17. Kim, S. J., Koh, K., Boyd, S., Gorinevsky, D., 10.1137/070690274, SIAM Rev. 51 (2009), 2, 339-360. MR2505584DOI10.1137/070690274
  18. Komodakis, N., Pesquet, J., 10.1109/msp.2014.2377273, IEEE Signal Process. Magazine 32 (2015), 6, 31-54. DOI10.1109/msp.2014.2377273
  19. Kowalski, M., 10.1016/j.acha.2009.05.006, Applied Comput. Harmonic Analysis 27 (2009), 3, 303-324. MR2559729DOI10.1016/j.acha.2009.05.006
  20. Kowalski, M., Torrésani, B., Structured Sparsity: from Mixed Norms to Structured Shrinkage., In: SPARS'09 - Signal Processing with Adaptive Sparse Structured Representations (R. Gribonval, ed.), Inria Rennes - Bretagne Atlantique 2009, pp. 1-6. 
  21. Kutyniok, G., Lim, W. Q., 10.1016/j.jat.2011.06.005, J. Approx. Theory 163 (2011), 11, 1564-1589. MR2832720DOI10.1016/j.jat.2011.06.005
  22. Levin, D., 10.1007/s10543-014-0522-0, BIT Numerical Math. 55 (2015), 3, 781-796. MR3401813DOI10.1007/s10543-014-0522-0
  23. Neubauer, J., Veselý, V., 10.1049/pbce065e_ch7, Informatica 22 (2011), 1, 149-164. MR2885664DOI10.1049/pbce065e_ch7
  24. Novosadová, M., Rajmic, P., 10.1109/icumt.2016.7765379, In: Proc. 8th International Congress on Ultra Modern Telecommunications and Control Systems, Lisabon 2016, pp. 317-322. DOI10.1109/icumt.2016.7765379
  25. Novosadová, M., Rajmic, P., 10.1109/tsp.2017.8076092, In: Proc. 40th International Conference on Telecommunications and Signal Processing (TSP), Barcelona 2017, pp. 769-774. DOI10.1109/tsp.2017.8076092
  26. Šorel, M., Šroubek, F., 10.1016/j.dsp.2016.04.012, Digital Signal Process. 55 (2016), 44-51. DOI10.1016/j.dsp.2016.04.012
  27. Perraudin, N., Shuman, D. I., Puy, G., Vandergheynst, P., Unlocbox A Matlab convex optimization toolbox using proximal splitting methods (2014). 
  28. Pock, T., Fast Total Variation for Computer Vision., Dissertation Thesis, Graz University of Technology 2008. 
  29. Rajmic, P., 10.1109/icecs.2003.1301820, In: Electronics, Circuits and Systems, 2003. ICECS 2003. Proc. 10th IEEE International Conference 2 (2003), pp. 455-458. DOI10.1109/icecs.2003.1301820
  30. Rajmic, P., Novosadová, M., 10.1109/tsp.2016.7760941, In: Proc. 39th International Conference on Telecommunications and Signal Processing, Brno University of Technology 2016, pp. 550-554. DOI10.1109/tsp.2016.7760941
  31. Selesnick, I. W., Arnold, S., Dantham, V. R., 10.1109/tsp.2012.2214219, IEEE Trans. Signal Process. 60 (2012), 12, 6305-6318. MR3006421DOI10.1109/tsp.2012.2214219
  32. Shem-Tov, S., Rosman, G., Adiv, G., Kimmel, R., Bruckstein, A. M., 10.1007/978-3-642-34141-0_17, In: Mathematics and Visualization, Springer 2012, pp. 379-405. MR3075841DOI10.1007/978-3-642-34141-0_17
  33. Starck, J. L., Candes, E. J., Donoho, D. L., 10.1109/tip.2002.1014998, IEEE Trans. Image Process. 11 (2002), 6, 670-684. MR1929403DOI10.1109/tip.2002.1014998
  34. Tibshirani, R., Regression shrinkage and selection via the LASSO., J. Royal Statist. Soc. Ser. B (Methodological) 58 (1996), 1, 267-288. MR1379242
  35. Tibshirani, R. J., 10.1214/13-aos1189, Ann. Statist. 42 (2014), 1, 285-323. MR3189487DOI10.1214/13-aos1189
  36. Tropp, J., 10.1109/tit.2004.834793, IEEE Trans. Inform. Theory 50 (2004), 2231-2242. MR2097044DOI10.1109/tit.2004.834793
  37. Zhang, B., Geng, J., Lai, L., 10.1109/tsp.2015.2411220, IEEE Trans. Signal Process. 63 (2015), 9, 2209-2224. MR3331995DOI10.1109/tsp.2015.2411220

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.