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
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
|
My research interests include High
Dimensional Probability, Mathematical
Statistics, Theoretical Computer Science,
Combinatorics, and Optimization.
Calendar with events of interest (some streamed live): |
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.
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 and D. G. Mixon
Wavelets and Sparsity XV, Proceedings of SPIE
Optics+Photonics, 2013
[arXiv] [bibtex]
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
A. S. Bandeira
INFORMS OS Today, The Newsletter of the INFORMS
Optimization Society, 2014.
[article]
Estimating
group transformations via convex relaxation
A. S. Bandeira
Oberwolfach Report (18/2014), Volume 11, Issue 2, 2014.
[article]
On partially
sparse recovery
A. S. Bandeira, K. Scheinberg, and L. N. Vicente
Preprint 11-13, Dept. of Mathematics, Univ. Coimbra,
2011.
[arxiv] [bibtex]
A. S. Bandeira
Master Thesis, Dep. Matematica, Univ. Coimbra, 2010
[thesis] [bibtex] [blog entry]