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

Braxton Osting; Jérôme Darbon; Stanley Osher

doi:10.3934/ipi.2013.7.907

Previous Article
A texture model based on a concentration of measure
IPI Home
This Issue
Next Article
Multi-view foreground segmentation via fourth order tensor learning

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

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

Braxton Osting ^1, , Jérôme Darbon ^1, and Stanley Osher ^2,

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

Abstract
Related Papers

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.

Keywords: graph-cut method., Kemeny-Snell ordering, rank aggregation, Statistical ranking, HodgeRank, $l^{1}$-norm minimization.

Mathematics Subject Classification: 62F07, 65F10, 05C20, 58A14, 05C8.

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]	J.-P. Aubin and A. Cellina, "Differential Inclusions. Set-Valued Maps and Viability Theory,", Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 264 (1984). doi: 10.1007/978-3-642-69512-4. Google Scholar
[2]	I. Ali, W. D. Cook and M. Kress, Ordinal ranking and intensity of preference: A linear programming approach,, Management Science, 32 (1986), 1642. doi: 10.1287/mnsc.32.12.1642. Google Scholar
[3]	R. Ahuja, D. Hochbaum and J. Orlin, Solving the convex cost integer dual network flow problem,, Management Science, 49 (2003), 950. Google Scholar
[4]	R. K Ahuja, T. L. Magnanti and J. B. Orlin, "Network Flows: Theory, Algorithms and Applications,", Prentice Hall, (1993). Google Scholar
[5]	, 2011 ATP world tour media guide,, accessed 10/5/2011. Available from: , (). Google Scholar
[6]	J. M. Bioucas-Dias and G. Valadao, Phase unwrapping via graph cuts,, IEEE Transactions on Image Processing, 16 (2007), 698. doi: 10.1109/TIP.2006.888351. Google Scholar
[7]	Y. Boykov and V. Kolmogorov, An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 26 (2004), 1124. Google Scholar
[8]	Y. Boykov, O. Veksler and R. Zabih, Fast approximate energy minimization via graph cuts,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 23 (2001), 1222. Google Scholar
[9]	I. Charon and O. Hudry, A survey on the linear ordering problem for weighted or unweighted tournaments,, 4OR, 5 (2007), 5. doi: 10.1007/s10288-007-0036-6. Google Scholar
[10]	W. D. Cook and M. Kress, Ordinal ranking with intensity preference,, Management Science, 31 (1985), 26. doi: 10.1287/mnsc.31.1.26. Google Scholar
[11]	E. Candes and T. Tao, Near optimal signal recovery from random projections: Univeral encoding strategies?,, IEEE Transactions on Information Theory, 52 (2006), 5406. doi: 10.1109/TIT.2006.885507. Google Scholar
[12]	J. Darbon, "Composants Logiciels et Algorithmes de Minimisation Exacte d'Énergies dÉdiés au Traitement des Images,", Ph.D. thesis, (2005). Google Scholar
[13]	H. A. David, "The Method of Paired Comparisons,", Hafner Publishing Co., (1963). Google Scholar
[14]	, C. Dwork, R. Kumar, M. Naor and D. Sivakumar,, Rank aggregation revisited., (). Google Scholar
[15]	_______, Rank aggregation methods for the web,, Proceedings International Conference World Wide Web (WWW'01), 10 (2001), 613. Google Scholar
[16]	L. R. Foulds, "Graph Theory Applications,", Universitext, (1992). doi: 10.1007/978-1-4612-0933-1. Google Scholar
[17]	M. Grant and S. Boyd, Graph implementations for nonsmooth convex programs,, in, 371 (2008), 95. doi: 10.1007/978-1-84800-155-8_7. Google Scholar
[18]	______, CVX: Matlab software for disciplined convex programming, version 1.21,, April, (2011). Google Scholar
[19]	D. Goldfarb and G. Iyengar, Robust portfolio selection problems,, Mathematics of Operations Research, 28 (2003), 1. doi: 10.1287/moor.28.1.1.14260. Google Scholar
[20]	D. F. Gleich and L.-H. Lim, Rank aggregation via nuclear norm minimization,, in, (2011), 60. doi: 10.1145/2020408.2020425. Google Scholar
[21]	D. Harville, The use of linear-model methodology to rate high school or college football teams,, Journal of the American Statistical Association, 72 (1977), 278. Google Scholar
[22]	A. N. Hirani, K. Kalyanaraman and S. Watts, Least squares ranking on graphs,, , (2011). Google Scholar
[23]	D. S. Hochbaum and E. Moreno-Centeno, Country credit-risk rating aggregation via the separation-deviation model,, Optimization Methods and Software, 23 (2008), 741. doi: 10.1080/10556780802402432. Google Scholar
[24]	D. S. Hochbaum, The separation and separation-deviation methodology for group decision making and aggregate ranking,, TutORials in Operations Research, 7 (2010), 116. Google Scholar
[25]	, Jester: The online joke recommender,, accessed 9/9/2011. Available from: , (). Google Scholar
[26]	X. Jiang, L.-H. Lim, Y. Yao and Y. Ye, Statistical ranking and combinatorial Hodge theory,, Math. Program. Ser. B, 127 (2011), 203. doi: 10.1007/s10107-010-0419-x. Google Scholar
[27]	J. G. Kemeny and J. L. Snell, "Mathematical Models in the Social Sciences,", The MIT Press, (1962). Google Scholar
[28]	V. Kolmogorov and A. Shioura, New algorithms for convex cost tension problem with application to computer vision,, Discrete Optimization, 6 (2009), 378. doi: 10.1016/j.disopt.2009.04.006. Google Scholar
[29]	V. Kolmogorov and R. Zabih, What energy functions can be minimized via graph cuts?,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2 (2004), 147. Google Scholar
[30]	J. I. Marden, "Analyzing and Modeling Rank Data,", Monographs on Statistics and Applied Probability, 64 (1995). Google Scholar
[31]	W. Ma, J.-M. Morel, S. Osher and A. Chien, An l1-based model for retinex theory and its application to medical images,, IEEE Conference on Computer Vision and Pattern Recognition, (2011), 153. Google Scholar
[32]	K. Murota, "Discrete Convex Optimization,", SIAM Society for Industrial and Applied Mathematics, (2003). Google Scholar
[33]	R. T. Rockafellar, "Convex Analysis,", Princeton Mathematical Series, (1970). Google Scholar
[34]	R. T. Rockafellar, "Network Flows and Monotropic Optimization,", Pure and Applied Mathematics (New York), (1984). Google Scholar
[35]	D. G. Saari, Mathematical structure of voting paradoxes. I. Pairwise votes,, Economic Theory, 15 (2000), 1. doi: 10.1007/s001990050001. Google Scholar
[36]	, Scrapy web crawling framework,, accessed 10/5/2011. Available from: , (). Google Scholar
[37]	R. T. Stefani, Football and basketball predictions using least squares,, IEEE Transactions on Systems, 7 (1977), 117. Google Scholar
[38]	, Tennis datenbank website,, accessed 10/5/2011. Available from: , (). Google Scholar
[39]	N. M. Tran, Pairwise ranking: Choice of method can produce arbitrarily different rank order,, Linear Algebra Appl., 438 (2013), 1012. doi: 10.1016/j.laa.2012.08.028. Google Scholar
[40]	_______, Hodgerank is the limit of Perron Rank,, preprint, (2012). Google Scholar
[41]	Q. Xu, Y. Yao, T. Jiang, Q. Huang, B. Yan and W. Lin, Random partial paired comparison for subjective video quality assessment via hodgerank,, in, (2011), 393. 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]	H. P. Young, Condorcet's theory of voting,, The American Political Science Review, 82 (1988), 1231. Google Scholar

