D. Achlioptas and F. Mcsherry, Fast computation of low-rank matrix approximations, Journal of the ACM, vol.54, issue.2, 2007.

N. Ailon, Active learning ranking from pairwise preferences with almost optimal query complexity, NIPS, pp.810-818, 2011.

D. Erling, K. D. Andersen, and . Andersen, The mosek interior point optimizer for linear programming: an implementation of the homogeneous algorithm. High performance optimization, pp.197-232, 2000.

J. E. Atkins, E. G. Boman, and B. Hendrickson, A Spectral Algorithm for Seriation and the Consecutive Ones Problem, SIAM Journal on Computing, vol.28, issue.1, pp.297-310, 1998.
DOI : 10.1137/S0097539795285771

F. Bach and M. Jordan, Learning spectral clustering, Adv. Neural Inf. Process. Syst, vol.16, pp.305-312, 2004.

E. Barbeau, Perron's Result and a Decision on Admissions Tests, Mathematics Magazine, vol.59, issue.1, pp.12-22, 1986.
DOI : 10.2307/2690012

T. Stephen, A. Barnard, H. Pothen, and . Simon, A spectral algorithm for envelope reduction of sparse matrices. Numerical linear algebra with applications, pp.317-334, 1995.

A. Barvinok, Approximating Orthogonal Matrices by Permutation Matrices, Pure and Applied Mathematics Quarterly, vol.2, issue.4, pp.943-961, 2006.
DOI : 10.4310/PAMQ.2006.v2.n4.a3

H. Heinz, P. L. Bauschke, D. Combettes, and . Luke, Phase retrieval, error reduction algorithm, and fienup variants: a view from convex optimization, JOSA A, vol.19, issue.7, pp.1334-1345, 2002.

R. Stephen, E. J. Becker, M. C. Candès, and . Grant, Templates for convex cone problems with applications to sparse signal recovery, Mathematical Programming Computation, vol.3, issue.3, pp.165-218, 2011.

A. Ben-tal and A. Nemirovski, Lectures on modern convex optimization : analysis, algorithms, and engineering applications. MPS-SIAM series on optimization, 2001.
DOI : 10.1137/1.9780898718829

C. Berg, J. Peter-reus-christensen, and P. Ressel, Harmonic analysis on semigroups : theory of positive definite and related functions, volume 100 of Graduate texts in mathematics, 1984.
DOI : 10.1007/978-1-4612-1128-0

L. Gilliland, S. Iype, and . Jain, The protein data bank, Acta Crystallographica Section D: Biological Crystallography, vol.58, issue.6, pp.899-907, 2002.

A. Blum, G. Konjevod, S. Ravi, and . Vempala, Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems, Theoretical Computer Science, vol.235, issue.1, pp.25-42, 2000.
DOI : 10.1016/S0304-3975(99)00181-4

S. Boyd and L. Vandenberghe, Convex Optimization, 2004.

R. A. , B. , and M. E. Terry, Rank analysis of incomplete block designs: I. the method of paired comparisons, Biometrika, pp.324-345, 1952.

M. Braverman and E. Mossel, Noisy sorting without resampling, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, pp.268-276, 2008.

O. Bunk, A. Diaz, F. Pfeiffer, C. David, B. Schmitt et al., Diffractive imaging for periodic samples: retrieving one-dimensional concentration profiles across microfluidic channels, Acta Crystallographica Section A Foundations of Crystallography, vol.63, issue.4, pp.306-314, 2007.
DOI : 10.1107/S0108767307021903

J. Emmanuel, X. Candes, and . Li, Solving quadratic equations via phaselift when there are about as many equations as unknowns, Foundations of Computational Mathematics, vol.14, issue.5, pp.1017-1026, 2014.

E. J. Candes, T. Strohmer, and V. Voroninski, PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming, Communications on Pure and Applied Mathematics, vol.38, issue.5, pp.661241-1274, 2013.
DOI : 10.1002/cpa.21432

