| Title:
|
Piecewise-polynomial signal segmentation using convex optimization (English) |
| Author:
|
Rajmic, Pavel |
| Author:
|
Novosadová, Michaela |
| Author:
|
Daňková, Marie |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 (print) |
| ISSN:
|
1805-949X (online) |
| Volume:
|
53 |
| Issue:
|
6 |
| Year:
|
2017 |
| Pages:
|
1131-1149 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
signal segmentation |
| Keyword:
|
denoising |
| Keyword:
|
sparsity |
| Keyword:
|
piecewise-polynomial signal model |
| Keyword:
|
convex optimization |
| MSC:
|
46N10 |
| MSC:
|
47N10 |
| MSC:
|
65K10 |
| MSC:
|
90C25 |
| MSC:
|
90C30 |
| MSC:
|
90C90 |
| idZBL:
|
Zbl 06861645 |
| idMR:
|
MR3758939 |
| DOI:
|
10.14736/kyb-2017-6-1131 |
| . |
| Date available:
|
2018-02-26T11:34:58Z |
| Last updated:
|
2018-05-25 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/147089 |
| . |
| Reference:
|
[1] Angelosante, D., Giannakis, G. B.: Group Lassoing change-points in piecewise-constant AR processes..EURASIP J. Advances Signal Process. 2012 (2012), 1, 1-16. 10.1186/1687-6180-2012-70 |
| Reference:
|
[2] Bleakley, K., Vert, J. P.: The group fused Lasso for multiple change-point detection..Technical Report. |
| Reference:
|
[3] 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 (2009), 1, 34-81. MR 2481111, 10.1137/060657704 |
| Reference:
|
[4] Candes, E. J., Wakin, M. B.: An introduction to compressive sampling..IEEE Signal Process. Magazine 25 (2008), 2, 21-30. 10.1109/msp.2007.914731 |
| Reference:
|
[5] Candes, E. J., Wakin, M. B., Boyd, S. P.: Enhancing sparsity by reweighted $\ell_1$ minimization..J. Fourier Analysis Appl. 14 (2008), 877-905. MR 2461611, 10.1007/s00041-008-9045-x |
| Reference:
|
[6] Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging..J. Math. Imaging Vision 40 (2011), 1, 120-145. MR 2782122, 10.1007/s10851-010-0251-1 |
| Reference:
|
[7] Chartrand, R.: Shrinkage mappings and their induced penalty functions..In: IEEE International Conference on Acoustics, Speech, and Signal Processing 2014. 10.1109/icassp.2014.6853752 |
| Reference:
|
[8] Combettes, P., Pesquet, J.: Proximal splitting methods in signal processing..In: Fixed-Point Algorithms for Inverse Problems in Science and Engineering 2011, pp. 185-212. MR 2858838, 10.1007/978-1-4419-9569-8_10 |
| Reference:
|
[9] Condat, L.: A generic proximal algorithm for convex optimization - application to total variation minimization..Signal Process. Lett., IEEE 21 (2014), 8, 985-989. 10.1109/lsp.2014.2322123 |
| Reference:
|
[10] Donoho, D. L., Elad, M.: Optimally sparse representation in general (nonorthogonal) dictionaries via $\ell_1$ minimization..Proc. National Acad. Sci. 100 (2003), 5, 2197-2202. MR 1963681, 10.1073/pnas.0437847100 |
| Reference:
|
[11] Elad, M.: Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing..Springer 2010. MR 2677506 |
| Reference:
|
[12] Fornasier, M., ed.: Theoretical Foundations and Numerical Methods for Sparse Recovery..De Gruyter, Berlin, Boston 2010. MR 2731598, 10.1515/9783110226157 |
| Reference:
|
[13] Frecon, J., Pustelnik, N., Abry, P., Condat, L.: On-the-fly approximation of multivariate total variation minimization..IEEE Trans. Signal Process. 64 (2016), 9, 2355-2364. MR 3480014, 10.1109/tsp.2016.2516962 |
| Reference:
|
[14] Giryes, R., Elad, M., Bruckstein, A. M.: Sparsity based methods for overparameterized variational problems..SIAM J. Imaging Sci. 8 (2015), 3, 2133-2159. MR 3402782, 10.1137/140998585 |
| Reference:
|
[15] Nettest, GN: Understanding OTDR..GN Nettest (2000). |
| Reference:
|
[16] Golub, G. H., Loan, C. F. V.: Matrix Computations. Third edition..Johns Hopkins University Press 1996. MR 1417720 |
| Reference:
|
[17] Kim, S. J., Koh, K., Boyd, S., Gorinevsky, D.: $\ell_1$ trend filtering..SIAM Rev. 51 (2009), 2, 339-360. MR 2505584, 10.1137/070690274 |
| Reference:
|
[18] Komodakis, N., Pesquet, J.: 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. 10.1109/msp.2014.2377273 |
| Reference:
|
[19] Kowalski, M.: Sparse regression using mixed norms..Applied Comput. Harmonic Analysis 27 (2009), 3, 303-324. MR 2559729, 10.1016/j.acha.2009.05.006 |
| Reference:
|
[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. |
| Reference:
|
[21] Kutyniok, G., Lim, W. Q.: Compactly supported shearlets are optimally sparse..J. Approx. Theory 163 (2011), 11, 1564-1589. MR 2832720, 10.1016/j.jat.2011.06.005 |
| Reference:
|
[22] Levin, D.: Between moving least-squares and moving least-$\ell_1$..BIT Numerical Math. 55 (2015), 3, 781-796. MR 3401813, 10.1007/s10543-014-0522-0 |
| Reference:
|
[23] Neubauer, J., Veselý, V.: Change point detection by sparse parameter estimation..Informatica 22 (2011), 1, 149-164. MR 2885664, 10.1049/pbce065e_ch7 |
| Reference:
|
[24] Novosadová, M., Rajmic, P.: Piecewise-polynomial curve fitting using group sparsity..In: Proc. 8th International Congress on Ultra Modern Telecommunications and Control Systems, Lisabon 2016, pp. 317-322. 10.1109/icumt.2016.7765379 |
| Reference:
|
[25] Novosadová, M., Rajmic, P.: Piecewise-polynomial signal segmentation using reweighted convex optimization..In: Proc. 40th International Conference on Telecommunications and Signal Processing (TSP), Barcelona 2017, pp. 769-774. 10.1109/tsp.2017.8076092 |
| Reference:
|
[26] Šorel, M., Šroubek, F.: Fast convolutional sparse coding using matrix inversion lemma..Digital Signal Process. 55 (2016), 44-51. 10.1016/j.dsp.2016.04.012 |
| Reference:
|
[27] Perraudin, N., Shuman, D. I., Puy, G., Vandergheynst, P.: Unlocbox A Matlab convex optimization toolbox using proximal splitting methods (2014).. |
| Reference:
|
[28] Pock, T.: Fast Total Variation for Computer Vision..Dissertation Thesis, Graz University of Technology 2008. |
| Reference:
|
[29] Rajmic, P.: 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. 10.1109/icecs.2003.1301820 |
| Reference:
|
[30] Rajmic, P., Novosadová, M.: 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. 10.1109/tsp.2016.7760941 |
| Reference:
|
[31] Selesnick, I. W., Arnold, S., Dantham, V. R.: Polynomial smoothing of time series with additive step discontinuities..IEEE Trans. Signal Process. 60 (2012), 12, 6305-6318. MR 3006421, 10.1109/tsp.2012.2214219 |
| Reference:
|
[32] Shem-Tov, S., Rosman, G., Adiv, G., Kimmel, R., Bruckstein, A. M.: 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. MR 3075841, 10.1007/978-3-642-34141-0_17 |
| Reference:
|
[33] Starck, J. L., Candes, E. J., Donoho, D. L.: The curvelet transform for image denoising..IEEE Trans. Image Process. 11 (2002), 6, 670-684. MR 1929403, 10.1109/tip.2002.1014998 |
| Reference:
|
[34] Tibshirani, R.: Regression shrinkage and selection via the LASSO..J. Royal Statist. Soc. Ser. B (Methodological) 58 (1996), 1, 267-288. MR 1379242 |
| Reference:
|
[35] Tibshirani, R. J.: Adaptive piecewise polynomial estimation via trend filtering..Ann. Statist. 42 (2014), 1, 285-323. MR 3189487, 10.1214/13-aos1189 |
| Reference:
|
[36] Tropp, J.: Greed is good: Algorithmic results for sparse approximation..IEEE Trans. Inform. Theory 50 (2004), 2231-2242. MR 2097044, 10.1109/tit.2004.834793 |
| Reference:
|
[37] Zhang, B., Geng, J., Lai, L.: Multiple change-points estimation in linear regression models via sparse group lasso..IEEE Trans. Signal Process. 63 (2015), 9, 2209-2224. MR 3331995, 10.1109/tsp.2015.2411220 |
| . |