show all references

References:

[1]	J.-P. Aubin and A. Cellina, "Differential Inclusions. Set-Valued Maps and Viability Theory,", Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 264 (1984). doi: 10.1007/978-3-642-69512-4. Google Scholar
[2]	I. Ali, W. D. Cook and M. Kress, Ordinal ranking and intensity of preference: A linear programming approach,, Management Science, 32 (1986), 1642. doi: 10.1287/mnsc.32.12.1642. Google Scholar
[3]	R. Ahuja, D. Hochbaum and J. Orlin, Solving the convex cost integer dual network flow problem,, Management Science, 49 (2003), 950. Google Scholar
[4]	R. K Ahuja, T. L. Magnanti and J. B. Orlin, "Network Flows: Theory, Algorithms and Applications,", Prentice Hall, (1993). Google Scholar
[5]	, 2011 ATP world tour media guide,, accessed 10/5/2011. Available from: , (). Google Scholar
[6]	J. M. Bioucas-Dias and G. Valadao, Phase unwrapping via graph cuts,, IEEE Transactions on Image Processing, 16 (2007), 698. doi: 10.1109/TIP.2006.888351. Google Scholar
[7]	Y. Boykov and V. Kolmogorov, An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 26 (2004), 1124. Google Scholar
[8]	Y. Boykov, O. Veksler and R. Zabih, Fast approximate energy minimization via graph cuts,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 23 (2001), 1222. Google Scholar
[9]	I. Charon and O. Hudry, A survey on the linear ordering problem for weighted or unweighted tournaments,, 4OR, 5 (2007), 5. doi: 10.1007/s10288-007-0036-6. Google Scholar
[10]	W. D. Cook and M. Kress, Ordinal ranking with intensity preference,, Management Science, 31 (1985), 26. doi: 10.1287/mnsc.31.1.26. Google Scholar
[11]	E. Candes and T. Tao, Near optimal signal recovery from random projections: Univeral encoding strategies?,, IEEE Transactions on Information Theory, 52 (2006), 5406. doi: 10.1109/TIT.2006.885507. Google Scholar
[12]	J. Darbon, "Composants Logiciels et Algorithmes de Minimisation Exacte d'Énergies dÉdiés au Traitement des Images,", Ph.D. thesis, (2005). Google Scholar
[13]	H. A. David, "The Method of Paired Comparisons,", Hafner Publishing Co., (1963). Google Scholar
[14]	, C. Dwork, R. Kumar, M. Naor and D. Sivakumar,, Rank aggregation revisited., (). Google Scholar
[15]	_______, Rank aggregation methods for the web,, Proceedings International Conference World Wide Web (WWW'01), 10 (2001), 613. Google Scholar
[16]	L. R. Foulds, "Graph Theory Applications,", Universitext, (1992). doi: 10.1007/978-1-4612-0933-1. Google Scholar
[17]	M. Grant and S. Boyd, Graph implementations for nonsmooth convex programs,, in, 371 (2008), 95. doi: 10.1007/978-1-84800-155-8_7. Google Scholar
[18]	______, CVX: Matlab software for disciplined convex programming, version 1.21,, April, (2011). Google Scholar
[19]	D. Goldfarb and G. Iyengar, Robust portfolio selection problems,, Mathematics of Operations Research, 28 (2003), 1. doi: 10.1287/moor.28.1.1.14260. Google Scholar
[20]	D. F. Gleich and L.-H. Lim, Rank aggregation via nuclear norm minimization,, in, (2011), 60. doi: 10.1145/2020408.2020425. Google Scholar
[21]	D. Harville, The use of linear-model methodology to rate high school or college football teams,, Journal of the American Statistical Association, 72 (1977), 278. Google Scholar
[22]	A. N. Hirani, K. Kalyanaraman and S. Watts, Least squares ranking on graphs,, , (2011). Google Scholar
[23]	D. S. Hochbaum and E. Moreno-Centeno, Country credit-risk rating aggregation via the separation-deviation model,, Optimization Methods and Software, 23 (2008), 741. doi: 10.1080/10556780802402432. Google Scholar
[24]	D. S. Hochbaum, The separation and separation-deviation methodology for group decision making and aggregate ranking,, TutORials in Operations Research, 7 (2010), 116. Google Scholar
[25]	, Jester: The online joke recommender,, accessed 9/9/2011. Available from: , (). Google Scholar
[26]	X. Jiang, L.-H. Lim, Y. Yao and Y. Ye, Statistical ranking and combinatorial Hodge theory,, Math. Program. Ser. B, 127 (2011), 203. doi: 10.1007/s10107-010-0419-x. Google Scholar
[27]	J. G. Kemeny and J. L. Snell, "Mathematical Models in the Social Sciences,", The MIT Press, (1962). Google Scholar
[28]	V. Kolmogorov and A. Shioura, New algorithms for convex cost tension problem with application to computer vision,, Discrete Optimization, 6 (2009), 378. doi: 10.1016/j.disopt.2009.04.006. Google Scholar
[29]	V. Kolmogorov and R. Zabih, What energy functions can be minimized via graph cuts?,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2 (2004), 147. Google Scholar
[30]	J. I. Marden, "Analyzing and Modeling Rank Data,", Monographs on Statistics and Applied Probability, 64 (1995). Google Scholar
[31]	W. Ma, J.-M. Morel, S. Osher and A. Chien, An l1-based model for retinex theory and its application to medical images,, IEEE Conference on Computer Vision and Pattern Recognition, (2011), 153. Google Scholar
[32]	K. Murota, "Discrete Convex Optimization,", SIAM Society for Industrial and Applied Mathematics, (2003). Google Scholar
[33]	R. T. Rockafellar, "Convex Analysis,", Princeton Mathematical Series, (1970). Google Scholar
[34]	R. T. Rockafellar, "Network Flows and Monotropic Optimization,", Pure and Applied Mathematics (New York), (1984). Google Scholar
[35]	D. G. Saari, Mathematical structure of voting paradoxes. I. Pairwise votes,, Economic Theory, 15 (2000), 1. doi: 10.1007/s001990050001. Google Scholar
[36]	, Scrapy web crawling framework,, accessed 10/5/2011. Available from: , (). Google Scholar
[37]	R. T. Stefani, Football and basketball predictions using least squares,, IEEE Transactions on Systems, 7 (1977), 117. Google Scholar
[38]	, Tennis datenbank website,, accessed 10/5/2011. Available from: , (). Google Scholar
[39]	N. M. Tran, Pairwise ranking: Choice of method can produce arbitrarily different rank order,, Linear Algebra Appl., 438 (2013), 1012. doi: 10.1016/j.laa.2012.08.028. Google Scholar
[40]	_______, Hodgerank is the limit of Perron Rank,, preprint, (2012). Google Scholar
[41]	Q. Xu, Y. Yao, T. Jiang, Q. Huang, B. Yan and W. Lin, Random partial paired comparison for subjective video quality assessment via hodgerank,, in, (2011), 393. 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]	H. P. Young, Condorcet's theory of voting,, The American Political Science Review, 82 (1988), 1231. Google Scholar