E. J. Candes, X. Li, and M. Soltanolkotabi, Phase retrieval from coded diffraction patterns, Applied and Computational Harmonic Analysis, vol.39, issue.2, 2014.
DOI : 10.1016/j.acha.2014.09.004

E. J. Candes, Y. C. Eldar, T. Strohmer, and V. Voroninski, Phase Retrieval via Matrix Completion, SIAM Review, vol.57, issue.2, pp.225-251, 2015.
DOI : 10.1137/151005099

E. J. Candes, X. Li, and M. Soltanolkotabi, Phase retrieval via wirtinger flow: Theory and algorithms. Information Theory, IEEE Transactions on, vol.61, issue.4, pp.1985-2007, 2015.

A. Chai, M. Moscoso, and G. Papanicolaou, Array imaging using intensity-only measurements, Inverse Problems, vol.27, issue.1, p.15005, 2011.
DOI : 10.1088/0266-5611/27/1/015005

M. Charikar, M. T. Hajiaghayi, H. Karloff, and S. Rao, ??? 2 2 Spreading Metrics for Vertex Ordering Problems, Algorithmica, vol.15, issue.2, pp.577-604, 2010.
DOI : 10.1007/s00453-008-9191-1

S. Clémençon and J. Jakubowicz, Kantorovich distances between rankings with applications to rank aggregation, Machine Learning and Knowledge Discovery in Databases, pp.248-263, 2010.

J. Commins, C. Toft, and M. A. Fares, Computational Biology Methods and Their Application to the Comparative Genomics of Endocellular Symbiotic Bacteria of Insects, Biological Procedures Online, vol.26, issue.2, pp.52-78, 2009.
DOI : 10.1007/s12575-009-9004-1

M. Thomas, J. A. Cover, and . Thomas, Elements of information theory, 2012.

M. Cucuringu, Sync-rank: Robust ranking, constrained ranking and rank aggregation via eigenvector and semidefinite programming synchronization, 2015.

G. B. Dantzig, Linear programming and extensions, 1963.
DOI : 10.1515/9781400884179

A. Aspremont and N. Karoui, Weak Recovery Conditions from Graph Partitioning Bounds and Order Statistics, Mathematics of Operations Research, vol.38, issue.2, pp.228-247, 2013.
DOI : 10.1287/moor.1120.0581
URL : https://hal.archives-ouvertes.fr/hal-00907541

A. Aspremont and S. Boyd, Relaxations and randomized methods for nonconvex qcqps, EE392o Class Notes, 2003.

J. Borda, Mémoire sur les élections au scrutin, 1781.

N. De and C. , Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix, p.1785

P. Diaconis and R. L. Graham, Spearman's footrule as a measure of disarray, Journal of the Royal Statistical Society. Series B (Methodological), pp.262-268, 1977.

M. Dierolf, A. Menzel, P. Thibault, P. Schneider, M. Cameron et al., Ptychographic X-ray computed tomography at the nanoscale, Nature, vol.109, issue.7314, pp.467436-439, 2010.
DOI : 10.1038/nature09419

C. Ding and X. He, Linearized cluster assignment via spectral ordering, Twenty-first international conference on Machine learning , ICML '04, p.30, 2004.
DOI : 10.1145/1015330.1015407

C. John, L. W. Duchi, M. I. Mackey, and . Jordan, On the consistency of ranking algorithms, Proceedings of the 27th International Conference on Machine Learning

C. John, L. Duchi, M. I. Mackey, and . Jordan, The asymptotics of ranking algorithms. The Annals of Statistics, pp.2292-2323, 2013.

C. Dwork, R. Kumar, M. Naor, and D. Sivakumar, Rank aggregation methods for the Web, Proceedings of the tenth international conference on World Wide Web , WWW '01, 2001.
DOI : 10.1145/371920.372165

C. Dwork, R. Kumar, M. Naor, and D. Sivakumar, Rank aggregation methods for the Web, Proceedings of the tenth international conference on World Wide Web , WWW '01, pp.613-622, 2001.
DOI : 10.1145/371920.372165

