{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,15]],"date-time":"2026-06-15T17:41:56Z","timestamp":1781545316217,"version":"3.54.5"},"publisher-location":"New York, NY, USA","reference-count":48,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100006063","name":"Paul and Daisy Soros Fellowships for New Americans","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006063","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100014718","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CAREER Award CCF-1453261, Large CCF-1565235"],"award-info":[{"award-number":["CAREER Award CCF-1453261, Large CCF-1565235"]}],"id":[{"id":"10.13039\/100014718","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384333","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"587-600","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Learning mixtures of linear regressions in subexponential time via Fourier moments"],"prefix":"10.1145","author":[{"given":"Sitan","family":"Chen","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jerry","family":"Li","sequence":"additional","affiliation":[{"name":"Microsoft Research, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhao","family":"Song","sequence":"additional","affiliation":[{"name":"Princeton University, USA \/ Institute for Advanced Study at Princeton, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.83"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.automatica.2011.01.036"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1214\/16-AOS1435"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2005.07.001"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.21432"},{"key":"e_1_3_2_1_6_1","volume-title":"International Conference on Machine Learning. 1040\u20131048","author":"Chaganty Arun Tejasvi","year":"2013","unstructured":"Arun Tejasvi Chaganty and Percy Liang . 2013 . Spectral experts for estimating mixtures of linear regressions . In International Conference on Machine Learning. 1040\u20131048 . Arun Tejasvi Chaganty and Percy Liang. 2013. Spectral experts for estimating mixtures of linear regressions. In International Conference on Machine Learning. 1040\u20131048."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591848"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055491"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.84"},{"key":"e_1_3_2_1_10_1","unstructured":"Yudong Chen Xinyang Yi and Constantine Caramanis. 2013. A convex formulation for mixed regression with two components: Minimax optimal rates. arXiv preprint arXiv:1312.7006.  Yudong Chen Xinyang Yi and Constantine Caramanis. 2013. A convex formulation for mixed regression with two components: Minimax optimal rates. arXiv preprint arXiv:1312.7006."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-9473(89)90043-1"},{"key":"e_1_3_2_1_12_1","volume-title":"Learning Structured Distributions.. Handbook of Big Data, 267","author":"Diakonikolas Ilias","year":"2016","unstructured":"Ilias Diakonikolas . 2016. Learning Structured Distributions.. Handbook of Big Data, 267 ( 2016 ). Ilias Diakonikolas. 2016. Learning Structured Distributions.. Handbook of Big Data, 267 (2016)."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897552"},{"key":"e_1_3_2_1_14_1","volume-title":"Conference on Learning Theory. 831\u2013849","author":"Diakonikolas Ilias","year":"2016","unstructured":"Ilias Diakonikolas , Daniel M Kane , and Alistair Stewart . 2016 . Optimal learning via the fourier transform for sums of independent integer random variables . In Conference on Learning Theory. 831\u2013849 . Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. 2016. Optimal learning via the fourier transform for sums of independent integer random variables. In Conference on Learning Theory. 831\u2013849."},{"key":"e_1_3_2_1_15_1","volume-title":"Conference on Learning Theory. 850\u2013878","author":"Diakonikolas Ilias","year":"2016","unstructured":"Ilias Diakonikolas , Daniel M Kane , and Alistair Stewart . 2016 . Properly learning poisson binomial distributions in almost polynomial time . In Conference on Learning Theory. 850\u2013878 . Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. 2016. Properly learning poisson binomial distributions in almost polynomial time. In Conference on Learning Theory. 850\u2013878."},{"key":"e_1_3_2_1_16_1","volume-title":"Sparse subspace clustering: Algorithm, theory, and applications","author":"Elhamifar Ehsan","year":"2013","unstructured":"Ehsan Elhamifar and Rene Vidal . 2013. Sparse subspace clustering: Algorithm, theory, and applications . IEEE transactions on pattern analysis and machine intelligence, 35, 11 ( 2013 ), 2765\u20132781. Ehsan Elhamifar and Rene Vidal. 2013. Sparse subspace clustering: Algorithm, theory, and applications. IEEE transactions on pattern analysis and machine intelligence, 35, 11 (2013), 2765\u20132781."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1080\/00949650802590261"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/358669.358692"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/312129.312198"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214029"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1720804115"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.61"},{"key":"e_1_3_2_1_23_1","volume-title":"Hierarchical mixtures of experts and the EM algorithm. Neural computation, 6, 2","author":"Jordan Michael I","year":"1994","unstructured":"Michael I Jordan and Robert A Jacobs . 1994. Hierarchical mixtures of experts and the EM algorithm. Neural computation, 6, 2 ( 1994 ), 181\u2013214. Michael I Jordan and Robert A Jacobs. 1994. Hierarchical mixtures of experts and the EM algorithm. Neural computation, 6, 2 (1994), 181\u2013214."},{"key":"e_1_3_2_1_24_1","volume-title":"Sparse Fourier Transform in Any Constant Dimension with Nearly-Optimal Sample Complexity in Sublinear Time. In Symposium on Theory of Computing Conference, STOC\u201916","author":"Kapralov Michael","year":"2016","unstructured":"Michael Kapralov . 2016 . Sparse Fourier Transform in Any Constant Dimension with Nearly-Optimal Sample Complexity in Sublinear Time. In Symposium on Theory of Computing Conference, STOC\u201916 , Cambridge, MA, USA , June 19-21, 2016. Michael Kapralov. 2016. Sparse Fourier Transform in Any Constant Dimension with Nearly-Optimal Sample Complexity in Sublinear Time. In Symposium on Theory of Computing Conference, STOC\u201916, Cambridge, MA, USA, June 19-21, 2016."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.66"},{"key":"e_1_3_2_1_26_1","unstructured":"Sushrut Karmalkar Pravesh Kothari and Adam Klivans. 2019. List-Decodable Linear Regression. In NeurIPS. arXiv preprint arXiv:1905.05679.  Sushrut Karmalkar Pravesh Kothari and Adam Klivans. 2019. List-Decodable Linear Regression. In NeurIPS. arXiv preprint arXiv:1905.05679."},{"key":"e_1_3_2_1_27_1","unstructured":"Jason M Klusowski Dana Yang and WD Brinda. 2017. Estimating the coefficients of a mixture of two linear regressions by expectation maximization. arXiv preprint arXiv:1704.08231.  Jason M Klusowski Dana Yang and WD Brinda. 2017. Estimating the coefficients of a mixture of two linear regressions by expectation maximization. arXiv preprint arXiv:1704.08231."},{"key":"e_1_3_2_1_28_1","unstructured":"Jeongyeol Kwon and Constantine Caramanis. 2019. EM Converges for a Mixture of Many Linear Regressions. arXiv preprint arXiv:1905.12106.  Jeongyeol Kwon and Constantine Caramanis. 2019. EM Converges for a Mixture of Many Linear Regressions. arXiv preprint arXiv:1905.12106."},{"key":"e_1_3_2_1_29_1","unstructured":"Jeongyeol Kwon Wei Qian Constantine Caramanis Yudong Chen and Damek Davis. 2018. Global convergence of EM algorithm for mixtures of two component linear regression. arXiv preprint arXiv:1810.05752.  Jeongyeol Kwon Wei Qian Constantine Caramanis Yudong Chen and Damek Davis. 2018. Global convergence of EM algorithm for mixtures of two component linear regression. arXiv preprint arXiv:1810.05752."},{"key":"e_1_3_2_1_30_1","volume-title":"Learning Mixtures of Linear Regressions with Nearly Optimal Complexity. In Conference On Learning Theory. 1125\u20131144","author":"Li Yuanzhi","year":"2018","unstructured":"Yuanzhi Li and Yingyu Liang . 2018 . Learning Mixtures of Linear Regressions with Nearly Optimal Complexity. In Conference On Learning Theory. 1125\u20131144 . Yuanzhi Li and Yingyu Liang. 2018. Learning Mixtures of Linear Regressions with Nearly Optimal Complexity. In Conference On Learning Theory. 1125\u20131144."},{"key":"e_1_3_2_1_31_1","volume-title":"Robust recovery of subspace structures by low-rank representation","author":"Liu Guangcan","year":"2012","unstructured":"Guangcan Liu , Zhouchen Lin , Shuicheng Yan , Ju Sun , Yong Yu , and Yi Ma. 2012. Robust recovery of subspace structures by low-rank representation . IEEE transactions on pattern analysis and machine intelligence, 35, 1 ( 2012 ), 171\u2013184. Guangcan Liu, Zhouchen Lin, Shuicheng Yan, Ju Sun, Yong Yu, and Yi Ma. 2012. Robust recovery of subspace structures by low-rank representation. IEEE transactions on pattern analysis and machine intelligence, 35, 1 (2012), 171\u2013184."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33786-4_26"},{"key":"e_1_3_2_1_33_1","unstructured":"Ankur Moitra. 2015. The threshold for super-resolution via extremal functions. In STOC.  Ankur Moitra. 2015. The threshold for super-resolution via extremal functions. In STOC."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.15"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Vasileios Nakos Zhao Song and Zhengyu Wang. 2019. (Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless. In FOCS.  Vasileios Nakos Zhao Song and Zhengyu Wang. 2019. (Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless. In FOCS.","DOI":"10.1109\/FOCS.2019.00092"},{"key":"e_1_3_2_1_36_1","unstructured":"Praneeth Netrapalli Prateek Jain and Sujay Sanghavi. 2013. Phase retrieval using alternating minimization. In Advances in Neural Information Processing Systems. 2796\u20132804.  Praneeth Netrapalli Prateek Jain and Sujay Sanghavi. 2013. Phase retrieval using alternating minimization. In Advances in Neural Information Processing Systems. 2796\u20132804."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007730.1007731"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.42"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Prasad Raghavendra and Morris Yau. 2019. List Decodable Learning via Sum of Squares. arXiv preprint arXiv:1905.04660.  Prasad Raghavendra and Morris Yau. 2019. List Decodable Learning via Sum of Squares. arXiv preprint arXiv:1905.04660.","DOI":"10.1137\/1.9781611975994.10"},{"key":"e_1_3_2_1_40_1","unstructured":"Hanie Sedghi Majid Janzamin and Anima Anandkumar. 2016. Provable tensor methods for learning mixtures of generalized linear models. In Artificial Intelligence and Statistics. 1223\u20131231.  Hanie Sedghi Majid Janzamin and Anima Anandkumar. 2016. Provable tensor methods for learning mixtures of generalized linear models. In Artificial Intelligence and Statistics. 1223\u20131231."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCVW.2015.114"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/3305890.3306040"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2010.939739"},{"key":"e_1_3_2_1_44_1","volume-title":"Three-view multibody structure from motion","author":"Vidal Rene","year":"2007","unstructured":"Rene Vidal and Richard Hartley . 2007. Three-view multibody structure from motion . IEEE transactions on pattern analysis and machine intelligence, 30, 2 ( 2007 ), 214\u2013227. Rene Vidal and Richard Hartley. 2007. Three-view multibody structure from motion. IEEE transactions on pattern analysis and machine intelligence, 30, 2 (2007), 214\u2013227."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2005.244"},{"key":"e_1_3_2_1_46_1","volume-title":"International Conference on Machine Learning. 613\u2013621","author":"Yi Xinyang","year":"2014","unstructured":"Xinyang Yi , Constantine Caramanis , and Sujay Sanghavi . 2014 . Alternating minimization for mixed linear regression . In International Conference on Machine Learning. 613\u2013621 . Xinyang Yi, Constantine Caramanis, and Sujay Sanghavi. 2014. Alternating minimization for mixed linear regression. In International Conference on Machine Learning. 613\u2013621."},{"key":"e_1_3_2_1_47_1","unstructured":"Xinyang Yi Constantine Caramanis and Sujay Sanghavi. 2016. Solving a mixture of many random linear equations by tensor decomposition and alternating minimization. arXiv preprint arXiv:1608.05749.  Xinyang Yi Constantine Caramanis and Sujay Sanghavi. 2016. Solving a mixture of many random linear equations by tensor decomposition and alternating minimization. arXiv preprint arXiv:1608.05749."},{"key":"e_1_3_2_1_48_1","unstructured":"Kai Zhong Prateek Jain and Inderjit S Dhillon. 2016. Mixed linear regression with multiple components. In Advances in neural information processing systems. 2190\u20132198.  Kai Zhong Prateek Jain and Inderjit S Dhillon. 2016. Mixed linear regression with multiple components. In Advances in neural information processing systems. 2190\u20132198."}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384333","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384333","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:32:57Z","timestamp":1750199577000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384333"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":48,"alternative-id":["10.1145\/3357713.3384333","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384333","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}