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


 




Home

Publications

CV >

Teaching

Videos
















My research interests include, among other things: High Dimensional Probability, Mathematical Statistics, Theoretical Computer Science, Combinatorics, and Optimization.

Calendar with events of interest (some streamed live):


Some announcements:

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.
 



Publications



Recent Lecture Notes, Books 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)


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


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]


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

6
th 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]

Computation of sparse low degree interpolating polynomials and their application to derivative-free optimization
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
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]

Computation of sparse low degree interpolating polynomials and ther application to Derivative-Free Optimization
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