P. Erdös and A. Rényi, On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci, vol.5, pp.17-61, 1960.

P. Erdös and A. Rényi, On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci, vol.5, pp.17-61, 1960.

G. Even, J. S. Naor, S. Rao, and B. Schieber, Divide-and-conquer approximation algorithms via spreading metrics, Journal of the ACM, vol.47, issue.4, pp.585-616, 2000.
DOI : 10.1145/347476.347478

U. Feige, Approximating the Bandwidth via Volume Respecting Embeddings, Journal of Computer and System Sciences, vol.60, issue.3, pp.510-539, 2000.
DOI : 10.1006/jcss.1999.1682

U. Feige and J. R. Lee, An improved approximation ratio for the minimum linear arrangement problem, Information Processing Letters, vol.101, issue.1, pp.26-29, 2007.
DOI : 10.1016/j.ipl.2006.07.009

U. Feige, P. Raghavan, D. Peleg, and E. Upfal, Computing with Noisy Information, SIAM Journal on Computing, vol.23, issue.5, pp.1001-1018, 1994.
DOI : 10.1137/S0097539791195877

J. R. Fienup, Phase retrieval algorithms: a comparison, Applied Optics, vol.21, issue.15, pp.2758-2769, 1982.
DOI : 10.1364/AO.21.002758

F. Fogel, R. Jenatton, F. Bach, and A. , Convex Relaxations for Permutation Problems, SIAM Journal on Matrix Analysis and Applications, vol.36, issue.4, 2013.
DOI : 10.1137/130947362
URL : https://hal.archives-ouvertes.fr/hal-00907528

L. Ford and D. R. Fulkerson, Flows in networks, volume 1962, 1962.

M. Frank and P. Wolfe, An algorithm for quadratic programming. Naval research logistics quarterly, pp.95-110, 1956.

Y. Freund, R. Iyer, R. E. Schapire, and Y. Singer, An efficient boosting algorithm for combining preferences. The Journal of machine learning research, pp.933-969, 2003.

A. Frieze and R. Kannan, Quick Approximation to Matrices and Applications, Combinatorica, vol.19, issue.2, pp.175-220, 1999.
DOI : 10.1007/s004930050052

D. R. Fulkerson and O. A. Gross, Incidence matrices and interval graphs, Pacific Journal of Mathematics, vol.15, issue.3, p.835, 1965.
DOI : 10.2140/pjm.1965.15.835

C. Gemma, E. Garriga, H. Junttila, and . Mannila, Banded structure in binary matrices. Knowledge and information systems, pp.197-226, 2011.

A. George and A. Pothen, An Analysis of Spectral Envelope Reduction via Quadratic Assignment Problems, SIAM Journal on Matrix Analysis and Applications, vol.18, issue.3, pp.706-732, 1997.
DOI : 10.1137/S089547989427470X

R. Gerchberg and W. Saxton, A practical algorithm for the determination of phase from image and diffraction plane pictures, Optik, vol.35, pp.237-246, 1972.

X. Michel and . Goemans, Smallest compact formulation for the permutahedron, Mathematical Programming, pp.1-7, 2014.

M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM, vol.42, issue.6, pp.1115-1145, 1995.
DOI : 10.1145/227683.227684

D. Griffin and J. Lim, Signal estimation from modified short-time fourier transform. Acoustics, Speech and Signal Processing, IEEE Transactions on, vol.32, issue.2, pp.236-243, 1984.

M. Grötschel, L. Lovász, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, 1988.

L. Hagen and A. B. Kahng, New spectral methods for ratio cut partitioning and clustering . Computer-aided design of integrated circuits and systems, ieee transactions on, vol.11, issue.9, pp.1074-1085, 1992.

R. W. Harrison, Phase problem in crystallography, Journal of the Optical Society of America A, vol.10, issue.5, pp.1046-1055, 1993.
DOI : 10.1364/JOSAA.10.001046

C. Helmberg, F. Rendl, R. J. Vanderbei, and H. Wolkowicz, An Interior-Point Method for Semidefinite Programming, SIAM Journal on Optimization, vol.6, issue.2, pp.342-361, 1996.
DOI : 10.1137/0806020

