|
|
Afonso S. Bandeira
contact info Prof. Dr. Afonso Bandeira HG G 23.1, ETH Zurich, Ramistrasse 101 8092 Zurich, Switzerland Professor of Mathematics, ETH Zurich Administration: Annette Ryter annette [dot] ryter [at] ifor [dot] math [dot] ethz [dot] ch
|
|
|
|||||||
|
|||||||||||
I am a Professor with the Department of Mathematics (D-MATH) at ETH Zurich. I am also a member of the Max Planck ETH Center for Learning Systems, the ETH Foundations of Data Science, the ETH AI Center, and have a courtesy appointment at D-ITET. I currently serve as the Director of the Institute For Operations Research (IFOR). Also, Here is a list of classes I teach, and seminars I organize at ETH (if link does not work, search in VVZ). Group Members: Antoine Maillard, Pedro Abdalla, Daniil Dmitriev, Konstantin Donhauser, Anastasia Kireeva, Petar Nizic-Nikolac, Kevin Lucca. (see CV for alumni). Published manuscripts by the group available at the ETH Research Collection. This webpage usually gets updated only once a year, with the start of a new calendar year (except for the announcements box). For up to date information you can use: for my preprints, for published manuscripts from the group, for my manuscripts and most lecture notes, for teaching, and for contact info of group members. If you are interested in a position in our group, or are an ETH student looking to do a project/thesis, see here. Publications Submitted, In Press, and selected Preprints Exact threshold for approximate ellipsoid fitting of random points A. Maillard, A. S. Bandeira arXiv:2310.05787 [math.PR], 2023 [arXiv] Fitting an ellipsoid to a quadratic number of random points A. S. Bandeira, A. Maillard, S. Mendelson, E. Paquette arXiv:2307.01181 [math.PR], 2023 [arXiv] On the concentration of Gaussian Cayley matrices A. S. Bandeira, D. Kunisky, D. G. Mixon, X. Zeng arXiv:2212.00066 [math.FA], 2022 [arXiv] Expander graphs are globally synchronising P. Abdalla, A. S. Bandeira, M. Kassabov, V. Souza, S. H. Strogatz, A. Townsend arXiv:2210.12788 [math.CO], 2022 [arXiv] - Work featured in Quanta Magazine article, July 2023. Injectivity of ReLU networks: perspectives from statistical physics A. Maillard, A. S. Bandeira, D. Belius, I. Dokmanic, S. Nakajima arXiv:2302.14112 [cond-mat.dis-nn], 2023 [arXiv] Guarantees for Spontaneous Synchronization on Random Geometric Graphs P. Abdalla, A. S. Bandeira, C. Invernizzi SIAM Journal on Applied Dynamical Systems, to appear. [arXiv] Some recent Lecture Notes, Books and Monographs Linear Algebra A. S. Bandeira Lecture Notes (introductory undergraduate course, Part II), Fall 2023, ETH Zurich Mathematics of Data Science (draft) A. S. Bandeira, A. Singer, T. Strohmer Book in preparation See here for videos of lectures on this material (*Disclaimer: they were prepared due to the Covid-19 pandemic, and are not polished or high-quality, I include them here in case they are still useful) Mathematics of Signals, Networks, and Learning A. S. Bandeira and A. Maillard Lecture Notes (undergraduate course), Spring 2023, ETH Zurich More available at my teaching page and at the bottom of this page Peer-Reviewed Publications Matrix Concentration Inequalities and Free Probability A. S. Bandeira, M. T. Boedihardjo, R. van Handel Inventiones Mathematicae, 234, pages 419-487, 2023 [arXiv] On free energy barriers in Gaussian priors and failure of cold start MCMC for high-dimensional unimodal distributions A. S. Bandeira, A. Maillard, R. Nickl, S. Wang Philosophical Transactions of the Royal Society A, 381: 20220150, 2023. [arXiv] Estimation under group actions: recovering orbits from invariants A. S. Bandeira, B. Blum-Smith, Joe Kileel, A. Perry, J. Weed, A. S. Wein Applied and Computational Harmonic Analysis 66: 236-319, 2023. [arXiv] [related video] - Co-authors awarded 2023 ACHA Charles Chui Young Researcher Best Paper Award. Subexponential-Time Algorithms for Sparse PCA Y. Ding, D. Kunisky, A. S. Wein, A. S. Bandeira Journal of the FoCM, 2023. [arXiv] [related video] A remark on Kashin's discrepancy argument and partial coloring in the Komlós conjecture A. S. Bandeira, A. Maillard, N. Zhivotovskiy Port. Math. 79 (2022), no. 3/4, pp. 311–316, 2022 [arXiv] [article] The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics A. S. Bandeira, A. El Alaoui, S. B. Hopkins, T. Schramm, A. S. Wein, I. Zadik NeurIPS 2022, Oral Presentation. [arXiv] [article] Dual bounds for the positive definite functions approach to mutually unbiased bases A. S. Bandeira, N. Doppelbauer, D. Kunisky Sampling Theory, Signal Processing, and Data Analysis (SaSiDa) 20, 2022 [arXiv] [article] Community Detection with a Subsampled Semidefinite Program P. Abdalla, A. S. Bandeira Sampling Theory, Signal Processing, and Data Analysis (SaSiDa) 20, 2022 [arXiv] [article] Computationally efficient sparse clustering M. Loffler, A. S. Wein, A. S. Bandeira Information and Inference: A Journal of the IMA, Volume 11, Issue 4, Pages 1255–1286, 2022. [arXiv] [article] Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio D. Kunisky, A. S. Wein, A. S. Bandeira In: Cerejeiras, P., Reissig, M. (eds) Mathematical Analysis, its Applications and Computation. ISAAC 2019. Springer Proceedings in Mathematics & Statistics, vol 385, 2022. [arXiv] [related video] [article] Average-Case Integrality Gap for Non-Negative Principal Component Analysis D. Kunisky, A. S. Wein, A. S. Bandeira MSML 2021 [arXiv] [article] Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs A. S. Bandeira, J. Banks, D. Kunisky, C. Moore, A. S. Wein COLT 2021 [arXiv] [video] The Spectral Norm of Random Lifts of Matrices A. S. Bandeira, Y. Ding Electron. Commun. Probab. 26: 1-10 (2021) [arXiv] [paper] The Average-Case Time Complexity of Certifying the Restricted Isometry Property Y. Ding, D. Kunisky, A. S. Wein, A. S. Bandeira IEEE Transactions on Information Theory (Volume: 67, Issue: 11, November 2021) [arXiv] [article] Group Testing in the High Dilution G. Arpino, N. Grometo, A. S. Bandeira ISIT 2021 [arXiv] [article] Likelihood Maximization and Moment Matching in Low SNR Gaussian Mixture Models A. Katsevich, A. S. Bandeira Communications on Pure and Applied Mathematics, 2022. [arXiv] [article] A Tight Degree 4 Sum-of-Squares Lower Bound for the Sherrington-Kirkpatrick Hamiltonian D. Kunisky, A. S. Bandeira, Mathematical Programming, 190, pages 721–759 (2021) [arXiv] [article] Non-unique games over compact groups and orientation estimation in cryo-EM A. S. Bandeira, Y. Chen, R. Lederman, and A. Singer Inverse Problems, Volume 36, Number 6 Special Issue on Cryo-Electron Microscopy and Inverse Problems, 2020. [arXiv] [paper] Statistical limits of spiked tensor models A. Perry, A. S. Wein, and A. S. Bandeira Annales de l'Institut Henri Poincare - Probabilites et Statistiques, Vol. 56, No. 1, 230-264, 2020. [arXiv] [paper] Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs N. Boumal, V. Voroninski, and A. S. Bandeira Communications on Pure and Applied Mathematics, Volume 73, Issue 3, 2020. [arXiv] [article] Computational Hardness of Certifying Bounds on Constrained PCA Problems A. S. Bandeira, D. Kunisky, A. S. Wein Innovations in Theoretical Computer Science (ITCS’20), 2020. [arXiv] [paper] [related video] Optimal rates of estimation for multi-reference alignment A. S. Bandeira, P. Rigollet, J. Weed Mathematical Statistics and Learning, Volume 2, Issue 1, 2019, pp. 25-75. [arXiv] [related video] Spurious Valleys in One-hidden-layer Neural Network Optimization Landscapes L. Venturi, A. S. Bandeira, J. Bruna Journal of Machine Learning Research (JMLR), 20(133):1-34, 2019. [arXiv] [paper] Previous title: Spurious Valleys in Two-layer Neural Network Optimization Landscapes Earlier version preprint: Neural Networks with Finite Intrinsic Dimension have no Spurious Valleys Experimental performance of graph neural networks on random instances of max-cut W. Yao, A. S. Bandeira, S. Villar SPIE Wavelets and Sparsity 2019. [arXiv] Connections between sum-of-squares optimization and structured tight frames A. S. Bandeira, D. Kunisky SPIE Wavelets and Sparsity 2019. [pdf] On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization S. Ling, R. Xu, A. S. Bandeira SIAM Journal on Optimization (SIOPT), 29(3), 1879–1907, 2019 [arXiv] The sample complexity of multi-reference alignment A. Perry, J. Weed, A. S. Bandeira, P. Rigollet, A. Singer SIAM Journal on Mathematics of Data Science (SIMODS), Vol. 1, No. 3, pp. 497--517, 2019. [arXiv] [related video] Sum-of-Squares Optimization and the Sparsity Structure of Equiangular Tight Frames A. S. Bandeira, D. Kunisky SampTA Sampling Theory and Applications, 13th International Conference, 2019. [arXiv] SE-Sync: A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group D. M. Rosen, L. Carlone, A. S. Bandeira, and J. J. Leonard International Journal of Robotics Research, International Journal of Robotics Research, Vol 38, Issue 2-3, 2019. [code] [technical report] [corrigendum] Notes on computational-to-statistical gaps: predictions using statistical physics A. S. Bandeira, A. Perry, A. S. Wein Portugaliae Mathematica, Portugaliae Mathematica, Vol 75, issue 2, pages 159-186, 2018. [arXiv] A Revised note on Learning Algorithms for Quadratic Assignment with Graph Neural Networks A. Nowak, S. Villar, A. S. Bandeira, J. Bruna IEEE Data Science Workshop, 2018. [arXiv] Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models A. Perry, A. S. Wein, A. S. Bandeira, and A. Moitra Annals of Statistics, Annals of Statistics, Volume 46, Number 5, pp. 2416-2451, 2018. [arXiv] [related video] Longer technical report: Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization. [arXiv] [related video] - A. Perry and A. Wein awarded 2018 Jonhson prize (MIT) for this paper. Message-passing algorithms for synchronization problems over compact groups A. Perry, A. S. Wein, A. S. Bandeira, A. Moitra Communications on Pure and Applied Mathematics, Communications on Pure and Applied Mathematics, Volume 71, Issue 11, Pages 2275-2322, 2018. [arXiv] [related video] Random Laplacian matrices and convex relaxations A. S. Bandeira Foundations of Computational Mathematics, Foundations of Computational Mathematics, 18, pages 345–379(2018). [arXiv] [bibtex] Multisection in the stochastic block model using semidefinite programming N. Agarwal, A. S. Bandeira, K. Koiliaris, A. Kolla Compressed Sensing and its Applications: MATHEON Workshop 2015 (Applied and Numerical Harmonic Analysis), 125-162, 2018. [arXiv] [bibtex] Compressive classification and the rare eclipse problem A. S. Bandeira, D. G. Mixon, and B. Recht Compressed Sensing and its Applications: MATHEON Workshop 2015 (Applied and Numerical Harmonic Analysis), 197-220, 2018. [arXiv] [bibtex] [blog entry] Discrete uncertainty principles and sparse signal processing A. S. Bandeira, M. E. Lewis, and D. G. Mixon Journal of Fourier Analysis and Applications, Journal of Fourier Analysis and Applications, volume 24, pages 935–956(2018) [arXiv] [bibtex] [paper] Resilience for the Littlewood-Offord Problem A. S. Bandeira, A. Ferber, and M. Kwan Advances in Mathematics vol. 319, pp. 292-312, 2017. [paper] [arXiv] A Note on Learning Algorithms for Quadratic Assignment with Graph Neural Networks A. Nowak, S. Villar, A. S. Bandeira, J. Bruna ICML 2017 Workshop on Principled Approaches to Deep Learning (PADL), 2017. [arXiv] Marcenko-Pastur Law for Kendall's Tau A. S. Bandeira, A. Lodhia, P. Rigollet Electronic Communications in Probability, Vol. 22, paper no. 32, 1-7, 2017. [paper][arXiv] Community Detection in Hypergraphs, Spiked Tensor Models, and Sum-of-Squares C. Kim, A. S. Bandeira, M. X. Goemans SampTA Sampling Theory and Applications, 12th International Conference, 2017. [arXiv] Tightness of the maximum likelihood semidefinite relaxation for angular synchronization A. S. Bandeira, N. Boumal, and A. Singer Mathematical Programming SERIES A (2017) 163: 145-167. [arXiv] [bibtex] [article] [SharedIt] A conditional construction of restricted isometries A. S. Bandeira, D. G. Mixon, and J. Moreira International Mathematics Research Notices (2017) 2017:372-381. [arXiv] [bibtex] [blog entry] A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group D. M. Rosen, L. Carlone, A. S. Bandeira, and J. J. Leonard Workshop on the Algorithmic Foundations of Robotics (WAFR) , 2016. [arXiv] [code] - Best paper award at WAFR 2016. The non-convex Burer-Monteiro approach works on smooth semidefinite programs N. Boumal, V. Voroninski, and A. S. Bandeira Neural Information Processing Systems, NIPS 2016. [arXiv] [bibtex] On the low-rank approach for semidefinite programs arising in synchronization and community detection A. S. Bandeira, N. Boumal, and V. Voroninski Conference on Learning Theory (COLT), 2016. [arXiv] [bibtex] Approximating the little Grothendieck problem over the orthogonal and unitary Groups A. S. Bandeira, C. Kennedy, and A. Singer Mathematical Programming SERIES A (2016) 160: 433-475. [arXiv] [bibtex] [blog entry] [related blog entry] Linear Boolean classification, coding and ''the critical problem'' E. Abbe, N. Alon, A. S. Bandeira, and C. Sandon IEEE Transactions on Information Theory (2016) 62: 1667-1673. [arXiv] [bibtex] [blog entry] Conference Proceedings version: Linear Boolean classification, coding and ''the critical problem'' at IEEE International Symposium on Information Theory (ISIT 2014), 2014. A note on Probably Certifiably Correct algorithms A. S. Bandeira Comptes Rendus Mathematique (2016) 354: 329-333, to appear, 2016. [arXiv] [bibtex] Derandomizing restricted isometries via the Legendre symbol A. S. Bandeira, M. Fickus, D. G. Mixon, and J. Moreira Constructive Approximation (2016) 43: 409-424. [arXiv] [bibtex] [paper] Sharp nonasymptotic bounds on the norm of random matrices with independent entries A. S. Bandeira and R. v. Handel Annals of Probability (2016) 44: 2479-2506. [arXiv] [bibtex] [blog entry] [related video part 1 and part 2] Exact Recovery in the Stochastic Block Model E. Abbe, A. S. Bandeira, G. Hall IEEE Transactions on Information Theory, vol.62, no.1, pp.471-487, 2016. [paper] [arXiv] [bibtex] [related lecture notes] [related video] - 2020 Information Theory Society Paper Award Relax, no need to round: integrality of clustering formulations P. Awasthi, A. S. Bandeira, M. Charikar, R. Krishnaswamy, S. Villar, and R. Ward 6th Innovations in Theoretical Computer Science (ITCS 2015). [arXiv] [bibtex] [errata] Decoding binary node labels from censored edge measurements: Phase transition and efficient recovery E. Abbe, A. S. Bandeira, A. Bracher, and A. Singer Transactions on Network Science and Engineering, 1(1), pp.10-20, 2014. [arXiv] [bibtex] [blog entry] [related blog entry] Open problem: Tightness of maximum likelihood semidefinite relaxations A. S. Bandeira, Y. Khoo, and A. Singer COLT Open Problem, JMLR W&CP 35: 1265-1267, 2014. [arXiv] [bibtex] [blog entry] Convergence of trust-region methods based on probabilistic models A. S. Bandeira, K. Scheinberg, and L. N. Vicente SIAM Journal on Optimization (SIOPT), 24(3), pp. 1238-1264, 2014 [paper] [arXiv] [bibtex] Linear Inverse problems on Erdos-Renyi graphs: Information-theoretic limits and efficient recovery E. Abbe, A. S. Bandeira, A. Bracher, and A. Singer IEEE International Symposium on Information Theory (ISIT 2014), 2014. [paper] [bibtex] [blog entry] [related blog entry] Phase retrieval from power spectra of masked signals A. S. Bandeira, Y. Chen, and D. G. Mixon Information and Inference: a Journal of the IMA, vol. 3, pp. 83-102, 2014. [arXiv] [bibtex] [blog entry] [code] Multireference alignment using semidefinite programming A. S. Bandeira, M. Charikar, A. Singer, and A. Zhu 5th Innovations in Theoretical Computer Science (ITCS 2014), 2014. [final paper] [arXiv] [bibtex] Saving phase: Injectivity and stability for phase retrieval A. S. Bandeira, J. Cahill, D. G. Mixon, and A. A. Nelson Applied and Computational Harmonic Analysis (ACHA), vol. 37, pp. 106-125, 2014. [final paper] [arXiv] [bibtex] [blog entry] Conference Proceedings version: Fundamental limits of phase retrieval at 10th International Conference on Sampling Theory and Applications, 2013. A Cheeger inequality for the graph connection Laplacian A. S. Bandeira, A. Singer, and D. A. Spielman SIAM Journal on Matrix Analysis and Applications (SIMAX), vol. 34, pp. 1611-1630, 2013. [final paper] [arXiv] [bibtex] [blog entry] Phase retrieval with polarization B. Alexeev, A. S. Bandeira, M. Fickus, and D. G. Mixon SIAM Journal on Imaging Sciences (SIIMS), vol. 7, pp. 35-66, 2013 [final paper] [arXiv] [bibtex] [blog entry] The road to deterministic matrices with the restricted isometry property A. S. Bandeira, M. Fickus, D. G. Mixon, and P. Wong Journal of Fourier Analysis and Applications, vol. 19, pp. 1123-1149, 2013. [final paper] [arxiv] [bibtex] [blog entry] - Best student paper award at the 36th Annual SIAM Southeastern Atlantic Section Conference, 2012. Certifying the restricted isometry property is hard A. S. Bandeira, E. Dobriban, D. G. Mixon, and W. Sawin IEEE Transactions on Information Theory, vol. 59, pp. 3448-3450,2013 [final paper] [arxiv] [bibtex] [blog entry] Near-optimal
phase retrieval of sparse vectors A. S. Bandeira, K. Scheinberg, and L. N. Vicente Mathematical Programming, vol. 134, pp. 223-257, 2012 [final paper] [arxiv] [bibtex] [blog entry] - INFORMS Optimization Society student paper prize, 2013. Landau's necessary density conditions for the Hankel transform L. D. Abreu and A. S. Bandeira Journal of Functional Analysis, vol. 262, pp. 1845-1866, 2012 [final paper] [arxiv] [bibtex] [blog entry] Other Manuscripts (Reports, Commentaries, Theses, Preprints, etc) A Gramian Description of the Degree 4 Generalized Elliptope A. S. Bandeira, D. Kunisky arXiv:1812.11583 [math.OC], 2018. [arXiv] The spectral norm of Gaussian matrices with correlated entries A. S. Bandeira, M. T. Boedihardjo arXiv:2104.02662 [math.PR], 2021 [arXiv] Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approach C. Kim, A. S. Bandeira, M. X. Goemans arXiv:1807.02884 [math.PR], 2018. [arXiv] Inference on Graphs via Semidefinite Programming A. S. Bandeira Proceedings of the National Academy of Sciences Commentary, 2016. [article] [preprint] A polynomial-time relaxation of the Gromov-Hausdorff distance S. Villar, A. S. Bandeira, A. J. Blumberg, and R. Ward arXiv:1610.05214 [math.GT], 2016. [arXiv] Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization A. Perry, A. S. Wein, A. S. Bandeira, and A. Moitra arXiv:1609.05573 [math.ST], 2016. [arXiv] Efficient Algorithm for Exact Recovery of Vertex Variables from Edge Measurements A. S. Bandeira Spotlight on Transactions, IEEE Computer, to appear, 2015 [preprint] Non-unique games over compact groups (Extended Abstract) A. S. Bandeira Oberwolfach Report (38/2015), 2015. Convex relaxations for certain inverse problems on graphs A. S. Bandeira PhD Thesis, Program in Applied and Computational Mathematics, Princeton University, 2015 [thesis] [bibtex] Sparse recovery in
derivative-free optimization Estimating
group transformations via convex relaxation On partially
sparse recovery A. S. Bandeira Master Thesis, Dep. Matematica, Univ. Coimbra, 2010 [thesis] [bibtex] [blog entry] Other Lecture Notes and Monographs Linear Algebra A. S. Bandeira Lecture Notes (introductory undergraduate course, Part II), Fall 2023, ETH Zurich [here is the winning entry to LA visualization student competition, Fall 2023] Mathematics of Machine Learning A. S. Bandeira and N. Zhivotovskiy Lecture Notes (undergraduate course), Spring 2021, ETH Zurich See here for videos of lectures on this material Ten Lectures and Forty-Two Open Problems in the Mathematics of Data Science A. S. Bandeira Lecture Notes, December 2015. See also MIT OCW page for a course based on this notes More available at my teaching page |
|||||||||||