Fetching the paper…
Reading the bibliography…
Sparse linear regression is a fundamental problem in high-dimensional statistics, but strikingly little is known about how to efficiently solve it without restrictive conditions on the design matrix.
Alfred Haar, Zur theorie der orthogonalen funktionensysteme , Mathematische Annalen 71
1911
Earlier work this paper cites.
Arthur P Dempster, Covariance selection , Biometrics (1972), 157–175
1972
Earlier work this paper cites.
Dean P Foster and Edward I George, The risk inflation criterion for multiple regression , The Annals of Statistics (1994), 1947–1975
1975
Earlier work this paper cites.
Shlomo Levy and Peter K Fullagar, Reconstruction of a sparse spike train from a portion of its spectrum and application to high-resolution deconvolution , Geophysics 46
1981
Earlier work this paper cites.
Diane Valerie Ouellette, Schur complements and statistics , Linear Algebra and its Applications 36
1981
Earlier work this paper cites.
Bernard Chazelle, A theorem on polygon cutting with applications , 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), IEEE, 1982, pp. 339–349
1982
Earlier work this paper cites.
Neil Robertson and Paul D Seymour, Graph minors. v. excluding a planar graph , Journal of Combinatorial Theory, Series B 41
1986
Earlier work this paper cites.
Fadil Santosa and William W Symes, Linear inversion of band-limited reflection seismograms , SIAM Journal on Scientific and Statistical Computing 7
1986
Earlier work this paper cites.
Leonidas Guibas, John Hershberger, Daniel Leven, Micha Sharir, and Robert E Tarjan, Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons , Algorithmica 2
1987
Earlier work this paper cites.
Steffen L Lauritzen and David J Spiegelhalter, Local computations with probabilities on graphical structures and their application to expert systems , Journal of the Royal Statistical Society: Series B (Methodological) 50
1988
Earlier work this paper cites.
David L Donoho and Philip B Stark, Uncertainty principles and signal recovery , SIAM Journal on Applied Mathematics 49
1989
Earlier work this paper cites.
Richard G Baraniuk and Douglas L Jones, A signal-dependent time-frequency representation: Fast algorithm for optimal kernel design , IEEE Transactions on Signal Processing 42
1994
Earlier work this paper cites.
Balas Kausik Natarajan, Sparse approximate solutions to linear systems , SIAM journal on computing 24
1995
Earlier work this paper cites.
Steffen L Lauritzen, Graphical models , vol. 17, Clarendon Press, 1996
1996
Earlier work this paper cites.
Robert Tibshirani, Regression shrinkage and selection via the lasso , Journal of the Royal Statistical Society: Series B (Methodological) 58
1996
Earlier work this paper cites.
Michael Kearns, Efficient noise-tolerant learning from statistical queries , Journal of the ACM (JACM) 45
1998
Earlier work this paper cites.
Thomas M Cover, Elements of information theory , John Wiley & Sons, 1999
1999
Earlier work this paper cites.
Stéphane Mallat, A wavelet tour of signal processing , Elsevier, 1999
1999
Earlier work this paper cites.
Richard G Baraniuk, Volkan Cevher, Marco F Duarte, and Chinmay Hegde, Model-based compressive sensing , IEEE Transactions on information theory 56
2001
Earlier work this paper cites.
Yousef Saad, Iterative methods for sparse linear systems , SIAM, 2003
2003
Earlier work this paper cites.
Noga Alon and Joel H Spencer, The probabilistic method , John Wiley & Sons, 2004
2004
Earlier work this paper cites.
Hans L Bodlaender, Discovering treewidth , International Conference on Current Trends in Theory and Practice of Computer Science, Springer, 2005, pp. 1–16
2005
Earlier work this paper cites.
Emmanuel J Candes and Terence Tao, Decoding by linear programming , IEEE transactions on information theory 51
2005
Earlier work this paper cites.
Christopher M Bishop, Pattern recognition and machine learning , springer, 2006
2006
Earlier work this paper cites.
Emmanuel J Candès, Justin Romberg, and Terence Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information , IEEE Transactions on information theory 52
2006
Earlier work this paper cites.
David L Donoho, Compressed sensing , IEEE Transactions on information theory 52
2006
Earlier work this paper cites.
Nicolai Meinshausen, Peter Bühlmann, et al., High-dimensional graphs and variable selection with the lasso , The annals of statistics 34
2006
Earlier work this paper cites.
Mark Rudelson and Roman Vershynin, Sparse reconstruction by convex relaxation: Fourier and gaussian measurements , 2006 40th Annual Conference on Information Sciences and Systems, IEEE, 2006, pp. 207–212
2006
Earlier work this paper cites.
Emmanuel Candes, Terence Tao, et al., The dantzig selector: Statistical estimation when p is much larger than n , Annals of statistics 35
2007
Earlier work this paper cites.
Scott Sheffield, Gaussian free fields for mathematicians , Probability theory and related fields 139
2007
Earlier work this paper cites.
Benny Applebaum, Boaz Barak, and David Xiao, On basing lower-bounds for learning on worst-case assumptions , 2008 49th Annual IEEE Symposium on Foundations of Computer Science, IEEE, 2008, pp. 211–220
2008
Earlier work this paper cites.
Radu Berinde, Anna C Gilbert, Piotr Indyk, Howard Karloff, and Martin J Strauss, Combining geometry and combinatorics: A unified approach to sparse signal recovery , 2008 46th Annual Allerton Conference on Communication, Control, and Computing, IEEE, 2008, pp. 798–805
2008
Cited alongside, same era.
Radu Berinde and Piotr Indyk, Sparse recovery using sparse random matrices , preprint (2008)
2008
Cited alongside, same era.
Abhimanyu Das and David Kempe, Algorithms for subset selection in linear regression , Proceedings of the fortieth annual ACM symposium on Theory of computing, 2008, pp. 45–54
2008
Cited alongside, same era.
Uriel Feige, MohammadTaghi Hajiaghayi, and James R Lee, Improved approximation algorithms for minimum weight vertex separators , SIAM Journal on Computing 38
2008
Cited alongside, same era.
Shai Shalev-Shwartz and Shai Ben-David, Understanding machine learning: From theory to algorithms , Cambridge university press, 2014
2014
Later among the works it cites.
Yuchen Zhang, Martin J Wainwright, and Michael I Jordan, Lower bounds on the performance of polynomial-time algorithms for sparse linear regression , Conference on Learning Theory, 2014, pp. 921–948
2014
Later among the works it cites.
Dean Foster, Howard Karloff, and Justin Thaler, Variable selection is hard , Conference on Learning Theory, PMLR, 2015, pp. 696–709
2015
Later among the works it cites.
Jinzhu Jia, Karl Rohe, et al., Preconditioning the lasso for sign consistency , Electronic Journal of Statistics 9
2015
Later among the works it cites.
Michael Krivelevich, The phase transition in site percolation on pseudo-random graphs , the electronic journal of combinatorics 22
2015
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
2008
Cited alongside, same era.
Alexandre B Tsybakov, Introduction to nonparametric estimation , Springer Science & Business Media, 2008
2008
Cited alongside, same era.
Martin J Wainwright and Michael Irwin Jordan, Graphical models, exponential families, and variational inference , Now Publishers Inc, 2008
2008
Cited alongside, same era.
Thomas Blumensath and Mike E Davies, Iterative hard thresholding for compressed sensing , Applied and computational harmonic analysis 27
2009
Cited alongside, same era.
Peter J Brockwell and Richard A Davis, Time series: theory and methods , Springer science & business media, 2009
2009
Cited alongside, same era.
Peter J Bickel, Ya’acov Ritov, Alexandre B Tsybakov, et al., Simultaneous analysis of lasso and dantzig selector , The Annals of statistics 37
2009
Cited alongside, same era.
Deanna Needell and Joel A Tropp, Cosamp: Iterative signal recovery from incomplete and inaccurate samples , Applied and computational harmonic analysis 26
2009
Cited alongside, same era.
Judea Pearl, Causality , Cambridge university press, 2009
2009
Cited alongside, same era.
Later among the works it cites.
Phillippe Rigollet and Jan-Christian Hütter, High dimensional statistics , Lecture notes for course 18S997 813
2015
Later among the works it cites.
Hans L Bodlaender, Pål Grǿnås Drange, Markus S Dregi, Fedor V Fomin, Daniel Lokshtanov, and Michał Pilipczuk, A c ˆ kn 5-approximation algorithm for treewidth , SIAM Journal on Computing 45
2016
Later among the works it cites.
Dimitris Bertsimas, Angela King, Rahul Mazumder, et al., Best subset selection via a modern optimization lens , Annals of statistics 44
2016
Later among the works it cites.
Chandra Chekuri and Julia Chuzhoy, Polynomial bounds for the grid-minor theorem , Journal of the ACM (JACM) 63
2016
Later among the works it cites.
Xi Chen, Adityanand Guntuboyina, and Yuchen Zhang, On bayes risk lower bounds , The Journal of Machine Learning Research 17
2016
Later among the works it cites.
2016
Later among the works it cites.
Jan-Christian Hütter and Philippe Rigollet, Optimal rates for total variation denoising , Conference on Learning Theory, PMLR, 2016, pp. 1115–1146
2016
Later among the works it cites.
2016
Later among the works it cites.
2017
Later among the works it cites.
Arnak S Dalalyan, Mohamed Hebiri, Johannes Lederer, et al., On the prediction performance of the lasso , Bernoulli 23
2017
Later among the works it cites.
2017
Later among the works it cites.
Jonas Peters, Dominik Janzing, and Bernhard Schölkopf, Elements of causal inference: foundations and learning algorithms , The MIT Press, 2017
2017
Later among the works it cites.
Yuchen Zhang, Martin J Wainwright, Michael I Jordan, et al., Optimal prediction for sparse linear models? lower bounds for coordinate-separable m-estimators , Electronic Journal of Statistics 11
2017
Later among the works it cites.
2018
Later among the works it cites.
Pierre C Bellec, Guillaume Lecué, Alexandre B Tsybakov, et al., Slope meets lasso: improved oracle bounds and optimality , Annals of Statistics 46
2018
Later among the works it cites.
2018
Later among the works it cites.
Ethan R Elenberg, Rajiv Khanna, Alexandros G Dimakis, Sahand Negahban, et al., Restricted strong convexity implies weak submodularity , Annals of Statistics 46
2018
Later among the works it cites.
Sara Van De Geer, On tight bounds for the lasso , Journal of Machine Learning Research 19
2018
Later among the works it cites.
Galen Reeves, Jiaming Xu, and Ilias Zadik, The all-or-nothing phenomenon in sparse linear regression , Conference on Learning Theory, PMLR, 2019, pp. 2652–2663
2019
Later among the works it cites.
Santosh Vempala and John Wilmes, Gradient descent for one-hidden-layer neural networks: Polynomial convergence and sq lower bounds , Conference on Learning Theory, PMLR, 2019, pp. 3115–3117
2019
Later among the works it cites.
Matthew Brennan and Guy Bresler, Reducibility and statistical-computational gaps from secret leakage , Conference on Learning Theory, PMLR, 2020, pp. 648–847
2020
Later among the works it cites.
2020
Later among the works it cites.
Jonathan Kelner, Frederic Koehler, Raghu Meka, and Ankur Moitra, Learning some popular gaussian graphical models without condition number bounds , Proceedings of Neural Information Processing Systems (NeurIPS), 2020
2020
Later among the works it cites.
Anirban Basak and Mark Rudelson, Sharp transition of the invertibility of the adjacency matrices of sparse random graphs , Probability Theory and Related Fields (2021), 1–76
2021
Closest in time.
Julia Chuzhoy and Zihan Tan, Towards tight (er) bounds for the excluded grid theorem , Journal of Combinatorial Theory, Series B 146
2021
Closest in time.