{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T08:17:34Z","timestamp":1761293854054,"version":"3.41.0"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2018,12,21]],"date-time":"2018-12-21T00:00:00Z","timestamp":1545350400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2018,12,21]]},"abstract":"<jats:p>We propose an algorithm to impute and forecast a time series by transforming the observed time series into a matrix, utilizing matrix estimation to recover missing values and de-noise observed entries, and performing linear regression to make predictions. At the core of our analysis is a representation result, which states that for a large class of models, the transformed time series matrix is (approximately) low-rank. In effect, this generalizes the widely used Singular Spectrum Analysis (SSA) in the time series literature, and allows us to establish a rigorous link between time series analysis and matrix estimation. The key to establishing this link is constructing a Page matrix with non-overlapping entries rather than a Hankel matrix as is commonly done in the literature (e.g., SSA). This particular matrix structure allows us to provide finite sample analysis for imputation and prediction, and prove the asymptotic consistency of our method. Another salient feature of our algorithm is that it is model agnostic with respect to both the underlying time dynamics and the noise distribution in the observations. The noise agnostic property of our approach allows us to recover the latent states when only given access to noisy and partial observations a la a Hidden Markov Model; e.g., recovering the time-varying parameter of a Poisson process without knowing that the underlying process is Poisson. Furthermore, since our forecasting algorithm requires regression with noisy features, our approach suggests a matrix estimation based method-coupled with a novel, non-standard matrix estimation error metric-to solve the error-in-variable regression problem, which could be of interest in its own right. Through synthetic and real-world datasets, we demonstrate that our algorithm outperforms standard software packages (including R libraries) in the presence of missing data as well as high levels of noise.<\/jats:p>","DOI":"10.1145\/3287319","type":"journal-article","created":{"date-parts":[[2018,12,26]],"date-time":"2018-12-26T12:39:28Z","timestamp":1545827968000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Model Agnostic Time Series Analysis via Matrix Estimation"],"prefix":"10.1145","volume":"2","author":[{"given":"Anish","family":"Agarwal","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA, USA"}]},{"given":"Muhammad Jehangir","family":"Amjad","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA, USA"}]},{"given":"Devavrat","family":"Shah","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA, USA"}]},{"given":"Dennis","family":"Shen","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA, USA"}]}],"member":"320","published-online":{"date-parts":[[2018,12,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.47"},{"key":"e_1_2_1_2_1","unstructured":"Emmanuel Abbe and Colin Sandon. 2015b. Recovering communities in the general stochastic block model without knowing the parameters. In Advances in neural information processing systems.   Emmanuel Abbe and Colin Sandon. 2015b. Recovering communities in the general stochastic block model without knowing the parameters. In Advances in neural information processing systems."},{"key":"e_1_2_1_3_1","unstructured":"Emmanuel Abbe and Colin Sandon. 2016. Detection in the stochastic block model with multiple clusters: proof of the achievability conjectures acyclic BP and the information-computation gap. Advances in neural information processing systems (2016).  Emmanuel Abbe and Colin Sandon. 2016. Detection in the stochastic block model with multiple clusters: proof of the achievability conjectures acyclic BP and the information-computation gap. Advances in neural information processing systems (2016)."},{"key":"e_1_2_1_4_1","unstructured":"Anish Agarwal Devavrat Shah Dennis Shen and Dogyoon Song. 2018. Supervised Learning in High Dimensions via Matrix Estimation. Working Paper (2018).  Anish Agarwal Devavrat Shah Dennis Shen and Dogyoon Song. 2018. Supervised Learning in High Dimensions via Matrix Estimation. Working Paper (2018)."},{"key":"e_1_2_1_5_1","unstructured":"Edo M Airoldi Thiago B Costa and Stanley H Chan. 2013. Stochastic blockmodel approximation of a graphon: Theory and consistent estimation. In Advances in Neural Information Processing Systems. 692--700.   Edo M Airoldi Thiago B Costa and Stanley H Chan. 2013. Stochastic blockmodel approximation of a graphon: Theory and consistent estimation. In Advances in Neural Information Processing Systems. 692--700."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3154489"},{"key":"e_1_2_1_7_1","unstructured":"Muhammad Jehangir Amjad Devavrat Shah and Dennis Shen. 2017. Robust synthetic control. arXiv preprint arXiv:1711.06940 (2017).  Muhammad Jehangir Amjad Devavrat Shah and Dennis Shen. 2017. Robust synthetic control. arXiv preprint arXiv:1711.06940 (2017)."},{"volume-title":"Conference on Learning Theory. 867--881","year":"2013","author":"Anandkumar Animashree","key":"e_1_2_1_8_1"},{"volume-title":"Proceedings of the 32nd International Conference on Machine Learning (ICML-15), David Blei and Francis Bach (Eds.). JMLR Workshop and Conference Proceedings, 2191--2199","year":"2015","author":"Anava Oren","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177699147"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1111\/rssb.12196"},{"key":"e_1_2_1_12_1","unstructured":"Sergei Bernstein. 1946. The Theory of Probabilities. Gastehizdat Publishing House.  Sergei Bernstein. 1946. The Theory of Probabilities. Gastehizdat Publishing House."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007586831473"},{"key":"e_1_2_1_14_1","unstructured":"Christian Borgs Jennifer Chayes Christina E Lee and Devavrat Shah. 2017. Thy Friend is My Friend: Iterative Collaborative Filtering for Sparse Matrix Estimation. In Advances in Neural Information Processing Systems. 4718--4729.   Christian Borgs Jennifer Chayes Christina E Lee and Devavrat Shah. 2017. Thy Friend is My Friend: Iterative Collaborative Filtering for Sparse Matrix Estimation. In Advances in Neural Information Processing Systems. 4718--4729."},{"key":"e_1_2_1_15_1","unstructured":"Christian Borgs Jennifer T Chayes Henry Cohn and Shirshendu Ganguly. 2015. Consistent nonparametric estimation for heavy-tailed sparse graphs. arXiv preprint arXiv:1508.06675 (2015).  Christian Borgs Jennifer T Chayes Henry Cohn and Shirshendu Ganguly. 2015. Consistent nonparametric estimation for heavy-tailed sparse graphs. arXiv preprint arXiv:1508.06675 (2015)."},{"key":"e_1_2_1_16_1","unstructured":"Jenkins Box and Reinsel. 1994. Time Series Analysis Forecasting and Control 3rd ed.). Prentice Hall Englewood Clifs NJ.   Jenkins Box and Reinsel. 1994. Time Series Analysis Forecasting and Control 3rd ed.). Prentice Hall Englewood Clifs NJ."},{"key":"e_1_2_1_17_1","unstructured":"Peter J Brockwell and Richard A Davis. 2013. Time series: theory and methods. Springer Science & Business Media.  Peter J Brockwell and Richard A Davis. 2013. Time series: theory and methods. Springer Science & Business Media."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2044061"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1214\/14-AOS1272"},{"key":"e_1_2_1_20_1","unstructured":"Yudong Chen and Martin J Wainwright. 2015. Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees. arXiv preprint arXiv:1509.03025 (2015).  Yudong Chen and Martin J Wainwright. 2015. Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees. arXiv preprint arXiv:1509.03025 (2015)."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6911(82)90002-0"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1214\/16-AOS1527"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai\/iau006"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1981.10477687"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"James Durbin and Siem Jan Koopman. 2012. Time series analysis by state space methods. Vol. 38. OUP Oxford.  James Durbin and Siem Jan Koopman. 2012. Time series analysis by state space methods. Vol. 38. OUP Oxford.","DOI":"10.1093\/acprof:oso\/9780199641178.001.0001"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.144706"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Nina Golyandina Vladimir Nekrutkin and Anatoly A Zhigljavsky. 2001. Analysis of time series structure: SSA and related techniques. Chapman and Hall\/CRC.  Nina Golyandina Vladimir Nekrutkin and Anatoly A Zhigljavsky. 2001. Analysis of time series structure: SSA and related techniques. Chapman and Hall\/CRC.","DOI":"10.1201\/9781420035841"},{"key":"e_1_2_1_30_1","unstructured":"James Douglas Hamilton. 1994. Time series analysis. Vol. 2. Princeton university press Princeton.  James Douglas Hamilton. 1994. Time series analysis. Vol. 2. Princeton university press Princeton."},{"volume-title":"AMELIA II: A Program for Missing Data. https:\/\/cran.r-project.org\/web\/packages\/Amelia\/vignettes\/amelia.pdf","year":"2015","author":"Honaker James","key":"e_1_2_1_31_1"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.42"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1115\/1.3662552"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2046205"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/1756006.1859920"},{"volume-title":"Blind Regression: Nonparametric Regression for Latent Variable Models via Collaborative Filtering. In Advances in Neural Information Processing Systems 29. 2155--2163.","year":"2016","author":"Lee Christina E.","key":"e_1_2_1_36_1"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmva.2010.10.012"},{"key":"e_1_2_1_38_1","unstructured":"Sahand Negahban and Martin J Wainwright. 2011. Estimation of (near) low-rank matrices with noise and high-dimensional scaling. The Annals of Statistics (2011) 1069--1097.  Sahand Negahban and Martin J Wainwright. 2011. Estimation of (near) low-rank matrices with noise and high-dimensional scaling. The Annals of Statistics (2011) 1069--1097."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1214\/12-AOS1018"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1859995.1860015"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/1953048.2185803"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1984.1056936"},{"key":"e_1_2_1_43_1","unstructured":"David S. Stoffer Robert H. Shumway. 2015. Time Series Analysis and It's Applications 3rd ed.). Blue Printing.  David S. Stoffer Robert H. Shumway. 2015. Time Series Analysis and It's Applications 3rd ed.). Blue Printing."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1162\/neco.1992.4.2.234"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1029\/2000GL012698"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5194\/npg-22-371-2015"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.720532"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-9892.1982.tb00349.x"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13634-016-0360-0"},{"key":"e_1_2_1_50_1","unstructured":"Roman Vershynin. 2010. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027 (2010).  Roman Vershynin. 2010. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027 (2010)."},{"key":"e_1_2_1_51_1","unstructured":"Christopher Xie Alex Talk and Emily Fox. 2016. A Unified Framework for Missing Data and Cold Start Prediction for Time Series Data. In Advances in neural information processing systems Time Series Workshop.  Christopher Xie Alex Talk and Emily Fox. 2016. A Unified Framework for Missing Data and Cold Start Prediction for Time Series Data. In Advances in neural information processing systems Time Series Workshop."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.5555\/3122009.3208006"},{"key":"e_1_2_1_53_1","unstructured":"Hsiang-Fu Yu Nikhil Rao and Inderjit S Dhillon. 2016. Temporal regularized matrix factorization for high-dimensional time series prediction. In Advances in neural information processing systems. 847--855.   Hsiang-Fu Yu Nikhil Rao and Inderjit S Dhillon. 2016. Temporal regularized matrix factorization for high-dimensional time series prediction. In Advances in neural information processing systems. 847--855."},{"key":"e_1_2_1_54_1","unstructured":"Yuan Zhang Elizaveta Levina and Ji Zhu. 2015. Estimating network edge probabilities by neighborhood smoothing. arXiv preprint arXiv:1509.08588 (2015).  Yuan Zhang Elizaveta Levina and Ji Zhu. 2015. Estimating network edge probabilities by neighborhood smoothing. arXiv preprint arXiv:1509.08588 (2015)."}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3287319","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3287319","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:01:53Z","timestamp":1750208513000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3287319"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,21]]},"references-count":52,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,12,21]]}},"alternative-id":["10.1145\/3287319"],"URL":"https:\/\/doi.org\/10.1145\/3287319","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2018,12,21]]},"assertion":[{"value":"2018-12-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}