×

Signal decomposition using masked proximal operators. (English) Zbl 1508.94029

In this article, the authors consider the problem of decomposing a vector time series signal into components with different characteristics, such as smooth, periodic, nonnegative, or sparse. They introduce a simple and general framework that unifies many existing approaches, where components are described by their loss functions. After the loss functions are chosen, the signal decomposition can be carried out by minimizing the sum of losses of the components (subject to the constraints). Note that the framework includes many well-known problems as specific instances, and it enables the design of newer, more complex components classes than traditional simple ones. By summarizing and clarifying prior results, the authors give two distributed optimization methods for computing the decomposition, which find the optimal decomposition when the component class loss functions are convex and are good heuristics when they are not. Both methods require only the masked proximal operator of each of the component loss functions, a generalization of the well-known proximal operator that handles missing entries in its argument. Both methods are distributed, i.e., handle each component separately. In addition, the tractable methods are derived for evaluating the masked proximal operators of some loss functions. The monograph is accompanied by an open-source software implementation called OSD, short for ‘Optimization(-based) Signal Decomposition’, available at https://github.com/cvxgrp/signal-decomposition.

MSC:

94A12 Signal theory (characterization, reconstruction, filtering, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] A. Agrawal, R. Verschueren, S. Diamond, and S. Boyd, “A rewrit-ing system for convex optimization problems”, Journal of Control and Decision, vol. 5, no. 1, 2018, pp. 42-60.
[2] D. Amelunxen, M. Lotz, M. B. McCoy, and J. A. Tropp, “Living on the edge: Phase transitions in convex programs with random data”, Information and Inference, vol. 3, no. 3, 2014, pp. 224-294. doi: 10.1093/imaiai/iau005. · Zbl 1339.90251
[3] O. Anderson, “On the logic of the decomposition of statistical series into separate components”, Journal of the Royal Statistical Society, vol. 90, no. 3, 1927, pp. 548-569. doi: 10.2307/2341204. · JFM 52.0530.01
[4] L. Avila and J. Cangialosi, “Tropical cyclone report for hurricane Irene (AL092011)”, NOAA National Hurricane Center, 2013, url: https://www.nhc.noaa.gov/data/tcr/AL092011_Irene.pdf.
[5] F. Bach, “Structured sparsity-inducing norms through submod-ular functions”, in Advances in Neural Information Processing Systems, J. Lafferty, C. Williams, J. Shawe-Taylor, R. Zemel, and A. Culotta, Eds., vol. 23, Curran Associates, Inc., 2010. doi: 10.48550/arXiv.1008.4220.
[6] R. Baillie and S.-K. Chung, “Modeling and forecasting from trend-stationary long memory models with applications to climatology”, International Journal of Forecasting, vol. 18, no. 2, 2002, pp. 215-226. doi: 10.1016/S0169-2070(01)00154-6.
[7] R. G. Baraniuk, V. Cevher, M. F. Duarte, and C. Hegde, “Model-based compressive sensing”, IEEE Transactions on Information Theory, vol. 56, no. 4, 2010, pp. 1982-2001. doi: 10.1109/TIT. 2010.2040894. · Zbl 1366.94215
[8] A. Beck and L. Tetruashvili, “On the convergence of block coor-dinate descent type methods”, SIAM Journal on Optimization, vol. 23, no. 4, 2013, pp. 2037-2060. doi: 10.1137/120887679. · Zbl 1297.90113
[9] D. Bertsekas, Nonlinear Programming: Third Edition. Nashua, NH: Athena Scientific, 2016. · Zbl 1360.90236
[10] M. Best and N. Chakravarti, “Active set algorithms for isotonic regression; a unifying framework”, Mathematical Programming, vol. 47, 1990, pp. 425-439. doi: 10.1007/BF01580873. · Zbl 0715.90085
[11] ”February 9-10, 2010 North American blizzard”, Wikipedia, url: https://en.wikipedia.org/w/index.php?title=February_9
[12] E2
[13] ”December 26-27th 2010 blizzard”, National Weather Service, url: https://www.weather.gov/okx/storm12262010.
[14] ”January 26-27 2015 blizzard”, National Weather Service, url: https://www.weather.gov/okx/Blizzard_01262715.
[15] ”January 31-February 2 2021 winter storm”, National Weather Service, url: https://www.weather.gov/okx/WinterStormJan31_Feb22021.
[16] P. Bloomfield, “Trends in global temperature”, Climatic Change, vol. 21, no. 1, 1992, pp. 1-16. doi: 10.1007/BF00143250.
[17] P. Bloomfield and D. Nychka, “Climate spectra and detecting climate change”, Climatic Change, vol. 21, no. 3, 1992, pp. 275-287. doi: 10.1007/BF00139727.
[18] C. Bouman and K. Sauer, “A generalized Gaussian image model for edge-preserving MAP estimation”, IEEE Transactions on Image Processing, vol. 2, no. 3, 1993, pp. 296-310. doi: 10.1109/ 83.236536.
[19] M. Boyd, “High-speed monitoring of multiple grid-connected pho-tovoltaic array configurations”, NIST Technical Note 1896, 2015. doi: 10.6028/NIST.TN.1896.
[20] M. Boyd, T. Chen, and B. Doughert, NIST Campus Photovoltaic (PV) Arrays and Weather Station Data Sets. National Institute of Standards and Technology, 2017. doi: 10.18434/M3S67G.
[21] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, “Dis-tributed optimization and statistical learning via the alternating direction method of multipliers”, Foundations and Trends in Ma-chine Learning, vol. 3, no. 1, 2011, pp. 1-122. doi: 10 . 1561 / 2200000016. · Zbl 1229.90122
[22] S. Boyd and L. Vandenberghe, Convex optimization. Cambridge University Press, 2009.
[23] S. Boyd and L. Vandenberghe, Introduction to Applied Linear Algebra. Cambridge university press, 2018. · Zbl 1406.15001
[24] E. J. Candès, X. Li, Y. Ma, and J. Wright, “Robust principal component analysis?”, Journal of the ACM, vol. 58, no. 3, 2011, pp. 1-37. doi: 10.1145/1970392.1970395. · Zbl 1327.62369
[25] E. J. Candès and B. Recht, “Exact matrix completion via convex optimization”, Foundations of Computational Mathematics, vol. 9, no. 6, 2009, pp. 717-772. doi: 10.1007/s10208-009-9045-5. · Zbl 1219.90124
[26] V. Chandrasekaran, B. Recht, P. A. Parrilo, and A. S. Willsky, “The convex geometry of linear inverse problems”, Foundations of Computational Mathematics, vol. 12, no. 6, 2010, pp. 805-849. doi: 10.1007/s10208-012-9135-7. · Zbl 1280.52008
[27] J. F. Claerbout and F. Muir, “Robust modeling with erratic data”, Geophysics, vol. 38, no. 5, 1973, pp. 826-844. doi: 10.1190/1. 1440378.
[28] R. Cleveland, W. Cleveland, J. McRae, and I. Terpenning, “STL: A seasonal-trend decomposition procedure based on loess”, Journal of Official Statistics, vol. 6, no. 1, 1990, pp. 3-73, url: https: / / www . proquest . com / scholarly -journals / stl -seasonal -trend -decomposition-procedure-based/docview/1266805989/se-2.
[29] P. Combettes and J. Pesquet, “Proximal splitting methods in signal processing”, Springer Optimization and Its Applications, vol. 49, 2011, pp. 185-212. doi: 10.1007/978-1-4419-9569-8_10. · Zbl 1242.90160
[30] A. Cuomo, “Governor Cuomo signs the ”New York State on PAUSE’ executive order, March 20, 2020“, New York Governor”s Press Office, url: https://web.archive.org/web/20200328191630/ https://www.governor.ny.gov/news/governor-cuomo-signs-new-york-state-pause-executive-order.
[31] S. Diamond and S. Boyd, “CVXPY: A Python-embedded modeling language for convex optimization”, Journal of Machine Learning Research, vol. 17, no. 83, 2016, pp. 1-5. · Zbl 1360.90008
[32] D. L. Donoho and X. Huo, “Uncertainty principles and ideal atomic decomposition”, IEEE Transactions on Information The-ory, vol. 47, no. 7, 2001, pp. 2845-2862. doi: 10.1109/18.959265. · Zbl 1019.94503
[33] R. Farebrother, “Adrien-Marie Legendre”, in Statisticians of the Centuries, C. Heyde, E. Seneta, P. Crépel, S. Fienberg, and J. Gani, Eds., New York, NY: Springer, 2001, pp. 101-104. doi: 10.1007/978-1-4613-0179-0_20. · Zbl 1016.01025
[34] M. Fischler and R. Bolles, “Random sample consensus: A paradigm for model fitting with applications to image analy-sis and automated cartography”, Communications of the ACM, vol. 24, no. 6, 1981, pp. 381-395. doi: 10.1145/358669.358692.
[35] E. Franklin, “Solar photovoltaic (PV) system components”, The University of Arizona College of Agriculture & Life Sciences, 2018, pp. 1-8, url: https://projects.sare.org/wp-content/uploads/ az1742-2017.pdf.
[36] D. Gabay and B. Mercier, “A dual algorithm for the solution of nonlinear variational problems via finite element approximation”, Computers and Mathematics with Applications, vol. 2, no. 1, 1976, pp. 17-40. doi: 10.1016/0898-1221(76)90003-1. · Zbl 0352.65034
[37] R. Glowinski and A. Marroco, “Sur l”approximation, par elements finis d’ordre un, et la resolution, par penalisation-dualité, d’une classe de problems de Dirichlet non lineares“, Revue Française d”Automatique, Informatique, et Recherche Opérationelle, vol. 9, no. R-2, 1975, pp. 41-76. doi: 10.1051/m2an/197509R200411. · Zbl 0368.65053
[38] S. Greenland and M. Longnecker, “Methods for trend estimation from summarized dose-response data, with applications to meta-analysis”, American Journal of Epidemiology, vol. 135, no. 11, 1992, pp. 1301-1309. doi: 10.1093/oxfordjournals.aje.a116237. References
[39] S. Grotzinger and C. Witzgall, “Projections onto order sim-plexes”, Applied Mathematics and Optimization, vol. 12, no. 1, 1984, pp. 247-270. doi: 10.1007/BF01449044. · Zbl 0577.65049
[40] T. Hastie, R. Tibshirani, and J. Friedman, The Elements of Statis-tical Learning: Data Mining, Inference, and Prediction. Springer Science & Business Media, 2013.
[41] R. Hodrick and E. Prescott, “Postwar U.S. business cycles: An empirical investigation”, Journal of Money, Credit and Banking, vol. 29, no. 1, 1997, pp. 1-16. doi: 10.2307/2953682.
[42] A. Hoerl and R. Kennard, “Ridge regression: Biased estimation for nonorthogonal problems”, Technometrics, vol. 12, no. 1, 1970, pp. 55-67. doi: 10.1080/00401706.1970.10488634. · Zbl 0202.17205
[43] P. Huber, “Robust estimation of a location parameter”, The Annals of Mathematical Statistics, vol. 35, no. 1, 1964, pp. 73-101. doi: 10.1214/aoms/1177703732. · Zbl 0136.39805
[44] P. Huber, Robust statistics, vol. 523. Hoboken, NJ: John Wiley & Sons, 1981. doi: 10.1002/0471725250. · Zbl 0536.62025
[45] R. Hyndman and G. Athanasopoulos, Forecasting: principles and practice. OTexts: Melbourne, Australia, 2018.
[46] P. Ineichen, “A broadband simplified version of the Solis clear sky model”, Solar Energy, vol. 82, no. 8, 2008, pp. 758-762. doi: 10.1016/j.solener.2008.02.009.
[47] R. Inman, Y. Chu, and C. Coimbra, “Cloud enhancement of global horizontal irradiance in California and Hawaii”, Solar Energy, vol. 130, 2016, pp. 128-138. doi: 10.1016/j.solener.2016.02.011.
[48] S.-J. Kim, K. Koh, S. Boyd, and D. Gorinevsky, “L1 trend fil-tering”, SIAM Review, vol. 51, no. 2, 2009, pp. 339-360. doi: 10.1137/070690274. · Zbl 1171.37033
[49] R. Koenker and G. Bassett, “Regression quantiles”, Econometrica, vol. 46, no. 1, 1978, p. 33. doi: 10.2307/1913643. · Zbl 0373.62038
[50] R. Koenker and K. F. Hallock, “Quantile regression”, Journal of Economic Perspectives, vol. 15, no. 4, 2001, pp. 143-156. doi: 10.1257/jep.15.4.143.
[51] C. Leser, “A simple method of trend construction”, Journal of the Royal Statistical Society: Series B (Methodological), vol. 23, no. 1, 1961, pp. 91-107. doi: 10.1111/j.2517-6161.1961.tb00393.x. · Zbl 0099.35702
[52] S. Levitt, “Understanding why crime fell in the 1990s: Four factors that explain the decline and six that do not”, Journal of Economic Perspectives, vol. 18, no. 1, 2004, pp. 163-190. doi: 10 . 1257 / 089533004773563485.
[53] W. Link and F. Sauer, “Estimating equations estimates of trends”, Bird Populations, vol. 2, 1994, pp. 23-32, url: https://bmeyers. github.io/assets/link-1994.pdf.
[54] S. Mallat, A Wavelet Tour of Signal Processing. Elsevier, 2009, pp. 20-41. doi: 10.1016/B978-0-12-374370-1.X0001-8. · Zbl 1170.94003
[55] M. B. McCoy, V. Cevher, Q. T. Dinh, A. Asaei, and L. Baldas-sarre, “Convexity in source separation: Models, geometry, and algorithms”, IEEE Signal Processing Magazine, vol. 31, no. 3, 2014, pp. 87-95. doi: 10.1109/MSP.2013.2296605.
[56] M. B. McCoy and J. A. Tropp, “Sharp recovery bounds for con-vex demixing, with applications”, Foundations of Computational Mathematics, vol. 14, no. 3, 2014, pp. 503-567. doi: 10.1007/ s10208-014-9191-2. · Zbl 1312.94016
[57] J.-J. Moreau, “Fonctions convexes duales et points proximaux dans un espace hilbertien”, Reports of the Paris Academy of Sciences, Series A, vol. 255, 1962, pp. 2897-2899. · Zbl 0118.10502
[58] ”Hourly traffic on Metropolitan Transportation Authority (MTA) bridges and tunnels”, NY Open Data, url: https://data.ny.gov/ Transportation/Hourly-Traffic-on-Metropolitan-Transportation-Auth/qzve-kjga.
[59] O. Neugebauer, The Exact Sciences in Antiquity, ser. Acta histor-ica scientiarum naturalium et medicinalium. Dover Publications, 1969, url: https://books.google.com/books?id=JVhTtVA2zr8C.
[60] A. Oppenheim and R. Schafer, Discrete-time Signal Processing, ser. Prentice-Hall signal processing series. United Kingdom: Pear-son, 2010.
[61] D. Osborn, “Moving average detrending and the analysis of busi-ness cycles”, Oxford Bulletin of Economics and Statistics, vol. 57, no. 4, 1995, pp. 547-558. doi: 10.1111/j.1468-0084.1995.tb00039.x.
[62] N. Parikh and S. Boyd, “Proximal algorithms”, Foundations and Trends in Optimization, vol. 1, no. 3, 2014, pp. 127-239. doi: 10.1561/2400000003.
[63] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay, “Scikit-learn: Machine learning in Python”, Journal of Machine Learning Research, vol. 12, 2011, pp. 2825-2830, url: https://jmlr.org/papers/v12/pedregosa11a.html. · Zbl 1280.68189
[64] D. Phillips, “A technique for the numerical solution of certain integral equations of the first kind”, Journal of the ACM, vol. 9, no. 1, 1962, pp. 84-97. doi: 10.1145/321105.321114. · Zbl 0108.29902
[65] R. Poliquin and R. Rockafellar, “Prox-regular functions in vari-ational analysis”, Transactions of the American Mathematical Society, vol. 348, no. 5, 1996, pp. 1805-1838. doi: 10.1090/S0002-9947-96-01544-9. · Zbl 0861.49015
[66] P. Richtárik and M. Takáč, “Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function”, Mathematical Programming, vol. 144, no. 1-2, 2014, pp. 1-38. doi: 10.1007/s10107-012-0614-z. · Zbl 1301.65051
[67] R. Rockafellar, Convex Analysis. Princeton University Press, 1970. · Zbl 0193.18401
[68] R. Sah, “Caltrans traffic census program”, California Department of Transportation, url: https://dot.ca.gov/programs/traffic-operations/census.
[69] P. Sen, “Estimates of the regression coefficient based on Kendall”s Tau”, Journal of the American Statistical Association, vol. 63, no. 324, 1968, pp. 1379-1389. doi: 10 . 1080 / 01621459 . 1968 . 10480934. · Zbl 0167.47202
[70] K. Singleton, “Econometric issues in the analysis of equilibrium business cycle models”, Journal of Monetary Economics, vol. 21, no. 2-3, 1988, pp. 361-386. doi: 10.1016/0304-3932(88)90036-0.
[71] J.-L. Starck, F. Murtagh, and J. M. Fadili, Sparse image and sig-nal processing: wavelets, curvelets, morphological diversity. Cam-bridge, UK: Cambridge university press, 2010. doi: 10 . 1017 / CBO9780511730344. · Zbl 1196.94008
[72] J. Perktold, S. Seabold, and J. Taylor, “Seasonal-trend decomposi-tion using LOESS (STL)”, Statsmodels documentation, url: https: //www.statsmodels.org/dev/examples/notebooks/generated/ stl_decomposition.html.
[73] ”STL: Seasonal decomposition of time series by loess”, R doc-umentation, url: https://www.rdocumentation.org/packages/ stats/versions/3.6.2/topics/stl.
[74] ”Time series decomposition”, MathWorks documentation, url: https://www.mathworks.com/help/econ/detrending.html.
[75] P. Tans and R. Keeling, “Mauna Loa CO2 weekly mean and historical comparisons”, NOAA Global Monitoring Laboratory, Earth System Research Laboratories, url: https://gml.noaa.gov/ ccgg/trends/data.html.
[76] H. L. Taylor, S. C. Banks, and J. F. McCoy, “Deconvolution with the l1 norm”, Geophysics, vol. 44, no. 1, 1979, pp. 39-52. doi: 10.1190/1.1440921.
[77] H. Theil, “A rank-invariant method of linear and polynomial re-gression analysis”, Proceedings of the Royal Netherlands Academy of Sciences, vol. 53, 1950, Part I: 386-392, Part II: 521-525, Part III: 1397-1412. doi: 10.1007/978-94-011-2546-8_20.
[78] A. Thompson and J. Kay, “On some Bayesian choices of regular-ization parameter in image restoration”, Inverse Problems, vol. 9, no. 6, 1993, pp. 749-761. doi: 10.1088/0266-5611/9/6/011. · Zbl 0798.62011
[79] R. Tibshirani, “Regression shrinkage and selection via the lasso”, Journal of the Royal Statistical Society: Series B (Methodological), vol. 58, no. 1, 1996, pp. 267-288. doi: 10.1111/j.2517-6161.1996. tb02080.x. · Zbl 0850.62538
[80] A. Tikonov, “Solution of incorrectly formulated problems and the regularization method”, Soviet Math., vol. 4, 1963, pp. 1035-1038. · Zbl 0141.11001
[81] D. Titterington, “General structure of regularization procedures in image reconstruction”, Astronomy and Astrophysics, vol. 144, no. 2, 1985, pp. 381-387.
[82] I. Tošić and P. Frossard, “Dictionary learning”, IEEE Signal Processing Magazine, vol. 28, no. 2, 2011, pp. 27-38. doi: 10.1109/ MSP.2010.939537.
[83] R. Tsay, Analysis of Financial Time Series, ser. Wiley Series in Probability and Statistics. Hoboken, NJ, USA: John Wiley & Sons, Inc., 2005, pp. 206-215. doi: 10.1002/0471746193. · Zbl 1086.91054
[84] M. Udell, C. Horn, R. Zadeh, and S. Boyd, “Generalized low rank models”, Foundations and Trends in Machine Learning, vol. 9, no. 1, 2016, pp. 1-118. doi: 10.1561/2200000055. · Zbl 1350.68221
[85] J. Wright and Y. Ma, High-dimensional data analysis with low-dimensional models: Principles, computation, and applications. New York, NY: Cambridge University Press, 2022. · Zbl 1478.68009
[86] S. Wright, “Coordinate descent algorithms”, Mathematical Pro-gramming, vol. 151, no. 1, 2015, pp. 3-34. doi: 10.1007/s10107-015-0892-3. · Zbl 1317.49038
[87] W. B. Wu, M. Woodroofe, and G. Mentz, “Isotonic regression: Another look at the changepoint problem”, Biometrika, vol. 88, no. 3, 2001, pp. 793-804. doi: 10.1093/biomet/88.3.793. · Zbl 0985.62076
[88] M. Wytock and J. Kolter, “Contextually supervised source sepa-ration with application to energy disaggregation”, Twenty-Eighth AAAI Conference on Artificial Intelligence, vol. 28, no. 1, 2013, pp. 486-492. doi: 10.1609/aaai.v28i1.8769.
[89] A. Yurtsever, V. M., and S. Sra, “Three operator splitting with a nonconvex loss function”, 2021. doi: 10.48550/arXiv.2103.04568.
[90] K. Zhao, M. A. Wulder, T. Hu, R. Bright, Q. Wu, H. Qin, Y. Li, E. Toman, B. Mallick, X. Zhang, and M. Brown, “Detecting change-point, trend, and seasonality in satellite time series data to track abrupt changes and nonlinear dynamics: A Bayesian ensemble algorithm”, Remote Sensing of Environment, vol. 232, 2019, pp. 111-181. doi: 10.1016/j.rse.2019.04.034.
[91] H. Zou and T. Hastie, “Regularization and variable selection via the elastic net”, Journal of the royal statistical society, series B (statistical methodology), vol. 67, no. 2, 2005, pp. 301-320. doi: 10.1111/j.1467-9868.2005.00503.x. · Zbl 1069.62054
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.