{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T16:36:31Z","timestamp":1787416591546,"version":"build-2736575974"},"reference-count":47,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/100004316","name":"International Business Machines Corporation","doi-asserted-by":"publisher","award":["IBM Faculty Award"],"award-info":[{"award-number":["IBM Faculty Award"]}],"id":[{"id":"10.13039\/100004316","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1272\/17"],"award-info":[{"award-number":["1272\/17"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>Principal component regression (PCR) is a useful method for regularizing least squares approximations. Although conceptually simple, straightforward implementations of PCR have high computational costs and so are inappropriate for large scale problems. In this paper, we propose efficient algorithms for computing approximate PCR solutions that, on one hand, are high quality approximations to the true PCR solutions (when viewed as minimizer of a constrained optimization problem) and, on the other hand, entertain rigorous risk bounds (when viewed as statistical estimators). In particular, we propose an input sparsity time algorithms for approximate PCR. We also consider computing an approximate PCR in the streaming model and kernel PCR. Empirical results demonstrate the excellent performance of our proposed methods.<\/jats:p>","DOI":"10.1137\/18m1188860","type":"journal-article","created":{"date-parts":[[2019,4,30]],"date-time":"2019-04-30T12:19:05Z","timestamp":1556626745000},"page":"454-485","source":"Crossref","is-referenced-by-count":9,"title":["Sketching for Principal Component Regression"],"prefix":"10.1137","volume":"40","author":[{"given":"Liron","family":"Mor-Yosef","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Haim","family":"Avron","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2019,4,30]]},"reference":[{"key":"atypb1","unstructured":"Z. Allen-Zhu and Y. Li,\n                      Faster principal component regression and stable matrix Chebyshev approximation\n                      , in Proceedings of the 34th International Conference on Machine Learning (ICML), 2017, pp. 107-115,http:\/\/proceedings.mlr.press\/v70\/allen-zhu17c.html."},{"key":"atypb2","first-page":"1557","volume":"19","author":"Artemiou A.","year":"2009","journal-title":"Statist. Sinica"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/16M1105396"},{"key":"atypb4","unstructured":"H. Avron, K. L. Clarkson, and D. P. Woodruff,\n                      Sharper bounds for regularized data fitting\n                      , in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2017), K. Jansen, J. D. P. Rolim, D. Williamson, and S. S. Vempala, eds., LIPIcs. Leibniz Internat. Proc. Inform. 81, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2017, pp. 27:1-27:22,https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2017.27."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/090767911"},{"key":"atypb6","unstructured":"H. Avron, H. Nguyen, and D. Woodruff,\n                      Subspace embeddings for the polynomial kernel\n                      , in Neural Information Processing Systems (NIPS), 2014, pp. 2258-2266."},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"C. Boutsidis and M. Magdon-Ismail,\n                      Faster SVD-truncated regularized least-squares\n                      , in 2014 IEEE International Symposium on Information Theory, 2014, pp. 1321-1325,https:\/\/doi.org\/10.1109\/ISIT.2014.6875047.","DOI":"10.1109\/ISIT.2014.6875047"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00400-6"},{"key":"atypb9","first-page":"201","author":"Chen S.","year":"2015","journal-title":"VA"},{"key":"atypb10","first-page":"989","author":"Chowdhury A.","year":"2018","journal-title":"PMLR"},{"key":"atypb11","first-page":"205","author":"Clarkson K. L.","year":"2009","journal-title":"ACM"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1145\/3019134"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"M. B. Cohen, S. Elder, C. Musco, C. Musco, and M. Persu,\n                      Dimensionality reduction for k-means clustering and low rank approximation\n                      , in Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, 2015, R. A. Servedio and R. Rubinfeld, eds., ACM, 2015, pp. 163-172,https:\/\/doi.org\/10.1145\/2746539.2746569.","DOI":"10.1145\/2746539.2746569"},{"key":"atypb14","first-page":"1","author":"Cohen M. B.","year":"2016","journal-title":"Italy"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/0707001"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/16M1091745"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-010-0331-6"},{"key":"atypb18","unstructured":"R. Frostig, C. Musco, C. Musco, and A. Sidford,\n                      Principal component projection without principal component analysis\n                      , in International Conference on Machine Learning (ICML), 2016, pp. 2349-2357."},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"G. H. Golub and C. F. Van Loan,\n                      Matrix Computations\n                      , JHU Press, 2012.","DOI":"10.56021\/9781421407944"},{"key":"atypb20","unstructured":"A. Gonen, F. Orabona, and S. Shalev-Shwartz,\n                      Solving ridge regression using sketched preconditioned SVRG\n                      , in Proceedings of the 33rd International Conference on International Conference on Machine Learning, ICML'16, JMLR.org, 2016, pp. 1397-1405,http:\/\/dl.acm.org\/citation.cfm?id=3045390.3045538."},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/090771806"},{"key":"atypb22","unstructured":"R. A. Horn and C. R. Johnson,\n                      Matrix Analysis\n                      , Cambridge University Press, 1990."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1037\/h0071325"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.2307\/2348005"},{"key":"atypb25","first-page":"448","author":"Kaban A.","year":"2014","journal-title":"PMLR"},{"key":"atypb26","unstructured":"F. Kawala, A. Douzal-Chouakria, E. Gaussier, and E. Dimert,\n                      Pr\u00e9dictions d'activit\u00e9 dans les r\u00e9seaux sociaux en ligne\n                      , in 4i\u00e8me conf\u00e9rence sur les mod\u00e8les et l'analyse des r\u00e9seaux: Approches math\u00e9matiques et informatiques, 2013."},{"key":"atypb27","unstructured":"M. G. Kendall,\n                      A Course in Multivariate Analysis\n                      , C. Griffin, 1957."},{"key":"atypb28","first-page":"272","author":"Kogan S.","year":"2009","journal-title":"Association for Computational Linguistics"},{"key":"atypb29","unstructured":"Y. Lu and D. P. Foster,\n                      Fast ridge regression with randomized principal component analysis and gradient descent\n                      , in Proceedings of the Thirtieth Conference on Uncertainty in Artificial Intelligence, UAI'14, AUAI Press, 2014, pp. 525-532."},{"key":"atypb30","unstructured":"O. Maillard and R. Munos,\n                      Compressed least-squares regression\n                      , in Neural Information Processing Systems (NIPS), 2009, pp. 1213-1221."},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1137\/120866580"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1145\/2493252.2493254"},{"key":"atypb33","first-page":"239","author":"Pham N.","year":"2013","journal-title":"ACM"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2450722"},{"key":"atypb35","first-page":"1842","volume":"17","author":"Pilanci M.","year":"2016","journal-title":"J. Mach. Learn. Res."},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0804869105"},{"key":"atypb37","unstructured":"M. Slawski,\n                      Compressed least squares regression revisited\n                      , in Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), 2017, pp. 1207-1215."},{"key":"atypb38","doi-asserted-by":"crossref","unstructured":"M. Slawski,\n                      On Principal Components Regression, Random Projections, and Column Subsampling\n                      , preprint,https:\/\/arxiv.org\/abs\/1709.08104, 2017.","DOI":"10.1214\/18-EJS1486"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1145\/1731022.1731031"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1137\/1019104"},{"key":"atypb41","doi-asserted-by":"crossref","unstructured":"G. W. Stewart,\n                      Matrix Algorithms: Volume II: Eigensystems\n                      , SIAM, 2001,https:\/\/doi.org\/10.1137\/1.9780898718058.","DOI":"10.1137\/1.9780898718058"},{"key":"atypb42","first-page":"51","author":"Thanei G.-A.","year":"2017","journal-title":"Springer"},{"key":"atypb43","first-page":"8039","volume":"18","author":"Wang S.","year":"2017","journal-title":"J. Mach. Learn. Res."},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1561\/0400000060"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1137\/16M1082214"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2015.2494219"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1137\/15M1054201"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M1188860","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:12:54Z","timestamp":1787328774000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M1188860"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":47,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1137\/18M1188860"],"URL":"https:\/\/doi.org\/10.1137\/18m1188860","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}