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, Springer-Verlag, Berlin, 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-1647. 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-964. Google Scholar
[4]	R. K Ahuja, T. L. Magnanti and J. B. Orlin, "Network Flows: Theory, Algorithms and Applications," 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]	J. M. Bioucas-Dias and G. Valadao, Phase unwrapping via graph cuts, IEEE Transactions on Image Processing, 16 (2007), 698-709. 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-1137. 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-1239. Google Scholar
[9]	I. Charon and O. Hudry, A survey on the linear ordering problem for weighted or unweighted tournaments, 4OR, 5 (2007), 5-60. 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-32. 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-5425. 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, Ecole Nationale Supérieure des Télćommunications, October, 2005. Google Scholar
[13]	H. A. David, "The Method of Paired Comparisons," Hafner Publishing Co., New York, 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-622. Google Scholar
[16]	L. R. Foulds, "Graph Theory Applications," Universitext, Springer-Verlag, New York, 1992. doi: 10.1007/978-1-4612-0933-1. Google Scholar
[17]	M. Grant and S. Boyd, Graph implementations for nonsmooth convex programs, 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]	______, CVX: Matlab software for disciplined convex programming, version 1.21, April, 2011. Available from: http://cvxr.com/cvx. Google Scholar
[19]	D. Goldfarb and G. Iyengar, Robust portfolio selection problems, Mathematics of Operations Research, 28 (2003), 1-38. 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 "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]	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-289. Google Scholar
[22]	A. N. Hirani, K. Kalyanaraman and S. Watts, Least squares ranking on graphs, arXiv:1011.1716v4, (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-762. 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-141. 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-244. 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-393. 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-159. Google Scholar
[30]	J. I. Marden, "Analyzing and Modeling Rank Data," Monographs on Statistics and Applied Probability, 64, Chapman & Hall, London, 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-160. 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, No. 28, Princeton University Press, Princeton, NJ, 1970. Google Scholar
[34]	R. T. Rockafellar, "Network Flows and Monotropic Optimization," Pure and Applied Mathematics (New York), A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York, 1984. Google Scholar
[35]	D. G. Saari, Mathematical structure of voting paradoxes. I. Pairwise votes, 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]	R. T. Stefani, Football and basketball predictions using least squares, 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]	N. M. Tran, Pairwise ranking: Choice of method can produce arbitrarily different rank order, Linear Algebra Appl., 438 (2013), 1012-1024. doi: 10.1016/j.laa.2012.08.028. Google Scholar
[40]	_______, Hodgerank is the limit of Perron Rank, preprint, arXiv:1201.4632, (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 "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]	H. P. Young, Condorcet's theory of voting, The American Political Science Review, 82 (1988), 1231-1244. 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, Springer-Verlag, Berlin, 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-1647. 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-964. Google Scholar
[4]	R. K Ahuja, T. L. Magnanti and J. B. Orlin, "Network Flows: Theory, Algorithms and Applications," 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]	J. M. Bioucas-Dias and G. Valadao, Phase unwrapping via graph cuts, IEEE Transactions on Image Processing, 16 (2007), 698-709. 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-1137. 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-1239. Google Scholar
[9]	I. Charon and O. Hudry, A survey on the linear ordering problem for weighted or unweighted tournaments, 4OR, 5 (2007), 5-60. 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-32. 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-5425. 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, Ecole Nationale Supérieure des Télćommunications, October, 2005. Google Scholar
[13]	H. A. David, "The Method of Paired Comparisons," Hafner Publishing Co., New York, 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-622. Google Scholar
[16]	L. R. Foulds, "Graph Theory Applications," Universitext, Springer-Verlag, New York, 1992. doi: 10.1007/978-1-4612-0933-1. Google Scholar
[17]	M. Grant and S. Boyd, Graph implementations for nonsmooth convex programs, 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]	______, CVX: Matlab software for disciplined convex programming, version 1.21, April, 2011. Available from: http://cvxr.com/cvx. Google Scholar
[19]	D. Goldfarb and G. Iyengar, Robust portfolio selection problems, Mathematics of Operations Research, 28 (2003), 1-38. 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 "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]	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-289. Google Scholar
[22]	A. N. Hirani, K. Kalyanaraman and S. Watts, Least squares ranking on graphs, arXiv:1011.1716v4, (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-762. 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-141. 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-244. 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-393. 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-159. Google Scholar
[30]	J. I. Marden, "Analyzing and Modeling Rank Data," Monographs on Statistics and Applied Probability, 64, Chapman & Hall, London, 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-160. 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, No. 28, Princeton University Press, Princeton, NJ, 1970. Google Scholar
[34]	R. T. Rockafellar, "Network Flows and Monotropic Optimization," Pure and Applied Mathematics (New York), A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York, 1984. Google Scholar
[35]	D. G. Saari, Mathematical structure of voting paradoxes. I. Pairwise votes, 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]	R. T. Stefani, Football and basketball predictions using least squares, 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]	N. M. Tran, Pairwise ranking: Choice of method can produce arbitrarily different rank order, Linear Algebra Appl., 438 (2013), 1012-1024. doi: 10.1016/j.laa.2012.08.028. Google Scholar
[40]	_______, Hodgerank is the limit of Perron Rank, preprint, arXiv:1201.4632, (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 "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]	H. P. Young, Condorcet's theory of voting, The American Political Science Review, 82 (1988), 1231-1244. Google Scholar

[1]	Duo Wang, Zheng-Fen Jin, Youlin Shang. A penalty decomposition method for nuclear norm minimization with l₁ norm fidelity term. Evolution Equations & Control Theory, 2019, 8 (4) : 695-708. doi: 10.3934/eect.2019034
[2]	Lei Wu, Zhe Sun. A new spectral method for $l_1$-regularized minimization. Inverse Problems & Imaging, 2015, 9 (1) : 257-272. doi: 10.3934/ipi.2015.9.257
[3]	Zhengshan Dong, Jianli Chen, Wenxing Zhu. Homotopy method for matrix rank minimization based on the matrix hard thresholding method. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 211-224. doi: 10.3934/naco.2019015
[4]	Yu-Ning Yang, Su Zhang. On linear convergence of projected gradient method for a class of affine rank minimization problems. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1507-1519. doi: 10.3934/jimo.2016.12.1507
[5]	Pia Heins, Michael Moeller, Martin Burger. Locally sparse reconstruction using the $l^{1,\infty}$-norm. Inverse Problems & Imaging, 2015, 9 (4) : 1093-1137. doi: 10.3934/ipi.2015.9.1093
[6]	P. R. Zingano. Asymptotic behavior of the $L^1$ norm of solutions to nonlinear parabolic equations. Communications on Pure & Applied Analysis, 2004, 3 (1) : 151-159. doi: 10.3934/cpaa.2004.3.151
[7]	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
[8]	Yingying Li, Stanley Osher, Richard Tsai. Heat source identification based on $l_1$ constrained minimization. Inverse Problems & Imaging, 2014, 8 (1) : 199-221. doi: 10.3934/ipi.2014.8.199
[9]	Ming Yang, Dunren Che, Wen Liu, Zhao Kang, Chong Peng, Mingqing Xiao, Qiang Cheng. On identifiability of 3-tensors of multilinear rank $(1,\ L_{r},\ L_{r})$. Big Data & Information Analytics, 2016, 1 (4) : 391-401. doi: 10.3934/bdia.2016017
[10]	Blaine Keetch, Yves van Gennip. A Max-Cut approximation using a graph based MBO scheme. Discrete & Continuous Dynamical Systems - B, 2019, 24 (11) : 6091-6139. doi: 10.3934/dcdsb.2019132
[11]	Lidan Li, Hongwei Zhang, Liwei Zhang. Inverse quadratic programming problem with $ l_1 $ norm measure. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2425-2437. doi: 10.3934/jimo.2019061
[12]	Yingying Li, Stanley Osher. Coordinate descent optimization for l¹ minimization with application to compressed sensing; a greedy algorithm. Inverse Problems & Imaging, 2009, 3 (3) : 487-503. doi: 10.3934/ipi.2009.3.487
[13]	Zhaohui Guo, Stanley Osher. Template matching via $l_1$ minimization and its application to hyperspectral data. Inverse Problems & Imaging, 2011, 5 (1) : 19-35. doi: 10.3934/ipi.2011.5.19
[14]	Song Li, Junhong Lin. Compressed sensing with coherent tight frames via $l_q$-minimization for $0 < q \leq 1$. Inverse Problems & Imaging, 2014, 8 (3) : 761-777. doi: 10.3934/ipi.2014.8.761
[15]	Jiying Liu, Jubo Zhu, Fengxia Yan, Zenghui Zhang. Compressive sampling and $l_1$ minimization for SAR imaging with low sampling rate. Inverse Problems & Imaging, 2013, 7 (4) : 1295-1305. doi: 10.3934/ipi.2013.7.1295
[16]	Vladimir Gaitsgory, Tanya Tarnopolskaya. Threshold value of the penalty parameter in the minimization of $L_1$-penalized conditional value-at-risk. Journal of Industrial & Management Optimization, 2013, 9 (1) : 191-204. doi: 10.3934/jimo.2013.9.191
[17]	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
[18]	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
[19]	Yunhai Xiao, Soon-Yi Wu, Bing-Sheng He. A proximal alternating direction method for $\ell_{2,1}$-norm least squares problem in multi-task feature learning. Journal of Industrial & Management Optimization, 2012, 8 (4) : 1057-1069. doi: 10.3934/jimo.2012.8.1057
[20]	Karina Samvelyan, Frol Zapolsky. Rigidity of the ${{L}^{p}}$-norm of the Poisson bracket on surfaces. Electronic Research Announcements, 2017, 24: 28-37. doi: 10.3934/era.2017.24.004

2020 Impact Factor: 1.639

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