[1]	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, , () : -. doi: 10.3934/ipi.2021001
[2]	Hongfei Yang, Xiaofeng Ding, Raymond Chan, Hui Hu, Yaxin Peng, Tieyong Zeng. A new initialization method based on normed statistical spaces in deep networks. Inverse Problems & Imaging, 2021, 15 (1) : 147-158. doi: 10.3934/ipi.2020045
[3]	Tengfei Yan, Qunying Liu, Bowen Dou, Qing Li, Bowen Li. An adaptive dynamic programming method for torque ripple minimization of PMSM. Journal of Industrial & Management Optimization, 2021, 17 (2) : 827-839. doi: 10.3934/jimo.2019136
[4]	Qiang Fu, Xin Guo, Sun Young Jeon, Eric N. Reither, Emma Zang, Kenneth C. Land. The uses and abuses of an age-period-cohort method: On the linear algebra and statistical properties of intrinsic and related estimators. Mathematical Foundations of Computing, 2020 doi: 10.3934/mfc.2021001
[5]	El Haj Laamri, Michel Pierre. Stationary reaction-diffusion systems in $ L^1 $ revisited. Discrete & Continuous Dynamical Systems - S, 2021, 14 (2) : 455-464. doi: 10.3934/dcdss.2020355
[6]	Waixiang Cao, Lueling Jia, Zhimin Zhang. A $ C^1 $ Petrov-Galerkin method and Gauss collocation method for 1D general elliptic problems and superconvergence. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 81-105. doi: 10.3934/dcdsb.2020327
[7]	Zongyuan Li, Weinan Wang. Norm inflation for the Boussinesq system. Discrete & Continuous Dynamical Systems - B, 2020 doi: 10.3934/dcdsb.2020353
[8]	Weinan E, Weiguo Gao. Orbital minimization with localization. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 249-264. doi: 10.3934/dcds.2009.23.249
[9]	Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077
[10]	Gökhan Mutlu. On the quotient quantum graph with respect to the regular representation. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020295
[11]	Yunping Jiang. Global graph of metric entropy on expanding Blaschke products. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1469-1482. doi: 10.3934/dcds.2020325
[12]	Shasha Hu, Yihong Xu, Yuhan Zhang. Second-Order characterizations for set-valued equilibrium problems with variable ordering structures. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020164
[13]	Mingchao Zhao, You-Wei Wen, Michael Ng, Hongwei Li. A nonlocal low rank model for poisson noise removal. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021003
[14]	Huiying Fan, Tao Ma. Parabolic equations involving Laguerre operators and weighted mixed-norm estimates. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5487-5508. doi: 10.3934/cpaa.2020249
[15]	Xiaoming Wang. Upper semi-continuity of stationary statistical properties of dissipative systems. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 521-540. doi: 10.3934/dcds.2009.23.521
[16]	Ferenc Weisz. Dual spaces of mixed-norm martingale hardy spaces. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020285
[17]	Vaibhav Mehandiratta, Mani Mehra, Günter Leugering. Fractional optimal control problems on a star graph: Optimality system and numerical solution. Mathematical Control & Related Fields, 2021, 11 (1) : 189-209. doi: 10.3934/mcrf.2020033
[18]	Bo Tan, Qinglong Zhou. Approximation properties of Lüroth expansions. Discrete & Continuous Dynamical Systems - A, 2020 doi: 10.3934/dcds.2020389
[19]	Kha Van Huynh, Barbara Kaltenbacher. Some application examples of minimization based formulations of inverse problems and their regularization. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020074
[20]	Helin Guo, Huan-Song Zhou. Properties of the minimizers for a constrained minimization problem arising in Kirchhoff equation. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1023-1050. doi: 10.3934/dcds.2020308

2019 Impact Factor: 1.373

American Institute of Mathematical Sciences

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

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

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

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors