Department of Mathematics,
Courant Institute of Mathematical Sciences, New York University

Address:
251 Mercer Street, Room 1123
New York, NY 10012, USA


I also spend time in Room 603 of the NYU Center for Data Science at 60 Fifth Av., NY 10011




 
Afonso S. Bandeira
bandeira [at] cims [dot] nyu [dot] edu


I am an Assistant Professor of Mathematics at the Courant Institute of Mathematical Sciences with a joint appointment in the Center for Data Science at NYU. I am a member of the NYU Math and Data Group.

I was fortunate to have had Amit Singer as my PhD adviser at Princeton. My thesis is available here.

 
(Copyright: NYU Photo Bureau: Kahn)











Home

Research Interests

Publications

CV >

Blog >

Teaching >










Research Interests
  • Applied Mathematics
  • Optimization
  • Probability
  • Information Theory
  • Signal Processing
  • Mathematics of Data Science
  • ...
I tend to be interested in the mathematics behind certain processes which extract information from limited or corrupted data.

You can visit my research Blog and see my list of publications below for more information.


Publications


Submitted, In Press or Preprint


Optimal rates of estimation for multi-reference alignment
A. S. Bandeira, P. Rigollet, J. Weed
arXiv:1702.08546 [math.ST], 2017.
[arXiv]


Statistical limits of spiked tensor models
A. Perry, A. S. Wein, and A. S. Bandeira
arXiv:1611.04505 [math.ST], 2016.
[arXiv]


Marcenko-Pastur Law for Kendall's Tau
A. S. Bandeira, A. Lodhia, and P. Rigollet
arXiv:1611.04505 [math.ST], 2016.
[arXiv]


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]

Message-passing algorithms for synchronization problems over compact groups
A. Perry, A. S. Wein, A. S. Bandeira, and A. Moitra
arXiv:1610.04583 [cs.IT], 2016.
[arXiv]

Resilience for the Littlewood-Offord Problem
A. S. Bandeira, A. Ferber, and M. Kwan
arXiv:1609.08136 [math.CO], 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]


Non-unique games over compact groups and orientation estimation in cryo-EM

A. S. Bandeira, Y. Chen, and A. Singer
arXiv:1505.03840 [cs.CV], 2015.
[arXiv]
[bibtex]


Discrete uncertainty principles and sparse signal processing
A. S. Bandeira, M. E. Lewis, and D. G. Mixon
arXiv:1504.01014 [cs.IT], 2015.
[arXiv]
[bibtex]

Multisection in the stochastic block model using semidefinite programming
N. Agarwal, A. S. Bandeira, K. Koiliaris, A. Kolla
arXiv:1507.02323 [cs.DS], 2015.
[arXiv] [bibtex]

Compressive classification and the rare eclipse problem
A. S. Bandeira, D. G. Mixon, and B. Recht
arXiv:1404.3203 [cs.LG], 2014.
[arXiv]
[bibtex] [blog entry]



Lecture Notes and Monographs:


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


Peer-Reviewed Publications


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]


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.

Longer technical report: 
SE-Synch: A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group
[arXiv] [technical report]

Random Laplacian matrices and convex relaxations
A. S. Bandeira
Foundations of Computational Mathematics, to appear.
[arXiv]
[bibtex]


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), to appear.
[arXiv]
[bibtex]


Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
A. S. Bandeira, N. Boumal, and A. Singer
Mathematical Programming SERIES A, to appear, 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, to appear, 2016.
[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 , to appear, 2016.
[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, to appear, 2016.
[arXiv]
[bibtex]


A conditional construction of restricted isometries

A. S. Bandeira, D. G. Mixon, and J. Moreira
International Mathematics Research Notices, to appear.
[arXiv]
[bibtex]
[blog entry]

Derandomizing restricted isometries via the Legendre symbol
A. S. Bandeira, M. Fickus, D. G. Mixon, and J. Moreira
Constructive Approximation, to appear, 2015.
[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, to appear, 2015.
[arXiv]
[bibtex] [blog entry]
[talk]

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]

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]


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]


Technical Reports, Theses, and other Articles

Inference on Graphs via Semidefinite Programming
A. S. Bandeira
Proceedings of the National Academy of Sciences Commentary, 2016.
[article] [preprint]


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]