August  2013, 7(3): 907-926. doi: 10.3934/ipi.2013.7.907

Statistical ranking using the $l^{1}$-norm on graphs

1. 

Department of Mathematics, University of California, Los Angeles 90095, United States, United States

2. 

Department of Mathematics, UCLA, Los Angeles, CA 90095-1555

Received  January 2012 Revised  January 2013 Published  September 2013

We consider the problem of establishing a statistical ranking for a set of alternatives from a dataset which consists of an (inconsistent and incomplete) set of quantitative pairwise comparisons of the alternatives. If we consider the directed graph where vertices represent the alternatives and the pairwise comparison data is a function on the arcs, then the statistical ranking problem is to find a potential function, defined on the vertices, such that the gradient of the potential optimally agrees with the pairwise comparisons. Potentials, optimal in the $l^{2}$-norm sense, can be found by solving a least-squares problem on the digraph and, recently, the residual has been interpreted using the Hodge decomposition (Jiang et. al., 2010). In this work, we consider an $l^{1}$-norm formulation of the statistical ranking problem. We describe a fast graph-cut approach for finding $\epsilon$-optimal solutions, which has been used successfully in image processing and computer vision problems. Applying this method to several datasets, we demonstrate its efficacy at finding solutions with sparse residual.
Citation: Braxton Osting, Jérôme Darbon, Stanley Osher. Statistical ranking using the $l^{1}$-norm on graphs. Inverse Problems & Imaging, 2013, 7 (3) : 907-926. doi: 10.3934/ipi.2013.7.907
References:
[1]

Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 264, Springer-Verlag, Berlin, 1984. doi: 10.1007/978-3-642-69512-4.  Google Scholar

[2]

Management Science, 32 (1986), 1642-1647. doi: 10.1287/mnsc.32.12.1642.  Google Scholar

[3]

Management Science, 49 (2003), 950-964. Google Scholar

[4]

Prentice Hall, Inc., Englewood Cliffs, NJ, 1993.  Google Scholar

[5]

, 2011 ATP world tour media guide,, accessed 10/5/2011. Available from: , ().   Google Scholar

[6]

IEEE Transactions on Image Processing, 16 (2007), 698-709. doi: 10.1109/TIP.2006.888351.  Google Scholar

[7]

IEEE Transactions on Pattern Analysis and Machine Intelligence, 26 (2004), 1124-1137. Google Scholar

[8]

IEEE Transactions on Pattern Analysis and Machine Intelligence, 23 (2001), 1222-1239. Google Scholar

[9]

4OR, 5 (2007), 5-60. doi: 10.1007/s10288-007-0036-6.  Google Scholar

[10]

Management Science, 31 (1985), 26-32. doi: 10.1287/mnsc.31.1.26.  Google Scholar

[11]

IEEE Transactions on Information Theory, 52 (2006), 5406-5425. doi: 10.1109/TIT.2006.885507.  Google Scholar

[12]

Ph.D. thesis, Ecole Nationale Supérieure des Télćommunications, October, 2005. Google Scholar

[13]

Hafner Publishing Co., New York, 1963.  Google Scholar

[14]

, C. Dwork, R. Kumar, M. Naor and D. Sivakumar,, Rank aggregation revisited., ().   Google Scholar

[15]