R. Herbrich, T. Minka, and T. Graepel, Trueskill TM : A bayesian skill rating system, Advances in Neural Information Processing Systems, pp.569-576, 2006.

R. Frank and . Hodson, The La Tène cemetery at Münsingen-Rain: catalogue and relative chronology, 1968.

L. Huang, D. Yan, M. I. Jordan, and N. Taft, Spectral Clustering with Perturbed Data, Advances in Neural Information Processing Systems (NIPS), 2008.

J. Peter and . Huber, Pairwise comparison and ranking: optimum properties of the row sum procedure. The annals of mathematical statistics, pp.511-520, 1963.

R. David and . Hunter, MM algorithms for generalized bradley-terry models, Annals of Statistics, pp.384-406, 2004.

G. Kevin, . Jamieson, D. Robert, and . Nowak, Active ranking using pairwise comparisons, NIPS, pp.2240-2248, 2011.

X. Jiang, L. Lim, Y. Yao, and Y. Ye, Statistical ranking and combinatorial Hodge theory, Mathematical Programming, vol.48, issue.2, pp.203-244, 2011.
DOI : 10.1007/s10107-010-0419-x

T. Joachims, Optimizing search engines using clickthrough data, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining , KDD '02, pp.133-142, 2002.
DOI : 10.1145/775047.775067

I. Johnson, K. Jefimovs, O. Bunk, C. David, M. Dierolf et al., Coherent Diffractive Imaging Using Phase Front Modifications, Physical Review Letters, vol.100, issue.15, p.100155503, 2008.
DOI : 10.1103/PhysRevLett.100.155503

L. Norman, S. Johnson, and . Kotz, Distributions in statistics: Continuous multivariate distributions, 1972.

N. K. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, vol.244, issue.S, pp.373-395, 1984.
DOI : 10.1007/BF02579150

J. P. Keener, The Perron???Frobenius Theorem and the Ranking of Football Teams, SIAM Review, vol.35, issue.1, pp.80-93, 1993.
DOI : 10.1137/1035004

G. David and . Kendall, Abundance matrices and seriation in archaeology. Probability Theory and Related Fields, pp.104-112, 1971.

M. G. Kendall, B. Babington, and . Smith, On the method of paired comparisons, Biometrika, pp.31-34, 1940.

C. Kenyon-mathieu and W. Schudy, How to rank with few errors, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing , STOC '07, pp.95-103, 2007.
DOI : 10.1145/1250790.1250806

L. G. Khachiyan, A polynomial algorithm in linear programming (in Russian) Doklady Akedamii Nauk SSSR, pp.1093-1096, 1979.

J. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM, vol.46, issue.5, pp.604-632, 1999.
DOI : 10.1145/324133.324140

J. Kuczynski and H. Wozniakowski, Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start, SIAM Journal on Matrix Analysis and Applications, vol.13, issue.4, pp.1094-1122, 1992.
DOI : 10.1137/0613066

M. Laurent and M. Seminaroti, The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure, Operations Research Letters, vol.43, issue.1, pp.103-109, 2015.
DOI : 10.1016/j.orl.2014.12.009

E. L. Lawler, The Quadratic Assignment Problem, Management Science, vol.9, issue.4, pp.586-599, 1963.
DOI : 10.1287/mnsc.9.4.586

I. Liiv, Seriation and matrix reordering methods: An historical overview. Statistical analysis and data mining, pp.70-91, 2010.

C. Han, L. , and S. Wright, Beyond the birkhoff polytope: Convex relaxations for vector permutation problems, Advances in Neural Information Processing Systems, pp.2168-2176, 2014.

L. Lovász and A. Schrijver, Cones of Matrices and Set-Functions and 0???1 Optimization, SIAM Journal on Optimization, vol.1, issue.2, pp.166-190, 1991.
DOI : 10.1137/0801013

R. Luce, Individual choice behavior, 1959.

J. Meidanis, O. Porto, and G. P. Telles, On the consecutive ones property, Discrete Applied Mathematics, vol.88, issue.1-3, pp.325-354, 1998.
DOI : 10.1016/S0166-218X(98)00078-X

J. Miao, T. Ishikawa, Q. Shen, and T. Earnest, Extending X-Ray Crystallography to Allow the Imaging of Noncrystalline Materials, Cells, and Single Protein Complexes, Annual Review of Physical Chemistry, vol.59, issue.1, pp.387-410, 2008.
DOI : 10.1146/annurev.physchem.59.032607.093642

S. Negahban, S. Oh, and D. Shah, Iterative ranking from pairwise comparisons, NIPS, pp.2483-2491, 2012.

A. Nemirovski, Sums of random symmetric matrices and quadratic optimization under orthogonality constraints, Mathematical Programming, vol.2, issue.97, pp.283-317, 2007.
DOI : 10.1007/s10107-006-0033-0

A. Nemirovski and U. Rothblum, On complexity of matrix scaling, Linear Algebra and its Applications, vol.302, issue.303, pp.435-460, 1999.
DOI : 10.1016/S0024-3795(99)00212-8

A. Nemirovskii and D. Yudin, Problem complexity and method efficiency in optimization, Nauka, 1979.

Y. Nesterov, Global quadratic optimization via conic relaxation. Number 9860, CORE Discussion Paper, 1998.

Y. Nesterov, Introductory Lectures on Convex Optimization, 2003.
DOI : 10.1007/978-1-4419-8853-9

Y. Nesterov and A. Nemirovskii, Interior-point polynomial algorithms in convex programming, Society for Industrial and Applied Mathematics, 1994.
DOI : 10.1137/1.9781611970791

A. Ng, M. Jordan, and Y. Weiss, On spectral clustering: Analysis and an algorithm, Advances in Neural Information Processing Systems, p.849, 2002.

L. Page, S. Brin, R. Motwani, and T. Winograd, The pagerank citation ranking: Bringing order to the web, 1998.

L. Portugal, F. Bastos, J. Júdice, J. Paixao, and T. Terlaky, An Investigation of Interior-Point Algorithms for the Linear Transportation Problem, SIAM Journal on Scientific Computing, vol.17, issue.5, pp.1202-1223, 1996.
DOI : 10.1137/S1064827593258280

A. Rajkumar and S. Agarwal, A statistical convergence perspective of algorithms for rank aggregation from pairwise data, Proceedings of the 31st International Conference on Machine Learning, pp.118-126, 2014.

S. Rao and A. W. Richa, New Approximation Techniques for Some Linear Ordering Problems, SIAM Journal on Computing, vol.34, issue.2, pp.388-404, 2005.
DOI : 10.1137/S0097539702413197

W. S. Robinson, A Method for Chronologically Ordering Archaeological Deposits, American Antiquity, vol.16, issue.04, pp.293-301, 1951.
DOI : 10.2307/276978

V. Roulet, Alexandre d'Aspremont, and Francis Bach. Supervised clustering in the data cube, 2015.

L. Thomas and . Saaty, The analytic hierarchy process: planning, priority setting, resources allocation, 1980.

L. Thomas and . Saaty, Decision-making with the ahp: Why is the principal eigenvector necessary, European journal of operational research, vol.145, issue.1, pp.85-91, 2003.

W. W. Schapire, R. E. Cohen, and Y. Singer, Learning to order things, Advances in Neural Information Processing Systems 10: Proceedings of the 1997 Conference, p.451, 1998.

O. Shamir and N. Tishby, Spectral clustering on a budget, International Conference on Artificial Intelligence and Statistics, pp.661-669, 2011.

Y. Shechtman, Y. C. Eldar, O. Cohen, H. N. Chapman, J. Miao et al., Phase retrieval with application to optical imaging. arXiv preprint arXiv:1402, 2014.

W. Sheppard, On the calculation of the double integral expressing normal correlation, Transactions of the Cambridge Philosophical Society, vol.19, pp.23-66, 1900.

