|
|
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
|
|
![]() |
|||||||
|
|||||||||||
Group Members: Antoine Maillard, March Boedihardjo, Pedro Abdalla, Daniil Dmitriev, Konstantin Donhauser, Anastasia Kireeva, Petar Nizic-Nikolac. 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. Publications Submitted, In Press, and selected Preprints 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] Guarantees for Spontaneous Synchronization on Random Geometric Graphs P. Abdalla, A. S. Bandeira, C. Invernizzi arXiv:2208.12246 [math.PR], 2022 [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, to appear. [arXiv] Matrix Concentration Inequalities and Free Probability A. S. Bandeira, M. T. Boedihardjo, R. van Handel arXiv:2108.06312 [math.PR], 2021 [arXiv] Subexponential-Time Algorithms for Sparse PCA Y. Ding, D. Kunisky, A. S. Wein, A. S. Bandeira Journal of the FoCM, to appear. [arXiv] [related video] A Gramian Description of the Degree 4 Generalized Elliptope A. S. Bandeira, D. Kunisky arXiv:1812.11583 [math.OC], 2018. [arXiv] Estimation under group actions: recovering orbits from invariants A. S. Bandeira, B. Blum-Smith, Joe Kileel, A. Perry, J. Weed, A. S. Wein arXiv:1712.10163 [math.ST], 2017. [arXiv] [related video] Books, Lecture Notes and Monographs 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) 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 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 More available at my teaching page Peer-Reviewed Publications 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] Technical Reports, Theses, Preprints, Unpublished Manuscripts, and other Articles 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] |
|||||||||||