Proceedings International Conference World Wide Web (WWW'01), 10 (2001), 613-622. Google Scholar

[16]

Universitext, Springer-Verlag, New York, 1992. doi: 10.1007/978-1-4612-0933-1.  Google Scholar

[17]

in "Recent Advances in Learning and Control" (eds. V. Blondel, S. Boyd and H. Kimura), Lecture Notes in Control and Information Sciences, 371, Springer, London, (2008), 95-110. Available from: http://stanford.edu/ boyd/graph_dcp.html. doi: 10.1007/978-1-84800-155-8_7.  Google Scholar

[18]

April, 2011. Available from: http://cvxr.com/cvx. Google Scholar

[19]

Mathematics of Operations Research, 28 (2003), 1-38. doi: 10.1287/moor.28.1.1.14260.  Google Scholar

[20]

in "Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining," ACM, New York, (2011), 60-68. doi: 10.1145/2020408.2020425.  Google Scholar

[21]

Journal of the American Statistical Association, 72 (1977), 278-289. Google Scholar

[22]

arXiv:1011.1716v4, (2011). Google Scholar

[23]

Optimization Methods and Software, 23 (2008), 741-762. doi: 10.1080/10556780802402432.  Google Scholar

[24]

TutORials in Operations Research, 7 (2010), 116-141. Google Scholar

[25]

, Jester: The online joke recommender,, accessed 9/9/2011. Available from: , ().   Google Scholar

[26]

Math. Program. Ser. B, 127 (2011), 203-244. doi: 10.1007/s10107-010-0419-x.  Google Scholar

[27]

The MIT Press, 1962. Google Scholar

[28]

Discrete Optimization, 6 (2009), 378-393. doi: 10.1016/j.disopt.2009.04.006.  Google Scholar

[29]

IEEE Transactions on Pattern Analysis and Machine Intelligence, 2 (2004), 147-159. Google Scholar

[30]

Monographs on Statistics and Applied Probability, 64, Chapman & Hall, London, 1995.  Google Scholar

[31]

IEEE Conference on Computer Vision and Pattern Recognition, (2011), 153-160. Google Scholar

[32]

SIAM Society for Industrial and Applied Mathematics, 2003. Google Scholar

[33]

Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, NJ, 1970.  Google Scholar

[34]

Pure and Applied Mathematics (New York), A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York, 1984.  Google Scholar

[35]

Economic Theory, 15 (2000), 1-53. doi: 10.1007/s001990050001.  Google Scholar

[36]

, Scrapy web crawling framework,, accessed 10/5/2011. Available from: , ().   Google Scholar

[37]

IEEE Transactions on Systems, Man, and Cybernetics, 7 (1977), 117-121. Google Scholar

[38]

, Tennis datenbank website,, accessed 10/5/2011. Available from: , ().   Google Scholar

[39]

Linear Algebra Appl., 438 (2013), 1012-1024. doi: 10.1016/j.laa.2012.08.028.  Google Scholar

[40]

preprint, arXiv:1201.4632, (2012). Google Scholar

[41]

in "Proceedings of the 19th ACM International Conference on Multimedia," ACM, New York, (2011), 393-402. doi: 10.1145/2072298.2072350.  Google Scholar

[42]

, Yahoo! Webscope dataset: ydata-ymovies-user-movie-ratings-content-v1_0,, accessed 10/5/2011. Available from: , ().   Google Scholar

[43]

The American Political Science Review, 82 (1988), 1231-1244. Google Scholar

show all references

References:
[1]

Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 264, Springer-Verlag, Berlin, 1984. doi: 10.1007/978-3-642-69512-4.  Google Scholar

[2]

Management Science, 32 (1986), 1642-1647. doi: 10.1287/mnsc.32.12.1642.  Google Scholar

[3]

Management Science, 49 (2003), 950-964. Google Scholar

[4]

Prentice Hall, Inc., Englewood Cliffs, NJ, 1993.  Google Scholar

[5]

, 2011 ATP world tour media guide,, accessed 10/5/2011. Available from: , ().   Google Scholar

[6]

IEEE Transactions on Image Processing, 16 (2007), 698-709. doi: 10.1109/TIP.2006.888351.  Google Scholar

[7]

IEEE Transactions on Pattern Analysis and Machine Intelligence, 26 (2004), 1124-1137. Google Scholar

[8]

IEEE Transactions on Pattern Analysis and Machine Intelligence, 23 (2001), 1222-1239. Google Scholar

[9]

4OR, 5 (2007), 5-60. doi: 10.1007/s10288-007-0036-6.  Google Scholar

[10]

Management Science, 31 (1985), 26-32. doi: 10.1287/mnsc.31.1.26.  Google Scholar

[11]

IEEE Transactions on Information Theory, 52 (2006), 5406-5425. doi: 10.1109/TIT.2006.885507.  Google Scholar

[12]

Ph.D. thesis, Ecole Nationale Supérieure des Télćommunications, October, 2005. Google Scholar

[13]

Hafner Publishing Co., New York, 1963.  Google Scholar

[14]

, C. Dwork, R. Kumar, M. Naor and D. Sivakumar,, Rank aggregation revisited., ().   Google Scholar

[15]

Proceedings International Conference World Wide Web (WWW'01), 10 (2001), 613-622. Google Scholar

[16]

Universitext, Springer-Verlag, New York, 1992. doi: 10.1007/978-1-4612-0933-1.  Google Scholar

[17]

in "Recent Advances in Learning and Control" (eds. V. Blondel, S. Boyd and H. Kimura), Lecture Notes in Control and Information Sciences, 371, Springer, London, (2008), 95-110. Available from: http://stanford.edu/ boyd/graph_dcp.html. doi: 10.1007/978-1-84800-155-8_7.  Google Scholar

[18]

April, 2011. Available from: http://cvxr.com/cvx. Google Scholar

[19]

Mathematics of Operations Research, 28 (2003), 1-38. doi: 10.1287/moor.28.1.1.14260.  Google Scholar

[20]

in "Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining," ACM, New York, (2011), 60-68. doi: 10.1145/2020408.2020425.  Google Scholar

[21]

Journal of the American Statistical Association, 72 (1977), 278-289. Google Scholar

[22]

arXiv:1011.1716v4, (2011). Google Scholar

[23]

Optimization Methods and Software, 23 (2008), 741-762. doi: 10.1080/10556780802402432.  Google Scholar

[24]

TutORials in Operations Research, 7 (2010), 116-141. Google Scholar

[25]

, Jester: The online joke recommender,, accessed 9/9/2011. Available from: , ().   Google Scholar

[26]

Math. Program. Ser. B, 127 (2011), 203-244. doi: 10.1007/s10107-010-0419-x.  Google Scholar

[27]

The MIT Press, 1962. Google Scholar

[28]

Discrete Optimization, 6 (2009), 378-393. doi: 10.1016/j.disopt.2009.04.006.  Google Scholar

[29]

IEEE Transactions on Pattern Analysis and Machine Intelligence, 2 (2004), 147-159. Google Scholar

[30]

Monographs on Statistics and Applied Probability, 64, Chapman & Hall, London, 1995.  Google Scholar

[31]

IEEE Conference on Computer Vision and Pattern Recognition, (2011), 153-160. Google Scholar

[32]

SIAM Society for Industrial and Applied Mathematics, 2003. Google Scholar

[33]

Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, NJ, 1970.  Google Scholar

[34]

Pure and Applied Mathematics (New York), A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York, 1984.  Google Scholar

[35]

Economic Theory, 15 (2000), 1-53. doi: 10.1007/s001990050001.  Google Scholar

[36]

, Scrapy web crawling framework,, accessed 10/5/2011. Available from: , ().   Google Scholar

[37]

IEEE Transactions on Systems, Man, and Cybernetics, 7 (1977), 117-121. Google Scholar

[38]

, Tennis datenbank website,, accessed 10/5/2011. Available from: , ().   Google Scholar

[39]

Linear Algebra Appl., 438 (2013), 1012-1024. doi: 10.1016/j.laa.2012.08.028.  Google Scholar

[40]

preprint, arXiv:1201.4632, (2012). Google Scholar

[41]

in "Proceedings of the 19th ACM International Conference on Multimedia," ACM, New York, (2011), 393-402. doi: 10.1145/2072298.2072350.  Google Scholar

[42]

, Yahoo! Webscope dataset: ydata-ymovies-user-movie-ratings-content-v1_0,, accessed 10/5/2011. Available from: , ().   Google Scholar

[43]

The American Political Science Review, 82 (1988), 1231-1244. Google Scholar

[1]

Ahmad Mousavi, Zheming Gao, Lanshan Han, Alvin Lim. Quadratic surface support vector machine with L1 norm regularization. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021046

[2]

Jiangang Qi, Bing Xie. Extremum estimates of the $ L^1 $-norm of weights for eigenvalue problems of vibrating string equations based on critical equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (7) : 3505-3516. doi: 10.3934/dcdsb.2020243

[3]

Meng Ding, Ting-Zhu Huang, Xi-Le Zhao, Michael K. Ng, Tian-Hui Ma. Tensor train rank minimization with nonlocal self-similarity for tensor completion. Inverse Problems & Imaging, 2021, 15 (3) : 475-498. doi: 10.3934/ipi.2021001

[4]

Kuei-Hu Chang. A novel risk ranking method based on the single valued neutrosophic set. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021065

[5]

Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006

[6]

Lunji Song, Wenya Qi, Kaifang Liu, Qingxian Gu. A new over-penalized weak galerkin finite element method. Part Ⅱ: Elliptic interface problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2581-2598. doi: 10.3934/dcdsb.2020196

[7]

Kaifang Liu, Lunji Song, Shan Zhao. A new over-penalized weak galerkin method. Part Ⅰ: Second-order elliptic problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2411-2428. doi: 10.3934/dcdsb.2020184

[8]

Fei Liu, Xiaokai Liu, Fang Wang. On the mixing and Bernoulli properties for geodesic flows on rank 1 manifolds without focal points. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021057

[9]

Manfred Einsiedler, Elon Lindenstrauss. On measures invariant under diagonalizable actions: the Rank-One case and the general Low-Entropy method. Journal of Modern Dynamics, 2008, 2 (1) : 83-128. doi: 10.3934/jmd.2008.2.83

[10]

Woocheol Choi, Youngwoo Koh. On the splitting method for the nonlinear Schrödinger equation with initial data in $ H^1 $. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3837-3867. doi: 10.3934/dcds.2021019

[11]

Maolin Cheng, Yun Liu, Jianuo Li, Bin Liu. Nonlinear Grey Bernoulli model NGBM (1, 1)'s parameter optimisation method and model application. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021054

[12]

Ondrej Budáč, Michael Herrmann, Barbara Niethammer, Andrej Spielmann. On a model for mass aggregation with maximal size. Kinetic & Related Models, 2011, 4 (2) : 427-439. doi: 10.3934/krm.2011.4.427

[13]

Sel Ly, Nicolas Privault. Stochastic ordering by g-expectations. Probability, Uncertainty and Quantitative Risk, 2021, 6 (1) : 61-98. doi: 10.3934/puqr.2021004

[14]

Eric Babson and Dmitry N. Kozlov. Topological obstructions to graph colorings. Electronic Research Announcements, 2003, 9: 61-68.

[15]

Rui Wang, Rundong Zhao, Emily Ribando-Gros, Jiahui Chen, Yiying Tong, Guo-Wei Wei. HERMES: Persistent spectral graph software. Foundations of Data Science, 2021, 3 (1) : 67-97. doi: 10.3934/fods.2021006

[16]

Mikhail Gilman, Semyon Tsynkov. Statistical characterization of scattering delay in synthetic aperture radar imaging. Inverse Problems & Imaging, 2020, 14 (3) : 511-533. doi: 10.3934/ipi.2020024

[17]

Kha Van Huynh, Barbara Kaltenbacher. Some application examples of minimization based formulations of inverse problems and their regularization. Inverse Problems & Imaging, 2021, 15 (3) : 415-443. doi: 10.3934/ipi.2020074

[18]

Suzete Maria Afonso, Vanessa Ramos, Jaqueline Siqueira. Equilibrium states for non-uniformly hyperbolic systems: Statistical properties and analyticity. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021045

[19]

Mingchao Zhao, You-Wei Wen, Michael Ng, Hongwei Li. A nonlocal low rank model for poisson noise removal. Inverse Problems & Imaging, 2021, 15 (3) : 519-537. doi: 10.3934/ipi.2021003

[20]

Bo Tan, Qinglong Zhou. Approximation properties of Lüroth expansions. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2873-2890. doi: 10.3934/dcds.2020389

2019 Impact Factor: 1.373

Metrics

  • PDF downloads (99)
  • HTML views (0)
  • Cited by (5)

Other articles
by authors

[Back to Top]