Kybernetika 53 no. 6, 1131-1149, 2017

Piecewise-polynomial signal segmentation using convex optimization

Pavel Rajmic, Michaela Novosadová and Marie DaňkováDOI: 10.14736/kyb-2017-6-1131

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.

Keywords:

signal segmentation, denoising, sparsity, piecewise-polynomial signal model, convex optimization

Classification:

46N10, 47N10, 65K10, 90C25, 90C30, 90C90

paper.pdf

References:

  1. D. Angelosante and G. B. Giannakis: Group Lassoing change-points in piecewise-constant {AR} processes. EURASIP J. Advances Signal Process. 2012 (2012), 1, 1-16.   DOI:10.1186/1687-6180-2012-70
  2. K. Bleakley and J. P. Vert: The group fused Lasso for multiple change-point detection. Technical Report.   CrossRef
  3. A. M. Bruckstein, D. L. Donoho and M. Elad: From sparse solutions of systems of equations to sparse modeling of signals and images. SIAM Rev.51 (2009), 1, 34-81.   DOI:10.1137/060657704
  4. E. J. Candes and M. B. Wakin: An introduction to compressive sampling. IEEE Signal Process. Magazine 25 (2008), 2, 21-30.   DOI:10.1109/msp.2007.914731
  5. E. J. Candes, M. B. Wakin and S. P. Boyd: Enhancing sparsity by reweighted $\ell_1$ minimization. J. Fourier Analysis Appl. 14 (2008), 877-905.   DOI:10.1007/s00041-008-9045-x
  6. A. Chambolle and T. Pock: A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vision 40 (2011), 1, 120-145.   DOI:10.1007/s10851-010-0251-1
  7. R. Chartrand: Shrinkage mappings and their induced penalty functions. In: IEEE International Conference on Acoustics, Speech, and Signal Processing 2014.   DOI:10.1109/icassp.2014.6853752
  8. P. Combettes and J. Pesquet: Proximal splitting methods in signal processing. In: Fixed-Point Algorithms for Inverse Problems in Science and Engineering 2011, pp. 185-212.   DOI:10.1007/978-1-4419-9569-8_10
  9. L. Condat: A generic proximal algorithm for convex optimization - application to total variation minimization. Signal Process. Lett., IEEE 21 (2014), 8, 985-989.   DOI:10.1109/lsp.2014.2322123
  10. D. L. Donoho and M. Elad: Optimally sparse representation in general (nonorthogonal) dictionaries via $\ell_1$ minimization. Proc. National Acad. Sci. 100 (2003), 5, 2197-2202.   DOI:10.1073/pnas.0437847100
  11. M. Elad: Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing. Springer 2010.   CrossRef
  12. M. Fornasier and ed.: Theoretical Foundations and Numerical Methods for Sparse Recovery. De Gruyter, Berlin, Boston 2010.   DOI:10.1515/9783110226157
  13. J. Frecon, N. Pustelnik, P. Abry and L. Condat: On-the-fly approximation of multivariate total variation minimization. IEEE Trans. Signal Process. 64 (2016), 9, 2355-2364.   DOI:10.1109/tsp.2016.2516962
  14. R. Giryes, M. Elad and A. M. Bruckstein: Sparsity based methods for overparameterized variational problems. SIAM J. Imaging Sci. 8 (2015), 3, 2133-2159.   DOI:10.1137/140998585
  15. GN Nettest: Understanding OTDR. GN Nettest (2000).   CrossRef
  16. G. H. Golub and C. F. V. Loan: Matrix Computations. Third edition. Johns Hopkins University Press 1996.   CrossRef
  17. S. J. Kim, K. Koh, S. Boyd and D. Gorinevsky: $\ell_1$ trend filtering. SIAM Rev. 51 (2009), 2, 339-360.   DOI:10.1137/070690274
  18. N. Komodakis and J. Pesquet: Playing with duality: An overview of recent primal-dual approaches for solving large-scale optimization problems. IEEE Signal Process. Magazine 32 (2015), 6, 31-54.   DOI:10.1109/msp.2014.2377273
  19. M. Kowalski: Sparse regression using mixed norms. Applied Comput. Harmonic Analysis 27 (2009), 3, 303-324.   DOI:10.1016/j.acha.2009.05.006
  20. M. Kowalski and B. Torrésani: 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.   CrossRef
  21. G. Kutyniok and W. Q. Lim: Compactly supported shearlets are optimally sparse. J. Approx. Theory 163 (2011), 11, 1564-1589.   CrossRef
  22. D. Levin: Between moving least-squares and moving least-$\ell_1$. BIT Numerical Math. 55 (2015), 3, 781-796.   DOI:10.1007/s10543-014-0522-0
  23. J. Neubauer and V. Veselý: Change point detection by sparse parameter estimation. Informatica 22 (2011), 1, 149-164.   DOI:10.1049/pbce065e_ch7
  24. M. Novosadová and P. Rajmic: Piecewise-polynomial curve fitting using group sparsity. In: Proc. 8th International Congress on Ultra Modern Telecommunications and Control Systems, Lisabon 2016, pp. 317-322.   DOI:10.1109/icumt.2016.7765379
  25. M. Novosadová and P. Rajmic: Piecewise-polynomial signal segmentation using reweighted convex optimization. In: Proc. 40th International Conference on Telecommunications and Signal Processing (TSP), Barcelona 2017, pp. 769-774.   DOI:10.1109/tsp.2017.8076092
  26. M. Šorel and F. Šroubek: Fast convolutional sparse coding using matrix inversion lemma. Digital Signal Process. 55 (2016), 44-51.   DOI:10.1016/j.dsp.2016.04.012
  27. N. Perraudin, D. I. Shuman, G. Puy and P. Vandergheynst: Unlocbox A Matlab convex optimization toolbox using proximal splitting methods (2014).    CrossRef
  28. T. Pock: Fast Total Variation for Computer Vision. Dissertation Thesis, Graz University of Technology 2008.   CrossRef
  29. P. Rajmic: Exact risk analysis of wavelet spectrum thresholding rules. In: Electronics, Circuits and Systems, 2003. ICECS 2003. Proc. 10th IEEE International Conference 2 (2003), pp. 455-458.   DOI:10.1109/icecs.2003.1301820
  30. P. Rajmic and M. Novosadová: On the limitation of convex optimization for sparse signal segmentation. In: Proc. 39th International Conference on Telecommunications and Signal Processing, Brno University of Technology 2016, pp. 550-554.   DOI:10.1109/tsp.2016.7760941
  31. I. W. Selesnick, S. Arnold and V. R. Dantham: Polynomial smoothing of time series with additive step discontinuities. IEEE Trans. Signal Process. 60 (2012), 12, 6305-6318.   DOI:10.1109/tsp.2012.2214219
  32. S. Shem-Tov, G. Rosman, G. Adiv, R. Kimmel and A. M. Bruckstein: Innovations for Shape Analysis. Chap. On Globally Optimal Local Modeling: From Moving Least Squares to Over-parametrization. In: Mathematics and Visualization, Springer 2012, pp. 379-405.   DOI:10.1007/978-3-642-34141-0_17
  33. J. L. Starck, E. J. Candes and D. L. Donoho: The curvelet transform for image denoising. IEEE Trans. Image Process. 11 (2002), 6, 670-684.   DOI:10.1109/tip.2002.1014998
  34. R. Tibshirani: Regression shrinkage and selection via the LASSO. J. Royal Statist. Soc. Ser. B (Methodological) 58 (1996), 1, 267-288.   CrossRef
  35. R. J. Tibshirani: Adaptive piecewise polynomial estimation via trend filtering. Ann. Statist. 42 (2014), 1, 285-323.   DOI:10.1214/13-aos1189
  36. J. Tropp: Greed is good: Algorithmic results for sparse approximation. IEEE Trans. Inform. Theory 50 (2004), 2231-2242.   DOI:10.1109/tit.2004.834793
  37. B. Zhang, J. Geng and L. Lai: Multiple change-points estimation in linear regression models via sparse group lasso. IEEE Trans. Signal Process. 63 (2015), 9, 2209-2224.   DOI:10.1109/tsp.2015.2411220