J. Shi and J. Malik, Normalized cuts and image segmentation. Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol.22, issue.8, pp.888-905, 2000.

N. Z. Shor, Quadratic optimization problems, Soviet Journal of Computer and Systems Sciences, vol.25, pp.1-11, 1987.

E. Sibony, S. Clemençon, and J. Jakubowicz, Mra-based statistical learning from incomplete rankings, Proceedings of the 32nd International Conference on Machine Learning (ICML-15), pp.1432-1441, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01270543

R. Sinkhorn, A relationship between arbitrary positive matrices and doubly stochastic matrices. The annals of mathematical statistics, pp.876-879, 1964.
DOI : 10.1214/aoms/1177703591

A. So, Moment inequalities for sums of random matrices and their applications in optimization, Mathematical Programming, vol.2, issue.1, pp.125-151, 2011.
DOI : 10.1007/s10107-009-0330-5

G. W. Stewart and J. Sun, Matrix perturbation theory, 1990.

M. Stoer and F. Wagner, A simple min-cut algorithm, Journal of the ACM, vol.44, issue.4, pp.585-591, 1997.
DOI : 10.1145/263867.263872

K. C. Toh, M. J. Todd, and R. H. Tutuncu, SDPT3 ??? A Matlab software package for semidefinite programming, Version 1.3, Optimization Methods and Software, vol.79, issue.1-4, pp.545-581, 1999.
DOI : 10.1287/moor.19.1.53

S. Vigna, Spectral ranking. arXiv preprint, 2009.

M. Vojnovic, Contest theory: Incentive mechanisms and ranking methods, 2015.
DOI : 10.1017/CBO9781139519366

U. Von and L. , A tutorial on spectral clustering, Statistics and computing, vol.17, issue.4, pp.395-416, 2007.

U. Von-luxburg, M. Belkin, and O. Bousquet, Consistency of spectral clustering. The Annals of Statistics, pp.555-586, 2008.

N. Vuokko, Consecutive ones property and spectral ordering, Proceedings of the 10th SIAM International Conference on Data Mining (SDM'10), pp.350-360, 2010.
DOI : 10.1137/1.9781611972801.31
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.187.2996

D. Wagner and F. Wagner, Between Min Cut and Graph Bisection, 1993.
DOI : 10.1007/3-540-57182-5_65
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.604

I. Waldspurger and S. Mallat, Time-frequency phase recovery. Working paper, 2012.

I. Waldspurger, A. Aspremont, and S. Mallat, Phase recovery, MaxCut and complex semidefinite programming, Mathematical Programming, vol.16, issue.3, pp.47-81, 2015.
DOI : 10.1007/s10107-013-0738-9
URL : https://hal.archives-ouvertes.fr/hal-00907535

L. Fabian, M. I. Wauthier, N. Jordan, and . Jojic, Efficient ranking from pairwise comparisons, Proceedings of the 30th International Conference on Machine Learning (ICML), 2013.

K. Q. Weinberger and L. K. Saul, Unsupervised Learning of Image Manifolds by Semidefinite Programming, International Journal of Computer Vision, vol.26, issue.1, pp.77-90, 2006.
DOI : 10.1007/s11263-005-4939-z

Y. Yu, T. Wang, and R. J. Samworth, A useful variant of the Davis???Kahan theorem for statisticians, Biometrika, vol.102, issue.2, pp.315-323, 2015.
DOI : 10.1093/biomet/asv008

E. Zermelo, Die Berechnung der Turnier-Ergebnisse als ein Maximumproblem der Wahrscheinlichkeitsrechnung, Mathematische Zeitschrift, vol.29, issue.1, pp.436-460, 1929.
DOI : 10.1007/BF01180541

Q. Zhao, E. Stefan, F. Karisch, H. Rendl, and . Wolkowicz, Semidefinite programming relaxations for the quadratic assignment problem, Journal of Combinatorial Optimization, vol.2, issue.1, pp.71-109, 1998.
DOI : 10.1023/A:1009795911987